BK-트리 계산기 (유사 문자열 검색)
단어 목록을 편집거리 기준으로 BK-트리에 넣고, 질의어와 허용 편집거리를 주면 트리 가지치기로 유사한 단어를 찾습니다.
"book"에서 편집거리 1 이하
5개
전체 단어 8개 중 5개 노드만 방문해 찾았습니다(가지치기 효과).
book거리 0
boo거리 1
books거리 1
boon거리 1
cook거리 1
가지치기는 삼각부등식 덕분입니다. 편집거리는 거리함수의 조건(d(A,C) ≤ d(A,B)+d(B,C))을 만족합니다. 그래서 어떤 노드의 자식으로 내려갈지 말지를 간선 라벨과 지금까지의 거리 차이만 보고 판단해도, 답을 놓칠 수 없다는 것이 수학적으로 보장됩니다.
같은 단어 집합이라도 입력 순서가 다르면 트리 모양이 달라집니다. 첫 줄의 단어가 항상 뿌리가 됩니다.
사용 방법
- 1한 줄에 하나씩 단어 목록을 입력합니다(넣은 순서대로 트리가 만들어집니다).
- 2질의어와 허용 편집거리(k)를 입력합니다.
- 3트리 가지치기로 찾은 결과와, 실제로 훑은 노드 수(전체 단어 수 대비)를 확인합니다.
자주 묻는 질문
맞춤법 교정기·유사어 검색처럼 "이 단어와 편집거리 k 이하인 단어를 모두 찾아라"는 질의를 빠르게 처리하는 자료구조입니다. 모든 단어와 하나하나 비교하지 않고도 트리 가지치기로 답을 찾습니다.
편집거리는 삼각부등식(d(A,C) ≤ d(A,B)+d(B,C))을 만족하는 거리함수입니다. 이 성질 덕분에 특정 조건을 만족하지 않는 가지는 방문하지 않아도 그 안에 답이 없다는 것이 수학적으로 보장됩니다.
levenshtein-ops는 단어 두 개 사이의 편집거리와 편집 과정 하나를 보여줍니다. 이 도구는 단어 여러 개를 트리로 미리 구성해 두고, 질의 하나로 편집거리 k 이하인 모든 단어를 한 번에 찾는 자료구조+검색 알고리즘입니다.
네. 첫 단어가 뿌리가 되고, 이후 단어는 순서대로 트리에 끼워 넣습니다. 같은 단어 집합이라도 넣는 순서가 다르면 트리 모양이 달라질 수 있습니다(찾는 결과는 항상 같습니다).
알아두면 좋은 점
- 단어는 최대 300개까지 다룹니다. 단어 하나는 최대 60자입니다.
- 입력값은 서버로 전송되지 않습니다. 브라우저에서만 계산됩니다.
함께 보면 좋은 도구
편집 거리 단계두 문자열의 편집 거리를 구하고 어떤 연산을 어느 순서로 하는지 DP 표와 함께 보여 줍니다.AVL 회전숫자를 차례로 넣으며 균형이 무너지는 자리와 그때 하는 회전(LL·RR·LR·RL)을 단계별로 보여 줍니다.gitignore 판정.gitignore 규칙과 경로를 넣으면 그 파일이 무시되는지, 어느 줄이 마지막으로 이겼는지 알려줍니다.울프람 규칙규칙 번호 0~255를 8비트로 풀어 세 칸 이웃에 대응시키고 세대를 쌓아 무늬를 그립니다.2-SAT「둘 중 하나는 참」인 조건을 여럿 넣으면 참·거짓 배정이 가능한지 판정하고 배정을 하나 찾아 줍니다.
마지막 검증: 2026년 9월 3일 · 결과는 참고용 추정치입니다.