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

Введение. Исследования в области поиска схожести в текстах ведутся фактически с начала компьютерной эры [1]. К данному классу относятся работы, в которых текст анализируется на уровнях символов, семантики и стиля его написания. К первому сегменту можно отнести исследования, связанные с расшифровкой генома человека, а также, например, работы, направленные на поиск текстового плагиата [2; 3], ко второму – работы, ориентированные на обработку текста в соответствии с его смысловой нагрузкой [4]. Примером исследований третьего сегмента являются работы по стилеметрии, направленные на определение авторства текстов [5; 6].

Приложения поиска схожих текстов ставят своей задачей, как правило, не только дать некую численную оценку степени схожести, но и выделить схожие тексты, сделав сравнение более удобным для человека. Для численной оценки качества определения степени схожести используются оценки точности и чувствительности, определяемые по формулам (1) и (2), а для оценки качества выделения – гранулярность, рассчитываемая через количество случаев обнаружения одного сходного фрагмента в документе [7]. С точки зрения времени сравнения критическими являются оценки точности и чувствительности, так как они позволяют выбрать некоторый набор «подозрительных» документов из всего множества потенциально схожих документов. При этом в соответствии с классической теорией измерений точность и чувствительность распознавания совпадений текстов определяются по формулам (1) и (2):

количество правильно распознанных совпадений

Точно сть =------------------------------------------------;                        (1)

количество распознанных совпадений количество правильно распознанных совпадений

Чувствительность =--------------------------¹---------¹---------------------------------------.      (2)

количество правильно распознанных + количество пропущенных совпадений

Одним из наиболее распространенных методов поиска схожих текстов является класс, основанный на конвертации документа в некоторый набор шинглов, а затем быстром сравнении последних. Методы выбора шинглов варьируются от их построения по символам – до построения по словам и более укрупненным синтаксическим конструктам, таким как предложения естественного языка. После построения модели текста, основанной на шинглах, возникает задача быстрого сравнения шинглов проверяемого (фильтруемого) текста с содержимым фильтра.

Результатом быстрого сравнения должен быть некоторый набор документов для процеду- ры детального сравнения. На данном этапе необходимо оградить выполнение детального сравнения от перегрузки, т.е. поддерживать достаточную точность при низкой чувствительности к шуму (ложноположительным срабатываниям).

Механизм быстрой фильтрации может быть основан на применении фильтра Блума, позволяющем проводить быстрое определение членства элемента в множестве с некоторой вероятностью ложноположительного результата. Фильтр Блума (ФБ) – это вероятностная структура данных, предложенная Б. Блумом в 1970 г. [8], позволяющая компактно хранить множество элементов и проверять принадлежность элемента заданному множеству с линейной скоростью, не зависящей от числа элементов в множестве.

На этапе предварительного отбора потенциальных кандидатов для детального сравнения ФБ может быть использован для быстрого поиска схожих частей текста в большом объеме документов. Необходимо отметить, что для документов само понятие сходства может быть формализовано различными способами [9]. В данной статье под сходством мы будет понимать идентичность фрагментов текста либо совсем без модификаций, либо с минимальными изменениями.

В работе проанализированы проблемы, связанные с практическим применением классического ФБ, рассмотрены варианты построения шинглов для загрузки в ФБ, предложен подход, позволяющий увеличить плотность матричного ФБ за счет задания специального индекса, отслеживающего загрузку документа в фильтр. В дополнение к процедуре индексации рассмотрен алгоритм удаления элемента, сохраняющий локализацию последнего.

Фильтр Блума и его модификации. ФБ представляет собой вероятностную структуру данных, позволяющую компактно хранить множество элементов и проверять принадлежность заданного элемента к множеству [10]. Основная идея заключается в использовании независимых хеш-функций для представления объекта из множества S = { x₀, x₁, …, x _{( n – 1)}} в виде бинарного вектора фиксированного размера m . ФБ использует k независимых хеш-функций h₀, h₁, …, h_{k – 1} для случайного размещения элемента в бит-массиве с индексами { 0, …, m – 1}. Для вставки элемента x в фильтр соответствующие биты – { h_i ( x ) , 0 ≤ i ≤ k – 1} задаются равными 1. Для проверки принадлежности элемента x фильтру соответствующие значения { h_i ( x’ ) , 0 ≤ i ≤ k – 1} должны быть вычислены и сравнены со значениями в фильтре. Если все соответствующие биты принимают значение 1, то элемент x принадлежит множеству.

