Хэширование слов

Ken,

Ну, если хотите конкретику - ни одна из хэш-функций, о которых я читала или реализовывала, не дает мне полной гарантии, что все и ВСЕГДА будет правильно. От этого мой уровень уверенности в себе падает. :)

Вывод: нужно искать компромиссы или придумывать свой вариант хэша(что тоже есть компромисс). ИМХО. :)

p.s.Скатываемся к флейму. Похоже, тема себя исчерпала.

Если среднее число слипаний 5, то алгоритм в ~5 раз медленнее если 2 то в ~2 раза медленнее. Не так уж и страшны коллизии.

Вот часть функции MD5, о которой шла речь

Round1(A, B, C, D, Data[ 0] + LongInt($d76aa478), 7);

Round1(D, A, B, C, Data[ 1] + LongInt($e8c7b756), 12);

Round1(C, D, A, B, Data[ 2] + LongInt($242070db), 17);

Round1(B, C, D, A, Data[ 3] + LongInt($c1bdceee), 22);

Round1(A, B, C, D, Data[ 4] + LongInt($f57c0faf), 7);

Round1(D, A, B, C, Data[ 5] + LongInt($4787c62a), 12);

Round1(C, D, A, B, Data[ 6] + LongInt($a8304613), 17);

Round1(B, C, D, A, Data[ 7] + LongInt($fd469501), 22);

Round1(A, B, C, D, Data[ 8] + LongInt($698098d8), 7);

Round1(D, A, B, C, Data[ 9] + LongInt($8b44f7af), 12);

Round1(C, D, A, B, Data[10] + LongInt($ffff5bb1), 17);

Round1(B, C, D, A, Data[11] + LongInt($895cd7be), 22);

Round1(A, B, C, D, Data[12] + LongInt($6b901122), 7);

Round1(D, A, B, C, Data[13] + LongInt($fd987193), 12);

Round1(C, D, A, B, Data[14] + LongInt($a679438e), 17);

Round1(B, C, D, A, Data[15] + LongInt($49b40821), 22);

Round2(A, B, C, D, Data[ 1] + LongInt($f61e2562), 5);

Round2(D, A, B, C, Data[ 6] + LongInt($c040b340), 9);

Round2(C, D, A, B, Data[11] + LongInt($265e5a51), 14);

Round2(B, C, D, A, Data[ 0] + LongInt($e9b6c7aa), 20);

Round2(A, B, C, D, Data[ 5] + LongInt($d62f105d), 5);

Round2(D, A, B, C, Data[10] + LongInt($02441453), 9);

Round2(C, D, A, B, Data[15] + LongInt($d8a1e681), 14);

Round2(B, C, D, A, Data[ 4] + LongInt($e7d3fbc8), 20);

Round2(A, B, C, D, Data[ 9] + LongInt($21e1cde6), 5);

Round2(D, A, B, C, Data[14] + LongInt($c33707d6), 9);

Round2(C, D, A, B, Data[ 3] + LongInt($f4d50d87), 14);

Round2(B, C, D, A, Data[ 8] + LongInt($455a14ed), 20);

Round2(A, B, C, D, Data[13] + LongInt($a9e3e905), 5);

Round2(D, A, B, C, Data[ 2] + LongInt($fcefa3f8), 9);

Round2(C, D, A, B, Data[ 7] + LongInt($676f02d9), 14);

Round2(B, C, D, A, Data[12] + LongInt($8d2a4c8a), 20);

Round3(A, B, C, D, Data[ 5] + LongInt($fffa3942), 4);

Round3(D, A, B, C, Data[ 8] + LongInt($8771f681), 11);

Round3(C, D, A, B, Data[11] + LongInt($6d9d6122), 16);

Round3(B, C, D, A, Data[14] + LongInt($fde5380c), 23);

Round3(A, B, C, D, Data[ 1] + LongInt($a4beea44), 4);

