Perm', Perm, Russian Federation
The paper is devoted to indistinct comparison of texts by means of q-grams and Bloom’s-filter on a material of official, art and scientific texts in Russian. The suggested method allows assess texts’ similarity approximately.
computer linguistics; indistinct comparison; N-grams; Bloom’sfilter; text similarity.
Проблема нечеткого сравнения текстов является одной из актуальных прикладных задач не только для современной лингвистики, но и прикладной биологии, теории информации, текстологии и др. Существует несколько распространенных методов нечеткого сравнения, среди которых можно упомянуть:
- суффиксные деревья;
- вычисление расстояния редактирования;
- суффиксные массивы;
- 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. Boytsov L.M. Klassifikatsiya i eksperimental’noe issledovanie sovremennykh algoritmov nechetkogo slovarnogo poiska [Classification and experimental study of the vocabulary of modern algorithms for fuzzy search], 2004. Available at: http://rcdl.ru/doc/2004/paper27.pdf/
2. Solov’ev V.D. Chastotnost’ kak ob’ekt korpusnykh issledovaniy [Frequency as the object of case studies]. Trudy mezhdunarodnoy konferentsii «Korpusnaya lingvistika — 2011» [Proc. Int. Konf. «Corpus linguistics – 2011»]. St. Petersburg, S. Peterburgskiy gos. un-t Publ., 2011, pp. 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, pp. 191–211.
