編集距離（Levenshtein距離）

🔥 Vibe プロンプト

「'kitten'と'sitting'の編集距離を計算。DPテーブルと操作シーケンスを出力。」

編集距離とは？

編集距離（Levenshtein距離） は、1つの文字列を別の文字列に変換するのに必要な最小の編集回数（挿入、削除、置換）を測定します。

| 操作 | コスト | 例 | |------|-------|----| | 挿入 | 1 | "cat"→"cats" ('s'を追加) | | 削除 | 1 | "cats"→"cat" ('s'を削除) | | 置換 | 1 | "cat"→"cut" ('a'→'u') | | 一致 | 0 | "cat"→"cat" (同じ文字、無料) |

実装

def edit_distance(s1, s2):
    """2つの文字列間の最小編集回数を返す"""
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        dp[i][0] = i  # 空文字列にするのにi回削除
    for j in range(n + 1):
        dp[0][j] = j  # 空文字列から作るのにj回挿入
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]  # 一致、コスト0
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j],    # 削除
                    dp[i][j-1],    # 挿入
                    dp[i-1][j-1]   # 置換
                )
    return dp[m][n]

# 例
print(f"kitten→sitting: {edit_distance('kitten', 'sitting')} 編集")
print(f"  k→s(1), e→i(1), g挿入(1) = 3")
print(f"Vibe→Vibes: {edit_distance('Vibe', 'Vibes')} 編集")
print(f"Sunday→Saturday: {edit_distance('Sunday', 'Saturday')} 編集")

スペルチェッカー

def spell_check(word, dictionary):
    """編集距離で最も近い単語を検索"""
    scored = [(w, edit_distance(word, w)) for w in dictionary]
    scored.sort(key=lambda x: x[1])
    return scored[:5]

dictionary = ["coding", "vibe", "tutor", "python", "algorithm",
              "react", "nextjs", "docker", "kubernetes", "typescript"]

misspelled = "codng"
suggestions = spell_check(misspelled, dictionary)
print(f"\nスペルチェック: '{misspelled}' →")
for word, dist in suggestions:
    print(f"  {word} (距離: {dist})")

まとめ

| 項目 | 詳細 | |------|------| | 状態定義 | dp[i][j] = s1[:i]をs2[:j]にする最小編集回数 | | 漸化式 | 一致: 0+dp[i-1][j-1] | 不一致: 1+min(削除, 挿入, 置換) | | 初期条件 | dp[i][0]=i, dp[0][j]=j | | 時間 | O(m×n) | | 応用 | スペルチェック、DNA配列比較、音声認識 |

よくある問題と解決策

| 問題 | 原因 | 解決方法 | |------|------|---------| | 期待通りの結果が出ない | パラメータ設定ミス | デフォルト値と境界条件を確認 | | 実行が遅い | アルゴリズムの効率 | より効率的なデータ構造を使用 | | メモリ不足 | データ量過多 | バッチ処理を検討 | | デバッグが困難 | ログ不足 | 詳細なログ出力を追加 |

さらに学ぶには

公式ドキュメントを読む
GitHubのオープンソース例を参照
コミュニティディスカッションに参加
コードを修正して結果の変化を観察