Patricia Trie para la recuperación rápida de la dirección IPv4 y los datos de satélite

Question

Estoy escribiendo un programa en C ++ que requiere que las direcciones IP (todo IPv4) se vean y se almacenan de manera rápida. Cada dirección IP tiene datos asociados con ella. En caso de que ya exista en el Trie, tengo la intención de fusionar los datos de la dirección IP en el Trie con los nuevos datos de direcciones. Si no está presente, tengo la intención de agregarlo como una nueva entrada al Trie. La eliminación de la dirección IP no es necesaria.

Para implementar esto, necesito diseñar una Patricia Trie. Sin embargo, no puedo visualizar el diseño más allá de esto. Parece bastante ingenuo de mí, pero la única idea que vino a mi mente era cambiar la dirección IP a su forma binaria y luego usar el Trie. Sin embargo, tengo ni idea de cómo exactamente para implementar esto.

Estaría realmente agradecido si pudieras ayudarme con este. Tenga en cuenta que encontré una pregunta similar aquí . La pregunta o más específicamente, la respuesta fue más allá de mi comprensión, ya que el código en el sitio web de CPAN no estaba lo suficientemente claro para mí.

TAMBIENTE NOTA, Mis datos son el siguiente 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 intenta resolver el problema de encontrar el mejor prefijo de cobertura para una dirección IP determinada (son utilizados por los enrutadores para determinar rápidamente que 192.168.0.0/16 es la mejor opción para 192.168.14.63, por ejemplo).Si solo está tratando de coincidir con las direcciones IP exactamente, una tabla Hash es una mejor opción.

Answer 2

Creo que se está refiriendo a una radixtree .Tengo una implementación de una Radixtrie en Java, si desea usarlo como punto de partida, lo que hace la clave real para valorar el mapeo.Utiliza una Patriciatrie como su estructura de respaldo.

Ejemplo utilizando las siguientes cadenas.

1. 10.10.101.2
2. 10.10.100.1
3. 10.10.110.3

trie ejemplo (sin comprimir)

└── 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 (comprimido)

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