Algoritmo / passos para encontrar pesquisa Longest Prefix em Patricia Trie

Question

Estou implementando tentativas Patricia por IP prefixo pesquisa, eu poderia obter o código de trabalho para o jogo chave completa, mas que enfrentam problemas com pesquisa de prefixo, quando há são as chaves que são prefixos de outras chaves, como:

1.2.3.0
1.2.0.0

Alguém pode me ajudar com o algoritmo para pesquisas de prefixo no caso acima Devo considerar estes como chaves de comprimento separado (ou seja, / 24 e 16)?

Answer 1

Dê uma olhada na Net-Patricia. Esta é uma implementação de um trie Patricia para procurar endereços IP. A interface é perl, mas o código subjacente está em C. Aqui está um link, mas muitos arquivos CPAN deve tê-lo:

http: //cpansearch.perl. org / src / PHILIPP / Net-Patricia-1.15_07 / libpatricia / patricia.c

Answer 2

Se você usar este trie para armazenar números de IP como elementos do comprimento fixo, então não é definitivamente o caminho certo. O importante aqui é que o PT é especialmente útil para o armazenamento de dados de comprimento variável.
Se você armazenar peças de números IP, como prefixos de comprimento variável, em seguida, a PT é uma boa escolha.
Neste caso sim suas chaves devem ser de comprimento diferente.
Vamos dizer que você está armazenando prefixo "192.168" em binário 0xC0 0xA8, você adicionar este como primeira chave.
Então, ao procurar por IP como 192.168.1.1 você pode obter informações que o seu trie contém 192.168 que é um prefixo do que você procurar.
Tudo que você tem a fazer é armazenar a "parte comum" ao atravessar a trie.
Esta é uma adição menor ao esta implementação . Apenas certifique-se que, enquanto a descer a trie você armazenar a algum lugar parte comum nos parâmetros da função recursiva.
Para uma boa compreensão da Patricia trie eu sugiro ler livro Algoritmos de Robert Sedgewick que é uma grande fonte de conhecimento.

Editar : Há um problema ao armazenar strings C em PT. Este trie é projetado para armazenar dados binários, mas você está apenas interessado em obter todo o bytes. Certifique-se de que você está armazenando parte comum do prefixo somente se seu tamanho em bits é múltiplo de 8. Para um mau exemplo: você tem chave na sua árvore: 0xC0 0xA5 e você está procurando fro 0xC0 0xA6. O seu percurso irá parar quando a parte comum "0xC0 0xA", mas você está interessado em tomar apenas "0xC0". Então certifique-se de armazenar bytes comuns, e não pedaços.

Answer 3

Há uma implementação C bastante legível no código de teste para LLVM: https://llvm.org/svn/llvm-project/test-suite/trunk/MultiSource/Benchmarks/MiBench/network-patricia/ ??