Árvore Burkhard-Keller

Um árvore Burkhard-Keller ou árvore BK é uma árvore métrica sugerida por Walter Austin Burkhard e Robert Keller, especificamente adaptada para espaços métricos discretos. Para simplicidade, vamos considerar uma métrica discreta com inteiros $d(x,y)$. Em seguida, uma árvore BK é definida da seguinte maneira. Um elemento arbitrário a é escolhido como nó raiz. Então, é usada uma função de distância que retorna um valor discreto para particionar os demais objetos do universo. O nó raiz pode ter zero ou mais subárvores. A k-ésima subárvore é recursivamente construída a partir de todos os elementos de b tais que $d(a,b)=k$. Árvores BK podem ser usadas para determinar correspondência aproximada de strings em um dicionário . Existem variações dessa árvore, por exemplo, pode-se fazer a restrição de que todos pivôs de um mesmo nı́vel na árvore sejam o mesmo objeto.

Ver também

• Distância Levenshtein – a distância métrica comumente utilizada durante a criação de uma árvore BK

Referências

• ↑ W. Burkhard and R. Keller. Some approaches to best-match file searching, CACM, 1973
• ↑ R. Baeza-Yates, W. Cunto, U. Manber, and S. Wu. Proximity matching using fixed queries trees. In M. Crochemore and D. Gusfield, editors, 5th Combinatorial Pattern Matching, LNCS 807, pages 198–212, Asilomar, CA, June 1994.
• ↑ Ricardo Baeza-Yates and Gonzalo Navarro. Fast Approximate String Matching in a Dictionary. Proc. SPIRE'98

Ligações externas

• Implementação em Common Lisp (em inglês) de uma árvore BK com os resultados dos testes e gráficos de desempenho.
• Uma explicação de Árvores BK e a sua relação com espaços métrica [3] (em inglês)
• Uma explicação sobre Árvores BK, com uma implementação em C#[4] (em inglês)
• Implementação de uma árvore BK em Lua [5] (em inglês)