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

[WebByte]

Задача не просто сопоставить датчик-сигнал числу, а сделать это сопоставление минимальным по объему. То есть найти нормальную хэш-функцию, чтобы хранить в качестве ключа не всю последовтельность в 200 байт, а несколько меньшую...

Представьте. Я храню в базе в качестве уникального ключа саму последовательность 200 байт. Знаете какой будет индекс для миллиона строк? А догадайтесь какая будет скорость поиска по этому индексу...

 

[Кром]

WebByte
Это все замечательно, только зачем тебе все эти манипуляции с матицами? Или ты все еще горишь желанием сократить размер mysql поля?

>А меньшей потому как известно, что для 32-х коллизий нет
Коллизии есть.

Tor
Это все замечательно. Но если мы создадим такую таблицу, а потом появятся новые датчики, значения и т.д, которые вызовут коллизию. Будем переписывать все значения под изменившийся размер столбца? Опять увеличивать?

По сути толку в этом нет. 30-60 мегов это ничто. Ерунда полная. Из-за этого парится смысла нет вообще.

 

[clevel]

что по размеру может быть меньше чисел? строка по определению больше занимает места..

 

[WebByte]

> Или ты все еще горишь желанием сократить размер mysql поля?

Ага. Мне известно, что для моего набора из пары миллионов строк все их md5-хэши попарно различные.

Более того, мне известно, что даже если взять только первые 11 символов каждого md5-хэша, то эти подстроки тоже все будут различны.. Но мне интересно, а вдруг можно взять 3 символа на каких-то позициях и опять хэши будут разными..

Но тупо перебирать все варианты бессмысленно.
Их 32*31*30/1*2*3 = 4960 (комбинации из N по K).
А на моих объемах данных перелопатить 2Мб * 4960 раз - смерти подобно. Проще уж остановиться на 11 байтах хэша.
Или найти оптимальный алгоритм перебора.

>что по размеру может быть меньше чисел? строка по определению больше занимает места..

Господин clevel. Если Вы мне покажите как 2 миллионам 200-байтных строк однозначно сопоставить числа от 0 до 2 миллионов, храня при этом всего 2 байта хэша на каждую их строк, я Вам даже заплачу пару тысяч баксов )

 

[AnToXa]

Господин clevel. Если Вы мне покажите как 2 миллионам 200-байтных строк однозначно сопоставить числа от 0 до 2 миллионов, храня при этом всего 2 байта хэша на каждую их строк, я Вам даже заплачу пару тысяч баксов )

насколько я понимаю это невозможно сделать однозначно, т.к. 2 байта мало для хранения чисел от 0 до 2M.

а как сопоставить? очевидно: пронумеровать их.

 

[WebByte]

> насколько я понимаю это невозможно сделать однозначно,
> т.к. 2 байта мало для хранения чисел от 0 до 2M

Ну так поэтому я и предложил, что ничего не потеряю

>а как сопоставить? очевидно: пронумеровать их

Ну да.
[200 байт] => 0
[200 байт] => 1
..
[200 байт] => 2 000 000

Только объем хранимых данных составит 200 * 2Мб = 400 Мб.

 

[AnToXa]

аха, а хэш сколько занимает?
ну допустим ваши любимые 10 байт

(200 + 10) * 2Mb = 420M

вы разве не видите, что основной объем занимают ваши 200 байт * 2M ?

если вы мне сейчас скажете, что вы преобразуете эти 200 байт в хэш и будете юзать их, то ответ вот: преобразуйте в 4 байта - которые есть номер в данной последовательности.

а потом вам еще надо и искать этот самый номер в последовательности: очень просто: сделайте хэш md5(16 байт) и сделайте два индекса по двум восьмибайтным половинкам или один по char(16) и ищите номера свои сколько влезет.

промежуточный номер вообще можно выкинуть.

поиск по миллиону записей по индексу занимает очень мало времени если правильно настроить сервер, потому что индекс буддет весь в памяти. размер индекса вас вообще волновать не должен, это копейки.

и вообще, то что вы пытаетесь решать проблему которой нет(как я понял вы подумали что все буддет тормозить не потестировав), называется prepature optimization, что есть the root of all evil.

 

[Мутник]

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

тебе 5 минут жалко ради гениальной задумки?

 

[AnToXa]

кстати, если я ничего не путаю, то определитель определен только для квадратных матриц

 

