ボイヤームーア文字列検索アルゴリズム

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
ボイヤームーア文字列検索
クラス文字列検索
データ構造
最悪の場合の パフォーマンスΘ(m)前処理+ O(mn)マッチング[注1]
最高の パフォーマンスΘ(m)前処理+Ω(n / m)マッチング
最悪の場合の スペースの複雑さΘ(k)[注2]

コンピュータサイエンスではボイヤー-ムーア文字列検索アルゴリズムは、実用的な文字列検索文献の標準ベンチマークである効率的な文字列検索アルゴリズムです。[1] 1977年にRobertS.BoyerJStrotherMooreによって開発されました。 [2]元の論文には、パターンシフトの生成方法の説明なしにパターンシフトを計算するための静的テーブルが含まれていました。テーブルを作成するためのアルゴリズムは、後続の論文で公開されました。この論文には、1980年にWojciechRytterによって修正されたエラーが含まれていました。 [3] [4]アルゴリズム 前処理を行います検索対象の文字列(パターン)ですが、検索対象の文字列(テキスト)ではありません。したがって、パターンがテキストよりもはるかに短いアプリケーションや、複数の検索にわたってパターンが持続するアプリケーションに最適です。Boyer–Mooreアルゴリズムは、前処理ステップで収集された情報を使用してテキストのセクションをスキップするため、他の多くの文字列検索アルゴリズムよりも定数係数が低くなります。一般に、アルゴリズムはパターンの長さが長くなるほど速く実行されます。アルゴリズムの主な機能は、パターンの頭ではなく尾で一致し、テキスト内のすべての文字を検索するのではなく、複数の文字のジャンプでテキストに沿ってスキップすることです。

定義

A N P A N M A N -
P A N - - - - - -
- P A N - - - - -
- - P A N - - - -
- - - P A N - - -
- - - - P A N - -
- - - - - P A N -
k=3からk=8までのパターンPANとテキストANPANMANの配置一致はk=5で発生します。
  • Tは、検索する入力テキストを示します。その長さはnです。
  • Pは、パターンと呼ばれる検索対象の文字列を示しますその長さはmです。
  • S [ i ]は、 1から数えて文字列Sのインデックスiにある文字を示します。
  • S [ i .. j ]は、インデックスiで始まりjで終わる文字列Sの部分文字列を示します。
  • S接頭辞、範囲[1、l ]内のいくつかのiの部分文字列S [1 .. i ]です。ここで、 lSの長さです。
  • S接尾辞、範囲[1、l ]内のいくつかのiの部分文字列S [ i .. l ]です。ここで、 lSの長さです。
  • PからTへのアラインメントは、Pの最後の文字がTのインデックスkとアラインメントされるようなTのインデックスkです
  • PがT [(k --m +1).. k ]等しい場合、 P一致または発生アライメントkで発生します。

説明

ボイヤームーアアルゴリズムは、さまざまな配置で明示的な文字比較を実行することによりT内のPの出現を検索します。すべてのアラインメントを力ずくで検索する代わりに()、Boyer–Mooreは、Pの前処理によって得られた情報を使用して、可能な限り多くのアライメントをスキップします。

このアルゴリズムが導入される前は、テキスト内を検索する通常の方法は、テキストの各文字でパターンの最初の文字を調べることでした。それが見つかると、テキストの後続の文字がパターンの文字と比較されます。一致が発生しなかった場合、一致を見つけるためにテキストが文字ごとに再度チェックされます。したがって、テキスト内のほとんどすべての文字を調べる必要があります。

このアルゴリズムの重要な洞察は、パターンの終わりをテキストと比較すると、テキストのすべての文字をチェックするのではなく、テキストに沿ってジャンプできることです。これが機能する理由は、パターンをテキストに並べるときに、パターンの最後の文字がテキストの文字と比較されるためです。文字が一致しない場合は、テキストに沿って逆方向に検索を続ける必要はありません。テキスト内の文字がパターン内のどの文字とも一致しない場合、チェックするテキスト内の次の文字は、テキストに沿ってm文字遠くに配置されます。ここで、mはパターンの長さです。本文中の文字パターンでは、テキストに沿ったパターンの部分的なシフトが行われ、一致する文字に沿って整列され、プロセスが繰り返されます。テキスト内のすべての文字をチェックするのではなく、テキストに沿ってジャンプして比較を行うと、実行する必要のある比較の数が減ります。これは、アルゴリズムの効率の鍵です。

