有限集合から記号のリストを符号化する最もコンパクトな方法は何ですか？

Question

私は最小限のバイト数で有限集合から記号列を表現することに興味があります。

たとえば、文字列a-zのみを含むテキスト文字列があるとします。あなたはasciiとしてそれらをエンコードすることができるので、シンボル（文字）ごとに1バイト。しかし、これを行うことで、1バイトあたり256の可能な値のうちの26個だけを使用しています。

私はうまくいくと思われるソリューションをコーディングしましたが、誰かがより良い方法を知っているか考えているかどうかを知りたいと思います。

私の方法は、シーケンスnをベースnの整数として扱います.nはthe size of the set of symbols + 1です。たとえば、あなたのセットまたはシンボル、つまり「アルファベット」が{a, b, c}（長さ3）だった場合は、基数4を使用します。シンボルには数値が割り当てられます（{a => 1, b => 2, c => 3}）。したがって、配列[b, a, c]は、基数4の213のように扱われるため、10進数で39になります。この整数は、2進数で符号化され、その基本4表現に復号化されて、2, 1, 3 => [b, a, c]というシーケンスを取り出すことができる。上記の

私のPython実装：radixcodec.py

だから私の質問は、私が説明してきたものよりも有限集合から要素のリストを符号化するより多くのスペース効率的な方法があるのですか？ Nシンボルの数（例えば{a => 0, b => 1, c => 2}）である

Answer 1

用基地N。この方法は、各シンボルが等しく現れる可能性が高い場合に最適です。 （もちろん、文字列の長さを格納しなければなりませんが、実装ではPython文字列を使用しますが、スペース効率の高いデータ構造ではありません）

周波数あなたがそれらを知っているなら、Huffman codingを使うことができます。あなたが周波数を知らないなら、adaptive Huffman codingがあります。

とにかく、最適な方法はアプリケーションによって異なります。