6

最長の重複しない部分文字列の (最適な?) アルゴリズムを誰かが知っているのだろうか。

たとえば、文字列で

アバゼッドバデス

最も長く繰り返されるのは「BAD」です。ちなみに、そのような結果がない場合、アルゴリズムはそのようなことが発生したことを警告する必要があります。私の推測では、これには接尾辞ツリーが含まれていると思います。

きっとこれはどこかにすでに存在しているに違いない。助けてくれてありがとう！

4

4 に答える 4

5

接尾辞配列は、その問題を解決するための優れたデータ構造です。

Jon Bentley によるProgramming Pearlsに、この問題の解決策があります。

于 2009-08-24T17:54:11.720 に答える
4

これを音楽に適用しているので、おそらく100％一致するものを探しているわけではありません。テーマのあるインスタンスから別のインスタンスへの不一致が予想されます。遺伝子配列分析アルゴリズムを調べてみるとよいでしょう。そこでは、このようなさまざまなことが行われています。BLASTまたは他のアライメントアルゴリズムを試してください。

WinEPIファミリーのアルゴリズム、およびこの特定の結果セットのさまざまなプレフィックスツリーの実装を試すこともできます（これらの結果では、サブストリングにギャップが生じます。たとえば、ABCIDとAFBCDの両方にABCDが含まれます）。私は実際に、興味があれば一見の価値があるかもしれないアルゴリズムに関する論文を持っています。配布承認を取得する必要がありますので、お知らせください。

これは実際には、大規模なデータセットでは（効率的に行うために）非常に複雑な主題であることに注意してください。

出典：同等の（テーマ検出）トピックに関する1、2年の調査。

于 2009-08-24T17:46:10.957 に答える
1

簡単なアルゴリズムはこれを行うことです：

  • 文字列のスライスを表すデータ構造を作成します。言語に応じて比較/ソートを実装する
  • [first-character, last-character]、[second-character、last-character] から [last-character, last-character] までの文字列のすべてのスライスのリストを作成します
  • このリストを並べ替える - O(n log n)
  • これにより、共通のプレフィックスを持つすべての文字列スライスがまとめられます。次に、リストを反復処理し、各ペアを比較して、最初に共有する文字数を確認します。最大値よりも大きい場合は、それをメモして新しい最大値として設定します

（投稿された他の返信が示すように、ここでは接尾辞配列について説明しています。）

于 2009-08-24T17:55:06.367 に答える
0

さて、ここに 1 つのクレイジーなアイデアがあります。

O(n) (n はテキストの長さ) に長さ k の繰り返し部分文字列があるかどうかを判断する関数を作成します。これは、ローリング ハッシュ ( Rabin-Karp String Matching Algorithm のウィキペディアを参照) を使用して線形時間ですべての n ハッシュを生成し、hashtable/BST (またはマップまたは dict または言語で呼び出されるもの) を使用して、対応する部分文字列の位置。現在のハッシュをデータ構造に挿入する前に、以前にそれを見たかどうかを確認します。以前に見られた場合は、このハッシュが生成されたインデックスを検索し、対応する部分文字列が重複しない一致であるかどうかを確認します。

O(n) 時間で ak の長さの部分文字列を見つけることができるようになったので、バイナリ検索を実行して、関数を使用して重複しない部分文字列の一致を見つけることができる最大の k を見つけます。

Python のコードは次のとおりです

A=23
MOD=10007 # use a random value in the real world

def hsh(text):
    return sum([ord(c)*A**(len(text)-i-1) for i,c in enumerate(text)])%MOD

def k_substring(text, k):
    substrings={}
    cur=hsh(text[:k])
    pwr=(A**(k-1))%MOD
    substrings[cur]=[0]
    for i in xrange(k,len(text)):
        to_remove=(ord(text[i-k])*pwr)%MOD
        to_add=ord(text[i])
        cur-=to_remove
        if cur<0:
            cur+=MOD
        cur=(cur*A)%MOD
        cur=(cur+to_add)%MOD
        if cur in substrings:
            lst=substrings[cur]
            for index in lst:
                if index+k<=i-k+1 and text[index:index+k]==text[i-k+1:i+1]:
                    return index
            lst.append(i-k+1)
        else:
            substrings[cur]=[i-k+1]
    return -1

def longest_substring(text):
    hi,lo=len(text),0
    while hi>lo:
        mid=(hi+lo+1)>>1
        if k_substring(text,mid)==-1:
            hi=mid-1
        else:
            lo=mid
    index=k_substring(text,lo)
    return text[index:index+lo]

（これが不明確でしたら申し訳ありません。ここは午前6時30分です。私は本当にベッドに戻る必要があります:)）

于 2009-08-24T23:34:51.627 に答える