• 締切済み

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

0～99999999の正の整数を0-9の数字とa～zのアルファベット（大文字小文字区別なし）で表現したいと思います。 私が考え付いたのが単純に36進数にした場合で六桁なのですが、 これ以上に短くなる方法をご存知の方、教えていただけないでしょうか。 よろしくお願いします。

みんなの回答

  • Oh-Orange
  • ベストアンサー率63% (854/1345)
回答No.8

★最終的に何を求めていますか？ ・タイトルの『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桁の整数を限りなく短くしたいのですか？ 　詳しい補足をお願いします。

全文を見る
すると、全ての回答が全文表示されます。
noname#241104
noname#241104
回答No.7

99999999を２進数で表すために必要な桁は 　log99999999 / log2 = 26.57....　で２７ビット！ 99999999を36真数で表すために必要な桁は 　log99999999 / log36 = 5.140...　で６バイト...４８ビット！ どっちが短いかは一目瞭然。 じゃ、0～zを１バイトではなく 　log36 / log2 = 5.1699... で６ビットで表現するとしても３６ビット必要となる。 もっと文字種を増やさないと桁は短くなんないでしょうね。

全文を見る
すると、全ての回答が全文表示されます。
  • jacta
  • ベストアンサー率26% (845/3158)
回答No.6

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

全文を見る
すると、全ての回答が全文表示されます。
  • jacta
  • ベストアンサー率26% (845/3158)
回答No.5

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

tool0514
質問者

お礼

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

全文を見る
すると、全ての回答が全文表示されます。
  • Werner
  • ベストアンサー率53% (395/735)
回答No.4

可変長でもかまわないなら、 ・0～35は"0"～"z" ・36～1331は"00"～"zz" ・1332～47987は"000"～"zzz" (以下略) と符号化すれば、平均符号長は減らせます。 出現頻度が均等として5.5桁くらいですけどね。 最大長はやっぱり6桁。 （可変長はかまわないが、符号終端が分からないと困るというなら、 少しやり方を変える必要がある。）

tool0514
質問者

お礼

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

全文を見る
すると、全ての回答が全文表示されます。
  • Oh-Orange
  • ベストアンサー率63% (854/1345)
回答No.3

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

tool0514
質問者

お礼

すみません、質問がわかりづらかったですね。 なんか例でも入れておけばよかったです。 >単純に36進数で変換して、先頭のゼロを省くようにすれば短く出来ます。 整数値ということもあり、こちらに関してはやってみています。 >それ以外は理論上無理！と思います。なお、ハフマン符号化すれば短 >くすることも出来ますが、8桁の数値を満遍なく表すとデータを圧縮で>きません。 すみません、この辺私の符号化等の理解が乏しくてよくわかっていません。8桁の数値を満遍なく表すとデータを圧縮できない理由をご説明願えませんでしょうか。 よろしくお願いします。

全文を見る
すると、全ての回答が全文表示されます。
  • Oh-Orange
  • ベストアンサー率63% (854/1345)
回答No.2

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

tool0514
質問者

お礼

ご回答ありがとうございます。 さて、62進数にするメリットはわかるのですが、 私の知識が間違っているのか、BASE64がなぜそこで出てくるのかがよくわかりません。むしろ桁数が増えるような。。。 http://ja.wikipedia.org/wiki/Base64 そして説明不足で申し訳ないのですが、 今回はアルファベットの区別ができないため、進数だけならば36が最大です。

全文を見る
すると、全ての回答が全文表示されます。
  • FEX2053
  • ベストアンサー率37% (7987/21355)
回答No.1

ハフマン符号化するとか・・・。 http://www.01-tec.com/document/basic_compression.html データに偏りがある場合（特定の数字が多発する場合）は、 ハフマン符号化はデータを短くするのに有効な手段です。

tool0514
質問者

お礼

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

tool0514
質問者

補足

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

全文を見る
すると、全ての回答が全文表示されます。
  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. その他（プログラミング・開発）

