概要

クエリに対して編集距離が近い単語を得たいときに、jaccardフィルタを併用して、高速化できるか検証しました。

背景

ラップやダジャレの自動生成のために、クエリ単語に音韻が類似した単語を編集距離ベースで取得したくなることがあります。
pythonにはeditdistance という高速な編集距離計算ライブラリがありますが、辞書サイズが大きくなると全件探索のコストが無視できなくなります。ベクトルの内積であれば、numpyのようなライブラリで高速化が可能ですが、編集距離ではそのようなことできません。

そこで、単に同じ文字が使われているかどうかだけに注目して、緩いフィルタリングをしてから、少数の候補に対して編集距離を求めることで、精度をある程度保ちつつ、高速化する方法を検討しました。

方法

以下の２つを比較しました。

愚直法: 全件（約33万件）に対してモーラ列同士の編集距離を計算
Jaccard フィルタ併用法: まずモーラ集合の Jaccard 類似度で上位1000件まで絞り、その範囲だけ編集距離を計算

データセットはunidic（unidic-cwj-202512_full.zip）から発音が定義された名詞のみを抽出したものを使用しました。

結果

適当なターゲット語「サトイモ」で試した結果は以下の通りです。

% uv run main.py サトイモ
辞書件数: 327910 / 対象語: サトイモ

[愚直 (全件で編集距離)]
  計算時間: 0.735 秒
  トップ100件中 上位10件を表示
      1. dist=0  jaccard=0.000 surface=さといも pronunciation=サトイモ id=14284
      2. dist=0  jaccard=0.000 surface=サトイモ pronunciation=サトイモ id=14284
      3. dist=0  jaccard=0.000 surface=里いも pronunciation=サトイモ id=14284
      4. dist=0  jaccard=0.000 surface=里芋 pronunciation=サトイモ id=14284
      5. dist=1  jaccard=0.000 surface=サトイ pronunciation=サトイ id=150286
      6. dist=1  jaccard=0.000 surface=佐戸井 pronunciation=サトイ id=150286
      7. dist=1  jaccard=0.000 surface=郷舎 pronunciation=サトイエ id=149192
      8. dist=1  jaccard=0.000 surface=里井 pronunciation=サトイ id=150286
      9. dist=2  jaccard=0.000 surface=いも pronunciation=イモ id=47343
     10. dist=2  jaccard=0.000 surface=いも pronunciation=イモ id=2504

[Jaccardフィルタ→編集距離 (候補1000件)]
  計算時間: 0.153 秒
  トップ100件中 上位10件を表示
      1. dist=0  jaccard=1.000 surface=さといも pronunciation=サトイモ id=14284
      2. dist=0  jaccard=1.000 surface=サトイモ pronunciation=サトイモ id=14284
      3. dist=0  jaccard=1.000 surface=里いも pronunciation=サトイモ id=14284
      4. dist=0  jaccard=1.000 surface=里芋 pronunciation=サトイモ id=14284
      5. dist=1  jaccard=0.750 surface=サトイ pronunciation=サトイ id=150286
      6. dist=1  jaccard=0.750 surface=佐戸井 pronunciation=サトイ id=150286
      7. dist=1  jaccard=0.600 surface=郷舎 pronunciation=サトイエ id=149192
      8. dist=1  jaccard=0.750 surface=里井 pronunciation=サトイ id=150286
      9. dist=2  jaccard=0.500 surface=いも pronunciation=イモ id=2504
     10. dist=2  jaccard=0.500 surface=いも pronunciation=イモ id=47343

[比較まとめ]
  愚直法: 0.735s, Jaccard法: 0.153s
  トップ100のうち共通 21 件 ( 25.3% )
  順位一致: トップ10件まで一致 (比較対象 100件)

モウラの重複を含むターゲット語「キキキリン」でも試してみます。

% uv run main.py キキキリン           
辞書件数: 327910 / 対象語: キキキリン

[愚直 (全件で編集距離)]
  計算時間: 0.710 秒
  トップ100件中 上位10件を表示
      1. dist=2  jaccard=0.000 surface=ききん pronunciation=キキン id=42766
      2. dist=2  jaccard=0.000 surface=きっきん pronunciation=キッキン id=45873
      3. dist=2  jaccard=0.000 surface=きりきり pronunciation=キリキリ id=99762
      4. dist=2  jaccard=0.000 surface=きりん pronunciation=キリン id=9553
      5. dist=2  jaccard=0.000 surface=つききり pronunciation=ツキキリ id=24510
      6. dist=2  jaccard=0.000 surface=つき切り pronunciation=ツキキリ id=24510
      7. dist=2  jaccard=0.000 surface=キヅ金 pronunciation=キズキン id=358236
      8. dist=2  jaccard=0.000 surface=キナゾリン pronunciation=キナゾリン id=250051
      9. dist=2  jaccard=0.000 surface=キノキサリン pronunciation=キノキサリン id=252802
     10. dist=2  jaccard=0.000 surface=キノリン pronunciation=キノリン id=132671

