レーベンシュタイン距離に関するウィキペディアの記事は、その可能な変更セクションで、「挿入、削除、および置換の数を個別に保存できる」と述べています。
これはどのように行われますか？記事で概説されている行列ベースの動的プログラミング ソリューションの実装を作成しました。この場合、行列の各セルは削除/挿入/置換に対して個別の値を持ちますが、私の人生ではうまくいかないようです論理。
直感的には、同じステップで削除と挿入を行う必要がある場合は、代わりにそれらを代用する必要があるようです。
完全に明確にするために、ソース文字列「mat」とターゲット文字列「catch」のサンプル マトリックスを次に示します。これには、1 回の置換 (つまり、"m" を "c" に変更) と 2 回の挿入 (つまり、"ch" の追加) が必要になると予想しています。各セルは「削除/挿入/置換」です。
キャッチ +-----+-----+-----+-----+-----+-----+ |D/I/S|0/1/0|0/2/0|0/3/0|0/4/0|0/5/0| +-----+-----+-----+-----+-----+-----+ M |1/0/0|0/0/1|0/1/1|0/2/1|0/3/1|0/4/1| +-----+-----+-----+-----+-----+-----+ |2/0/0|1/0/1|0/0/1|0/1/1|0/2/1|0/3/1| +-----+-----+-----+-----+-----+-----+ |3/0/0|2/0/1|1/0/1|0/0/1|0/1/1|0/2/1| +-----+-----+-----+-----+-----+-----+
誰かがこのアルゴリズムを解決しましたか?