8桁整数を限りなく短い文字列にしたい！！

質問

0～99999999の正の整数を0-9の数字とa～zのアルファベット（大文字小文字区別なし）で表現したいと思います。

私が考え付いたのが単純に36進数にした場合で六桁なのですが、
これ以上に短くなる方法をご存知の方、教えていただけないでしょうか。

よろしくお願いします。

回答No.8

Oh-Orange

★最終的に何を求めていますか？
・タイトルの『8桁整数を限りなく短い文字列にしたい！！』とは、変換した何らかの整数値の
　IDという事は分かりました。でも、全体像がよく分かりませんので、最終的にどんな事を
　実現するために『8桁整数』を限りなく短くしたいのですか。ここを補足して欲しいです。
・あと『満遍なく表すデータが圧縮できない』理由は、
　整数値の出現頻度に偏りがあれば、これをビット列の長さに変換して圧縮を行うため、
　整数値の出現頻度に偏りがない(満遍なく)存在するデータ値ではビット列が同じ長さに
　なるため圧縮効果が薄いか、意味がなくなります。
・分かりやすい例えですと
　10…1000回の出現頻度
　100…100回の出現頻度
　1000…10回の出現頻度
　と大幅に整数値の出現頻度に偏りがある場合は、
　10…1ビット長で表す
　100…2ビット長で表す
　1000…3ビット長で表す
　と関連付けます。すると一番多い 10 の整数値は 1 ビットで表せるため、全体では
　1000回×1ビット＝1000ビットで済みます。もし、同じ事をするのに生のままの整数値では
　8桁の整数は 27 ビット必要ですので、1000回×27ビット＝27000ビットとなります。
　1000ビット(125バイト)と27000ビット(3375バイト)ではどちらが圧縮されるかは分かりますよね。
・このように整数データの出現頻度に偏りが出た場合に圧縮できるのです。でも、10、100、1000の
　整数値がすべて 100 回で同じ頻度で満遍なく出現する場合は、ビットの長さが同じになって意味が
　無くなるため、圧縮できない→圧縮の意味を持たないとなるのです。
　zip、lha などの圧縮ソフトでは文字列の出現頻度を辞書として管理して、一番出現頻度が多い文字列に
　一番短いビット長を割り当てるのです。そして、最も出現頻度が低い(1回程度しか出現しない)文字列には
　一番長いビット長を割り当てる仕組みになっています。
・今回は、整数値のデータですが考え方は同じです。整数値も最終的にはビット長で表現できるため
　出現頻度に偏りがあれば、同様な理由で圧縮できます。あと jpg ファイルの圧縮はアルゴリズムが全く
　異なるため今回は無縁です。jpg の画像は周波数の成分を数学的な数式に置き換えて、複数の波形を
　合成することで画像を表現します。よって jpg は複数の波形で刻みの細かい波形を記録しないことで
　大幅な圧縮を行っているのです。zip、lhz とは全く違うアルゴリズムですし、元の画像に完全には復元
　されることはありません。今回は必ず元の状態に戻せないといけませんので全く異なります。
・以上。最終的に何を実現するために8桁の整数を限りなく短くしたいのですか？
　詳しい補足をお願いします。

回答No.7

noname#241104

99999999を２進数で表すために必要な桁は
　log99999999 / log2 = 26.57....　で２７ビット！
99999999を36真数で表すために必要な桁は
　log99999999 / log36 = 5.140...　で６バイト...４８ビット！
どっちが短いかは一目瞭然。

じゃ、0～zを１バイトではなく
　log36 / log2 = 5.1699... で６ビットで表現するとしても３６ビット必要となる。

もっと文字種を増やさないと桁は短くなんないでしょうね。

回答No.6

jacta

> 変換したいのは整数値のIDでして、
> 一回の変換時にどれだけの種類のIDが出現するか、どのIDが出現するかは推測ができません。
> こういった場合は無理なんでしょうか。

目的が明らかであれば、何とかできるかもしれません。

たとえば、比較的遅い通信手段を使って文字列として送受信する場合を考えてみましょう。送受信の頻度が非常に高いので、文字数を少しでも短くしようとしているような場合です。送受信の頻度が高くても、扱うIDの数がそれほど多くないのであれば、あらかじめ双方でIDの表を用意し（あらかじめ表を送信しておく必要があるかもしれません）、そのインデックスだけをやり取りするのであれば、かなり短くできるはずです。
# もっとも、このような場合には、やりとりの頻度を少なくするための検討をするか、通信手段を見直す方がよいと思いますが...

