Как сделать текстовые исправления с массивом суффиксов?

Question

Мы использовали массив суффиксов для реализации поиска по ключевым словам, например рассмотрим фразу:

белая плитка для ванной

вставляем суффиксы:

1) белая плитка для ванной

2) плитка для ванной

3) плитка

и теперь можно найти фразу «белая плитка для ванной комнаты», если пользователь вводит слова «белый», «ванная комната» или «плитка».

Однако, теперь есть проблема, человек может напечатать "tyle", и ничего не будет найдено.

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

Я подумывал применить дистанцию ​​Левенштейна, но моя попытка не удалась. Идея заключалась в том, что мы могли бы найти группу слов, которые начинаются с «t» и вычислить расстояние Левенштейна для каждого из них, а затем вернуть результаты, где расстояние Левенштейна было минимальным.

Это не удалось, потому что пользователь может набрать «iile» вместо «tile», и теперь без слов, мой алгоритм применяет расстояние Левенштейна к словам в группе «i».

Какой хороший способ решить эту проблему?

Answer 1

Найдена эта интересная статья о структуре данных под названием BK-дерево и связанных алгоритмах. Итак, я рассматриваю возможность использования BK-дерева.

Также эта статья говорит о еще более мощных методах.

Answer 2

Левенштейново расстояние лучше для слов, дополнительно вы можете использовать Cosine_shoityity мера сходства между двумя ненулевыми векторами внутреннего пространства произведений, которая измеряет косинус угла между ними

и для предложения или абзаца схожести вы можете использовать TF-IDF measure

Answer 3

Вы можете использовать Алгоритм редактирования расстояния Алгоритм поиска списка слов, которые имеют минимальное расстояние редактирования с искомым словом.

Например, со словом tyle и ile расстояние редактирования искомого слова tile будет равно 1. Для слова iile расстояние редактирования между tile и iile также будет равно 1.

Обновить

Если обойти все слова в массиве суффиксов и вычислить расстояние редактирования медленно (то есть расстояние редактирования составляет O(^2) по временной сложности), я бы предложил построить дерево префиксов (trie) свсе суффиксы предложения.И затем во время поиска, например, для слова tyle, попробуйте пройти по дереву префиксов следующим образом:

• Если в дереве префиксов есть узел для текущего символа, просмотрите узел
• Если для текущего символа нет узла, рекурсивно обойдите все узлы и пропустите этот символ.
• Во время поиска рассчитайте количество пропущенных символов.Чем меньше символов вы пропустите, тем лучше будет слово.