-1

「meetateight」のような文字列があり、動的計画法を使用して「meet」「at」「eight」などの意味のある単語にセグメント化する必要があるとします。

ブロック/セグメント "x = x1x2x3" がどの程度「良い」かを判断するために、入力 x に対して次のような実数の品質 (x) を返すブラック ボックスが与えられます。 x は英語の単語に近く、大きな負の数は x が英語の単語から遠いことを示します。

同じアルゴリズムの設計に助けが必要です。

品質が低下するたびに、品質とセグメントに基づいて文字を繰り返し追加するアルゴリズムについて考えてみました。しかし、上記の例では、meet ではなく me を切り取っているため、これは失敗します。

より良いアルゴリズムの提案が必要です。

ありがとう

4

3 に答える 3

0

動的計画法を使用して、入力の各プレフィックスのスコアを追跡し、一度に1文字ずつ追加できます。文字を追加するたびに、すでに使用しているプレフィックスにサフィックスを追加できるかどうかを確認します（スコアが最も高いプレフィックスを選択します）。例えば：

m = 0
me = 1
mee = 0
meet = 1
meeta = 1 (meet + a)
meetat = 1 (meet + at)
meetate = 1 (meet + ate)
meetatei = 1 (meetate + i)
meetateig = 0
meetateigh = 0
meetateight = 1 (meetat + eight)

0から1までの値を処理するには、それらを掛け合わせることができます。また、使用した単語を保存して、最後に文字列全体を分割できるようにします。

于 2012-11-09T13:45:59.737 に答える
0

英語辞書を使用してTrieを構築し、リーフへのすべての可能なパスを使用して文字列をスキャンして下に移動するのはどうですか (複数の選択肢がある場合はバックトラックします)。

于 2012-11-09T13:35:10.193 に答える
-1

私は自分のブログでこれを行うプログラムを書きました。ここに含めるには長すぎます。基本的な考え方は、単語を形成する接頭辞を切り落とし、残りの入力を再帰的に処理し、文字列全体を分割できない場合はバックトラックすることです。

于 2012-11-09T13:43:03.353 に答える