Эффективная реализация Trie для строк Unicode

12

Я искал эффективную реализацию String Trie. В основном я нашел такой код:

Ссылочная реализация в Java (за википедию)

Мне не нравятся эти реализации в основном по двум причинам:

  1. Они поддерживают только 256 символов ASCII. Мне нужно охватить такие вещи, как кириллица.
  2. Они крайне неэффективны в памяти.

Каждый узел содержит массив из 256 ссылок, что составляет 4096 байт на 64-битном компьютере в Java. Каждый из этих узлов может иметь до 256 подузлов с 4096 байтами ссылок в каждом. Таким образом, полная Trie для каждой строки символов ASCII 2 потребует чуть более 1 МБ. Три строки символов? 256 МБ только для массивов в узлах. И так далее.

Конечно, я не собираюсь иметь все 16 миллионов трехсимвольных строк в моем Trie, так что много места просто теряется. Большинство этих массивов являются просто нулевыми ссылками, поскольку их емкость намного превышает фактическое количество вставленных ключей. И если я добавлю Unicode, массивы станут еще больше (char имеет значения 64k вместо 256 в Java).

Есть ли надежда на эффективную обработку строк? Я рассмотрел несколько улучшений по сравнению с этими типами реализаций:

  • Вместо использования массива ссылок, я мог бы использовать массив примитивного целочисленного типа, который индексирует в массив ссылок на узлы, размер которых близок к числу фактических узлов.
  • Я мог бы разбить строки на 4-битные части, что позволило бы создавать массивы узлов размером 16 за счет более глубокого дерева.
RokL
источник

Ответы:

2

Для чего вы используете этот три? Какое общее количество слов вы планируете удержать, и какова редкость составляющих их символов? И самое главное, подходит ли это слово (в отличие от простой карты префикса в списке слов)?

Ваша идея промежуточной таблицы и замены указателей на индексы будет работать, при условии, что у вас относительно небольшой набор коротких слов и разреженный набор символов. В противном случае вы рискуете нехватить места в промежуточной таблице. И если вы не посмотрите на очень маленький набор слов, вы не сэкономите столько места: 2 байта для короткого и 4 байта для ссылки на 32-битной машине. Если вы работаете на 64-битной JVM, экономия будет больше.

Ваша идея разбить символы на 4-битные порции, вероятно, не сильно вас спасет, если только вы не ожидаете, что все ваши ожидаемые символы находятся в чрезвычайно ограниченном диапазоне (возможно, хорошо для слов, ограниченных прописными буквами US-ASCII, вряд ли с общим корпусом Unicode ).

Если у вас есть редкий набор символов, то, HashMap<Character,Map<...>>возможно, ваша лучшая реализация. Да, каждая запись будет намного больше, но если у вас не так много записей, вы получите общий выигрыш. (в качестве примечания: я всегда думал, что было забавно, что статья в Википедии о Tries показала - может быть, до сих пор - пример, основанный на хешированной структуре данных, полностью игнорируя пространственно-временные компромиссы этого выбора)

Наконец, вы можете избежать всего этого. Если вы посмотрите на набор нормальных слов на человеческом языке (10 000 слов в активном использовании, со словами длиной 4-8 символов), вам, вероятно, будет НАМНОГО лучше с a HashMap<String,List<String>, где ключом является весь префикс.

Парсифаль
источник
- Ссылки - 8 байтов на 32-битных, 16 байтов на 64-битных машинах - Это для функциональности автозаполнения - Большинство символов в строках находятся в диапазоне ASCII, но есть несколько центрально-европейских символов, добавленных. Вот почему я хотел меньшего разветвления чем 256, потому что это будет вырезать большое количество символов. Я не вижу, что HashMap <String, List <String >> лучше или быстрее или меньше потребляет память, хотя его действительно легко писать и использовать. Но я приму идею HashMap <Character, Map>. Было бы хорошо для символов более 128 (редко в моем случае - будет плохо для китайского текста).
RokL
4

если вы закодируете строки в UTF8, вы можете использовать стандартное дерево ветвлений 256 и при этом быть совместимым с юникодом

также вы должны отметить, что только 70 или около того символов из возможных 128 символов ascii (которые все кодируют до 1 байта в UTF8) будут найдены наиболее интенсивно, что вы можете оптимизировать для этого (например, включить общие орграфы вместо неиспользуемых управляющих символов). )

чокнутый урод
источник
Я знаю, что UTF8 можно представить таким образом. Однако это все еще не решает потребление памяти, которое все еще довольно высоко. Перестановка символов в базовый диапазон 256 потребует довольно много переключений предложений, я сомневаюсь, что это того стоит. Что касается UTF-8 ... это действительно проблема, над которой я сейчас размышляю. Java String использует символы UTF-16, которые я могу легко получить, я могу кодировать эти байты за байтом. Или я могу конвертировать в UTF-8 и использовать это. На данный момент мне неясно, является ли стоимость преобразования из UTF-16 в UTF-8 чрезмерной или нет.
RokL
на каком языке вы планируете использовать это в большинстве случаев? пытаться оптимизировать все невозможно (или это было бы уже сделано), так что оптимизируйте для общего случая
трещотка урод
1
Это один из очень немногих случаев использования, когда CESU-8 предпочтительнее UTF-8: здесь огромное преимущество в том, что переход от кодовой точки UTF-8 к соответствующей кодовой точке CESU-8 тривиален (тогда как вам потребуется декодировать 1-2 кодовые точки UTF-16, чтобы добраться до соответствующих кодовых точек UTF-8).
Иоахим Зауэр
1
@ratchetfreak Java. Хотя я думаю, что вопрос можно обобщить для большинства языков. Я предполагаю, что в C вы могли бы просто привести указатель, byte*чтобы закодировать любой тип в побитовом виде.
RokL
@ UMad Я имел в виду, на каких языках будут входные строки (английский, французский, немецкий, ...)
трещотка урод