BK ағашы: жақын тіркес іздеу алгоритмі

Кіріспе

BK ағашы – Уолтер Остин Беркхард пен Роберт М. Келлер ұсынған, дискретті метрикалық кеңістіктерге арнайы бейімделген метрикалық ағаш. Түсіну үшін, бүтін сандық дискретті метриканы қарастырайық. Онда BK ағашы былай анықталады: кез келген элемент a тамыр түйіні ретінде таңдалады. Тамыр түйінінде нөл немесе одан көп кіші ағаштар болуы мүмкін. k-шы кіші ағаш, BK ағаштарын сөздікте шамамен тізбектерді сәйкестендіру үшін қолдануға болады, сондықтан барлық b элементтерінен рекурсивті түрде құрылады.

Іздеу алгоритмінің үлгісі

Жоғарыда көрсетілген 8 түйінді B K ағашын қарастырып, "cool" деп қойыңыз. бастапқыда ағаштың түбірімен толтырылады, содан кейін ол with ="book" -тің бірінші мәні ретінде алынады. Әрі, "book" пен "cool" арасындағы қашықтық 2 болғандықтан және бұл осы уақытқа дейін табылған ең жақсы (яғни ең кіші) қашықтық болғандықтан. Келесіде, түбірден шығатын әр доға кезекпен қарастырылады: "book" пен "books" арасындағы доғаның салмағы 1, және кіші болғандықтан, "books" түйіні одан әрі өңдеу үшін қосылады. Келесі доға, "book" пен "cake" арасындағысы, салмағы 4, және кем емес болғандықтан, "cake" түйіні қосылмайды. Сондықтан "cake" түбіріндегі кіші ағаш іздеуден алынып тасталады, себебі "cool" сөзіне ең жақын сөз сол кіші ағашта болуы мүмкін емес. Бұл алынып тастаудың дұрыс екенін түсіну үшін, "cake" кіші ағашындағы кез келген сөздің "cool" сөзінен 2-ден кем қашықтықта болуы үшбұрыш теңсіздігін бұзатынын ескеріңіз: үшбұрыш теңсіздігі бойынша үш санның (үшбұрыштың қабырғалары ретінде) екісінің қосындысы үшіншісінен кем болмауы керек, бірақ мұнда "cool" мен "book" арасындағы қашықтық (2) және "cool" мен арасындағы қашықтық (2-ден кем) "book" пен "cake" арасындағы қашықтықтан (4) кем болуы мүмкін емес. Сондықтан "cake" түбіріндегі бүкіл ағашты елемеуге болады. Келесіде "books" түйіні алынып, енді "cool" мен "books" арасындағы қашықтық болады. 2 болып қалады және "books" түйінінен шығатын жалғыз доға қарастырылады. Содан кейін "boo" түйіні алынып, "cool" мен "boo" арасындағы қашықтық болады. Бұл да жақсартпайды. "boo" түйінінен шығатын әр доға қарастырылады; "boo" мен "boon" арасындағы доғаның салмағы 1, және болғандықтан, "boon" қосылады. Сол сияқты, болғандықтан, "cook" та қосылады. Соңында элементтерінің соңғы екеуі кездейсоқ тәртіппен қарастырылады: егер "cook" түйіні бірінші болып алынса, қашықтық 1-ге дейін жақсарады, содан кейін "boon" түйіні соңғы болып алынады, ол "cool" сөзінен 2 қашықтықта болады және ең жақсы нәтижеге жетпейді. Соңында "cook" жауап ретінде қайтарылады, қашықтығы .

Consider the example 8 node B K Tree shown above and set "cool". is initialized to contain the root of the tree, which is subsequently popped as the first value of with ="book". Further since the distance from "book" to "cool" is 2, and as this is the best (i. e. smallest) distance found thus far. Next each outgoing arc from the root is considered in turn: the arc from "book" to "books" has weight 1, and since is less than , the node containing "books" is inserted into for further processing. The next arc, from "book" to "cake," has weight 4, and since is not less than , the node containing "cake" is not inserted into Therefore, the subtree rooted at "cake" will be pruned from the search, as the word closest to "cool" cannot appear in that subtree. To see why this pruning is correct, notice that a candidate word appearing in "cake"s subtree having distance less than 2 to "cool" would violate the triangle inequality: the triangle inequality requires that for this set of three numbers (as sides of a triangle), no two can sum to less than the third, but here the distance from "cool" to "book" (which is 2) plus the distance from "cool" to (which is less than 2) cannot reach or exceed the distance from "book" to "cake" (which is 4). Therefore, it is safe to disregard the entire subtree rooted at "cake". Next the node containing "books" is popped from and now , the distance from "cool" to "books." As , remains set at 2 and the single outgoing arc from the node containing "books" is considered. Next, the node containing "boo" is popped from and , the distance from "cool" to "boo." This again does not improve upon Each outgoing arc from "boo" is now considered; the arc from "boo" to "boon" has weight 1, and since , "boon" is added to Similarly, since , "cook" is also added to
Finally each of the two last elements in are considered in arbitrary order: suppose the node containing "cook" is popped first, improving to distance 1, then the node containing "boon" is popped last, which has distance 2 from "cool" and therefore does not improve the best result. Finally, "cook" is returned as the answer with .