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

134

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!

Justin Bozonier
fonte
1
Vale a pena notar que uma árvore redix é mais eficiente que uma simples tentativa, porque você não precisa de uma nova ramificação para cada byte de string. Além disso, as árvores redix fornecem suporte para pesquisas "difusas" melhor do que tabelas de hash, porque você está vendo bits individuais ao trabalhar no caminho. Por exemplo, 00110010pode ser o byte de entrada, mas você deseja incluir a correspondência 00111010que é removida apenas um bit.
Xeoncross 24/09/19

Respostas:

116

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 )
Darius Bacon
fonte
26
não pode concordar com "Mais espaço-eficiente do que a óbvia estrutura trie vinculada" - em uma implementação geral de tabela de hash, ocupa um espaço muito maior para conter chaves, enquanto nas tentativas, cada nó representa uma palavra. Nesse sentido, as tentativas são mais eficientes em termos de espaço.
Galactica
1
que tal acessar dados de uma estrutura versus a outra? Estou pensando cache e localização
Horia Toma
8
@ galactica, que entra em conflito com a minha experiência: por exemplo, nesta resposta de todas as estruturas que medi para o espaço, uma tentativa foi a pior. Isso faz sentido, pois um ponteiro é muito maior que um byte. Sim, o compartilhamento de prefixos ajuda, mas deve superar muita sobrecarga para alcançar a paridade. Uma representação mais eficiente em termos de espaço pode ajudar muito, mas não estamos mais falando sobre a óbvia estrutura vinculada.
Darius Bacon
1
O @DariusBacon que lida com planos de numeração telefônica parece um cenário razoável para tentativas. Exemplo de cenário: número de telefone correspondente à operadora, incl. números portados de uma operadora para outra. Para dicionários comuns, isso pode depender do idioma (mandarim x inglês), você precisará de n gramas e / ou outros dados estatísticos. Para um livro de rimas, uma árvore de sufixos também parece uma boa opção.
mbx
A diversidade dos dados para pesquisa importa muito. Se uma grande porcentagem de seus valores de dados for exclusiva, sua complexidade de espaço aumentará no hash devido ao uso de ponteiros nulos adicionais.
Estatísticas de aprendizado por exemplo
45

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.

Adam Rosenfield
fonte
8
se hash table e trie têm a mesma complexidade na consulta, O (k) para k length string, por que devemos usar hash? você poderia explicar?
Sazzad Hissain Khan
29

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.

user179156
fonte
11

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.
Dr.Sai
fonte
4

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.

user3391564
fonte
3

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.

Visiedo
fonte
"Um hash fornecerá O (1) para pesquisa e inserção, mas primeiro você deve calcular o hash com base na string de entrada, que novamente é O (s)." Obrigado por explicar isso!
abadawi 19/01
O cálculo da função hash não é O (s). Na verdade, é O (1). Você não precisa de todos os bits da string para computá-lo, alguns deles (um número constante deles) são suficientes.
Nicola Amadio
2

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.

Jay Jodiwal
fonte
-2

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.

Adam Liss
fonte
6
A maioria das tabelas de hash não garantem um tempo de execução conhecido - o pior caso é O (n), se cada colide elemento e fica acorrentado
Adam Rosenfield
2
Para qualquer conjunto de dados, você pode calcular uma função de hash perfeita que garantirá O (1) pesquisas para esses dados. Obviamente, calcular o hash perfeito não é gratuito.
George V. Reilly
5
Além disso, o encadeamento não é a única maneira de lidar com colisões; existem todos os tipos de maneiras interessantes e inteligentes de lidar com isso - cuckoo hashing ( en.wikipedia.org/wiki/Cuckoo_hashing ) para um - e a melhor opção depende das necessidades do código do cliente.
Hank Gay
não sabia sobre o hash do cuco e sua relação com o filtro de bloom, fará uma leitura interessante, obrigado!
Horia Toma
Não se esqueça do Robin-hood Hashing, que é superior para cache e variação. sebastiansylvan.com/2013/05/08/... codecapsule.com/2013/11/11/robin-hood-hashing
Jarred Nicholls