后记:
-- 极限压表.
先摆上压之前的, 长这个样:
记 0:
为了方便压表, 将原序列转化成前缀和形式.
从 48 种字符处理成 11 种,
便于下面的压表.
记 1:
使用相等字符压表. 压缩效果并不好...... 实测无效 =.=
效果:
不使用前缀和优化:
** 我要前缀和有何用
下面有用 (滑稽
附: 前缀和后相等的串长会全部减一, 于是就会导致连续相等字符数减少于是前缀和压缩效果会变差
记 2:
处理成前缀和后, 可以将两个字符暴力压成一个......
$11$ 进制, 两位是 $121$, 一个 $char$ 是 $127$, 挺好.
但是问题在于在 $\mathsf{ASCII}$ 表码上找不到一段长度 $\geq 121$ 的有效字符?
下面是打出来的表码
- !
- "
- #
- $
- %
- &
- '
- (
- )
- *
- +
- ,
- -
- .
- /
- 0
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- :
- ;
- < =
- >
- ?
- @
- A
- B
- C
- D
- E
- F
- G
- H
- I
- J
- K
- L
- M
- N
- O
- P
- Q
- R
- S
- T
- U
- V
- W
- X
- Y
- Z
- [
- 93 ]
- ^
- _
- `
- a
- b
- c
- d
- e
- f
- g
- h
- i
- j
- k
- l
- m
- n
- o
- p
- q
- r
- s
- t
- u
- v
- w
- x
- y
- z
- {
- |
- }
- ~
是这样......
所以实现起来可能还需要一些其他的技巧?
理论上可以实现并压到 $500KB$
记 3:
一种专业压缩的数据结构: 哈夫曼树.
显然我去颓了一波代码.
并且实现也像 ** 一样.
在前缀和后, 内部的字符频数是这样的:
G | H | I | J | K | L | M | N | O | P | Q |
407022 | 326991 | 169760 | 63867 | 23165 | 6733 | 1822 | 486 | 119 | 30 | 5 |
那么在这棵树上是长这个样的:(这里我们用 H 表示 0)
编号 | 字母 | 字符频数 | 编码 |
1 | G | 407022 | 0 |
2 | H | 326991 | 11 |
3 | I | 169760 | 101 |
4 | J | 63867 | 1001 |
5 | K | 23165 | 10001 |
6 | L | 6733 | 100001 |
7 | M | 1822 | 1000001 |
8 | N | 486 | 10000001 |
9 | O | 119 | 100000001 |
10 | P | 30 | 1000000001 |
11 | Q | 5 | 1000000000 |
具体节点:
编号 | 字符 | 权值 | 父亲 | 左孩子 | 右孩子 |
1 | G | 407022 | 21 | 0 | 0 |
2 | H | 326991 | 20 | 0 | 0 |
3 | I | 169760 | 19 | 0 | 0 |
4 | J | 63867 | 18 | 0 | 0 |
5 | K | 23165 | 17 | 0 | 0 |
6 | L | 6733 | 16 | 0 | 0 |
7 | M | 1822 | 15 | 0 | 0 |
8 | N | 486 | 14 | 0 | 0 |
9 | O | 119 | 13 | 0 | 0 |
10 | P | 30 | 12 | 0 | 0 |
11 | Q | 5 | 12 | 0 | 0 |
12 | \ | 35 | 13 | 11 | 10 |
13 | \ | 154 | 14 | 12 | 9 |
14 | \ | 640 | 15 | 13 | 8 |
15 | \ | 2462 | 16 | 14 | 7 |
16 | \ | 9195 | 17 | 15 | 6 |
17 | \ | 32360 | 18 | 16 | 5 |
18 | \ | 96227 | 19 | 17 | 4 |
19 | \ | 265987 | 20 | 18 | 3 |
20 | \ | 592978 | 21 | 19 | 2 |
21 | \ | 1000000 | 0 | 1 | 20 |
\: 中间节点, 具体字符无影响.
那么理论压缩后表长:$244KB$
优秀的算法!
依然过不了...... 但是可以启发思路 (巨雾)
部分内容源自 ooo 大神
$$\text{%%%ooo}$$
来源: http://www.bubuko.com/infodetail-3259515.html