BK-strom - BK-tree

tento článek může být pro většinu čtenářů příliš technická na to, aby je pochopili. Prosím pomozte to vylepšit na aby to bylo srozumitelné pro neodborníky, aniž by byly odstraněny technické podrobnosti. (Březen 2019) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

A BK-strom je metrický strom navrhl Walter Austin Burkhard a Robert M. Keller^[1] speciálně upraveno pro diskrétní metrické prostory Pro jednoduchost zvažte celé číslo diskrétní metrika ${ displaystyle d (x, y)}$. Potom je BK-strom definován následujícím způsobem. Libovolný prvek A je vybrán jako kořenový uzel. Kořenový uzel může mít nulový nebo více podstromů. The k-tý podstrom je rekurzivně sestaven ze všech prvků b takhle ${ displaystyle d (a, b) = k}$. Lze použít BK-stromy přibližná shoda řetězců ve slovníku.^{[2][potřebný příklad ]}

Viz také

• Levenshteinova vzdálenost - metrika vzdálenosti běžně používaná při stavbě stromu BK
• Vzdálenost Damerau – Levenshtein - upravená forma vzdálenosti Levenshtein, která umožňuje transpozice

Reference

• ^ W. Burkhard a R. Keller. Některé přístupy k vyhledávání souborů s nejlepší shodou, CACM, 1973
• ^ R. Baeza-Yates, W. Cunto, U. Manber a S. Wu. Proximity matching using fixed queries trees. In M. Crochemore a D. Gusfield, redaktoři, 5th Combinatorial Pattern Matching, LNCS 807, strany 198–212, Asilomar, CA, červen 1994.
• ^ Ricardo Baeza-Yates a Gonzalo Navarro. Rychlé přibližné porovnávání řetězců ve slovníku. Proc. SPIRE'98

externí odkazy

• Implementace BK-stromu v Společný Lisp s výsledky testů a grafy výkonu.
• Vysvětlení stromů BK a jejich vztahu k metrickým prostorům [3]
• Vysvětlení stromů BK s implementací v C #[4]
• Implementace BK-stromu v Lua [5]
• Implementace BK-stromu v Krajta [6]

Tento algoritmy nebo datové struktury související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.