Часть 1. Алгоритм шинглов для веб-документов

VitaliyRodnenko, 01.08.2009

Ранее я показал элементарную реализацию алгоритма шинглов, позволяющую определять, являются ли два документа почти дубликатами или нет. В этот раз я поясню реализацию алгоритма, описанную Зеленковым  Ю. Г. и Сегаловичем И.В. в публикации «Сравнительный анализ методов определения нечетких дубликатов для Web-документов».

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

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

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

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

Итак, алгоритм шинглов для веб-документов

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

  1. канонизация текста;
  2. разбиение на шинглы;
  3. вычисление хэшей шинглов с помощью 84х статических функций;
  4. случайная выборка 84 значений контрольных сумм;
  5. сравнение, определение результата.

1. Канонизация текста

Что такое канонизация текста я описывал в своей прошлой статье об алгоритме шинглов. Но в коротко повторюсь. Канонизация текста приводит оригинальный текст к единой нормальной форме.

Текст очищается от предлогов, союзов, знаков препинания, HTML тегов, и прочего не нужного «мусора», который не должен участвовать в сравнении. В большинстве случаев так же предлагается удалять из текста прилагательные, так как они не несут смысловой нагрузки.

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

С канонизацию текста можно экспериментировать и экспериментировать, простор для действий тут широк.

На выходе имеем текст, очищенный от «мусора», и готовый для сравнения.

Процесс канонизации текста

2. Разбиение на шинглы

Шинглы (англ) — чешуйки, выделенные из статьи подпоследовательности слов.

Необходимо из сравниваемых текстов выделить подпоследовательности слов, идущих друг за другом по 10 штук (длина шингла). Выборка происходит внахлест, а не встык.

Таким образом, разбивая текст на подпоследовательности, мы получим набор шинглов в количестве равному количеству слов минус длина шингла плюс один (кол_во_слов — длина_шингла + 1).

Напоминаю, что действия по каждому из пунктов выполняются для каждого из сравниваемых текстов.

Процесс разбиения текста на шинглы

3. Вычисление хэшей шинглов с помощью 84х статических функций

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

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

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

Поясню: для каждого шингла рассчитывается 84 значения контрольной суммы через разные функции (например SHA1, MD5, CRC32 и т.д., всего 84 функции). Итак каждый из текстов будет представлен, можно сказать, в виде двумерного массива из 84х строк, где каждая строка характеризует соответствующую из 84х функций контрольных сумм.

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

Нахождение контрольных сумм шинглов

4. Случайная выборка 84 значений контрольных сумм

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

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

Случайная выборка шинглов

5. Сравнение, определение результата

И последний этап — сравнение. Сравниваем между собой 84 элемента первого массива с соответствующими 84ю элементами второго массива, считаем отношение одинаковых значений, из этого получаем результат.

Сравнение, результат

Заключение

Надеюсь, я доступно смог изложить теорию нахождения почти дубликатов для веб-документов, описанную в публикации Зеленкова  Ю. Г. и Сегаловича И.В. не вдаваясь в особенности реализации на конкретном языке программирования.

Во второй статье цикла я собираюсь описать алгоритм супершинглов для веб-документов.

Надеюсь было интересно, удачи.

Подписаться на обновления блога

Вам понравился наш блог, хотите следить за обновлениями? Подпишитесь на RSS рассылку или рассылку по электронной почте. Так же вы можете следить за нами в Twitter.

Категории: Алгоритмы | Комментировать

