Un árbol BK es un árbol métrico sugerido por Walter Austin Burkhard y Robert M. Keller [1] específicamente adaptado a espacios métricos discretos . Para simplificar, considere métricas discretas enteras. Entonces, BK-tree se define de la siguiente manera. Se selecciona un elemento arbitrario a como nodo raíz. El nodo raíz puede tener cero o más subárboles. El subárbol k-ésimo se construye recursivamente con todos los elementos b de manera que. Los árboles BK se pueden utilizar para la coincidencia aproximada de cadenas en un diccionario. [2] [ ejemplo necesario ]
Ejemplo
Esta imagen muestra el árbol BK para el set. de palabras {"libro", "libros", "pastel", "boo", "bendición", "cocinar", "pastel", "capa", "carrito"} obtenidas mediante la distancia de Levenshtein
- cada nodo está etiquetado por una cadena de ;
- cada arco está etiquetado por dónde denota la palabra asignada a .
El árbol BK está construido para que:
- para todos los nodos del árbol BK, el peso asignado a sus arcos de salida es distinto;
- para todo el arco etiquetado por , cada descendiente de satisface la siguiente ecuación: :
- Ejemplo 1: considere el arco de "libro" a "libros". La distancia entre "libro" y cualquier palabra en {"libros", "boo", "boon", "cook"} es igual a 1;
- Ejemplo 2: Considere el arco de "libros" a "boo". La distancia entre "libros" y cualquier palabra en {"boo", "boon", "cook"} es igual a 2.
Inserción
La primitiva de inserción se usa para poblar un árbol BK según una métrica discreta .
Aporte:
- : el árbol BK;
- denota el peso asignado a un arco ;
- denota palabra asignada a un nodo );
- : la métrica discreta utilizada por (por ejemplo, la distancia de Levenshtein );
- : el elemento a insertar en ;
Producción:
- El nodo de correspondiente a
Algoritmo:
- Si el esta vacio:
- Crea un nodo raíz en
- Regreso
- Colocar a la raíz de
- Tiempo existe:
- Si :
- Regreso
- Encontrar el hijo de tal que
- Si no se encuentra:
- Crea el nodo
- Crea el arco
- Regreso
Buscar
Dado un elemento buscado , la primitiva de búsqueda atraviesa el árbol BK para encontrar el elemento más cercano de . La idea clave es restringir la exploración de a nodos que solo pueden mejorar al mejor candidato encontrado hasta ahora aprovechando la organización del árbol BK y la desigualdad del triángulo (criterio de corte).
Aporte:
- : el árbol BK;
- : la métrica discreta correspondiente (por ejemplo, la distancia de Levenshtein );
- : el elemento buscado;
- : la distancia máxima permitida entre la mejor coincidencia y , por defecto es ;
Producción:
- : el elemento más cercano a guardado en y de acuerdo a o si no se encuentra;
Algoritmo:
- Si esta vacio:
- Regreso
- Crear un conjunto de nodos para procesar e insertar la raíz de dentro .
- Tiempo :
- Pop un nodo arbitrario de
- Si :
- Para cada arco de salida:
- Si : (criterio de corte)
- Insertar dentro .
- Si : (criterio de corte)
- Regreso
Ver también
- Distancia de Levenshtein : la métrica de distancia que se usa comúnmente al construir un árbol BK
- Distancia de Damerau-Levenshtein : una forma modificada de la distancia de Levenshtein que permite transposiciones
Referencias
- ^ W. Burkhard y R. Keller. Algunos enfoques para la búsqueda de archivos con las mejores coincidencias, CACM, 1973
- ^ R. Baeza-Yates, W. Cunto, U. Manber y S. Wu. Coincidencia de proximidad mediante árboles de consultas fijas. En M. Crochemore y D. Gusfield, editores, 5th Combinatorial Pattern Matching, LNCS 807, páginas 198–212, Asilomar, CA, junio de 1994.
- ^ Ricardo Baeza-Yates y Gonzalo Navarro. Coincidencia de cadenas aproximada rápida en un diccionario. Proc. SPIRE'98
enlaces externos
- Una implementación de árbol BK en Common Lisp con resultados de pruebas y gráficos de rendimiento.
- Una explicación de BK-Trees y su relación con los espacios métricos [3]
- Una explicación de BK-Trees con una implementación en C # [4]
- Una implementación de árbol BK en Lua [5]
- Una implementación de árbol BK en Python [6]