Existem várias formas de representar tentativas, correspondendo a diferentes trade-offs entre o uso de memória e a velocidade das operações. A forma básica é a de um conjunto de nós ligados, onde cada nó contém um conjunto de ponteiros filhos, um para cada símbolo no alfabeto (assim, para o alfabeto inglês, seriam armazenados 26 ponteiros filhos e para o alfabeto de bytes, 256 ponteiros). Isto é simples mas desperdiçador em termos de memória: usando o alfabeto de bytes (tamanho 256) e ponteiros de quatro bytes, cada nó requer um kilobyte de armazenamento, e quando há pouca sobreposição nos prefixos das cordas, o número de nós necessários é aproximadamente o comprimento combinado das cordas armazenadas.:341 Colocando de outra forma, os nós perto do fundo da árvore tendem a ter poucos filhos e há muitos deles, então a estrutura desperdiça espaço armazenando apontadores nulos.
O problema de armazenamento pode ser aliviado por uma técnica de implementação chamada redução do alfabeto, onde as cordas originais são reinterpretadas como cordas mais longas sobre um alfabeto menor. Por exemplo, uma cadeia de n bytes pode ser considerada alternativamente como uma cadeia de 2n unidades de quatro bits e armazenada em uma trie com dezesseis ponteiros por nó. As pesquisas precisam visitar o dobro dos nós no pior caso, mas os requisitos de armazenamento diminuem por um fator de oito.:347-352
Uma implementação alternativa representa um nó como um triplo (símbolo, filho, próximo) e liga os filhos de um nó como uma lista ligada individualmente: filho aponta para o primeiro filho do nó, ao lado do próximo filho do nó pai. O conjunto de crianças também pode ser representado como uma árvore de busca binária; uma instância desta idéia é a árvore de busca ternária desenvolvida por Bentley e Sedgewick.:353
Outra alternativa para evitar o uso de um array de 256 ponteiros (ASCII), como sugerido anteriormente, é armazenar o array alfabético como um bitmap de 256 bits representando o alfabeto ASCII, reduzindo drasticamente o tamanho dos nós.
Bitwise tryEdit
Bitwise tries are much the same as a normal character-based trie except that individual bits are used to traverse what effectively becomes a form of binary tree. Geralmente, as implementações usam uma instrução especial da CPU para encontrar muito rapidamente o primeiro bit definido em uma chave de comprimento fixo (por exemplo, GCC’s __builtin_clz() intrínseco). Este valor é então usado para indexar uma tabela de 32 ou 64 entradas que aponta para o primeiro item no bitwise trie com esse número de bits zero. A busca então procede testando cada bit subseqüente na chave e escolhendo child ou child apropriadamente até que o item seja encontrado.
Embora esse processo possa parecer lento, ele é muito cache-local e altamente paralelizável devido à falta de dependências de registro e, portanto, tem de fato um excelente desempenho em CPUs modernas de execução fora de ordem. Uma árvore vermelha-negra, por exemplo, tem um desempenho muito melhor no papel, mas é altamente inapropriada para o cache e causa múltiplas falhas de pipeline e TLB em CPUs modernas, o que torna esse algoritmo limitado pela latência de memória em vez da velocidade da CPU. Em comparação, um bitwise trie raramente acessa a memória, e quando o faz, ele o faz apenas para ler, evitando assim a sobrecarga de coerência de cache SMP. Assim, ele está se tornando cada vez mais o algoritmo de escolha para código que executa muitas inserções e exclusões rápidas, como alocadores de memória (por exemplo, versões recentes do famoso alocador Doug Lea’s (dlmalloc) e seus descendentes). O pior caso de passos para pesquisa é o mesmo que bits usados para indexar bins na árvore.
Alternativamente, o termo “bitwise trie” pode mais geralmente se referir a uma estrutura de árvore binária contendo valores inteiros, ordenando-os pelo seu prefixo binário. Um exemplo é o trie x-fast.
Comprimir tentativasEditar
Comprimir o trie e fundir os ramos comuns pode às vezes gerar grandes ganhos de performance. Isto funciona melhor sob as seguintes condições:
- A trie é (na maioria das vezes) estática, de modo que nenhuma inserção ou exclusão de chave é necessária (por exemplo, após a criação em massa da trie).
- Apenas pesquisas são necessárias.
- Os nós da trie não são codificados por dados específicos do aceno, ou os dados dos nós são comuns.
- O conjunto total de chaves armazenadas é muito esparso dentro do seu espaço de representação (assim a compressão compensa).
Por exemplo, ele pode ser usado para representar bits esparsos; ou seja, subconjuntos de um conjunto muito maior e enumerável fixo. Neste caso, o trie é digitado pela posição do elemento bit dentro do conjunto completo. A chave é criada a partir da cadeia de bits necessária para codificar a posição integral de cada elemento. Tais tentativas têm uma forma muito degenerada com muitos ramos em falta. Após detectar a repetição de padrões comuns ou preencher as lacunas não utilizadas, os nós de folha únicos (cadeias de bits) podem ser armazenados e comprimidos facilmente, reduzindo o tamanho total do trie.
Tal compressão também é usada na implementação das várias tabelas de pesquisa rápida para recuperar as propriedades dos caracteres Unicode. Estas poderiam incluir tabelas de mapeamento de casos (por exemplo, para a letra grega pi, de Π a π), ou tabelas de pesquisa normalizando a combinação de base e combinação de caracteres (como o a-umlaut em alemão, ä, ou o dalet-patah-dagesh-ole em hebraico bíblico, דַּ֫). Para tais aplicações, a representação é semelhante a transformar uma tabela muito grande, unidimensional e esparsa (por exemplo, pontos de código Unicode) em uma matriz multidimensional de suas combinações, e então usando as coordenadas na hiper-matriz como a chave de string de uma trie não comprimida para representar o caracter resultante. A compressão consistirá então em detectar e fundir as colunas comuns dentro da hiper-matriz para comprimir a última dimensão na chave. Por exemplo, para evitar o armazenamento do ponto de código Unicode completo e multibyte de cada elemento formando uma coluna matricial, os agrupamentos de pontos de código semelhantes podem ser explorados. Cada dimensão da hiper-matriz armazena a posição inicial da dimensão seguinte, de modo que apenas o offset (normalmente um único byte) precisa ser armazenado. O vetor resultante é compressivo quando também é esparso, assim cada dimensão (associada a um nível de camada na trie) pode ser comprimida separadamente.
Algumas implementações suportam essa compressão de dados dentro de tentativas dinâmicas esparsas e permitem inserções e exclusões em tentativas comprimidas. Entretanto, isso geralmente tem um custo significativo quando segmentos comprimidos precisam ser divididos ou fundidos. Algumas trocas têm que ser feitas entre compressão de dados e velocidade de atualização. Uma estratégia típica é limitar a gama de buscas globais para comparar os ramos comuns na trie esparsa.
O resultado de tal compressão pode parecer similar a tentar transformar a trie em um gráfico acíclico dirigido (DAG), porque a transformação inversa de um DAG para uma trie é óbvia e sempre possível. Entretanto, a forma do DAG é determinada pela forma da chave escolhida para indexar os nós, restringindo a compressão possível.
Outra estratégia de compressão é “desvendar” a estrutura de dados em uma única matriz de bytes. Isto, por sua vez, permite o mapeamento da memória e o uso de memória virtual para carregar eficientemente os dados do disco.
Uma outra abordagem é “empacotar” a trie. Liang descreve uma implementação eficiente em termos de espaço de uma trie compactada esparsa aplicada à hifenização automática, na qual os descendentes de cada nó podem ser intercalados na memória.
Tentativas de memória externaEditar
Variantes de trieeveral são adequadas para manter conjuntos de strings na memória externa, incluindo árvores de sufixos. Uma combinação de trie e B-tree, chamada de B-trie também foi sugerida para esta tarefa; em comparação com as árvores de sufixos, elas são limitadas nas operações suportadas, mas também mais compactas, enquanto executam as operações de atualização mais rapidamente.