Программа предложения слов

Question

Предложите мне программу или способ обработки системы исправления / предложения слов. - Допустим, входные данные задаются как «Suggset», они должны предлагать «Suggest».

Спасибо заранее. И я использую Python и AJAX. Пожалуйста, не предлагайте мне какие-либо jquery-модули, потому что мне нужна алгоритмическая часть.

Answer 1

Алгоритм, который решает вашу проблему, называется «редактировать расстояние». Учитывая список слов в некотором языке и опечатку / неполное слово, вам нужно составить список слов из данного словаря, ближайшего к нему. Например, расстояние между «предложить» и «suggset» равно 2 - вам нужно одно удаление и одну вставку. В качестве оптимизации вы можете назначить разные веса для каждой операции - например, вы можете сказать, что подстановка дешевле, чем удаление, а подстановка между двумя буквами, расположенными ближе на клавиатуре (например, «v» и «b»), дешевле, чем между теми, которые находятся далеко друг от друга (например, 'q' и 'l').

Впервые описание алгоритма правописания и исправления появилось в 1964 году. В 1974 году Роберт А. Вагнер и Майкл Дж. Фишер назвали эффективный алгоритм, основанный на динамическом программировании, в статье «Задача исправления строки в строку». В любой книге по алгоритмам есть более или менее подробное описание.

Для python есть библиотека, которая делает это: Дистанционная библиотека Левенштейна Также проверьте это предыдущее обсуждение переполнения стека

Answer 2

Чтобы сделать один из них, потребуется много работы. Существует действительно хорошая библиотека проверки орфографии, написанная на python, под названием PyEnchant , которая мне показалась довольно хорошей. Вот пример с их сайта:

>>> import enchant
>>> d = enchant.Dict("en_US")
>>> d.check("Hello")
True
>>> d.check("Helo")
False
>>> d.suggest("Helo")
['He lo', 'He-lo', 'Hello', 'Helot', 'Help', 'Halo', 'Hell', 'Held', 'Helm', 'Hero', "He'll"]
>>>