Вероятностный характер вычисления h_i может привести к ложноположительному результату [11], который определяется следующим образом [12]:

kn

I 1 I           - kn /m p = I 1--I » e .          (3)

к m )

Проблемы применения фильтра Блума. С. Жераванд и М. Ахмади сформулировали понятие матричного фильтра Блума (МФБ), предложив использовать набор (матрицу) фильтров, где каждый отдельный фильтр состоит из шинглов одного документа [13]. Текст, который планируется проверить, помещается в фильтр отдельной строкой и сравнивается с каждой строкой МФБ. Хотя множество независимых фильтров не похоже на классический ФБ, такое множество обладает одним важным свойством: количество операций для проверки членства элемента в множестве для МФБ линейно зависит от размера матрицы (фактически от количества документов). Таким образом, при использовании одинакового фиксированного размера всех строк матрицы сохраняется свойство высокой производительности фильтра.

Этот подход обладает недостатком в виде неэффективного потребления памяти каждой строкой в матрице из-за двух факторов:

• -    в одной строке сохраняется только один документ;

• -    размер документа не должен превышать m -заданную величину, которая определяет фиксированную длину индивидуального ФБ (строки матрицы). Последнее дает возможность производить вычисления фильтра сравниваемого документа только один раз, что значительно повышает скорость сравнения документов.

Первое ограничение может быть ослаблено путем добавления в матрицу дополнительного индекса. В следующей секции статьи представлены такой индекс и алгоритмы его использования.

Одним из важных этапов фильтрации текстовых документов является выбор сравниваемых фрагментов текста, т.е. построение некоего отпечатка текста. Желательными характеристиками отпечатка являются его уникальность, равномерность покрытия текста, объем занимаемой памяти и ресурсы, требуемые для построения самого отпечатка. Последнее менее важно, так как отпечаток строится один раз перед его загрузкой в механизм сравнения (фильтр).

Существуют различные алгоритмы построения отпечатка документа для дальнейшего поиска подстрок или другого документа в нем. Классическим примером является алгоритм Рабина-Карпа [14], но он скорее предназначен для поиска подстрок и имеет недостатки, в том числе связанные с неустойчивостью к небольшим изменениям текста. Алгоритмы типа Винновинг [15] обладают требуемыми характеристиками к равномерности покрытия текста и показали хорошие результаты в задачах обнаружения плагиата [16; 17].

Однако, как показали эксперименты, выполненные в рамках данной работы, построение равномерного отпечатка возможно также и на основе простых алгоритмов сортировки. Для каждой возможной грамматики заданной длины n из обрабатываемого текста рассчитывается хеш- функция. Для выполнения данного расчета может использоваться один из известных криптографических хешей, например, такой как MD5 [18].

Далее значения хешей помещаются во временную таблицу базы данных и упорядочиваются по значению хеша. Данный отпечаток будет сильно избыточным, так как будет содержать количество хешей, близкое к количеству символов в документе. Данная избыточность может быть уменьшена выбором некоторого количества значений хешей.

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

Эксперимент, проведенный на одной тысяче документов из интернет-библиотеки LIB.RU, показал приемлемые результаты: при плотности выборки 5% на 873 документах из 1000 получен равномерный отпечаток (коэффициент уверенности равен 0,05). Выполнение данного алгоритма требует всего одного оператора SELECT/ORDER в любой реляционной базе данных. Таким образом мы показали, что построение отпечатка документа может быть выполнено различными способами.

Дальнейшая дискуссия в данной статье не затрагивает методы получения отпечатка (грамматик), так как они не влияют на основные характеристики ФБ. Однако стоит заметить, что именно способ построения отпечатка позволяет заложить в систему критерии схожести текста.

