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

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


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


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


Нужно чтобы хэш их был одинаковый. Подскажите есть ли подобные алгоритмы?
  • Вопрос задан
  • 8383 просмотра
Решения вопроса 1
Donskoy
@Donskoy
Simhash или charikar's hash.
Используется в гугле для поиска похожих документов. Легко переделывается для строк (в качестве фич берутся не биграммы-токены, а биграммы-символы).
Подробный алгоритм здесь.
Теоретическое обоснование – в статье «Similarity estimation techniques from rounding algorithms».
Ответ написан
Пригласить эксперта
Ответы на вопрос 21
barker
@barker
см. расстояние Левенштейна.

А хеш одинаковый это вряд ли, конечно…
Ответ написан
el_gato
@el_gato
Не получится, слишком много неопределенностей, особенно без сравнения строк, для примера
Васюковая -> Масюковая -> Масюковае -> Масюковое -> Масуковое -> Мосуковое -> Мозуковое -> Мозуговое -> Мозугавое -> Мозугадое
Каждое слово схоже с следующим, и следовательно должено иметь одинаковый хэш, но разница между первым и последним уже огромная.
Ответ написан
alexeygrigorev
@alexeygrigorev
Переворачиватель пингвинов
Совсем без сравнений, как мне кажется, нельзя. Если нет возможности сравнивать входящие данные, сравнивайте выходящие — сами хэши.
Ответ написан
@bachin
выкидываем из строки все цифры (+пробелы, +знаки препинания).
от остального считаем хэш любым алгоритмом (CRC32, MD5, etc)
ваши строки сматчатся в одно значение.
вы этого хотели?
если нет — потрудитесь объяснить что значит «схожие строки» — на мой взгляд это совсем разные строки — дом 12 по улице Васюковской — это 8-подъездная многоэтажка, а дом 121 — это ветхая хибара.
Ответ написан
@dime
Уточните вопрос
Вам нужен конкретный алгоритм, возвращающий одинаковый хэш для двух этих конкретных строк (и не важно что для всех остальных)?
Или вам нужен генератор алгоритмов хэш-функций, которому на вход дают две строки, а генератор генерирует такой алгоритм хэширования, чтобы для этих заданных строк получалась коллизия (и опять не важно, что там получится для всех остальных)?
Ответ написан
TheHorse
@TheHorse
Можно пробовать хеш функцию, которая является суммой всех символов div С, где С — константа, большая (например,100). Тогда с высокой долей вероятности, строки, которые отличаются на 1-2 символа будут попадать в один хеш.

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

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

«479465 12»
«479465 12»

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

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

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

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

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

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

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

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

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

А так алгоритмов реальных не знаю, но если писать очередной велосипед, то TheHorse предложил то же, что и мне в голову. Я бы только дополнил немного, что полученное число я бы использовал не как хэш, а для инициализации генератора случайных чисел и из него бы уже вытягивал хэш нужной длины.
Ответ написан
xsen
@xsen
Программист
Вомзожно можно оптимизировать алгоритм шинглов, только вместо слов использовать n-ое кол-во символов.
Ответ написан
Nomad1
@Nomad1
Кстати, с адресом очень интересный пример. Если бы задача ограничивалась адресом, то решалась бы так:
1. неким алгоритмом получаем название страны (например, страна часто пишется в адресе последней, есть список стран) и берем его идентификатор как первую часть хеш-кода
2. другим алгоритмом получаем название штата/области (в US двубуквенные сокращения, в пост-СССР со словом «обл.», есть список штатов всех стран), если найден — берем как вторую часть кода
3. третьим алгоритмом получаем город (обычно идет первым, с большой буквы, без префиксов, есть список городов, есть список ZIP кодов/индексов), его идентификатор становится третьей частью хеш-кода. Если есть связка город-штат и неопределен результат в п.2, заполняем его

Получаем трехкомпонентный хеш-код, который с большой долей вероятности будет одинаков для всех адресов одного города (как и в изначальном примере). Написания улиц могут и будут различаться, потому эту часть мы специально отбрасываем и расчитываем на коллизию размером с все улицы одного города.
Такой метод подходит для большей части городов мира, особенно для суб-урбанизированных стран вроде США и совершенно не подходит для Москвы и других мегаполисов.
Ответ написан
@Dilon
В свое время довелось использовать ssdeep.sourceforge.net/ для похожей задачи.
Ответ написан
EndUser
@EndUser
Мдя… А зачем вам такая функция?
Функция «хэш» характерна минимальными коллизиями.
Вам, по-видимому, в задаче нужна другая функция. Например «индекс».
Ответ написан
Donskoy
@Donskoy
Если нужно сравнивать имена собственные, то вместо Левенштейна лучше подходит Jaro-Winkler distance.
Эта метрика была разработана для поиска имен с похожим написанием (или с ошибками в написании) при переписи населения в США.
Ответ написан
Ryadovoy
@Ryadovoy
Смотри метод Хеширование по сигнатуре + расстояние Левенштейна
habrahabr.ru/post/114997/
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы