- 記入中
- 参照元
- 答え
編集距離(レーベンシュタイン距離)
kitten を sitting に変えるには、1文字の変更が何回必要でしょうか。答えは3回です。k を s に置換し、e を i に置換し、g を追加します。この数が編集距離で、スペルチェッカーが候補を並べるときや、生物学者が遺伝子を比べるときに使われます。2つの単語を入力して、表がこの数を求める様子を見てみましょう。 「再生」で表が埋まっていく様子を見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。2つの単語を入力してください。1つ目は表の左端に縦に、2つ目は上端に横に並びます。各マスには、その行までの文字をその列までの文字に変えるのに必要な最小の編集回数が入ります。最後に、右下のマスから編集をさかのぼって読み取ります。「新しい例」で別の単語の組を選びます。ボードを選択した状態では、矢印キーでステップ、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。
使い方
- 2つの単語を入力します。1つ目は表の左端に縦に、2つ目は上端に横に並びます。
- 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。
- 各マスが3つの隣のマスから最も安いものを選ぶ様子を見たあと、編集がオレンジ色でさかのぼって読み取られるのを確かめましょう。
表のしくみ
各マスには、1つ目の単語のその行までの文字を、2つ目の単語のその列までの文字に変えるのに必要な最小の編集回数が入ります。最初の行は挿入の回数で、2つ目の単語を空から作ります。最初の列は削除の回数です。マスの2文字が同じなら、左上のマスをコピーします。編集は不要だからです。そうでなければ、3つの隣のマスの最小値に1を足します。左上は置換、上は削除、左は挿入に当たります。
編集をさかのぼって読む
右下のマスが編集距離です。アプリはそこから始めて、マスの値がどの隣のマスから来たかを調べ、そこへ移動します。残した文字や置換した文字なら斜めに、削除した文字なら上に、挿入した文字なら左に進みます。左上から読むと、これらのステップが最短の編集リストになり、表の下に表示されます。普通の文字は残した文字、k→s は置換、−e は削除、+g は挿入です。
よくある質問
レーベンシュタイン距離とは何ですか?
この編集距離の別名で、ある文字列を別の文字列に変えるのに必要な、1文字の挿入・削除・置換の最小回数です。1965年にこれを示したウラジーミル・レーベンシュタインにちなんで名付けられました。
kitten と sitting の編集距離はいくつですか?
3です。k を s に置換し、e を i に置換し、最後に g を挿入します。これより短い編集リストがないことは表が示しています。
編集距離のアルゴリズムはどれくらい速いですか?
長さ m と n の単語では表のマスは (m + 1)·(n + 1) 個で、各マスを1ステップで埋めるので、O(m·n) の時間がかかります。距離だけが必要なら、表の2行分だけで足ります。
ほかにどんな編集距離がありますか?
ダメラウ・レーベンシュタイン距離は、隣り合う2文字の入れ替えも1回の編集として数えるので、タイプミスに向いています。ハミング距離は置換だけを許し、同じ長さの文字列に使います。LCS 距離は挿入と削除だけを許します。
データはどこかに送信されますか?
いいえ。すべての計算はブラウザー内で行われ、最後の設定はこのブラウザーのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