Алгоритм сравнения слов (не по алфавиту)

Question

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

Пользователь вводит слово, которое должно быть одним из нескольких фиксированных вариантов (я храню варианты в списке).Я знаю, что введенные данные должны быть в члене списка, но, поскольку это ввод пользователя, он/она, возможно, допустили ошибку.Я ищу алгоритм, который скажет мне, какое наиболее вероятное слово имел в виду пользователь.У меня нет никакого контекста, и я не могу заставить пользователя выбирать из списка (т. е.он должен иметь возможность вводить слово свободно и вручную).

Например, предположим, что список содержит слова «вода», «четверть», «пиво», «свекла», «ад», «привет» и «трубкозуб».

Решение должно учитывать различные типы «нормальных» ошибок:

• Опечатки скорости (например,удвоение символов, удаление символов и т. д.)
• Опечатки соседних символов на клавиатуре (например,«qater» — «вода»)
• Неродные английские опечатки (например.«quater» от «четверть»)
• И так далее...

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

Я пишу код на Python, но считаю, что этот вопрос не зависит от языка.

Есть какие-нибудь рекомендации/мысли?

Answer 1

Вы хотите прочитать, как Google это делает: http://norvig.com/spell-correct.html

Редактировать:Некоторые люди упоминали алгоритмы, которые определяют метрику между заданным пользователем словом и словом-кандидатом (левенштейн, soundex).Однако это не полное решение проблемы, поскольку для эффективного выполнения неевклидова поиска ближайшего соседа также потребуется структура данных.Это можно сделать, например.с Деревом Обложек: http://hunch.net/~jl/projects/cover_tree/cover_tree.html

Answer 2

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

Answer 3

Рассматривали ли вы алгоритмы сравнения по фонетическим звукам, например Саундекс?Не должно быть слишком сложно создать звуковое представление вашего списка слов, сохранить его, а затем получить звуковое выражение пользовательского ввода и найти там ближайшее совпадение.

Answer 4

Найдите алгоритм Bitap.Он хорошо подходит для того, что вы хотите сделать, и даже содержит пример исходного кода в Википедии.

Answer 5

Если ваш набор данных действительно мал, достаточно просто сравнить расстояние Левенштейна для всех элементов независимо.Однако, если он больше, вам придется использовать БК-Дерево или аналогичная система индексации.В статье, на которую я ссылаюсь, описывается, как найти совпадения на заданном расстоянии Левенштейна, но ее довольно легко адаптировать для поиска ближайших соседей (и оставлено читателю в качестве упражнения;).

Answer 6

Хотя это может не решить всю проблему, вы можете рассмотреть возможность использования алгоритма soundex как части решения.Быстрый поиск в Google по словам «soundex» и «python» показал некоторые реализации алгоритма на Python.

Answer 7

Попробуйте поискать «расстояние Левенштейна» или «изменить расстояние».Он подсчитывает количество операций редактирования (удаление, вставка, изменение буквы), необходимых для преобразования одного слова в другое.Это общий алгоритм, но в зависимости от проблемы вам может понадобиться что-то особенное с разным весом для разных типов опечаток.