download: 咕泡云 P6:Java 互联网高级架构师 4 期（SVIP 涨薪班）
ZY 复制下崽：https://www.zxit666.com/4278/
自研字符串压缩算法
概述
在开发中，常常有上报线上堆栈来分析处理线上问题的场景，所以，对堆栈的压缩和加密也是必不可少的。加密：可能使用 AES 对称加密算法，压缩：可能在上传时利用 protobuf 天生的紧缩性对字符串进行压缩。
不过，出于对流量的俭约和传输效率的晋升，可能通过在堆栈上传前先压缩一次数据来保障。上面给大家介绍一种笔者自己摸索的一种压缩字符串的算法，并且自带加密成果。
算法介绍
此算法使用场景：无限字符集的字符串压缩。
例如 Java 方法全限定名的压缩，对于方法全限定来说，组成成分：大小写英文字母，数字，特殊字符。在开发过程中，一个标准且合格的类名，方法名需要做到见名知意，根据无效统计，方法全限定 99% 以上由大小写英文字母组成。
算法实现
压缩原理简述
将 char 字符的空闲 bit 位来存储无效的数据。比如通过将 a ~ z 映射成 1 ~ 26 的数字, 并将 Char 类型以 5bit 为一组分为高、中、低三组，别离来存储一个数字（这一个数字代表一个字符）
建立字符串头结构: Head
在 Java 代码编写过程中，一个全限定字符串中的大写字母占比绝对较小，因此，通过使用前补充字符的形式来记录全限定字符串中的大写字母。一个字符串如果是无限且不可变的，那么所组成他们的字符之间的绝对地位是必定的。实现算法如下：
public char[] build(String s) {
...
for (int i = 0; i < len; i++) {c = s.charAt(i);
b = Character.isUpperCase(c);
if (b || c == FILL) {if (i - lastIndex >= maxDistance) {maxDistance = i - lastIndex;}
upCharIndex.add(i - lastIndex);
lastIndex = i;
}
if (b) upCharCount++;
}
...
return handleHead(type);}
复制代码
在压缩前的第一步：在字符串开始时，保存并记录大写字母的地位和每一个大写字母之间的距离。（小数点认为是一个大写字母）。
private char[] handleHead(int type) {
...
int k, j;
// 记录大写字母地位与 char 中
for (int i = 0; i < chars.length; i++) {if (i == 0) {for (j = 0, k = 1; j < ch1; j++, k++) {ch = bitToLeft(ch, upCharIndex.get(j), 12 - (k * stepDistance));
}
chars[i] = ch;
} else {
char emptyCh = FILL;
emptyCh &= 0;
int start = (i - 1) * sizeOfChar + ch1;
for (j = start, k = 1; j < start + sizeOfChar; j++, k++) {if (j == upCharIndex.size())
break;
emptyCh = bitToLeft(emptyCh, upCharIndex.get(j), 16 - (k * stepDistance));
}
chars[i] = emptyCh;
}
}
return chars;}
复制代码
Head 的最小长度为：1 个 Char，也就是 16bit。在 16bit 的高 2 位存储步长。接下来的 2 位记录真正的 Head 长度大小。
head 长度：Head 最小的长度是 1 个 Char，其中记录步长和 Head 长度的信息。目前，填充长度最长为 3+1, 可通过步长算法实现 Head 长度的扩大。扩大方法：getTypeBySize、getSizeByType
存储大写字母的地位时，按照步长来填充。例如：步长为 3, 那么就意味着每 3 个 bit 存储一个大写字母地位。
Head 的长度取决于填充了几个步长。例如：填充 10 个步长为 3 的地位，需要 16%3 等于 5，那么就需要两个 Char.
步长：步长是一个可变的量，在算法设计中，提供如下几种步长类型：（据统计最长英文单词：45 个字符）
STEP_0：示意没有大写字母
STEP_3：示意大写字母距离(0,8), 步长为 3
STEP_15：示意大写字母间距离[8，16), 步长为 4
STEP_OVER_15: 示意大写字母间距离[16，63)，步长为 6
建立压缩字符串内容：Content
Content 压缩是按照 1 个 Char 的高、中、低三位中别离存储一个字符的算法实现的。具体的实现 FormatUtil.ContentBuilder：
填充: 因为字符串并不都是 3 的倍数。为了保障原字符串的完好性，在宰割字符串之前先给原来字符串填充肯定数量的字符，保障其在宰割的时候可能每 3 个字符为一组。
public String handleString(String s) {
int f;
if ((f = s.length() % 3) != 0) {StringBuilder sBuilder = new StringBuilder(s);
for (f = 3 - f; f > 0; f--)
sBuilder.append(FILL);
s = sBuilder.toString();}
return s.toLowerCase();}
复制代码
宰割替换: 在实现填充当前，将原来的字符串以三个为一组宰割成多个组。对于字符串中的数字或者特殊字符，咱们在 mapping 文件中并没有形成映射，因此，一旦出现，那么就通过“MASK”去代替。
public short buildShort(char high, char mid, char low) {
short b = 0;
b |= getShortFromMapping(high) << 10;
b |= getShortFromMapping(mid) << 5;
b |= getShortFromMapping(low);
return b;}
public short getShortFromMapping(char ch) {
if (mapping.containsKey(ch))
return mapping.get(ch);
return mapping.get(MASK);}
复制代码
建立实现压缩后字符串
Head + content = 压缩实现后的字符串。
总结
在算法构思后期，实践压缩效率可达 66%：将三个 Char 存储在一个 Char 中，不过从最初包大小的总压缩率来计算，压缩率应该只有 50% 左右。出现这种的情况的原因如下：
字符串长度不都是 3 的整数倍，有多余的字符填充
压缩完当前的字符并不是一个正确的 ASCII 码，在 Java 底层对字符集的编解码过程中，将其认为是汉字，一次一个字符会被解码成两个字符大小。