Признаки похожести

Чего-то я сегодня туплю :)

Правильно ли я понял, что вы предлагаете для документа (например, 200 слов) делать 20 хешей и потом сравнивать по ним?

Нет, не 20 хешей, а 191 (Для слов 1-10, 2-11, 3-12 и т. д.) Дальше все полученные хеши складываются в одну огромную таблицу. При обработке нового документа - берем его хеши, и выбираем из таблицы документы, в которых такие же встречаются. И уже с этими документами сравниваем обрабатываемый. Объем данных конечно немеряный, так что если в лоб так делать не хватает ресурсов, то надо искать способы что-то выкинуть.

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

1. Число всех шинглов для данного документа будет n-1 (где n-размерность шингла. в нашем случае 10)

2. Короткие документы размножать нет смысла. Лучше либо зациклить получение шинглов (то есть текст-кольцо) либо уменьшать кратность выбираемых шинглов, так, чтобы они были "совместимы" с шинглами больших документов (например для текста, где количество слов от 0 до 99 выбираем каждый 10 шингл, 100-999, каждый 20-й, больше 1000 каждый 40-й. Таким образом шинглы из коротких документов буду сравними с шинглами из длинных и можно определить степень включенности меньшего в большее, хотя и с большей погрешность чем документы одних рангов).

"Страницы с одинаковой контрольной суммой проверяются методом шинглов на похожесть."

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

Действительно так проще.

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

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

Вопрос в том, как сравнивать документы разных рангов, ведь если кратность шинглов будет для них различна (как я и предлагаю), то сравнимы они будут только при условии кратности этих кратностей (5, 10, 20 или 15, 30, 60), то есть так, чтобы кратность для меньшего по значению ранга была кратна кратности большего.

Таким образом сравнивая например страницы 1-го и 2-го ранга (страницы 1-го ранга от 0 до 99 слов, 2-го от 100 до 999) мы будем выбирать из шинглов (первой страницы) только шинглы кратные 20 (при условии что кратность по рангам распределена так: 10, 20, 40), сокращая таким образом сравниваемые шинглы документа 1-го ранга приблизительно в 2 раза. Но это помогает нам "унифицировать" шинглы, хотя и за счет небольшой потери в качестве.

Rusl, а что с чем вы сравниваете? Ведь если у документа №1 взять каждый 10-й шингл, и у документа №1копия взять каждый 10-й, и эти документы будут отличаться одним словом (вставленным в начало документа №1), то дубль не выловится. А если брать только шинглы, значение которых кратно 8 или 16 - то прекрасно выловится.

Каждый десятый имел ввиду конечно кратный 10. Не имеет никакого значения какую кратность выбрать (естественно при этом нужно исходить из удовлетворительного соотношения "качество"-"количество шинглов (быстрота обработки)").

Думаю будут погрешности на "границах рангов", поясню на примере:

Имеем ранги:

1-й ранг от 0 до 99 слов, отбираются шинглы с кратные (по значению) 10

2-й ранг от 100 до 150 слов, отбираются шинглы кратные 15

Имеем два документа с отличием в одно слово:

1-й документ содержит 99 слов (1-й ранг)

2-й документ содержит 100 слов (2-й ранг)

В результате для 1-го документа отберутся шинглы кратные 10, для 2-го кратные 15. Получается шинглы не совпадут.

Вот в этом то все и дело!

Надо правильно выбирать кратность Если вы возмете 10 и 15 - естественно они не совпадут. Но если например 10, 20 и 40 - очень даже.

Просто сравнивая 1-ый ранг (шинглы кратны 10) с 3-им (шинглы кратны 40), из первого для сравнения выбираем только кратные 40-ка. Понимаете?