10進数の巨大数をなるべく少ない文字列で表したい

表題の通りです。
例えば

1982398471093871098719831489020412341

のような数字をなるべく少ない文字列で表したいです。

８８進数などを作る　→　できても2桁の省略
2桁ごとに区切って１００進数等適用　→　半分ほど省略できますが、文字コードの考慮必要あり

等考えましたが、より良い方法が思い浮かびません。
この手の問題はきっと先人が何万回も考えていることかと思いますが、どのように検索すればよいか分かりませんでした。
よろしくお願いします。

Zuishin

2022/05/03 01:40

「なるべく」がどの程度を想定しているのかによります。場合によってはランレングス、もしくはもっと高度な圧縮アルゴリズムを使用する必要があります。

rzgriz11

2022/05/03 01:55

コメントありがとうございます。また、検索のヒントありがとうございます。「圧縮」技術にて調べてみます。 1文字まで絞れれば最高です。元の文字列長から1/4までは最低限、短縮したいです。

rzgriz11

2022/05/03 02:03

想定している場面について１、NW.jsにて数値を取得２、その数値を文字列にして圧縮３、jsonファイルに記述・保存する４、jsonファイルより参照した際に解凍５、数値を適用するという流れになります。このため、可逆圧縮であることが条件です。

行動規範の内容に同意します

回答2件

ベストアンサー

情報理論的に冗長な部分を削るのが（可逆）圧縮だけど、提示の数値単体では冗長性（＝法則）が見いだせない。せいぜい、数値をBase64みたいなのでエンコードすればBase10(ASCII数値文字列)より桁数は減るよ、程度（1byteあたりのペイロードが6bitと3.3bitなので、桁数は約半減。提示の「2桁区切りで100進数」と同じ）。

複数の数値があれば、相関がでて圧縮できることもある。DNSみたいな、「前に出てきた何バイト目～何バイトと同じ」とか、「前の値に＋2411」とか。
あるいは、プログラム側に辞書を内蔵しておくとか(HTTP3系）、何らかの法則によって生成された数値であるなら数式を内蔵して、係数を渡す手もあるかもしれない。
＃json全体をgzip圧縮したようなのの方が縮んだりすることも多いけどね。

1文字まで絞りたい？辞書内蔵で1982398471093871098719831489020412341に対して（だけ）コード'A'を割り振るみたいな仕様にすれば絞れるけど、辞書式で絞りたい他の数値が300種類でもあったら原理上無理だよね。1byteで区別できるのは255種だし、UTF-8の1byte1文字なら127種で空白・制御記号を外すと100もない。
UnicodeのEMOJIとかの複雑な結合を「1文字」とするのであれば、楽しい符号化もいろいろ考えられるけど、もちろん実用上のメリットは全くない。（表示上1文字幅になるけど、実際は60byteあって4byteのペイロードを保持する、みたいな話。）

投稿2022/05/03 02:39

matukeso

総合スコア1590

rzgriz11

2022/05/03 02:50

詳細なご回答を頂きありがとうございます。首肯ございます。原理的に半分に圧縮がいいところのようですね。ただ、冗長性というヒントも頂きましたので、圧縮、冗長性という2キーワードにてさらに考えてみたいと思います。 Zuishin様、matukeso様コメント、ご回答いただきありがとうございました。

行動規範の内容に同意します

８８進数などを作る　→　できても2桁の省略

2桁の省略とはどういうことでしょうか？

８８進数を作るとこんな感じになって37桁から19文字になります。
asciiで問題が起きそうにない文字を利用すると93進数まで作れますがその場合も19文字でした。

python
1data = 1982398471093871098719831489020412341
2
3#t = ' !"#$%&()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[]^_`abcdefghijklmnopqrstuvwxyz{|}~'
4t = ' !"#$%&()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[]^_`abcdefghijklmnopqrstuvwxy'
5
6def encode(d, r = ''):
7  s = len(t)
8  (d, m) = divmod(d, s)
9  r = t[m] + r
10  if d == 0:
11    return r
12  return encode(d, r)
13
14def decode(d, r = 0):
15  r = t.index(d[0]) + r * len(t)
16  if len(d) > 1:
17    return decode(d[1:], r)
18  return r
19
20print(data, len(str(data)))
21
22s = encode(data)
23print(s, len(s))
24print(decode(s))

あとは冗長性以外では、出現頻度に差があれば、その頻度によってビット長を変えて割り当てるのもありですね。
その場合は辞書を内蔵する必要があります。
例えば、0が他のすべての文字と同じだけ出現する場合には
0 - 0
1001 - 1
1010 - 2
1011 - 3
1100 - 4
1101 - 5
11100 - 6
11101 - 7
11110 - 8
11111 - 9