masterspammer (masterspammer) wrote,
masterspammer
masterspammer

Category:

Префиксное дерево по-домашнему или грибные эльфы наносят ответный удар

Итак, есть префиксное дерево, это примерно вот так. То есть с начала идёшь по веточке "ж", потом "о", "п" и "а" и приходишь к тому, что это слово, как завещал Ю. Олеша, лучше печатными не писать, бо смешно идентификатору в БД, например (uint32). Если присмотреться к структуре, то всякому, кто по Си или Паскалю свой как минимум трояк получал сам, будет понятно, что сие построено главным образом из указателей.

А на дворе у нас средневековье, мракобесие и джаз 21-й век и машины шестидясетичетырёхбитные. 64 бита это 8 байт; уж не помню, прилагается к ним ещё какой-нибудь этак __сегмент__, но вроде бы нет; однако у нас узлов графа для словаря с http://opencorpora.org/ миллионов так 5, что даёт 40 мегабайт только ссылок на эти узлы + 5 мегабайт символов в узлах (юникод там не нужен, но полубайта уже мало будет, да и неудобно).

И вот тут приплыли - память сейчас конечно большая, но в кэш это точно не лезет, да и указатели на диске хранить не получится. И ещё вариант - для веба, где такое счастье требуется редко и хранить в памяти - зря, а читать (или строить) под 100мегов за раз да ещё на пи-малине - совсем зря.

Вариант - заменить адреса индексами массива (байт), уже в два раза можно скинуть; ну и дальше - хранить где можно не абсолютные адреса, а относительные, что даст ближе к концам слов где два байта, а где и один; но даже и 5 мегабайт просто на __ничего__ жалко (тем более, что информацию о том, где байт, где два, а где - четыре - тоже нужно где-то сохранить).

Первый указатель можно, кстати, не хранить; этот объект (в норме) будет сразу за самим узлом, то есть ясно где. Вот тот uint32 тоже имеет известный размер (хотя может быть не один, например "конь" как зверь и "Конь" как женская фамилия и они разные кони, даже и склоняются по-разному, но о конях позже) и его можно пропустить.

Кроме собственно указателей есть ещё и буквы, которым эти указатели соответствуют. Когда их из узла выходит много, это всяко битовый массив; когда мало - список. И тут вот masterspammer подумал - а как оно вообще бывает?

Придумал (для узла) сигнатуру - вот например "+1,М,Х!1" - это значит, что в узле уже 1 id (который uint32), из узла выходят ветви для букв "М" и "Х", причём для "Х" (тут я слегка забегаю вперёд) узел будет уже конечным с одним id/uint32. Построил статистику, выглядит так:

4618196 [all]
1206544 1
498373 2
219062 3
190872 +0,Я!1
148998 +1,С
104620 +0,Ь!1
102118 +0,Я!2
101600 4
89733 +1,И!1
75138 +2,С
67176 +0,О!3
67078 +0,Ю!1
66995 +3,И!1
66696 +2,У!2
56828 +0,Я!3

Видно, что большую часть составляют конечные узлы, то есть вот пришли, а там - только результаты; думаю - а что, если не считать конечные узлы вообще, вот как там я выше забежал вперёд, так и считать окончания частью родительского узла; статистика стала такой:

2569934 [all]
190872 +0,Я!1
148998 +1,С
104620 +0,Ь!1
102118 +0,Я!2
89733 +1,И!1
75138 +2,С
67176 +0,О!3
67078 +0,Ю!1
66995 +3,И!1
66696 +2,У!2
56828 +0,Я!3
51415 +0,С
51332 +0,Е

Видно, что всего узлов стало меньше почти в два раза и разнообразие возросло (но одного байта хватит, чтоб покрыть 90% узлов), так и буду кодировать; 254 значения - самые частые из таблицы, 255 - нет в таблице, читай дальше, а 0 - это значит, что узел изменён (структура с массивом хороша для read-only, каковой на 99% и будет являтся) и нужно использовать альтернативу, о которой позже.</all></all>
P.S. А с сегодняшнего дня я формально - специалист по машинному обучению (и компьютерной лингвистике), ибо первую зарплату получил.
Tags: ТекстовыеАлгоритмы, ХочетсяСтранного, Язык
Subscribe

  • Про "прёт" и результат

    Когда-то давно (уже офигительно давно по нашим новым торопливым временам) я начинал делать колонки. Сначала одни, потом другие; другие - долго,…

  • Прокрастинирую

    На выходных дал маха - что-то приклеил, что-то пошлифовал; потом уже дома вспомнил, что забыл закрыть клей. Вернулся - по идее закрутить крышку; по…

  • (no subject)

    Если понедельник начинается в субботу (и давно пора строить Алдан), другими словами суббота - понедельник следущей недели, то понедельник это…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 13 comments

  • Про "прёт" и результат

    Когда-то давно (уже офигительно давно по нашим новым торопливым временам) я начинал делать колонки. Сначала одни, потом другие; другие - долго,…

  • Прокрастинирую

    На выходных дал маха - что-то приклеил, что-то пошлифовал; потом уже дома вспомнил, что забыл закрыть клей. Вернулся - по идее закрутить крышку; по…

  • (no subject)

    Если понедельник начинается в субботу (и давно пора строить Алдан), другими словами суббота - понедельник следущей недели, то понедельник это…