より正式には、アルゴリズムはアライメントから始まります、したがって、Pの開始はTの開始と整列します。次に、 PTの文字が、PインデックスmTのkから開始して、後方に移動して比較されます。文字列は、 Pの終わりからPの始まりまで一致します。比較は、Pの先頭のいずれかまで続きますに到達する(一致があることを意味する)か、不一致が発生すると、いくつかのルールで許可されている最大値に従って、位置合わせが前方(右)にシフトされます。比較は新しいアラインメントで再度実行され、アラインメントがTの終わりを超えてシフトされるまでプロセスが繰り返されます。これは、それ以上一致するものが見つからないことを意味します。

シフトルールは、 Pの前処理中に生成されたテーブルを使用して、一定時間のテーブルルックアップとして実装されます

シフトルール

シフトは、不良文字ルールと良好サフィックスルールの2つのルールを適用して計算されます。実際のシフトオフセットは、これらのルールによって計算されたシフトの最大値です。

悪いキャラクタールール

説明

- - - - バツ - - K - - -
A N P A N M A N A M -
- N N A A M A N - - -
- - - N N A A M A N -
パターンP = NNAAMANを使用した不正な文字ルールのデモンストレーション。Xでマークされた列のN(入力テキスト内)とA (パターン内)の間に不一致がありますパターンは右にシフトされ(この場合は2)、現在の文字(中央のA )の左側にある文字N(パターンP )の次の出現が検出されます。

不良文字ルールは、比較プロセスが失敗したTの文字を考慮します(そのような失敗が発生したと想定)。その文字のPの左側の次の出現が検出され、その出現をTの不一致の出現と一致させるシフトが提案されます。不一致文字がPの左側に発生しない場合は、P全体を不一致点を超えて移動するシフトが提案されます。

前処理

メソッドは、不正な文字ルールのテーブルがとるべき正確な形式によって異なりますが、単純な一定時間のルックアップソリューションは次のとおりです。最初にアルファベットの文字cのインデックスでインデックス付けされ、次にアルファベットの文字cのインデックスでインデックス付けされる2Dテーブルを作成します。パターン内のインデックスi 。このルックアップは、次に高いインデックスを持つPでのc出現を返しますまたは、そのような発生がない場合は-1。提案されたシフトは、 とルックアップ時間と長さkの有限のアルファベットを想定したスペース。

以下のCおよびJavaの実装には、スペースの複雑さ(make_delta1、makeCharTable)。これは、元のdelta1およびBMH不良文字テーブルと同じです。このテーブルは、位置にあるキャラクターをマップしますシフトする、最後のインスタンス(シフト量が最小)が優先されます。未使用の文字はすべて次のように設定されます番兵として。

良い接尾辞ルール

説明

- - - - バツ - - K - - - - -
M A N P A N A M A N A P -
A N A M P N A M - - - - -
- - - - A N A M P N A M -
パターンP = ANAMPNAMの適切なサフィックスルールのデモンストレーションここで、tT [6..8]であり、t'P [2..4]です。

良い接尾辞の規則は、悪い文字の規則よりも概念と実装の両方で著しく複雑です。不正な文字ルールと同様に、パターンの最後からパターンの開始に向かって進むアルゴリズムの比較機能も利用します。それは次のように説明することができます:[5]

PTの特定の配置について、 Tの部分文字列tPの接尾辞と一致するとしますが、左への次の比較で不一致が発生します。

  1. 次に、存在する場合、 t'がPの接尾辞ではなく、Pのt'左側の文字がPのt左側の文字と異なるように、Pのtの右端のコピーt'を見つけます。 Pを右にシフトしてPの部分文字列t'Tの部分文字列tと整列するようにします。
  2. t'が存在しない場合は、シフトされたパターンの接頭辞Tのtの接尾辞と一致するように、Pの左端をTのtの左端を超えて最小量だけシフトします。
  3. そのようなシフトが不可能な場合は、Pn(Pの長さ)だけ右にシフトします。
  4. Pの出現が見つかった場合は、シフトされたPの適切な接頭辞がT内のPの出現の接尾辞と一致するように、 Pを最小量だけシフトします。
  5. そのようなシフトが不可能な場合は、Pn桁シフトします。つまり、Pをtを超えてシフトします。

