Go: полиномиальный отпечаток для сравнения строк

Я хочу реализовать скользящую хэш-функцию для сравнения строк (Рабин-Карп)

Для этого я преобразовываю свою входную строку в фрагмент байтов (используя go unicode/utf8) и применяю к ней функцию «полиномиального снятия отпечатков пальцев».

Например, я ввожу строку qwerty, которая переводится как [113 119 101 114 116 121] . Я использую базу 256.

rune 121, base 256.0, exponent 0, value 121
rune 116, base 256.0, exponent 1, value 29696
rune 114, base 256.0, exponent 2, value 7471104
rune 101, base 256.0, exponent 3, value 1694498816
rune 119, base 256.0, exponent 4, value 511101108224
rune 113, base 256.0, exponent 5, value 124244813938688

У меня проблемы с концепцией «полимониального отпечатка пальца»: быстро база становится действительно большой, как это может масштабироваться с вводом строки, которую пользователь хочет сопоставить?

В моем случае он запутался после 7 символов, потому что функция Go math.Pow использует тип float64.

rune 114, base 256.0, exponent 7, value 8214565720323784704
rune 101, base 256.0, exponent 8, value -9223372036854775808
rune 119, base 256.0, exponent 9, value -9223372036854775808
rune 113, base 256.0, exponent 10, value -9223372036854775808

Я чувствую, что использование uint64 просто немного продвинет проблему


go algorithm hash math rabin-karp
person Kuruwan    schedule 03.05.2020    source источник
comment
Вероятно, вы хотите, чтобы пакет math/big обрабатывал большие числа.   -  person Marc    schedule 03.05.2020
comment
Вы должны брать результат по модулю N для некоторого N (если вы делаете простой скользящий хеш, а не снятие отпечатков пальцев Рабина). Если вы используете дактилоскопию Рабина, это сложнее, но см.: github.com /aclements/go-rabin/tree/master/rabin   -  person Paul Hankin    schedule 03.05.2020
comment
math.Pow для этого не подходит, да и pow-функция вам вообще не нужна.   -  person Paul Hankin    schedule 03.05.2020
comment
Мне вообще не нужна функция pow, вы имеете в виду: просто реализовать ее? я смотрю на возведение в степень по квадрату   -  person Kuruwan    schedule 08.05.2020

Ответы (1)


arrow_upward
1
arrow_downward

Идея хеш-функции на самом деле заключается в том, что она будет переполняться, но с большой вероятностью разные строки будут давать разные хэши. Чтобы заставить его работать, вам нужно использовать взаимно простые числа для базы и модуля операций. Вы должны использовать некоторое простое основание (больше размера алфавита) и выполнять все операции по модулю некоторого простого числа (как можно большего) (простые числа приведут к минимальной вероятности столкновения). Используйте целочисленный тип для этого хеша. Если вам нужно, чтобы ваш алфавит был не менее 256 символов, вы можете использовать uint64, основание 257 и выполнять все операции, например, по модулю 1012+39

person Roman Svistunov    schedule 03.05.2020