サフィックス配列を使用した正規表現検索

2012年1月、Russ Coxは、トライグラムインデックスを使用してGoogle Code Searchがどのように機能するかを説明する素晴らしいブログ投稿を公​​開しました。



この時点で、 livegrepと呼ばれる私の独自のソースコード検索エンジンの最初のバージョンは、異なるインデックス方法ですでにリリースされていました。 このシステムは、数人の友人の助けを借りて、Googleから独立して作成しました。 この記事では、その動作のメカニズムについて少し遅れて説明します。

接尾辞配列

接尾辞配列は、主にバイオインフォマティクスの分野で、他のアプリケーションの全文検索を実行するために使用されるデータ構造です。



接尾辞配列の概念は非常に単純です。これは、文字列のすべての接尾辞を並べ替えた配列です。 そのため、「here and there」という文字列については

0 1 2 3 4 5 6 7 8 9 10     _  _    
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次の接尾辞配列を作成できます。





4 _

6 _

10

3

9

2

5

7

0

1

8







配列の各要素にサフィックス全体を保存する必要はありません。インデックス（左列）とソース行のみを保存し、必要に応じて行で目的のインデックスを検索できます。 したがって、この配列は次の形式で保存されます。

 [4 6 10 3 9 2 5 7 0 1 8]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

サフィックス配列をすばやく（O（n）時間で）構築したり、元の配列をサフィックスに変換したり（配列自体の外部に一定量の追加メモリを使用）できるアルゴリズムがあります。

全文部分文字列検索

接尾辞配列の主な用途の1つは、全文検索です。



テキストのコーパスで部分文字列を探している場合、そのような部分文字列は、存在する場合、コーパスのサフィックスのプレフィックスになります。 つまり、接尾辞配列を作成する場合、ケースのサブストリングは配列の要素の先頭である必要があります。 たとえば、「here and there」行で「yes」を検索すると、この行に2回表示され、上記の配列で2行が始まることがわかります。

   2    9 
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

しかし、接尾辞配列がソートされているため、バイナリ検索方法を使用してこれらの要素をすばやく見つけることができ、インデックスはソーステキスト内の目的の部分文字列の場所を示します。

正規表現検索に向けて

ソースコード本体の検索を開始する前に、正規表現の検索をマスターします。



インデックス作成プロセス中に、livegrepはすべてのソースを読み取り、それらを巨大なバッファーに結合します（livegrepはlibdivsufsortオープンライブラリを使用してサフィックス配列を構築します。livegrepの古いバージョンは基数ソートを使用しました。インデックスが大幅に増加しました）。 次に、いわゆる「ファイルコンテンツマップ」がメモリに格納されます。これは、フォームのソートテーブル( , , )



、どの( , , )



バッファ内の特定のバイトが( , , )



れるかを判断できます。



（メカニズムは単純に説明されていますが、実際、livegrepは1つの巨大なサフィックス配列の代わりに複数を使用し、さらに同じ行を重複排除することで入力データを圧縮します。これにより、ファイルコンテンツマップが複雑になります。



しかし、正規表現の一致をすばやく見つけるためにこの構造を適用する方法は？



最初に思い浮かぶのは、正規表現でリテラル部分文字列を見つけ、接尾辞配列でそのような部分文字列をすべて見つけてから、ケース内でそれらの場所を探すという考えです。



たとえば、正規表現/hello.*world/



ます。 当然、必要なすべての部分文字列には「hello」という単語が含まれます。つまり、この単語を含むすべての文字列を検索し、正規表現を使用してチェックできます。

より複雑な検索

私たちはもっとうまくやれることがわかりました。 接尾辞配列の構造は、部分文字列の検索に加えて、少なくとも2つの基本的なクエリを実行できるようになっています。

• 範囲検索：配列の両端でバイナリ検索を使用すると、ある範囲の文字からすべての出現をすばやく見つけることができます。 範囲が[AF]
  
  
  
  場合、バイナリ検索により、 A
  
  
  
  で始まる最初の接尾辞とF
  
  
  
  で始まる最後の接尾辞が見つかります。また、知っているように、それらの間の接尾辞配列の各要素はA
  
  
  
  とF
  
  
  
  間の範囲の文字で始まりますF
  
  
  
  
  
  
  
  
• チェーンの検索：サフィックス配列のブロックがあり、そのすべての要素に共通のプレフィックスがある場合、このブロック内の次の文字で追加検索を使用して検索を絞り込むことができます。 たとえば、 /hi(s|m)/
  
  
  
  を探すと、 hi
  
  
  
  で始まるすべての要素を見つけて、配列内の隣接する要素のブロックを取得できます。 ブロック内の要素はソートされているため、この範囲でさらに2、3文字でバイナリ検索を実行できます。 1回の検索でs
  
  
  
  、2番目のm
  
  
  
  が検索され、最終的に2つの小さなセグメントが得られます-彼と彼のためです。

複数のアイテムを一度に検索し、結果を結合することもできます。 たとえば、正規表現/hello|world/



「hello」の一致、「world」の一致を個別に検索し、テキスト内の両方の単語の場所を調べます。



さらに、これらすべての戦略の組み合わせを適用できます。 たとえば、式/[af][0-9]/



