拡張ハフマンコード

Question

私はこの宿題を持っています：特定のアルファベットでシンボルのコードワードを見つける。 3つのシンボルのグループでバイナリハフマンを使用する必要があると言います。それは正確に何を意味しますか？ [アルファベット]^3で通常のハフマンを使用しますか？もしそうなら、どのようにしてグループ内の3つの記号の違いを伝えることができますか？

Answer 1

問題の説明はそれほど詳細ではないので、私はわかりませんが、アルファベットの各シンボルを個別にエンコードする代わりに、グループとしてシンボルの各トリプルを踏むことになっていることを意味すると思います。 。

したがって、たとえば、アルファベットが a, b, 、 と c, 、それらのそれぞれのエンコードを個別に生成する代わりに、あなたは aaa, aab, aac, 、これらの文字列のそれぞれは、ハフマンアルゴリズムの別のシンボルとして扱われます。文字列比較を行うだけで、それらを区別することができます。任意の長さの入力を受け入れる必要がある場合は、長さ1または2の文字列であるアルファベットシンボルにも含める必要があります。たとえば、文字列をエンコードする場合は aabacab, 、それをシンボルに分解する必要があります aab, aca, 、 と b.

それはあなたの質問に答えるのに役立ちますか？私はあなたが探しているものがよくわからなかったので、これが何もクリアしていない場合は、あなたの質問を編集したり、コメントで返信したりしてください。

Answer 2

思考のための食べ物：短い弦と「ブロック境界」の順列はどうですか？ 1と2の文字列はどうですか？ 3、6、9、12、...入力テキストに充電してから、最後に不均一な長さをnullパッドしますか？

チャンクがさまざまなサイズの場合、最適なフィット感を見つけるのは本当に面白くなります。私はそれが旅行セールスマンのような問題に退化するのではないかと思いますが、おそらくこの種のことのためにきちんとした「定理」や他のツールがあるかもしれません。

おそらく、最も頻繁に使用されるものを保存して、3枚のcharのすべての順列を試してから、1枚と2枚のチャールのギャップに適したフィット感を考えてみてください。うーん、それは本当に遅いかもしれませんが、何らかの再帰的格差とカウンカーのアプローチを使用して実行可能かもしれません：ブロック長nの長い文字列を引き出してから、長さn -1としてギャップをエンコードするように再発します。

答えよりも多くの質問があります、私は恐れています。