árbol BK

Un árbol BK es un árbol métrico sugerido por Walter Austin Burkhard y Robert M. Keller ^[1] adaptado específicamente a espacios métricos discretos . Para simplificar, considere la métrica discreta entera . Entonces, el árbol BK 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 k-ésimo subárbol se construye recursivamente de todos los elementos b tales que . Los árboles BK se pueden usar para la coincidencia aproximada de cadenas en un diccionario. ^{[2] [ ejemplo necesario ]}${\displaystyle d(x,y)}$${\displaystyle d(a,b)=k}$

Esta imagen muestra el árbol BK para el conjunto de palabras {"book", "books", "cake", "boo", "boon", "cook", "cake", "cape", "cart"} obtenido mediante el uso de la distancia de Levenshtein.${\displaystyle W}$

• Cada nodo está etiquetado por una cadena de ;${\displaystyle u}$${\displaystyle w_{u}\in W}$
• Cada arco está etiquetado por donde denota la palabra asignada a .${\displaystyle (u,v)}$${\displaystyle d_{uv}=d(w_{u},w_{v})}$${\displaystyle w_{u}}$${\displaystyle u}$

El árbol BK está construido de manera que:

• Para cada nodo del árbol BK, el peso asignado a sus arcos de salida es distinto;${\displaystyle u}$
• Para todo arco etiquetado por , cada descendiente de satisface la siguiente ecuación: : ${\displaystyle e=(u,v)}$${\displaystyle k}$${\displaystyle v'}$${\displaystyle v}$${\displaystyle d(w_{u},w_{v'})=k}$
  • Ejemplo 1: Considere el arco que va desde "book" hasta "books". La distancia entre "book" y cualquier palabra en {"books", "boo", "boon", "cook"} es igual a 1;
  • Ejemplo 2: Considere el arco que va desde "books" hasta "boo". La distancia entre "books" y cualquier palabra en {"boo", "boon", "cook"} es igual a 2.

La primitiva de inserción se utiliza para rellenar un árbol BK de acuerdo con una métrica discreta . ${\displaystyle t}$${\displaystyle d}$

Aporte:

• ${\displaystyle t}$:el árbol BK;
  • ${\displaystyle d_{uv}}$denota el peso asignado a un arco ;${\displaystyle (u,v)}$
  • ${\displaystyle w_{u}}$denota palabra asignada a un nodo ;${\displaystyle u}$
• ${\displaystyle d}$:la métrica discreta utilizada por (por ejemplo, la distancia de Levenshtein );${\displaystyle t}$
• ${\displaystyle w}$:el elemento que se insertará en ;${\displaystyle t}$

Producción:

• El nodo correspondiente a${\displaystyle t}$${\displaystyle w}$

Algoritmo:

• Si está vacío: ${\displaystyle t}$
  • Crear un nodo raíz en${\displaystyle r}$${\displaystyle t}$
  • ${\displaystyle w_{r}\leftarrow w}$
  • Devolver ${\displaystyle r}$
• Establecer en la raíz de${\displaystyle u}$${\displaystyle t}$
• Mientras exista: ${\displaystyle u}$
  • ${\displaystyle k\leftarrow d(w_{u},w)}$
  • Si : ${\displaystyle k=0}$
    • Devolver ${\displaystyle u}$
  • Encuentra el hijo de tal que${\displaystyle v}$${\displaystyle u}$${\displaystyle d_{uv}=k}$
  • Si no se encuentra: ${\displaystyle v}$
    • Crear el nodo${\displaystyle v}$
    • ${\displaystyle w_{v}\leftarrow w}$
    • Crea el arco${\displaystyle (u,v)}$
    • ${\displaystyle d_{uv}\leftarrow k}$
    • Devolver ${\displaystyle v}$
  • ${\displaystyle u\leftarrow v}$

Dado un elemento buscado , la primitiva de búsqueda recorre el árbol BK para encontrar el elemento más cercano de . La idea clave es restringir la exploración de a los nodos que solo pueden mejorar el mejor candidato encontrado hasta el momento aprovechando la organización del árbol BK y la desigualdad triangular (criterio de corte). ${\displaystyle w}$${\displaystyle w}$${\displaystyle t}$

Aporte:

• ${\displaystyle t}$:el árbol BK;
• ${\displaystyle d}$:la métrica discreta correspondiente (por ejemplo, la distancia de Levenshtein );
• ${\displaystyle w}$:el elemento buscado;
• ${\displaystyle d_{max}}$:la distancia máxima permitida entre la mejor coincidencia y , el valor predeterminado es ;${\displaystyle w}$${\displaystyle +\infty }$

Producción:

• ${\displaystyle w_{best}}$:el elemento más cercano a almacenado en y según o si no se encuentra;${\displaystyle w}$${\displaystyle t}$${\displaystyle d}$${\displaystyle \perp }$

Algoritmo:

• Si está vacío: ${\displaystyle t}$
  • Devolver ${\displaystyle \perp }$