の検索は次のように実行されます。

1. af
   
   
   
   を見つけるためのバイナリ検索
2. a, b, c, d, e
   
   
   
   、 f
   
   
   
   6つのブロックに分割
3. 各ブロック内で、2番目の文字によるバイナリ検索を実行し、2番目の文字が範囲[0-9]
   
   
   
   属するブロックを見つけます

その結果、接尾辞配列のセグメントのセットを取得し、その要素は/[AF][0-9]/



対応する部分文字列を示します。



これは本質的に、リクエストへの応答が次の構造を持つことができることを意味します（Go構文）：

 type IndexKey struct { edges []struct { min byte max byte next *IndexKey } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Livegrepは、正規表現の解析に使用されるいくつかの追加フィールドを除き、 ほぼ同じ構造を使用します。



クエリの各edge



について、特定の範囲の文字で始まるすべてのサフィックスを見つけ、範囲を個別の文字に分割し、次に再帰的に評価して、1文字のサフィックスに深く入ります。



Livegrepは正規表現を解析し、次のプロパティを持つIndexKey



を見つけます。正規表現に一致する部分文字列はすべて、このIndexKey



一致する必要があります。



多くの場合、これは単純です。文字クラスは一連の範囲に簡単に変換でき、文字列は1文字の範囲を持つ線形IndexKey



キーIndexKey



などです。 繰り返し演算子または選言演算子（|）を見ると、事態は複雑になります。 これについては今後の記事でさらに詳しく説明したいと思っていますが、今のところ、興味があれば、 indexer.ccを読むか、livegrep分析の結果を表示するdot



出力モードを持つanalyze-reを試してみてください。

応募結果

上記のように接尾辞配列を通過すると、見つける必要がある場合に（おそらく非常に大きな）インデックスのセットを取得します。 それぞれを個別に検索する代わりに、livegrepはすべての一致を取得してメモリ内で並べ替えます。 順序付けられたリストを調べて、互いに近い複数の一致を見つけると、1つの正規表現をすぐにセグメント全体に適用します。



Livegrepは、正規表現とRuss Cox独自のRE2ライブラリを照合します。 RE2



は十分に高速で動作するだけでなく、PCREや正規表現を操作する他のほとんどのライブラリとは異なり、正規表現を状態マシンに変換し、保証された線形時間でタスクを実行します。



見つかった一致をグループ化して、大きなテキストの同時処理にRE2速度を使用します。これにより、要求を低レベルで管理したり、多くの冗長な情報を保存したりすることができなくなります。



一致する可能性のある検索範囲を決定するために、livegrepがソースコードの行で探しているものを思い出しましょう：単純なmemchr



を使用して新しい行の最も近い文字を見つけ、コードのどの行で正確な表現を見つけることができます。



潜在的な一致を含むすべての位置に対してRE2



を実行した後、ケースで見つかった一致の最終リストを取得します。 上記のファイルコンテンツマップを使用して、一致ごとに、これらのバイトを含むファイルを見つけます。 行番号を確認するには、ファイルの内容全体を引き出して、改行文字をカウントします。



検索を特定のファイル（たとえば、 file:foo\.c



）に制限する場合、インデックスを調べた後、結果のリストと同時にファイルコンテンツマップを調べ、それらを含むファイルがリクエストからのファイルと一致しない場合は、そこからエントリを削除します。



このアプローチの興味深い機能は、ファイル名の制限により実際に検索エリアがわずかに減少することです-livegrepはサフィックス配列全体を検索し、見つかった各一致を確認します（ただし、ファイルコンテンツマップをはるかに速くチェックでき、RE2を呼び出せません） ） それでも、livegrepは非常に生産的であるため、結果をすばやく生成するためにファイル名の制限を利用する必要はありません。これは、特定のファイルを指定せずに要求を処理できるようにするために必要なことです。



最も遅いlivegrepは、ファイルへのパスを厳密に制限し、同時にサフィックス配列を非効率的に使用する要求を処理します。 . file:zzzz



は、おそらくlivegrepが送信できる1日で最も遅いリクエストの1つです。

続く

livegrepは一般的な用語でのみ確認しました。 次回は、インデックスクエリを作成し、正規表現をインデックスクエリに変換する方法について詳しく説明します。最後に、ここで説明した簡易バージョンと比較して、livegrepでサフィックス配列とファイルコンテンツ構造が実際にどのように機能するかを説明します。 特に、livegrepは実際に入力を大幅に圧縮します。これにより、インデックスの構築と結果の処理が複雑になりますが、メモリ消費が削減され、検索が高速化されます。

ああ、仕事に来てくれませんか？ :)

wunderfund.ioは、 高頻度アルゴリズム取引を扱う若い財団です。 高頻度取引は、世界中の最高のプログラマーと数学者による継続的な競争です。 私たちに参加することで、あなたはこの魅力的な戦いの一部になります。



熱心な研究者やプログラマー向けに、興味深く複雑なデータ分析と低遅延の開発タスクを提供しています。 柔軟なスケジュールと官僚主義がないため、意思決定が迅速に行われ、実施されます。



チームに参加： wunderfund.io