このように、短くしたい理由を明らかにすれば、まだ手の打ちようがあります。

回答No.5

jacta

実際にどんな値が出現するかがわかっていれば、それに応じた最適化が可能です。そうでなければ、一般的な圧縮手法を採用するしかないと思います。ただ、値の集合全体を圧縮するのではなく、個々の値を独立して扱いたい場合には、あまり有効な方法がありません。

お礼

ご回答ありがとうございます。

変換したいのは整数値のIDでして、
一回の変換時にどれだけの種類のIDが出現するか、どのIDが出現するかは推測ができません。
こういった場合は無理なんでしょうか。
段々弱気になってきてしまいました。。。

回答No.4

Werner

可変長でもかまわないなら、
・0～35は"0"～"z"
・36～1331は"00"～"zz"
・1332～47987は"000"～"zzz"
(以下略)
と符号化すれば、平均符号長は減らせます。
出現頻度が均等として5.5桁くらいですけどね。

最大長はやっぱり6桁。

（可変長はかまわないが、符号終端が分からないと困るというなら、
少しやり方を変える必要がある。）

お礼

ご回答ありがとうございます。

>可変長でもかまわないなら～～
すみません、説明が不足しておりました。
整数値ということで私も0抜き（0000001=1）して36進数化しております。

回答No.3

Oh-Orange

★質問は『限りなく短い文字列にしたい！！』ですよね。
・文字列は『文字』の並びですので 36 進数が最大ならば、BASE64 は使えませんね。
　申し訳ありません。質問文に『大文字小文字区別なし』と書かれてありましたね。
・文字列で表す以上 0～9、A～Z の文字しか利用できないならば 6 桁で限界ですよ。
　バイナリの 2 進数で処理すれば 4 バイト(4桁)ですみますが、0～35 の数値を
　１桁の文字で表すのだから 6 桁以下には出来ません。ただし、先頭のゼロを省けば
　短くはなりますけど…。
・単純に36進数で変換して、先頭のゼロを省くようにすれば短く出来ます。それ以外は
　理論上無理！と思います。なお、ハフマン符号化すれば短くすることも出来ますが、
　8桁の数値を満遍なく表すとデータを圧縮できません。先頭のゼロを省いて表記する
　方が分かりやすいと思います。
・以上。おわり。

お礼

すみません、質問がわかりづらかったですね。
なんか例でも入れておけばよかったです。

>単純に36進数で変換して、先頭のゼロを省くようにすれば短く出来ます。
整数値ということもあり、こちらに関してはやってみています。

>それ以外は理論上無理！と思います。なお、ハフマン符号化すれば短
>くすることも出来ますが、8桁の数値を満遍なく表すとデータを圧縮で>きません。

すみません、この辺私の符号化等の理解が乏しくてよくわかっていません。8桁の数値を満遍なく表すとデータを圧縮できない理由をご説明願えませんでしょうか。

よろしくお願いします。

回答No.2

Oh-Orange

★BASE64とかはどうですか？
・64ビットを１桁に出来ます。
　でも 0～9、A～Z、a～z のみしか利用したくないのならば、10＋26＋26＝62進数で
　１桁を表すようにすれば BASE64 に近づけます。
・8桁の整数ならば、62進数で 5桁にパックされます。
　BASE64 でも 5桁になります。→BASE64 なら 5桁で 10＾9 まで表せます。
・以上。参考に。

お礼

ご回答ありがとうございます。

さて、62進数にするメリットはわかるのですが、
私の知識が間違っているのか、BASE64がなぜそこで出てくるのかがよくわかりません。むしろ桁数が増えるような。。。
http://ja.wikipedia.org/wiki/Base64

そして説明不足で申し訳ないのですが、
今回はアルファベットの区別ができないため、進数だけならば36が最大です。

回答No.1

FEX2053

ハフマン符号化するとか・・・。
http://www.01-tec.com/document/basic_compression.html

データに偏りがある場合（特定の数字が多発する場合）は、
ハフマン符号化はデータを短くするのに有効な手段です。

お礼

ご回答ありがとうございます。

ハフマン符号についてはよく知らないのですが、
変換対象の整数は一意のIDのため、使用頻度はほぼ一定でして
FEX2053さんがおっしゃるように符号化がデータ頻度があるものに有効なものならば、あまり効果はないかもしれません。
が、実際に試したことはないので調査して試してみたいと思います！

補足

参考URLありがとうございます。

少々「頻度」の意味を誤解していました。
リンク先を参考に勉強したいと思います！