Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=.
BK stablo, ili Burkhard-Keller stablo, je struktura podataka projektovana za brzo nalaženje najbližeg suseda ili nejasnu pretragu niski (engl. fuzzy string searching), najčešće korišćenu prilikom provere pravopisa (engl. spell-checking). Ovo stablo je prvi put predloženo od strane W. A. Burkhard-a i R. M. Keller-a 1973. godine, u radu "Some approaches to best match file searching", objavljenom u magazinu “Communications of the ACM”.
Pre definisanja BK stabla, potrebno je odrediti nekoliko stvari[1]. Da bi bilo moguće indeksirati i pretraživati neki dati rečnik, potreban je metod poređivanja dve niske. Najčešće korišćen metod je Levenštajnovo rastojanje, koje za date dve niske vraća minimalan broj izmena (umetanja, brisanja ili zamenjivanja slova), potrebnih da se jedna niska pretvori u drugu. Moguće je koristiti i druge metode, dokle god one formiraju metrički prostor.
Iz nejednakosti trouglova vidi se da je put od x do z uvek manji ili jednak bilo kom putu koji prolazi kroz neku dodatnu tačku y.
Neka je dato neko q koje se traži u rečniku, i n koja je najveća dozvoljena daljina između niske q i neke niske koja se stavlja u skup rešenja. Tada, d je razdaljina između niske q i neke nasumično izabrane niske t. Pošto važi nejednakost trouglova, sve niske iz skupa rešenja moraju biti najviše udaljene za d+n izmena, i najmanje za d-n od niske t.
Svaki čvor u BK stablu ima proizvoljan broj čvorova potomaka, i svaka grana ima pridružen broj koji odgovara Levenštajnovom rastojanju između njena dva čvora, odnosno između čvora roditelja i čvora potomka.
Primera radi, ako roditelj čvor ima vrednost “book”, i ima dva čvora potomka “rook” i “nooks”, onda grana između “book” i “rook” će imati vrednost 1, a grana između “book” i “nooks” ce imati vrednost 2.
Prilikom izgradnje stabla, nasumično se izabere neka niska i postavlja se kao koren stabla. Kada se ubacuje nova niska u stablo, meri se Levenštajnovo rastojanje između nove niske i niske korena, tj. d(novaniska, koren) = k. Nova niska se dalje rekurzivno poredi sa čvorom potomkom do kojeg vodi grana sa vrednošću k. Kada se dođe do trenutka da pomenuta grana ne postoji, pravi se novi čvor koji se postavlja kao potomak, i grani koja vodi do njega se daje vrednost Levenštajnovog rastojanja između tog čvora i njegovog roditelja.
Primera radi, kod ubacivanja reči “boon” u prethodno stablo, računa se razdaljina d("book", "boon") = 1. Dalje se ispituje čvor potomak do kojeg vodi grana težine 1, što je u primeru reč “rook”. Računa se daljina d("rook", "boon") = 2, pa se niska “boon” ubacuje kao potomak čvora “rook”, sa težinom grane koja vodi do njega 2.
Prilikom pretrage stabla, računa se Levenštajnovo rastojanje između date niske q i niske korena, tj. d(q, koren) = d i rekurzivno se ispituje svako podstablo do koje vodi grana sa vrednošću između d-n i d+n, inkluzivno. Ako je daljina između čvora koji se ispituje i datog q manja od n, taj čvor (odnosno niska), se dodaje u skup rešenja.
Ovakav algoritam pretraživanja je, okvirno gledano, vremenske složenosti O(log n)[2]. Procenat stabla koje se obilazi se drastično menja u zavisnosti od najveće dozvoljene daljine n, a i zavisi od samih niski koje su u sastavu rečnika.