前処理

適切なサフィックスルールには、2つのテーブルが必要です。1つは一般的なケースで使用するためのもので、もう1つは一般的なケースが意味のある結果を返さないか一致が発生する場合に使用するものです。これらのテーブルは、それぞれLおよびHで示されます。それらの定義は次のとおりです。[5]

iについて、文字列がm未満の最大位置ですの接尾辞に一致しますそして、その接尾辞の前の文字が等しくないように条件を満たす位置がない場合はゼロと定義されます。

させての最大の接尾辞の長さを示しますこれは、 Pのプレフィックスでもあります(存在する場合)。存在しない場合は、ゼロになります。

これらのテーブルは両方ともで構築可能です時間と使用スペース。Pのインデックスiアライメントシフトは次の式で与えられます。またHは次の場合にのみ使用してくださいがゼロであるか、一致が見つかりました。

ガリルルール

ボイヤームーア文字の単純だが重要な最適化は、1979年にZvi Galilによって発表されました。 [6] シフトとは対照的に、Galilルールは、一致することがわかっているセクションをスキップすることにより、各配置で行われる実際の比較を高速化します。アラインメントk1で、PがTと比較されてTの文字cになるとします次に、左端がck1の間にあるようにPがk2にシフトされた場合、次の比較フェーズで、Pの接頭辞は部分文字列T [k 2 - n .. k1 ]したがって、比較がTの位置k 1まで下がった場合、過去のk 1を明示的に比較しなくても、 Pの発生を記録できますボイヤームーア文字の効率を高めることに加えて、最悪の場合の線形時間実行を証明するためにガリル規則が必要です。

ガリルルールは、元のバージョンでは、複数の一致を出力するバージョンに対してのみ有効です。これは、 c = 0、つまり完全一致でのみ部分文字列の範囲を更新します。サブマッチを処理するための一般化されたバージョンは、1985年にApostolico–Giancarloアルゴリズムとして報告されました。[7]

パフォーマンス

元の論文で提示されているボイヤームーアアルゴリズムの実行時間は、最悪の場合、パターンがテキストに表示されない場合のみ。これは、1977年にクヌースモリスプラットによって最初に証明され[3]、1980年にギバスオドリツコが続いて[8]、最悪の場合の比較上限は5nでした。リチャード・コールは、 1991年の最悪の場合に3n比較の上限で証明を与えました。 [9]

テキストにパターンが含まれている場合、元のアルゴリズムの実行時間は次のようになります。最悪の場合。これは、パターンとテキストの両方が同じ繰り返し文字のみで構成されている場合に簡単に確認できます。ただし、ガリルルールを含めると、すべてのケースで実行時間が線形になります。[6] [9]

実装

さまざまなプログラミング言語でさまざまな実装が存在します。C ++ではC ++ 17以降の標準ライブラリの一部であり、Boostはアルゴリズムライブラリの下で一般的なボイヤームーア検索の実装も提供します。Go(プログラミング言語)では、 search.goに実装があります。D(プログラミング言語)は、Phobosランタイムライブラリの一部として、範囲内の述語ベースのマッチングに BoyerMooreFinderを使用します。

ボイヤームーアアルゴリズムは、GNUgrepでも使用されます。[10]

Pythonの実装

 importと入力すること から* #このバージョンでは、大文字と小文字を区別しないマッチングのために、ASCIIの英語のアルファベットに対応しています。#この機能を削除するには、alphabet_indexをord(c)として定義し、「26」のインスタンスを#「256」または任意の最大コードポイントに置き換えます。Unicodeの場合、0x10FFFFサイズのテーブルを作成する代わりに、UTF-8#バイトで一致させることができます。 





ALPHABET_SIZE  =  26

