6

プレフィックス コードは、コードが別のコードのプレフィックスではないコードのセットです。たとえば、次のセットはプレフィックス コードです。

10
11
000
001
0100
0101
0110
0111

n = 8メンバーと。これらは通常、ある種のハフマン木で作成されていると思います。

私の質問は次のとおりです。「n」個のメンバーを持つバイナリ プレフィックス コードを生成する関数を作成するのを手伝ってくれませんか?

このようなもの：

list<int> GenerateBinaryPrefixCodes(int n);

また、必要条件は、ビットの合計が最小化されるという意味で「最適」であることです。

C/C++/C#/似たようなものでの回答を希望します。これは実際には宿題ではありませんが、良いハードウェアの問題になりそうなので、そのようにタグ付けしました。

ありがとう！

4

6 に答える 6

6

プレフィックス コード

ご指摘のとおり、プレフィックス コードとは、特定のコードが他の特定のコードのプレフィックスではないものです。これは非常に一般的な定義です。ハフマン エンコーディングは、プレフィックス コードの制限された形式です。

ハフマン コーディングの一般的な使用法は、「メッセージ」のエンコードに必要な合計ビット数を最小化 (最適化) することです。「メッセージ」は通常、シンボルのシーケンスであり、各シンボルの出現を特定のプレフィックス コードにマッピングし、その場所にプレフィックス コードを書き出すことによってエンコードされます。これを行うために、任意のプレフィックス コードのセットを使用できます。ただし、ハフマン エンコーディングでは、ビット カウントに基づいて可能な限り短いメッセージが生成されます。

たとえば、ASCII 文字セットは、8 ビットのプレフィックス コードのセットへのシンボルのマッピングと見なすことができます。これは、エンコードされたメッセージに可能な各シンボルがまったく同じ数含まれていれば、ハフマン エンコードと見なすこともできます。

興味深いことは、エンコードされるメッセージに等しくないシンボル周波数が含まれている場合に始まります。この時点で、異なる長さのプレフィックス コードを使用することで、メッセージの合計ビット長を減らすことができます。使用頻度の高いシンボルには短いプレフィックス コードを使用し、使用頻度の低いシンボルには長いプレフィックス コードを使用します。

あなたの例から、エンコードするシンボルが8つあります。プレフィックス コード '11' および '10' にマップされたシンボルは、メッセージ内で最も頻繁に使用されるシンボルです。同様に、「0111」、「0110」、「1010」、および「0100」にマップされたシンボルは、最も頻度が低くなります。周波数が高いほど、プレフィックス コードは短くなります。

ハフマンコーディングを作成する際の「トリック」は、メッセージ内の各シンボルを関連するプレフィックスコードにマッピングした後、メッセージに含まれるビットができるだけ少なくなるように、プレフィックスコードのセットを構築することです。

プレフィックス コードを、各リーフ ノードがシンボルにマップされるバイナリ ツリーとして表示すると便利です。たとえば、質問で指定されたプレフィックス コード (01、11、000、001、0100、0101、0110、0111) に対応するバイナリ ツリーは次のようになります。

           +-- (11)
        +--+
        |  +-- (10)
        |
        |        +-- (0111)
      --+     +--+
        |     |  +-- (0110)
        |  +--+
        |  |  |  +-- (0101)
        |  |  +--+
        +--+     +-- (0100)
           |
           |  +-- (001)
           +--+
              +-- (000)

括弧内の値を取得するには、上端をたどる場合は「1」を割​​り当て、下端をたどる場合は「0」を割り当てます。

そのような木をどのように構築するのですか？

二分木とリストを表すデータ構造から始めます。

二分木には 2 種類のノードが含まれます。1) シンボルとその頻度を表す葉ノード、および 2) その下のすべてのノードの累積頻度を表す内部ノード (また、2 つのポインターが必要です。1 つは左側の分岐用で、もう 1 つは右側の分岐用です)。

リストには、バイナリ ツリーからのノードの順序付けられたセットが含まれます。リスト内のノードは、それらが指すノードの頻度値に基づいて順序付けられます。最も頻度の低いノードはリストの先頭にあり、リストの最後に向かって増加します。ツリー ノードへのポインターのリンクされたリストは有用な実装かもしれませんが、任意の順序付けられたリスト構造で十分です。

以下のアルゴリズムは、「参照」リストと「作業」リストの 2 つのリストを使用します。ノードが「参照」リストから処理されると、新しいノードが作成されて「作業」リストに挿入され、「作業」リストはノードの頻度順に並べられたままになります。

これらのデータ構造と次のアルゴリズムを使用して、ハフマン エンコーディングを作成します。

