Как определяется уникальность текста методом шингл?

Это читали?

Читал. Но, как говорится, каждое слово понятно, а что хотели сказать - нет.

Вот это:

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

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

Что конкретно мы делаем?

Для КАЖДОГО шингла первого текста посредством 84 функций рассчитываем 84 значения контрольной суммы.

И для второго текста аналогичным образом рассчитываем 84 значения контрольной суммы.

Так?

Вы начали с усложненного метода шинглов. Приведенная статья - она больше описывает метод повышения качества этого алгоритма, чем сам алгоритм.

Начните с более простой статьи этого же автора. Не забудьте прочитать комментарии :)

Спасибо, теперь дело прояснилось!

Смысл алгоритма такой текст разбивается на куски по 10 слов. Если у двух текстов определенный процент совпадений этих кусков, то тексты считаются копиями.

Остальное все тонкости, например, что что шинглы взахлест считаются или Хеш.

Hkey добавил 03.10.2009 в 00:00

Статья не понравилась. Полный бред, как будто яндекс ресурсы своих машин не бережет. Один символ у него входит в 84 * 10 контрольных сумм )))

Каждое слово от 10го до N-10 входит 10 шинглов, следовательно, если считать 84 строковых чексумма каждый символ будет входить в 840 чексумм. А, например для CRC, один чек сумм это 20 операций. Символов в тексте пару тысяч. 16 миллионов операций на тысячу символов это круто)))) Я понял почему сайты так долго не индексируются)))

Канонизация текста!!!??? Нафиг нужно, в 500-600 раз быстрее попытаться найти слово в базе, если нет посчитать его чексумм, не обрезая и не канонизируя. Отброс прилагательных сомнителен. Минимум 2% прилагательных в тексте будут иметь омонемию с существительными.

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

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

Откуда число 84? У яши в статьях 85.

----------------------------------------------------------------------------

Моя версия:

Считается для каждого слова чексумм (номер его в словарной базе или чемсумм его как строки) ибо нефиг по 640 раз рассчитывать сумму одного символа. Причем, чем слово более редкое, тем больше номер его в базе.

Берем 85 многочленов первой степени от десяти переменных. a1* X1+ a2* X2 + ... +a10* X10 абсолютно случайных, но так чтобы a>0 и чтобы матрица этих коэффициентов имела ранг 85. Находим их максимумы так, чтобы в них не попадали несколько раз (ну если текст маленький, то можно и несколько раз) одни и теже шинглы. Поскольку слова в базе упорядочены по редкости, то вероятность, что "выстрелит" шингл с редким словом выше.

Считаем хеш этих шингов (хеш сложнее чем случайная функция и выполняется дольше) и сравниваем по хешам этих 85 функций.

Hkey

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

ПС. Как у матрицы 85*10 нашли ранг = 85? :)

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

Очень различные результаты работы разных программ!

Сравниваю две пары тестовых созданных вручную клонов. В одной паре тексты достаточно близки, в другой более уникальны. Сервис http://www.wsgu.ru/servis/copy.php дает 57% и 2% неуникальности. ShinglesExpert дает 52% и 3%. Программа ShExpertPro дает 17% и 15 процентов.

И непонятно, кому верить...

Разная длина шинглов это раз.

Учет стоп слов и знаков препинания разный это два.

Разное понятие об уникальности процент уникальных шинглов против процента уникального текста это три.

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

Еще могут быть у разработчиков всякие ухищрения, например в 1.5 раза завысить процент, чтобы программа показалась более "умной". Я никого не хочу обидеть, просто предполагаю такой возможности.

Погрешность (доверительный интервал) при выборке 85 шинглов с надежностью 0,90 будет 2%. Т.е. 90% случаев погрешность не превышает двух процентов.

Важность этого параметра я прекрасно понимаю! Поэтому приведенные мною цифры относятся к шинглам одной длины.