BK 트리

BK 트리는 월터 오스틴 버크하드와 로버트 M. 켈러에^[1] 의해 제안된 미터법 트리다.단순성을 위해 정수 이산형 메트릭 $d(x,y)$ , y $d(x,y)$ ) $d(x,y)$ 을(를) 고려하십시오 $d(x,y)$ 그러면 BK-tree는 다음과 같은 방법으로 정의된다.임의 요소 a가 루트 노드로 선택된다.루트 노드는 0개 이상의 하위 트리를 가질 수 있다.k-th 하위 트리는 $d(a,b)=k$ ( $d(a,b)=k$ , b $d(a,b)=k$ ) $d(a,b)=k$ = $d(a,b)=k$ $d(a,b)=k$ 과 같은 모든 요소 b로 재귀적으로 구축된다 $d(a,b)=k$ BK-tree는 사전에서 대략적인 문자열 일치를 위해 사용될 수 있다.^[2]^{[example needed]}

예

BK-트리의 예

이 그림은 레벤스테인 거리를 이용하여 얻은 단어 {"책", "책", "케이크", "부", "분", "쿡", "케이크", "케이프", "케이프", "카트"의 $W$ W $W$ 셋트의 BK 트리를 묘사하고 있다.

각 노드 $u$ $u$ 은 $u$ (는) $w_{u}\in W$ $w_{u}\in W$ $w_{u}\in W$ $w_{u}\in W$ ${\displaystyle w_{u}\in W$ ;
각 호 $(u,v)$ , v $(u,v)$ ) ${\displaystyle (u,$ $d_{uv}=d(w_{u},w_{v})$ $)}$ 은(는) d $d_{uv}=d(w_{u},w_{v})$ = d $d_{uv}=d(w_{u},w_{v})$ , $d_{uv}=d(w_{u},w_{v})$ ) ${\displaystyle d_{u}=d(w_{u$ $},$ $w_{$ $v})$ 로 레이블이 지정되며 $(u,v)$ , $w_{u}$ 서 $d_{uv}=d(w_{u},w_{v})$ w는 $w_{u}$ $u$ ${\displaystystyleyle u}$ 에 할당된 단어를 나타낸다 $w_{u}$ $u$

BK 트리는 다음과 같이 제작된다.

BK 트리의 모든 $u$ 노드 $u$ $u$ 에 대해 송신 호에 할당된 중량은 구별된다.
모든 호 $e=(u,v)$ = ( $e=(u,v)$ , $e=(u,v)$ ) ${\$ $displaystyle$ $e=(u,v$ $)}$ 에 $e=(u,v)$ 대해 $k$ $v$ $v'$ 의 $v'$ 각 하위 v $v$ ${\$ v $d(w_{u},w_{v'})=k$ 은 $($ $d(w_{u},w_{v'})=k$ , $d(w_{u},w_{v'})=k$ u $d(w_{u},w_{v'})=k$ ) $=$ {\ $displaystystyle d(w_{u},w_{v$ ') $==}$ k $k$ }:
- 예 1: "책"에서 "책"까지의 호를 고려한다.{"book", "boo", "boon", "cook"}의 "book"과 "cook" 사이의 거리는 1과 같다.
- 예 2: "책"에서 "부"까지의 호를 고려한다.{"boo", "bun", "쿡"}의 "책"과 임의의 단어 사이의 거리는 2와 같다.

삽입

삽입 원시 값은 개별 메트릭 $d$ $d$ 에 따라 $t$ BK 트리 $t$ $t$ 을(를) 채우는 데 사용된다 $d$

입력:

$t$ $[\displaystyle t}$ : BK-트리;
- $d_{uv}$ $d_{uv}$ v ${\$ 는 $d_{uv}$ 호 $(u,v)$ , v $(u,v)$ ) ${\displaystyle(u,v$
- $w_{u}$ $w_{u}$ ${\$ 은(는) 노드 $u$ $u$ 에 할당된 단어를 의미한다 $w_{u}$ . $u$
$d$ $d$ : t $t$ 에서 사용하는 이산형 메트릭( $t$ 예: Levenshtein 거리);
$w$ $w$ : $t$ $t$ 에 삽입할 요소 $t$

출력:

$w$ $w$ 에 해당하는 $t$ $t$ $t$ 의 노드

알고리즘:

$t$ $t$ 이(가) 비어 $t$ 있는 경우:
- $t$ $t$ 에 $r$ 루트 노드 $r$ $r$ 생성
- $w_{r}\왼쪽 화살표 w$
- 반품 $(\displaystyle r}$
$t$ $u$ 을(를) t $t$ 의 루트로 설정하십시오 $u$ .
$u$ $u$ 이(가) 있는 $u$ 동안:
- $k\leftarrow d(w_{u}w)$
- $k=0$ = $k=0$ $k=0$ 인 경우 $k=0$
  - 반품 $(\displaystyle u}$
- $d_{uv}=k$ $d_{uv}=k$ v $d_{uv}=k$ = $d_{uv}=k$ $d_{uv}=k$ 과 $u$ (와) 같은 $u$ $u$ 의 자식 $v$ $v$ $v$ 을(를) 찾으십시오.
- $v$ $v$ 을 $v$ (를) 찾을 수 없는 경우:
  - $노드$ v $v$ 생성
  - $w_{v}\왼쪽 화살표 w$
  - 호 $(u,v)$ , $(u,v)$ ) ${\displaystyle(u,v)}$ 생성
  - $d_{uv}\왼쪽 화살표 k$
  - 반품 $v$
- $왼쪽 화살표로 v}디스플레이 스타일 u\왼쪽 화살표 v}$

찾다

검색 요소 $w$ ${\displaystyle$ w $}$ 을 $w$ 를) 지정하면 조회 원시 요소는 BK-트리를 통과하여 w $w$ 의 가장 가까운 요소를 찾는다 $w$ 핵심 아이디어는 BK 트리 조직과 삼각불평등(컷오프 기준)을 활용해 지금까지 발견된 최고의 후보만을 개선할 수 있는 노드들로 $t$ $t$ ${\디스플레이$ 스타일 $t}$ 탐사를 제한하자는 것이다.

입력:

$t$ $[\displaystyle t}$ : BK-트리;
$d$ $[\displaystyle d}$ : 해당 이산 측정지표(예: 레벤슈테인 거리);
$w$ $w$ : 검색된 요소;
$d_{max}$ $d_{max}$ $d_{max}$ $d_{max}$ ${\$ : $w$ 의 일치와 w $w$ 사이에 허용되는 최대 거리는 + $+\infty$ $+\inft$ 로 기본 설정됨 $+\infty$

출력:

$w_{best}$ b $w_{best}$ s $w_{best}$ ${\$ : $t$ $t$ 에 $t$ 저장되고 $w$ $d$ $d$ 또는 $d$ $\perp$ or $\perp$ 에 $\perp$ 따라 저장된 $w$ $w$ 에 가장 가까운 요소;

알고리즘:

$t$ $t$ 이 $t$ (가) 비어 있는 경우:
- 반품 $\displaystyle \perp }$
$t$ 할 노드 집합의 $S$ $S$ $S$ 을(를) 생성하고 $t$ $t$ 의 루트를 S $S$ 에 $t$ 삽입하십시오 $S$
${\displaystyle(w_{best}d_{best}\좌측 화살표(\perp ,d_{max}})}$
$S\neq \emptyset$ $S\neq \emptyset$ $S\neq \emptyset$ $S\neq \emptyset$ 동안 $S\neq \emptyset$
- $S$ $S$ 에서 $u$ 임의 노드 $u$ $u$ 을(를) 팝업
- $d_{u}\왼쪽 화살표 d(w,w_{u})$
- $d_{u}<d_{best}$ d $d_{u}<d_{best}$ < $d_{u}<d_{best}$ $d_{u}<d_{best}$ $d_{u}<d_{best}$ $d_{u}<d_{best}$ ${\$ :
  - ${\displaystyle(w_{best}d_{best})\좌측 화살표(w_{u}d_{u}}}$
- 각 송신 $(u,v)$ u , $(u,v)$ ) $(u,v)$ 에 대해 $(u,v)$
  - $|d_{uv}-d_{u}|<d_{best}$ $|d_{uv}-d_{u}|<d_{best}$ v $|d_{uv}-d_{u}|<d_{best}$ - d $|d_{uv}-d_{u}|<d_{best}$ < $|d_{uv}-d_{u}|<d_{best}$ $|d_{uv}-d_{u}|<d_{best}$ $|d_{uv}-d_{u}|<d_{best}$ $|d_{uv}-d_{u}|<d_{best}$ ${\$ : (차단 기준)
    - $v$ $v$ 을(를) $S$ $S$ 에 $v$ 삽입하십시오 $S$
반품 $w_{best}$

조회 알고리즘 예제

위에 표시된 8-노드 B-K 트리의 예를 들어 $w=$ = ${\displaystyle$ w $=}$ "cool"을 설정하십시오.트리의 루트를 포함하도록 $S$ $S$ 이(가) 초기화되며 $S$ , 이후 $w_{u}$ ${\$ =" $w_{u}$ book"과 $u$ 함께 $u$ $u$ 의 첫 번째 값으로 펑크가 발생한다.추가 $d_{u}=2$ $d_{u}=2$ = " $d_{u}=2$ "에서 " $cool$ "까지의 거리가 2이므로 2 {\displaystyle $d_{u}=2}$ 이고 $d_{u}=2$ , d $d_{best}=2$ $d_{best}=2$ $d_{best}=2$ = 2 $d_{best}=2$ 이 $d_{best}=2$ (가) 지금까지 발견된 가장 좋은(즉, 가장 작은) 거리인 것이다.다음으로 루트로부터 나가는 각 호를 차례대로 고려한다: "책"에서 "책"까지의 호는 무게가 $|1-2|=1$ 이며, $|1-2|=1$ - $|1-2|=1$ = 1 $1-2 =1$ 이(가) $d_{best}=2$ b $d_{best}=2$ $d_{best}=2$ t $d_{best}=2$ = $d_{best}=2$ ${\displaystyd_{best}=2}$ 보다 $|1-2|=1$ 작기 때문에 $d_{best}=2$ "책"을 포함하는 $S$ 를 S ${\displaystyle$ S}에 삽입하여 추가 $S$ 처리를 한다.The next arc, from "book" to "cake," has weight 4, and since $4-2 =2$ is not less than $d_{best}=2$ , the node containing "cake" is not inserted into $S$ . Therefore the subtree rooted at "cake" will be pruned from the search, as the word closest to "cool"은 해당 하위 트리에 나타날 수 없다.이 가지치기 작업이 올바른 이유를 보려면, "케이크" 하위 트리에 나타나는 $c$ 후보 단어 $c$ $c$ 이(가) 2 - "쿨"을 나타내는 삼각형 불평등을 위반한다는 것을 주목하십시오. 삼각형 불평등은 이 세 개의 숫자 집합에 대해 (삼각형의 측면으로), 두 개의 숫자를 세 번째 숫자 이하로 합칠 수 없지만, 여기서는 디스플레잉을 참조하십시오."cool"에서 "book"(이 2인)까지의 탠스와 "cool"에서 " $c$ " $c$ 까지의 거리 $($ 이 2인 미만 $)$ 는 "book"에서 "cake"(이 4인)까지의 거리에 도달하거나 초과할 수 없다.그러므로 "케이크"에 뿌리를 둔 하위 트리 전체를 무시해도 무방하다.

다음으로 "책"을 포함하는 노드가 $S$ $S$ 에서 $S$ 펑크 났으며, 이제 $d_{u}=3$ $d_{u}=3$ = $d_{u}=3$ ${\displaystyle d_{u}=3$ "쿨"에서 "책"까지의 거리. $d_{u}>d_{best}$ $d_{u}>d_{best}$ > $d_{u}>d_{best}$ $d_{u}>d_{best}$ e $d_{u}>d_{best}$ ${\$ $d_{best}$ $d_{best}$ $d_{best}$ $d_{best}$ $d_{best}$ {\ $displaystyle d_{best}}}$ 는 2로 설정된 $d_{best}$ 상태로 유지되며, "책"을 포함하는 노드의 단일 송신 호를 고려한다.다음으로, "boo"를 포함하는 노드는 "cool"에서 "boo"까지의 $S$ 인 $d_{u}=2$ S $S$ 및 $S$ $d_{u}=2$ = $d_{u}=2$ $d_{u}=2$ 에서 펑크가 난다.이것은 또 다시 dbes 있어=2{\displaystyle d_{최고의}=2에}."야유"에서 각각의 외향적이고 아크 지금으로 간주되면이고,"야유""요긴한 것"에 이르는 아크 무게 1 가지고 있으며, 이후 2− 1=1<>개선되지 않는다;dbes 있어=2{\displaystyle 2=1<, d_{최고의}=2},"요긴한 것"포함에 S{S\displaystyle}. 마찬가지로부터. 2− $|2-2|=0<d_{best}$ = $|2-2|=0<d_{best}$ < $|2-2|=0<d_{best}$ $|2-2|=0<d_{best}$ $|2-2|=0<d_{best}$ $|2-2|=0<d_{best}$ ${\$ "쿡"도 S $S$ 에 추가된다 $S$

마지막으로 $S$ $S$ 의 마지막 두 요소를 임의의 순서로 고려한다 $S$ . "쿡"을 포함하는 노드를 먼저 펑크하여 $d_{best}$ $d_{best}$ $d_{best}$ t $d_{best}$ {\ $displaystyle d_{best}}$ 를 거리 1로 $d_{best}$ 개선한 다음, "분"을 포함하는 노드가 마지막으로 펑크(boon)을 터뜨려 "쿨"과 거리가 2이므로 최상의 r이 개선되지 않는다고 가정한다.esult. 마지막으로, "쿡"은 $d_{best}=1$ $w_{best}$ $w_{best}$ $d_{best}=1$ $w_{best}$ t ${\$ w_{ $best$ $d_{best}=1$ 과(와 $w_{best}$ $)$ $d_{best}=1$ b e s = 1 {\ $displaystyle$ d_ ${best}=1$ }로 반환된다 $d_{best}=1$

참고 항목

Levenshtein 거리 – BK-tree를 만들 때 일반적으로 사용되는 거리 측정 기준
Damerau-Levenshtein 거리 – 전이가 가능한 레벤쉬테인 거리의 변형된 형태

참조

^ W. Burkhard와 R. Keller.CACM, 1973년 최고의 파일 검색 방법
^ R. Baeza-Yates, W. Cunto, U. Manber, S.우. 고정 쿼리 트리를 사용한 근접 일치.M. Crochmore와 D.에서.거스필드, 편집자, 제5회 콤비네이터 패턴 매칭, LNCS 807페이지, 198–212페이지, 아실로마르, CA, 1994년 6월.
^ 리카르도 배자 예이츠와 곤살로 나바로.사전의 빠른 대략적인 문자열 일치.프로크. SPIRE'98

외부 링크

테스트 결과 및 성능 그래프를 포함한 Common Lisp의 BK 트리 구현.
BK-Tree 및 미터법 공간과의 관계에 대한 설명 [3]
C# [4]에서 구현된 BK-Tree에 대한 설명
Lua에서 BK-트리 구현 [5]
Python의 BK 트리 구현 [6]

이 알고리즘이나 데이터 구조와 관련된 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.

[1]

[2]

v t 트리 데이터 구조
나무 검색 (이중 세트/관련 배열)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (최적) 이진 검색 춤 HTree 간격 오더통계 (좌편향) 빨강-검은색 희생양 스플레이 T 트레프 UB 무게균형
힙스	이진수 이항체 브로달 피보나치 좌익 페어링 스큐 판 엠드 보아스 약한
시도하다	씨트리 C-트리(압축 ADT) 해시 라딕스 접미사 3차 검색 X-fast Y-fast
공간 데이터 분할 트리	볼 BK BSP 카르테시안 힐베르트 R k-d(일반적으로 k-d) M 미터법 MVP 옥트리 PH 우선 순위 R 쿼드 R R+ R* 세그먼트 부사장 X
다른 나무들	커버 지수적 펜윅 손가락 프랙탈 트리 지수 퓨전 해시 캘린더 아이 디스턴스 케이애리 왼손잡이 우시블링 링크/컷 로그 구조 병합 머클 p q. 범위 SPQR 톱

Search

BK 트리

네임스페이스

더

목차

예

삽입

찾다

조회 알고리즘 예제

참고 항목

참조

외부 링크