Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=.
БК стабло, или Буркхард-Келлер стабло, је структура података пројектована за брзо налажење најближег суседа или нејасну претрагу ниски (енгл. фуззy стринг сеарцхинг), најчешће коришћену приликом провере правописа (енгл. спелл-цхецкинг). Ово стабло је први пут предложено од стране W. А. Буркхард-а и Р. M. Келлер-а 1973. године, у раду "Соме аппроацхес то бест матцх филе сеарцхинг", објављеном у магазину “Цоммуницатионс оф тхе АЦМ”.
Пре дефинисања БК стабла, потребно је одредити неколико ствари[1]. Да би било могуће индексирати и претраживати неки дати речник, потребан је метод поређивања две ниске. Најчешће коришћен метод је Левенштајново растојање, које за дате две ниске враћа минималан број измена (уметања, брисања или замењивања слова), потребних да се једна ниска претвори у другу. Могуће је користити и друге методе, докле год оне формирају метрички простор.
Из неједнакости троуглова види се да је пут од x до з увек мањи или једнак било ком путу који пролази кроз неку додатну тачку y.
Нека је дато неко q које се тражи у речнику, и н која је највећа дозвољена даљина између ниске q и неке ниске која се ставља у скуп решења. Тада, д је раздаљина између ниске q и неке насумично изабране ниске т. Пошто важи неједнакост троуглова, све ниске из скупа решења морају бити највише удаљене за д+н измена, и најмање за д-н од ниске т.
Сваки чвор у БК стаблу има произвољан број чворова потомака, и свака грана има придружен број који одговара Левенштајновом растојању између њена два чвора, односно између чвора родитеља и чвора потомка.
Примера ради, ако родитељ чвор има вредност “боок”, и има два чвора потомка “роок” и “ноокс”, онда грана између “боок” и “роок” ће имати вредност 1, а грана између “боок” и “ноокс” це имати вредност 2.
Приликом изградње стабла, насумично се изабере нека ниска и поставља се као корен стабла. Када се убацује нова ниска у стабло, мери се Левенштајново растојање између нове ниске и ниске корена, тј. д(нованиска, корен) = к. Нова ниска се даље рекурзивно пореди са чвором потомком до којег води грана са вредношћу к. Када се дође до тренутка да поменута грана не постоји, прави се нови чвор који се поставља као потомак, и грани која води до њега се даје вредност Левенштајновог растојања између тог чвора и његовог родитеља.
Примера ради, код убацивања речи “боон” у претходно стабло, рачуна се раздаљина д("боок", "боон") = 1. Даље се испитује чвор потомак до којег води грана тежине 1, што је у примеру реч “роок”. Рачуна се даљина д("роок", "боон") = 2, па се ниска “боон” убацује као потомак чвора “роок”, са тежином гране која води до њега 2.
Приликом претраге стабла, рачуна се Левенштајново растојање између дате ниске q и ниске корена, тј. д(q, корен) = д и рекурзивно се испитује свако подстабло до које води грана са вредношћу између д-н и д+н, инклузивно. Ако је даљина између чвора који се испитује и датог q мања од н, тај чвор (односно ниска), се додаје у скуп решења.
Овакав алгоритам претраживања је, оквирно гледано, временске сложености О(лог н)[2]. Проценат стабла које се обилази се драстично мења у зависности од највеће дозвољене даљине н, а и зависи од самих ниски које су у саставу речника.
