数字字符串压缩与解压

在玩NB-IoT的时候会向服务器上报一串数字，但是直接上报会比较浪费流量，因此想了一个办法来简单压缩数字字符串。这个办法就是利用进制转换，把十进制的数字字符串转换到0~9、A~Z、a~z三组字符组合起来的数字空间。

之所以不用char的0~255的空间，是因为Iot上传数据的时候会要求使用可显示字符。

之所以不用0~9、A-Z、a~z之外的可显示字符是为了看起来简洁。当然如果实在紧张也可以把其它可显示字符纳入进来。

由于数字字符串通常比较长，很难用编译器自带的int、int64来直接运算。所以需要自定义一个类型

压缩

typedef struct big_int {
  int8_t d[1024]; // 数字在这里用逆序的方式存储，比如123，按字节从低到高存的是3,2,1，且是数字，不是字符
  int len;

  big_int() { len = 0; }
} BigInt;

由于进制转换只需要用到除法，因此写一个除法运算

BigInt divide(const BigInt &a, int b, int &m) {
    BigInt r;

    m = 0;
    for(int i=a.len-1; i>=0; i--) {
        m *= 10;
        m += (int)a.d[i];

        if(m < b) {
            r.d[i] = 0;
        } else {
            r.d[i] = (int8_t)(m / b);
            m %= b;
        }
    }

    r.len = a.len;

    for(int i=r.len-1; i>=1; i--) {
        if(r.d[i] != 0) {
            break;
        } else {
            r.len--;
        }
    }

    return r;
}

接着利用短除法来进行压缩

std::string compress(const BigInt &x) {
  std::string n;
  const std::string CHAR = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
  cout << CHAR << endl;
  BigInt t = x;
  while (true) {
    int m = 0;
    int divN = CHAR.length();
    BigInt d = divide(t, divN, m);

    n += CHAR[m];

    if (d.len == 1 && d.d[0] == 0) {
      break;
    }

    t = d;
  }

  reverse(n.begin(), n.end());
  return n;
}

解压

解压算法直接用go语言实现，go可以直接利用它的math/big来运算大整数

package main

import (
	"fmt"
	"log"
	"math/big"
)

const CHAR = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

var inxTab map[rune]int

func init() {
	inxTab = make(map[rune]int)
	for i, c := range CHAR {
		inxTab[c] = i
	}
}

func decompress(s string) string {
	r := big.NewInt(0)
	base := big.NewInt(int64(len(CHAR)))
	for _, c := range s {
		inx := inxTab[c]

		r = r.Mul(r, base)

		n := big.NewInt(int64(inx))

		r = r.Add(r, n)
	}

	return fmt.Sprintf("%s", r)
}

func main() {
	defer fmt.Println("Program Exited...")
	log.Println(decompress("aB1"))
}