Аномалия в тексте

Question

Позвольте мне объяснить на примере. У нас есть следующий текст:

«Comme Il Faut был основан в 1927 году. Табачная компания наиболее известна своей репутацией производителя индивидуальных торговых марок для своих партнеров по всему миру».

Это обычный текст. Но следующий текст:

«CommeIlFaut был основан в 1927 году. Табачная компания является наиболее известной благодаря своей репутации по производству индивидуальных брендов для своих партнеров по всему миру»

Это текстовая аномалия: опечатки, слова без пробела, может быть, что-то еще.

Как искать такие аномалии?
Какие существуют алгоритмы для этого (статистические)?

Желательно, чтобы результат был в процентах: например, 80% от аномалий.

Спасибо.

Answer 1

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

Answer 2

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

Это, однако, предполагает, что у вас есть как правильная, так и разорванная строка. Если у вас есть только сломанная строка, это будет намного сложнее. В этом случае я бы посоветовал вам либо попробовать упомянутый выше подход trie, либо использовать некоторую внешнюю библиотеку, такую ​​как ispell, чтобы она могла обрабатывать эту логику. Вы можете взглянуть на код для ispell или его варианты, чтобы увидеть, насколько сложной может стать такая задача.

Answer 3

Несколько ссылок, которые могут быть полезны:

http://www.codeproject.com/KB/cs/spellcheckdemo.aspx
http://www.codeproject.com/KB/recipes/spellcheckparser.aspx