4

text文字列のアナグラムである文字列から部分文字列を見つけようとしていますpattern。

私の質問： ラビン-カープアルゴリズムをこの目的に合わせて調整できますか？または、より良いアルゴリズムはありますか？

私はブルートフォースアルゴリズムを試しましたが、テキストとパターンはそれぞれ最大100万文字になる可能性があるため、私の場合は機能しませんでした。

更新： O（1）スペースを使用する最悪の場合のO（n 2）アルゴリズムがあると聞きました。誰かがこのアルゴリズムが何であるか知っていますか？

更新2：参考までに、Rabin-Karpアルゴリズムの擬似コードは次のとおりです。

function RabinKarp(string s[1..n], string sub[1..m])
    hsub := hash(sub[1..m]);  hs := hash(s[1..m])
    for i from 1 to n-m+1
       if hs = hsub
          if s[i..i+m-1] = sub
              return i
       hs := hash(s[i+1..i+m])
    return not found

これはローリングハッシュ関数を使用してO（1）で新しいハッシュを計算できるようにするため、全体的な検索は最悪の場合はO（nm）ですが、適切なハッシュ関数を使用すると、最良の場合はO（m + n）になります。 。few collisions文字列のアナグラムを検索するときに生成されるローリングハッシュ関数はありますか？

4

4 に答える 4

9

パターン内の文字の順序に依存しないパターンのハッシュを計算します（たとえば、各文字の文字コードの合計を使用します）。次に、Rabin-Karpの場合と同じように、同じハッシュ関数を「ローリング」方式でテキストに適用します。ハッシュが一致する場合は、ハッシュが他の値とも衝突する可能性があるため、テキスト内の現在のウィンドウに対してパターンの完全なテストを実行する必要があります。

アルファベットの各記号を素数に関連付け、それらの素数の積をハッシュコードとして計算することで、衝突が少なくなります。

ただし、次のような実行中の製品を計算する場合に役立つ数学的なトリックが少しあります。ウィンドウをステップ実行するたびに、実行中のハッシュコードにシンボルのコードの逆数を掛けます。ウィンドウを離れてから、ウィンドウに入るシンボルのコードを掛けます。

例として、文字「a」〜「z」のハッシュを符号なし64ビット値として計算しているとします。次のようなテーブルを使用します。

シンボル| コード| コード-1
------- + ------ + ---------------------
   a | 3 | 12297829382473034411
   b | 5 | 14757395258967641293
   c | 7 | 7905747460161236407
   d | 11 | 3353953467947191203
   e | 13 | 5675921253449092805
  ..。
   z | 103 | 15760325033848937303

nの逆数は、ある数を法として、 nを掛けたときに1を生成する数です。64ビットの数値を使用しているため、ここでのモジュラスは264です。したがって、5 * 14757395258967641293たとえば1にする必要があります。GF（2 64 ）で乗算しているだけなので、これは機能します。

最初の素数のリストを計算するのは簡単です。プラットフォームには、これらの数値の逆数を効率的に計算するためのライブラリが必要です。

2は整数のサイズ（作業中のプロセッサでは2の累乗）と互いに素であり、反転できないため、数値3でコーディングを開始します。

于 2013-02-03T01:27:42.763 に答える
8

1つのオプションは、ウィンドウ内に含まれる文字のヒストグラムを保持するスライディングウィンドウを維持することです。そのヒストグラムが、アナグラムを見つける必要のある文字列の文字ヒストグラムと等しくなる場合は、見ているものが一致していることがわかり、それを出力できます。そうでなければ、あなたはあなたが持っているものがおそらく一致することはできないことを知っています。

より具体的には、文字からその頻度への連想配列Aマッピングを作成します。文字列Pのアナグラムを検索する場合は、最初の|P|を読み取ります。テキスト文字列TからAへの文字を入力し、ヒストグラムを適切に作成します。ウィンドウを1ステップ前にスライドし、ウィンドウの最初の文字に関連付けられた頻度を減らしてから、ウィンドウにスライドした新しい文字に関連付けられた頻度を増やすことにより、O（1）連想配列操作のAを更新できます。

現在のウィンドウとパターンウィンドウのヒストグラムが大きく異なる場合は、それらをかなりすばやく比較できるはずです。具体的には、アルファベットがΣだとしましょう。最悪の場合、2つのヒストグラムの比較には時間O（|Σ|）がかかります。これは、ヒストグラムAの各文字/頻度のペアを参照ヒストグラムで確認する必要があるためです。ただし、最良の場合は、Aと参照ヒストグラムの不一致の原因となる文字をすぐに見つけることができるため、全体として多くの文字を調べる必要はありません。

理論的には、このアプローチの最悪の場合の実行時間はO（|T||Σ|+| P |）です。これは、初期ヒストグラムを作成するためにO（n）の作業を実行し、次に最悪の場合のΣの作業を実行する必要があるためです。 Tの文字ごと。ただし、これは実際にはおそらくはるかに高速であると思います。

お役に立てれば！

于 2013-02-03T00:08:49.207 に答える
3

  1. 26 int（ゼロに設定）の配列letter_countsと、欠落している文字の数を保持する変数missing_countを作成します。

  2. サブストリング内の文字ごとに、letter_countsの関連するintを1ずつデクリメントし、missing_countを1ずつインクリメントします（したがって、missing_countはサブストリングのサイズと等しくなります）。

  3. サブストリングのサイズがkであるとします。文字列の最初のk文字を見てください。letter_countsの関連するintを1ずつインクリメントします。インクリメントした後、値が<= 0の場合、missing_countを1だけデクリメントします。

  4. ここで、このように文字列に沿って「ロールフォワード」します。a。ウィンドウの先頭に最も近い文字を削除し、letter_countsの関連メンバーをデクリメントします。デクリメント後、int <0の場合、missing_countを1ずつインクリメントします。ウィンドウの向こう側に文字列の最初の文字を追加します。letter_countsの関連メンバーをインクリメントします。インクリメントした後、int <= 0の場合、missing_countを1デクリメントします。

いずれかの時点でmissing_count==0の場合、ウィンドウに検索文字列のアナグラムが表示されます。

私たちが維持する不変条件は、missing_countが、ウィンドウにないサブストリング内の文字の数を保持することです。これがゼロの場合、ウィンドウ内の文字はサブストリング内の文字と完全に一致します。

これはTheta（n）です。各文字を1回だけ見るので、線形時間です。

- - 編集 - -

letter_countsは、部分文字列の個別の文字のみを格納する必要があり、部分文字列のサイズ（符号付き）と同じ大きさの整数のみを保持する必要があります。したがって、メモリ使用量はサブストリングのサイズでは線形ですが、ストリングのサイズでは一定です。

于 2013-02-12T15:51:13.660 に答える
0

これを提案するのはばかげているかもしれませんが、1つの代替方法は、2つの文字列を配列に分割してから、文字ごとに再帰的に検索することです。

重複する文字の一致を回避するために、配列内で文字が見つかった場合、textそれぞれの配列インデックスが削除され、一致するたびに完了配列スキャンまでの時間が効果的に短縮され、同時にtext2x'B'が含まれるようになります。 'apatternを3x'B'と一致させません。

パフォーマンスを向上させるために、文字ごとのカウントを行う前に両方の文字列をスキャンし、各文字列に存在するアルファベットのリストを作成し、それらのリストを比較して不一致があるかどうかを確認できます（たとえば、 「アップル」の文字「z」）、および文字列がある場合は「アナグラム不可」としてマークします。

于 2013-02-12T15:02:49.247 に答える