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

ok, если Вам так все понятно, то может объяснить навскидку

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

б) что такое "и специальное представление текстов основы. Это представление заменяет текст основы на сответствующий ему бит из хэш-таблицы большого размера." надо думать, что это специальное представление - просто хеш-функция, но почему так запутанно написано? а все потому что конспирация непонятно от кого и непонятно зачем. Хотя не исключаю и недостаток времени. А теперь возьмите и почитайте оригинальную статью MclIroy

http://gpsis.utp.edu.co/downloads/a3udeloz_spell.pdf и Вы поймете, что понятно, а что не очень. :-)

в) ну и наконец последний вопрос (ссылку с PDF только чур не открывать): как называется оригинальная статья, на которую Илья ссылается? конечно, сейчас есть гугл скулар, просто гугл автокорректор в гугле, но раньше я бы, вполне возможно, не нашел бы эту статью, пользуясь альтавистой.

Дык, мне понятна статья, и понятно, как она соотносится с ночной дискуссией, а не то, что Вам в ней не понятно.

Более того, не удивлюсь, если вообще не пойму, что Вы - об этой статье - спрашиваете. ;-)

"Представление заменяет текст основы на сответствующий ему бит из хэш-таблицы большого размера" - это я понимаю так, что вводится хэш-функция, отображающая ЛЮБУЮ последовательность букв в множество целых чисел, скажем, от 1 до 1 000 000 000. А потом берется битовый массив (размером в эти 1 000 000 000 бит) и "прожигается" единичками в тех точках, которые соответсвуют буквосочетаниями, ПРИЗНАВАЕМЫМИ нами "правильными" основами слов.

Там, правда, еще написано, что в эту же матрицу напиханы "плотно идущие" коды слов (основ). Тоже понятно, но конструкция становится менее красивой.

_______________

Я вот тоже работаю со словарем, когда АСС (Ассоциативно-семантичекую Сеть) строю. Но - поигрался немного со всякими хэшами и вернулся к простейшей таблице, проиндексированой. То бишь - бинарные деревья там, причем не самописные, а предустановленные Биллом Гейтсом в его MS Access, на котором, собственно, и ваяю. Дешево и сердито; усилия расходуются не на изобретение велосипедов, а на исследование терра инкогнито.

Думаю, людей, у которых в лохматые 90-е был словарь Зализняка в 300К не так уж и мало. Вот и у нас такой имелся. Просто задача была: работать в 640К. Конечно, если быть точным, словарь у нас был в 350К, но в нем еще была полная морфологическая информация (прямые и обратные коды) для лексем и словоформ.

Причем, метод построения словаря мы использовали другой, чем Илья: у него была хэш-таблица, у нас - дерево. Точнее, 2 дерева - основ и окончаний. Плюс очевидные "экономящие" правила, например, приставка НЕ с прилагательными.

Так что задачка не такая трудная, если ее можно решать разными способами.

То есть надо думать, что все-таки префиксное дерево?

Попробую

Конечно, экономили на битах, считали статистику последовательностей и кодировали их. Главная проблема, насколько я помню (опять же!), была в тяжести адресации последних узлов (листьев). С ней справились через неявную адресацию.

Вообще, основной недостаток дерева - в представлении его в компьютерной памяти. Память же линейна. Т.е. мы дерево вынуждены разрезать по ВСЕМ веточкам и соединить их заново связями. Представьте дерево в саду и мысленно разрежьте его, выложив в струнку и соединив ниточками узлы. Цена этого особенно велика на конечных узлах.

Под префиксным деревом я понимаю дерево, в котором слова с одинаковым префиксом запихиваются в одно поддерево.

Я очень даже хорошо понимаю ситуацию с префиксным деревом. Да Вы совершенно правы насчет тяжести адресации последних узлов. То есть, в принципе, можно их не адресовать вовсе, а искать там последовательно. А что Вы понимаете по неявной адресацией?

Кстати, по поводу нескольких решений. Дело в том, что решение Ильи (ну точнее говоря это не совсем его решение см. ссылочку в его статье) не является точным. Так что описываемое Вами решение пока единственное. Теперь немного деталей. Префиксное дерево не может быть занимать меньше, чем весь словарь, закодированный префиксным кодом. Но дело в том, что стотысячный словарь, закодированный префиксным кодом занимает 300К ровно. С учетом кодирования букв 5 битами (ну может хафмманом будет 4, но не меньше) и прочими битовыми радостями. Ну и, конечно, же включая правило генерации окончаний (приставок). То есть префиксное дерево должно занимать места больше.

Можно даже предсказать на сколько. Очевидно, что если это действительно полное дерево, то на каждый лист указывает пойнтер. Поэтому чтобы уложиться в 350 - 50 Кб нужно кодировать пойнтер 4 битами. То есть если это даже относительный пойнтер, 4 бит явно не хватит. Собственно поэтому мне так интересно понять насколько "полным" было дерево и что такое неявная адресация.

PS: хорошо, что есть люди, которые не пытаются слупить денег за якобы секретные технологии, а просто рассказывают про них :-)

PPS: кстати, а точно у вас был полный Зализняк, то есть порядка ста тысяч словооснов?

Увы, "пытать будут - не выдам", многого уже не помню.

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

Уникальных основ получилось поменьше, чем 100 тыс. Обратите внимание: кодируются именно основы, а не первые формы, например. Здесь выигрываем на совпадении многих основ - "омосновах", так сказать. Да и про обработку приставок не забывайте.

Адресация узлов разнобитная - ровно столько, сколько надо, естественно, относительная. Сами узлы (не буквы!), кстати, тоже хорошо поддавались статистическому кодированию (по Хаффману): наш словарик тогда утаптывался часов 10-12, зато потом никаких потерь по скорости (кроме "битовых радостей", естественно, но основы-то короткие).

Вот про неявную адресацию терминальных узлов, увы, почти ничего не скажу. С прямым поиском мы тогда не прошли по скорости, но сегодня машины совсем другие, так что попробуйте.

Надеюсь, теперь Вы полностью вооружены, дерзайте.

Такой словарик можно засунуть куда-нибудь в маленькую машинку типа мобильника. Или даже для них теперь это неактуально?

На самом деле мне тут подумалось, что это все совсем не напрасные муки. Мы тут все радостно забыли про то, что L1 и L2 кеши на порядок быстрее оперативной памяти. И если написать приложение так, что морфологический разбор протекает "последовательно" то есть скачали миллион документов, выбрали миллион уникальных слов, прогнали морфоанализатор, то выигрыш по скорости может быть довольно-таки приличным. А размеры кешей сейчас как раз в районе 500 кб - 1 мб.

Пожалуй, Вы правы.

Даже если не "последовательный" разбор (уж больно круг сужаем специальными задачами), словарик в 300-350К будет с большой вероятностью в кэше процессора, ведь объем 2М теперь не редкость.