Пермь, Пермский край, Россия
Статья посвящена нечеткому сравнению текстов с помощью N-грамм и фильтра Блума на материале официально-деловых, художественных и научных текстов на русском языке. Предлагаемый метод позволяет приблизительно оценить схожесть текстов.
компьютерная лингвистика, нечеткое сравнение, N-граммы, фильтр Блума, схожесть текстов.
Проблема нечеткого сравнения текстов является одной из актуальных прикладных задач не только для современной лингвистики, но и прикладной биологии, теории информации, текстологии и др. Существует несколько распространенных методов нечеткого сравнения, среди которых можно упомянуть:
- суффиксные деревья;
- вычисление расстояния редактирования;
- суффиксные массивы;
- N граммы [3].
В нашей работе мы рассматриваем модифицированный метод N-грамм, сочетая сам метод с фильтром Блума. В широком смысле N-граммы (также называемые q-grams в англоязычной литературе) — это последовательность из N объектов одинаковой природы. Мы рассматриваем последовательности символов в печатном тексте. Так, для слова фрейлина можно выделить следующие 5-граммы (N = 5): фрейл, рейли, ейлин, йлина и 6-граммы: фрейли, рейлин, ейлина. Аналогично выделяются 2-, 3-, 4-, 7- и 8-граммы. Изменения, касающиеся самого метода, были произведены с целью минимизации объема дополнительных данных и максимизации скорости сравнения. Объем дополнительных данных может достигать значительных величин, в зависимости от N. Так, для произведения «Анна Каренина» Л.Н. Толстого количество 6 грамм превышает 70 тыс., занимая более полумегабайта памяти, что достаточно сильно замедляет автоматическую обработку текста.
N-граммы уже достаточно широко используются в обработке естественного языка, в том числе для нечеткого поиска и сравнения (см., например, [1, 2, 5]).
Фильтр Блума используется в прикладной лингвистике, например, в вероятностной модели перевода [4, с. 468–476]. Фильтр Блума работает следующим образом: для множества объектов A мощностью M задается функция (или несколько разных функций) отображения на множество натуральных чисел 1 … m, такое, что m < M, при этом распределение отображения должно быть равномерным. Для каждого объекта, который нужно запомнить, вычисляется функция отображения, и в таблице B размером m делается отметка в соответствующей ячейке. Так как m < M, то неизбежно появление коллизий, т.е. разные объекты множества A будут обозначатся одним и тем же способом в таблице B. Этот эффект снижает точность метода, однако количество коллизий предсказуемо и регулируемо за счет изменения размера таблицы B.
1. Бойцов Л.М. Классификация и экспериментальное исследование современных алгоритмов нечеткого словарного поиска // Труды RCDL 2004. URL: http://rcdl.ru/doc/2004/paper27.pdf/
2. Соловьев В.Д. Частотность как объект корпусных исследований // Труды международной конференции «Корпусная лингвистика — 2011». СПб.: С. Петербургский гос. ун-т, 2011. С. 328–332.
3. Navarro G., Baeza-Yates R., Sutinen E., Tarhio J. Indexing Methods for Approximate String Matching // IEEE Data Engineering Bulletin. 2001. № 24(4). P. 19–27. URL: http://www.dcc.uchile.cl/~gnavarro/ps/deb01.pdf/
4. Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning. Prague, 2007. June.
5. Ukkonen E. Approximate string-matching with q-grams and maximal matches // Theoretical Computer Science. 1992. Р. 191–211.
