Хранить слова в словаре

[Nashev]

Совать строчки (слова, словоформы, URI) в общее дерево, размазывая их по ветвям от корня. А указателем на строку иметь адрес финального листочка. Тогда можно раскатать от него до корня, и восстановить строчку.

Так в файловой системе, по сути, хранятся полные имена файлов — пути размазаны по дереву каталогов. Собственно, можно это дерево строк и на дерево папок отражать...

В пределе, в корне и на каждом уровне получится алфавит, а глубина дерева станет равна длине самого длинного слова. Но до тех пор совпадающие части от начала строчки будут храниться в одном экземпляре.

Предположительно, это даст сэкономить на памяти за счет однократного хранения строк.

Можно пойти дальше — строчки узлов глубже корня тоже хранить в этом же дереве, храня вместо строк указатели на их финальные листочки.

Разматывание слова получится рекурсивным в квадрате...

Размазывание (интеграция в это дерево) получится тоже сложнее... Но, кажется, все равно возможно.

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

Растить массив узлов можно блоками, и в номере узла выделять номер блока и номер в блоке. Блоки подгружать отдельно, по мере необходимости. Если узлы понадобиться удалять или менять им смысл, можно помечать их удалёнными и дальше иметь механизмы дефрагментации и хранить таблицу соответствий прежних номеров новым, обращаясь к новой базе через неё.

У узла нужны ссылки на соседа, первого ребёнка и на родителя. А так же ссылка на содержимое (строку у корневых узлов или хэндл строки у дочерних) и счётчик использований снаружи.

Хотя, счётчики можно и нужно иметь отдельно, в отдельной таблице. Они не нужны самому дереву, и могут быть контекстно-зависимыми...

[Nashev]

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

В пустое хранилище кладём «ехал», «ел», «еловый», «ехала», «ела» и «ехать». Это 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 символов

В пределе, кажись, получается что окончание отделяется после каждого символа, и цепочка каждого слова имеет свой нумерованный узел, и состоит из "(символ + (символ) + (символ + (символ + ...(символ)...)) — индекс", то есть столько рекурсивных обращений к словарю, сколько в нём букв. Но обращения рекурсивные, то есть есть шанс что не каждое из них придётся хранить отдельно.

Интересно было б посчитать количество внешних использований слов, и количество внутренних переиспользований частей слов. И посмотреть топы обоих списков.

[Nashev]

Добавляем «нахал»

• е
  ** (2) — 1 // е + хал
  ** (9) — 10 // е + хать
  *** (7) — 8 // ехал + а
  ** (4) — 3 // е + л
  *** (5) — 6 // ел + овый
  *** (7) — 8 // ел + а
• ха
  ** (4) — 2 // ха + л
  ** (11) — 9 // ха + ть
• л — 4
• овый — 5
• а — 7
• ть — 11
• на
  ** (2) — 12 // на + хал
  = 16 узлов + 13 символов вместо 29 символов словаря

тут при добавлении слова ищется, нет ли для него в словаре готового окончания. Иначе говоря, после облома с нахождением максимально подходящего начала, с каждой буквы добавляемого слова ищется аналогичное начинающееся слово и раскручиваются его дети в поисках подходящего продолжения...

Добавляем «хахаль» - чтоб и начало было знакомым и середина, и новое окончание

• е
  ** (2) — 1 // е + хал
  ** (9) — 10 // е + хать
  *** (7) — 8 // ехал + а
  ** (4) — 3 // е + л
  *** (5) — 6 // ел + овый
  *** (7) — 8 // ел + а
• ха
  ** (13) — ха + халь
  ** (4) — 2 // ха + л
  *** (14) — 13 // хал + ь
  ** (11) — 9 // ха + ть
• л — 4
• ь — 14
• овый — 5
• а — 7
• т
  ** (14) — 11 // т + ь
• на
  ** (2) — 12 // на + хал
  = 20 узлов + 13 символов вместо 35 символов словаря

то есть, если нашли начало - говорим, что новое слово это оно, плюс всё оставшееся окончание. Затем пристраиваем это оставшееся окончание как новое слово. Если не нашли начало - то смотрим, какую часть считать новым началом, исходя из того, какую часть окончания можно считать уже пристроенной.

[Nashev]

Что-то статистика не сильно вдохновляющая получается.

Символ - это 2 байта (юникод), а то и 1 (UTF-8 при латинице) и плюс накладных расходов на строчку по 12 байт

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

Неоднозначненько для меня это всё по-прежнему. Надо смотреть, что получится по факту.