PATRICIA – Algoritmo práctico para recuperar información codificada en alfanumérico,D.R.Morrison (1968).
Un árbol PATRICIA está relacionado con unTrie.El problema de los Trie es que cuando el conjunto de claves es escaso,es decir,cuando las claves reales forman un pequeño subconjunto de claves potenciales,como ocurre muy a menudo,muchos (la mayoría de los nodos internos del Trie tienen sólo un descendiente.es decir,cuando las claves reales forman un pequeño subconjunto del conjunto de claves potenciales,como ocurre muy a menudo,muchos (la mayoría) de los nodos internos del Trie tienen un solo descendiente.Esto hace que el Trie tenga una alta complejidad espacial.
Un Trie utiliza cada parte (bit, carácter, …) de la clave, a su vez, para determinar qué subárbol seleccionar.Un árbol PATRICIA en cambio nomina (almacenando su posición en el nodo)qué elemento de la clave se utilizará a continuación para determinar la ramificación.Esto elimina la necesidad de cualquier nodo con un solo descendiente:
El índice de PATRICIA difiere de la estructura de trios binarios de Fredkin en que el índice sólo registra las ramas verdaderas; cuando una frase sólo tiene una extensión correcta, no se registra en el índice.Este hecho reduce el número de filas del índice a sólo el doble del número de inicios, y lo hace independiente de la longitud de las frases almacenadas.
– Morrison 1968 pp520.
Es más fácil crear un árbol PATRICIA para claves (cadenas) sobre un alfabeto de tamaño dos: {a,b}, o {0,1}.Sin embargo, las cadenas sobre un alfabeto de más de dos elementos, por ejemplo ascii, pueden tratarse como cadenas sobre un alfabeto de dos tomando los bits dentro de cada carácter del alfabeto mayor.
El siguiente ejemplo muestra el crecimiento de un árbol PATRICIA bajo una secuencia de inserciones:
C
o
m
p
u
t
e
r
–
S
c
i
e
n
c
e
empty -- initial state
12345 -- number character positionsinsert ababb -- the key
----> ababb
insert ababa; la búsqueda termina en ababb~=ababa;la primera diferencia está en la posición 5, así que…
----> -- i.e. test position #5 . . a. . b . . ababa ababb
insert ba; no tiene la posición #5;puede saltarse las posiciones clave pero debe probar en orden, así que…
--------> . . . . . . ba . . . . . .ababa ababb
insert aaabba; la búsqueda termina en ababb~=aaabba;puede saltar posiciones clave pero debe probar en orden, así que…
--------> . . . . . . ba . . . . . .aaabba . . . . . . ababa ababb
insert ab; ab es también un prefijo de ababa y ababb;debe tener la capacidad de terminar en un nodo intermedio, como con Tries.
-------> . . . . . . ba . . . . . .aaabba --->ab . . . . . . . . . ababa ababb
El tratamiento de una clave, como «ab», que es el prefijo de otra clave, por ejemplo, «ababa», puede ser manejado de varias maneras. Un carácter de terminación real, o ficticio, a menudo denotado como «$» (o «0» en C y sus parientes) puede ser considerado como un tercer carácter en el alfabeto, pero sólo se permite que ocurra en los extremos de las claves.Esta pequeña complicación no surge en el caso especial de que todas las claves tengan la misma longitud.
Notas
- D. R. Morrison.PATRICIA -Practical Algorithm to Retrieve Information Coded in Alphanumeric.Jrnl. of the ACM, 15(4) pp514-534, Oct 1968.
Originalmente presentó PATRICIA como un índice para buscar en texto marcado. - G. H. Gonnet. Handbook of Algorithms and Data Structures.Addison-Wesley, International Computer Series, pp 109, 1984.
Contiene una buena codificación directa de los algoritmosPATRICIA, y de muchos otros.Este libro es un gran recurso. - R. Sedgewick.Algorithms in C. Addison-Wesley, edn 1, pp253, 1990.
Almacena elementos (o punteros a elementos) dentro de nodos internos `fork’. - Ver para la búsqueda de cadenas, etc..