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

euhenio, Долго... и лениво-лениво... 😆

Я, понимаешь, хотела, чтобы все и сразу :)

Сколько коллизий не считал, потому что сразу было ясно 100.000 слов в 65.535 позиций не влезут.

При выборе хэш-функции поступили просто - подобрали методом "научного" перебора. Получили MAX 8 слипаний на одну коллизию и успокоились - для 100 тысяч - норма. Правда при этом пришлось добавить процедуру сравнения входного слова со словарным и сам процесс разрешения коллизий. При всем при этом рассеивающая функция базировалась на отработки номеров н-грамм (те же слоги) из которых состояло слово.

На несловарных словоформах, аббревиатурах и.т.п получается чуть хуже, разобраться, что там на что влияет - это вопрос к математикам.

На больших объемах тестировать не стали - положили, что проще сделать 10 емкостей по 100 тысяч, чем делать все это 64 битным или 32 битным ключем т.к. по расчетам памяти при этом тратится несоизмеримо больше.

Joy,

Это должно что-то означать? Если да, то, что?

Не смешивайте в кучу профессию и развлечения. Вас не поймут.

И причем тут кошка в церкви? По-моему, вопрос вполне уместен для темы. Мне нравится получать уместные ответы от умных людей...

Ken, первым в стоял вопрос - сколько вообще коллизий на весь список? Вы не ответили.

Если вы запихнули 100 тыс. слов в 65 тыс., то плевать на максимальное число коллизий. Но каждое второе слово будет слипаться с каждым третьим. Такому "научному" алгоритму место в помойке, имхо.

PS Это без учета словоформ.

Нет, 16 бит (65 536) не подойдут, конечно!

Вообще, кажется, для вычисления id-шника придется придумывать, как предлагал выше euhenio, какой-нибудь смешанный алгоритм...

Это надо придумывать.

Ясно☝

Пасиба

Ок. Допустим, таблица состовит из одних коллизий и все они имеют 8 слипаний остальные 53тыс. ячеек пусты?

Или, допустим, все что вся таблица с коллизиями т.е. где-то 2 слипания на каждое значение?

Ну и где тут помойка?

Я и не старался быть понятным. А по теме можно вспомнить о том что великий Кнут явно пишет о непригодности чистого хэширования для серьезных задач потому что у этого способа индексации очень плохая производительность в наихудшем случае. Возможно что то что предлагает euhenio по поводу дополнения хэширования деревом будет оптимальным решением. Только я бы хэшировал не часть слова а все слово полностью чем нибудь типа md5 для лучшего распределения при этом не обращая внимания на совпадения и брал бы столько бит что их бы хватило на хэширование без совпадений при идеальном случае то есть дерево было бы только страховкой для наихудшего случая при совпадениях.

Вот немного по теме - хранение лексикона в сжатом виде:

http://www-db.stanford.edu/cs347.2001.spring/handouts/lecture2-4in1.pdf

Artisan,

Что ж, вы цели достигли :)

Склоняюсь к тому, что при желании и при необходимости нужно придумывать свой алгоритм хэширования (или просто поиска id-шника для слова), основываясь на какой-нибудь статической древовидной структуре с возможностью расширения дерева и исключения отношения "все-ко-всем" (проектировщики БД меня прибьют за вольности с терминологией), то есть прямого перечета всех символов алфавита. Возможен подход со слогами... не знаю. :)

То есть, придется взять хороший словарь, и...

Спасибо всем, интересное обсуждение.

Скажи человеку что на небе 8 567 122 433 звезды - он верит.

Скажи, что надо хэшировать выделенным N символам - то же верят (хотя это читая гипотеза).

А вот когда пишешь, что можно пытаться подобрать функцию - отвечают ИХМО....

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