Я искал эффективную реализацию String Trie. В основном я нашел такой код:
Ссылочная реализация в Java (за википедию)
Мне не нравятся эти реализации в основном по двум причинам:
- Они поддерживают только 256 символов ASCII. Мне нужно охватить такие вещи, как кириллица.
- Они крайне неэффективны в памяти.
Каждый узел содержит массив из 256 ссылок, что составляет 4096 байт на 64-битном компьютере в Java. Каждый из этих узлов может иметь до 256 подузлов с 4096 байтами ссылок в каждом. Таким образом, полная Trie для каждой строки символов ASCII 2 потребует чуть более 1 МБ. Три строки символов? 256 МБ только для массивов в узлах. И так далее.
Конечно, я не собираюсь иметь все 16 миллионов трехсимвольных строк в моем Trie, так что много места просто теряется. Большинство этих массивов являются просто нулевыми ссылками, поскольку их емкость намного превышает фактическое количество вставленных ключей. И если я добавлю Unicode, массивы станут еще больше (char имеет значения 64k вместо 256 в Java).
Есть ли надежда на эффективную обработку строк? Я рассмотрел несколько улучшений по сравнению с этими типами реализаций:
- Вместо использования массива ссылок, я мог бы использовать массив примитивного целочисленного типа, который индексирует в массив ссылок на узлы, размер которых близок к числу фактических узлов.
- Я мог бы разбить строки на 4-битные части, что позволило бы создавать массивы узлов размером 16 за счет более глубокого дерева.
если вы закодируете строки в UTF8, вы можете использовать стандартное дерево ветвлений 256 и при этом быть совместимым с юникодом
также вы должны отметить, что только 70 или около того символов из возможных 128 символов ascii (которые все кодируют до 1 байта в UTF8) будут найдены наиболее интенсивно, что вы можете оптимизировать для этого (например, включить общие орграфы вместо неиспользуемых управляющих символов). )
источник
byte*
чтобы закодировать любой тип в побитовом виде.