Снова не могу не согласиться с Вами, Artisan. И распределение CRC неравновероятное, и ключевое слово правильное.
Для начала обычно принимается, что задача обычная и решается обычными известными и очевидными методами, а вот если они не проходят, тогда уже можно пытаться внести модификации в велосипед.
CRC действительно хорош быстродействием, что в методе шинглов (пересекающихся покрытий) совсем не лишнее.
Согласен, можно верить и не верить.
А система ловли дублей, в одной из частей которой применен CRC32, работает у нас уже довольно давно. На базе - около сотни гиг.
Ну не так уж все страшно.
Все это задачи решаемые (и, главное, решенные).
Верно, как и для многих других хэш-функций.
Другое дело, насколько это важно для поставленной задачи, декодирование в нее, кажется, не входило.
Можно также взять CRC32. Число коллизий будет чуть меньше, чем у обрезанного до 4-х байт MD5.
При хэшировании вероятность коллизий в любом случае ненулевая. Для CRC32 ~ 0,002 (Влад Шабанов).
А можно завести словарь (отсортированный список), тогда номер будет определяться абсолютно однозначно.
Малый объем - где-то до 10 тыс. слов.
Средний объем - до нескольких сот тысяч слов.
Что до классического русского языка (например, словаря Зализняка), здесь зависит от того, сводим словоформы или нет.
Хэш-алгоритм с разрешением коллизий (тем более, с деревом в конце) во многих случаях не проще и не быстрее собственно дерева, и даже простого плоского списка с бинарным поиском.
Мне кажется так:
- для малых объемов словаря - плоский список;
- для средних объемов - тот же список с хэшем (когда бинарный поиск становится менее эффективным);
- для больших объемов - дерево.
Смысл? В 16 байт и само слово влезет.
Цитирую Влада Шабанова (да простит автор):
"Для 30 миллионов слов CRC32 дает примерно
тысяч 50 коллизий. Максимальное количество
слипаний в одной коллизии ~ 150."
Оригинал - 404
Для начала прочтите Сегаловича - обзор по большинству вопросов построения поисковой системы. Конкретно по Вашему вопросу попробуйте метод tf*idf.
