Nashev
commented
5 years ago Хотя не, сильно дальше так не пройти: если строчку второго уровня уложить в то же дерево, получится строка, начинающаяся со своей первой буквы, ... хм.. надо пример расписать.
В пустое хранилище кладём «ехал», «ел», «еловый», «ехала», «ела» и «ехать». Это 6 слов длинной 4+2+6+5+3+4=24 символа.
Если не пойти:
В пустое хранилище кладём «ехал»
- ехал - 1 = 1 узел + 4 символа
Добавляем туда «ел»
- е хал — 1 л — 2 = 3 узла + 5 символов
Добавляем «еловый»
- е хал — 1 л — 2 *** овый — 3 = 4 узла + 9 символов
Добавляем «ехала»
- е хал — 1 а — 4 л — 2 овый — 3 = 5 узлов + 10 символов
Добавляем «ела»
- е хал — 1 а — 4 л — 2 овый — 3 *** а — 5 = 6 узлов + 11 символов
Добавляем «ехать»
- е ха л — 1 ** а — 4 ** ть — 6 л — 2 овый — 3 *** а — 5 = 8 узлов + 13 символов
А теперь то же самое, если пойти:
В пустое хранилище кладём «ехал»
- ехал - 1 = 1 узел + 4 символа
Добавляем туда «ел»
- е (2) — 1 // е + хал (4) — 3 // е + л
- ха ** (4) — 2 // ха + л
- л — 4 = 6 узлов + 4 символа. «ехал» разделилась на общее начало и остаток «хал». Далее добвлялся остаток от добавляемого слова - «л». И добавившееся было словечко «хал» в постпроцессинге корневых слов при добавлении нового корневого слова («л») тоже оказывается разобрано на своё начало и новое известное окончание.
Добавляем «еловый»
- е (2) — 1 // е + хал (4) — 3 // е + л *** (5) — 6 // ел + овый
- ха ** (4) — 2 // ха + л
- л — 4
- овый — 5 = 8 узлов + 8 символов
Добавляем «ехала»
- е (2) — 1 // е + хал (7) — 8 // ехал + а (4) — 3 // е + л (5) — 6 // ел + овый
- ха ** (4) — 2 // ха + л
- л — 4
- овый — 5
- а — 7 = 10 узлов + 9 символов
Добавляем «ела»
- е (2) — 1 // е + хал (7) — 8 // ехал + а (4) — 3 // е + л (5) — 6 // ел + овый *** (7) — 8 // ел + а
- ха ** (4) — 2 // ха + л
- л — 4
- овый — 5
- а — 7 = 11 узлов + 9 символов
Добавляем «ехать»
- е (2) — 1 // е + хал (9) — 10 // е + хать * (7) — 8 // ехал + а * (4) — 3 // е + л (5) — 6 // ел + овый *** (7) — 8 // ел + а
- ха (4) — 2 // ха + л (11) — 9 // ха + ть
- л — 4
- овый — 5
- а — 7
- ть — 11 = 14 узлов + 11 символов
В пределе, кажись, получается что окончание отделяется после каждого символа, и цепочка каждого слова имеет свой нумерованный узел, и состоит из "(символ + (символ) + (символ + (символ + ...(символ)...)) — индекс", то есть столько рекурсивных обращений к словарю, сколько в нём букв. Но обращения рекурсивные, то есть есть шанс что не каждое из них придётся хранить отдельно.
Интересно было б посчитать количество внешних использований слов, и количество внутренних переиспользований частей слов. И посмотреть топы обоих списков.
Совать строчки (слова, словоформы, URI) в общее дерево, размазывая их по ветвям от корня. А указателем на строку иметь адрес финального листочка. Тогда можно раскатать от него до корня, и восстановить строчку.
Так в файловой системе, по сути, хранятся полные имена файлов — пути размазаны по дереву каталогов. Собственно, можно это дерево строк и на дерево папок отражать...
В пределе, в корне и на каждом уровне получится алфавит, а глубина дерева станет равна длине самого длинного слова. Но до тех пор совпадающие части от начала строчки будут храниться в одном экземпляре.
Предположительно, это даст сэкономить на памяти за счет однократного хранения строк.
Можно пойти дальше — строчки узлов глубже корня тоже хранить в этом же дереве, храня вместо строк указатели на их финальные листочки.
Разматывание слова получится рекурсивным в квадрате...
Размазывание (интеграция в это дерево) получится тоже сложнее... Но, кажется, все равно возможно.
Для отвязки от памяти и облегчения сериализации, особенно независимой, можно ссылкой на такую строку считать не указатель на узел, а его индекс в массиве узлов дерева. Если он будет только расти, номера устаревать не будут. Хэндлы. Сериализуемые.
Растить массив узлов можно блоками, и в номере узла выделять номер блока и номер в блоке. Блоки подгружать отдельно, по мере необходимости. Если узлы понадобиться удалять или менять им смысл, можно помечать их удалёнными и дальше иметь механизмы дефрагментации и хранить таблицу соответствий прежних номеров новым, обращаясь к новой базе через неё.
У узла нужны ссылки на соседа, первого ребёнка и на родителя. А так же ссылка на содержимое (строку у корневых узлов или хэндл строки у дочерних) и счётчик использований снаружи.
Хотя, счётчики можно и нужно иметь отдельно, в отдельной таблице. Они не нужны самому дереву, и могут быть контекстно-зависимыми...