Как получить одинаковый хэш двух схожих строк?

Question

[blare]

К примеру, есть две схожие строки:


Москва, ул. Васюковская 12


Москва, ул. Васюковая 121


Нужно чтобы хэш их был одинаковый. Подскажите есть ли подобные алгоритмы?

Comments

[blare]

Основное условие: строки сравнивать нельзя.

[blare]

В качестве сравниваемых строк могут быть не адреса

Answer 1

[Donskoy]

Simhash или charikar's hash.
Используется в гугле для поиска похожих документов. Легко переделывается для строк (в качестве фич берутся не биграммы-токены, а биграммы-символы).
Подробный алгоритм здесь.
Теоретическое обоснование – в статье «Similarity estimation techniques from rounding algorithms».

Answer 2

[barker]

см. расстояние Левенштейна.

А хеш одинаковый это вряд ли, конечно…

Answer 3

[el_gato]

Не получится, слишком много неопределенностей, особенно без сравнения строк, для примера
Васюковая -> Масюковая -> Масюковае -> Масюковое -> Масуковое -> Мосуковое -> Мозуковое -> Мозуговое -> Мозугавое -> Мозугадое
Каждое слово схоже с следующим, и следовательно должено иметь одинаковый хэш, но разница между первым и последним уже огромная.

Answer 4

[Ололёша Ололоев]

Совсем без сравнений, как мне кажется, нельзя. Если нет возможности сравнивать входящие данные, сравнивайте выходящие — сами хэши.

Answer 5

[bachin]

выкидываем из строки все цифры (+пробелы, +знаки препинания).
от остального считаем хэш любым алгоритмом (CRC32, MD5, etc)
ваши строки сматчатся в одно значение.
вы этого хотели?
если нет — потрудитесь объяснить что значит «схожие строки» — на мой взгляд это совсем разные строки — дом 12 по улице Васюковской — это 8-подъездная многоэтажка, а дом 121 — это ветхая хибара.

Comments

[blare]

Применение не обязательно к адресам. Это может быть что угодно.
Хэши могут отличаться, но так, что бы была возможность при задании некого коэффициента схожести говорить, что эти строки одинаковые.

[bachin]

Тогда стоит определиться что значит «коэффициент схожести»
Например, «Васюковская улица» и «ацилу яаксвокюсаВ» — совсем несхожие строки, а состоят из одинаковых букв. То есть формально они схожие.
Рассматриваем вашу задачу формально — строки являются схожими, если одна переводится в другую заменой не более N символов, убиранием не более M символов и вставлением не более K символов.
При N = 4, M = 3, K = 3 строка «счастье» будет равна строке «жопа»
Какие у вас коэффициенты?

[blare]

можно учитывать и порядок букв.
Я же не привожу свой алгоритм, у меня нет коэфициентов, мне интересно есть ли уже существующий, чтобы не изобретать велосипед

Answer 6

[dime]

Уточните вопрос
Вам нужен конкретный алгоритм, возвращающий одинаковый хэш для двух этих конкретных строк (и не важно что для всех остальных)?
Или вам нужен генератор алгоритмов хэш-функций, которому на вход дают две строки, а генератор генерирует такой алгоритм хэширования, чтобы для этих заданных строк получалась коллизия (и опять не важно, что там получится для всех остальных)?

Answer 7

[TheHorse]

Можно пробовать хеш функцию, которая является суммой всех символов div С, где С — константа, большая (например,100). Тогда с высокой долей вероятности, строки, которые отличаются на 1-2 символа будут попадать в один хеш.

В общем случае, для адресов не спасает расстояние Левенштейна, и не спасают какие либо хеш — функции.

Answer 8

[sergpenza]

Вначале их нужно привести к какому-то одинаковому виду
Разбить строку по словам, привести к одному регистру, выкинуть малозначительное и неуникальное, типа «ул.», знаки препинания и прочее.
Слить слова в строку, вида «москва васюковская» «москва васюковая», взять фонетический код, получится, например, 479465.
С цифрами несколько непонятно, какие будут варианты. Но в данном случае — выкинуть все повторы и оставить только цифры, входящие в номер как первой строки, так и второй.

Таким образом у нас получится две одинаковые строки (если фонетический код совпадет) вида

«479465 12»
«479465 12»

Можно вычислять хэш.

Comments

[blare]

Спасибо, за интересные мысли

Answer 9

[AR1ES]

Подобный вопрос: stackoverflow.com/questions/10599401/hashing-similar-strings-to-same-hash-value

Comments

[blare]

Спасибо

Answer 10

[Spamkit]

Не думали насчет алгоритмов нечеткого поиска, как, например, Soundex или метафон? Готовая имплементация есть в Apache Codec, алгоритмы Metaphone и Metaphone 2.

Смотрите вот здесь. Онлайн демка (работает судя по всему только с латиницей).

Answer 11

[egorinsk]

