非常に大きなファイル数万のIDEで使用する高速部分文字列検索アルゴリズム

Question

私は何万という非常に大きな（テキスト）ファイルを扱うIDEと非常によく似たものを開発しています。主題の芸術の状態が何であるかを調査する。

例として、標準（正規表現ではない）式のIntellijの検索アルゴリズムはかなり直ぐです。彼らはどのようにこれを達成するのですか？検索可能なすべてのファイルのサフィックスツリーをメモリに保存していますか？彼らはメモリ内のファイルの内容のかなりの部分を保持しているだけなので、ディスクI/Oを避けるために、ほぼ完全にメモリ内の標準KMPを実行しますか？

おかげ

Answer 1

現在

、のIntelliJ IDEAのインデックスファイル、およびそのファイルで発生した3グラム（3つの文字または数字のシーケンス）覚えています。検索時には、クエリを3グラムに分割し、これらのすべてのトリグラムを含むインデックスからファイルを取得し、それらのセットを交差させ、それらのファイルのそれぞれに比較的簡単なテキスト検索を使用して、文字列。

Answer 2

あなたはApache Luceneを見てみることができます。これは、Javaで完全に書かれたテキスト検索エンジンライブラリです。あなたの使用には多少重すぎるかもしれませんが、オープンソースなので、その仕組みを見てみることができます。

demoを使用すると、インデックスを作成してライブラリのソースコードを検索することができます。これは、実行したいこととほぼ同じです。

また、Boyer-Moore文字列検索アルゴリズムを見てください。これは、です。明らかに、は、ctrl + fスタイルの文書検索を提供するアプリケーションで一般的に使用されています。これは、検索用語を事前処理することで、可能な限り比較を少なくすることができます。

Answer 3

js441はApache Luceneが良い選択肢だと指摘しましたが、あなたがGoogle検索の仕組みと同様に用語ベースの検索を行う場合にのみ必要です。 Luceneという用語にまたがる任意の文字列を検索する必要がある場合は、あなたを助けません。

後者の場合、ある種の接尾辞ツリーを構築する必要があります。あなたがサフィックスツリーを構築した後でできることは、それをファイルに書き込んでそれをメモリ空間にmmapすることです。こうすることで、ツリー全体をRAMに保存するメモリを無駄にすることはありませんが、自動的にキャッシュされたツリーの部分に頻繁にアクセスすることになります。 mmapの欠点は、最初の検索がやや遅いことです。また、ファイルが頻繁に変更されても、これは実行されません。

編集したファイルだけを検索する場合は、大量のファイルと最近編集したファイルの2つのインデックスを保持することができます。だからあなたが検索をするときは、両方のインデックスを検索します。新しいファイルの内容でパーマネントインデックスを定期的に再構築し、古いファイルを置き換える必要があります。ここで

はLuceneのが良いときと接尾辞木が良好な場合のいくつかの例は以下のとおりです。

次を含むドキュメントがあるとします。

速い茶色の犬は怠惰なキツネの上にジャンプしました。

のLuceneは、次の検索のために良いです：

あなたは次のことを行うことができます

• 迅速
• 速い茶色
• いくつかのトリックとのQ *

• のq * bの

  検索はうまくいく：

• '*嫌*自分の'

  検索のこのタイプは、

• 'Q *が嫌茶色のD *のG'

  非常に遅い実行され、検索のこのタイプは何

を見つけることはありません

• 「茶色のd」

  Luceneはあなたの文書を単語の袋として扱うときにも役に立ちます。だから、あなたに関係なく、真ん中にあるものを迅速かつキツネの言葉を持っていないすべての文書を検索します。この

• 迅速なキツネ

  のような検索を簡単に行うことができます。一方の接尾辞木に

  でも例に、文書内の部分文字列の完全一致検索でうまく動作検索があるとき、用語や開始にまたがる用語の途中で終了します。大きな配列の接尾辞木を構築するため

  良いアルゴリズム（Warnignがpaywalled）here記載されています。

  プロジェクトで