Como faço para escolher entre uma tabela hash e um Trie (prefixo árvore)?

Question

Então, se eu tiver que escolher entre uma tabela hash ou uma árvore de prefixo quais são os fatores discriminantes que me levam a escolher um sobre o outro. Do meu próprio ponto de vista ingênuo parece que usando um trie tem alguma sobrecarga extra, uma vez que não é armazenado como uma matriz, mas que em termos de tempo de execução (assumindo que a chave mais longa é a palavra Inglês mais longo) pode ser, essencialmente, O (1) (em relação ao limite superior). Talvez a palavra Inglês mais longa é de 50 caracteres?

As tabelas de hash são instantâneas olhar para cima uma vez que você obter o índice . Hash a chave para obter o índice no entanto parece que poderia facilmente levar perto de 50 passos.

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

Answer 1

Vantagens de tentativas:

O básico:

• previsível O (k) tempo de pesquisa, onde k é a dimensão da chave
• Lookup pode levar menos de tempo k se ele não está lá
• Suporta ordenou travessia
• Não há necessidade de uma função hash
• A exclusão é simples

As novas operações:

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

Vantagens da estrutura ligada:

• Se houver muitos prefixos comuns, o espaço que eles exigem é compartilhado.
• tentativas imutáveis ??pode compartilhar estrutura. Em vez de atualizar um trie no lugar, você pode construir um novo que é diferente apenas ao longo de um ramo, em outra parte apontando para o velho trie. Isto pode ser útil para a simultaneidade, várias versões simultâneas de uma mesa, etc.
• Uma trie imutável é compressível. Ou seja, ele pode compartilhar estrutura no sufixos , bem como, por-consing hash.

Vantagens de hashtables:

• Toda a gente sabe hashtables, certo? O sistema já terá uma boa implementação bem otimizado, mais rápido do que tentativas para a maioria dos propósitos.
• As chaves não precisa ter qualquer estrutura especial.
• Mais espaço-eficiente que a estrutura trie ligada óbvia ( ver comentários abaixo )

Answer 2

Tudo depende de qual é o problema que você está tentando resolver. Se tudo que você precisa fazer é inserções e pesquisas, ir com uma tabela hash. Se você precisa resolver problemas mais complexos, tais como consultas de prefixo-relacionada, em seguida, um trie pode ser a melhor solução.

Answer 3

Todo mundo sabe tabela hash e seus usos, mas não é olhar exatamente constante o tempo, isso depende de quão grande é a tabela hash é, a complexidade computacional da função hash.

A criação de grandes tabelas de hash para pesquisa eficiente não é uma solução elegante na maioria dos cenários industriais onde mesmo pequenas questões de latência / escalabilidade (por exemplo .: negociação de alta frequência). Você tem que se preocupam com as estruturas de dados para ser otimizado para o espaço que ocupa na memória também para reduzir Cache Miss.

Um bom exemplo onde Trie melhor se adequa as exigências é de mensagens middleware. Você tem um milhão de assinantes e editores de mensagens para várias categorias (em termos JMS - Tópicos ou trocas), em tais casos, se você quiser filtrar mensagens com base em tópicos (que na verdade são cordas), você definitivamente não quer criar tabela hash para os milhões de assinaturas com milhão de tópicos. Uma abordagem melhor é armazenar os tópicos em trie, então quando filtragem é feita com base em fósforo tópico, a sua complexidade é independente do número de tópicos / inscrições / editores (somente depende do comprimento de corda). Eu gosto dele porque você pode ser criativo com este estrutura de dados para otimizar os requisitos de espaço e, portanto, têm menor cache miss.

Answer 4

Use uma árvore:

1. Se você precisar de funcionalidade completa auto
2. Encontre todas as palavras que começam com 'a' ou 'machado' assim por diante.
3. Uma árvore de sufixo é uma forma especial de uma árvore. árvores de sufixo tem toda uma lista de vantagens que hash não pode cobrir.

Answer 5

HashTable implementação é espaço eficiente em comparação com básico Trie implementação. Mas com cordas, ordenação é necessário na maioria das aplicações práticas. Mas HashTable perturba totalmente a ordem lexographical. Agora, se o seu aplicativo está fazendo operações com base na ordem lexographical (como pesquisa parcial, todas as cordas com prefixo dado, todas as palavras em ordem de classificação), você deve usar tentativas. Por apenas pesquisa, HashTable deve ser utilizado (como sem dúvida, dá tempo mínimo lookup).

P.S:. Para além destas, ternário Pesquisa Árvores (TST) seria uma excelente escolha. Seu tempo de pesquisa é mais do que HashTable, mas é tempo-eficiente em todas as outras operações. Além disso, é mais eficiente do espaço de tentativas.

Answer 6

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

Este é supondo que você tem uma boa função hash. Se você não quiser "farm" e "animais de fazenda" para hash para o mesmo valor, em seguida, a função hash terá que usar todos os bits da chave, e assim por hashing "animais de fazenda" deve levar cerca de duas vezes, enquanto "farm" (a menos que você está em algum tipo de rolar cenário de hash, mas há cenários de economia de operação um pouco semelhantes com tentativas também). E com uma tentativa de baunilha, é claro por que a inserção de "animais de fazenda" levará cerca de duas vezes, enquanto apenas "fazenda". No longo prazo, é verdade, com tentativas comprimido também.

Answer 7

Inserção e de pesquisa em um trie é linear com o lengh da cadeia de entrada O (s).

Um hash lhe dará uma ó (1) para pesquisa de ans de inserção, mas em primeiro lugar tem que calcular o hash baseado na cadeia de entrada que por sua vez é O (s).

conclussion, a complexidade de tempo assintótica é linear em ambos os casos.

O trie tem um pouco mais em cima da perspectiva de dados, mas você pode escolher um trie comprimido que irá colocá-lo de novo, mais ou menos em um empate com a tabela de hash.

Para quebrar o empate pergunte a si mesmo: Eu preciso pesquisar por apenas palavras cheias? Ou eu preciso para retornar todas as palavras correspondentes prefixo? (Como em um sistema de entrada de texto preditivo). Para o primeiro caso, ir para um hash. É mais simples e um código mais limpo. Mais fácil de testar e manter. Para um caso de uso mais ellaborated onde prefixos ou sufixes assunto, ir para um trie.

E se você fazê-lo apenas por diversão, implementando uma trie iria colocar uma tarde de domingo para um bom uso.

Answer 8

Alguns (geralmente incorporados, em tempo real) aplicações requerem que o tempo de processamento ser independente dos dados. Nesse caso, uma tabela hash pode garantir um tempo de execução conhecido, enquanto um trie varia de acordo com os dados.