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

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

А как насчет опечаток?
Например: «F0rb1d». Думаю использовать дамерау – Левенштейна или другое. Вы предложения?

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

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


c# nlp similarity lemmatization
person user348173    schedule 03.04.2011    source источник
comment
Не точные дубликаты, а похожие вопросы tions.   -  person khachik    schedule 03.04.2011

Ответы (2)


arrow_upward
3
arrow_downward

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

Вы можете попробовать использовать динамическое программирование, 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%E2%80%93Morris%E2%80%93Pratt_algorithm

Итак, теперь вы можете сравнить преимущества этих двух и вашего предложения.

person Aurimas Neverauskas    schedule 05.04.2011

arrow_upward
1
arrow_downward

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

person kojoma    schedule 05.04.2011