На самом деле мне тут подумалось, что это все совсем не напрасные муки. Мы тут все радостно забыли про то, что L1 и L2 кеши на порядок быстрее оперативной памяти. И если написать приложение так, что морфологический разбор протекает "последовательно" то есть скачали миллион документов, выбрали миллион уникальных слов, прогнали морфоанализатор, то выигрыш по скорости может быть довольно-таки приличным. А размеры кешей сейчас как раз в районе 500 кб - 1 мб.
Под префиксным деревом я понимаю дерево, в котором слова с одинаковым префиксом запихиваются в одно поддерево.
Я очень даже хорошо понимаю ситуацию с префиксным деревом. Да Вы совершенно правы насчет тяжести адресации последних узлов. То есть, в принципе, можно их не адресовать вовсе, а искать там последовательно. А что Вы понимаете по неявной адресацией?
Кстати, по поводу нескольких решений. Дело в том, что решение Ильи (ну точнее говоря это не совсем его решение см. ссылочку в его статье) не является точным. Так что описываемое Вами решение пока единственное. Теперь немного деталей. Префиксное дерево не может быть занимать меньше, чем весь словарь, закодированный префиксным кодом. Но дело в том, что стотысячный словарь, закодированный префиксным кодом занимает 300К ровно. С учетом кодирования букв 5 битами (ну может хафмманом будет 4, но не меньше) и прочими битовыми радостями. Ну и, конечно, же включая правило генерации окончаний (приставок). То есть префиксное дерево должно занимать места больше.
Можно даже предсказать на сколько. Очевидно, что если это действительно полное дерево, то на каждый лист указывает пойнтер. Поэтому чтобы уложиться в 350 - 50 Кб нужно кодировать пойнтер 4 битами. То есть если это даже относительный пойнтер, 4 бит явно не хватит. Собственно поэтому мне так интересно понять насколько "полным" было дерево и что такое неявная адресация.
PS: хорошо, что есть люди, которые не пытаются слупить денег за якобы секретные технологии, а просто рассказывают про них :-)
PPS: кстати, а точно у вас был полный Зализняк, то есть порядка ста тысяч словооснов?
То есть надо думать, что все-таки префиксное дерево?
А где гарантия, что эти самые поисковики не проиндексируют завтра какое-то новое слово?
поиск иероглифов - это совершенно отдельная тема. там нет однозначной границы слов. кстати, мне тоже кто-то минусов понадобавлял в теме про словарь в 300К. думаю, что это тот же самый человек. сейчас пойдем навалимся на него дружно сбросим ему репутацию вообще до нуля :-)
О опять кто-то шлет отрицательные отзывы. Боюсь, что теперь уж точно кой у кого репутация окажется нулевой.
большой это в данном случае сравнимый с размером самих данных.
изначально дискуссия шла про словарь в 300 кб, а каждому слову нужен айди. так вот если хранить этот самый айди этот минимум 100-200кб только на это самой айди. так вот если его вычислять, то будет гораздо быстрее.
плотная хеш - это в точности то, что изготовляет gperf.
сейчас вот запустил его на множестве 100 тысяч строк и жду результата. ну и в нашем случае абсолютно не нужен плотный хеш. достаточно, чтобы хеш попадал в диапазон скажем от нуля до одного миллиарда, а всем новым словам можно выдавать айди, начиная с миллиарда.
euhenio, понятие реально существующего слова в интернете - это миф. В принципе, если бы проблема была разрешима, то алгоритмы индексации и поиска можно было бы немножечко упростить.
!Иван FXS, gperf вроде бы делает это, но он, кажется, генерирует в результате табличку большого размера. а контекст был такой, что хотелось бы генерировать айди из слова практически не затрачивая дополнительной памяти.
Кстати, Зодчий со словарем все очень непросто. Вполне можно придумать простую функцию хеширования, которая именно на этом словаре дает уникальность. Особенно если словарь маленький. Смотрите берется обычная хорошая функция хеширования, вычисляем ее значения на словаре. Получаем там парочку коллизий. Запоминаем слова, для которых коллизии и выдаем им номера из числа свободных. И все. Так что номера статического словаря хранить действительно не обязательно. Но работать это будет гарантированно только для заданного набора слов. И вполне может быть, что именно этот нехитрый и никому ненужный прием нам боялись поведать. Ну так теперь мы его знаем :-)
InSan, зачот :-)
ok, у женщин, вообще, кажется своя какая-то логика, так что к мужеству их взывать вообще бессмысленно. пример с ослами неудачный, потому что обращение импликации - есть ошибка. а самоуничтожение двойного отрицания - факт вполне правильный, с точки зрения современной классической логики.
ЗЫ: по поводу вашего замечания о числе слов в Интернете и интов я абсолютно согласен, но тема совсем не об этом.