[Jaccardフィルタ→編集距離 (候補1000件)]
  計算時間: 0.147 秒
  トップ100件中 上位10件を表示
      1. dist=2  jaccard=0.667 surface=ききん pronunciation=キキン id=42766
      2. dist=2  jaccard=0.667 surface=きりきり pronunciation=キリキリ id=99762
      3. dist=2  jaccard=1.000 surface=きりん pronunciation=キリン id=9553
      4. dist=2  jaccard=0.600 surface=キナゾリン pronunciation=キナゾリン id=250051
      5. dist=2  jaccard=0.600 surface=キノキサリン pronunciation=キノキサリン id=252802
      6. dist=2  jaccard=0.750 surface=キノリン pronunciation=キノリン id=132671
      7. dist=2  jaccard=0.667 surface=キリキリ pronunciation=キリキリ id=99762
      8. dist=2  jaccard=1.000 surface=キリン pronunciation=キリン id=9553
      9. dist=2  jaccard=0.667 surface=キンキン pronunciation=キンキン id=205637
     10. dist=2  jaccard=0.667 surface=切り切り pronunciation=キリキリ id=388415

[比較まとめ]
  愚直法: 0.710s, Jaccard法: 0.147s
  トップ100のうち共通 33 件 ( 33.7% )
  順位一致: トップ1件まで一致 (比較対象 100件)

考察

速度については、Jaccard フィルタ併用法が約5倍高速化しました。精度については、ターゲット語によりますがトップ100件のうち約３割前後は共通しており、実用的なトレードオフかと思います。

ランキングの完全一致については、ターゲット語「サトイモ」ではtop10まで一致したのに対し、「キキキリン」ではtop1件のみでした。モウラの重複がある語では、Jaccard 類似度が文字の重複をまるめて計算されるために粗いフィルタとなってしまい、精度が落ちやすい可能性があります。
trigram など位置情報を持つフィルタも検討するとよいかもしれません。

実装

検証に用いたコードを以下に示します。

similarity_search.py

from __future__ import annotations

import csv
import heapq
from dataclasses import dataclass
from itertools import count
from pathlib import Path
from time import perf_counter
from typing import Iterable, Sequence

import editdistance
from jamorasep.main import Morasep


@dataclass(frozen=True)
class NounEntry:
    surface: str
    pronunciation: str
    noun_id: str
    mora: tuple[str, ...]


@dataclass(frozen=True)
class RankedResult:
    surface: str
    pronunciation: str
    noun_id: str
    distance: int
    jaccard: float


_MORA_PARSER = Morasep()


def _mora_sequence(text: str) -> tuple[str, ...]:
    normalized = (text or "").strip()
    if not normalized:
        return tuple()
    try:
        morae = _MORA_PARSER.parse(normalized)
    except Exception:
        # Fallback to character-level if Morasep fails
        morae = list(normalized)
    return tuple(morae)


def load_nouns(csv_path: str | Path) -> list[NounEntry]:
    """Load noun entries from nouns.csv."""
    path = Path(csv_path)
    if not path.exists():
        raise FileNotFoundError(f"nouns CSV not found: {path}")

    entries: list[NounEntry] = []
    with path.open("r", encoding="utf-8", newline="") as csvfile:
        reader = csv.DictReader(csvfile)
        if reader.fieldnames is None:
            raise ValueError("nouns.csv must include a header row")

        for row in reader:
            surface = row.get("surface")
            pronunciation = (row.get("pronunciation", "") or "").strip()
            noun_id = row.get("id", "")
            if not surface:
                continue
            mora_source = pronunciation if pronunciation else surface
            mora = _mora_sequence(mora_source)
            entries.append(
                NounEntry(
                    surface=surface,
                    pronunciation=pronunciation,
                    noun_id=noun_id,
                    mora=mora,
                )
            )

    return entries


def _jaccard_similarity(lhs_chars: set[str], rhs_chars: set[str]) -> float:
    if not lhs_chars and not rhs_chars:
        return 1.0
    union = lhs_chars | rhs_chars
    if not union:
        return 0.0
    return len(lhs_chars & rhs_chars) / len(union)


def rank_by_edit_distance(
    target: str,
    entries: Sequence[NounEntry],
    *,
    top_n: int = 100,
) -> tuple[float, list[RankedResult]]:
    """Rank entire vocabulary purely by edit distance."""
    target_mora = _mora_sequence(target)
    ranked: list[RankedResult] = []
    start = perf_counter()

    for entry in entries:
        distance = int(editdistance.eval(target_mora, entry.mora))
        ranked.append(
            RankedResult(
                surface=entry.surface,
                pronunciation=entry.pronunciation,
                noun_id=entry.noun_id,
                distance=distance,
                jaccard=0.0,
            )
        )

    ranked.sort(key=lambda result: (result.distance, result.surface))
    elapsed = perf_counter() - start
    return elapsed, ranked[:top_n]


