как подсказка слов в Microsoft Word угадывает альтернативы?

посмотрите на этот пример в ms word; Я намеренно написал слово "complemet" с ошибкой, чтобы показать вам, что я имею в виду;

введите здесь описание изображения

Интересно, как MS Word выбирает слова, наиболее похожие на то, что я набрал (я имею в виду алгоритм)

это не проверка орфографии, а поиск наиболее похожих слов(как результаты на картинке)

Я хочу реализовать алгоритм, чтобы я мог найти слова, наиболее похожие на то, что уже набрал пользователь;


ms-word search-suggestion
person wiki    schedule 20.07.2013    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

(Ради эффективности вы, вероятно, не хотите сравнивать какое-либо слово со всем списком слов. Возможно, вы захотите выполнить быструю отбраковку с помощью одного или нескольких других методов, чтобы отсеять возможные альтернативы.)

(Редактировать)

Это было весело! :) Просто чтобы посмотреть, как это работает, я реализовал это на C, используя список words OSX по умолчанию и версию C алгоритма на Викиучебники. Вот топ-10 хитов для вашего «комплимента»:

'complment' -> LD=compliment(1)
   LD=complement(1)
   LD=component(2)
   LD=couplement(2)
   LD=comment(2)
   LD=compellent(2)
   LD=competent(2)
   LD=compilement(2)
   LD=complacent(2)
   LD=complaint(2)

Процедура сравнения хранила небольшой массив «лучших на данный момент» совпадений, и когда массив заполнялся, самые высокие значения отбрасывались. Вычисление полного расстояния для каждого слова в списке (235 886 слов) заняло 0,370 с.

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

Несколько случайных слов, которые я пробовал (показаны не все возможные решения):

'unforutntately' -> LD=unfortunately(3) LD=infortunately(4) LD=fortunately(5)
'abcacadabra' -> LD=abracadabra(1) LD=barracuda(7)
'athtahn' -> LD=Ethan(3) LD=thawn(3) LD=Pathan(3) LD=attaghan(3)
'jongware' ->

... последний не дал совпадений никаких вообще. Только после удаления моей процедуры One-Character-Off я получил

'jongware' -> LD=nonglare(2)
   LD=congiary(3)
   LD=henware(3)
   LD=hogward(3)
   LD=honeyware(3)

Ну что ж.

(Дальнейшее редактирование) Поскольку вы написали

дело не в проверке орфографии, а в поиске наиболее похожих слов

Я запустил его снова с правильно написанным словом «комплимент». Это результат для этого:

'compliment' -> LD=compliment(0)
  LD=complement(1)
  LD=complimenter(2)
  LD=compliant(2)
  LD=complicant(2)
  LD=complacent(2)
  LD=couplement(2)

Как видите, первое значение — «0» — точное совпадение, а остальные слова — «похожие».

person Jongware    schedule 20.07.2013