Metraipolis › archive › dc_35a2e7ca26b5
BK-tree — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/BK-tree
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-10T17:23:40.601Z
- SHA-256 of the archived text
9cc20be5f1aaab14c0b70ae5358f9ef346f8953001e96fde75aff6db20d5ecd3- Stable URL of this page
https://metraipolis.com/documento/dc_35a2e7ca26b5
How to cite
BK-tree — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/BK-tree (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_35a2e7ca26b5 (Metraipolis archive dc_35a2e7ca26b5, sha256 9cc20be5f1aaab14c0b70ae5358f9ef346f8953001e96fde75aff6db20d5ecd3)
BibTeX
@misc{dc35a2e7ca26b5,
title = {BK-tree — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/BK-tree},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_35a2e7ca26b5; sha256 9cc20be5f1aaab14c0b70ae5358f9ef346f8953001e96fde75aff6db20d5ecd3},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/BK-tree. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
A BK-tree (short for Burkhard-Keller tree) is a metric tree suggested by Walter Austin Burkhard and Robert M. Keller[1] specifically adapted to discrete metric spaces. For simplicity, given a way to measure the distance between any two elements of a set, a BK-tree is built with a single root node and several subtrees, each connected to the root as a child. All nodes in a subtree have an equal distance to the root node, and the edge weight of the edge connecting the subtree to the root is equal to the distance. As shown in the picture. Also, each subtree of a BK-tree is a BK-tree. BK-trees can be used for approximate string matching in a dictionary [2]. The problem is formulated as follows: Given a pattern string P = p 1 p 2 . . . p m {\displaystyle P=p_{1}p_{2}...p_{m}} and a text string T = t 1 t 2 … t n {\displaystyle T=t_{1}t_{2}\dots t_{n}} , we need to find a substring T j ′ , j = t j ′ … t j {\displaystyle T_{j',j}=t_{j'}\dots t_{j}} in T {\displaystyle T} , which, of all substrings of T {\displaystyle T} , has the smallest edit distance to the pattern P {\displaystyle P} . An ordinary way using BK-tree is to insert all Θ ( n 2 ) {\displaystyle \Theta (n^{2})} substrings of T {\displaystyle T} and the pattern string P {\displaystyle P} into the BK-tree, and find the subtree containing nodes with the smallest distance from the root. This will lead to a time complexity of Θ ( n 2 log n ) {\displaystyle \Theta (n^{2}\log n)} . However, this algorithm is very accurate and can find every substrings with the smallest edit distance to P {\displaystyle P} .
Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in inglese, in ordine alfabetico).
Fonte: Wikipedia in inglese, voce «BK-tree» — https://en.wikipedia.org/wiki/BK-tree
Wikidata Q4835786: «tree data structure for metric spaces» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q4835786
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/BK-tree?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1376355969, consultata il 2026-11-10T17:20:49.947Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 74884b3ffb24f338e1b350164cdd41e67897ca728820b272fdec6859e7a2f372