3

バックトラッキングを使用して、可変長の一致を可能にする長い文字列内のすべての部分文字列を検索したいと思います。つまり、指定された最大数の不一致、挿入、および削除を許可する一致です。有用な例を見つけることができませんでした。私が見つけた最も近いものは、こちらの論文ですが、それは非常に複雑です。誰？

乾杯、

マーティン

4

3 に答える 3

3

アルゴリズム

以下の関数ff()は、再帰 (バックトラッキング) を使用して問題を解決します。基本的な考え方は、 への呼び出しの開始時に、元の「needle」文字列のサフィックスを「haystack」文字列f()のサフィックスに一致させようとする一方で、各タイプの編集操作を特定の数だけ許可するというものです。ts

// ss is the start of the haystack, used only for reporting the match endpoints.
void f(char* ss, char* s, char* t, int mm, int ins, int del) {
    while (*s && *s == *t) ++s, ++t;    // OK to always match longest segment
    if (!*t) printf("%d\n", s - ss);    // Matched; print endpoint of match
    if (mm && *s && *t) f(ss, s + 1, t + 1, mm - 1, ins, del);
    if (ins && *s) f(ss, s + 1, t, mm, ins - 1, del);
    if (del && *t) f(ss, s, t + 1, mm, ins, del - 1);
}

// Find all occurrences of t starting at any position in s, with at most
// mm mismatches, ins insertions and del deletions.
void ff(char* s, char* t, int mm, int ins, int del) {
    for (char* ss = s; *s; ++s) {
//      printf("Starting from offset %d...\n", s - ss);
        f(ss, s, t, mm, ins, del);
    }
}

呼び出しの例:

ff("xxabcydef", "abcdefg", 1, 1, 1);

これは以下を出力します:

9
9

「xxabcydef」で「abcdefg」を見つけるには、各種類の変更が最大で 1 つある方法が 2 つあり、これらの方法はどちらも 9 位で終わるためです。

Haystack: xxabcydef-
Needle:     abc-defg

1 つの挿入 ( のy) と 1 つの削除 ( のg) があり、

Haystack: xxabcyde-f
Needle:     abc-defg

これには、1 つの挿入 (のy)、1 つの削除 (のf)、および 1 つの置換がありgますf。

支配関係

while3 行目のループを使用して、2 つの文字列の先頭にあるできるだけ多くの文字を貪欲に一致させることが実際に安全である理由は明らかではないかもしれません。実際、これにより、特定の終了位置が一致として報告される回数が減る可能性がありますが、終了位置が完全に忘れられることはありません。マッチは干し草の山の特定の位置で終了します。このwhileループがなければ、アルゴリズムは常に針のサイズで指数関数的に時間がかかります。これは双方にメリットがあるようです。

優劣関係があるので動作保証されています。これを確認するために、実際には安全ではない (つまり、いくつかの一致を逃した) と考えてみてください。次に、両方の文字列の等しい文字の最初のセグメントが互いに整列されていない一致が発生します。次に例を示します。

Haystack: abbbbc
Needle:   a-b-bc

ただし、そのような一致は、ギャップの左側のギャップに続く左端の文字をシャントすることにより、各タイプの同じ数の操作を持ち、同じ位置で終了する別の一致に変換できます。

Haystack: abbbbc
Needle:   ab--bc

置換を必要とせずに文字をシャントすることができなくなるまでこれを繰り返し行うと、両方の文字列の等しい文字の最大の最初のセグメントが互いに整列する一致が得られます。

Haystack: abbbbc
Needle:   abb--c

私のアルゴリズムはそのような一致をすべて見つけるので、一致位置が見落とされることはありません。

指数時間

他のバックトラッキング プログラムと同様に、この関数は特定の入力で指数関数的な速度低下を示します。もちろん、たまたま使用する入力では、これは発生せず、DP アルゴリズムの特定の実装よりも高速に機能する可能性があります。

于 2011-09-27T08:53:50.787 に答える
0

レーベンシュタインの距離アルゴリズムから始めます。これは、不一致、挿入、および削除によって文字列の類似性をチェックする際の標準的なアプローチです。

アルゴリズムはボトムアップの動的計画法を使用するため、潜在的な部分文字列ごとにアルゴリズムを実行しなくても、おそらくすべての部分文字列を見つけることができます。

于 2011-09-26T15:12:12.087 に答える
0

これについて私が知っている最も優れたアルゴリズムは、Gene Myers による動的プログラミングに基づく近似文字列マッチングのための高速ビット ベクトル アルゴリズムです。長さ n の検索対象テキスト、長さ m の検索対象パターン文字列、および不一致/挿入/削除の最大数 k を指定すると、このアルゴリズムには O(mn/w) の時間がかかります。ここで、w はコンピューターのワード サイズ (32または64）。文字列のアルゴリズムについてよく知っていれば、k とは無関係に時間がかかるアルゴリズムが存在することは、実際には非常に信じられないことです。長い間、これは不可能な目標のように思われていました。

上記のアルゴリズムの既存の実装については知りません。ツールagrepが必要な場合は、まさに必要なものかもしれません。O(mnk/w) の時間がかかる初期のアルゴリズムを使用しますが、低い k に対しては十分高速です。最悪の場合、バックトラッキング検索より数マイル先です。

agrepShift-Or (または「Bitap」) アルゴリズムに基づいています。これは、その状態を整数のビットとして表現し、状態を更新する作業のほとんどを実行するためにバイナリ加算を取得する、非常に巧妙な動的プログラミング アルゴリズムです。より典型的な実装よりも 32 倍または 64 倍アルゴリズムを高速化するものです。:) Myers のアルゴリズムもこのアイデアを使用して、1/w 速度係数を取得します。

于 2011-09-26T20:58:56.403 に答える