[WebByte]

>> (200 + 10) * 2Mb = 420M
>> вы разве не видите, что основной объем занимают ваши 200 байт * 2M ?

Неверно, я уже писал выше, что сами 200 байт мне не нужно нигде хранить. Хранить я буду именно 2М*длину_хэша.
Найду хэш длиной 10 байт - буду хранить 20М, найду хэш 3 байта - буду хранить 6М.

>> преобразуйте в 4 байта - которые есть номер в данной последовательности.

Ну так это преобразование и есть та самая хэш-функция, реализацию алгоритма которой я пытаюсь понять.
Найду - сопоставлю строке в 200 байт 4 байта хэша и буду хранить 8 метров данных.

>> размер индекса вас вообще волновать не должен, это копейки
Какие ж это копейки, если их размер сопоставим с данными?
Если ключ уникален, то индекс займет столько же места. (утрирую)


>> как я понял вы подумали что все буддет тормозить не потестировав

Я не столько хочу увеличить скорость, сколько уменьшить объем данных. Млин, неужели никто не программировал под 286-е, когда память приходилось собирать по крохам?

Если бы мне было параллельно, я бы давно забил на эту задачу, реализовал бы 32 байтный хэш и не мучался. Смысл не в том, чтобы получить хэш, а в том, чтобы хэш был минимального размера

-~{}~ 12.08.05 03:00:

>тебе 5 минут жалко ради гениальной задумки?
Да нет. Поэтому и пишу сижу. Уже хэш до 10 байт сократил.
Ищу 9-ти байтный.

>кстати, если я ничего не путаю, то определитель определен только для квадратных матриц

Запросто, я уже не помню. Это и не суть важно, если честно.

 

[AnToXa]

повторяю: md5 дает хэш размером 16 байт, 32 - это у него представление в виде hex-строки.

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

Смысл не в том, чтобы получить хэш, а в том, чтобы хэш был минимального размера

надо было начинать с того что вам нужно уменьшить объем хранимых данных, а не с того, что нужна короткая хэш-функция.

 

[WebByte]

>md5 дает хэш размером 16 байт, 32 - это у него представление в виде hex-строки.

Кажется, параметр, указывающий какую длину возвращать, только в PHP5 появился. Ну да неважно.

>>надо было начинать с того что вам нужно уменьшить объем хранимых данных, а не с того, что нужна короткая хэш-функция.

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

 

[AnToXa]

http://www.faqs.org/rfcs/rfc1321.html - первый абзац, это алгоритм выдает 16 байт, а не пхп магически получает из 32 16 %)

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

да я сам виноват - несколько потерял нить дискуссии

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

 

[WebByte]

> я вот только непойму, а что вы буддете делать, если вдруг у вас все-таки получится коллизия?

Искать другой алгоритм хэширования. Но повторюсь - строки никогда не поменяются. Как было их 2 миллиона, так и будет. И точно известно, что по крайней мере md5 возвращает 2 миллиона различных 16-байтных хэшей

Если я точно буду знать, что коллизия возникнет хотя бы на 15 байтах, я буду хранить 16. Но поскольку опытным путем мне уже известно, что коллизии отсутствуют и при некоторых меньших подстроках, то хочу найти минимальный из возможных хэшей, который лежит в размерности от теоретических трех до практически найденных 11-ти.

 

[Silent]

WebByte, решение твоей задачи давно известно - minimal perfect hashing. В Гугле есть и готовый код. Только если нет возможности использовать сишный код, я бы лучше брал что-нибудь стандартное (тот же md5), пусть он и больше по размерам.

 

[camka]

Автор оригинала: WebByte
Если я точно буду знать, что коллизия возникнет хотя бы на 15 байтах, я буду хранить 16. Но поскольку опытным путем мне уже известно, что коллизии отсутствуют и при некоторых меньших подстроках, то хочу найти минимальный из возможных хэшей, который лежит в размерности от теоретических трех до практически найденных 11-ти.

Товарищ Tor же уже ответил, как найти минимальный хэш. Режь его с конца по одному символу пока mysql не заорет.

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

Да и вообще, если ты изначально знаешь последовательности и они достаточно разнообразны, то есть последовательность байт сильно отличается, тем же способом ты можешь сделать индекс и по префиксу определенной длинны. Длина префикса вычисляется вышеописаным способом.

 

[IntenT]

[удалил]