Алгоритм вычисления расстояния редактирования между двумя словами

Question

Я пытаюсь написать Python код, который принимает слово в качестве ввода (например, книгу) и выводит наиболее похожее слово со значением сходства.

Я испробовал различные готовые алгоритмы редактирования расстояния, такие как косинус, Левенштейн и другие, но они не могут определить степень различия. Например, (книга, бук) и (книга, bo0k). Я ищу алгоритм, который может дать разные оценки для этих двух примеров. Я думаю об использовании fastText или BPE, однако они используют косинусное расстояние.

Есть ли алгоритм, который может решить эту проблему?

Answer 1

Проблема в том, что и "bo0k", и "bouk" - это один символ, отличный от "book", и никакие другие метри c не позволят вам различить guish между ними.

Что вам нужно будет сделать, это изменить оценку: вместо того, чтобы считать другого персонажа как расстояние редактирования 1, вы можете дать ему более высокий балл, если это другой класс персонажей (ie вместо git письма). Таким образом, вы получите другой балл за ваши примеры.

Возможно, вам придется адаптировать и другие баллы, чтобы замена / вставка / удаление оставались неизменными.

Answer 2

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

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

Так, например, O окружен I90PLK, I окружен U89OK или, возможно, U89OKJ.

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

Так что все, что вам нужно сделать, это сгенерировать всех возможных соседей по опечатке и просто найти все словарные слова в мутантах, что должно быть эффективным запросом.

например, для bo0k

bo0k
vo0k
go0k
ho0k
no0k
_o0k

bi0k
b90k
b00k
bp0k
bl0k
bk0k

bo9k
bo0k
bo-k
bopk
book       - bingo!
boik

bo0j
bo0u
bo0i
bo0o
bo0l
bo0,
bo0m

Здесь вы можете видеть, что во всем наборе базовых c опечаток есть только одно словарное слово.

Так что это не не использовать алгоритмы подобия, но в случае опечаток клавиатуры, он может найти исправления. Вы даже можете зафиксировать «принятие» этих предложений пользователем и сформировать свой собственный корпус вероятностей коррекции. Я предполагаю, что многие опечатки довольно распространены и непротиворечивы.

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

Answer 3

Это очень интересный вопрос - возможно, со многими возможными ответами. Вы можете добавить биграмный (n-граммный) анализ, чтобы оценить, насколько вероятно, что буквы будут связаны друг с другом в типичных словах.

Предполагая, что ваша система не "знает" целевое слово, но кто-то печатает "bouk". Затем он анализирует все биграммы:

бо, оу, ук

или триграммы

бу, ук

Я бы догадался, что "бо", «ou», «bou» были бы хорошими, поскольку они обычны, но «uk» и «ouk» вряд ли были бы в Engli sh. Таким образом, это могло бы просто иметь оценку 3/5, но на самом деле каждая триграмма имела бы свою собственную оценку частоты (вероятность), поэтому общее число для предлагаемого слова могло бы быть очень точным.

Затем сравнив это с "bo0k «вы бы посмотрели на все биграммы:

бо, о0, 0к

или триграммы

бо0, о0к

Теперь вы можете видеть это только» бо "хорошо бы забил здесь. Все остальные не будут найдены в общем корпусе n-грамм. Таким образом, это слово будет иметь гораздо меньшую вероятность, чем «бук», например, 1/5 по сравнению с 3/5 для «бук».

Решение будет примерно три:

Вам потребуется корпус с установленными частотами n-граммы для языка. Например, этот случайный блог, который я нашел, обсуждает, что: https://blogs.sas.com/content/iml/2014/09/26/bigrams.html

Затем вам нужно будет обработать (разбить на токены и отсканировать) ваши входные слова в n-граммах, а затем посмотреть их частоты в корпус. Вы можете использовать что-то вроде SK Learn,

Затем вы можете суммировать части любым удобным для вас способом, чтобы установить sh общий балл за слово.

Обратите внимание, что вы можете найти большинство жетонов и обработку n-грамм для центров естественного языка вокруг отношений между словами , а не букв внутри слов. В этом легко заблудиться, так как часто тот факт, что библиотека сосредоточена на грамматиках слов, прямо не упоминается, потому что это наиболее распространенный вариант. Я заметил это раньше, но n-граммы также используются во всех других наборах данных (временные ряды, musi c, любая последовательность). В этом вопросе обсуждается, как можно преобразовать векторизатор SK Learn в буквенные граммы, но я сам не пробовал: N-грамм для письма в sklearn