BK-Tree (Burkhard–Keller Tree)
Cuando se realizan búsquedas de strings similares dentro de un texto más grande, suele ocurrir que se puede cometer un typo. A pesar de que este sea mínimo, con los algoritmos tradicionales de búsqueda exacta no funcionan, ya que como lo indica su nombre, solo encuentran coincidencias exactas, y no si tienen mínimos errores de escritura. El BK-Tree (Burkhard–Keller Tree) es una solución eficiente para realizar búsquedas aproximadas en espacios donde los elementos pueden compararse mediante una distancia métrica, como la distancia de Levenshtein (edición).
Descripción
Un BK-Tree es una estructura de datos tipo árbol diseñada para realizar búsquedas aproximadas en un
conjunto de elementos, donde se puede definir una distancia métrica entre cada par. Una métrica es
una función que mide que tan distintos son dos elementos.
Para que sea una métrica válida, debe cumplir tres propiedades fundamentales:
- No negatividad:
dist(a, b) ≥ 0, ydist(a, b) = 0si y solo sia = b. - Simetría:
dist(a, b) = dist(b, a). - Desigualdad triangular:
dist(a, c) ≤ dist(a, b) + dist(b, c).
Estas propiedades garantizan que las distancias tengan un comportamiento coherente, lo que permite realizar búsquedas eficientes.
Estructura del árbol
- Cada nodo almacena un elemento del conjunto (por ejemplo, una palabra).
- Cada arista que conecta un nodo con su hijo está etiquetada con la distancia entre el nodo y el elemento hijo, calculada mediante la métrica.
- Cada nodo puede tener varios hijos, uno por cada valor distinto de distancia.
Implementación
A continuación una implementación en C++ de la estructura descrita.
// C++ program to demonstrate working of BK-Tree
#include "bits/stdc++.h"
using namespace std;
// maximum number of words in dict[]
#define MAXN 100
// defines the tolerance value
#define TOL 2
// defines maximum length of a word
#define LEN 10
struct Node
{
// stores the word of the current Node
string word;
// links to other Node in the tree
int next[2*LEN];
// constructors
Node(string x):word(x)
{
// initializing next[i] = 0
for(int i=0; i<2*LEN; i++)
next[i] = 0;
}
Node() {}
};
// stores the root Node
Node RT;
// stores every Node of the tree
Node tree[MAXN];
// index for current Node of tree
int ptr;
int min(int a, int b, int c)
{
return min(a, min(b, c));
}
// Edit Distance
// Dynamic-Approach O(m*n)
int editDistance(string& a,string& b)
{
int m = a.length(), n = b.length();
int dp[m+1][n+1];
// filling base cases
for (int i=0; i<=m; i++)
dp[i][0] = i;
for (int j=0; j<=n; j++)
dp[0][j] = j;
// populating matrix using dp-approach
for (int i=1; i<=m; i++)
{
for (int j=1; j<=n; j++)
{
if (a[i-1] != b[j-1])
{
dp[i][j] = min( 1 + dp[i-1][j], // deletion
1 + dp[i][j-1], // insertion
1 + dp[i-1][j-1] // replacement
);
}
else
dp[i][j] = dp[i-1][j-1];
}
}
return dp[m][n];
}
// adds curr Node to the tree
void add(Node& root,Node& curr)
{
if (root.word == "" )
{
// if it is the first Node
// then make it the root Node
root = curr;
return;
}
// get its editDistance from the Root Node
int dist = editDistance(curr.word,root.word);
if (tree[root.next[dist]].word == "")
{
/* if no Node exists at this dist from root
* make it child of root Node*/
// incrementing the pointer for curr Node
ptr++;
// adding curr Node to the tree
tree[ptr] = curr;
// curr as child of root Node
root.next[dist] = ptr;
}
else
{
// recursively find the parent for curr Node
add(tree[root.next[dist]],curr);
}
}
vector <string> getSimilarWords(Node& root,string& s)
{
vector < string > ret;
if (root.word == "")
return ret;
// calculating editdistance of s from root
int dist = editDistance(root.word,s);
// if dist is less than tolerance value
// add it to similar words
if (dist <= TOL) ret.push_back(root.word);
// iterate over the string having tolerance
// in range (dist-TOL , dist+TOL)
int start = dist - TOL;
if (start < 0)
start = 1;
while (start <= dist + TOL)
{
vector <string> tmp =
getSimilarWords(tree[root.next[start]],s);
for (auto i : tmp)
ret.push_back(i);
start++;
}
return ret;
}
// driver program to run above functions
int main(int argc, char const *argv[])
{
// dictionary words
string dictionary[] = {"hell","help","shell","smell",
"fell","felt","oops","pop","oouch","halt"
};
ptr = 0;
int sz = sizeof(dictionary)/sizeof(string);
// adding dict[] words on to tree
for(int i=0; i<sz; i++)
{
Node tmp = Node(dictionary[i]);
add(RT,tmp);
}
string w1 = "ops";
string w2 = "helt";
vector < string > match = getSimilarWords(RT,w1);
cout << "similar words in dictionary for : " << w1 << ":\n";
for (auto x : match)
cout << x << endl;
match = getSimilarWords(RT,w2);
cout << "Correct words in dictionary for " << w2 << ":\n";
for (auto x : match)
cout << x << endl;
return 0;
}
Ejemplo
A continuación se presenta un ejemplo adaptado del sitio GeeksforGeeks [1], donde se construye un BK-Tree utilizando la métrica de distancia de edición (Levenshtein) sobre un conjunto de diccionario:
{"hell", "help", "shell", "smell", "fell", "felt", "oops", "pop", "oouch", "halt"}.
La raíz del árbol se inicializa con la palabra "help". Cada palabra restante se inserta calculando
su distancia con respecto a "help" y ubicándola en el hijo correspondiente, de acuerdo con ese
valor.
Por ejemplo:
- dist("help", "hell") = 1, entonces "hell" se ubica como hijo a distancia 1.
- dist("help", "shell") = 2, entonces "shell"` se ubica como hijo a distancia 2.
- dist("help", "halt") = 3, entonces "halt" se ubica como hijo a distancia 3.
Durante una búsqueda aproximada se especifica una palabra de consulta y una tolerancia de error
TOL.
Por ejemplo, si buscamos "oop" con TOL = 2, primero se calcula la distancia con la raíz:
Aplicando la desigualdad triangular, se determina que solo es necesario explorar los subárboles cuyas aristas estén en el rango:
De esta forma, el algoritmo evita visitar ramas cuya distancia de etiqueta esté fuera de ese rango,
reduciendo significativamente el número de comparaciones.
El resultado final de la búsqueda entrega las palabras similares encontradas en el diccionario:
{"oops", "pop"}
Este ejemplo ilustra cómo el BK-Tree permite realizar búsquedas aproximadas eficientes, aprovechando las propiedades métricas para podar ramas y acotar el espacio de búsqueda, sin necesidad de recorrer la totalidad del conjunto.
Complejidad teórica
- Construcción: O(nlog(n)), en caso promedio.
- Búsqueda: para un k pequeño, la complejidad se acerca a O(log(n)). Para un k grande, la complejidad se acerca a O(n).
Aplicaciones
La aplicación más habitual del BK-Tree se encuentra en los sistemas de corrección ortográfica y autocompletado, en los cuales permite sugerir términos cercanos a una palabra ingresada con errores tipográficos. Por ejemplo, puede utilizarse en los autocorrectores de teclado, donde se buscan las palabras más similares a la escrita por el usuario. También se usa mucho en los motores de búsqueda, que ante un error de tipeo presentan el mensaje “también se muestran resultados para...”, ofreciendo coincidencias cercanas a la consulta original. Se adjunta ejemplo en la figura 2.
En términos generales, esta estructura resulta especialmente adecuada cuando se cumplen las siguientes condiciones:
- La métrica utilizada satisface la desigualdad triangular.
- El conjunto de datos es relativamente estático (es decir, las inserciones o eliminaciones son poco frecuentes).
- Las operaciones de búsqueda son considerablemente más comunes que las de actualización.
Gracias a estas características, el BK-Tree constituye una herramienta eficiente y versátil para la búsqueda rápida y tolerante a errores en una amplia variedad de dominios, tales como el procesamiento de texto, la recuperación de información y la comparación de secuencias.
Referencias
[1] GeeksforGeeks. "BK-tree Introduction and Implementation".
Disponible en:
https://www.geeksforgeeks.org/dsa/bk-tree-introduction-implementation/