Методы нечеткого поиска текста на веб-странице

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

Метод n-грамм, модифицированный для поиска в «мешке слов». Обычно используется n=3, увеличение значения ведёт к росту количества ложноотрицательных ошибок, но увеличивает скорость поиска. Достоинства: приемлемая скорость, хорошие результаты на естественных текстах, высокое качество работы при множественных естественных ошибках в тексте (слияние-разделение слов, перестановка соседних символов, замена символов), допускается потоковое применение. Для увеличения быстродействия до максимального теоретического предела алгоритм может быть модифицирован в конечный автомат. Недостатки: увеличение количества ложноположительных ошибок при поиске коротких слов и ложноотрицательных – при малых n.

Метод шинглов и хеширование текста – предварительно фразы из словаря и выделенные по специальному признаку фрагменты текста трансформируются таким образом, чтобы некоторая хеш-функция от похожих фрагментов возвращала одинаковые (численные) значения [1]. Поиск осуществляется в предварительно проиндексированном тексте. Обычно трансформацию подбирают так, чтобы оставить только значимые лемматизированные и стеммизированные слова текста, часто без учёта их порядка. Достоинства: это один из немногих способов поиска, когда искомый текст и веб-страница могут быть, теоретически, произвольно большого размера. Недостатки: требуется предварительная индексация всех искомых фрагментов и текста, в котором ищут, часто для уменьшения размера индекса используют вычислительно сложные алгоритмы трансформации.

Предварительно обученная нейронная сеть специальной структуры для потокового нечеткого поиска в тексте [2]. Достоинства: за счёт особенностей работы нейросети возможен поиск нежелательного контента в трудноформализуемых случаях, в формах, в которых он не был представлен на момент обучения нейросети, по контексту, в значительно искажённых текстах и текстах с большим количеством ошибок. Скорость работы сравнительно высока по сравнению с комбинацией любых других способов, дающих аналогичную функциональность. Недостатки: необходимо предварительное длительное обучение нейронной сети.

В качестве меры сходства двух текстов, обычно используется какая-либо метрика типа редакционного расстояния или его аналогов. Перспективна оценка сходства посредством расстояния, вычисленного с помощью word2vec [3] (или аналогичного метода) – алгоритм после предварительной обработки корпуса текстов может быть использован для вычисления меры отношения этих слов в обрабатываемых текстах. Алгоритм точнее работает, если тематика проверяемого текста соответствует тематике корпуса текстов. Достоинства: сравнительно высокая скорость применения, высочайшее качество контекстно-зависимой меры схожести слов для естественных текстов, не требует предварительной обработки текстов (но может быть применён для неё), возможно потоковое применение. Недостатки: требуется предварительное ресурсоёмкое обучение на корпусе текстов, значительно снижается качество работы на несоответствующих обучающему корпусу текстах, что преодолевается увеличением разнообразия текстов в корпусе и увеличением размера корпуса.

Обычно алгоритмы нечеткого поиска применяются комбинированно. Однако, использование в качестве метрики word2vec с корректным корпусом делает бессмысленным использование других алгоритмов предобработки и может быть напрямую использовано в алгоритме «мешка слов» при линейном поиске или любой ускоряющей поиск модификации. Рассмотренные методы нечёткого поиска могут применяться (или применяются) в системах обнаружения нежелательного контента, при детектировании спама, в системах антифрода, персонализации поисковой выдачи, системах анализа и доставки персонализированного контента.

Благодарности: работа выполнена при финансовой поддержке РФФИ грант № 15-07-08378.