Решение проверки орфографии в java

Question

Мне нужно реализовать проверку орфографии в java, позвольте мне привести пример строки, чтобы сказать, что «sch aproblm iseasili resolved» мой вывод «такая проблема легко решена». Максимальная длина строки, которую нужно исправить, равна 64. Как вы можете видеть, моя строка может содержать пробелы, вставленные в неправильные места или вообще не написанные, и даже слова с ошибками. Мне нужна небольшая помощь в поиске эффективного алгоритма поиска исправленной строки. В настоящее время я пытаюсь удалить все пробелы в моей строке и вставлять пробелы в каждую возможную позицию, поэтому давайте скажем для слова (оно также относится к предложению) «hot» Я генерирую следующие возможные строки для повторных слов, с использованием levenshtein расстояние: горячее; горячий; горячий; горячий. Как вы можете видеть, я создал 2^(string.length() -1) возможные строки. Таким образом, для строки с длиной 64 она будет генерировать 2^63 возможных строк, которые являются чертовски высокими, а послесловия мне нужно обрабатывать их по одному и выбирать лучший из них с помощью другого набора параметров, таких как: - полное редактирование расстояние (должно занимать наименьшее) -если у меня больше строк с одинаковым расстоянием редактирования, я должен выбрать один с меньшим количеством слов -if у меня больше строк с таким же количеством слов, которые мне нужно выбрать с общей максимальной частотой слова имеют (у меня есть словарь наиболее часто встречающихся 8000 слов вместе с их частотой) - и, наконец, если есть больше строк с одинаковой общей частотой, я должен взять наименьшую лексикографическую.

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

EDIT: Итак, я подумал, что я должен сделать другой подход на этом . Вот что я имею в виду: я беру первое письмо из своей строки и извлекаю из словаря все слова, которые начинаются с этого письма. После этого я обрабатываю их все и извлекаю из моей строки все возможные первые слова. Я останусь в своем предыдущем примере, для слова «горячий», генерируя все возможные комбинации, я получил 4 результата, но с моим новым алгоритмом я получаю только 2 «горячих» и «хо», поэтому он уже улучшается. Хотя я нужно немного помочь в создании рекурсивного или PD-алгоритма для этого. Мне нужен способ хранить все возможные строки для первого слова, затем для всех этих возможных строк для второго слова и т. Д. И, наконец, для объединения всех возможностей и добавления их в массив или что-то в этом роде. По-прежнему будет много комбинаций для больших строк, но не так много, как необходимость выполнять ВСЕ из них. Может ли кто-нибудь помочь мне с псевдокодом или чем-то еще, поскольку это не мой сильный костюм.

EDIT2: вот код, в котором я генерирую все возможное первое слово из моей строки http://pastebin.com/d5AtZcth. Мне нужно каким-то образом реализовать это, чтобы сделать то же самое для остальных и объединиться для каждого первого слова с каждым вторым словом и так далее, и хранить все эти конкатенированные в массив или что-то еще.

Answer 1

Несколько советов для вас:

1. пытаются исправлять только мелкие части строки, а не все сразу.

2. 90% эррос (IIRC) имеют 1 отредактированное расстояние от источника.

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

4. Вы можете предположить, что большинство опечаток являются ошибками QWERTY (j => k, h => g) и сначала проверяйте их.

несколько больше идей можно найти в этом хорошей статье:

http://norvig.com/spell-correct.html