Round3(D, A, B, C, Data[ 4] + LongInt($4bdecfa9), 11);

Round3(C, D, A, B, Data[ 7] + LongInt($f6bb4b60), 16);

Round3(B, C, D, A, Data[10] + LongInt($bebfbc70), 23);

Round3(A, B, C, D, Data[13] + LongInt($289b7ec6), 4);

Round3(D, A, B, C, Data[ 0] + LongInt($eaa127fa), 11);

Round3(C, D, A, B, Data[ 3] + LongInt($d4ef3085), 16);

Round3(B, C, D, A, Data[ 6] + LongInt($04881d05), 23);

Round3(A, B, C, D, Data[ 9] + LongInt($d9d4d039), 4);

Round3(D, A, B, C, Data[12] + LongInt($e6db99e5), 11);

Round3(C, D, A, B, Data[15] + LongInt($1fa27cf8), 16);

Round3(B, C, D, A, Data[ 2] + LongInt($c4ac5665), 23);

Round4(A, B, C, D, Data[ 0] + LongInt($f4292244), 6);

Round4(D, A, B, C, Data[ 7] + LongInt($432aff97), 10);

Round4(C, D, A, B, Data[14] + LongInt($ab9423a7), 15);

Round4(B, C, D, A, Data[ 5] + LongInt($fc93a039), 21);

Round4(A, B, C, D, Data[12] + LongInt($655b59c3), 6);

Round4(D, A, B, C, Data[ 3] + LongInt($8f0ccc92), 10);

Round4(C, D, A, B, Data[10] + LongInt($ffeff47d), 15);

Round4(B, C, D, A, Data[ 1] + LongInt($85845dd1), 21);

Round4(A, B, C, D, Data[ 8] + LongInt($6fa87e4f), 6);

Round4(D, A, B, C, Data[15] + LongInt($fe2ce6e0), 10);

Round4(C, D, A, B, Data[ 6] + LongInt($a3014314), 15);

Round4(B, C, D, A, Data[13] + LongInt($4e0811a1), 21);

Round4(A, B, C, D, Data[ 4] + LongInt($f7537e82), 6);

Round4(D, A, B, C, Data[11] + LongInt($bd3af235), 10);

Round4(C, D, A, B, Data[ 2] + LongInt($2ad7d2bb), 15);

Round4(B, C, D, A, Data[ 9] + LongInt($eb86d391), 21);

Может есть смысл сделать функцию по проще?

И при этом разрешать N-слипаний?

Ken,

-везде. Слипания хешей = на одно слово у вас будут искаться от 2 до 8 слов. Это не годится никак.

Ken,

-ты первую половину прочитал, прочитай все полностью. Остальное может искаться по менее производительному алгоритму по дереву. Но зато он не чувствителен к разреженности.

Хэш-алгоритм с разрешением коллизий (тем более, с деревом в конце) во многих случаях не проще и не быстрее собственно дерева, и даже простого плоского списка с бинарным поиском.

Мне кажется так:

- для малых объемов словаря - плоский список;

- для средних объемов - тот же список с хэшем (когда бинарный поиск становится менее эффективным);

- для больших объемов - дерево.

AlexA, а если для словаря русского языка - это в какую группу попадает?

Малый объем - где-то до 10 тыс. слов.

Средний объем - до нескольких сот тысяч слов.

Что до классического русского языка (например, словаря Зализняка), здесь зависит от того, сводим словоформы или нет.

AlexA,

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

Действительно, зачем все это городить? Если Вы уточните задачу то возможно еще идеи появятся.

Artisan,

На первых страницах треда объяснялось зачем - чтоб при индексации не дергать какие-нибудь БД для сопоставления слову(словоформе) уникальный идентификатор. Получается гораздо быстрее, если у нас есть какая-нибудь спец-функция.

Что же до количества слов, то реально выходит, что в словаре будет храниться около 500 тыс. записей (несловарные слова, английские и русские).