Добрый день. Ищу совет по созданию 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-битными последовательностями.
Задача сложная. Существует ли ее "хорошее" решение - вопрос.
Если решения не существует - требуется это доказать.
Если есть идеи или советы как решить данную задачу, буду благодарен.

Это сообщение отредактировал(а) sandland - 27.11.2010, 03:09