文字列マッチングベース(上):ハッシュアルゴリズムによる効率的な文字列マッチングはどのように実現されますか?
4207 ワード
文字列マッチングベース(上):ハッシュアルゴリズムによる効率的な文字列マッチングはどのように実現されますか?
文字列整合アルゴリズム:BFアルゴリズムとRKアルゴリズムは、一つのモード列整合アルゴリズム、すなわち一つの列ともう一つの列がマッチングし、BMアルゴリズムとKMPアルゴリズムはマルチモードストリングマッチングアルゴリズム、すなわち一つのストリップが同時に複数のストリップを検索し、それぞれTrieツリーとAC自動機である.
RKアルゴリズムはBFアルゴリズムの改善であり、RKアルゴリズムはどのようにハッシュアルゴリズムを介して効率的な文字列マッチングを実現するのか?
BFアルゴリズム
暴力的なマッチングアルゴリズムは、シンプルなマッチングアルゴリズムとも呼ばれます.
メインストリングとモードストリング
文字列Aの中で文字列Bを探して、あのAはメインストリングで、Bはモードストリングで、メインストリングの長さをnと書いて、モードストリングの長さはmと書いて、メインストリングの中でモードストリングを探すので、n>m
最も簡単で最も暴力的な文字列マッチングアルゴリズムとして、BFアルゴリズムは私達がメインストリングの中で、スタート位置はそれぞれ0,1,2…n-mで、長さはmのn-m＋1個のサブストリングがありますか?
メインストリングが「aaa…aa」モードの列が「aaaaaab」なら、私達は毎回m文字と比較して、n-m＋1と比較します.最も複雑な時間複雑度はO(n∗m)O(n*m)O(n∗m)です.
BFアルゴリズムの時間の複雑さは高いが、一般的な文字列マッチングアルゴリズムです.一:実際のソフトウェア開発では、モードストリングとメインストリングの長さはそんなに長くないです.毎回、モードストリングとメインストリングのサブストリングが一致すると、途中でマッチできない文字に出会うと停止します.m文字を全部比較する必要はありません.シンプルな文字列をアルゴリズムに合わせるのは簡単です.間違えにくいです.バグがあっても暴露して修復しやすいです.
RKアルゴリズム
RKアルゴリズムはBFアルゴリズムに基づいて改良され、シンプルな文字列マッチングアルゴリズムの改造に対して、ハッシュアルゴリズムを導入すると、時間の複雑さが低減される.
ハッシュ・アルゴリズムによって、メイン・列のn−m＋1個のサブストリングにそれぞれハッシュ値を求め、次いで、一つずつパターン・ストリングのハッシュ値と比較すると、あるサブストリングのハッシュ値がモード・ストリングと等しい場合、対応するサブストリングとモード・ストリングが一致することを示す.
このとき、ハッシュアルゴリズムの設計は、一致する文字列の文字セットがK文字だけを含むと仮定して、1つのK進数でサブストリングを表すことができ、このK進数は10進数に変換され、サブストリングのハッシュ値として使用される.
処理する文字列はa~z 26文字の小文字しか含まれていません.この26進数で文字列を表します.a
このようなハッシュアルゴリズムの主な列のうち、隣接する2つのサブストリングのハッシュ値の計算式には、ある関係がある.隣接する2つのサブストリングs[i-1]とs[i](iは、サブストリングの開始位置を表し、サブストリングの長さは共にmである.s[i-1]のハッシュ値を使用することにより、s[i]のハッシュ値h[i−1]を素早く算出することができる.のハッシュ値、h［i］は、サブストリングs［i,i＋m−1］のハッシュ値h［i−1］＝2 6(m−1)∗(s［i−1］−−−a’)＋2 6(m−1)−−−−−−−−−−−−−−−−−−−−−−1)＋＋2−0−−−−−−−−−−0−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−2−−−−−−−−−−−−0−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−ヽ.i＋m−2−−−−−−−−−−a’＋2 6−0∗(s［i＋m−1−−−−−−−−1］−a’)式は、B＝A−8727であることが分かるので、h［i］とh［i−1］の関係は、h［i］=(h［i−1］−2−−6(m−1)−−1(m−1)−−−−−−−−−−−−1)−−−−−−−−−−−−−−−−−−−1(m−−1)−−−−−−−−−−−−−−−−−−−−−−−−−−−−1(m−−−−−−−−−−−−−−−−−−−−s[i-1,i+m-2]のハッシュ値は、h[i]がサブ串s[i,i+m-1]のハッシュ値h[i-1]===26(m-1)*(s[i-1]-'''')+26(m-1)*(s[i]-')+………+26^0*(s[i+m-2]-''')h[i]===='''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''B=A*26なので、h[i]とh[i-1]の関係は、h[i]=(h[i-1]-26^(m-1)*s[i-1]-')*26+26^0*(s[i+m-1]-'a')h[i−1]に対応するサブシリアルsです.i−−1,i＋m−2のハッシュ値、h［i］は、サブ列s［i,i＋m−1］のハッシュ値h［i−−1］＝26(m−1)∗(s［i−1］−a’)＋26(m−1)−−−−−−−i(m−1)−−−−−−−−−−−−−−−−−−−−−−−−−i(s−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−1)−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−＋…＋26∗(s[i＋m−2]−a')＋260∗(s[i＋m−1]−a′)の数式から、B=A∗26とh[i]とh[i−1]の関係は、h[i]=(h［i−1］−26(m−1)s［i−1］−a’)∗26＋260∗(s［i＋m−1］−a’)ここの26
RKアルゴリズムの時間複雑さはO(n)である.
二次元文字列行列(メインストリング)の場合、他の二次元文字列行列(モードストリング)を検索しますか?
KaTeX parse error:Unidefined control sequence:\matix at position 13:メインストリング=\left[\̲m̲a.̲t̲r̲i̲x̲｛d&a&b&…
KaTeX parse error:Unidefined control sequence:\matix at position 14:モード列=\left[\̲m̲a.̲t̲r̲i̲x̲｛c&a\\e&…
最初の行の文字列を検索します.長さがmなら、bfやrkでも大丈夫です.n
マッチがある場合は、2行目からm行目の文字列に順次マッチします.複雑度は最初と同じですので、複雑度は異なります.
文字列整合アルゴリズム:BFアルゴリズムとRKアルゴリズムは、一つのモード列整合アルゴリズム、すなわち一つの列ともう一つの列がマッチングし、BMアルゴリズムとKMPアルゴリズムはマルチモードストリングマッチングアルゴリズム、すなわち一つのストリップが同時に複数のストリップを検索し、それぞれTrieツリーとAC自動機である.
RKアルゴリズムはBFアルゴリズムの改善であり、RKアルゴリズムはどのようにハッシュアルゴリズムを介して効率的な文字列マッチングを実現するのか?
BFアルゴリズム
暴力的なマッチングアルゴリズムは、シンプルなマッチングアルゴリズムとも呼ばれます.
メインストリングとモードストリング
文字列Aの中で文字列Bを探して、あのAはメインストリングで、Bはモードストリングで、メインストリングの長さをnと書いて、モードストリングの長さはmと書いて、メインストリングの中でモードストリングを探すので、n>m
最も簡単で最も暴力的な文字列マッチングアルゴリズムとして、BFアルゴリズムは私達がメインストリングの中で、スタート位置はそれぞれ0,1,2…n-mで、長さはmのn-m＋1個のサブストリングがありますか?
メインストリングが「aaa…aa」モードの列が「aaaaaab」なら、私達は毎回m文字と比較して、n-m＋1と比較します.最も複雑な時間複雑度はO(n∗m)O(n*m)O(n∗m)です.
BFアルゴリズムの時間の複雑さは高いが、一般的な文字列マッチングアルゴリズムです.一:実際のソフトウェア開発では、モードストリングとメインストリングの長さはそんなに長くないです.毎回、モードストリングとメインストリングのサブストリングが一致すると、途中でマッチできない文字に出会うと停止します.m文字を全部比較する必要はありません.シンプルな文字列をアルゴリズムに合わせるのは簡単です.間違えにくいです.バグがあっても暴露して修復しやすいです.
RKアルゴリズム
RKアルゴリズムはBFアルゴリズムに基づいて改良され、シンプルな文字列マッチングアルゴリズムの改造に対して、ハッシュアルゴリズムを導入すると、時間の複雑さが低減される.
ハッシュ・アルゴリズムによって、メイン・列のn−m＋1個のサブストリングにそれぞれハッシュ値を求め、次いで、一つずつパターン・ストリングのハッシュ値と比較すると、あるサブストリングのハッシュ値がモード・ストリングと等しい場合、対応するサブストリングとモード・ストリングが一致することを示す.
このとき、ハッシュアルゴリズムの設計は、一致する文字列の文字セットがK文字だけを含むと仮定して、1つのK進数でサブストリングを表すことができ、このK進数は10進数に変換され、サブストリングのハッシュ値として使用される.
処理する文字列はa~z 26文字の小文字しか含まれていません.この26進数で文字列を表します.a
~zの26文字を0~25の26文字にマッピングします.aは0、bは1、zは25です.10進数の表示法では、1つの数字の値は次の方法で計算され、26進数に対応します.aからzまでの26文字を含む文字列の一つで、ハッシュ値を計算するときは、キャリーを10から26に変更するだけで「657」＝6∗10∗10+5?10+7?1「c b」＝「c」26?26+「b」26+「b」＋26?26++26:+26:::::+26::::::「「「「???????????????????????????????????????????????????????」」」」」」+26*10+7*1「c b a」=「c」＊26*26+「b」26+「a」＊1=2*26*26+1*26+0*1=1353「657」=6∗10∗10+5?10+5?10+7+7?1「c b a」=「c」26?26+「b」?26+「a」26+「a」26+「a」26+「a」26+「a」+1+1+1字+1字+1字+1字+1字+2787+ 1字+278787+ 2787+ 2787+ 2787+ 2787+ 1字+1字+2787+ 2787+ 2787文字列、対応するハッシュ値は26進数で10進数に変換された結果です.このようなハッシュアルゴリズムの主な列のうち、隣接する2つのサブストリングのハッシュ値の計算式には、ある関係がある.隣接する2つのサブストリングs[i-1]とs[i](iは、サブストリングの開始位置を表し、サブストリングの長さは共にmである.s[i-1]のハッシュ値を使用することにより、s[i]のハッシュ値h[i−1]を素早く算出することができる.のハッシュ値、h［i］は、サブストリングs［i,i＋m−1］のハッシュ値h［i−1］＝2 6(m−1)∗(s［i−1］−−−a’)＋2 6(m−1)−−−−−−−−−−−−−−−−−−−−−−1)＋＋2−0−−−−−−−−−−0−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−2−−−−−−−−−−−−0−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−ヽ.i＋m−2−−−−−−−−−−a’＋2 6−0∗(s［i＋m−1−−−−−−−−1］−a’)式は、B＝A−8727であることが分かるので、h［i］とh［i−1］の関係は、h［i］=(h［i−1］−2−−6(m−1)−−1(m−1)−−−−−−−−−−−−1)−−−−−−−−−−−−−−−−−−−1(m−−1)−−−−−−−−−−−−−−−−−−−−−−−−−−−−1(m−−−−−−−−−−−−−−−−−−−−s[i-1,i+m-2]のハッシュ値は、h[i]がサブ串s[i,i+m-1]のハッシュ値h[i-1]===26(m-1)*(s[i-1]-'''')+26(m-1)*(s[i]-')+………+26^0*(s[i+m-2]-''')h[i]===='''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''B=A*26なので、h[i]とh[i-1]の関係は、h[i]=(h[i-1]-26^(m-1)*s[i-1]-')*26+26^0*(s[i+m-1]-'a')h[i−1]に対応するサブシリアルsです.i−−1,i＋m−2のハッシュ値、h［i］は、サブ列s［i,i＋m−1］のハッシュ値h［i−−1］＝26(m−1)∗(s［i−1］−a’)＋26(m−1)−−−−−−−i(m−1)−−−−−−−−−−−−−−−−−−−−−−−−−i(s−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−1)−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−＋…＋26∗(s[i＋m−2]−a')＋260∗(s[i＋m−1]−a′)の数式から、B=A∗26とh[i]とh[i−1]の関係は、h[i]=(h［i−1］−26(m−1)s［i−1］−a’)∗26＋260∗(s［i＋m−1］−a’)ここの26
^(m−1)この計算は、表を調べる方法によって効率を向上させ、26、459126、45914、674、…また、1つのmの配列に格納され、26のx乗を計算する際には、配列からxと標示された位置から値を取ることができ、直接に使用されます.RKアルゴリズムの時間複雑さはO(n)である.
二次元文字列行列(メインストリング)の場合、他の二次元文字列行列(モードストリング)を検索しますか?
KaTeX parse error:Unidefined control sequence:\matix at position 13:メインストリング=\left[\̲m̲a.̲t̲r̲i̲x̲｛d&a&b&…
KaTeX parse error:Unidefined control sequence:\matix at position 14:モード列=\left[\̲m̲a.̲t̲r̲i̲x̲｛c&a\\e&…
最初の行の文字列を検索します.長さがmなら、bfやrkでも大丈夫です.n
^nの配列なら、bf複雑度は(n-m)^n、rk複雑度はnです.マッチがある場合は、2行目からm行目の文字列に順次マッチします.複雑度は最初と同じですので、複雑度は異なります.