Псевдоматричный фильтр Блума. Как было показано ранее, МФБ предполагает размещение одного документа из базы сравнения в одной строке матрицы. С учетом того, что документы будут иметь разную длину, подобный подход неизбежно ведет к неплотному заполнению фильтра короткими документами. Предлагаемая модификация ФБ-псевдоматричный фильтр Блума (ПМФБ) также состоит из неограниченного количества ФБ одинакового размера.

Главное отличие от решения, предложенного в работе [13], заключается в использовании одного ФБ для хранения фрагментов текста, которые принадлежат одному или более документам. Из равенства (3) мы можем найти фиксированный размер m , который позволит установить p -приемлемый уровень ложноположительных срабатываний ФБ с максимальным количеством элементов n :

m >

n ■ t n ( p )

( t n (2)) ^{2 .}

Приемлемый уровень ложноположительных срабатываний фильтра достигается при субоптимальном распределении памяти, что требует меньшей, чем максимальная (< n ), заполняемости каждой строки фильтра. Для обеспечения такого распределения памяти в случае ПМФБ необходимо поддерживать два дополнительных индекса. Первый должен отслеживать остаток свободного места в каждой строке фильтра. Второй – обеспечивать хранение индексов документов, размещенных в каждой строке ПМФБ. В последней части статьи показано, что в реальных приложениях не будет такого равномерного распределения, и многие документы могут быть сохранены в одной строке. Если ФБ’ скомпилированы из документов T’ и имеют определенное сходство с ФБ_i , мы можем сказать, что текст T’ , возможно, схож с одним из документов множества { T_i }, размещенного в ФБ_i . В дальнейшем необходимо выполнить детальное сравнение для подтверждения схожести документов. Это может быть сделано с помощью любого подходящего метода, например, с использованием расстояния Левенштейна. Обсуждение процедуры детального сравнения документов выходит за рамки данной статьи.

Подробно проблемы применения ПМФБ для решения задач быстрого сравнения текстов рассмотрены в работе [19]. Одной из возможных проблем, возникающих при использовании матричных ФБ, является проблема ложноположительных результатов при сравнении бит-строк по методу, предложенному в работе [13]. Определение порога ложноположительных срабатываний позволит снизить нагрузку на модуль детальной проверки. Теоретическое и практическое исследование пороговых значений ложноположительных срабатываний является одним из важных направлений данного проекта.

Эксперименты. Два эксперимента были проведены, чтобы проверить эффективность предложенного подхода для построения ПМФБ. Первый эксперимент был посвящен оценке степени сжатия документов в ПМФБ, второй – изучению применимости ПМФБ для реальных данных [19; 20].

Целью первого эксперимента было показать, что на реальных данных размер ПМФБ имеет явное преимущество над размером МФБ. Для этого были использованы тестовые данные с соревнований по обнаружению плагиата PAN 2009 [21]. Блок данных содержал 14428 документов, содержащих заимствованные куски текста. Среднее количество слов в документе было около 38000. Более 95% документов содержали количество слов, меньше чем 123000. Удалось показать, что, с одной стороны, с увеличением длины строки матрицы n улучшается сжатие, но это, в свою очередь, увеличивает нагрузку на компоненты системы, которые будут выполнять детальное сравнение.

Целью второго эксперимента была проверка применимости ПМФБ для обнаружения сходства текста. Для сравнения были использованы два множества. Первое множество состояло из 500 документов, в текст которых были произведены вставки текста из 50 различных источников. Каждая вставка текста была взята только из одного из 50 источников и размещена внутри документа случайным образом. Все документы содержали около 4000 слов.

В связи с тем, что в данном блоке тестовых документов все они имели одинаковое количество слов, сжатие данных с использованием ПМФБ отсутствовало, и каждый из документов был помещен в отдельную строку матрицы. Каждый из 50 исходных документов сравнивался со всеми 500 документами тестового блока. Уровень сходства оценивался количеством единиц в одинаковых позициях одной строки [22].

Как указано выше, блок тестовых данных для данного эксперимента был взят с соревнований PAN’09 и содержал 14428 документов [23]. Количество операций сравнения для всех документов тестового блока будет около (14 * 103 * 14 * 103) / 2 ~ 108. В эксперименте были использованы два подхода для заполнения ПМФБ.

