2

Rabin-Karp アルゴリズムに基づいて、昇順で 2 つのテキスト ファイルの最長共通部分文字列を見つける関数を作成しました。メイン関数は「find_longest」で、内部関数は「make_hashtable」、「extend_fingerprints」、および「has_match」です。has_matchの平均的なケースの複雑さを分析するのに問題があります。

n1,n2 を text1,text2 として、l を現在の「ウィンドウ」のサイズとして示します。finger は部分文字列のハッシュ テーブルです。

def has_match(text1,text2,fingers1,fingers2,l,r):
h = make_hashtable(fingers2,r)
for i in range(len(fingers1)):
    for j in h[fingers1[i]]:
        if text1[i:i+l] == text2[j:j+l]:
            return text1[i:i+l]
return None

これは「make_hashtable」です。ここでは、complexity が O(n2-l+1) であることを確信しています。

def make_hashtable(fingers, table_size):
hash_table=[[] for i in range(table_size)]
count=0
for f in fingers:
    hash_table[f].append(count)
    count+=1
return hash_table

これは「find_longest」です。複雑さの分析には必要ないという事実にもかかわらず、この関数を追加しています。

def find_longest(text1,text2,basis=2**8,r=2**17-1):
match = ''
l = 0 #initial "window" size
#fingerprints of "windows" of size 0 - all are 0
fingers1 = [0]*(len(text1)+1)
fingers2 = [0]*(len(text2)+1)

while match != None: #there was a common substring of len l
    l += 1
    extend_fingerprints(text1, fingers1, l, basis, r)
    extend_fingerprints(text2, fingers2, l, basis, r)
    match = has_match(text1,text2,fingers1,fingers2,l,r)
    print(match)
return l-1

これは「extend_fingerprints」です。

def extend_fingerprints(text, fingers, length, basis=2**8, r=2**17-1):
count=0
for f in fingers:
    if count==len(fingers)-1:
        fingers.pop(len(fingers)-1)
        break
    fingers[count]=(f*basis+ord(text[length-1+count]))%r
    count+=1

この2つのオプションの間に疑問があります:

1. O(n_2-l+1)+O(n_1-l+1)*O(l) r を定数として参照しますが、n1、n2 は非常に大きいため、ハッシュ テーブルで多くの衝突が発生します (すべての「セル」で O(1) アイテムとしますが、常にいくつかの「偽陽性」とします)。 "）

2.O(n_2-l+1)+O(n_1-l+1)+O(l)
適切なハッシュ関数に最適な r を参照してください。したがって、衝突はほとんどありません。つまり、ハッシュ テーブルで 2 つのテキストが同じセルである場合、それらは実際には同じテキストであると想定できますか?

個人的には大胆な声明に傾いています。tnx。

4

1 に答える 1

1

答えは

O((n_2-l) + l*(n_1-l))

. (n_2-l) は、2 番目のテキストの make_hashtable の複雑さを表します。l*(n_1-l) は、最初のテキストのフィンガー プリントのすべてのアイテムを通過し、1 つの比較操作 (長さ l のスライス) を実行する 2 つのネストされたループを表します。ハッシュ テーブルの同じインデックス。

于 2013-06-01T15:30:00.913 に答える