あるバイナリ文字列があったとします


これを,ASCII の,case-insentive(大文字小文字を区別しない)だけで表すのに,どういった方法が考えられるでしょうか

よくバイナリの表現に使われる,MIME/Base64 は,case-inseintive ではないので使えません

base32,punycode(文字列以外で使えるかわからない),UTF-5(使えるのか?)などがあると思います

試しに base32 で実装してみたら,文字列がかなり長くなってしまう,という問題がありました

回答の条件
  • 1人5回まで
  • 登録:2008/11/21 11:37:20
  • 終了:2008/11/21 14:15:01

ベストアンサー

id:rev-9 No.2

rev-9回答回数61ベストアンサー獲得回数82008/11/21 12:38:20

ポイント78pt

>使える文字列は,[a-z0-9]のみ

 とすると36通りの文字しか使えないことになりますので、一桁で表せる情報量は最大でも\log {}_2 36≒5.17ビットです。base32では5ビット、したがって表すバイナリ列に統計的な偏りなどが存在しなければ、何をどう工夫してもbase32で表した場合の5/5.17≒0.97倍より短くはできません。base32表記をかなり長いとされるのであれば、情報論的にご要望を満たすことは不可能かと思います。

id:goodvn

ありがとうございます

直感的に考えても,base32 は使える文字列をほぼ全て使ってしまっていますものね...

他のところで工夫してみます

2008/11/21 14:08:21

その他の回答(3件)

id:zzz_1980 No.1

zzz_1980回答回数492ベストアンサー獲得回数642008/11/21 11:43:32

ポイント26pt

ここは基本にたちもどって、uuencode。

http://seclan.dll.jp/ccuubq.htm

id:goodvn

ありがとうございます

要件を書き忘れたのですが,使える文字列は,[a-z0-9]のみとなるため,uuencode は使えません

2008/11/21 12:03:19
id:rev-9 No.2

rev-9回答回数61ベストアンサー獲得回数82008/11/21 12:38:20ここでベストアンサー

ポイント78pt

>使える文字列は,[a-z0-9]のみ

 とすると36通りの文字しか使えないことになりますので、一桁で表せる情報量は最大でも\log {}_2 36≒5.17ビットです。base32では5ビット、したがって表すバイナリ列に統計的な偏りなどが存在しなければ、何をどう工夫してもbase32で表した場合の5/5.17≒0.97倍より短くはできません。base32表記をかなり長いとされるのであれば、情報論的にご要望を満たすことは不可能かと思います。

id:goodvn

ありがとうございます

直感的に考えても,base32 は使える文字列をほぼ全て使ってしまっていますものね...

他のところで工夫してみます

2008/11/21 14:08:21
id:q11 No.3

q11回答回数32ベストアンサー獲得回数22008/11/21 13:30:01

ポイント32pt

binhexとかだとバイト数が増えるので嬉しくないですよね。

古いのだとs9フォーマットとかあるけどこれも16進数に変換なので倍以上に増えますね。

ちょっとおぼろな記憶ですが、ishフォーマットで特定のスイッチを指定するとアルファベットだけ使ってくれたような記憶があります。

http://www.vector.co.jp/vpack/browse/person/an000019.html

↑こちらにソースもあるので参考になるんではないかと思います。

昔、ASCII文字しか送れないパソコン通信の時代にバイナリを送るためのエンコードかつデータ圧縮と訂正フォーマットが色々あったのでその頃のフォーマットでishファイルは一世を風靡していました。


http://homepage1.nifty.com/glass/tom_neko/web/web_03.html

id:goodvn

ありがとうございます

ish も検討しましたが,base32 に比べた場合に,サイズは小さくならないようだったので,検証はパスしました

2008/11/21 14:09:32
id:hamazo_special No.4

hamazo_special回答回数1ベストアンサー獲得回数02008/11/21 13:18:03

ポイント10pt

単純ですが、単に各バイトを2文字の16進数で表現するようにしてはだめですか?

変換後は元の文字列の倍の長さになります。

id:goodvn

binhex のことをおっしゃってますでしょうか?

2008/11/21 14:14:24
  • id:goodvn
    補足です.局所的に質問してしまったので,状況が分かりにくいかと思います

    状況としては,

    ある文字列(case-i の英数字+記号) -> 共通鍵暗号 -> 文字列

    とする処理を書いています

    このプロセスを経ることで,元は 26byte だった文字列が,約2倍の 53byte になってしまっています

    今,元の文字列が case-insentive なので,この特徴を使って圧縮を掛けた上で,共通鍵暗号へもっていこうと工夫していますが,元の文字列が短いために,既存のよく使われる圧縮アルゴリズム(zlibなど)で圧縮すると,逆にデータが増えてしまっています

    なんとか,バイナリデータを短い文字列であらわせれると,素敵です
  • id:zzz_1980
    既存のエンコード方式は入力として0x00-0xffを想定していますから、特別なエンコーダー・デコーダーを書かないとダメですね。
    入力も出力も同じ[a-z][0-9]でしょうか。
  • id:b-wind
    > base32 で実装してみたら,文字列がかなり長くなってしまう
    同じ情報量のデータをより少ない符号で表そうとするんだから、基本はどうやってもそうなると思うよ。
  • id:Mook
    文字種が限定されているのであれば、データ長が長くなるのはしょうがないのではないですか。
    base32 はデータ長が(8/5倍)になりますが、これが「かなり」と判断されるのであれば
    base64(4/3倍)など他のエンコードへの対応を考えるしかないのではないでしょうか。
  • id:dev_zer0
    まさか、26byteのcase-insentiveの文字列をもっと少ない桁数で出力したい
    ただし、文字種はcase-insentiveのままである
     
    ではないですよね?
  • id:zzz_1980
    質問者は入力が0x00-0xff(8bitフル)とは言っていないので…と外野で騒いでもしょうがないですが。
  • id:goodvn
    >zzz_1980さん
    はい.ありそうで,無いんですね,case-insensitive の文字列を圧縮するといったライブラリが.

    >b-windさん,Mookさん
    途中に,バイナリへの変換(暗号化)が絡むせいで,かなりサイズが大きくなっていたようです

    >dev_zer0さん
    いえ,元の文字列よりは長くなるのは想定してたのですが,一気に長くなりすぎたので,悩んでいました


    皆さん,回答とコメント本当にありがとうございました

    結局,暗号化周りを見直し,独自の圧縮ルーチンを書く事で,元の文字列の2割増しくらいで,欲しい文字列が得られました
  • id:goodvn
    元が,case-insensitive な文字列を前提とするため,独自の 6bitエンコーディングを使い,27byte の文字列を 33byte に,23byte の文字列を 29byte という程度に抑えることができました.(サイズが増えるのは,6bit をフルに使わないため)

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません