干し草の山の中の針：気の利いた大規模なテキスト検索アルゴリズムのチュートリアル

「テキスト検索」という用語に出くわすと、通常、ユーザーが入力したときに1つ以上の検索用語をすばやく検索できるように索引付けされた大量のテキストを思い浮かべます。 これは、多くの解決策が存在するコンピューター科学者にとって典型的な問題です。

しかし、逆のシナリオはどうですか？ 事前に索引付けに使用できるのが検索フレーズのグループであり、実行時にのみ大量のテキストが検索用に表示される場合はどうなりますか？ これらの質問は、このトライデータ構造チュートリアルが対処しようとしているものです。

アプリケーション

このシナリオの実際のアプリケーションは、いくつかの医学論文を病状のリストと照合し、どの論文がどの病状について議論しているかを調べることです。 別の例は、判例の大規模なコレクションを横断し、それらが参照する法律を抽出することです。

直接アプローチ

最も基本的なアプローチは、検索フレーズをループし、各フレーズのテキストを1つずつ検索することです。 このアプローチはうまく拡張できません。 別の文字列内の文字列を検索すると、複雑さがO（n）になります。 これを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回のパスで、テキスト本文と並行して線形に横断できる構造で検索フレーズにインデックスを付ける必要があり、 O（n）の最終的な複雑さを実現します。

このシナリオに特に適したデータ構造はtrieです。 この用途の広いデータ構造は通常見過ごされており、検索の問題に関しては他のツリー関連の構造ほど有名ではありません。

Toptalの以前の試行に関するチュートリアルは、それらがどのように構造化され、使用されるかについての優れた入門書を提供します。 要するに、トライは特別なツリーであり、ルートから任意のノードへのパスをトレースすると、そのシーケンスの有効なサブセットが生成されるように、値のシーケンスを格納できます。

したがって、すべての検索フレーズを1つのトライにまとめることができ、各ノードに単語が含まれている場合、ルートから下に向かって任意のパスをたどるだけで有効な検索フレーズが生成される構造にフレーズが配置されます。

トライの利点は、検索時間を大幅に短縮できることです。 このトライチュートリアルの目的のために理解しやすくするために、二分木を想像してみましょう。 各ノードが2つに分岐し、残りのトラバースが半分になるため、バイナリツリーのトラバースはO（log 2 n）の複雑さを持ちます。 そのため、三分探索木はO（log 3 n）の走査複雑度を持ちます。 ただし、トライでは、子ノードの数はそれが表すシーケンスによって決定され、読み取り可能で意味のあるテキストの場合、通常、子ノードの数は多くなります。

テキスト検索アルゴリズム

簡単な例として、次の検索フレーズを想定します。

• 「同じ家族」
• 「別の家族」
• 「別の存在」
• 「リーグのメンバー」

検索フレーズは事前に知っていることを忘れないでください。 したがって、トライの形式でインデックスを作成することから始めます。

後で、私たちのソフトウェアのユーザーは、次のテキストを含むファイルを提示します。

ヨーロッパの言語は同じ家族の一員です。 それらの別個の存在は神話です。

残りは非常に簡単です。 私たちのアルゴリズムには2つのインジケーター（必要に応じてポインター）があります。1つはルートまたはトライ構造の「開始」ノードで始まり、もう1つはテキスト本文の最初の単語で始まります。 2つのインジケーターは、単語ごとに一緒に移動します。 テキストインジケータは単に前方に移動し、トライインジケータは一致する単語の軌跡をたどってトライを深さ方向に横断します。

トライインジケーターは、2つの場合に開始に戻ります。ブランチの終わりに到達したとき、つまり検索フレーズが見つかったとき、または一致しない単語が見つかったとき、その場合は一致が見つかりませんでした。

テキストインジケータの移動の1つの例外は、部分一致が見つかった場合、つまり、一連の一致の後、分岐が終了する前に不一致が検出された場合です。 この場合、最後の単語が新しいブランチの始まりである可能性があるため、テキストインジケータは前方に移動されません。

このアルゴリズムをトライデータ構造の例に適用して、どのようになるかを見てみましょう。

ご覧のとおり、システムは「同じ家族」と「別の存在」という2つの一致するフレーズを正常に検出します。

実際の例

最近のプロジェクトでは、次の問題が発生しました。クライアントは、自分の仕事の分野に関連する多数の記事と博士論文を持っており、同じ分野に関連する特定のタイトルとルールを表す独自のフレーズのリストを生成しました。仕事。

彼女のジレンマはこれでした：彼女のフレーズのリストを考えると、彼女はどのように記事/論文をそれらのフレーズにリンクしますか？ 最終的な目標は、フレーズのグループをランダムに選択し、それらの特定のフレーズに言及している記事/論文のリストをすぐに入手できるようにすることです。

前に説明したように、この問題を解決するには2つの部分があります。フレーズをトライにインデックス付けすることと、実際の検索です。 次のセクションでは、C＃での簡単な実装について説明します。 これらのスニペットは、この記事の範囲外であるため、ファイル処理、エンコードの問題、テキストのクリーンアップ、および同様の問題は処理されないことに注意してください。

インデックス作成

インデックス作成操作では、フレーズを1つずつトラバースし、ノード/レベルごとに1つの単語をトライに挿入します。 ノードは次のクラスで表されます。

 class Node { int PhraseId = -1; Dictionary<String, Node> Children = new Dictionary<String, Node>(); public Node() { } public Node(int id) { PhraseId = 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 < words.Length; ++i) { // if the current word does not exist as a child // to current node, add it if (node.Children.ContainsKey(words[i]) == false) node.Children.Add(words[i], new Node()); // move traversal pointer to current word node = node.Children[words[i]]; // if current word is the last one, mark it with // phrase Id if (i == words.Length - 1) node.PhraseId = phraseId; } }

検索

検索プロセスは、上記のチュートリアルで説明したトライアルゴリズムの直接実装です。

 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<int> foundPhrases = new List<int>(); // 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 < words.Length;) { // if current node has current word as a child // move both node and words pointer forward if (node.Children.ContainsKey(words[i])) { // move trie pointer forward node = node.Children[words[i]]; // move words pointer forward ++i; } else { // current node does not have current // word in its children // if there is a phrase Id, then the previous // sequence of words matched a phrase, add Id to // found list if (node.PhraseId != -1) foundPhrases.Add(node.PhraseId); if (node == root) { // if trie pointer is already at root, increment // words pointer ++i; } else { // if not, leave words pointer at current word // and return trie pointer to root node = root; } } } // one case remains, word pointer as reached the end // and the loop is over but the trie pointer is pointing to // a phrase Id if (node.PhraseId != -1) foundPhrases.Add(node.PhraseId); }

パフォーマンス

ここに示されているコードは、実際のプロジェクトから抽出されたものであり、このドキュメントの目的のために簡略化されています。 このコードを同じマシン[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のテキスト本文で構成されています。