Размер словаря

Леня, чего там гадать. Эта старинная статья с Диалога-95, про то как была упакована моя морфология в эпоху Библейского Компьютерного Справочника. Там же все подробнейшим образом написано и ссылка на Макилроевcкий ispell имеется.

Идешь в Яндекс, смотришь на полку с книжками, открываешь тоненькую книжечку "Жемчужины стиля программирования" Бентли (оба русских издания и хоть старое МИР-овское, хоть новый "кошмар переводчика") и читаешь там изложенную на русском языке историю как МакИлрой делал испелл и как он упихал анлицкий словарь в 50 килобайт.

Вкратце: "VBC-упакованная" (*) "сблокированная, с субиндексом" (**) "кишка" (***) "хешей" (****) основ слов.

(*) "VBC-упакованная" = здесь наверное объяснять не надо

(****) "хеш" - хеш-функция по большому основанию, то есть в разреженной (sparsed) таблице, чтобы вероятность коллизии была близка к нулю: я брал в районе 2^12 умн. на размер словаря, что давало 2 или 3 коллизии, кажется, в статье есть. То есть 140 тысяч основ*4 тысячи = примерно 500 миллионов. Поскольку используется VBC, то грубо, столько примерно бит (12) и потребуется на 1 основу.

(***) "кишка" - отсортированный по возрастанию разностно-упакованный массив (внутрияндексный термин)

(**) "сблокированная, с субиндексом" - внутрь кишки в начало блоков по несколько килобайт, "смотрит" табличка указателей, то есть субиндекс. Чтобы при поиске слова не распаковывать всю кишку, а бежать только от начала блока

Естественно тексты там не хранятся, синтез невозможен, это все в статье есть, несловарные слова в БКС оставлялись текстами и тд

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

Например; "блок" - это килобайты (0.5-16, типично 4), а "слот" - скажем 32-256 (типично 32 или 64) байт.

В каждом слоте данные лежат с "инкрементальной упаковкой", так как весь блок распаковывать дорого.

Понятно, что "послотовый" обмен с диском слишком невыгоден: требуется слишком большое оглавление, а файловая система все равно производит обмен не меньше размера сектора или кластера.

Т.о. "Блок" - единица обработки данных для диска, а "слот" - единица обработки данных для процессора.

б) старался писать понятно.

в) Когда я писал эту статью (март 1995), у меня еще не было интернета (он у меня появился в сентябре, а читать статьи я начал в ноябре), статьи появились в сети гораздо позже (siteseer открыли году в 1998, а наполненным он стал не раньше 2000-го, pdf тогда еще не индексировались). Возможно, что я тогда, 10 лет назад, неточную ссылку поставил.

Да мы это уже все более или менее поняли, просто Зодчий невнимательно прочел статью и взбаламутил народ. А МакИлроя я уже в оригинале прочел, слава богу не только в Яндексе есть полки :-)

Ну что самое смешно, что ровно в 300 кб словарь запихнуть без искажений нельзя, потому как где-то 280-290кб это словарь запакованный префиксным кодом с правилами раскрутки суффиксов. А вот в 350-400 при очень большом желании можно.

разжевали нарешти :-)

ну нифигаж себе наезды, а чем взбаламутил позвольте узнать? вопросом как удалось запихнуть словарь с морфологией в 300Кб?

тем, что у Ильи в статьи говорилось про эмпирическое неточное решение, а ты мучал народ вопросом, как запихнуть словарь в тот же объем, но чтобы он там точно хранился :-)

можно процитировать где я это сказал? ну а насчет мучал... некто ведь не заставлял отвечать не такли?

Вот на первой странице

если решение неточное, то говорить о целом словаре не приходится, не так ли? по-крайней мере, я так подумал. а насчет взбаламутил, это вовсе не наезд, не надо так принимать близко к сердцу :-)

Точный и целый разные вещи, нетакли? А насчет неточьности решения и «целого» словаря при этом, спорный вопрос

точный, целый, спорный, фиолетовый....

мне спать пора! счастливо.

Удивлен... Вроде бы, мы с Вами договорились, как это сделать можно (300К - словарь без морфоинформации, 350 - с ней).

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