編集距離の定義は次のとおりです。私の質問は、単語1から単語2までの距離を編集するか、単語2から単語1までの距離を編集することと常に同じかどうか、そしてなぜですか？ありがとう。文字列編集距離アルゴリズムの混乱
word1とword2の2つの単語が与えられた場合、edit distanceはword1をword2に変換するために必要な最小ステップ数です。 （各動作が1つのステップとしてカウントされる。）
ワードに許容3つの操作があります
A）文字 B）文字 C削除）文字を
よろしく交換を挿入、 Lin
常に同じです.w1からw2に至るプロセスは、同じステップ数で後方に実行できます。
各ステップa）には、対応するステップb）があり、逆も同様である。各ステップc）は、別のステップc）によって取り消すことができる。
ありがとうHenry、投票アップ、あなたはw1からw2までの最適なステップを見つけたと仮定しますが、対応するステップを後方に実行するとw2からw1に最適な（つまり最小のステップ数）がわかりますか？ –
最適でない場合（つまり、短い配列がある場合）、これを逆にして、w1からw2までの短い配列を作成できます。これは、元のシーケンスのw1からw2への最適性と矛盾する。 – Henry
ヘンリーさんに感謝します。これは賢明であり、投票します。応答として回答を記入してください。 –
はい、どちらの方法も同じステップ数はかかりません。 word1をword2に変換する最適なソリューションでは、word2をword1に変換する最適なソリューションに文字を追加すると、文字を削除すると仮定できます。したがって、これらの削除と追加操作に同じコストを支払うと、word1をword2に変換するか、その逆に変換するかにかかわらず、コストは常に同じになります。
返信いただき、ありがとうございます。 –
しかし、挿入コストと削除コストは常に同じであるはずですか？それらを変更することはできませんか？ –
@KurtBourbakiそれらは異なることができますが、その場合は両方の解決策が異なる可能性があります。 – Roshan
一般に、あなたが話している編集距離アルゴリズムに依存します。 – hatchet
@hatchet、返事と投票のために感謝します。私の質問は混乱するかもしれませんが、実際に私は特定の編集距離アルゴリズムの実装を意味するわけではありません、私はアルゴリズムから距離の結果を編集することを意味します。アドバイスがあれば、それは素晴らしいでしょう。 :) –