3.2.3 Метод «опорных» слов

Существует еще один способ выявления почти дубликатов, основанный на сигнатурном подходе. Данный метод тоже заключается в использовании лексических принципов, то есть на основе словаря. Метод был предложен С. Ильинским и др. [46] и получил название — метод «опорных» слов. Рассмотрим более детально принцип данного алгоритма.

Изначально из индекса по правилу, описанному ниже, мы выбираем множество из N слов, называемых «опорными». В данном случае, N определяется экспериментально. В дальнейшем, каждый документ выглядит N-мерным двоичным вектором, в котором i-я координата равна 1, если i-е «опорное» слово имеет в документе относительную частоту выше определенного порога (устанавливаемого отдельно для каждого «опорного» слова) и равна 0 в противном случае. Этот двоичный вектор и является сигнатурой документа. Соответственно, два документа считаются идентичными при совпадении сигнатур. При построении множества «опорных» слов используются следующие соображения:

1. Множество слов должно охватывать максимально возможное число документов.

2. Число слов в наборе должно быть минимальным.

3. При этом «качество» слова должно быть максимально высоким. Рассмотрим принцип построения множества алгоритма и выбор пороговых частиц. Допустим «частота» — это нормированная внутридокументная частота слова в документе TF, которая находится в диапазоне 0...1, единица в данном случае будет соответствовать наиболее частому слову в документе TF. Распределение документов по данной внутридокументной «частоте» строится для каждого слова однократно. Рассмотрим несколько этапов, каждый из которых состоит из двух фаз. В первой фазе увеличивается покрытие документов в индексе при фиксированной (ограниченной снизу) точности. Во второй фазе уже увеличивается точность при фиксированном покрытии. В данном случае точность будет максимально высокой, если повторение слова в дельта-окрестности значения относительной частоты минимально. Частота, которая имеет наибольшую точность, получила название пороговой. Поэтапно сортируются самые неподходящие слова, а когда наступает последняя стадия, то остаются только группы слов, которых достаточно для обеспечения качественного покрытия. Получается, что благодаря этому алгоритму, можно отфильтровать несколько тысяч слов и оставить только 3-5 тысяч.

3.3 Метод шинглов

Наибольшую известность поиска плагиата в произвольных текстах получил метод «шинглов» [35-37]. Алгоритм шинглов — алгоритм, разработанный для поиска копий и дубликатов рассматриваемого текста в документе, мощный инструмент, призванный бороться с проявлениями плагиата.

Уди Манбер в 1994г. первым в мире выразил идею поиска дубликатов, а в 1997г. Андрей Бродер оптимизировал и довел её до логического завершения, дав имя данной системе — «алгоритм шинглов».

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

Разберем, через какие этапы проходит текст, подвергшийся сравнению: