Algoritmo/pasos para encontrar la búsqueda del prefijo más largo en Patricia Trie

Question

Estoy implementando Patricia intentos para la búsqueda de prefijo IP, podría hacer que el código funcione para una coincidencia de teclas completa, pero enfrentando problemas con la búsqueda de prefijo, cuando hay claves que son prefijos de otras claves, como:

1.2.3.0
1.2.0.0

¿Alguien puede ayudarme con el algoritmo para las búsquedas de prefijo en el caso anterior debería considerarlas como claves de longitud separada (es decir, /24 y 16)?

Answer 1

Tome un vistazo a Net-Patricia. Esta es una implementación de un trie Patricia para buscar direcciones IP. La interfaz es Perl, pero el código subyacente es en C. Aquí hay un enlace, pero muchos archivos CPAN debería tenerlo:

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

Answer 2

Si utiliza este intento para almacenar números IP como elementos de longitud fija, definitivamente no es la forma correcta.El punto aquí es que PT es especialmente útil para almacenar datos de longitud variable.

Si almacena partes de números IP, como prefijos de longitud variable, PT es una buena opción.
En este caso, sí, las llaves deben tener una longitud diferente.
Digamos que está almacenando el prefijo "192.168" en binario 0xC0 0xA8, agrega esto como primera clave.
Luego, al buscar una IP como 192.168.1.1, puede obtener información de que su trie contiene 192.168, que es un prefijo de lo que busca.

Todo lo que tienes que hacer es almacenar la "parte común" mientras atraviesas el intento.
Esta es una adición menor a la este implementación.Solo asegúrese de que mientras baja por el intento almacene la parte común en algún lugar de los parámetros de la función recursiva.
Para una buena comprensión de Patricia Trie, sugeriría leer. Libro de algoritmos de Robert Sedgewick que es una gran fuente de conocimiento.

EDITAR:Hay un problema al almacenar cadenas C en PT.Este intento está diseñado para almacenar datos binarios, pero solo le interesa obtener los bytes completos.Asegúrese de almacenar la parte común del prefijo solo si su tamaño en bits es múltiplo de 8.Para un ejemplo equivocado:tienes la clave en tu árbol:0xC0 0xA5 y estás buscando 0xC0 0xA6.Su recorrido se detendrá cuando la parte común sea "0xC0 0xA", pero le interesa tomar solo "0xC0".Así que asegúrese de almacenar bytes comunes, no bits.

Answer 3

Hay una implementación C bastante legible en el código de prueba para LLVM: https://llvm.org/svn/llvm-project/test-suite/trunk/MultiSource/Benchmarks/MiBench/network-patricia/