[問題] 請問縮字串

看板Prob_Solve作者 (cjcmt)時間15年前 (2010/11/12 23:14), 編輯推噓4(4推 0噓 8→)
留言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
‣ 更多 cjcmt 的文章
文章代碼(AID): #1CtLdjGD (Prob_Solve)