Day 149-Q2 — BK-tree（Burkhard-Keller Tree・編集距離の三角不等式による距離空間探索木）

2026-09-10 赤色 Master / Phase 8+ ★★★★★★★★★ 親からの編集距離をラベルとする子を持ち、三角不等式で近似文字列検索を枝刈りする

問題

英小文字の単語が追加順に N 個与えられる。編集距離（レーベンシュタイン距離）edit(a,b)を使い、以下の手順で BK-tree を構築せよ。

構築手順

  1. 1番目の単語を根とする。
  2. 2番目以降の単語 w について、根から d = edit(node.word, w) を計算。d==0なら何もしない。ラベルdの子が既存ならそこへ移動して繰り返す。無ければラベルdの新規子として追加する。

クエリ処理

visited = 0
stack = [root]
結果 = []
while stack:
    node = stack.pop(); visited += 1
    d = edit(node.word, Q)
    if d <= tau: 結果に追加
    for label, child in node.children:
        if d - tau <= label <= d + tau:  # 三角不等式による枝刈り
            stack.push(child)

入力形式

N
w_1
:
w_N
Q_word tau

制約

$2 \le N \le 10$
単語は小文字英字のみ、長さ$1$〜$8$
$0 \le \tau \le 4$
単語リストに重複なし

入出力例

入力例1

7
book
books
cake
boo
boot
cape
cart
bo 2

出力例1

3
boo 1
book 2
boot 2
6

1行目: 条件を満たす単語数。続く行: 単語と距離を辞書順に。最終行: visited（訪問ノード数）。

概念図：構築されたBK-treeとクエリ "bo" (τ=2) の探索

挿入順: book, books, cake, boo, boot, cape, cart book 1 books 4 cake 2 boo 1 cape 1 cart 2 赤い経路 = クエリ"bo"で辿るノード(d(book,bo)=2→ラベル[0,4]全て候補、d(boo,bo)=1→ラベル[-1,3]でboot(1)のみ) cake側はd(book,cake)=4がラベル範囲[0,4]内で訪問対象、cape/cartはさらにcakeとの距離で絞られる

ヒント（段階的開示）

ヒント1（方向性）

BK-treeは似た単語ほど木の中で近くに配置される。親からの子への辺ラベルが編集距離そのものであり、編集距離が三角不等式を満たすために成立する。

ヒント2（アプローチ）

クエリQで今のノードとの距離がdのとき、三角不等式からedit(Q,child)>=|d-label|が言える。edit(Q,child)<=τになり得るのは|d-label|<=τのときだけなので、範囲外の子は探索不要。

ヒント3（誘導） 
def edit_distance(a, b):
    n, m = len(a), len(b)
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(n+1): dp[i][0] = i
    for j in range(m+1): dp[0][j] = j
    for i in range(1, n+1):
        for j in range(1, m+1):
            cost = 0 if a[i-1]==b[j-1] else 1
            dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+cost)
    return dp[n][m]

模範解答 (Python)

import sys


def edit_distance(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = i
    for j in range(m + 1):
        dp[0][j] = j
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            cost = 0 if a[i - 1] == b[j - 1] else 1
            dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + cost)
    return dp[n][m]


class BKNode:
    __slots__ = ('word', 'children')

    def __init__(self, word):
        self.word = word
        self.children = {}


def bk_insert(root, word):
    if root is None:
        return BKNode(word)
    node = root
    while True:
        d = edit_distance(node.word, word)
        if d == 0:
            return root
        if d in node.children:
            node = node.children[d]
        else:
            node.children[d] = BKNode(word)
            return root


def bk_search(root, query, tau):
    visited = 0
    results = []
    stack = [root]
    while stack:
        node = stack.pop()
        visited += 1
        d = edit_distance(node.word, query)
        if d <= tau:
            results.append((node.word, d))
        for label, child in node.children.items():
            if d - tau <= label <= d + tau:
                stack.append(child)
    return sorted(results), visited


def main():
    data = sys.stdin.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    words = []
    for _ in range(N):
        words.append(data[idx]); idx += 1
    query = data[idx]; idx += 1
    tau = int(data[idx]); idx += 1

    root = None
    for w in words:
        root = bk_insert(root, w)

    results, visited = bk_search(root, query, tau)
    out = [str(len(results))]
    for w, d in results:
        out.append(f"{w} {d}")
    out.append(str(visited))
    print('\n'.join(out))


main()

Step-by-Step 解説

1編集距離を三角不等式に使う
編集距離が距離の公理を満たすことに依存し、挿入時に既存ラベルと一致すればそこへ合流させ似た単語同士を同じ部分木にまとめる。
2挿入は決定的な1本道
根から「ラベルが一致する子があればそこへ」を繰り返し、なければ新規追加して終了する。
3枝刈り条件の導出
三角不等式から$|edit(a,b)-edit(b,c)|\le edit(a,c)$が導け、$a=Q,b=node,c=child$とすると枝刈り条件$|d-label|\le\tau$が得られる。
4訪問数で効果を確認
愚直探索なら$visited=N$だが、枝刈りが効くと$visited<N$。入力例1では$N=7$に対し$visited=6$。

よくあるミス

ミス原因正しい書き方
重複語を新規ノードとして追加d==0の判定漏れd==0なら何もせず終了
枝刈り範囲を[0,τ]にしてしまう三角不等式の意味を誤解範囲はdを中心とした幅2τの区間[d-τ,d+τ]
visitedを結果数と混同訪問数と一致数を取り違えるvisitedはpop回数でカウント
挿入前に単語をソートしてしまう木の形が挿入順依存であることを見落とす与えられた順のまま挿入する
結果の出力順をソートし忘れる探索順は辞書順と一致しない結果は単語の辞書順にソートしてから出力

次のステップ

  • 発展: 本問では編集距離をそのつど$O(len^2)$で計算し直したが、実運用ではLevenshtein Automatonなどで距離計算自体を高速化する余地がある。
  • 次回予告: Union-Find with Rollback（ロールバック可能Union-Find・union by sizeのみで履歴スタックによる取り消し）

自己評価

自分の回答

気づき・メモ