хэш-функция для индексации подобного текста - PullRequest
Новая
       20

хэш-функция для индексации подобного текста

4 голосов
/ 14 июля 2010

Я ищу что-то вроде хэш-функции для индексации подобного текста.Так, например, если у нас есть два очень длинных текста, называемых «A» и «B», где A и B отличаются не так сильно, то хеш-функция (называемая H), применяемая к A и B, должна возвращать одно и то же число.

Итак, H (A) = H (B), где A и B. - похожий текст.

Я попробовал «DoubleMetaphone» (я использую текст на итальянском языке), но я увидел, что он очень сильно зависит отСтроковые префиксы.Например:

A = "Это очень длинный текст, который я хочу хэшировать" B = "Это очень"

==> doubleMetaPhone (A) = doubleMetaPhone (B)

И это не так хорошо для меня, потому что строки с одинаковым префиксом можно сравнивать как похожие, и я не хочу этого.

Может кто-нибудь предложить мне другой способ?

Ответы [ 2 ]

2 голосов
/ 14 июля 2010

Ваша проблема (близка к) неразрешима для многих функций расстояния между строками.

Большинство функций расстояния (например, редактирование расстояния ) позволяют преобразовать строку в другую строку с помощью последовательностииз преобразований на 1 расстояние: 

"AAAA" -> "AAAB" -> "AAABC"

в соответствии с вашими требованиями, первая и вторая строки должны иметь одинаковое значение хеш-функции.Но так должно быть вторым и третьим, и так далее.Таким образом, все строки должны будут иметь одинаковый хеш, , если мы позволим паре с расстоянием = 1 иметь одинаковое значение хеш-функции.

Даже если мы установим более высокий порог для расстояния(возможно, относительно длины строки), мы получим грязный результат.

Лучший (IMO) подход - найти отношение эквивалентности на множестве строк, например,что каждая строка в каждом классе эквивалентности имеет одинаковый хэш.Возможность состоит в том, чтобы определить классы по их расстоянию до предварительно определенной строки (например, расстояние редактирования от «AAAAA»), и само расстояние будет значением хеш-функции.Вероятно, этот подход не будет лучшим в вашем случае, но, возможно, с некоторой дополнительной информацией по проблеме, мы можем придумать лучшее отношение эквивалентности.

1 голос
/ 20 декабря 2010
...