美文网首页
自研字符串压缩算法

自研字符串压缩算法

作者: BlueSocks | 来源:发表于2023-02-06 15:02 被阅读0次

    概述

    在开发中,经常有上报线上堆栈来分析处理线上问题的场景,所以,对堆栈的压缩和加密也是必不可少的。加密:可以使用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底层对字符集的编解码过程中,将其认为是汉字,一次一个字符会被解码成两个字符大小。

    相关文章

      网友评论

          本文标题:自研字符串压缩算法

          本文链接:https://www.haomeiwen.com/subject/cletkdtx.html