defalphabet_index  c str -> int "" "0から数えて、英語のアルファベットで指定された文字のインデックスを返します。" "" val = ord c。lower - ord " a" val >= 0およびval < ALPHABET_SIZEをアサートしてvalを返します   
    
        
           
     

def  match_length S  str  idx1  int  idx2  int  ->  int 
    """idx1とidx2で始まるSのサブストリングの一致の長さを返します。""" 
    if  idx1  ==  idx2 
        return  len S  -idx1  match_count 
    = 0 idx1 < len S およびidx2 < len S およびS _  
             [ idx1 ]  ==  S [ idx2 ]:
        match_count  + =  1 
        idx1  + =  1 
        idx2  + =  1 
    return  match_count

def  basic_preprocess S  str  ->  List [ int ]:
    "" "Return Z、Sの基本的な前処理。

    Z [i]は、Sのプレフィックスでもあるiで始まる部分文字列の長さです。
    この前処理はO(n)時間で実行されます。ここで、nはSの長さです
。len S )の場合は    "" " 
    == 0 #空の文字列の大文字小文字を処理return [] if len S == 1 #1文字の文字列の大文字小文字を処理return [ 1 ] z = [ 0 for x in S ] z [ 0 ] = len      
         
         
         
          
      S 
    z [ 1 ]  =  match_length S  0、1  for i in range 2、1 + z [ 1 ]):
    演習1-5から最適z [ i ] = z [ 1 ] -i + 1 #範囲内のiに対してz-box l = 0 r = 0の下限と上限を定義します        
              
    
      
      
       2  +  z [ 1 ]、 len S )):
        if  i  <=  r   #iは既存のzボックス内にあり
            ますk  =  i  --l b =  z [ k ] a = r --i + 1 if b < a #bは既存のz-box内で終了しますz [ i ] = b else #bはz-boxの終了時または終了後に終了します。z-boxの右側で明示的に一致させる必要があります
              
                  
                 
                  
              
                z [ i ]  =  a  +  match_length S  a  r  +  1 
                l  =  i 
                r  =  i  +  z [ i ]  --1  else : #i既存のzボックス内に存在しませんz [ i ] 
        = match_length S 0 i if z [ i ] > 0 l =  
                
               
                  i 
                r  =  i  +  z [ i ]  -1  return z _
     

def  bad_character_table S  str  ->  List [ List [ int ]]:
    "" " 
    SのRを生成します。これは、英語のアルファベットの文字cの位置によってインデックス付けされた配列
    です。Rのそのインデックスには配列があります。長さ|S| +1で、Sの各
    インデックスi(およびSの後のインデックス)に対して
    、iから開始してSを右から左にトラバースするときに検出される文字cの次の位置を指定します。これは、の一定時間のルックアップ
    に使用されます。 Boyer-Moore文字列検索アルゴリズムの不正な文字ルール。ただし
    、非定数時間ソリューションよりもサイズがはるかに大きくなります。
    "" "
    if  len S  ==  0 
        return  [[]  for  a  in  range ALPHABET_SIZE )] 
    R =  [  [ -1 ] for a in range ALPHABET_SIZE )] alpha = [ -1 for a in range ALPHABET_SIZE ] for i c in enumerate S ):alpha [    
          
        
        alphabet_index c )]  =  i 
        for  j  a  in  enumerate alpha ):
            R [ j ] 追加a 
    return  R

