3

入ってくるビット シーケンスを文字 ('a' .. 'z' ) として表現できるアルゴリズムを探しています。ビット ストリームを文字から再生成できるように、シーケンス全体を保持する必要はありません。記憶に。

つまり、外部ビット ソース (読み取りごとに実質的にランダムなビットが返される) と、ビット数のユーザー入力が与えられた場合、それらのビットを表すことができる最小数の文字を出力したいと考えています。

理想的には、パラメータ化が必要です - いくらかの無駄が必要になる前に、メモリの量と最大ビット数。

効率目標 - ビットの base-26 表現と同じ数の文字。

非解決策:

  1. 十分なストレージが存在する場合は、シーケンス全体を保存し、大整数 MOD 26 演算を使用します。

  2. 9 ビットごとに 2 文字に変換 - これは最適ではないように思われ、文字出力の情報容量の 25% を無駄にします。

4

6 に答える 6

8

文字ごとに異なるビット数を割り当てると、ビットを無駄にすることなく、許可された 26 文字のビットを正確にエンコードできるはずです。(これはハフマン コードによく似ていますが、事前に構築されたバランスの取れたツリーのみを使用します。)

ビットを文字にエンコードするには: ルックアップ テーブル内のビット コードの 1 つと正確に一致するまで、ビットを蓄積します。その文字を出力し、ビット バッファをクリアして、続行します。

文字をビットにデコードするには: 各文字について、テーブル内のビット シーケンスを出力します。

コードでの実装は、読者の課題として残されています。（または、後で退屈した場合は、私にとって。）

a 0000
b 0001
c 0010
d 0011
e 0100
f 0101
g 01100
h 01101
i 01110
j 01111
k 10000
l 10001
m 10010
n 10011
o 10100
p 10101
q 10110
r 10111
s 11000
t 11001
u 11010
v 11011
w 11100
x 11101
y 11110
z 11111
于 2008-09-24T23:46:04.370 に答える
6

47 ビットの各ブロックを 10 桁の 26 進数に変換します。これにより、99.99% 以上の効率が得られます。

このメソッドは、Huffman などの他のメソッドと同様に、可変長入力をサポートするためのパディング メカニズムが必要です。これは、より長い入力ではそれほど重要ではない非効率性をもたらします。

ビット ストリームの最後に、余分な1ビットを追加します。これは、ビット ストリームの長さが 47 の倍数であっても、すべての場合に実行する必要があります。「ゼロ」値の上位文字は、エンコードされた出力の最後のブロックでスキップできます。

文字をデコードするとき、切り捨てられた最終ブロックに「ゼロ」文字を入力して、47 ビットの基数 2 表現に変換できます。最後の1ビットはデータではありませんが、ビット ストリームの終わりを示します。

于 2008-09-24T23:48:12.447 に答える
3

廃棄物ゼロは、1 文字あたり log_2(26) ビットになります。先に指摘したように、47 ビットを読み取って 10 文字に変換することで 4.7 に到達できます。ただし、14 ビットごとに 3 文字に変換すると、4.67 になります。これには、整数に収まるという利点があります。記憶域があり、実行時間が重要な場合は、可能な 14 ビットを 3 文字にマッピングする 17,576 エントリのルックアップ テーブルを作成できます。それ以外の場合は、mod 操作と div 操作を実行して 3 文字を計算できます。

number of letters    number of bits    bits/letter
 1                    4                4
 2                    9                4.5
 3                   14                4.67
 4                   18                4.5
 5                   23                4.6
 6                   28                4.67
 7                   32                4.57
 8                   37                4.63
 9                   42                4.67
10                   47                4.7
于 2008-09-25T05:49:53.310 に答える
3

ハフマンコーディングはあなたが探しているものでしょうか? これは圧縮アルゴリズムであり、無駄なビットを最小限に抑えてあらゆる情報を表現します。

于 2008-09-24T23:30:06.997 に答える
1

26 は 2 のべき乗ではないため、使用するソリューションはどれもスペース効率が悪くなります。アルゴリズムに関する限り、一連の 9 ビットごとにその場で計算するよりもルックアップ テーブルを使用したいと思います。ルックアップ テーブルの長さは 512 エントリになります。

于 2008-09-24T23:31:30.253 に答える
1

各文字のバイナリ フットプリントを同じサイズにする場合、最適解はArithmetic Encodingによって与えられます。ただし、4.5 ビット/文字の平均表現という目標には到達しません。26 の異なる文字 (スペースなどを含まない) を考えると、可変長エンコーディング (たとえば、ハフマン。Jaegers の回答を参照) やその他の圧縮アルゴリズムを使用せずに到達できるのは、4.7 が最適です。

単純ではありますが、次善の解決策は、大きな整数に収まる実行可能な文字数を見つけることです。たとえば、6 文字のチャンクごとに 32 ビット整数を形成する場合 (26^6 < 2^32 の場合)、5.33 ビット/文字を使用します。実際には、13 文字を 64 ビット整数 (4.92 ビット/文字) に収めることもできます。これは最適なソリューションに非常に近く、実装もかなり簡単です。多くのプログラミング言語ではネイティブ サポートがないため、64 ビットより大きい int を使用するのは難しい場合があります。

テキストの圧縮率をさらに向上させたい場合は、LZW や Deflate などの辞書ベースの圧縮アルゴリズムも検討する必要があります。

于 2008-09-25T05:30:24.667 に答える