Implementação eficiente de Trie para strings unicode

12

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:

  1. Eles suportam apenas 256 caracteres ASCII. Eu preciso cobrir coisas como cirílico.
  2. 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.
RokL
fonte

Respostas:

2

Para que você está usando esse teste? Qual é o número total de palavras que você planeja conter e qual a escassez de seus caracteres constituintes? E o mais importante, um teste é mesmo apropriado (em comparação com um simples mapa de prefixo para a lista de palavras)?

Sua idéia de uma tabela intermediária e a substituição de ponteiros por índices funcionará, desde que você tenha um conjunto relativamente pequeno de palavras curtas e um conjunto de caracteres esparsos. Caso contrário, você corre o risco de ficar sem espaço na sua tabela intermediária. E, a menos que você esteja procurando um conjunto de palavras extremamente pequeno, não economizará muito espaço: 2 bytes para um curto versus 4 bytes para uma referência em uma máquina de 32 bits. Se você estiver executando uma JVM de 64 bits, a economia será maior.

Sua idéia sobre dividir os caracteres em partes de 4 bits provavelmente não poupará muito, a menos que todos os caracteres esperados estejam em um intervalo extremamente limitado (talvez seja bom para palavras limitadas a US-ASCII maiúsculas, provavelmente não com um corpus Unicode geral )

Se você tiver um conjunto de caracteres esparsos, a HashMap<Character,Map<...>>poderá ser sua melhor implementação. Sim, cada entrada será muito maior, mas se você não tiver muitas entradas, obterá uma vitória geral. (como uma observação lateral: sempre achei engraçado que o artigo da Wikipedia sobre Tries mostrasse - talvez ainda o faça - um exemplo baseado em uma estrutura de dados com hash, ignorando completamente as trocas de espaço / tempo dessa escolha)

Por fim, convém evitar completamente. Se você estiver visualizando um corpus de palavras normais em uma linguagem humana (10.000 palavras em uso ativo, com palavras de 4 a 8 caracteres), provavelmente estará MUITO melhor com a HashMap<String,List<String>, onde a chave é o prefixo inteiro.

parsifal
fonte
- As referências são 8 bytes em máquinas de 32 bits e 16 bytes em máquinas de 64 bits - É para funcionalidade de preenchimento automático - A maioria dos caracteres nas seqüências está no intervalo ASCII, mas há alguns caracteres da Europa Central inseridos. É por isso que eu queria ramificações menores que 256, porque cortará um grande número de caracteres. Não vejo o HashMap <String, List <String>> melhor ou mais rápido ou menos consumindo memória, embora seja realmente fácil de escrever e usar. Mas aceitarei a ideia <HashMap <Caractere, Mapa>. Seria bom para caracteres acima de 128 (raro no meu caso - seria ruim para texto em chinês).
RokL
4

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 )

catraca arrepiante
fonte
Eu sei que UTF8 pode ser representado assim. No entanto, isso ainda não resolve o consumo de memória, que ainda é bastante alto. Trocar caracteres no intervalo básico de 256 exigiria um pouco de frases de troca, duvido que valha a pena. No que diz respeito ao UTF-8 ... esse é realmente um problema que estou pensando agora. Java String usa caracteres UTF-16, que posso obter facilmente, posso codificar esses byte a byte. Ou posso converter para UTF-8 e usá-lo. Neste ponto, não está claro para mim se o custo da conversão de UTF-16 para UTF-8 é proibitivo ou não.
RokL
qual é o idioma que você imagina usar isso na maioria das vezes? tentando otimizar para tudo é impossível (ou teria sido feito já) para otimizar para o caso comum
catraca aberração
1
Este é um dos poucos casos de uso em que o CESU-8 seria preferível ao UTF-8: é uma grande vantagem aqui é que é trivial passar de um ponto de código UTF-8 para o ponto de código CESU-8 correspondente (embora você precise decodificar 1-2 pontos de código UTF-16 para chegar aos pontos de código UTF-8 correspondentes).
Joachim Sauer
1
@ratchetfreak Java. Embora eu ache que a questão possa ser generalizada para a maioria dos idiomas. Eu acho que em C você pode simplesmente usar o ponteiro byte*para codificar qualquer tipo em um trie de bits.
RokL
@UMad eu quis dizer quais idiomas as cadeias de entrada estará em (Inglês, Francês, Alemão, ...)
catraca aberração