Como escolho entre uma tabela de hash e uma trie (árvore de prefixo)?

Portanto, se eu tiver que escolher entre uma tabela de hash ou uma árvore de prefixos, quais são os fatores discriminantes que me levariam a escolher um sobre o outro. Do meu ponto de vista ingênuo, parece que o uso de um trie tem uma sobrecarga extra, pois não é armazenado como uma matriz, mas que em termos de tempo de execução (supondo que a chave mais longa seja a palavra mais longa em inglês), pode ser essencialmente O (1) (em relação ao limite superior). Talvez a palavra em inglês mais longa tenha 50 caracteres?

As tabelas de hash são pesquisadas instantaneamente quando você obtém o índice . Pressionar a tecla para obter o índice, no entanto, parece que pode facilmente levar cerca de 50 etapas.

Alguém pode me fornecer uma perspectiva mais experiente sobre isso? Obrigado!

Vantagens das tentativas:

O básico:

• Tempo de pesquisa O (k) previsível em que k é o tamanho da chave
• A pesquisa pode levar menos de k tempo, se não estiver lá
• Suporta passagem ordenada
• Não há necessidade de uma função de hash
• A exclusão é direta

Novas operações:

• Você pode procurar rapidamente prefixos de chaves, enumerar todas as entradas com um determinado prefixo, etc.

Vantagens da estrutura vinculada:

• Se houver muitos prefixos comuns, o espaço necessário será compartilhado.
• Tentativas imutáveis ​​podem compartilhar estrutura. Em vez de atualizar um trie no lugar, você pode criar um novo diferente apenas ao longo de uma ramificação, apontando para o trie antigo. Isso pode ser útil para simultaneidade, várias versões simultâneas de uma tabela etc.
• Um teste imutável é compressível. Ou seja, ele também pode compartilhar estrutura nos sufixos , por hash-consing.

Vantagens das hashtables:

• Todo mundo conhece as hashtables, certo? Seu sistema já terá uma implementação bem otimizada, mais rápida do que tentativas para a maioria dos propósitos.
• Suas chaves não precisam ter nenhuma estrutura especial.
• Mais economia de espaço do que a estrutura trie vinculada óbvia ( veja os comentários abaixo )

Tudo depende do problema que você está tentando resolver. Se tudo o que você precisa fazer é inserções e pesquisas, escolha uma tabela de hash. Se você precisar resolver problemas mais complexos, como consultas relacionadas a prefixos, uma tentativa poderá ser a melhor solução.

Todo mundo conhece a tabela de hash e seus usos, mas não é exatamente o tempo de pesquisa constante, depende do tamanho da tabela de hash, da complexidade computacional da função de hash.

Criar enormes tabelas de hash para uma pesquisa eficiente não é uma solução elegante na maioria dos cenários industriais em que até uma pequena latência / escalabilidade é importante (por exemplo, negociação de alta frequência). Você também precisa se preocupar com as estruturas de dados para otimizar o espaço que ocupa na memória para reduzir a falta de cache.

Um bom exemplo de como o trie melhor se adapta aos requisitos é o middleware de mensagens. Você tem um milhão de assinantes e publicadores de mensagens para várias categorias (em termos JMS - Tópicos ou trocas); nesses casos, se desejar filtrar mensagens com base em tópicos (que na verdade são cadeias), você definitivamente não deseja criar tabela de hash para o milhão de assinaturas com milhões de tópicos. Uma abordagem melhor é armazenar os tópicos em ordem, portanto, quando a filtragem é feita com base na correspondência de tópicos, sua complexidade é independente do número de tópicos / assinaturas / editores (depende apenas do comprimento da sequência). Gosto porque você pode ser criativo com essa estrutura de dados para otimizar os requisitos de espaço e, portanto, ter menos perda de cache.

Use uma árvore:

1. Se você precisar do recurso de preenchimento automático
2. Encontre todas as palavras que começam com 'a' ou 'machado' etc.
3. Uma árvore de sufixo é uma forma especial de uma árvore. As árvores de sufixo têm uma lista completa de vantagens que o hash não pode cobrir.

Há algo que eu não vi ninguém mencionar explicitamente que acho importante ter em mente. As tabelas de hash e as tentativas de vários tipos geralmente têm O(k)operações, onde ké o comprimento da sequência em bits (ou equivalente em caracteres).

Isso pressupõe que você tenha uma boa função de hash. Se você não deseja que "farm" e "farm animals" tenham hash com o mesmo valor, a função hash terá que usar todos os bits da chave; portanto, o hashing de "farm animals" deve demorar cerca do dobro do tempo "farm" (a menos que você esteja em algum tipo de cenário de hash contínuo, mas também há cenários semelhantes de economia de operação com tentativas). E com uma baunilha, fica claro por que a inserção de "animais de fazenda" levará duas vezes mais do que apenas "fazenda". A longo prazo, é verdade também com tentativas compactadas.

A inserção e a pesquisa em uma árvore são lineares com o comprimento da (s) sequência (s) de entrada.

Um hash fornecerá O (1) para pesquisa e inserção, mas primeiro você deve calcular o hash com base na cadeia de entrada, que novamente é O (s).

Conclusão: a complexidade do tempo assintótico é linear nos dois casos.

O trie tem um pouco mais de sobrecarga da perspectiva dos dados, mas você pode escolher um trie compactado que o colocará novamente, mais ou menos empatado com a tabela de hash.

Para quebrar o empate, faça a si mesmo esta pergunta: Preciso procurar apenas palavras completas? Ou preciso retornar todas as palavras correspondentes a um prefixo? (Como em um sistema preditivo de entrada de texto). Para o primeiro caso, escolha um hash. É um código mais simples e limpo. Mais fácil de testar e manter. Para um caso de uso mais elaborado, em que prefixos ou sufixos são importantes, faça um teste.

E se você fizer isso apenas por diversão, a implementação de um teste colocaria uma tarde de domingo em um bom uso.

A implementação do HashTable é eficiente em termos de espaço em comparação com a implementação básica do Trie . Mas com seqüências de caracteres, a ordenação é necessária na maioria das aplicações práticas. Mas o HashTable perturba totalmente a ordem lexográfica. Agora, se seu aplicativo estiver executando operações com base em ordem lexográfica (como pesquisa parcial, todas as seqüências de caracteres com prefixo fornecido, todas as palavras na ordem de classificação), você deve usar Tries. Apenas para pesquisa, o HashTable deve ser usado (como é possível, isso fornece um tempo mínimo de pesquisa).

PS: Além disso, as Árvores de Pesquisa Ternária (TSTs) seriam uma excelente opção. Seu tempo de pesquisa é maior que o HashTable, mas economiza tempo em todas as outras operações. Além disso, é mais eficiente em termos de espaço do que tenta.

Alguns aplicativos (geralmente incorporados em tempo real) exigem que o tempo de processamento seja independente dos dados. Nesse caso, uma tabela de hash pode garantir um tempo de execução conhecido, enquanto uma tentativa varia com base nos dados.