Aは、A[0]がアルファベットの0番目の文字の頻度を保持する配列であると想定します。
コードの長さを計算する最も効率的な（*）方法は何ですか？確かではありませんが、効率はメモリ使用量または必要な手順の観点から考えられます。
私が興味を持っているのは、アルファベットの0番目の文字のコード長（ビット数）を含む配列です。ここで、コードは、周波数配列から構築された標準ハフマンツリーから取得されますL。L[0]
質問する
1565 次
1 に答える
5
周波数が単調なシーケンスを形成する場合、すなわち。A [0] <= A [1] <= ... <=A[n-1]またはA[0]>= A [1]> = ...> = A [n-1]の場合、 O（n）時間とO（1）追加スペースで最適なコード長を生成できます。このアルゴリズムは、アレイ上で2回の単純なパスのみを必要とし、非常に高速です。完全な説明は[1]にあります。
周波数がソートされていない場合は、最初にそれらをソートしてから、上記のアルゴリズムを適用する必要があります。この場合、時間計算量はO（n log n）であり、ソートされた順序（空間計算量O（n））を格納するには、n個の整数の補助配列が必要です。
[1]：AlistairMoffatとJyrkiKatajainenによる最小冗長性コードのインプレース計算。オンラインで入手可能：http ：//www.diku.dk/~jyrki/Paper/WADS95.pdf
于 2011-03-29T18:35:25.577 に答える