私はこの宿題を持っています：与えられたアルファベットの記号のコードワードを見つけること。3つのシンボルのグループにバイナリハフマンを使用する必要があると書かれています。それは正確にはどういう意味ですか？[アルファベット]^3で通常のハフマンを使用しますか？もしそうなら、どうすればグループ内の3つのシンボルの違いを知ることができますか？
質問する
1523 次
2 に答える
1
問題の説明はそれほど詳細ではないため、よくわかりませんが、アルファベットの各記号を個別にエンコードする代わりに、記号の各トリプルをグループとして処理することになっていると推測できます.
したがって、たとえば、アルファベットがa、b、およびcで構成されている場合、それぞれのエンコーディングを個別に生成するのではなくaaa、aab、aac、 などのエンコーディングを作成します。これらの文字列のそれぞれは、ハフマンアルゴリズム; 文字列を比較するだけで、それらを区別できます。任意の長さの入力を受け入れる必要がある場合は、長さ 1 または 2 の文字列であるアルファベット記号も含める必要があります。たとえば、文字列をエンコードしている場合は、それをaabacab記号に分解する必要があります。 aab、aca、およびb。
それはあなたの質問に答えるのに役立ちますか? お探しのものがよくわからなかったので、質問を編集するか、これで解決しない場合はコメントで返信してください。
于 2010-01-13T06:36:37.840 に答える
0
考察の材料: より短い文字列と「ブロック境界」の順列についてはどうですか? 1文字列と2文字列の場合は？入力テキストに 3、6、9、12、... 文字を数えて、最後に不均等な長さを null で埋めますか?
チャンクのサイズを可変にできる場合、最適なサイズを見つけるのは非常に興味深いことです。私はそれが巡回セールスマンのような問題に退化しているのではないかと思っていますが、おそらくこの種のことのためのきちんとした「定理」または他のツールがそこにあります.
おそらく、最も頻繁に使用されるものを保存して、3 文字のすべての順列を試してから、1 文字と 2 文字の長さのギャップに適したものを見つけようとするでしょうか? うーん、それは本当に遅いかもしれませんが、ある種の再帰的な分割とカウンターのアプローチを使用して実行可能です: ブロック長 N の長い文字列を引き出し、再帰的にギャップを長さ N - 1 としてエンコードします。
答えよりも質問の方が多いと思います。
于 2010-01-13T07:03:58.580 に答える