游程编码

游程编码

• 概述

  • 游程编码又称“运行长度编码”或“行程长度编码”，RLE(Run- Length Encoding 行程长度编码)是一种统计编码，该编码属于无损压缩编码。
  • 在数据进行编码时，沿一定方向排列的字符可看成是连续符号，用字串代替这些连续符号，可大幅度减少数据量
  • 为一种“使用固定长度的码来取代连续重复出现的原始资料”的压缩技术
  • 游程编码记录方式有两种：①行记录每个游程的长度 ②逐逐行记录每个游程的终点列号

• 基本思想

  • 用一个符号值或串长代替具有相同值的连续符号（连续符号构成了一段连续的“行程”。行程编码因此而得名），使符号长度少于原始数据的长度。
  • 只在各行或者各列数据的代码发生变化时，一次记录该代码及相同代码重复的个数，从而实现数据的压缩。

• 适用场景

  • 源数据中存在大量重复的符号

• 样例

  • 输入:

    777773344444444

  • 输出:

    第一种方式：572384---5个7 然后是2个3  然后是8个4
    第二种方式：705307415---截止到第5个是7 截止到第7个都是3  截止到第15个都是4
    

• java实现--第一种方式且最小重复字符的长度是1
  · 压缩

   /**
     * 游程编码 压缩的实现--
     * @param src 原始字符串
     * @param num_len 重复字符的最大长度的位数
     * @return 压缩后结果
     */
    public static String RLCEncoding(String src, int num_len) {
        String STR_FORMAT = "";
        for (int i = 0; i < num_len; i++) {
            STR_FORMAT = STR_FORMAT + "0";
        }

        DecimalFormat df = new DecimalFormat(STR_FORMAT);
        StringBuffer sbuffer = new StringBuffer();

        int length = src.length();

        char c = src.charAt(0);
        int current_size = 0;
        for (int i = 0; i <= length; i++) {

            if (i == length) {
                sbuffer.append(df.format(current_size)).append(c);
                break;
            }
            char c1 = src.charAt(i);

            if (c == c1) current_size++;
            else {
                sbuffer.append(df.format(current_size)).append(c);
                current_size = 1;
                c = c1;
            }
        }

        return sbuffer.toString();
    }  

· 解压缩

    /**
     * 游程编码 解压缩的实现
     *
     * @param src     原始字符串
     * @param num_len 重复字符的最大长度的位数
     * @return 解压缩的结果
     * @throws ParseException
     */
    public static String RLCDecoding(String src, int num_len) throws ParseException {
    
        int num_len_1 = ++num_len;
        String STR_FORMAT = "";
        for (int i = 0; i < num_len; i++) {
            STR_FORMAT = STR_FORMAT + "0";
        }
    
        DecimalFormat df = new DecimalFormat(STR_FORMAT);
    
        StringBuffer sbuffer = new StringBuffer();
    
        int size = src.length() / num_len_1;
    
        for (int i = 0; i < size; i++) {
            String substring = src.substring(i * num_len_1, (i + 1) * num_len_1);
            long l = df.parse(substring).longValue();
            long len = l / 10;
            int numChar = (int) (l % 10);
    
            for (long i1 = 0; i1 < len; i1++) {
                sbuffer.append(numChar);
            }
        }
    
        return sbuffer.toString();
    }