НЕЧЕТКОЕ СРАВНЕНИЕ ТЕКСТОВ МОДИФИЦИРОВАННЫМ МЕТОДОМ N-ГРАММ
Аннотация и ключевые слова
Аннотация (русский):
Статья посвящена нечеткому сравнению текстов с помощью 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.

Войти или Создать
* Забыли пароль?