Patricia Trie para recuperação rápida de endereços IPv4 e dados de satélite

Question

Eu estou escrevendo um programa em C++ que requer endereços IP( todos os IPv4) para ser analisada e armazenada de uma forma rápida.Todos os endereços de IP tem uma base de dados associada a ele.No caso de já existir na trie, pretendo mesclar os dados do endereço IP na trie com os novos endereços de dados.Se ele não está presente, eu pretendo adicionar uma nova entrada para o trie.Exclusão de endereço IP não é necessário.

Para implementar isso, eu preciso de design de uma Patricia Trie.No entanto, eu sou incapaz de visualizar o projeto, além deste.Parece bastante ingênua de mim, mas a única idéia que me veio à mente foi a de alterar o endereço IP para o seu binário de formulário e, em seguida, usar o trie.Contudo estou a menor ideia sobre o COMO exatamente para implementar isso.

Eu seria muito grato se você poderia me ajudar com este.Por favor, note que eu achei uma pergunta semelhante aqui .A questão ou, mais especificamente, a resposta estava além da minha compreensão como o código no CPAN web site não foi clara o suficiente para mim.

Observe também que os meus dados é o seguinte formato

10.10.100.1:"Tom","Jack","Smith"

192.168.12.12:"Jones","Liz"

12.124.2.1:"Jimmy","George"

10.10.100.1:"Mike","Harry","Jennifer"

Answer 1

Patricia tenta resolver o problema de encontrar o melhor prefixo de cobertura para um determinado endereço IP (eles são usados pelos roteadores para determinar rapidamente que 192.168.0.0/16 é a melhor escolha para 192.168.14.63, por exemplo).Se você está apenas tentando combinar os endereços IP exatamente, uma tabela de hash é uma melhor escolha.

Answer 2

Eu acho que você está se referindo a um RadixTree.Eu tenho uma implementação de um RadixTrie em Java, se você quer usar isso como um ponto de partida, que é a chave real para mapeamento de valor.Ele usa um PatriciaTrie como ele está fazendo estrutura.

Exemplo usando as seguintes seqüências de caracteres.

1. 10.10.101.2
2. 10.10.100.1
3. 10.10.110.3

Trie exemplo (não comprimido)

└── 1
    └── 0
        └── .
            └── 1
                └── 0
                    └── .
                        └── 1
                            ├── 0
                            │   ├── 1
                            │   │   └── .
                            │   │       └── (2) 10.10.101.2
                            │   └── 0
                            │       └── .
                            │           └── (1) 10.10.100.1
                            └── 1
                                └── 0
                                    └── .
                                        └── (3) 10.10.110.3

Patricia Trie (compactado)

└── [black] 10.10.1
    ├── [black] 0
    │   ├── [white] (0.1) 00.1
    │   └── [white] (1.2) 01.2
    └── [white] (10.3) 10.10.110.3