Улучшенный алгоритм Левенштейна

Question

Я недавно внедрил алгоритм Левенштейна в нашу базу данных поисковой системы, но мы столкнулись с проблемой.

По основному левенштейну

Левенштейн («123456», «12x456») совпадает со значением Левенштейна («123456», «12345x»)

Обычно это нормально, но для моей конкретной проблемы это неправильно. Когда кто-то использует наш сайт, это неправильно. Производители электронных компонентов часто производят аналогичные продукты, только с разницей в самом последнем письме. Если первая буква отличается, это обычно совершенно другая категория. Поэтому мне нужен алгоритм, который считает совпадения в начале слова более ценными, чем те, что в спине, или, другими словами, несоответствия, которые происходят в начале, должны применять большее наказание, чем в конце.

Если у кого-нибудь есть идеи, пожалуйста, дайте мне знать.

Answer 1

Используйте Расстояние Яро-Винклера ... Это именно то, что вы просите.

Answer 2

См. Алгоритм Смита-Уотермана , широко используемый в биоинформатике. Он может выполнить локальное выравнивание вашего запроса, но это будет медленнее, чем Левенштейн.

Answer 3

У нас была похожая проблема, и мы использовали метод Brew edit distance

Мы были в Perl, поэтому мы использовали библиотеку Text :: Brew . Мой коллега сделал хорошую презентацию об использовании нескольких различных алгоритмов , включая Brew.