0

Karp-Rabin を実装し、テスト ファイルと 2 番目の部分で実行するという 2 つの宿題の問題があります。

  1. q を法とするハッシュ値について、q を 2 の累乗として使用することがなぜ悪い考えなのかを説明してください。たとえば、q=64 と n=15 の場合のひどい例を作成できますか?

これはアルゴリズムの私の実装です:

def karp_rabin(text, pattern):
    # setup
    alphabet = 'ACGT'
    d = len(alphabet)
    n = len(pattern)
    d_n = d**n
    q = 2**32-1
    m = {char:i for i,char in enumerate(alphabet)}
    positions = []

    def kr_hash(s):
        return sum(d**(n-i-1) * m[s[i]] for i in range(n))

    def update_hash():
        return d*text_hash + m[text[i+n-1]] - d_n * m[text[i-1]]

    pattern_hash = kr_hash(pattern)
    for i in range(0, len(text) - n + 1):
        text_hash = update_hash() if i else kr_hash(text[i:n])
        if pattern_hash % q == text_hash % q and pattern == text[i:i+n]:
            positions.append(i)

    return ' '.join(map(str, positions))

...質問の2番目の部分は、コード/アルゴリズムのこの部分を参照しています:

    pattern_hash = kr_hash(pattern)
    for i in range(0, len(text) - n + 1):
        text_hash = update_hash() if i else kr_hash(text[i:n])
        # the modulo q used to check if the hashes are congruent
        if pattern_hash % q == text_hash % q and pattern == text[i:i+n]:
            positions.append(i)

q を 2 のべき乗として使用することがなぜ悪い考えなのか理解できません。提供されたテスト ファイル (ecoli のゲノム) でアルゴリズムを実行してみましたが、識別可能な違いはありません。

ハッシュがどのように導出されるかについての式を調べてみました (私は数学が苦手です)。q が 2 の累乗である場合、ハッシュに対して多くの衝突が発生するはずなので、文字列をさらに比較する必要があるように感じますが、それらの線に沿って何も見つかりませんでした。

私は困惑しているので、これについて助けていただければ幸いです。最初の部分で改善できる点 (コードの効率、読みやすさ、正確さなど) を誰かが指摘したい場合は、それについての意見もお待ちしています。

4

2 に答える 2

2

Thue-Morse シーケンスには、2 のべき乗がハッシュ モジュールである場合に多項式ベース ( ) が何であれ、その多項式ハッシュがすぐにゼロになるという特性がありますd。したがって、長い Thue-Morse シーケンスで短い Thue-Morse シーケンスを検索しようとすると、大量のハッシュ衝突が発生します。

たとえば、わずかに変更されたコード:

def karp_rabin(text, pattern):
    # setup
    alphabet = '01'
    d = 15
    n = len(pattern)
    d_n = d**n
    q = 32
    m = {char:i for i,char in enumerate(alphabet)}
    positions = []

    def kr_hash(s):
        return sum(d**(n-i-1) * m[s[i]] for i in range(n))

    def update_hash():
        return d*text_hash + m[text[i+n-1]] - d_n * m[text[i-1]]

    pattern_hash = kr_hash(pattern)
    for i in range(0, len(text) - n + 1):
        text_hash = update_hash() if i else kr_hash(text[i:n])
        if pattern_hash % q == text_hash % q : #and pattern == text[i:i+n]:
            positions.append(i)

    return ' '.join(map(str, positions))

print(karp_rabin('0110100110010110100101100110100110010110011010010110100110010110', '0110100110010110'))

多くの位置を出力しますが、適切な一致はそのうちの 3 つだけです。

小切手を落としたことに注意してand pattern == text[i:i+n]ください。明らかにそれを元に戻せば、結果は正しくなりますが、アルゴリズムがこの追加の条件をチェックするよりもはるかに多くの作業を行うことも明らかですq。実際、非常に多くの衝突があるため、アルゴリズムのアイデア全体が機能しなくなります。すべての位置で一致をチェックする単純なアルゴリズムを効果的に作成することもできます。

また、実装が非常に奇妙であることに注意してください。多項式ハッシュの全体的な考え方は、ハッシュを計算するたびにモジュロ演算を行うことです。そうでなければ、あなたのpattern_hashとtext_hashは非常に大きな数です。他の言語では、これは算術オーバーフローを意味する可能性がありますが、Python では、これにより大きな整数演算が呼び出されます。これは遅く、アルゴリズムの全体像が再び失われます。

于 2015-09-07T15:49:30.497 に答える