xmoonlight
@xmoonlight
https://sitecoder.blogspot.com

Хеширование слова с допуском ошибок при вводе и/или написании. Как сделать?

Всем, привет.

Например, стоит задача захешировать слово: "простор"
так, чтобы при любых 2-х ошибках в написании слова (неверные 1-2 буквы и/или пропущены 1-2 буквы) так, чтобы хеш - не изменялся и оставался постоянным.

У кого есть соображения по тому, как это сделать? => hash: кгтсбржнпмдл

Заранее, Благодарю всех за помощь.
  • Вопрос задан
  • 820 просмотров
Пригласить эксперта
Ответы на вопрос 3
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Вот пример такого хеша:

int hash(string s) {
  return 42;
}


Можно вместо 42 возвращать другое число, но обязательно, всегда одно и то же.
Это все потому, что множества слов с ошибками перекрываются. Например, строки "aaaa" и "aabb" должны давать одинаковый хеш. Но точно так же сроки "bbbb" и "aabb" должны давать одинаковый хеш. В итоге получается, что все возможные строки должны давать одинаковый хеш.

В чем состоит изначальная задача? Зачем вам такой хеш понадобился? Наверняка что-то типа поиска строк, совпавших с 1-2 ошибками. В этом случае следует перебором сгенерировать из заданной строки все возможные с 1-2 ошибками, эти строки уже сохранить как-то (например, используя стандартный хеш в хеш-таблице).

Или можно сравнивать строки парами, считая сколько нужно ошибок, чтоб получить из одной строки другую. Это стандартное динамическое программирование. Гуглите дистанцию редактирования.
Ответ написан
angrySCV
@angrySCV
machine learning, programming, startuping
возможно графы лучше подойдут, тогда ты при наличии ошибки, можешь пробовать другие варианты одного из узлов (буквы).
Ответ написан
sgjurano
@sgjurano
Разработчик
То, что вы ищете, называется "нечёткий поиск".
Вот неплохая статья на эту тему:
https://m.habrahabr.ru/post/114997/
Ответ написан
Ваш ответ на вопрос

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

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