Комментарии (19)

  1. CakePHP. Как создать модуль без привязки к таблице в базе данных / 02.08.2009 в 13:26

    [...] Алгоритм шинглов для веб-документов New [...]

  2. Jack / 04.08.2009 в 12:58

    Отличная и понятная статья.
    Правильно ли я понял, что на этапе канонизации — множество вариантов, и оптимальный способ «чистки» зависит от набора сравниваемых документов? Если да, то есть ли какие-нибудь рекомендации по выбору варианта канонизации. Использование морфологического и лексического анализа — это не слишком простая задача..

    P.S. Ожидается ли реализация на том же Python?

  3. Skaizer / 06.08.2009 в 11:21

    Jack, правильнее было бы сказать, что оптимальный способ чистки зависит от типа сравниваемых документов, если сравниваются статьи, то выкидывать предлоги, союзы, знаки препинания например, если это HTML документы, то чистить текст от тегов. Использовать морфологический анализ — по желанию, как вы правильно выразились — это не слишком простая задача, но существуют готовые библиотеки, которые можно использовать.
    Реализовывать я врядли буду данный алгоритм, времени нет абсолютно, к сожалению, да и смысла пока нету, т.к. обрабатывать миллионы страниц мне не надо. А для фильтрации уникальных статей, предназначенных для продвижения сайтов мне хватает своей реализации.

  4. Александр / 24.08.2009 в 22:07

    Серьезная и понятная статья (правда, в области с хэшами не совсем понятно, но это МНЕ и, видимо, потому, что я не программист). Нечасто хочется сказать «браво» блоггеру, но в данный момент хочется. Приятно видеть «Ученого о СЕО», который зрит в корень ПС. Еще раз «браво» — настоящий «хакерский подход» (я сейчас совсем не про киберпреступников говорю, а именно про подход к решению задач).

  5. Алексей / 31.08.2009 в 23:59

    Во-первых, огромное спасибо за проделанный труд автору!
    Тема щекотливая, интересная и в тоже время сложная. Есть пару вопросов.
    (1 вопрос) Почему используют РАЗНЫЕ статические функции?

    Насколько я понял, двумерный массив состоит: 84 строки (стат. функции) и N’го числа столбцов (зависит от численного количества шинглов).
    (2 вопрос) Если одномерный массив формируется случайным образом для каждого текста, то в чем смысл проверки? Поясню. Скажем для первого текста случайно выбрались только такие то функции, а для второго текста — другие, т.е. их контрольные суммы не сравнить. Или я не правильно понял?

  6. Skaizer / 01.09.2009 в 10:47

    Здравствуйте, Алексей.

    На два вопроса дам один обобщающий ответ. Вы все верно поняли, двумерный массив состоит из 84 строки и N’го числа столбцов. Использование 84х различных статических функций необходимо для осуществления выборки 84х случайных шинглов для каждого из текстов (одномерный массив получится в итоге). То есть из одной строки выбирается один элемент.

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

    Далее 84 элемента массива случайных значений для первого текста ставятся в соответствие 84м элементам массива случайных значений второго текста. То есть сравниваем следующим образом (пример на яыке Python):

    # A => список из 84 элементов случайной выборки из матрицы контрольных сумм для ТЕКСТА_1 (содержит минимальные значения каждой из строк)
    # B => список из 84 элементов случайной выборки из матрицы контрольных сумм для ТЕКСТА_2 (содержит минимальные значения каждой из строк)
    for i in range(84):
        if A[i] == B[i]:
            #Прибавляем +1 к количеству совпавших шинглов

    То есть элементы одномерных массивов для двух текстов сравниваются попарно, в соответствии алгоритму контрольной суммы, по которому они были вычислены. Контрольная сумма одного текста, вычисленная, например через MD5 сравнивается с контрольной суммой другого текста, так же вычисленной через MD5, а не SHA1 и прочие.

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

    Надеюсь, смог доступно объяснить :)

  7. Алексей / 01.09.2009 в 14:07

    Огромное спасибо за доходчивое объяснение!
    Тогда у меня к вам вопросы несколько практического плана :)
    1. Есть ли смысл размножать тексты на автомате? Скажем, Generating The Web, например. Тем более, если предположить, что ПС использует семантику (обычная замена слов на синонимы в этом случае не должна сработать)
    2. Второй вопрос, вытекает из первого :) Какую, по мнению автора, длину шингла использовать при проверке на уникальность (понимаю, что чем длина шингла меньше — тем выше вероятность получить уникальный контент, но все же интересно послушать Ваше мнение)

  8. Skaizer / 06.09.2009 в 22:48

    Извиняюсь, что так не сразу отвечаю, был в другом городе на конференции, времени почитать комменты в блоге не было. Итак:

    1. Размножать тексты смысл имеет. Я в практике активно использую размноженные статьи, хотя для жирных площадок статьи использую уникальные. Для площадок < =8$ - размноженные. Generating The Web можно использовать, но из обще распространенного софта я предпочитаю Allsubmitter.
    2. Длина шингла полностью зависит от длины текста. И не всегда чем меньше длина, тем лучше отбор, порой короткий шингл может отбросить большое количество уникальных статей. На практике для текстов в 2000-3500 символов я использую длину шингла в 8 слов, и отбираю статьи с уникальностью от 96%. Для большего текста можно использовать длину шингла в 9 или 10 слов.

    См. статью размножение статей в Allsubmitter. В статье я как раз описал отличие принципа размножения Allsubmitter-ом от Generating The Web (в статье, где упоминается другой софт). Generating The Web уж слишком долго генерирует достаточное количество статей, ввиду заложенного алгоритма перебора синонимов.

  9. булат / 11.10.2009 в 22:25

    А если в тексте поменять местами соседние слова то какой результат даст этот алгоритм при сравнение получившегося текста и исходного?

  10. Skaizer / 21.10.2009 в 22:48

    Если поменять соседние слова местами, то алгоритм определит текст уникальным. Но определить последовательности слов можно на этапе канонизации, тогда слова для двух текстов будут выстроены порядок по одинаковому алгоритму.

  11. TepKuH / 21.11.2009 в 00:45

    >»Но определить последовательности слов можно на этапе канонизации, тогда слова для двух текстов будут выстроены порядок по одинаковому алгоритму»
    Не понятно что имелось ввиду. По какому алгоритму Вы предлагаете выстраивать слова? по алфавиту? Но тогда добавление в текст хотя бы 1 слова уже сломает все построение.
    PS. Спасибо за алгоритм. Очень интересный.

  12. Skaizer / 23.11.2009 в 22:14

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

  13. TepKuH / 24.11.2009 в 16:08

    >в принципе изменение любой последовательности слов путем добавления нового слова ее разрушит
    Это я согласен. Но добавление какого либо слова-фразы к тексту это довольно таки не простая задача(если слово-фраза в тему, а не с балды). Речь то как раз именно о перестановке слов. Вы просто выше сказали что определить перестановку можно на этапе канонизации. Вот я не очень понимаю по какому алгоритму.
    Есть еще одна слабость алгоритма, но она на конечной фазе(вычисление процента схожести) и правда относится к Вашей тема про «…поиск нечетких дубликатов текста»
    Она(слабость) заключается в том что процент вычисляется как мне кажется не правильно. Объясню на примере: есть у нас контент 10кбайт. Мы берем от туда скажем первый абзац объемом ~1кбайт. Т.е. ничего не меняли, ничего не правили, берем просто какой то небольшой(по сравнению с общим объемом) кусок и в данном случаи процент похожести документов будет крайне низкий. Хотя маленький кусок взят из большого.

  14. Виктор / 27.12.2009 в 23:41

    С наступающим Новым годом! Процветания и творческих успехов. Отличная компания, отличные люди! Так держать!

  15. Ukrbox / 20.02.2010 в 10:31

    Как по мне, так основная проблема это канонизация текста. Это требует понимания лингвистических особенностей рассматриваемого текста и такое каноническое преобразование может быть неоднозначным. Имхо кончено.

  16. Аватар / 15.03.2010 в 03:41

    Хочу задать вопрос автору, Это не вы случайно написали программу шингл эксперт?
    Если нет, то хочется знать, вы реализуете вышеописанный алгоритм в виде программы?

  17. Skaizer / 08.04.2010 в 21:58

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

  18. Алексей / 30.01.2011 в 15:23

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

  19. Игорь / 13.10.2011 в 22:52

    Поддерживаю вопрос о выборе функций — всегда ли они должны быть типичными хешевыми?

Оставить комментарий

480×60
480×60