1

私の質問は、有効な単語を介して1つの単語を別の単語に変換するアルゴリズムに似ています

しかし、とは大きな違いです。「JAMES」という固定語と、i/pとしてさまざまな辞書があります。もちろん、今は辞書を前処理することはできません。

そのため、さまざまな辞書を入力として「JAMES」から「JOHNY」を処理するための最小コストを見つける必要があります。

とにかく、実行時に最小数の編集距離計算を実行する必要があるように、「JAMES」という単語を前処理することはできますか？あなたたちは何を提案しますか？

4

2 に答える 2

1

ルールはあなたが引用した質問に似ていると思います。つまり、一度に編集できるのは一度に 1 つだけで、各中間語は指定された辞書に存在する必要があります。

  1. ソース文字列から宛先文字列への単一編集バージョンを作成します。例: JOMES JAHES JAMNS JAMEY

これらの単語ごとに再帰し、一意の単語ごとにノードを作成し続けます。ノードがすでに作成されている場合は、エッジを作成するだけです。これで前処理は完了です。

辞書が与えられたら、辞書の最初のレベルの単語をすべて見つけます。すべての一致について、目的の単語に到達するまで、すべての第 2 レベルの単語などをさらに検索します。

于 2012-07-28T17:08:39.877 に答える
0

まず、ルールを適切に定義する必要があります。「編集」で複数の文字を追加または削除したり、1 文字を置き換えたりすることはできますか?

とにかく - 明白なことから始めたいと思います - 各単語が直接編集できるすべての単語にリンクするグラフを作成します。次に、深さ制限のある再帰を使用し、訪問した要素を「ダーティ」としてマークしてサイクルを回避し、解決策が見つかるまで、またはすべてのパスがその深さでダーティになるまで、1 回編集のソリューション、2 回編集のソリューションなどがあるかどうかを確認します。(「ダーティ」メンバーで試行されている深さを記録すると、深さ制限を増やすたびにそれらを消去することを心配する必要はありません。また、再帰を避けるために、すべてダーティなサブツリーをマークすることもできます。 .)

于 2012-04-24T02:16:13.253 に答える