def rank_with_jaccard_prefilter(
    target: str,
    entries: Sequence[NounEntry],
    *,
    filter_size: int = 1000,
    top_n: int = 100,
) -> tuple[float, list[RankedResult], int]:
    """Use a Jaccard similarity filter before computing edit distance."""
    if filter_size <= 0:
        raise ValueError("filter_size must be positive")

    target_mora = _mora_sequence(target)
    target_mora_set = set(target_mora)
    heap: list[tuple[float, int, NounEntry]] = []
    tie_counter = count()
    start = perf_counter()

    for entry in entries:
        sim = _jaccard_similarity(target_mora_set, set(entry.mora))
        candidate = (sim, next(tie_counter), entry)
        if len(heap) < filter_size:
            heapq.heappush(heap, candidate)
            continue
        if candidate > heap[0]:
            heapq.heapreplace(heap, candidate)

    if not heap:
        return 0.0, [], 0

    ranked: list[RankedResult] = []
    for sim, _, entry in heap:
        distance = int(editdistance.eval(target_mora, entry.mora))
        ranked.append(
            RankedResult(
                surface=entry.surface,
                pronunciation=entry.pronunciation,
                noun_id=entry.noun_id,
                distance=distance,
                jaccard=sim,
            )
        )

    ranked.sort(key=lambda result: (result.distance, result.surface))
    elapsed = perf_counter() - start
    return elapsed, ranked[:top_n], len(heap)


def format_results(results: Iterable[RankedResult], limit: int) -> list[str]:
    lines: list[str] = []
    for rank, result in enumerate(results, start=1):
        lines.append(
            f"{rank:>3}. dist={result.distance:<2} jaccard={result.jaccard:0.3f} "
            f"surface={result.surface} pronunciation={result.pronunciation} id={result.noun_id}"
        )
        if rank >= limit:
            break
    return lines

main.py

from __future__ import annotations

import argparse
from typing import Sequence

from similarity_search import (
    RankedResult,
    format_results,
    load_nouns,
    rank_by_edit_distance,
    rank_with_jaccard_prefilter,
)


def parse_args() -> argparse.Namespace:
    parser = argparse.ArgumentParser(
        description="Compare brute-force and Jaccard-filtered edit-distance search."
    )
    parser.add_argument("target", help="検索対象の単語")
    parser.add_argument(
        "--csv-path",
        default="nouns.csv",
        help="名詞一覧CSVへのパス (default: nouns.csv)",
    )
    parser.add_argument(
        "--top",
        type=int,
        default=100,
        help="取得する上位件数 (default: 100)",
    )
    parser.add_argument(
        "--filter-size",
        type=int,
        default=1000,
        help="Jaccardフィルタで残す候補数 (default: 1000)",
    )
    parser.add_argument(
        "--preview",
        type=int,
        default=10,
        help="表示する上位件数 (default: 10)",
    )
    return parser.parse_args()


def print_results(title: str, elapsed: float, results: Sequence[RankedResult], preview: int) -> None:
    print(f"\n[{title}]")
    print(f"  計算時間: {elapsed:.3f} 秒")
    print(f"  トップ{len(results)}件中 上位{min(preview, len(results))}件を表示")
    for line in format_results(results, preview):
        print(f"    {line}")


def main() -> None:
    args = parse_args()
    nouns = load_nouns(args.csv_path)
    print(f"辞書件数: {len(nouns)} / 対象語: {args.target}")

    brute_elapsed, brute_results = rank_by_edit_distance(
        args.target, nouns, top_n=args.top
    )
    jaccard_elapsed, jaccard_results, filtered = rank_with_jaccard_prefilter(
        args.target,
        nouns,
        filter_size=args.filter_size,
        top_n=args.top,
    )

    print_results("愚直 (全件で編集距離)", brute_elapsed, brute_results, args.preview)
    print_results(
        f"Jaccardフィルタ→編集距離 (候補{filtered}件)",
        jaccard_elapsed,
        jaccard_results,
        args.preview,
    )

    brute_set = {result.surface for result in brute_results}
    jaccard_set = {result.surface for result in jaccard_results}
    overlap = brute_set & jaccard_set
    prefix_match = 0
    for brute_result, jaccard_result in zip(brute_results, jaccard_results):
        if brute_result.surface == jaccard_result.surface:
            prefix_match += 1
        else:
            break
    comparable = min(len(brute_results), len(jaccard_results))
    print("\n[比較まとめ]")
    print(f"  愚直法: {brute_elapsed:.3f}s, Jaccard法: {jaccard_elapsed:.3f}s")
    print(
        f"  トップ{args.top}のうち共通 {len(overlap)} 件 ( {len(overlap) / max(1, len(brute_set)) * 100:.1f}% )"
    )
    if comparable:
        print(
            f"  順位一致: トップ{prefix_match}件まで一致 (比較対象 {comparable}件)"
        )
    else:
        print("  順位一致: 比較対象なし")


if __name__ == "__main__":
    main()

実行コマンドは以下です。

uv run python main.py サトイモ --top 100 --preview 10 --filter-size 1000