0. Initialize the "reference" list by creating a leaf node for each symbol
   then add it into this list such that nodes with the lowest frequency 
   occur at the front of the list and those with the highest frequency
   occur at the back (basically a priority queue).

1. Initialize the "working" list to empty.

2. Repeat until "reference" list contains 1 node

   2.1 Set MaxFrequency to the sum of the first 2 node frequencies

   2.1 Repeat until "reference" list is empty
       If ("reference" list contains 1 node) OR
          (sum of the next two nodes frequency > MaxFrequency)
            Move remaining nodes to the "working" list
            Set "reference" list to empty
       Else
          Create a new internal node
          Connect the first "reference" node to the left child
          Connect the second "reference" node to the right child
          Set the new node frequency to the sum of the frequencies of the children
          Insert the new node into the "working" list
          Remove the first and second nodes from the "reference" list

   2.2 Copy the "working" list to the "reference" list
   2.3 Set the "working" list to empty

このプロセスの最後に、単一の「参照」リスト項目がハフマン ツリーのルートになります。ツリーの深さ優先トラバーサルを実行することで、プレフィックス コードを列挙できます。取られたすべての左側の分岐に対して「0」を書き込み、すべての右側の分岐に対して「1」を書き込みます。リーフが検出されると、コードは完了です。リーフのシンボルは、生成されたばかりのハフマン コードによってエンコードされます。

最適なエンコードとは

実行できる興味深い計算は、プレフィックス エンコーディングの「ビット ウェイト」を計算することです。ビットの重みは、プレフィックス コードのセットを表すために必要なビットの総数です。

上の元の木を見てください。このツリーの重みは (2 ビット * 2) + (4 ビット * 5) + (3 ビット * 2) = 30 ビットです。8 つのプレフィックス値を表すために 30 ビットを使用しました。使用できた最小ビット数は? 考えてみてください。木がアンバランスになると、一部の葉までのパスの長さが長くなります。これにより、重みが増します。たとえば、4 つの値のプレフィックス ツリーの最悪のケースは次のようになります。

                 +-- (1 bit)
               --+                  
                 |  +-- (2 bits)
                 +--+
                    |  +-- (3 bits)
                    +--+
                       +-- (3 bits)

(1 ビット * 1) + (2 ビット * 1) + (3 ビット * 2) = 9 ビットの合計重みを与える

木のバランスを取る:

                +-- (2 bits)
             +--+
             |  +-- (2 bits)
           --+  
             |  +-- (2 bits)
             +--+
                +-- (2 bits)

(2 ビット * 4) = 8 ビットの合計重みを与えます。バランスの取れたツリーでは、すべてのプレフィックス コードが同じビット数になることに注意してください。

ツリー ビットの重みは、すべての葉へのパスの長さの合計です。パスの合計長を最小化することでビットの重みを最小化します。これは、ツリーのバランスを取ることによって行われます。

ご覧のとおり、特定のプレフィックス ツリーを最小化してもあまり価値はありません。固定長のシンボル エンコーディングになってしまうだけです。結果のエンコードされたメッセージのビットの重みを考慮すると、値が得られます。それを最小化すると、ハフマン エンコーディングにつながります。

いくつの異なるエンコーディングがありますか?

プレフィックス コードは、バイナリ ツリーをトラバースし、リーフに遭遇するまで、下位の分岐ごとに '0' を発行し、上位の分岐ごとに '1' を発行することによって生成できます。次のように:

             +--+ (1)
             |  
           --+  
             |  +-- (01)
             +--+
                +-- (00)

別の方法として、そのルールを「反転」して、各下部ブランチに '1' を割り当て、上部ブランチに '0' を割り当てることもできます。

             +-- (0)
             |  
           --+  
             |  +-- (10)
             +--+
                +-- (11)

これらは、2 つの異なるプレフィックス コードのセットを生成します。ブランチへのすべての可能な 1/0 割り当てを調べてから、ツリーをトラバースすることにより、追加のセットを生成できます。これにより、2^n セットが得られます。ただし、これを行うと、同じプレフィックス コードが生成される可能性がありますが、順序が異なることがわかります。たとえば、前のツリーは次のセットを生成します: {(0, 10, 11), (0, 11, 01), (1, 01, 00), (1, 00, 01)}. 次に、ツリーを次のように反転します。

                +-- (??)
             +--+
             |  +-- (??)
           --+
             |
             +-- (?)

