Пользователь
0,0
рейтинг
1 августа 2009 в 13:31

Разработка → Поиск нечетких дубликатов. Алгоритм шинглов для веб-документов

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

Заключение


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

Оригинальная статья на нашем блоге: Часть 1. Алгоритм шинглов для веб-документов. Следите за обновлениями, скоро будет продолжение.
Виталий Родненко @Skaizer
карма
29,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

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

  • НЛО прилетело и опубликовало эту надпись здесь
  • +4
    Извиняюсь за глупый вопрос, но зачем нам использовать 84 разных алгоритма вычисления хеша? Разве одного не достаточно? Я скорей всего где-то что-то недопонял :)
    • +1
      Использование 84 различных функций нахождения контрольных сумм позволит:
      1) Конкретно определять порог, для определения, когда документ является почти-дубликатом. То есть например если 5 из 84х сходятся, то почти дубликаты.
      2) Алгоритм супершинглов подразумевает разбиение 84х контрольных сумм на группы (супершинглы), из которых так же, например, могут вычисляться контрольные суммы и сравниваться между собой.

      Использовать один алгоритм вычисления контрольной суммы вполне возможно, и этого будет достаточно для малого количества документов, но для оптимизации процесса необходимо сводить к минимуму количество операций сравнения.
      • +1
        а почему не 48 или 96?
      • +1
        Не понял ничего из вашего объяснения, но попробую предположить:

        84 функции берутся для того, чтобы можно было выбирать 84 шингла для двух документов, которые будут относиться к разным наборам слов, но, если документы дубликаты, с большой вероятностью будут совпадать у обоих документов. Т.е. для того, чтобы, выбирая «случайные» шинглы из двух документов мы с большой вероятностью выбирали одни и те же наборы слов для документов-дубликатов.
        И третим способом скажу то же самое: если в 2х документах совпадает 50% шинглов, то в двумерных таблицах (раздел 3) двух документах будет совпадать 50% строк. Выбирая «случайным» образом 84 ячейки, мы в среднем получим 42 (грубо говоря) совпадающих контрольных суммы для обоих документов (т.к. в среднем половина строк совпадает, а выбираем ячейки мы по определённой функции, то для каждого столбца вероятность выбрать совпадающие для двух таблиц контрольные суммы равна 50% (опять же, грубо говоря). Т.е. проведя всего 84 сравнения, мы определим, что документы являются дубликатами
        • 0
          з.ы. конечно, число 84 не принципиально:)
          • +1
            Может число 84 навеяно произведением «Автостопом по галактике» и ответом 42?
        • 0
          Все верно :)
      • 0
        Понял :) Спасибо за разъяснение.
  • 0
    Если мы делаем случайную выборку контрольных сумм для каждой из 84х строк двумерного массива. Наверное проще было перед тем как хэшировать шинглы выбирать для каждой хэш-функции случайную шинглу и только её уже хэшировать. Т.о. не нужно будет хэшировать для каждого алгоритма все шинглы. Или я что-то недопонял?
    • 0
      А по какому принципу вы будете выбирать случайный шингл для каждой функции?
      • 0
        Разьве это проблема? Для этого есть функция random()
        • 0
          Вероятность того, что вы отберете одинаковые шинглы будет минимальна. Для почти дубликатов можно предположить, что одинаковые подпоследовательности слов будут встречаться чаще, следовательно при случайной выборке высока вероятность отбора именно одинаковых контрольных сумм.
          • 0
            А разьве при выборке минимального хеша вероятность того, что я отберу одинаковые шинглы будет отличаться от того что я выберу случайную шинглу до хеширования? По моему нет.
            • 0
              Минимальный хеш будет одинаков для текстов с вероятностью, равной проценту совпадающих шинглов в двух документах. А случайный хеш будет одинаков с вероятностью, равной 1/количество шинглов. Разница очевидна :)
              • +1
                з.ы. 1/количество шинглов это у полных дубликатов. Если совпадение не полное — соответственно нужно ещё умношить на процент совпадающих шинглов. Т.е. вероятность найти совпадение при случайной выборке в <количество шинглов> раз меньше.
                • 0
                  Согласен, спасибо за разъяснение.
              • 0
                Спасибо, опередили :)
  • 0
    Да, интересная идея, полезная.
    Надо будет взять на вооружение, в работе пригодится. :)
  • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      1) Сравнение строк более ресурсоёмко, чем сравнение контрольных сумм, по этой причине высчитываются хэши.
      2) Количество сравнений, если не выполнять случайную выборку будет экспоненциально зависеть от количества шинглов, для больших документов это выльется в ресурсоемкую задачу. А так мы в 84 сравнения сможем определить, являются документы почти дублями или нет.
      • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          У меня тоже первая мысль была, что такая выборка похожа на случайную. Но вторая мысль была, что раз об этом пишут, значит всё не так просто и надо ещё чуть-чуть подумать :)
        • 0
          1) Алгоримт предназначен для массового сравнения, когда обрабатываются не 1-10000 текстов, а гораздо больше.
          2) Нет, это разные вещи :) Вот ответ на вопрос: habrahabr.ru/blogs/algorithm/65944/#comment_1850489
          • НЛО прилетело и опубликовало эту надпись здесь
            • 0
              Результат экспериментов :)
              На данном этапе высчитывать контрольные суммы через 84 функции может показаться нелогичным. Но в модификации алгоритма шинглов используется случайная выборка над этими 84мя значениями для увеличения производительности.
              • НЛО прилетело и опубликовало эту надпись здесь
                • 0
                  Извиняюсь, не правильно выразился. Не случайная выборка производится. 84 шингла разбивают на 6 групп по 14 шинглов, далее сравнивают.
        • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      Чтобы найти процент совпадений из 2х наборов по 1000 шинглов, нужно провести 1000000 сравнений. А 1000 шинглов — это совсем немного — только на этой странице их на порядок больше.
      • 0
        Да, когда вы сравниваете 2 документа, этим можно пренебречь. А если вы сравниваете миллион?
  • 0
    Не могли бы вы прокомментировать зачем для каждого шилинга рассчитывается несколько хэш функций и почему мы выбираем для сравнения шилингов определённый тот хэш, значение которого минимально? Есть мнение, что это требуется для последующего усовершенствования алгоритма, а на данном этапе не имеет смысла.
    Если что-то не так понял, прошу извинить, тк читал полностью только вашу первую статью на эту тему, а данную лишь пробежал глазами.
    • 0
      Веткой выше как раз это мы обсуждаем с автором)
  • 0
    Почему именно 84 функции? Почему не 2, 10?

    Про отсутствие смысловой нагрузки у прилагательных лучше бы убрали…
  • 0
    Ээээх. Где вы были раньше :))) Такая статья бы мне ой как помогла в свое время…
    • 0
      Аналогично. Годика 3 назад бы очень пригодилось!
    • 0
      Универ? )
      • +1
        К сожалению нет, такого не преподавали :) В одном проекте давно (3-5 лет назад, а может и больше) необходимо было использовать шинглы. Много литературы было пролопачено (т.к. столкнулись в первый раз), в итоге все-таки добили. Проекта того уже нет на горизонте (по отдельным причинам), сейчас, прочитав обе ваши статьи, вспомнил.
  • 0
    Как я описывал выше, сравнивать элементы каждого из 84х массивов между собой — ресурсоемко. Для увеличения производительности выполним случайную выборку контрольных сумм для каждой из 84х строк двумерного массива, для обоих текстов. Например, будем выбирать самое минимальное значение из каждой строки.

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

    Пример: 100 шинглов * 84 хеша
    8400 операции сравнения
    поиск минимума 99 сравнений * 84 хеша + 84сравнения итого 8400 :)

    Для оптимизации предлагаю сравнивать не минимальные, а случайные или последовательно первый из первого шингла, второй со второго, 84й из 84го, а далее опять 1й,2й и т.д.
    • 0
      Пример: 100 шинглов * 84 хеша
      8400 операции сравнения
      поиск минимума 99 сравнений * 84 хеша + 84сравнения итого 8400 :)

      Сравнить два массива по 100 шинглов => 10000 операций сравнения, учитываем, что у нас 84 таких набора, то 84 * 10000 = 840000 сравнений.
      Используя случайную выборку мы ограничиваемся 84 сравнениями на финальном этапе, ну и + выборка минимального элемента.
      • 0
        Сравнить два массива по 100 шинглов => 10000 операций сравнения

        Во первых шинглы не нужно сравнивать, нужно сравнивать их хеши, а хешей 84*100 = 8400.
        Во вторых хеши сравниваются с соответствующими т.е. CRC(1го шингла:1го сайта) с CRC(1го шингла:2го сайта) и т.д. до 100го шингла каждого сайта.

        Ну и основной момент в том что поиск минимального значения хеша лишний.
        • 0
          84 набора как раз-таки и используются для последующей случайной выборки.
          Для чего сравнивать каждый из 100 значений 84 раза между собой, в соответствии алгоритму хэширования? Можно было бы вполне обойти и одной функцией.
  • 0
    > Выборка происходит внахлест, а не встык.

    Можно развернуть? Не совсем понятно как это — внахлест.
    • 0
      А взгляните на рисунок пункта_2, там как раз иллюстрировано, что такое выборка внахлест.
      • 0
        Если, как на картинке, в тексте меньше 10 слов — то как? Надо закольцевать текст? И считать шинглы уже по нему?
        • 0
          Как выход, при сравнении коротких текстов, можно уменьшить длину шингла и закольцевать текст, вы правы.
          • 0
            Понял, спасибо.
  • НЛО прилетело и опубликовало эту надпись здесь
    • +1
      ну, видимо автор и пытался это рассказать. только не «к примеру минимальны», а именно минимальны.
  • 0
    Как я себе вижу интерпретацию конечного результата. Пусть в исходных текстах по n шинглов, из которых m одинаковых в обоих текстах. Выбор минимального значения хеша — это фактически выбор «псевдо»-случайного элемента в следующем смысле. В каждом из текстов с вероятностью m/n выбранный шингл попадет на совпадающую часть, причем, если это произойдет в обоих текстах, то это будет один и тот же шингл. Т.е. шингл1 и шингл2 совпадут с вероятностью (m/n)^2.
    При достаточно большом количестве испытаний (хеш-функций), отношение числа совпадений к числу испытаний будет близко к вероятности совпадения. Т.е. то что мы получаем в конце, это не (m/n) как хотелось бы, а (m/n)^2.
    Вы это учитываете?
  • –1
    А почему в шингле 10 слов? Если в двух предложениях будут перемешенны 20 слов в разном порядку, то скорее всего с длинной шингла в 10, вы не найдете сходства. Может я чего-то недопонял?
  • 0
    Интересно, но уж слишком много magic numbers.
    Почему 84 хэша? Для реализации алгоритмов, базирующихся на показанном? Странно, причинно-следственная связь не в ту сторону :)
    Почему 10 слов в шингле?
    Как уже упоминали выше, увеличения производительности путем выбора минимальных значений не достигается, все те же 8400 операций.
    Ну и самое интересное — эффективность алгоритма. Почему следует использовать этот алгоритм? Насколько эффективно он позволяет найти дубликаты? Какова вычислительная сложность? Насколько критично количество сравниваемых документов? И т.д.
    • –1
      Почему бы не прочитать статью?
  • +3
    Ой-ой, по моему вы что-то сильно путаете. Судя по всему, вы пытаетесь рассказать алгоритм, предложенный Fetterly et al. A Large-Scale Study of the Evolution of Web Pages, www2003. Никаких 84 хэш-функций там нет, это стандартное вычисление мегашинглов на основе вероятностного вычисления индекса Жаккарда (отсюда кстати и эмперическая оценка в 84 перестановки, которая (на память) дает погрешность в 15%). У Зеленкова и Сегаловича, как я понял, сам алгорим изложен не верно, да и у Fetterly очень кратко написано.

    Прочитайте оригинал Broder et al, Syntactic Clustering of the Web, 1997 и еще статья 1993 про полиномы Рабина и сравните с тем, что вы написали. А по поводу мистических цифр — Broder et al, Min-Wise Independent Permutations 2000 и там по ссылкам.

    И, кстати, при вычислении индекса жаккрада сложность не экспоненциальная, а полиномиальная (хотя это тоже плохо на больших коллекциях) :)
  • +2
    с нетерпением буду ждать выхода четвёртой статьи — про аццких шинглов :)))))))
    • 0
      … случайно выбирает 84 мегашингла… :)
  • –2
    а ничего что контрольные суммы шинглов не гарантируют совпадение самих шинглов? :)
    • –1
      видимо ничего :)
    • –2
      Совпадение контрольных сумм шинглов гарантирует совпадение самих шинглов.
      • +1
        Конечно при отсутствии коллизий хеш-функций.
        • –1
          а кто гарантирует отсутствие коллизий? :) вообщето это ни один хэш алгоритм не гарантирует :) гарантируют только сложность подбора коллизии и большую разницу в хэшах при малом изменении исходных данных :)

          вообще в принципе отношение N:M где N>M всегда будет иметь коллизии :)
          • –1
            Вероятность в данном случае крайне низка и никакой угрозы не несет.
            • –1
              где математическое доказательство этой низкой вероятности? :)
              кроме всего прочего описанный в статье метод рушится после простой перестановки сущствительных в предложении :)
              • –1
                Зачем нам математическое доказательство на данном этапе? Теорию алгоритма я разъяснил, думаю для заинтересованных этого будет достаточно.

                Смотря что понимать под «простой», равнозначно можно сказать, что перестановка существительных в предложении делает статью не дубликатом, а уникальной, определите границы, пожалуйста.
                • –1
                  то есть вы изначально опираетесь на необснованные выкладки и считаете что они будут работать?

                  если вас интересует дубликат то зачем столько накладываемых фильтров? :) определите рамки пожалуйста :)
                  • –1
                    Я изначально опираюсь на труд Зеленкова Ю. Г. и Сегаловича И.В., ссылку на который представил в статье. Повторяюсь, для разъяснения теории считаю этого достаточным.

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

                    Что значит «если вас интересует дубликат »? Меня интересует не дубликат, а проверка на почти-дубликат, это во первых. Во вторых какие рамки нужно определить? Каждый сам для себя определит, что считать дубликатом, а что нет. Выражайтесь конкретнее.
                    • –1
                      у Зеленкова с Сегаловичем тоже обоснования как я понимаю нет

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

                      так чем почти дубликат где два существительных поменяны местами отличается от других «почти дубликатов»? :)
                      • –1
                        Мне так и не понятно, какие рамки вы просили определить, пожалуйста, поясните.
                        у Зеленкова с Сегаловичем тоже обоснования как я понимаю нет

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

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

                        По вашему сравниваются слова/фразы в явном виде, а не их контрольные суммы, алгоритмы расчета которых содержат вероятность возникновения коллизий?
                        Данный подход называется «Методом описательных слов», насколько мне известно и вполне может быть использован для решения конкретных задач.
                        так чем почти дубликат где два существительных поменяны местами отличается от других «почти дубликатов»? :)

                        Для веб-документов подобная подмена неприменима, перестановка существительных в предложении местами превратит текст в нечитабельный, сайт, на котором он будет размещен вероятно постигнет участь дорвеев.
                        Существует услуга размножения текстов для SEOшников, где «обмана» поисковых систем для слов и словосочетаний подбирают синонимы, затем производят случайное комбинирование и в результате получают читабельные тексты, готовые к размещению на площадках. Для фильтрации наиболее «уникальных» статей, использование данного алгоритма вполне уместно.
                        • 0
                          * где для «обмана»
                        • –1
                          еще раз повторюсь, равенство хэшсумм не гарантирует вам равенства первоначальных «шинглов». А если еще посмотреть на то как выбираются шинглы, то понятно что даже равенство шинглов не гарантирует идентичность статей (язык это не просто набор слов, это еще и знаки препинания и артикли с предлогами и тп). Отсюда берем «вероянтное, но не обязательное» условие A умножаем его на такоеже условие B, получаем еще менее вероятно и менее обязательное условие C. Хорошо что гугл такой «математикой» не занимается…

                          Опять опрометчивые заявления. Пожалуйста вот вам простой текст который от смены мест существительных ни в чем не меняется по смыслу:
                          Сергей Иванович Перепелкин купил на днях новую продукцию фирмы филипс кофемолку свомещенную с блендером совершенно новой модели «Колибри» которая зарекомендовала себя на рынке как отличный продукт.

                          На днях купил Перепелкин Сергей Иванович новую блендер, продукцию филипс, совмещенный с кофемолкой, которая зарекомендовала себя на рынке как отличный продукт новой модели «Колибри»

                          Следуя описанному алгоритму эти тексты совсем различны. Хотя простой взвес слов и их отношений покажет что они идентичны.
                          • 0
                            опять же если нужно простое сравнение, то смысла вычислять все эти суммы нет никакого.
                            • 0
                              Про хэш суммы понятно, я еще в самом начале дискуссии это указал.

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

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

                              Но давайте вспомним, все началось с коллизий хэш-алгоритмов. Собственно вопрос: вы считаете, что даже в приведенном вами методе описательных слов, фразы сравниваются в явном виде, а не их контрольные суммы?
                              • 0
                                То что алгоритм в частном случае работает, не значит что он работает в общем случае (опять же хэши и вырезание «лишнего»)

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

                                  Обоснование использования контрольных сумм: быстрота сравнения, легковестность хранения в БД (значительная между прочим).
                                  Сравнивая вы 2 текста без использования хэш функций, возможно значительную разницу вы и не почувствуете. При пакетной обработке текстов использование контрольных сумм значительно(!) ускорит процесс.
                                  • –1
                                    ага, а сравнить простую сумму без шинглов еще быстрее :)
                                    • 0
                                      Не вижу смысла сравнивать простую сумму без шинглов *PARDON*
                                    • 0
                                      + не вижу смысла писать комментарии просто чтобы что-то написать.
                                      Если по делу сказать больше нечего, предлагают завершить данную ветку.
                                      • +1
                                        чтобы сравнить тексты на идентичность :) ну да ладно, оставим это действительно :) а то заклюют же :)
                          • НЛО прилетело и опубликовало эту надпись здесь
                            • –2
                              я не против шинглирования, я против таких небрежных сумм поверх этого шинглирования :)
                              • НЛО прилетело и опубликовало эту надпись здесь
                                • –2
                                  читал, и что? я все равно считаю что эта схема не дает нужного результата в общем случае. А в тех случаях, в которых она дает результат подойдут и более простые схемы.
                                  • 0
                                    я все равно считаю что эта схема не дает нужного результата в общем случае.

                                    Ваше право, считайте :)
                                    • –2
                                      мое то мое, но как минусуете то :)
                                  • НЛО прилетело и опубликовало эту надпись здесь
                  • НЛО прилетело и опубликовало эту надпись здесь
                    • –2
                      вот и считают :) коллизии уже давным давно подбираются за конечное время для таких распространненных хэшей как мд5 и ша1
                      • НЛО прилетело и опубликовало эту надпись здесь
                        • –2
                          • НЛО прилетело и опубликовало эту надпись здесь
                            • –1
                              вообщето там понизили до 33 однако…
                              и кроме того привели примеры…
                              • НЛО прилетело и опубликовало эту надпись здесь
      • НЛО прилетело и опубликовало эту надпись здесь
  • +1
    Спасибо за статью, только уж очень запутано, много незнакомых слов и нет практических примеров.
    Сразу говорю я плохой математик, может свяязано с этим, может с чем то еще, но делаю так:
    1. Чищю текст от мусора, примерно как сказано в этой статье;
    2. Разбиваю на шинглы по 2 слова (тексты у меня небольшие, мне хватает);
    3. Генерю хеш использую md5 (пробовал другие алгоритмы, но не покатило как то, хотя слышал, что это не самый быстрый алгоритм и плюс хеш получается символьно-числовой, а такой, опять же по слухам. сравнимать тяжелее чем чисто числовой);
    4. Заливаю в БД (таблица из двух столбцов — doc_id и word_hash, названия взял из одной из предыдущих статей на эту тему);
    5. В таблице в документами есть поля id, parent, percent (это конечно не все, но для примера больше и не надо, что бы не путать), поле parent указывает id документа наиболее похожего на текущий (значение по умолчанию 0), поле percent — процент похожести (значение по умолчанию -1);
    6. Таблиц с хешами у меня две — основная и временная, в основной хранятся хеши уникальных документов, во временной еще не проверенных на уникальность;
    7. В БД стоит event (можно и внешними средствами выполнять его фенкцию), который и обрабатывает с определенным интервалом временную таблицу, выполняя процедуру которая содержит такой запрос (конечно не только его, но именно этот запрос ищет ID документы с наибольшим количеством одинаковых с проверяемым документом шинглов):
    SELECT t1.doc_id, count(t1.word_hash) AS parent into p_parent,p_c_doc_id

    FROM items_hashes t1, items_hashes_tmp t2

    WHERE t2.doc_id=p_item_id AND t1.word_hash=t2.word_hash

    GROUP BY t1.doc_id

    ORDER BY parent DESC

    LIMIT 1;
    Этот запрос используется в хранимой процедуре MySQL поэтому тут есть вещи типа «into p_parent,p_c_doc_id
    » — сохраняем полученный значения в эти переменные и p_item_id — эта переменная содержит ID проверяемого документы, значение получает через курсор.
    8. Затем выполняю:
    SELECT 100/p_count*p_c_doc_id into p_percent;
    p_count = количество шинглов в проверяемом документе, p_c_doc_id=количество идентичных шинглов в документе максимально похожем на проверяемый (как то не очень понятно предложение получилось, но глядя на звпросы будет все понятно, надеюсь).
    9. После выясиления. если считаю документ оригинальным переношу его шинглы в постоянную таблицу, если документ признается дубликатом — его шинглы удаляются и в дальнейшем с ним уже ничего не сравнивается.
    Вот примерно так, буду рад критике и предложениям. Надеюсь кому то это поможет понять.
    • 0
      вроде бы вы смотрите только одинаковые шинглы, но не учитываете количество разных. хз, хорошо это или плохо, зависит от задачи. сформулируйте, условно на пальцах, что для вас похожие документы, т.к. это сильно влияет на алгоритмы. т.е. если вы ищите, к примеру, плагиат — это одно, а если новости об одном и том же, то несколько другое, от этого у будет зависеть мера.

      а в пункте 9 вы пытаетесь делать кластеризацию, но, например, если A похоже на B, B похоже на C, но A не похоже на C, то A с С у вас не стростется. тоже от задачи зависит, хорошо это или плохо.

      в общем, не понятно, какую задачу решает ваш алгоритм :)
      • +1
        Я ищу дубликаты новостей. Если А похож на Б, Б похож на С, но А не похож на С то А и С останутся, и это рпвильно. Например А это какая то новость, а С это более полный обзор этой новости, так пусть он останется. А если Б отличается от А парой слов, тотакое нам не надо, вот Б и будет удален. Так оно и надо, это нормально.
  • 0
    Редко кто SEO, как наукой занимается — ТС молодец, конечно.
    • 0
      Не так уж и редко.
  • –1
    мораль примерно проста — достаточно переставить два слова местами, чтобы текст стал уникальным.
    Интересная статья для размышления при использовании и разработке синонимайзеров )
  • 0
    Пара замечаний/вопросов:
    1. Если быть точным, то описанный вами алгоритм просто цитируется в статье Зеленкова и Сегаловича. Оригинальное описание алгоритма дано в статье Fetterly, Manasse, Najork. A Large-Scale Study of the Evolution of Web Pages.
    2. В оригинальном алгоритме для расчета дактилограмм («pre-images») используется алгоритм Карпа-Рабина. С какой целью вы заменили его на crc32, md5 и т.д.?
    3. Проводили ли числовую оценку своей реализации? В статье Зеленкова и Сегаловича говорится, что их первоначальная реализация алгоритма давала полноту равную 0.0, и поэтому в действительности там вместо 84-х функций использовалось 36. Соответственно, возникают сомнения в том, что ваша реализация алгоритма может дать приемлемое качество.
    • 0
      Интересно было бы услышать ответы.
  • 0
    Прошу прощения, стоит ли ждать статью про супершинглы?

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.