• Cree un conjunto de nodos para procesar e inserte la raíz de en .${\displaystyle S}$${\displaystyle t}$${\displaystyle S}$
• ${\displaystyle (w_{best},d_{best})\leftarrow (\perp ,d_{max})}$
• Mientras : ${\displaystyle S\neq \emptyset }$
  • Extraer un nodo arbitrario de${\displaystyle u}$${\displaystyle S}$
  • ${\displaystyle d_{u}\leftarrow d(w,w_{u})}$
  • Si : ${\displaystyle d_{u}<d_{best}}$
    • ${\displaystyle (w_{best},d_{best})\leftarrow (w_{u},d_{u})}$
  • Para cada arco de salida : ${\displaystyle (u,v)}$
    • Si : (criterio de corte) ${\displaystyle |d_{uv}-d_{u}|<d_{best}}$
      • Insertar en .${\displaystyle v}$${\displaystyle S}$
• Devolver ${\displaystyle w_{best}}$

Considere el ejemplo de árbol BK de 8 nodos que se muestra arriba y configure "cool". se inicializa para que contenga la raíz del árbol, que posteriormente se extrae como el primer valor de con ="book". Además, dado que la distancia de "book" a "cool" es 2, y como esta es la mejor (es decir, la más pequeña) distancia encontrada hasta ahora. A continuación, se considera cada arco saliente desde la raíz por turno: el arco de "book" a "books" tiene peso 1, y como es menor que , el nodo que contiene "books" se inserta en para su posterior procesamiento. El siguiente arco, de "book" a "cake", tiene peso 4, y como no es menor que , el nodo que contiene "cake" no se inserta en . Por lo tanto, el subárbol enraizado en "cake" se podará de la búsqueda, ya que la palabra más cercana a "cool" no puede aparecer en ese subárbol. Para ver por qué esta poda es correcta, observe que una palabra candidata que aparece en el subárbol "cake" y que tiene una distancia menor que 2 a "cool" violaría la desigualdad triangular: la desigualdad triangular requiere que para este conjunto de tres números (como lados de un triángulo), ningún par puede sumar menos que el tercero, pero aquí la distancia de "cool" a "book" (que es 2) más la distancia de "cool" a (que es menor que 2) no puede alcanzar o superar la distancia de "book" a "cake" (que es 4). Por lo tanto, es seguro ignorar todo el subárbol enraizado en "cake". ${\displaystyle w=}$${\displaystyle S}$${\displaystyle u}$${\displaystyle w_{u}}$${\displaystyle d_{u}=2}$${\displaystyle d_{best}=2}$${\displaystyle |1-2|=1}$${\displaystyle d_{best}=2}$${\displaystyle S}$${\displaystyle |4-2|=2}$${\displaystyle d_{best}=2}$${\displaystyle S}$${\displaystyle c}$${\displaystyle c}$

A continuación, se extrae el nodo que contiene "libros" de y ahora , la distancia de "genial" a "libros". Como , permanece establecido en 2 y se considera el único arco saliente del nodo que contiene "libros". A continuación, se extrae el nodo que contiene "buuu" de y , la distancia de "genial" a "buuu". Esto tampoco mejora . Ahora se considera cada arco saliente de "buuu"; el arco de "buuu" a "bendición" tiene peso 1, y como , "bendición" se suma a . De manera similar, como , "cocinar" también se suma a . ${\displaystyle S}$${\displaystyle d_{u}=3}$${\displaystyle d_{u}>d_{best}}$${\displaystyle d_{best}}$${\displaystyle S}$${\displaystyle d_{u}=2}$${\displaystyle d_{best}=2}$${\displaystyle |2-1|=1<d_{best}=2}$${\displaystyle S}$${\displaystyle |2-2|=0<d_{best}}$${\displaystyle S}$

Finalmente, cada uno de los dos últimos elementos en se considera en orden arbitrario: supongamos que el nodo que contiene "cook" se elimina primero, mejorando a la distancia 1, luego el nodo que contiene "boon" se elimina por último, que tiene una distancia de 2 de "cool" y, por lo tanto, no mejora el mejor resultado. Finalmente, "cook" se devuelve como la respuesta con . ${\displaystyle S}$${\displaystyle d_{best}}$${\displaystyle w_{best}}$${\displaystyle d_{best}=1}$

• Distancia de Levenshtein : la métrica de distancia que se usa comúnmente al construir un árbol BK
• Distancia Damerau-Levenshtein : una forma modificada de la distancia de Levenshtein que permite transposiciones

• ^ W. Burkhard y R. Keller. Algunos enfoques para la búsqueda de archivos con la mejor coincidencia, 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. Correspondencia rápida aproximada de cadenas en un diccionario. Proc. SPIRE'98

• Una implementación de árbol BK en Common Lisp con resultados de pruebas y gráficos de rendimiento.
• Una explicación de los árboles BK y su relación con los espacios métricos [3]
• Una explicación de los árboles BK 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]