関連するQ&A

  • ２桁の正の整数について

    問題は 2桁の正の整数で、二乗した数の下２桁がもとの数と同じになるようなものをすべてあげるのですが、 これは２桁だから10から99の数なんですよね？ でも,10から99の数を二乗して求めるのはとても時間がかかってしまいます。 簡単な求める方法はありますか？ おねがいします

  • ３桁の整数の表し方と証明

    各位の数字が全て異なり各位とも0でない３桁の整数がある。この整数の各位の数字を入れ替えて出来る全ての整数ともとの整数を加えると222の倍数になることを証明せよ。という問題ですが、、 もとの３桁整数を表すのに100a+10b+cと考えました。 各位を入れ換えた整数を例えば100b+10c+aとすると加えると101a+110b+11cとなります。これが222の倍数となると証明できないし、、。最初の３桁の整数の表し方が違うんですかね、、。すいません、教えて下さい。

  • 16進n桁の文字列変換の方法は？

    手持ちの本『JavaScriptポケットリファレンス』によると『toString(16)』で 整数値を16進数の文字列へ変換できるようです。 そこで質問します。 整数値『123』を16進数の4桁『007B』に変換する方法を教えて下さい。 『Number(123).toString(16).toUpperCase()』とすると『7B』ですので、 先頭に『00』を追加したいのです。どうすれば良いでしょうか？ あと、10進n桁の方法も同じように出来ると思いますが、その方法も一緒に教えて下さい。 以上。お願いします。→JavaScript 歴1.5ヵ月です。

  • nは3桁の正の整数で√n/12が整数になる数は何個

    nは3桁の正の整数で√n/12が整数になる数は何個ですか？ この問題の解き方教えてください。

  • 文字列から整数導き出したい

    お世話になります。 現在、簡易的な占いのプログラムを作ってみています。 フォームに入力された文字から占いの結果を表示するようなものを 作りたいのですが、中々うまくいきません。 仕組み的にはフォームから文字列をＰＯＳＴ⇒10進数の整数に変換⇒10進数の整数に対応する占い結果を表示という形を考えています。 文字列をbin2hex関数で16進数にはできるのですが、16進数から10進数変換する方法がわかりません。 何かより方法がありましたらご教授ください。

    • ベストアンサー
    • PHP
  • 整数問題／2ケタの整数を2個ずつ作る

    以下の問題です。 -------------------------------------- 1～9の数字が書かれた9枚のカードがあります。 今，Ａ君がまず２枚のカードを取り，十の位の数が一の位の数より大きくなるように並べて2ケタの数を作り，さらに2枚のカードを取り，十の位の数が一の位の数より大きくなるように並べて2ケタの数を作ります。こうして，Ａ君は2ケタの数を2つ作ります。 次に，Ｂ君が残りの5枚のカードからＡ君と同様に2ケタの数を2つ作ります。 Ａ君が作った2つの2ケタの数の和とＢ君が作った2つの2ケタの数の和が同じになったとき，和は全部で何通り考えられますか。 --------------------------------------------- [1]のカードを使わない場合は，繰り上がりがないので数えやすいのですが(6通り), その他の場合は，繰り上がりがないことの証明はどうしたらいいのでしょうか。 お力をお貸しください。

  • ５ケタの正の整数

    こんばんは。 SPIの問題を解いておりましたら、分からない問題が出てきまして。。。。。。。。 ５ケタの正の整数７２□□２があります。 この□□に適当な数字を入れて３の倍数となるようにした時、最大のものと最小のものの差はいくらですか。 このような問題です。 解答欄を見てみますと。。。。。。。。 ３の倍数の見分け方は、各位の数字の和が３の倍数であるかないか。 ５ケタの正の整数７２□□２では、 ７＋２＋□＋□＋２が３の倍数であるようにする。 従って、 最大は７２９７２。 最小は７２０１２。 その差は９６０である。 。。。。。。。。。。。。。このようになっていたのですが。。。。。 ３の倍数の見分け方は各位の数字の【和】が３の倍数であるかないか、という定義（概念？考え方？）が今いちピンとこないです。。。。。。。。。。 ７＋２＋□＋□＋２が３の倍数になるかならないかが問題を解く鍵になる。。。。。。。。。 根本の部分がダメなんでしょうね。。。。。。。。 試験まで丸暗記するしかないかな。。。。。。。と今は思ってます（苦笑） お時間のある時に回答して頂けると幸いです。

  • ある文字列の最後の２桁で分解し配列にする方法・・・

    こんにちは。 ある１２桁～２４桁の数字に＋１をした数字を表示しようとしています。 int型とfloat型が１６桁以上の数字が扱えないようなので、おかしくなってしまいます・・・ 1111111111111111の数字に＋１をすると 1.1111111111111E+15となります・・・。 これをどうにかできるようにしたいので、 この数字の最後の２桁で文字を分解し その２桁に＋１をして、 再び 最後の２桁とそれ以前の文字列とを足して 元の桁数にしようと考えました。 しかし、この最後の２桁で文字を分解し、各変数か配列に収める方法がわかりません・・・ 何かよい方法もしくは関数などありませんか？ どうか、よろしくお願いします。

    • ベストアンサー
    • PHP
  • 整数を文字列として認識したい

    整数を文字列として認識したいんですが、可能なのでしょうか？ 例えば、i=12470というint型の整数があるとして、1万の位の数1や、十の位の数7だけを取り出したいんです。 しかし、この際、1万の位の数1をi/10000、十の位の数7を(i%100)/10などというようにしては取り出したくないんです。 ややこしい質問ですが、よろしくお願いします。 というのも、整数を文字列として認識する目的は、int型として送られてきたデータが本当に整数なのかをチェックするためだからです。 初心者なので合っているか分かりませんが、整数を文字列として認識できれば、isdigit関数を使うことで、データが本当に整数なのかをチェックすることができるのかなあと考えているんですが・・・ もし、私の考えが間違っていたり、他に良い方法があったら是非教えて欲しいと思います。

  • エクセル　関数　文字列を分ける

    23Ar23 28Ar05 3Ta16 8Ta07 11Ta53 14Ta21 …以下多数 のように文字列があって、アルファベット前の数字（１文字か２文字）、アルファベット（2文字）、アルファベット後の数字（２文字）の３つに分割したいのです。データ区切り位置の機能を使えれば簡単ですが、アルファベットの前の文字数が１字と２字のものがあるのでできません。RIGHT、LEFTの関数を使用すれば、アルファベット２文字とアルファベット後の数字２文字は抽出できますが、アルファベット前の数字（１文字か２文字）だけ取り出せません。 関数か何かの方法で文字数を分ける方法を教えてください。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する