Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 103
Извиняюсь за глупый вопрос, но зачем нам использовать 84 разных алгоритма вычисления хеша? Разве одного не достаточно? Я скорей всего где-то что-то недопонял :)
Использование 84 различных функций нахождения контрольных сумм позволит:
1) Конкретно определять порог, для определения, когда документ является почти-дубликатом. То есть например если 5 из 84х сходятся, то почти дубликаты.
2) Алгоритм супершинглов подразумевает разбиение 84х контрольных сумм на группы (супершинглы), из которых так же, например, могут вычисляться контрольные суммы и сравниваться между собой.
Использовать один алгоритм вычисления контрольной суммы вполне возможно, и этого будет достаточно для малого количества документов, но для оптимизации процесса необходимо сводить к минимуму количество операций сравнения.
1) Конкретно определять порог, для определения, когда документ является почти-дубликатом. То есть например если 5 из 84х сходятся, то почти дубликаты.
2) Алгоритм супершинглов подразумевает разбиение 84х контрольных сумм на группы (супершинглы), из которых так же, например, могут вычисляться контрольные суммы и сравниваться между собой.
Использовать один алгоритм вычисления контрольной суммы вполне возможно, и этого будет достаточно для малого количества документов, но для оптимизации процесса необходимо сводить к минимуму количество операций сравнения.
а почему не 48 или 96?
Не понял ничего из вашего объяснения, но попробую предположить:
84 функции берутся для того, чтобы можно было выбирать 84 шингла для двух документов, которые будут относиться к разным наборам слов, но, если документы дубликаты, с большой вероятностью будут совпадать у обоих документов. Т.е. для того, чтобы, выбирая «случайные» шинглы из двух документов мы с большой вероятностью выбирали одни и те же наборы слов для документов-дубликатов.
И третим способом скажу то же самое: если в 2х документах совпадает 50% шинглов, то в двумерных таблицах (раздел 3) двух документах будет совпадать 50% строк. Выбирая «случайным» образом 84 ячейки, мы в среднем получим 42 (грубо говоря) совпадающих контрольных суммы для обоих документов (т.к. в среднем половина строк совпадает, а выбираем ячейки мы по определённой функции, то для каждого столбца вероятность выбрать совпадающие для двух таблиц контрольные суммы равна 50% (опять же, грубо говоря). Т.е. проведя всего 84 сравнения, мы определим, что документы являются дубликатами
84 функции берутся для того, чтобы можно было выбирать 84 шингла для двух документов, которые будут относиться к разным наборам слов, но, если документы дубликаты, с большой вероятностью будут совпадать у обоих документов. Т.е. для того, чтобы, выбирая «случайные» шинглы из двух документов мы с большой вероятностью выбирали одни и те же наборы слов для документов-дубликатов.
И третим способом скажу то же самое: если в 2х документах совпадает 50% шинглов, то в двумерных таблицах (раздел 3) двух документах будет совпадать 50% строк. Выбирая «случайным» образом 84 ячейки, мы в среднем получим 42 (грубо говоря) совпадающих контрольных суммы для обоих документов (т.к. в среднем половина строк совпадает, а выбираем ячейки мы по определённой функции, то для каждого столбца вероятность выбрать совпадающие для двух таблиц контрольные суммы равна 50% (опять же, грубо говоря). Т.е. проведя всего 84 сравнения, мы определим, что документы являются дубликатами
Понял :) Спасибо за разъяснение.
Если мы делаем случайную выборку контрольных сумм для каждой из 84х строк двумерного массива. Наверное проще было перед тем как хэшировать шинглы выбирать для каждой хэш-функции случайную шинглу и только её уже хэшировать. Т.о. не нужно будет хэшировать для каждого алгоритма все шинглы. Или я что-то недопонял?
А по какому принципу вы будете выбирать случайный шингл для каждой функции?
Разьве это проблема? Для этого есть функция random()
Вероятность того, что вы отберете одинаковые шинглы будет минимальна. Для почти дубликатов можно предположить, что одинаковые подпоследовательности слов будут встречаться чаще, следовательно при случайной выборке высока вероятность отбора именно одинаковых контрольных сумм.
А разьве при выборке минимального хеша вероятность того, что я отберу одинаковые шинглы будет отличаться от того что я выберу случайную шинглу до хеширования? По моему нет.
Да, интересная идея, полезная.
Надо будет взять на вооружение, в работе пригодится. :)
Надо будет взять на вооружение, в работе пригодится. :)
1) Сравнение строк более ресурсоёмко, чем сравнение контрольных сумм, по этой причине высчитываются хэши.
2) Количество сравнений, если не выполнять случайную выборку будет экспоненциально зависеть от количества шинглов, для больших документов это выльется в ресурсоемкую задачу. А так мы в 84 сравнения сможем определить, являются документы почти дублями или нет.
2) Количество сравнений, если не выполнять случайную выборку будет экспоненциально зависеть от количества шинглов, для больших документов это выльется в ресурсоемкую задачу. А так мы в 84 сравнения сможем определить, являются документы почти дублями или нет.
У меня тоже первая мысль была, что такая выборка похожа на случайную. Но вторая мысль была, что раз об этом пишут, значит всё не так просто и надо ещё чуть-чуть подумать :)
1) Алгоримт предназначен для массового сравнения, когда обрабатываются не 1-10000 текстов, а гораздо больше.
2) Нет, это разные вещи :) Вот ответ на вопрос: habrahabr.ru/blogs/algorithm/65944/#comment_1850489
2) Нет, это разные вещи :) Вот ответ на вопрос: habrahabr.ru/blogs/algorithm/65944/#comment_1850489
Чтобы найти процент совпадений из 2х наборов по 1000 шинглов, нужно провести 1000000 сравнений. А 1000 шинглов — это совсем немного — только на этой странице их на порядок больше.
Не могли бы вы прокомментировать зачем для каждого шилинга рассчитывается несколько хэш функций и почему мы выбираем для сравнения шилингов определённый тот хэш, значение которого минимально? Есть мнение, что это требуется для последующего усовершенствования алгоритма, а на данном этапе не имеет смысла.
Если что-то не так понял, прошу извинить, тк читал полностью только вашу первую статью на эту тему, а данную лишь пробежал глазами.
Если что-то не так понял, прошу извинить, тк читал полностью только вашу первую статью на эту тему, а данную лишь пробежал глазами.
Почему именно 84 функции? Почему не 2, 10?
Про отсутствие смысловой нагрузки у прилагательных лучше бы убрали…
Про отсутствие смысловой нагрузки у прилагательных лучше бы убрали…
1) Про 84 функции habrahabr.ru/blogs/algorithm/65944/#comment_1850530
2) По поводу прилагательных, объясните, пожалуйста.
2) По поводу прилагательных, объясните, пожалуйста.
Ээээх. Где вы были раньше :))) Такая статья бы мне ой как помогла в свое время…
Аналогично. Годика 3 назад бы очень пригодилось!
Универ? )
К сожалению нет, такого не преподавали :) В одном проекте давно (3-5 лет назад, а может и больше) необходимо было использовать шинглы. Много литературы было пролопачено (т.к. столкнулись в первый раз), в итоге все-таки добили. Проекта того уже нет на горизонте (по отдельным причинам), сейчас, прочитав обе ваши статьи, вспомнил.
Как я описывал выше, сравнивать элементы каждого из 84х массивов между собой — ресурсоемко. Для увеличения производительности выполним случайную выборку контрольных сумм для каждой из 84х строк двумерного массива, для обоих текстов. Например, будем выбирать самое минимальное значение из каждой строки.
Сравнение двух двумерных массивов по сложности такое же как и поиск минимального значения в одномерном с последующим сравнением их с соответствующими значениями из другого массива.
Пример: 100 шинглов * 84 хеша
8400 операции сравнения
поиск минимума 99 сравнений * 84 хеша + 84сравнения итого 8400 :)
Для оптимизации предлагаю сравнивать не минимальные, а случайные или последовательно первый из первого шингла, второй со второго, 84й из 84го, а далее опять 1й,2й и т.д.
Пример: 100 шинглов * 84 хеша
8400 операции сравнения
поиск минимума 99 сравнений * 84 хеша + 84сравнения итого 8400 :)
Сравнить два массива по 100 шинглов => 10000 операций сравнения, учитываем, что у нас 84 таких набора, то 84 * 10000 = 840000 сравнений.
Используя случайную выборку мы ограничиваемся 84 сравнениями на финальном этапе, ну и + выборка минимального элемента.
Сравнить два массива по 100 шинглов => 10000 операций сравнения
Во первых шинглы не нужно сравнивать, нужно сравнивать их хеши, а хешей 84*100 = 8400.
Во вторых хеши сравниваются с соответствующими т.е. CRC(1го шингла:1го сайта) с CRC(1го шингла:2го сайта) и т.д. до 100го шингла каждого сайта.
Ну и основной момент в том что поиск минимального значения хеша лишний.
> Выборка происходит внахлест, а не встык.
Можно развернуть? Не совсем понятно как это — внахлест.
Можно развернуть? Не совсем понятно как это — внахлест.
Как я себе вижу интерпретацию конечного результата. Пусть в исходных текстах по n шинглов, из которых m одинаковых в обоих текстах. Выбор минимального значения хеша — это фактически выбор «псевдо»-случайного элемента в следующем смысле. В каждом из текстов с вероятностью m/n выбранный шингл попадет на совпадающую часть, причем, если это произойдет в обоих текстах, то это будет один и тот же шингл. Т.е. шингл1 и шингл2 совпадут с вероятностью (m/n)^2.
При достаточно большом количестве испытаний (хеш-функций), отношение числа совпадений к числу испытаний будет близко к вероятности совпадения. Т.е. то что мы получаем в конце, это не (m/n) как хотелось бы, а (m/n)^2.
Вы это учитываете?
При достаточно большом количестве испытаний (хеш-функций), отношение числа совпадений к числу испытаний будет близко к вероятности совпадения. Т.е. то что мы получаем в конце, это не (m/n) как хотелось бы, а (m/n)^2.
Вы это учитываете?
А почему в шингле 10 слов? Если в двух предложениях будут перемешенны 20 слов в разном порядку, то скорее всего с длинной шингла в 10, вы не найдете сходства. Может я чего-то недопонял?
Интересно, но уж слишком много magic numbers.
Почему 84 хэша? Для реализации алгоритмов, базирующихся на показанном? Странно, причинно-следственная связь не в ту сторону :)
Почему 10 слов в шингле?
Как уже упоминали выше, увеличения производительности путем выбора минимальных значений не достигается, все те же 8400 операций.
Ну и самое интересное — эффективность алгоритма. Почему следует использовать этот алгоритм? Насколько эффективно он позволяет найти дубликаты? Какова вычислительная сложность? Насколько критично количество сравниваемых документов? И т.д.
Почему 84 хэша? Для реализации алгоритмов, базирующихся на показанном? Странно, причинно-следственная связь не в ту сторону :)
Почему 10 слов в шингле?
Как уже упоминали выше, увеличения производительности путем выбора минимальных значений не достигается, все те же 8400 операций.
Ну и самое интересное — эффективность алгоритма. Почему следует использовать этот алгоритм? Насколько эффективно он позволяет найти дубликаты? Какова вычислительная сложность? Насколько критично количество сравниваемых документов? И т.д.
Ой-ой, по моему вы что-то сильно путаете. Судя по всему, вы пытаетесь рассказать алгоритм, предложенный 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 и там по ссылкам.
И, кстати, при вычислении индекса жаккрада сложность не экспоненциальная, а полиномиальная (хотя это тоже плохо на больших коллекциях) :)
Прочитайте оригинал Broder et al, Syntactic Clustering of the Web, 1997 и еще статья 1993 про полиномы Рабина и сравните с тем, что вы написали. А по поводу мистических цифр — Broder et al, Min-Wise Independent Permutations 2000 и там по ссылкам.
И, кстати, при вычислении индекса жаккрада сложность не экспоненциальная, а полиномиальная (хотя это тоже плохо на больших коллекциях) :)
с нетерпением буду ждать выхода четвёртой статьи — про аццких шинглов :)))))))
а ничего что контрольные суммы шинглов не гарантируют совпадение самих шинглов? :)
видимо ничего :)
Совпадение контрольных сумм шинглов гарантирует совпадение самих шинглов.
Конечно при отсутствии коллизий хеш-функций.
а кто гарантирует отсутствие коллизий? :) вообщето это ни один хэш алгоритм не гарантирует :) гарантируют только сложность подбора коллизии и большую разницу в хэшах при малом изменении исходных данных :)
вообще в принципе отношение N:M где N>M всегда будет иметь коллизии :)
вообще в принципе отношение N:M где N>M всегда будет иметь коллизии :)
Вероятность в данном случае крайне низка и никакой угрозы не несет.
где математическое доказательство этой низкой вероятности? :)
кроме всего прочего описанный в статье метод рушится после простой перестановки сущствительных в предложении :)
кроме всего прочего описанный в статье метод рушится после простой перестановки сущствительных в предложении :)
Зачем нам математическое доказательство на данном этапе? Теорию алгоритма я разъяснил, думаю для заинтересованных этого будет достаточно.
Смотря что понимать под «простой», равнозначно можно сказать, что перестановка существительных в предложении делает статью не дубликатом, а уникальной, определите границы, пожалуйста.
Смотря что понимать под «простой», равнозначно можно сказать, что перестановка существительных в предложении делает статью не дубликатом, а уникальной, определите границы, пожалуйста.
то есть вы изначально опираетесь на необснованные выкладки и считаете что они будут работать?
если вас интересует дубликат то зачем столько накладываемых фильтров? :) определите рамки пожалуйста :)
если вас интересует дубликат то зачем столько накладываемых фильтров? :) определите рамки пожалуйста :)
Я изначально опираюсь на труд Зеленкова Ю. Г. и Сегаловича И.В., ссылку на который представил в статье. Повторяюсь, для разъяснения теории считаю этого достаточным.
Данные «выкладки» работают очень успешно в несколько упрощенном варианте, проверено лично мной и несколькими пользователями моей программы. Об их не успешности мне ничего не известно *PARDON*
Что значит «если вас интересует дубликат »? Меня интересует не дубликат, а проверка на почти-дубликат, это во первых. Во вторых какие рамки нужно определить? Каждый сам для себя определит, что считать дубликатом, а что нет. Выражайтесь конкретнее.
Данные «выкладки» работают очень успешно в несколько упрощенном варианте, проверено лично мной и несколькими пользователями моей программы. Об их не успешности мне ничего не известно *PARDON*
Что значит «если вас интересует дубликат »? Меня интересует не дубликат, а проверка на почти-дубликат, это во первых. Во вторых какие рамки нужно определить? Каждый сам для себя определит, что считать дубликатом, а что нет. Выражайтесь конкретнее.
у Зеленкова с Сегаловичем тоже обоснования как я понимаю нет
боюсь что данные выкладки являются «тыканием пальцем в небо». С точки зрения банальной логики сравнение опосредованных сумм, гораздо хуже чем простое сравнение количества ключевых слов и фраз. Такой вес будет точнее показывать тематику документа и позволит обходить простые уловки типа переставления слов или предложений местами.
так чем почти дубликат где два существительных поменяны местами отличается от других «почти дубликатов»? :)
боюсь что данные выкладки являются «тыканием пальцем в небо». С точки зрения банальной логики сравнение опосредованных сумм, гораздо хуже чем простое сравнение количества ключевых слов и фраз. Такой вес будет точнее показывать тематику документа и позволит обходить простые уловки типа переставления слов или предложений местами.
так чем почти дубликат где два существительных поменяны местами отличается от других «почти дубликатов»? :)
Мне так и не понятно, какие рамки вы просили определить, пожалуйста, поясните.
Обоснований чего? Они не обсуждали криптостойкости алгоритмов расчета контрольных сумм, а предложили решения задачи, упомянув о том, что коллизии хэш-кодов имеют место быть. А так же представили результаты экспериментов.
Каждый имеет право на собственное мнение :)
По вашему сравниваются слова/фразы в явном виде, а не их контрольные суммы, алгоритмы расчета которых содержат вероятность возникновения коллизий?
Данный подход называется «Методом описательных слов», насколько мне известно и вполне может быть использован для решения конкретных задач.
Для веб-документов подобная подмена неприменима, перестановка существительных в предложении местами превратит текст в нечитабельный, сайт, на котором он будет размещен вероятно постигнет участь дорвеев.
Существует услуга размножения текстов для SEOшников, где «обмана» поисковых систем для слов и словосочетаний подбирают синонимы, затем производят случайное комбинирование и в результате получают читабельные тексты, готовые к размещению на площадках. Для фильтрации наиболее «уникальных» статей, использование данного алгоритма вполне уместно.
у Зеленкова с Сегаловичем тоже обоснования как я понимаю нет
Обоснований чего? Они не обсуждали криптостойкости алгоритмов расчета контрольных сумм, а предложили решения задачи, упомянув о том, что коллизии хэш-кодов имеют место быть. А так же представили результаты экспериментов.
боюсь что данные выкладки являются «тыканием пальцем в небо»
Каждый имеет право на собственное мнение :)
С точки зрения банальной логики сравнение опосредованных сумм, гораздо хуже чем простое сравнение количества ключевых слов и фраз. Такой вес будет точнее показывать тематику документа и позволит обходить простые уловки типа переставления слов или предложений местами.
По вашему сравниваются слова/фразы в явном виде, а не их контрольные суммы, алгоритмы расчета которых содержат вероятность возникновения коллизий?
Данный подход называется «Методом описательных слов», насколько мне известно и вполне может быть использован для решения конкретных задач.
так чем почти дубликат где два существительных поменяны местами отличается от других «почти дубликатов»? :)
Для веб-документов подобная подмена неприменима, перестановка существительных в предложении местами превратит текст в нечитабельный, сайт, на котором он будет размещен вероятно постигнет участь дорвеев.
Существует услуга размножения текстов для SEOшников, где «обмана» поисковых систем для слов и словосочетаний подбирают синонимы, затем производят случайное комбинирование и в результате получают читабельные тексты, готовые к размещению на площадках. Для фильтрации наиболее «уникальных» статей, использование данного алгоритма вполне уместно.
* где для «обмана»
еще раз повторюсь, равенство хэшсумм не гарантирует вам равенства первоначальных «шинглов». А если еще посмотреть на то как выбираются шинглы, то понятно что даже равенство шинглов не гарантирует идентичность статей (язык это не просто набор слов, это еще и знаки препинания и артикли с предлогами и тп). Отсюда берем «вероянтное, но не обязательное» условие A умножаем его на такоеже условие B, получаем еще менее вероятно и менее обязательное условие C. Хорошо что гугл такой «математикой» не занимается…
Опять опрометчивые заявления. Пожалуйста вот вам простой текст который от смены мест существительных ни в чем не меняется по смыслу:
Сергей Иванович Перепелкин купил на днях новую продукцию фирмы филипс кофемолку свомещенную с блендером совершенно новой модели «Колибри» которая зарекомендовала себя на рынке как отличный продукт.
На днях купил Перепелкин Сергей Иванович новую блендер, продукцию филипс, совмещенный с кофемолкой, которая зарекомендовала себя на рынке как отличный продукт новой модели «Колибри»
Следуя описанному алгоритму эти тексты совсем различны. Хотя простой взвес слов и их отношений покажет что они идентичны.
Опять опрометчивые заявления. Пожалуйста вот вам простой текст который от смены мест существительных ни в чем не меняется по смыслу:
Сергей Иванович Перепелкин купил на днях новую продукцию фирмы филипс кофемолку свомещенную с блендером совершенно новой модели «Колибри» которая зарекомендовала себя на рынке как отличный продукт.
На днях купил Перепелкин Сергей Иванович новую блендер, продукцию филипс, совмещенный с кофемолкой, которая зарекомендовала себя на рынке как отличный продукт новой модели «Колибри»
Следуя описанному алгоритму эти тексты совсем различны. Хотя простой взвес слов и их отношений покажет что они идентичны.
опять же если нужно простое сравнение, то смысла вычислять все эти суммы нет никакого.
Про хэш суммы понятно, я еще в самом начале дискуссии это указал.
На этапе канонизации текста, он очищается от лишнего, что не предназначено для сравнения и может повлиять на значения контрольных сумм.
Так я и не утверждал идеальность данного алгоритма.
Я сообщаю факт: статьи, отфильтрованные моей самописной, более легкой версией данного алгоритма очень хорошо кушаются как гуглом, так и яндексом и висят в индексе уже более года :) О чем это говорит? Наверное о возможности каждого алгоритма работать с погрешностями.
Но давайте вспомним, все началось с коллизий хэш-алгоритмов. Собственно вопрос: вы считаете, что даже в приведенном вами методе описательных слов, фразы сравниваются в явном виде, а не их контрольные суммы?
На этапе канонизации текста, он очищается от лишнего, что не предназначено для сравнения и может повлиять на значения контрольных сумм.
Так я и не утверждал идеальность данного алгоритма.
Я сообщаю факт: статьи, отфильтрованные моей самописной, более легкой версией данного алгоритма очень хорошо кушаются как гуглом, так и яндексом и висят в индексе уже более года :) О чем это говорит? Наверное о возможности каждого алгоритма работать с погрешностями.
Но давайте вспомним, все началось с коллизий хэш-алгоритмов. Собственно вопрос: вы считаете, что даже в приведенном вами методе описательных слов, фразы сравниваются в явном виде, а не их контрольные суммы?
То что алгоритм в частном случае работает, не значит что он работает в общем случае (опять же хэши и вырезание «лишнего»)
я считаю что для сравнения которое удовлетворяет вашим потребоностям не нужна лишняя работа, тем более такая, не имеющая обоснования.
я считаю что для сравнения которое удовлетворяет вашим потребоностям не нужна лишняя работа, тем более такая, не имеющая обоснования.
Успешность алгоритма характеризует его возможность решать конкретные задачи.
Для меня частный случай определяет задача, с которой облегченная версия алгоритма успешно справляется.
Обоснование использования контрольных сумм: быстрота сравнения, легковестность хранения в БД (значительная между прочим).
Сравнивая вы 2 текста без использования хэш функций, возможно значительную разницу вы и не почувствуете. При пакетной обработке текстов использование контрольных сумм значительно(!) ускорит процесс.
Для меня частный случай определяет задача, с которой облегченная версия алгоритма успешно справляется.
Обоснование использования контрольных сумм: быстрота сравнения, легковестность хранения в БД (значительная между прочим).
Сравнивая вы 2 текста без использования хэш функций, возможно значительную разницу вы и не почувствуете. При пакетной обработке текстов использование контрольных сумм значительно(!) ускорит процесс.
Спасибо за статью, только уж очень запутано, много незнакомых слов и нет практических примеров.
Сразу говорю я плохой математик, может свяязано с этим, может с чем то еще, но делаю так:
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. После выясиления. если считаю документ оригинальным переношу его шинглы в постоянную таблицу, если документ признается дубликатом — его шинглы удаляются и в дальнейшем с ним уже ничего не сравнивается.
Вот примерно так, буду рад критике и предложениям. Надеюсь кому то это поможет понять.
Сразу говорю я плохой математик, может свяязано с этим, может с чем то еще, но делаю так:
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. После выясиления. если считаю документ оригинальным переношу его шинглы в постоянную таблицу, если документ признается дубликатом — его шинглы удаляются и в дальнейшем с ним уже ничего не сравнивается.
Вот примерно так, буду рад критике и предложениям. Надеюсь кому то это поможет понять.
вроде бы вы смотрите только одинаковые шинглы, но не учитываете количество разных. хз, хорошо это или плохо, зависит от задачи. сформулируйте, условно на пальцах, что для вас похожие документы, т.к. это сильно влияет на алгоритмы. т.е. если вы ищите, к примеру, плагиат — это одно, а если новости об одном и том же, то несколько другое, от этого у будет зависеть мера.
а в пункте 9 вы пытаетесь делать кластеризацию, но, например, если A похоже на B, B похоже на C, но A не похоже на C, то A с С у вас не стростется. тоже от задачи зависит, хорошо это или плохо.
в общем, не понятно, какую задачу решает ваш алгоритм :)
а в пункте 9 вы пытаетесь делать кластеризацию, но, например, если A похоже на B, B похоже на C, но A не похоже на C, то A с С у вас не стростется. тоже от задачи зависит, хорошо это или плохо.
в общем, не понятно, какую задачу решает ваш алгоритм :)
Я ищу дубликаты новостей. Если А похож на Б, Б похож на С, но А не похож на С то А и С останутся, и это рпвильно. Например А это какая то новость, а С это более полный обзор этой новости, так пусть он останется. А если Б отличается от А парой слов, тотакое нам не надо, вот Б и будет удален. Так оно и надо, это нормально.
Редко кто SEO, как наукой занимается — ТС молодец, конечно.
мораль примерно проста — достаточно переставить два слова местами, чтобы текст стал уникальным.
Интересная статья для размышления при использовании и разработке синонимайзеров )
Интересная статья для размышления при использовании и разработке синонимайзеров )
Пара замечаний/вопросов:
1. Если быть точным, то описанный вами алгоритм просто цитируется в статье Зеленкова и Сегаловича. Оригинальное описание алгоритма дано в статье Fetterly, Manasse, Najork. A Large-Scale Study of the Evolution of Web Pages.
2. В оригинальном алгоритме для расчета дактилограмм («pre-images») используется алгоритм Карпа-Рабина. С какой целью вы заменили его на crc32, md5 и т.д.?
3. Проводили ли числовую оценку своей реализации? В статье Зеленкова и Сегаловича говорится, что их первоначальная реализация алгоритма давала полноту равную 0.0, и поэтому в действительности там вместо 84-х функций использовалось 36. Соответственно, возникают сомнения в том, что ваша реализация алгоритма может дать приемлемое качество.
1. Если быть точным, то описанный вами алгоритм просто цитируется в статье Зеленкова и Сегаловича. Оригинальное описание алгоритма дано в статье Fetterly, Manasse, Najork. A Large-Scale Study of the Evolution of Web Pages.
2. В оригинальном алгоритме для расчета дактилограмм («pre-images») используется алгоритм Карпа-Рабина. С какой целью вы заменили его на crc32, md5 и т.д.?
3. Проводили ли числовую оценку своей реализации? В статье Зеленкова и Сегаловича говорится, что их первоначальная реализация алгоритма давала полноту равную 0.0, и поэтому в действительности там вместо 84-х функций использовалось 36. Соответственно, возникают сомнения в том, что ваша реализация алгоритма может дать приемлемое качество.
Прошу прощения, стоит ли ждать статью про супершинглы?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Поиск нечетких дубликатов. Алгоритм шинглов для веб-документов