Домашнее задание: Внедрение Карп-Рабина; Для значений хеш-функции по модулю q объясните, почему плохая идея использовать q как степень 2?

Question

У меня двоякая домашняя задача: внедрить Karp-Rabin, запустить его на тестовом файле и второй части:

2. Для значений хеш-функции по модулю 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))

... Вторая часть вопроса относится к этой части кода / алгоритма:

    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, это должно вызвать много столкновений для хэшей, поэтому вам нужно будет сравнивать строки намного больше, но я также не нашел ничего подобного.

Я очень признателен за помощь в этом, так как я в тупике. Если кто-то захочет указать на то, что я могу сделать лучше в первой части (эффективность кода, читаемость, правильность и т. Д.), Я также буду рад услышать ваше мнение по этому поводу.

Answer 1

Существует проблема, если q делит некоторую степень d, потому что тогда только несколько символов вносят вклад в хеш. Например, в вашем коде d=4, если вы берете q=64, только последние три символа определяют хэш (d**3 = 64).

Я не вижу проблемы, если q является степенью 2, но gcd(d,q) = 1.

Ваша реализация выглядит немного странно, потому что вместо

if pattern_hash % q == text_hash % q and pattern == text[i:i+n]:

Вы также можете использовать

if pattern_hash == text_hash and pattern == text[i:i+n]:

что было бы лучше, потому что вы получаете меньше столкновений.

Answer 2

Последовательность Туэ – Морса имеет среди своих свойств то, что ее полиномиальный хэш быстро становится равным нулю, когда степень 2 является хеш-модулем для любой полиномиальной базы (d). Поэтому, если вы попытаетесь найти короткую последовательность Туэ-Морса в более длинной последовательности, у вас будет много коллизий хешей.

Например, ваш код немного адаптирован:

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'))

выводит много позиций, хотя только три из них являются правильными.

Обратите внимание, что я уронил and pattern == text[i:i+n] проверять. Очевидно, что если вы восстановите его, результат будет правильным, но также очевидно, что алгоритм будет выполнять гораздо больше работы, проверяя это дополнительное условие, чем для других q, На самом деле, поскольку коллизий так много, сама идея алгоритма становится неработоспособной: вы могли бы почти так же эффективно написать простой алгоритм, который проверяет каждую позицию на совпадение.

---

Также обратите внимание, что ваша реализация довольно странная. Вся идея полиномиального хеширования состоит в том, чтобы выполнять операцию по модулю каждый раз, когда вы вычисляете хеш. В противном случае ваш pattern_hash а также text_hash очень большие цифры. В других языках это может означать арифметическое переполнение, но в Python это вызовет целочисленную арифметику, которая является медленной и снова теряет всю идею алгоритма.