Хэширование данных

[WebByte]

Хэширование данных

Ищется алгоритм, отвечающий следующим требованиям.

1. Устойчивость к коллизиям. Для 1 млн строк коллизий быть не должно.
2. Результат алгоритма - хэш, длиной не более 10-12 символов

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

md5 слишком уж длинный, crypt покороче, но все равно длина не подходит. crc32 выдал 6% коллизий на миллионе строк.

 

[Tor]

md5 слишком уж длинный

и это привод к огромному перерасходу ресурсов?
молодой человек, хватит изобретать велосипед, их и так у нас есть

 

[WMix]

воспользуйся мд5 но сохраняй только 12 символов.... бред но прокатит

 

[Tor]

воспользуйся мд5 но сохраняй только 12 символов.... бред но прокатит

ключевое слово третье с конца

 

[WebByte]

и это привод к огромному перерасходу ресурсов

Вроде того. Конечно, +/- 18 мб данных и столько же индекса не смертельны, но хотелось бы по возможности оптимизировать.

воспользуйся мд5 но сохраняй только 12 символов.... бред но прокатит

Оно, конечно, прокатит, но алгоритм, который бы подтвердил, что да, все строки будут разные, писать не хочется.. Как и алгоритм считающий какие номера позиций взять, чтобы получить уникальный хэш

 

[Кром]

>Конечно, +/- 18 мб данных и столько же индекса не смертельны, но хотелось бы по возможности оптимизировать.

А зачем тебе 18 метров хешей?
Мне это напоминает старую байку:
http://nudnik.ru/entry/1154

 

[WebByte]

>А зачем тебе 18 метров хешей?

А их больше будет. 32 байта md5 * 1-2 млн строк = 32-64 Мб данных и индекса столько же (ну сравнительно).

А надо это не мне, а заказчику. Число строк корреллирует с возможными значениями неких датчиков.

 

[Кром]

>Число строк корреллирует с возможными значениями неких датчиков.

"Число строк"? Очень интересно.
Может стоит просто завести отдельную таблицу с одним полем, в которое писать это число строк. Зачем для этого сами строки?

 

[kruglov]

Хэши по определению не гарантируют отсутствия совпадений.
Ибо являются отображением множества в множество меньшей мощности (которое инъективным быть не может никак)

-~{}~ 11.08.05 17:14:

p. s. а для "быстрого поиска" вам не все равно, 1 найдется или (в редких случаях) 2 или даже 3?

Вы промерьте быстродействие-то...

 

[WebByte]

>Зачем для этого сами строки?

Там с пары десятков тысяч датчиков идут сигналы различных видов. Однозначно определить какой сигнал и с какого датчика можно только так - сигнал придет определенным набором байт (бинарных, порядка пары сотен байт длины). Один и тот же сигнал с одного и того же датчика всегда состоит из одной и той же последовательности. Но идентификатора датчика и вида сигнала в последовательности нет. Просто известны пару миллионов этих последовательностей и известно какая за что и где отвечает.
Таблица-то простая по идее:
------------------------------------------
пакет | id_датчика | id_сигнала
------------------------------------------
Но хранить пакет из пары сотен байт не очень хочется, он потому как в итоге не нужен. А хочется хранить его хэш. Которого вполне для дальнейших целей достаточно.

>Хэши по определению не гарантируют отсутствия совпадений.
Знаю, но к примеру md5-хэши для всех моих последовательностей различны. Но вдруг еще короче возможен хэш...

 

[Tor]

Но вдруг еще короче возможен хэш

и кто тебе без данных ответит?
сиди и откусывай по одному символу

 

[Sherman]

вот тут обсуждали сию проблему не так давно, в разрезе морфологии:

http://forum.searchengines.ru/showthread.php?t=16663

 

[Кром]

>сиди и откусывай по одному символу

Нет, откусывать тут ничего нельзя. Иначе результаты будут непредсказуемы.
Лучше все таки остановится на md5().

 

[WebByte]

>Лучше все таки остановится на md5().

Скорее всего так и сделаю.
Единственно, если известно, что все 32-байтные хэши для набора разные, то возникает вопрос - как оптимальнее искать меньшую последовательность...
Ну то есть, имеем в общем случае матрицу 32x2 000 000.
Задача определить какие столбцы надо взять, чтобы определитель полученной матрицы не был равен нулю.

 

[Кром]

>что все 32-байтные хэши для набора разные, то возникает вопрос - как оптимальнее искать меньшую последовательность...
>какие столбцы надо взять, чтобы определитель полученной матрицы не был равен нулю

Поясни, ничего непонятно. Последовательность чего? Почему меньшую? Что значит определитель матрицы?

 

[Tor]

Нет, откусывать тут ничего нельзя

залить эти хеши в поле базы и сделать его уникальным
потом сделать ALTER, сократив длину на один символ
и делать так, пока не ругнется на дублирование записи

 

[WebByte]

Эээ.. Ну это из теории матриц. (Вот уж не думал, что пригодятся спустя столько лет знания за первый курс института).

Под матрицей понимается некая таблица N x M
Каждой матрице сопоставляется некоторое число, которое находится исходя из ее элементов.
Называется определитель, впрочем за точность не поручусь.
Если две строки / два столбца в матрице одинаковы, то это число будет равно нулю.

Так вот, в моем случае коллизия - это и есть совпадение минимум двух строк в матрице размерности меньшей чем 32 x 1-2000000. (32 - md5-хэш. А меньшей потому как известно, что для 32-х коллизий нет).

Ну вот и требуется найти такие номера столбцов матрицы (ну или номера символов в md5-хэше), для которых определитель будет неравен нулю (иными словами, для которых не будет коллизий).

Только это всё, что я из этой самой матричной теории помню

-~{}~ 12.08.05 01:41:

>и делать так, пока не ругнется на дублирование записи

Это хорошо, если меньший хэш находится в диапазоне символов. Например, с 1 по 15. А если хэш возможен только с 1, 3, 5, 7..итп.? Как в базе альтер делать?

В принципе, я сейчас так и делаю, только не с базой, а с массивами строк в памяти... Почти перебором, конечно, получается, но оптимальнее вроде никак

 

[clevel]

хм.. а просто автоинкриментного поля не хватит? мне для словарика с морфологией русского языка на 1,5 млн. слов его хватило...

 

[WebByte]

Хватит. Но смысл не просто, чтобы иметь соответствия, но чтобы объем данных был минимален. А соответственно поиск шел быстрее.

 

[kruglov]

Если у вас 10000 датчиков, каждые 2 из которых вы можете различить по выдаваемой последовательности, то постройте словарь этих датчиков

id (autoincrement) - определяющая последовательность.