誰かが最も重複しない重複しないサブストリングの（最適な？）アルゴリズムを知っているのだろうかと思います。例えば最長の重複しないサブストリング
、文字列
ABADZEDGBADEZ
で最長の繰り返しは、 "BAD" になります。ちなみに、そのような結果がない場合、アルゴリズムはそのようなことが起こったことを警告しなければならない。私の推測では、これには接尾辞ツリーが含まれているということです。
これは既にどこかに存在しているはずです。助けてくれてありがとう！
音楽にこれを適用しているので、おそらく100％のマッチを探しているわけではありません。テーマの1つのインスタンスから別のインスタンスへの不一致が予想されます。あなたは遺伝子配列解析アルゴリズムを調べるかもしれません - そこにはさまざまなことが起こっています。 BLASTまたは他のアラインメントアルゴリズムを試してください。
また、この特定の結果セットのさまざまなプレフィックスツリー実装（これらの結果は、ABCIDとAFBCDの両方にABCDが含まれているなど、部分文字列の隙間が許されます）を使用することもできます。私は実際にあなたが興味を持っているかどうかを調べる価値のあるアルゴリズムに関する論文を持っています。私は配布認可を取得する必要がありますので、私に知らせてください。
これは、実際には、大規模なデータセットでは（効率的に）非常に複雑な対象です。
出典：比較可能な（テーマ検出）トピックで1年または2年間の研究。
私にアクセス権を与えることができれば、それは分かります！ –
彼はこれを歌詞に適用していると思うので、彼は100％マッチを探していると思う。 – las3rjock
@Brandon - 私は許可を要求しました。私は何ができるかを見ていきます。 @ las3rjock - 実際はありません。例えば： 私は愚かな男でした 私は愚かな男でした テーマの例：過去時制の愚かさ。文字列は完全一致ではありません。さらに、多くの歌詞には異なる句読点やその他のものがあります。だから私は彼が完全に一致するかどうかはわからない。 –
Suffix arrayは、この問題を解決するための優れたデータ構造です。
この問題の解決策は、Jon BentleyのProgramming Pearlsです。
プログラミングの真珠はどこにありますか？ –
@Emil H、** 15.2フレーズ** –
@Nick Programing Pearlsの同じソリューションをここで直接適用できるとは思いません。 「BANANA」の例は、OPによって言及された条件に反して、2回起こり、したがってオーバーラップする「ANA」を与える。重複していない状態では、一部の変更が必要になることがあります。あなたは何を言っていますか？ –
単純なアルゴリズムはこれを行うことです。
今投稿された他の返信は、ここで接尾辞配列を記述していることを示しています）。
これはまだかなり力強いです。もう少し洗練されたアプローチがあるのだろうか？ツリーベースのアプローチは、構造情報を保持するだけでなく、最長の長さの情報を提供するためにすばやくトラバースできる深度情報を提供すると信じています。 –
適切なソート - 接尾辞配列wikipediaの記事を参照してください - 最悪の場合、実行時間はO（n log n）、通常はより良いです。反復はO（n）なので、ソートコストが支配的です。明らかなブルートフォースは少なくとも（可能なすべてのペアを比較して）O（n^2）になるでしょう。ツリーを構築することは、より多くのメモリを必要とする可能性が高く、実績に悪影響を与えます（キャッシュなどを考慮します）。 –
O（n）（nはテキストの長さ）に長さkの反復部分文字列があるかどうかを判断する関数を作成します。これは、ハッシュテーブル/ BST（またはマップや辞書、またはあなたの言語がそれを呼んでいるもの）を使用して、対応する部分文字列の位置を格納するために、ローリングハッシュ（wikipedia Rabin-Karp String Matching Algorithmを参照）を使用して実行できます。現在のハッシュをデータ構造体に挿入する前に、以前に見たことがあるかどうかを確認します。以前に見たことがある場合は、このハッシュが生成されたインデックスを検索し、対応する部分文字列がオーバーラップしない一致であるかどうかを確認するだけです。
ここで、O（n）時間にk個の部分文字列を見つけることができます。バイナリ検索を実行して、関数を使って重複しない部分文字列一致を見つけることができる最大の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]
だけのビジネスアプリケーション何curious-（:)これは。不明であることは、午前6時30分ここにあると私は本当にベッドに戻って行く必要がある場合には申し訳ありません）このため？ – Beth
ビジネスアプリケーションではありません。これは、曲にテーマを見つけることに関連し、私がプロジェクトに参加するまで、現時点ではもっと古典的です。 =] –