Согласен. Вопрос не легко понять.
Вот в этом то все и дело!
Надо правильно выбирать кратность Если вы возмете 10 и 15 - естественно они не совпадут. Но если например 10, 20 и 40 - очень даже.
Просто сравнивая 1-ый ранг (шинглы кратны 10) с 3-им (шинглы кратны 40), из первого для сравнения выбираем только кратные 40-ка. Понимаете?
Каждый десятый имел ввиду конечно кратный 10. Не имеет никакого значения какую кратность выбрать (естественно при этом нужно исходить из удовлетворительного соотношения "качество"-"количество шинглов (быстрота обработки)").
Тут есть небольшая тонкость. Сравнивая документы одного ранга (документы распределены по рангам в зависимости от объема) мы будем иметь ровно тоже что имели бы взяв шинглы кратные какому то числу для этого ранга, как если бы документов других рангов небыло (надеюсь не слишком сумбурно все излагаю).
Вопрос в том, как сравнивать документы разных рангов, ведь если кратность шинглов будет для них различна (как я и предлагаю), то сравнимы они будут только при условии кратности этих кратностей (5, 10, 20 или 15, 30, 60), то есть так, чтобы кратность для меньшего по значению ранга была кратна кратности большего.
Таким образом сравнивая например страницы 1-го и 2-го ранга (страницы 1-го ранга от 0 до 99 слов, 2-го от 100 до 999) мы будем выбирать из шинглов (первой страницы) только шинглы кратные 20 (при условии что кратность по рангам распределена так: 10, 20, 40), сокращая таким образом сравниваемые шинглы документа 1-го ранга приблизительно в 2 раза. Но это помогает нам "унифицировать" шинглы, хотя и за счет небольшой потери в качестве.
1. Число всех шинглов для данного документа будет n-1 (где n-размерность шингла. в нашем случае 10)
2. Короткие документы размножать нет смысла. Лучше либо зациклить получение шинглов (то есть текст-кольцо) либо уменьшать кратность выбираемых шинглов, так, чтобы они были "совместимы" с шинглами больших документов (например для текста, где количество слов от 0 до 99 выбираем каждый 10 шингл, 100-999, каждый 20-й, больше 1000 каждый 40-й. Таким образом шинглы из коротких документов буду сравними с шинглами из длинных и можно определить степень включенности меньшего в большее, хотя и с большей погрешность чем документы одних рангов).
"Страницы с одинаковой контрольной суммой проверяются методом шинглов на похожесть."
Вот это странное решение. Зачем? Ведь одинаковые контрольные суммы говорят что документы абсолютно похожи (с точностью до знака).
Вообще не обязательно проверять все шинглы (так действительно никаких мощностей не хватит). Но так как распределение контрольных сумм (хешей шинглов) равномерное, то мы можем использовать значения шинглов кратных какому-нибудь числу (10-30). Критерий выборки, в данном случае, получается не привязанным к особенностям текста, так как значения контрольных сумм для разных документов распределены равномерно. И получается что количество сравниваемых шинглов приблизительно равно 1/10-1/30 от общего объема текста (если мерять его в словах). Хотя в принципе думаю Вы это и так прекрасно знаете.
А откуда известно о характере распределения? Имею ввиду, все знают что распределение не подчиняется нормальному закону распределения (надеюсь я правильно понял термин равновероятное), но никто не говорит на чем основано подобное заключение и откуда взялась цифра 0.002.
В принципе, не такая большая проблема выяснить все самому, но не очень хочется (если говорить честно) разбирать алгоритм по косточкам, только для того, чтобы посчитать вероятность (хотя, если не найду выкладок, все же скорее всего придется).
"Существует обширная литература по алгоритмам вычисления контрольных сумм, я упомяну здесь самые известные: fnv, md5, crc. Обычно более-менее все равно, какой из них выбрать, но в любом случае при выборе алгоритма его положительной стороной можно считать хорошее быстродействие."
Вот здесь.
Хотя может быть он лукавит.
Дело в том, что работаю в Фоксе, а там уже есть готовая функция на базе CRC32. Вся проблема в вероятности. Быть может как раз в моем случае она будет вполне приемлема.
Поймите меня правильно, самому расчитать вероятность не большая проблема. Проблема понять алгоритм CRC32, для того чтобы эту вероятность расчитать.
Насчет постановки задачи. Пытаюсь чистить выборку и удалять дублирующую информацию (точнее дубликаты и почти-дубликаты), с помощью шинглов. Соответственно, здесь и необходимо хэширование.
