データサイエンスとデータベース
干し草の山の中の針：気の利いた大規模なテキスト検索アルゴリズムのチュートリアル
「テキスト検索」という用語に出くわすと、通常、ユーザーが入力したときに1つ以上の検索用語をすばやく検索できるように索引付けされた大量のテキストを思い浮かべます。これはの古典的な問題です コンピューター科学者 、多くのソリューションが存在します。
しかし、逆のシナリオはどうですか？事前にインデックスを作成できるのが検索フレーズのグループであり、実行時にのみ大量のテキストが検索用に表示される場合はどうなりますか？これらの質問は、このトライデータ構造チュートリアルが対処しようとしているものです。
アプリケーション
このシナリオの実際のアプリケーションは、いくつかの医学論文を病状のリストと照合し、どの論文がどの病状について議論しているかを調べることです。別の例は、司法判例の大規模なコレクションを横断し、それらが参照する法律を抽出することです。
直接アプローチ
最も基本的なアプローチは、検索フレーズをループし、各フレーズのテキストを1つずつ検索することです。このアプローチはうまく拡張できません。別の文字列内の文字列の検索は複雑です オン） 。のためにそれを繰り返す m 検索フレーズはひどいにつながります O（m * n） 。
次のC＃スニペットで明らかなように、実装が簡単な直接アプローチの（おそらく唯一の）利点：
String[] search_phrases = File.ReadAllLines ('terms.txt'); String text_body = File.ReadAllText('body.txt'); int count = 0; foreach (String phrase in search_phrases) if (text_body.IndexOf (phrase) >= 0) ++count; 私の開発マシンでこのコードを実行する [1] テストサンプルに対して [2] 、私は1時間14分の実行時間を取得しました。これは、コーヒーを飲み、起き上がってストレッチする必要がある時間、または開発者が作業をスキップするために使用するその他の言い訳をはるかに超えています。
より良いアプローチ-トライ
前のシナリオは、いくつかの方法で拡張できます。たとえば、検索プロセスは、複数のプロセッサ/コアで分割および並列化できます。ただし、このアプローチによって達成される実行時間の短縮（4プロセッサー/コアにわたる完全な分割を想定した合計実行時間は20分）は、コーディング/デバッグの複雑さの追加を正当化するものではありません。
最善の解決策は、テキスト本文を1回だけトラバースすることです。これには、1回のパスで、テキスト本文と並行して直線的に横断できる構造で検索フレーズにインデックスを付ける必要があり、最終的な複雑さを実現します。 オン） 。
このシナリオだけに特に適したデータ構造は、 トライ 。この用途の広いデータ構造は通常見過ごされており、検索の問題に関しては他のツリー関連の構造ほど有名ではありません。
試行に関するApeeScapeの以前のチュートリアル それらがどのように構造化され、使用されるかについての優れた紹介を提供します。つまり、トライは特別なツリーであり、ルートから任意のノードへのパスをトレースすると、そのシーケンスの有効なサブセットが生成されるように、値のシーケンスを格納できます。
したがって、すべての検索フレーズを1つのトライに組み合わせることができ、各ノードに単語が含まれている場合、ルートから任意のパスを経由して下にトレースするだけで有効な検索フレーズが生成される構造にフレーズが配置されます。
トライの利点は、検索時間を大幅に短縮できることです。このトライチュートリアルの目的のために理解しやすくするために、二分木を想像してみましょう。二分木のトラバースには、次のような複雑さがあります。 O（ログ2n） 、各ノードが2つに分岐するため、残りのトラバーサルを半分にカットします。そのため、三分木はトラバーサルの複雑さが O（ログ3n） 。ただし、トライでは、子ノードの数はそれが表すシーケンスによって決定され、読みやすい/意味のあるテキストの場合、通常、子ノードの数は多くなります。
テキスト検索アルゴリズム
簡単な例として、次の検索フレーズを想定します。
- 「同じ家族」
- 「別の家族」
- 「別の存在」
- 「リーグのメンバー」
検索フレーズは事前に知っていることを忘れないでください。したがって、トライの形式でインデックスを作成することから始めます。
データを視覚的に表現するための便利な方法
後で、私たちのソフトウェアのユーザーは、次のテキストを含むファイルを提示します。
ヨーロッパの言語は同じ家族の一員です。それらの別個の存在は神話です。
残りは非常に簡単です。私たちのアルゴリズムには2つのインジケーター（必要に応じてポインター）があります。1つはルートまたはトライ構造の「開始」ノードで始まり、もう1つはテキスト本文の最初の単語で始まります。 2つのインジケーターは、単語ごとに一緒に移動します。テキストインジケータは単に前方に移動しますが、トライインジケータは一致する単語の軌跡をたどってトライを深さ方向に横断します。
トライインジケーターは、ブランチの終わりに到達したとき（検索フレーズが見つかったことを意味します）、または一致しない単語に遭遇したとき（一致するものが見つからなかった場合）の2つの場合に開始に戻ります。
テキストインジケータの移動の1つの例外は、部分的な一致が見つかった場合、つまり、一連の一致の後、ブランチが終了する前に不一致が発生した場合です。この場合、最後の単語が新しいブランチの始まりである可能性があるため、テキストインジケータは前方に移動されません。
このアルゴリズムをトライデータ構造の例に適用して、どのようになるかを見てみましょう。
| ステップ | トライインジケーター | テキストインジケータ | 一致？ | トライアクション | テキストアクション |
|---|---|---|---|---|---|
| 0 | 開始 | ザ・ | - | へ引っ越す 開始 | 次へ移動 |
| 1 | 開始 | ヨーロッパ人 | - | へ引っ越す 開始 | 次へ移動 |
| 2 | 開始 | 言語 | - | へ引っ越す 開始 | 次へ移動 |
| 3 | 開始 | です | - | へ引っ越す 開始 | 次へ移動 |
| 4 | 開始 | メンバー | メンバー | へ引っ越す メンバー | 次へ移動 |
| 5 | メンバー | の | の | へ引っ越す の | 次へ移動 |
| 6 | の | インクルード | インクルード | へ引っ越す インクルード | 次へ移動 |
| 7 | インクルード | 同じ | - | へ引っ越す 開始 | - |
| 8 | 開始 | 同じ | 同じ | へ引っ越す 同じ | 次へ移動 |
| 9 | 同じ | 家族 | 家族 | へ引っ越す 開始 | 次へ移動 |
| 10 | 開始 | 彼らの | - | へ引っ越す 開始 | 次へ移動 |
| 十一 | 開始 | 分ける | 分ける | へ引っ越す 分ける | 次へ移動 |
| 12 | 分ける | 存在 | 存在 | へ引っ越す 開始 | 次へ移動 |
| 13 | 開始 | です | - | へ引っ越す 開始 | 次へ移動 |
| 14 | 開始 | に | - | へ引っ越す 開始 | 次へ移動 |
| 15 | 開始 | 神話 | - | へ引っ越す 開始 | 次へ移動 |
ご覧のとおり、システムは2つの一致するフレーズを正常に検出します。 「同じ家族」 そして 「別の存在」 。
実際の例
最近のプロジェクトで、次の問題が発生しました。クライアントは、自分の仕事の分野に関連する多数の記事と博士論文を持っており、同じ分野に関連する特定のタイトルとルールを表すフレーズの独自のリストを生成しました。作業。
彼女のジレンマはこれでした：彼女のフレーズのリストを考えると、彼女はどのように記事/論文をそれらのフレーズにリンクしますか？最終的な目標は、フレーズのグループをランダムに選択し、それらの特定のフレーズに言及している記事/論文のリストをすぐに入手できるようにすることです。
前に説明したように、この問題を解決するには2つの部分があります。フレーズをトライにインデックス付けすることと、実際の検索です。次のセクションでは、C＃での簡単な実装について説明します。これらのスニペットは、この記事の範囲外であるため、ファイル処理、エンコードの問題、テキストのクリーンアップ、および同様の問題は処理されないことに注意してください。
インデックス作成
インデックス作成操作では、フレーズを1つずつトラバースし、ノード/レベルごとに1つの単語をトライに挿入します。ノードは次のクラスで表されます。
class Node { int PhraseId = -1; Dictionary Children = new Dictionary(); public Node() { } public Node(int id) { PhraseId = id; } } 各フレーズはIDで表されます。IDは増分数と同じくらい単純で、次のインデックス関数に渡されます（変数ルートはトライの実際のルートです）。
void addPhrase(ref Node root, String phrase, int phraseId) { // a pointer to traverse the trie without damaging // the original reference Node node = root; // break phrase into words String[] words = phrase.Split (); // start traversal at root for (int i = 0; i 検索中
検索プロセスは、上記のチュートリアルで説明したトライアルゴリズムの直接実装です。
void findPhrases(ref Node root, String textBody) { // a pointer to traverse the trie without damaging // the original reference Node node = root; // a list of found ids List foundPhrases = new List(); // break text body into words String[] words = textBody.Split (); // starting traversal at trie root and first // word in text body for (int i = 0; i パフォーマンス
ここに示されているコードは、実際のプロジェクトから抽出されたものであり、このドキュメントの目的のために簡略化されています。同じマシンでこのコードを再度実行する [1] と同じテストサンプルに対して [2] その結果、トライの構築に2.5秒、検索に0.3秒の実行時間が発生しました。休憩時間はこれだけですよね？
バリエーション
このトライチュートリアルで説明されているアルゴリズムは、特定のエッジケースで失敗する可能性があるため、事前定義された検索用語を念頭に置いて設計されていることを認識することが重要です。
たとえば、次のように、ある検索用語の先頭が別の検索用語の一部と同一である場合。
- 「」 共有する 友達と楽しむ」
- 「私は2枚のチケットを持っています 共有する 誰かと'
また、テキスト本文には、次のように、トライポインタが間違ったパスを開始する原因となるフレーズが含まれています。
友達と共有して楽しむためのチケットが2枚あります。
その場合、テキストインジケーターがテキスト本文の一致する用語の先頭を通過するまで、トライインジケーターは開始ノードに戻らないため、アルゴリズムはどの用語とも一致しません。
アルゴリズムを実装する前に、この種のエッジケースがアプリケーションで可能かどうかを検討することが重要です。その場合、アルゴリズムを追加のトライインジケーターで変更して、一度に1つの一致だけでなく、任意の時点ですべての一致を追跡できます。
結論
テキスト検索は、コンピュータサイエンスの深い分野です。問題と解決策が豊富な分野。私が処理しなければならなかった種類のデータ（23MBのテキストは実生活では大量の本です）はまれな出来事または特殊な問題のように見えるかもしれませんが、言語学の研究、アーカイブ、またはその他の種類のデータ操作を扱う開発者、定期的にはるかに大量のデータに遭遇します。
上記のトライデータ構造のチュートリアルで明らかなように、目前の問題に対して正しいアルゴリズムを慎重に選択することが非常に重要です。この特定のケースでは、トライアプローチにより、ランタイムが1時間以上から3秒未満に99.93％も大幅に削減されました。
これが唯一の効果的なアプローチというわけではありませんが、十分に単純であり、機能します。このアルゴリズムがおもしろいと思っていただければ幸いです。また、コーディング作業の成功を祈っています。
[1] このテストに使用されたマシンの仕様は次のとおりです。
- Intel i7 4700HQ
- 16GB RAM
テストは、.NET4.5.1を使用するWindows8.1と、最新バージョンのmonoを使用するKubuntu 14.04で実行され、結果は非常に似ていました。
[2] テストサンプルは、合計サイズが23.5MBの280Kの検索フレーズと、1.5MBのテキスト本文で構成されています。
