Eu estava procurando por uma implementação eficiente de String trie. Principalmente eu encontrei código como este:
Implementação referencial em Java (por wikipedia)
Não gosto dessas implementações por dois motivos:
- Eles suportam apenas 256 caracteres ASCII. Eu preciso cobrir coisas como cirílico.
- Eles são extremamente ineficientes na memória.
Cada nó contém uma matriz de 256 referências, com 4096 bytes em uma máquina de 64 bits em Java. Cada um desses nós pode ter até 256 subnós com 4096 bytes de referências cada. Portanto, um Trie completo para cada sequência de caracteres ASCII 2 exigiria um pouco mais de 1 MB. Três cadeias de caracteres? 256 MB apenas para matrizes em nós. E assim por diante.
É claro que não pretendo ter todos os 16 milhões de strings de três caracteres no meu Trie, então muito espaço é desperdiçado. A maioria dessas matrizes são apenas referências nulas, pois sua capacidade excede em muito o número real de chaves inseridas. E se eu adicionar unicode, as matrizes ficam ainda maiores (char possui valores de 64k em vez de 256 em Java).
Existe alguma esperança de fazer um teste eficiente para strings? Eu considerei algumas melhorias sobre esses tipos de implementações:
- Em vez de usar uma matriz de referências, eu poderia usar uma matriz do tipo inteiro primitivo, que indexa em uma matriz de referências a nós cujo tamanho é próximo ao número de nós reais.
- Eu poderia dividir seqüências de caracteres em partes de 4 bits, o que permitiria matrizes de nós do tamanho 16 ao custo de uma árvore mais profunda.
se você codificar as seqüências de caracteres em UTF8, poderá usar o padrão de 256 ramificações e ainda assim ser compatível com unicode
Além disso, observe que apenas 70 caracteres dentre os 128 caracteres ASCII possíveis (todos codificados em 1 byte em UTF8) serão encontrados com mais força. Você pode otimizar isso (por exemplo, incluir os digrafos comuns no lugar dos caracteres de controle não utilizados )
fonte
byte*
para codificar qualquer tipo em um trie de bits.