{(11, 10, 0), (10, 11, 0), (01, 00, 1), (00, 01, 1)} が得られます。両方を合わせて 2^3 = 8 セットです。ただし、順序を無視して一意のセットが必要な場合は、{(0, 10, 11), (1, 00, 01)} の 2 つのセットしかありません。バランスの取れた木に対して同じ演習を行うと、セットは 1 つだけになります。これらすべてのことから、一意のエンコーディングの数は、プレフィックス コードの生成に使用されるツリーのバランス構造に関連していると思われます。残念ながら、私は正確な公式や計算式を持っていません。推測では、その数は 2^(個別のコード長の数 - 1) になると思います。バランスの取れたツリーの場合: 2^(1 - 1) = 1; 2 つの異なるコード長を持つツリーの場合 (上記の例のように): 2^(2 - 1) = 2; あなたの例では: 2^(3 - 1) = 4.

于 2011-09-07T18:01:54.037 に答える
5

ビット数の合計が最小化されるという要件は、コードが、各シンボルが 1 回出現する文字列の最適なハフマン コードであることを要求することと同じです。したがって、単純にn 個の一意の文字を含む文字列を作成し、それに対してハフマン ツリーを生成します。アルゴリズムはウィキペディアで概説されています。

于 2011-09-06T15:58:30.957 に答える
1

n=8 の例は、最適なソリューションを表していないようです。

10 11 000 001 0100 0101 0110 0111 合計ビット: 26

000 001 010 011 100 101 110 111 合計ビット: 24

一定の頻度がある場合、最適なプレフィックス エンコーディングは固定長になります。各プレフィックス コードの長さは log(n) で、0..n-1 のアルファベットのバイナリ表現になります。

n が 2 の累乗でない場合の編​​集。

// generate tree
function PCode(n) {
 var a = [];
 for(var x=1; x<=n; x++) {
  a.push({"v":x});
 }
 for(var x=0; x<n-1; x++) {
  var node = {"v": null, "l": a.shift(), "r": a.shift()};
  a.push(node);  
 }
 return a.pop();
}

//print
function Print(node, s) {
 if(node["v"] != null) {
  console.log(s);
 }
 if(node["l"] != null) Print(node["l"], s + "0");
 if(node["r"] != null) Print(node["r"], s + "1");
 return;
}

//test
Print(PCode(3), "");
于 2011-09-06T17:49:35.510 に答える
0

こちらの C++ チュートリアル サイトをご覧ください。役立つ C++ 構造を提供します。また、右側の「関連」セクションで、役立つ可能性のある他の同様の SO の質問を見ています。

以前、C で再帰アルゴリズムを使用してこれを行ったことがありますが、そうです、宿題の大きな問題になるでしょう。

于 2011-09-06T16:09:18.297 に答える
0

バイナリ表現が 1x である数値でバイナリ文字列 x をエンコードしましょう。それ以外の場合、0 と 00 は同じ int にマップされます。

std::vector<int> GenerateBinaryPrefixCodes(int n) {
    std::vector<int> list;
    for (int i = n; i != 2 * n; ++i) list.push_back(i);
    return list;
}
于 2011-09-07T05:56:31.313 に答える
0

生成の問題 (デコードの一意性) は、n リーフ ノードのバイナリ ツリーを構築し、ツリー内のそのような各ノードの位置を列挙することによって保証できます (0 は左ブランチ、1 は右ブランチ)。そうです、ハフマン木にはこの性質があります。ハフマン ツリーの場合、各ノードにはその代表的な文字の頻度に等しい重みが与えられ、ノード結合の左右の決定がその時点までの子の合計に基づくという再帰的なプロパティを使用してツリーが構築されることに注意してください。 . この累積和の性質は、フィボナッチ分布がハフマン木に最悪の圧縮を与える理由でもあります。

ハフマン エンコーディングは、固定アルファベットの可変エンコーディングに最適です。固定されていないアルファベットの例としては、" the " をセット内の 1 つの要素として圧縮するという決定があります (2 つのスペースと 1 つの文字ではなく)。

あなたの問題は、置換に関連していないようです。すべてのプレフィックス コードの長さの合計が最小化される n 要素のプレフィックス コードが必要なだけです。これは、すべての要素頻度が 1 であるハフマン ツリーを構築することと同じです (これは、エンコードされた文字列全体の最小エンコードを保証するためです。これは、エンコードされたすべての要素のビットの合計に 1 回だけ等しい、つまり、合計を最小化するためです)。ビット）。注: これは最小のエンコードを保証するものであり、最速の実装を保証するものではありません。メソッド呼び出しごとにツリーを作成する必要はおそらくありません。残念ながら、私は頭のてっぺんからの実装を知りません。

于 2011-09-06T16:52:14.843 に答える