[問題] 請問縮字串

看板Prob_Solve (計算數學 Problem Solving)作者 (cjcmt)時間14年前 (2010/11/12 23:14), 編輯推噓4(408)
留言12則, 5人參與, 最新討論串1/1
隨意的34個數字,每個數字都是在0~9之間,例如 12345678912345678912345678912345678,我想要用 比較短的字串(限ascii碼)去表示它。 目前想到的方式就是從第一個數字開始,拆成兩兩一 組,例如1234就視為12及34,然後再建一個00~99的 array(對照表),例如12 = a,34 = b,這以樣我就 可以用ab去表示1234了,可以縮短50%的長度。 但不曉得大家有沒有更好的解法可以縮的更短,或是 不需要建到100個的對照key呢? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.169.53.136

11/12 23:21, , 1F
直接做進位轉換就好啦,例如轉成 62 進位(數字+大寫+小寫)
11/12 23:21, 1F
※ 編輯: cjcmt 來自: 220.136.154.171 (11/12 23:30)

11/13 00:40, , 2F
visible ascii 其實只有 94 個 (33~126)...
11/13 00:40, 2F

11/13 00:41, , 3F
所以其實並不到 50%
11/13 00:41, 3F

11/13 00:41, , 4F
嚴格一點算的話最多是 log_94 10 = 0.50681 即 50.7%
11/13 00:41, 4F

11/13 00:42, , 5F
也就是至少要 18 個字
11/13 00:42, 5F

11/13 00:43, , 6F
不過要達成這樣你得自己寫個 34 位的大數除
11/13 00:43, 6F

11/13 00:46, , 7F
如果不要用大數除就只好九位一組(0~10^9-1)變成94進位五個字
11/13 00:46, 7F

11/13 00:46, , 8F
這樣還是有 55.56%
11/13 00:46, 8F

11/13 00:46, , 9F
huffman ?
11/13 00:46, 9F

11/13 00:54, , 10F
咦 我在說啥 @@
11/13 00:54, 10F

11/13 14:17, , 11F
其實不清楚你的目的XD....不然直接存成兩個long long (?)
11/13 14:17, 11F

11/14 19:48, , 12F
字典法 壓縮
11/14 19:48, 12F
文章代碼(AID): #1CtLdjGD (Prob_Solve)
文章代碼(AID): #1CtLdjGD (Prob_Solve)