Я когда-то думал над подобным способом для поиска слов с опечатками. Одним хешем тут точно не обойтись, и вот почему. Допустим (упростим задачу), все слова имеют одинаковую длину, например, 4 символа, мы хотим, чтобы у слов, различающихся 1 буквой, был одинаковый хеш. Тогда слова abcd и abce имеют одинаковый хеш, слова abcd и zbcd имеют одинаковый хеш… в итоге, все слова будут иметь один и тот же хеш.

Потому, одним хешем тут не обойтись. Нужно как минимум, несколько.

Например, хеш для всех букв, кроме первой. Хеш для всех, кроме второй, и т.д. Тогда у различающихся 1 буквой слов будут 2 совпадающих хеша.

Или другой подход — разбиение слов на триграммы и поиск по ним. У похожих слов большинство триграмм будет одинаковыми.

Answer 12

[Mikhail Osher]

Напишите функцию, которая примет a='Москва, ул. Васюковская 12 ' и b='Москва, ул. Васюковая 121' и вернет true для определенных условий (что-то вроде дом начинается одинаково && первые 5-6 символов улиц начинаются/заканчиваются одинаково && одинаковый город). Тогда берите все части, которые совпали и берите по ним хэш.
Скажем, для данного примера возьмите хэш по выделенной строке:
Москва, ул. Васюковская 12
Москва, ул. Васюковая 121

Тут кол-во коллизий не так уж и мало.
Этот алгоритм был выдуман сразу после прочтения, и вероятнее всего есть куда более элегантные решения.

Comments

[blare]

Я уточнил вопрос, строки не сравниваются между собой

Answer 13

[MikhailEdoshin]

Нет. Как вы себе представляете работу такой функции? А если дом 122? Или 21? Тоже одинаковый хэш должен быть? А если улица «Масюковская» — тоже? А когда он должен делаться неодинаковый?

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

Comments

[blare]

адреса приведены в качестве примера, да должен быть одинаковый

Answer 14

[AR1ES]

Вообще, вопрос противоречит сам себе.
Насколько я помню, одна из основных особенностей (требований или хз как назвать) хэша заключается в том, что он должен выдавать совершенно разные значения даже для максимально близких строк.

А так алгоритмов реальных не знаю, но если писать очередной велосипед, то TheHorse предложил то же, что и мне в голову. Я бы только дополнил немного, что полученное число я бы использовал не как хэш, а для инициализации генератора случайных чисел и из него бы уже вытягивал хэш нужной длины.

Comments

[spiff]

Не совсем. Контакт у хеш функции такой:
1) Равенство/одинаковость объектов значит, что хеши равны.
2) Неравенство/неодинаковость объектов не означает, что хеши разные.

Answer 15

[AR1ES]

Вообще, вопрос противоречит сам себе.
Насколько я помню, одна из основных особенностей (требований или хз как назвать) хэша заключается в том, что он должен выдавать совершенно разные значения даже для максимально близких строк.

А так алгоритмов реальных не знаю, но если писать очередной велосипед, то TheHorse предложил то же, что и мне в голову. Я бы только дополнил немного, что полученное число я бы использовал не как хэш, а для инициализации генератора случайных чисел и из него бы уже вытягивал хэш нужной длины.

Comments

[AR1ES]

Приношу свои извинения… Проблемы с интернетом.

Answer 16

[AR1ES]

Вообще, вопрос противоречит сам себе.
Насколько я помню, одна из основных особенностей (требований или хз как назвать) хэша заключается в том, что он должен выдавать совершенно разные значения даже для максимально близких строк.

А так алгоритмов реальных не знаю, но если писать очередной велосипед, то TheHorse предложил то же, что и мне в голову. Я бы только дополнил немного, что полученное число я бы использовал не как хэш, а для инициализации генератора случайных чисел и из него бы уже вытягивал хэш нужной длины.

Answer 17

[Евгений Лещенко]

Вомзожно можно оптимизировать алгоритм шинглов, только вместо слов использовать n-ое кол-во символов.

Answer 18

[Dilon]

В свое время довелось использовать ssdeep.sourceforge.net/ для похожей задачи.

Comments

[Dilon]

Под одинаковостью для вашей задачи, я понимаю схожесть между двумя хэшами на >N%.

Answer 19

[EndUser]

Мдя… А зачем вам такая функция?
Функция «хэш» характерна минимальными коллизиями.
Вам, по-видимому, в задаче нужна другая функция. Например «индекс».

Answer 20

[Donskoy]

Если нужно сравнивать имена собственные, то вместо Левенштейна лучше подходит Jaro-Winkler distance.
Эта метрика была разработана для поиска имен с похожим написанием (или с ошибками в написании) при переписи населения в США.

Answer 21

[Ryadovoy]

Смотри метод Хеширование по сигнатуре + расстояние Левенштейна
habrahabr.ru/post/114997/