BK 트리1 버크하드-켈러 트리(Burkhard-Keller Tree) 본 분서는 http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees의 내용을 번역한 것이다. BK-트리, 또는 버크하드-켈러 트리는 트리 기반의 구조로 주어진 문자열에 대한 빠른 근사 매치를 하도록 해준다. 예를 들어, 스펠링 검사기나 '퍼지(유사어)' 검색을 수행하는 등의 작업에 사용된다. 더 자세히 예를 들자면, "aeek"를 검색하는데 이와 유사한 "seek"과 "peek"의 단어들이 반환되는 것이 목적이다. 무엇이 BK-트리를 빛나게 하냐면, 단순 무식한 무작위 검색 방식(brute-force search) 외에는 뾰족한 검색 방법이 없는 문제가 있을 때, 검색 속도를 엄청나게 향상시킬 수 있는 단순하고 우아한 방법을 제공해 주기 때문.. 2012. 11. 27. 이전 1 다음