| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Алгоритм CheckSum функции для текстового документа |
| Автор: sandland 27.11.2010, 02:58 |
| Добрый день. Ищу совет по созданию checkSum ф-ции. Задача такая: имеется множество M документов, ||M||= N >10^7. Необходимо каждому документу m из M сопоставить некоторую 64-битную последовательность симовлов {a-Z,0-9}, удовлетворяющую определенным критериям. Введеем дополнительные определения: A. Определение: При заданных положительных k и последовательноти терминов в документе d, будем называть k-шинглами документа d множество всех неприрывных последовательностей, состоящих из k терминов документа. Пример: a rose is a rose is a rose. При k=4 поулчаем 4 шингла: 1.a rose is a 2.rose is a rose 3.a rose is a 4.is a rose is 1 и 3 шинглы совпадают. Б. Расстояние d(a,b) между документами a и b. Рассятоние определяется через коэффициент Жаккера. Пусть S1- множество шинглов для документа a, S2 - соответственно для b d(a,b)= |S1 OR S2| / |S1 AND S2| Критерии CheckSum-фции. 1. Бинарность отображения, либо крайне малая вероятноть существования на конечном множестве одинаковой CheckSum ф-ции для двух разных документов 2. Нет необходимости в криптостойоксти CheckSum ф-ции. 3. "Вычитая" из ChekSum ф-ции одного документа CheckSum ф-ции другого, мы могли бы дать объективную оценку о расстоянии между данными документами. Для чего это нужно: В определенной задаче, чтобы не считать расятоние между документами "в лоб", хотелось бы ускорить алгоритм, вычитая разность между 64-битными последовательностями. Задача сложная. Существует ли ее "хорошее" решение - вопрос. Если решения не существует - требуется это доказать. Если есть идеи или советы как решить данную задачу, буду благодарен. |