Анализ текста (лемматизация, редактирование расстояния)

Question

Мне нужно проанализировать текст на наличие в нем запрещенных слов.Предположим, в черном списке есть слово: «Запретить».Слово имеет много форм.В тексте слово может быть, например: «запрещающий», «запрещенный», «запрещенный».Чтобы привести слово в исходную форму, я использую процесс лемматизации.Ваши предложения?

А как насчет опечаток?
Например: "F0rb1d".Я думаю использовать damerau – Levenshtein или другое.Ваши предложения?

А что если текст написан следующим образом :
«Запрещенная информация. Частная корреспонденция компании».ИЛИ "F0rb1dden1nformation.Privatecorresp0ndenceoftccmpany."(да, без пробелов)

Как решить эту проблему?
Желательно быстрый алгоритм, потому что текст обрабатывается в реальном времени.
И, возможно, какие советы по улучшению производительности (как хранить и т. д.))

Answer 1

Насколько мне известно, есть два возможных решения.

Вы можете попробовать использовать динамическое программирование, LCS (самая длинная общая подпоследовательность). Он будет искать в оригинальном тексте искомое слово как образец, я думаю, что это O (mn):

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem http://www.ics.uci.edu/~eppstein/161/960229.html

Хотя проще было бы использовать алгоритм текстового поиска. Лучшее, что я знаю, это KMP , и это O (n). Для сравнения символов вы можете сгруппировать их в наборы, такие как {i I l (L) 1}, {o O 0} и так далее. Тем не менее, вы можете изменить это, чтобы не совпадать со всеми буквами (запрещать -> запрещать).

http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm

Так что теперь вы можете сравнить преимущества этих двух с вашим предложением.

Answer 2

Вы также можете использовать совпадения RegEx для проверки слов.http://www.c -sharpcorner.com / uploadfile / prasad_1 / regexppsd12062005021717am / regexppsd.aspx