Быстрая фильтрация текста при помощи модифицированного фильтра Блума

Целью данной работы является решение задачи быстрого сравнения текстовых массивов. Предмет исследования - фильтры Блума и их адаптация для задач быстрой фильтрации текстовых данных. В работе проведен сравнительный анализ различных вариаций фильтров Блума на возможность их использования в данной области. На базе анализа предложены алгоритмы и структуры данных для быстрой фильтрации текстов на основе псевдоматричных фильтров Блума. Рассмотрены различные вариации хранения текста в фильтре. Для решения задачи локализации поиска предложено добавить дополнительный индекс, содержащий указатели фрагментов документов, загруженных в фильтр. Показаны преимущества предлагаемой модели на примере модельных документов с разной степенью искажения анализируемого текста. Областью применения данных методов является широкий круг задач текстового поиска, включающий задачи обнаружения плагиата или защиты от утечки конфиденциальной информации. Полученные экспериментальные результаты показали приемлемые значения ложноположительных и ложноотрицательных срабатываний фильтра, заметное преимущество размера псевдоматричных фильтров над размером матричного фильтра Блума. Также результаты эксперимента показали применимость предложенного подхода для быстрого обнаружения документов, содержащих 5% и более совпадающего текста.