データを圧縮したい

0或いは1が512個連続するビットパターンがあります。

11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

のようなのです。

これを

eYLfJXkQiS6{m"mMtI;|l"dajI.| YBCy/`usySwXm7n95(ad#oj6m7K5A:kRY5SC.)4}EvHND5R8a

まで圧縮できました。

もっと圧縮する方法はありますか？

テキストファイル（データ）しばりでお願いします。

これぞという回答お待ちしています。

No.19 回答者： tatsu99 回答日時： 2014/09/16 20:07

今回の要件をまとめると

要件１．512ビット(=64バイト）の任意のバイナリデータがある。
要件２．これをテキストファイル用の文字で表示したい。
テキストファイル用の文字とは、文字コードが16進数で0x20(スペース)から0xFE（チルダ）
の範囲の95文字である。
要件３．現在７８文字で表示可能であるが、77文字以下で表示可能な方法がないか。

ということでしょうか。
もし、要件２で、さらに使用可能な文字があるなら、その文字を追加して使用すれば、さらに
小さくなりますが、95文字が前提なら、78文字より小さくする方法はありません。
（６４バイトの任意データを95進数で表示すると７８桁となる。）
但し、
前提４．特定のデータについては、77文字以内で、それ以外のデータは78文字で表示できれば良い。
ということであれば、以下のようにして、特定のデータのみ小さくすることは可能です。
１．６４バイトデータを良く知られた方法で圧縮する。（例：zip形式等）
２．それが６３バイト以内に圧縮された場合は、95進数で変換。（結果は必ず77バイト以内になる）
３．６３バイト以内にならない場合は、圧縮前のデータを95進数に変換。（結果は必ず78バイトになる）
４．復元時は、７８バイトかそうでないかで、zip形式等の圧縮の有無を判定する。

この回答への補足

>要件１．512ビット(=64バイト）の任意のバイナリデータがある。

512バイトのテキストデータです。（別に全角の０，１で1024バイトとかでもいいけど）

>前提４．特定のデータについては、77文字以内で、それ以外のデータは78文字で表示できれば良い。

特定のデータかそうでないかという区別は実質できないですね。

圧縮率が高いのは法則性があるからと思いますが、法則性があると望ましくないデータなのです。(入力、出力ともに)

補足日時：2014/09/16 21:26

No.18 回答者： SortaNerd 回答日時： 2014/09/15 19:39

ああ失礼、こんな文章なんでまともに読んでなかった。

この回答への補足

お気になさらずに。

補足日時：2014/09/16 01:16

No.17 回答者： uyama33 回答日時： 2014/09/15 06:58

http://www.amazon.co.jp/%E3%83%87%E3%83%BC%E3%82 …

これ。

この回答への補足

どうも。
金ないので買えないので、どこか落ちてないか探します
知ってたら教えてください。要約でもいいです。

補足日時：2014/09/15 16:46

No.16 回答者： nag0720 回答日時： 2014/09/15 06:52

Shift_JISコードでいいのなら、半角カナも使えるので１バイトで95+63=158個の文字が表現可能

158^70<2^512<158^71

で、71バイトまでは圧縮できる。

この回答への補足

半角カナはさすがに勘弁願います…

補足日時：2014/09/15 16:44

No.14 回答者： SortaNerd 回答日時： 2014/09/15 03:40

Ascii85

この回答への補足

それ78文字より小さくなるんですか？

補足日時：2014/09/15 16:44

No.13 回答者： uyama33 回答日時： 2014/09/14 16:50

”データ圧縮ハンドブック”　トッパン

M.ネルソン　著　　荻原　山口　訳

古い本ですが、参考になると思います。

この回答への補足

入手のあてがありません

補足日時：2014/09/15 03:10

No.12 回答者： wormhole 回答日時： 2014/09/14 13:50

#9です。

とりあえずいっておくと'0'と'1'の2種の文字で512文字ということはバイナリで512ビット、1バイト8ビット換算で64バイトのデータとして表せますが、64バイト程度のデータは汎用的な方法では圧縮はあんまりできませんし、それをテキスト化すると64バイトよりもたいてい増えます(一番元となる512文字よりは少ないでしょうけど)。
並びに何か規則性があるとかならまた違いますが。

この回答への補足

ですね。
すいませんが他の回答への補足を見て頂いたうえで何か教えて頂けたら幸いです。

補足日時：2014/09/15 03:12

No.11 回答者： kmee 回答日時： 2014/09/14 13:41

(1) 0と1から構成される512文字の文字列を、 512ビット(64バイト)のバイナリデータに変換

(2) (1)を処理する
(3) (2)をテキストの範囲の文字列に符号化して出力

※ビット毎の処理が面倒、かつ、文字列操作が簡単なら、(1)の変換を行わないで、文字列をそのまま「512ビットのデータ」として扱う、という手段もある

というのが、基本の流れです。
例の一つが #9 にある
(2) : なにもしない
(3) : Base64と同じ手法を使ってテキストの範囲に符号化
というものです。


(2)で何かの圧縮処理をすることで、より短い出力になる可能性はあります。
(例えば、ZIP圧縮するとか)
しかし、短くなるか、かえって長くなるかは、入力に依存します。
必ず短くなる、と保証できません。

例えば。
ランレングス法という圧縮方法があります。これは、データを、1が続く数、0が続く数で表現します。
質問にあったものに適用するなら「1が512」となります。
連続するデータが多いと、圧縮率も高いのですが、0/1がランダムになっていると非常に効率が悪いです。
元と同じデータ量になったり、ランレングスの情報を加えた分元より大きくなったりもします。


(3) は、元のmビット、つまり、2進数m桁の数値を、n進数何桁で表現できるか、で長さが決まります。

上記より、最悪は512ビットです。
いわゆる16進文字列なら、
2^612 = 16^128
で128文字
Base64なら
64^85 < 2^512 <= 64^86
で86文字
ASCIIの印字可能文字(≒テキスト)は95文字なので
95^77 < 2^512 <= 95^78
で78文字
です。


つまり、データの内容に依らずに保証できるのは 「ASCIIの95文字を使った 78文字」です。
これ以上短くなるかどうかは、データの内容と(2)の処理に依存します。

処理のコストやプログラムの難易度を考えたら、「(2)の処理無しで(3)にBase64」で妥協するのがいいかもしれません。


・余談
ビットパターンと言えば、コンピュータ内部での0/1のパターンのことを指します。「 0と1からなる文字列」ではありません。
ビットパターンは0/1の列ですので、別の値が入ったり途中で切れたりしないという意味では「0と1の連続」です。
ですが、そんなのは当り前なので、そのことを「連続」と言ったりはしません。
「0または1が連続」と言われれば「000....」「1111....」を意味するのが当然です。

この回答への補足

＞必ず短くなる、と保証できません。
保証できないとだめです。

＞データの内容に依らずに保証できるのは 「ASCIIの95文字を使った 78文字」です。

やっぱこれしかないんですね。
なんか不可能な質問をしてしまったみたいですいませんでした。

＞・余談
ビットパターンと言えば、コンピュータ内部での0/1のパターンのことを指します。「 0と1からなる文字列」ではありません。
ビットパターンは0/1の列ですので、別の値が入ったり途中で切れたりしないという意味では「0と1の連続」です。
ですが、そんなのは当り前なので、そのことを「連続」と言ったりはしません。
「0または1が連続」と言われれば「000....」「1111....」を意味するのが当然です。

よく分かりました。これからは「０と１で構成された文字列」と書くことにします。

補足日時：2014/09/15 03:17

この回答へのお礼

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

お礼日時：2014/09/15 03:18

No.10 回答者： ts3m-ickw 回答日時： 2014/09/14 12:38

これ、結果もテキストでないとダメって言ってるのかな‥‥。

テキストの定義から必要になりそうだ。

「1」を1、「0」を0に定義すれば512ビットで済む。
7ビットASCII文字にして、0x00～0x1Fのときは8ビットに拡張して、
73文字くらいにはできるか。
提示されたのとあまり変わらないね。

この回答への補足

＞これ、結果もテキストでないとダメって言ってるのかな

そうです。
処理が終わるとメモ帳が自動的に開いて結果が表示されるとか、コマンドプロンプトで実行したら結果が次の行に表示されるとかってかんじです。

＞「1」を1、「0」を0に定義すれば512ビットで済む。
7ビットASCII文字にして、0x00～0x1Fのときは8ビットに拡張して、
73文字くらいにはできるか。

もう少し詳しく教えてください。
入力と表示（出力）はふつうに出来ますか？
人間が手で、普通のキーボードから入力したり、結果をコピペしてブラウザで検索したりとか。

＞提示されたのとあまり変わらないね。

1文字でも少ないほうがいいので、教えてください。

補足日時：2014/09/15 03:09

この回答へのお礼

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

お礼日時：2014/09/15 03:19

No.9 回答者： wormhole 回答日時： 2014/09/14 10:00

あなたが質問されたい事が

「文字の'0'と'1'で構成された512文字を効率よく圧縮する方法はありませんか。ただし圧縮後はASCII文字のテキストで表現できる形式でお願いします。」
という事なら、
圧縮ではないですが、どんなパターンでもASCII文字86文字のテキストにする方法でよければあります。

・6文字を1つの単位としてASCII文字を1文字割り当てる。
・6文字を1つの単位にすると512文字の場合、2文字あまるのでその2文字には'0'を4文字追加して6文字にする。
・ACSII文字の割り当てはbase64を参考に次のようにする。

000000 A
000001 B
000002 C
...
111111 /

この方法だと質問に書かれている'1'が512文字のパターンは

/////////////////////////////////////////////////////////////////////////////////////w

になります。

この回答への補足

＞「文字の'0'と'1'で構成された512文字を効率よく圧縮する方法はありませんか。ただし圧縮後はASCII文字のテキストで表現できる形式でお願いします。」

もうすこし条件が付きますがそういうことです

＞どんなパターンでもASCII文字86文字のテキストにする方法でよければ

それだったら最初に質問に書いたののほうが少ないので。
でも考えてくれてありがとうございました。

補足日時：2014/09/15 03:03

この回答へのお礼

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

お礼日時：2014/09/15 03:19