def  good_suffix_table S  str  ->  List [ int ]:
    """
    強力な適切な接尾辞ルールの実装で使用される配列であるSのLを生成します
    。L[i]=k、SのようなSの最大位置[i:](iで始まるSの接尾辞)
    はS [:k](kで終わるSの部分文字列)の接尾辞と一致します。Boyer-Mooreで使用されるLは、
    Tに対してPをシフトする量を与えます。 T内のPのインスタンスはスキップされず、P [:L [i]]
    のサフィックスは、前回の一致試行でPのサフィックスと一致したTのサブストリングと一致します。
    具体的には、不一致が位置i-1で発生した場合P、シフトの大きさが与えられます
    方程式len(P)-L[i]によって。L [i] = -1の場合、フルシフトテーブルが使用されます。
    適切な接尾辞のみが重要であるため、L [0]=-1です。
    "" " 
    L  =  [ -1 for c in S ] N = basic_preprocess S [::- 1  ])#S [::-1] reverses S N .reverse for j in range 0 len S -1 i = len S   
        
    
          
           -N [ j ] if i != len  S L [ i ] = j return L
           
              
     

def  full_shift_table S  str  ->  List [ int ]:
    """
    ボイヤームーア
    文字列検索アルゴリズムの適切なサフィックスルールの特殊なケースで使用される配列であるSのFを生成します。F[i]は長さです。 Sの接頭辞でもあるS[i:]の最長の接尾
    辞の。これが使用される場合、テキストTに対するパターンPのシフトの大きさ
    はlen(P)-F [i]であり、不一致があります。 i-1で発生します。
    """ 
    F  =  [ 0  for  c  in  S ] 
    Z  =  basic_preprocess S 
    longest  =  0 
    for  i  zv  in  enumerate reverse Z longest = max zv longest if zv == i + 1 else longest F [ --i --1 ] = longest return F
                   
            
     

def  string_search P  T  ->  List [ int ]:
    "" "
    ボイヤームーア文字列検索アルゴリズムの実装。これにより
    、T内のPのすべての出現が検出され、パターンを前処理して最適なものを決定するさまざまな方法が組み込まれます。
    文字列をシフトして比較をスキップする量。実際には、O(m)(さらには
    サブリニア)時間で実行されます。ここで、mはTの長さです。この実装は、スペースを含まないASCIIアルファベット文字に対して大文字と小文字を区別しない
    検索を実行します。
    "" " 
    if  len P  ==  0 または len T  ==  0 または len T  <  len P ):
        return  []

    一致 =  []

    #前処理
    R  =  bad_character_table P 
    L  =  good_suffix_table P 
    F  =  full_shift_table P 

    k  =  len P  -1  #Tに対するPの終わりの位置合わせを表しますprevious_k = -1       前のフェーズ(ガリルの法則)での位置合わせを表しますが、k < len T ):i = len P -1 文字Pで比較するh = k # i >= 0かつh > previous_kおよびP [ i ]でT比較する文字
           
       
              
                     
                  ==  T [ h ]:  #Pの終わりから始まる一致
            i-  =  1 
            h-  =  1 ( 
        i == - 1またはh == previous_kの場合)  #一致が見つかりました(ガリルの法則)が一致します。append k --len P + 1 k + = len P -F [ 1 ] if len P > 1 _        
                
                     else  1 
        else : #一致なし、不正な  文字と適切な接尾辞のルールの最大値によるシフト
            char_shift  =  i  --R  [ alphabet_index T [ h ])] [ i ] if i + 1 == len P ):#不一致が発生した最初の試行suffix_shift = 1 elif L [ i + 1 ] == --1 一致したサフィックスはPのどこにも表示されませんsuffix_shift =
                   
                  
                   
                  len P  -F  [ i + 1 ] else #一致した接尾辞がPに表示さますsuffix_shift = len P -1 --L [ i + 1 ] shift = max char_shift suffix_shift previous_k = k if shift > = i + 1 else previous_k #ガリルのルールk +=シフト  
                           
                        
               
                        
              
    リターン マッチ

C実装

#include <stdint.h> 
#include <stddef.h> 
#include <stdbool.h> 
#include <stdlib.h> 

#define ALPHABET_LEN 256 
#define max(a、b)((a <b)?b:a)

//不正な文字ルール。
// delta1テーブル:delta1 [c]には、patの最後の
//文字とpatのcの右端のオカレンスとの間の距離が含まれます。
// 
// cがpatで発生しない場合、delta1 [c]=patlen。
// cがstring[i]にありc!= pat [patlen-1]の場合、iを安全にシフトできます
//delta1[c]でシフトできます。これは
文字列を取得するために//前方にシフトするのに必要な最小距離です[i]パットのキャラクターと並んでいます。
// c == pat [patlen-1]ゼロを返すことは、デルタ2を
持たない//BMHの懸念事項にすぎません。このような場合、BMHは価値をパトレンにします。
//これ以上スキップするため、元の0の代わりに//この選択に従います
(正しさ?)
//
//このアルゴリズムはalphabet_len+patlen時間で実行されます。
void make_delta1 ptrdiff_t * delta1 uint8_t * pat size_t patlen {       
    for int i = 0 ; i < ALPHABET_LEN ; i ++ {       
        delta1 [ i ] = patlen ;  
    }
    for int i = 0 ; i < patlen ; i ++ {       
        delta1 [ pat [ i ]] = patlen -1 - i ;    
    }
}

//word[pos]で始まる単語の接尾辞が
//単語の接頭辞である
場合はtrueboolis_prefix uint8_t * word size_t wordlen ptrdiff_t pos {       
    int Supplementlen = wordlen --pos ; _     
    //ここでstrncmp()ライブラリ関数を使用することもできます
// return!strncmp(word、&word [pos]、suffixlen); for int i = 0 ; i < suffixlen ; i ++ {    
             
        if word [ i ] != word [ pos + i ]){    
            falseを返します; 
        }
    }
    trueを返します; 
}

//word[pos]で終わる単語の最長の接尾辞の長さ。
// Supplement_length( "dddbcabc"、8、4)= 2 
size_t suffix_length uint8_t * word size_t wordlen ptrdiff_t pos {       
    size_t i ; 
    
//接尾辞の長さiを単語の最初の不一致または先頭にインクリメントします// for i = 0 ; word [ pos --i ] == word [ wordlen -1 - i ])&& i <= pos ; i ++ );    
               
    私を返す; 
}

//良い接尾辞のルール。
// delta2テーブル:pat [pos]で不一致が発生した場合、
// pat [pos +1]からpat[patlen-1]について知っていることに基づいて、//次に可能な完全一致を調整します。
// //ケース1:// pat [pos +1]からpat[patlen-1]がpatの他の場所で発生しない場合、//次のもっともらしい一致は不一致時または不一致後に始まります。//部分文字列pat[pos+ 1 .. patlen-1]内に、// patの接頭辞がある場合、次のもっともらしい一致はここにあります(//部分文字列に複数の接頭辞がある場合は、最も長いものを選択します)。それ以外の場合、//次のもっともらしい一致は、//pat[patlen-1]に揃えられた文字を超えて開始されます。// //ケース2の場合:











// pat [pos +1]からpat[patlen-1]は、patの他の場所で発生します。//不一致は、
一致の終了を確認していないことを示しています。
//ただし、試合の途中を見ている可能性があります。
// 
//ケース1を処理する最初のループは、
// KMPテーブルに類似しており、//「逆方向」のスキャン順序に適合してい
ます
。接尾辞。最悪のシナリオ
では、// patは繰り返される同じ文字で構成されているため、すべてのサフィックスは
//プレフィックスです。ただし、このループだけでは不十分
です。//patが「ABYXCDBYX」でテキストが「.....ABYXCDEYX」であるとします。
// X、Yを照合し、B!=Eを見つけます。patの接頭辞はありません
//接尾辞「YX」が含まれているため、最初のループは
//9文字先にスキップするように指示します。
//表面的にはKMPテーブルに似ていますが、KMPテーブルは// 
BMアルゴリズムにはない//部分一致の開始に関する情報に依存しています。
// // 2番目のループはケース2に対応します。suffix_lengthは//一意ではない可能性があるため、最小値を取得します。これにより、//最も近い潜在的な一致がどれだけ離れているかがわかります。void make_delta2 ptrdiff_t * delta2 uint8_t * pat size_t patlen {




       
    ssize_t p ; 
    size_t last_prefix_index = 1 ;   

    //最初のループ
for p = patlen -1 ; p > = 0 ; p - {        
        if is_prefix pat patlen p + 1 )){    
            last_prefix_index = p + 1 ;  
        }
        delta2 [ p ] = last_prefix_index + patlen -1 - p );      
    }

    // 2番目のループ
for p = 0 ; p < patlen -1 ; p ++ {          
        size_t slen = Supplement_length pat patlen p );     
        if pat [ p --slen ] != pat [ patlen -1 - slen ] {        
            delta2 [ patlen -1 - slen ] = patlen -1 - p + slen ;        
        }
    }
}

//最初に一致するポインタを返します。
// glibc memmem()(非BM)およびstd :: boyer_moore_searcher(最初の一致)も参照してください。
uint8_t * boyer_moore uint8_t * string size_t stringlen uint8_t * pat size_t patlen {          
    ptrdiff_t delta1 [ ALPHABET_LEN ]; 
    ptrdiff_t delta2 [ patlen ]; // C99 VLA make_delta1 delta1 pat patlen );  
      
    make_delta2 delta2 pat patlen );  

    //空のパターンは特別に考慮する必要があります
if patlen == 0 {        
        文字列を返す; 
    }

    size_t i = patlen - 1 ; // str-idx while i < stringlen {             
        
        ptrdiff_t j = patlen - 1 ; // pat-idx while j > = 0 && string [ i ] == pat [ j ])){      
                
            --;
            --j ; _
        }
        if j < 0 {    
            return string [ i + 1 ]; 
        }

        ptrdiff_t shift = max delta1 [ string [ i ]]、delta2 [ j ]);    
        i +=シフト;  
    }
    NULLを返します; 
}

Javaの実装

    /***指定された部分文字列
     が最初に出現する*この文字列内のインデックスを返します
サブストリングでない場合は、-1を返します。
     * 
     *ガリルは1つの一致しか生成しないため、ガリルはありません。
     * 
     *@paramhaystackスキャンする文字列*@paramneedle
     検索するターゲット文字列
     *@returnサブストリングの開始インデックス
     */ 
    public  static  int  indexOf char []  haystack  char []  needle  { 
        if  needle 長さ ==  0  { 
            0を返す ; } int charTable [] = makeCharTable needle ); int offsetTable [] = makeOffsetTable ); for int i =長さ-1 j ; i <干し草長さ;){ for j =長さ-1 ;[
        
           
           
                   
                  j ]  == 干し草の山[ i ] ;  --i -- j { if j == 0 { return i ; _ } } // i + =needle.length-j; //素朴な方法の場合i += Math max offsetTable [ needle .length --1 --j ] charTable [ haystack [ i ] ] ; _ }  
                    
                     
                
            
            
                   
        
        戻り -1 ; }
    

    /***
     不一致の文字情報に基づいてジャンプテーブルを作成します。
     * / 
    private  static  int []  makeCharTable char []  needle  { 
        final  int  ALPHABET_SIZE  =  Character MAX_VALUE  +  1 ;  // 65536 
        int []  table  =  new  int [ ALPHABET_SIZE ] ; 
        for  int  i  =  0 ;  i  <  table .length _;  ++ i  {
            テーブル[ i ]  = 長さ; 
        } 
        for  int  i  =  0 ;  i  < 長さ;  ++ i  {
            テーブル[[ i ]]  =  -1  -  i  ; }リターンテーブル; }
        
         
    

    /***
     不一致が発生するスキャンオフセットに基づいてジャンプテーブルを作成します。
     *(悪い文字ルール)。
     * / 
    private  static  int []  makeOffsetTable char []  needle {  int 
        [ ]  table  =  newint  [ needle 長さ] ; int lastPrefixPosition = needle 長さ; for inti =; i > 0
           
               ;  --i { if isPrefix needle i { lastPrefixPosition = i ; }テーブル[-i ] = lastPrefixPosition - i +長さ; } for int i = 0 ; i <-1 ; ++ i  
               
                  
            
                    
        
                   { 
            int  slen  =  suffixLength needle  i ); 
            テーブル[ slen ]  =  -1  - i +  slen ; }リターンテーブル; }   
        
         
    

    / ** 
     *needle [p:end]は針の接頭辞ですか?
     * / 
    private  static  boolean  isPrefix char []  needle int  p  {  for 
         int i  =  p  j  =  0  ; i  <  needle  .length ; ++ i ++ j { if needle [ i ] =[ j ] {   
                
                 falseを返します; 
            } 
        } 
        return  true ; 
    }

    / ** 
     *部分文字列の最大長をpで終了し、接尾辞として返します。
     *(適切なサフィックスルール)
     * / 
    private  static  int  SupplementLength char []  needle  int  p  { 
        int  len  =  0 ; 
        for  int  i  =  p  j  = 長さ -1  ; i > = 0 &&[ i ] ==[ j
                       ] ;  --i -j { len + = 1 ; _ } return len ; }  
              
        
         
    

バリアント

ボイヤー-ムーア-ホースプールアルゴリズムは、不良文字ルールのみを使用してボイヤー-ムーアアルゴリズムを単純化したものです

Apostolico–Giancarloアルゴリズム、明示的な文字比較をスキップすることにより、指定された配置で一致が発生したかどうかをチェックするプロセスを高速化します。これは、パターンの前処理中に収集された情報を、各一致試行で記録された接尾辞の一致長と組み合わせて使用​​します。サフィックスの一致長を保存するには、検索対象のテキストと同じサイズの追加のテーブルが必要です。

Raitaアルゴリズムは、Boyer-Moore-Horspoolアルゴリズムのパフォーマンスを向上させます特定の文字列内の特定のサブ文字列の検索パターンは、Boyer-Moore-Horspoolアルゴリズムとは異なります。

メモ

  1. ^ mは、テキストで検索しているパターン文字列の長さであり、長さはnです。このランタイムは、ガリル規則なしで、パターンのすべての出現を見つけるためのものです。
  2. ^ kはアルファベットのサイズです

参照

  1. ^ ヒューム; 日曜日(1991年11月)。「高速文字列検索」。ソフトウェア:実践と経験21(11):1221–1248。土井10.1002/spe.4380211105S2CID5902579 _
  2. ^ ボイヤー、ロバートS .; Moore、J Strother(1977年10月)。「高速文字列検索アルゴリズム」。通信。ACMNew York:Association forComputingMachinery。20(10):762–772。土井10.1145/359842.359859ISSN0001-0782_ S2CID15892987_   
  3. ^ a b Knuth、Donald E .; モリス、ジェームスH.、ジュニア; プラット、ヴォーンR.(1977)。「文字列の高速パターンマッチング」SIAMジャーナルオンコンピューティング6(2):323–350。CiteSeerX10.1.1.93.8147_ 土井10.1137/0206024ISSN0097-5397_  
  4. ^ Rytter、Wojciech(1980)。「ボイヤームーア文字列検索のための正しい前処理アルゴリズム」。SIAMジャーナルオンコンピューティング9(3):509–512。土井10.1137/0209037ISSN0097-5397_ 
  5. ^ a b Gusfield、Dan(1999)[1997]、 "Chapter 2-Exact Matching:Classical Comparison-Based Methods"、Algorithms on Strings、Trees、and Sequences(1 ed。)、Cambridge University Press、pp。19–21 、ISBN  0521585198
  6. ^ a b ガリル、Z。(1979年9月)。「ボイヤー-ムーア文字列照合アルゴリズムの最悪の場合の実行時間を改善することについて」。通信。ACMNew York:Association forComputingMachinery。22(9):505–508。土井10.1145/359146.359148ISSN0001-0782_ S2CID1333465_   
  7. ^ アポストリコ、アルベルト; ジャンカルロ、ラファエル(1986年2月)。「ボイヤー-ムーア-ガリル文字列検索戦略の再検討」SIAMジャーナルオンコンピューティング15:98〜105。土井10.1137/0215007
  8. ^ ギバス、レオニダス; オドリツコ、アンドリュー(1977)。「ボイヤー-ムーア文字列検索アルゴリズムの線形性の新しい証明」コンピュータサイエンスの基礎に関する第18回年次シンポジウムの議事録SFCS'77。ワシントン、コロンビア特別区:IEEE Computer Society:189–195。土井10.1109/SFCS.1977.3S2CID6470193_  
  9. ^ a b コール、リチャード(1991年9月)。「ボイヤー-ムーア文字列照合アルゴリズムの複雑さには厳しい限界があります」離散アルゴリズムに関する第2回ACM-SIAMシンポジウムの議事録ソーダ'91。ペンシルベニア州フィラデルフィア:Society for Industrial and Applied Mathematics:224–233。ISBN  0-89791-376-0
  10. ^ Haertel、Mike(2010年8月21日)。「GNUgrepが高速である理由」FreeBSD-現在のメーリングリストアーカイブ

外部リンク