Упрощенный алгоритм шинглов

Описание алгоритма шинглов («чешуек») и его модификаций можно найти в литературе, в частности, в работах [3 — 5]. Алгоритм предполагает выделение в предварительно обработанном (канонизированном) тексте без предлогов и знаков препинания цепочек слов заданной длины (шинглов), расчет для каждого шингла контрольных сумм и затем подсчет числа совпадающих контрольных сумм в сравниваемых текстах. В упомянутой выше программе использован алгоритм шинглов в упрощенной постановке (рис.2).

Рис. 2 Схема упрощенного алгоритма шинглов

Варианты повышения быстродействия системы

Для системы можно выделить два варианта использования (прецедента):

• — оценка степени схожести двух заданных текстовых документов;
• — оценка степени схожести заданного текстового документа с имеющимися текстовыми документами.

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

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

В качестве возможного подхода для решения подобной задачи можно рассмотреть использование Map — Reduce [6]. В качестве этапа Map могут выступать составление шинглов и вычисление их контрольных сумм, затем может выполняться сравнение и группировка результатов на этапе Reduce. Для реализации этого подхода целесообразно использовать какой-либо из каркасов (фреймворков) Map-Reduce. В то же время такой подход потребует существенной переработки программы и самого алгоритма.

Другие подходы предполагают различные варианты реализации параллельной обработки и группировки базовых подзадач. Для рассматриваемой задачи возможно применение различных технологий параллельных вычислений, включая OpenMP, OpenCL, CUDA [7], MPI и другие. Возможно применение многопоточных вычислений в рамках платформы .NET, на которой реализована исходная программа. Выбор технологии в данном случае в значительной степени определяется вычислительной платформой, которую предполагается использовать. Вариант с использованием Map-Reduce предполагает разворачивание соответствующей облачной вычислительной платформы, а также масштабируемые вычислительные ресурсы, эти вопросы в рамках небольшого вычислительного кластера ВолгГТУ пока не решены. Вариант с использованием массивно-параллельных графических ускорителей (GPU) (и соответственно — технологий OpenCL / CUDA) для данной задачи представляется достаточно эффективным [7], однако подобные вычислители доступны в рамках кластера ФЭВТ ВолгГТУ в небольшом количестве. Поскольку планируется перенос системы на неоднородную серверную платформу Intel Xeon E5 с ускорителями Intel MIC, в качестве основного был выбран вариант многопоточной реализации упрощенного алгоритма шинглов на языке С++ с возможным использованием API для Intel MIC [8].