Árvore Burkhard-Keller

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa
Ícone de esboço Este artigo sobre estrutura de dados é um esboço. Você pode ajudar a Wikipédia expandindo-o.


Um árvore Burkhard-Keller ou árvore BK é uma árvore métrica sugerida por Walter Austin Burkhard e Robert Keller[1], especificamente adaptada para espaços métricos discretos. Para simplicidade, vamos considerar uma métrica discreta com inteiros . 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.[1] 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 . Árvores BK podem ser usadas para determinar correspondência aproximada de strings em um dicionário [2]. 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. [1]

Ver também[editar | editar código-fonte]

Referências

  1. a b Nadvorny, César Feijó (2005). TM-tree: um método de acesso para consultas por similaridade (Dissertação de Mestrado). Universidade Federal do Rio Grande do Sul 

Links externos[editar | editar código-fonte]

  • 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)