👋 はじめに
みなさんこんにちは！
今回は、文字列探索アルゴリズム（力まかせ法、KMP法、Boyer-Moore法）の動きを視覚的に理解できるWebアプリケーションを作成しました。この記事では、アルゴリズムの基礎知識から実装の工夫点まで詳しく解説します。
文字列探索は、テキストエディタの検索機能や全文検索エンジンなど、身近なアプリケーションで広く使われている技術です。しかし、アルゴリズムの動作を本だけで理解するのは難しいと感じたことはありませんか？
そこで本記事では、3つの代表的な文字列探索アルゴリズムを実際にステップ実行しながら学習できる可視化ツールを作成しました。
🎮 デモプレイ
💻 ソースコード
🔍 文字列探索とは
文字列探索とは、テキスト（長さ n）の中から特定のパターン（長さ m）を探し出す問題です。例えば、「ABCABDABC」というテキストから「ABD」というパターンを見つける処理が該当します。
この問題を効率的に解くために、様々なアルゴリズムが考案されてきました。
📚 本アプリで扱う3つのアルゴリズム
1. 力まかせ法（Brute-Force）
最もシンプルな探索手法です。テキストの各位置を起点として、パターンと1文字ずつ比較していきます。
動作の流れ
- テキストの先頭からパターンを重ねる
- 左から順に1文字ずつ比較
- 不一致があればパターンを1文字だけ右にずらす
- テキストの最後まで繰り返す
実装がシンプルで理解しやすい一方、不一致のたびに1文字しかずらさないため、多くの無駄な比較が発生します。
2. クヌース–モリス–プラット法（KMP法）
パターン内の接頭辞と接尾辞の一致情報を事前に計算し、不一致時に効率的にスキップする手法です。
動作の流れ
- パターンからLPS配列（Longest Proper Prefix which is also Suffix）を事前計算
- テキストとパターンを左から比較
- 不一致が発生したら、LPS配列を参照して次の比較位置を決定
- すでに一致した部分を再利用することで無駄な比較を削減
力まかせ法と異なり、すでに一致した部分の情報を活用できるため、効率が向上します。
3. ボイヤー・ムーア法（Boyer-Moore法）
パターンを右から左に比較し、不一致時に大きくスキップする手法です。実用的な場面で最も高速とされています。
動作の流れ
- Bad Character テーブルを事前計算（各文字がパターン末尾からどれだけ離れているか）
- パターンを右端から左に向かって比較
- 不一致が発生したら、Bad Character ルールに基づいて大幅にスキップ
- パターン長が長いほど効率が向上
右から比較することで、不一致が早期に発見でき、かつ大きくジャンプできるため高速です。
📊 アルゴリズムの比較
| アルゴリズム | 最良時間計算量 | 平均時間計算量 | 最悪時間計算量 | 空間計算量 | 特徴 |
|---|---|---|---|---|---|
| 力まかせ法 | O(n) | O(n×m) | O(n×m) | O(1) | シンプルだが非効率 |
| KMP法 | O(n) | O(n+m) | O(n+m) | O(m) | 一度一致した部分を再利用 |
| Boyer-Moore法 | O(n/m) | O(n+m) | O(n×m) | O(m) | 実用的に最速 |
アルゴリズム選択の指針
- パターンが短い場合や実装の簡潔さを重視する場合 → 力まかせ法
- 最悪ケースでも安定した性能が必要な場合 → KMP法
- 実用的な速度を重視する場合（特にパターンが長い） → Boyer-Moore法
📖 アプリケーションの使い方
🎯 シングルモード
- アルゴリズムを選択: プルダウンから探索アルゴリズムを選択
-
データパターンを選択: 以下の4種類から選択可能
- ランダム: ランダムな英数字の組み合わせ
- 反復パターン: パターンが繰り返し出現する文字列
- 部分一致多数: 部分一致が多く含まれる文字列
- 最悪ケース: アルゴリズムの最悪ケースとなる文字列
- データサイズを設定: テキスト長とパターン長をスライダーで調整
- テキストとパターンを入力: 自動生成されたデータを手動で編集も可能
- 実行ボタンをクリック: アニメーションが開始
- 速度調整: スライダーで実行速度を0.25x〜3.0xまで調整可能
- 一時停止・再開: 途中で停止して各ステップを確認できる
- リセット: 初期状態に戻す
⚖️ 比較モード
- 比較モードに切り替え: 画面上部の「比較モード」ボタンをクリック
- 左右のアルゴリズムを選択: それぞれ異なるアルゴリズムを選択
- データパターンとサイズを設定: 両方のアルゴリズムに同じデータが適用される
- 両方実行: 左右のアルゴリズムが同時に実行され、性能差が視覚的に分かる
🎨 可視化の見方
アニメーション中、各文字は以下のように色分けされます。
| 状態 | 色 | 意味 |
|---|---|---|
| 未処理 | 灰色 | まだ処理されていない文字 |
| 比較中 | 青色 | 現在比較中の文字 |
| 一致 | 緑色 | 一致した文字 |
| 不一致 | 赤色 | 不一致の文字 |
| 発見 | 黄色 | パターンが見つかった位置 |
| パターン位置 | 橙色 | 現在のパターン位置（Boyer-Moore用） |
また、画面には以下の統計情報がリアルタイムで表示されます。
- ステップ数: アルゴリズムの実行ステップ総数
- 比較回数: 文字比較を行った回数
- シフト回数: パターンをずらした回数
- 実行時間: アニメーション開始からの経過時間
- 一致位置: パターンが見つかった位置のリスト
💡 実装の工夫点
🎲 データ生成パターンによる学習支援
アルゴリズムの特性を理解するため、4種類のデータ生成パターンを用意しました。
ランダムデータでは平均的なケースを、反復パターンでは特定のアルゴリズムが得意とするケースを、部分一致多数では誤マッチが多発するケースを、最悪ケースでは計算量が最大になるケースを、それぞれ体験できます。
これらのパターンを切り替えることで、同じアルゴリズムでも入力データによって性能が大きく変わることを実感できるようになっています。
🎓 アプリで可視化することで得られる学習効果
👁️ アルゴリズムの動作を直感的に理解できる
教科書や解説記事でアルゴリズムを学ぶ場合、疑似コードやテキストベースの説明だけでは具体的な動きをイメージしにくいことがあります。
本アプリでは、各ステップで何が起こっているのかを色や位置の変化で視覚的に表現しているため、アルゴリズムの動作原理を直感的に理解できます。特に初学者にとって、抽象的な概念を具体的な動きとして見られることは大きな学習効果があります。
🚀 アルゴリズム間の性能差を体感できる
比較モードを使うことで、同じデータに対して異なるアルゴリズムがどのように振る舞うかを並べて観察できます。
力まかせ法が1文字ずつ丁寧に比較していく様子と、Boyer-Moore法が大きくジャンプして効率的に探索する様子を同時に見ることで、各アルゴリズムの特性が体感として理解できます。
🔄 入力データとアルゴリズムの相性を学べる
データパターンを切り替えることで、アルゴリズムの得意・不得意を実感できます。
例えば、最悪ケースのデータでは力まかせ法とKMP法の性能差が顕著に現れますし、ランダムデータではBoyer-Moore法の優位性が際立ちます。このように、理論的な計算量だけでなく、実際のデータ特性に応じた選択の重要性を学べます。
📈 計算量の意味を実践的に理解できる
リアルタイムで表示される統計情報により、計算量の違いが具体的な数値として確認できます。
O(n×m)とO(n+m)の差が、実際の比較回数やステップ数にどう現れるのかを目で見て理解することで、理論と実践を結びつける学習ができます。
⏯️ 自分のペースで学習を進められる
一時停止・再開機能により、理解が追いつかない部分で止めて考えたり、速度を調整して繰り返し観察したりできます。
また、手動でテキストやパターンを入力すれば、自分が確認したい特定のケースを試すこともできます。このように、受動的な学習ではなく、能動的に試行錯誤しながら理解を深められる点が本アプリの大きな特徴です。
🎉 まとめ
文字列探索アルゴリズムの可視化ツールを作成しました。React + TypeScriptの組み合わせにより、型安全で保守性の高い実装を実現しています。
可視化によって、アルゴリズムの動作原理や性能差を直感的に理解できるようになり、学習効果が大きく向上します。特に初学者の方や、アルゴリズムを視覚的に理解したい方には有用なツールになっているのではないかと思います。
もし興味があれば、ぜひ実際に動かしてみて、各アルゴリズムの特性を体感してみてください！