При первом подходе документы целиком размещались в строках, и в строке могло быть несколько документов.

При втором подходе – документы, по длине не поместившиеся в одну строку, размещались в нескольких строках матрицы. В таблице показано, что увеличение плотности документов в матрице привело к уменьшению ложноположительных срабатываний, но количество ложноотрицательных срабатываний увеличилось вдвое.

При втором подходе строки фильтра были заполнены только на 50% от своей емкости, что в результате снизило показатель ложноположительных срабатываний. И в том, и другом подходе имеется некоторое количество ложноотрицательных срабатываний, их анализ показал, что все они были связаны с документами, которые содержали менее 1% текста, заимствованного из исходных документов.

В 26 документах из 117, по которым были ложноотрицательные срабатывания, вставленный текст был модифицирован. С учетом того, что сравнение производилось на уровне слов, такие результаты можно считать ожидаемыми. Результаты с ложноположительными срабатываниями в обоих подходах разнятся. При уменьшении плотности размещения текста в строках матрицы на 50% наблюдается значительное уменьшение количества ложноположительных срабатываний. Поэтому данный вопрос требует проведения дополнительных исследований и будет решаться на протяжении данного проекта.

Результаты двух подходов размещения текста документа в ПМФБ

Результат	Размещение текста в одной строке	Размещение текста в нескольких строках
Ложноположительные срабатывания (см. формулу (1))	301977 (~1%)	9322 (~0,01%)
Ложноотрицательные срабатывания (см. формулу (2))	51 (~5%)	117 (~11%)

Проведенные эксперименты показали, что ПМФБ может быть использован в системах быстрого сравнения текстов для фильтрации большого объема документов, но при этом возможны пропуски модифицированного текста.

Одним из возможных направлений улучшения качества работы предложенной структуры данных является использование методов распознавания стиля документа (стилеметрии) [24] для снижения объема шинглов, загружаемых в ФБ. В этом случае стилевые характеристики позволят определить неоднородности текста и выбрать ограниченное число шинглов в ПМФБ.

Дополнительная компрессия, выполненная подобным образом, должна снизить объем па- мяти, требуемый для ПМФБ, и, как следствие, увеличить скорость сравнения. Для определения того, насколько этот подход повлияет на качество определения схожих фрагментов, требуется провести дополнительные эксперименты.

Наряду с совершенствованием алгоритмов, проблема быстрого сравнения текстов на больших массивах данных может решаться по двум направлениям: вертикальным масштабированием, т.е. наращиванием мощности одной системы, либо путем горизонтального масштабирования, т.е. распределением нагрузки на кластере вычислительных машин. Первый подход позволяет избежать смены программного обеспечения при увеличении количества документов в базе срав- нения, но имеет ограничение, связанное с невозможностью существенного наращивания ОЗУ без периодической смены программно-аппаратной платформы. Второй подход требует специальных алгоритмов поиска на кластерах, но позволит наращивать мощность системы путем увеличения числа вычислительных машин в кластере. В следующей публикации будут рассмотрены оба варианта построения поисковых систем обнаружения плагиата: вариант размещения массива документов в ОЗУ и предварительная модель данных, позволяющая разделить поисковый индекс по кластерам. Первая модель предусматривает использование псевдоматричных фильтров Блума (ФБ). Вторая модель основывается на NoSQL базах данных.

Заключение. Для решения проблемы быстрого сравнения документов предлагается использовать основанную на фильтре Блума структуру данных. Предложенные структура данных и алгоритмы обработки способствуют эффективному использованию памяти при сравнении документов. Дополнительный индекс позволяет находить потенциально похожие документы, даже если они были распределены по разным строкам фильтра или в одной строке с другими документами. Также индекс дает возможность эффективно проводить операции удаления документов из фильтра.

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

Первый эксперимент показал заметное преимущество размера ПМФБ над размером матричного фильтра Блума. Результаты второго эксперимента показали применимость ПМФБ для быстрой фильтрации текстов, содержащих 5% и более заимствованного текста.

Для решения задач масштабирования системы сравнения текстов намечен путь развития подхода, связанный с использованием нереляционных баз данных.