Мне нужно реализовать проверку орфографии в java, позвольте мне привести пример для строки, скажем, "sch aproblm iseasili решен" мой вывод "такая проблема легко решается". Максимальная длина строки для исправления 64. Как вы можете видеть, в моей строке могут быть вставлены пробелы в неправильных местах или нет вообще, и даже слова с ошибками. Мне нужна небольшая помощь в поиске эффективного алгоритма поиска исправленной строки. В настоящее время я пытаюсь удалить все пробелы в моей строке и вставляю пробелы в каждую возможную позицию, поэтому, скажем, для слова (это относится и к предложению) «горячий», я генерирую следующие возможные строки, чтобы послесловия корректировались слово за словом используя расстояние Левенштейна: горячее; горячей; горячей; горячей. Как вы видите, я сгенерировал 2 ^ (string.length () -1) возможных строк. Таким образом, для строки длиной 64 он сгенерирует 2 ^ 63 возможных строк, что чертовски высоко, и после слов мне нужно обработать их одну за другой и выбрать лучший из другого набора параметров, таких как: - полное редактирование расстояние (должно быть наименьшее)
-Если у меня больше строк с одинаковым расстоянием редактирования, я должен выбрать ту, у которой меньше слов
-Если у меня есть больше строк с тем же количеством слов, мне нужно выбрать ту, у которой общая максимальная частота слов (у меня есть словарь наиболее часто встречающихся 8000 слов вместе с их частотой)
и, наконец, если есть еще строки с одинаковой общей частотой, мне нужно взять наименьшую лексикографическую.
Таким образом, в основном я генерирую все возможные строки (вставляя пробелы во всех возможных позициях в исходную строку), а затем один за другим вычисляю их общее расстояние редактирования, количество слов и т. Д. а затем выберите лучший и выведите исправленную строку. Я хочу знать, есть ли более простой (с точки зрения эффективности) способ сделать это, например, не нужно генерировать все возможные комбинации строк и т. Д.
РЕДАКТИРОВАТЬ: Итак, я подумал, что я должен принять другой подход к этому. Вот то, что я имею в виду: я беру первую букву из моей строки и извлекаю из словаря все слова, которые начинаются с этой буквы. что я обрабатываю их все и извлекаю из своей строки все возможные первые слова. Я останусь в моем предыдущем примере, для слова «горячий», генерируя все возможные комбинации, я получил 4 результата, но с моим новым алгоритмом я получаю только 2 «горячий» и «хо», так что это уже улучшение. нужна небольшая помощь в создании рекурсивного алгоритма или алгоритма PD для этого. Мне нужен способ сохранить все возможные строки для первого слова, затем для всех этих всех возможных строк для второго слова и так далее, и, наконец, объединить все возможности и добавить их в массив или что-то еще. Все еще будет много комбинаций для больших строк, но не так много, как для ВСЕХ из них. Может ли кто-нибудь помочь мне с псевдокодом или чем-то еще, так как это не моя сильная сторона?
EDIT2: вот код, в котором я генерирую все возможные первые слова из моей строки http://pastebin.com/d5AtZcth. Мне нужно как-то реализовать это, чтобы сделать то же самое для остальных и объединить для каждого первого слова с каждым вторым словом и так далее, и хранить все эти данные в виде массива или чего-то подобного.