一次自定义编码的探索

2019 年 10 月 21 日

朋友给了个题：
对1-500000000（别数了，5亿）的整数，实现一个encode编码方法，要求编码后的字符串只包含数字和字母，然后对应实现一个decode方法，可以将该字符串还原回去。
比如：

  • encode(123) => ‘jh52a2’
  • decode(‘jh52a2’) => 123

[要求]

  1. 编码后的字符串尽可能的短
  2. 不能明显看出连续的两个数字编码后的字符也是连续的:
    1. 123=>’jh52a2′ 124=>’jh52a3′ 就不符合要求
    2. 123=>’jh52a2′ 124=>’jh58iu’ 勉强符合
    3. 123=>’jh52a2′ 125=>’iu92s1′ 这就很好了

编码的方式我们其实接触过许多，最常见的莫过于：Base64了。编码与加密的区别在于，在知道算法的前提下，可以很容易得出编码前的值，而加密则需要密钥方可解密。所以决定了编码与加密的应用场景不一样，在算法公开的情况下，加密用于数据安全，而编码用于数据传输与存储。而在算法不公开的情况下，编码在一定情况下也可以当加密使用。

言归正传，分析下上面的题：

  1. 使用数字、字母作为编码因子，意味着我们可以使用的因子数有62个：[0-9a-zA-Z]，而涉及到数值的话，我们考虑使用62进制
  2. 5位62进制容量为 62x62x62x62x62 = 916132832，所以我们用5位编码即可表示1-5亿的整数
  3. 两个连续数字的二进制如：100110 与 100111 需要通过何种变换让其结果不明显连续？考虑位运算：
    1. 异或运算：c=a^b;a=b^c;b=a^c;
    2. 自定义移位运算：1101001 右移三位：0011101

当然，自己一开始在做的过程中并不是一次性这么想的，经过了多次坎坷的调整。

首先，实现62进制与10进制互转的方法：

const radix62 = (function radix62() {
    // 打乱基本单位，不按常规的0-9a-zA-Z
    const code = 'tkI8oWKbxh0VcpuZO7yq3QwrRHPT9evsjlFzSGYXCm1AigUBd4LMJN6n2af5DE';
    return {
        encode(dec) {
            let str = ''
            do {
                let quotient = Math.floor(dec / 62)
                let remainer = dec - quotient * 62
                str = code[remainer] + str
                dec = quotient
            } while (dec)
            return str
        },
        decode(str) {
            return [...str].reduce((acc, cur, index) => {
                let pos = code.indexOf(cur)
                if (pos === -1) throw new TypeError(`字符串：“${str}”中含有非62进制字符：“${cur}”`)
                return acc += pos * 62 ** (str.length - index - 1)
            }, 0)
        }
    }
})()

实现方式很简单，参考10进制如何转2进制、如何转16进制的方法，依葫芦画瓢。

然后再来实现自定义的位运算，这里对题目要求扩展下，虽然我们计算了表示5亿只需5位62进制，我们可以设计传入任意位表示：

class BitHanler {
    static getBitHanle(bitCount) {
        return new this(bitCount)
    }

    // 在str前补零，直至长度达到 bitCount
    static pad0(str, bitCount) {
        return ('0'.repeat(bitCount) + str).slice(-bitCount)
    }

    constructor(bitCount) {
        this.bitCount = bitCount
        this.isOdd = bitCount % 2 !== 0
        this.cls = this.constructor
    }

    // 十进制整数dec转二进制，并补零至bitCount位
    toBitCountBinary(dec) {
        return this.cls.pad0(dec.toString(2), this.bitCount)
    }

    // 移动二进制位，不同于 <<、>>运算，此运算挪出的位置会补到头或尾
    bitMov(dec, x, toRight = false) {
        let str = this.toBitCountBinary(dec)
        const pos = toRight ? -x : x;
        str = str.slice(pos) + str.slice(0, pos)
        return parseInt(str, 2)
    }

    rightMov(dec, x) {
        return this.bitMov(dec, x, true)
    }

    leftMov(dec, x) {
        return this.bitMov(dec, x)
    }

    /**
     * 核心方法，dec转成bitCount位的二进制后，均匀划分为两段 a,b 
     * a,b异或运算得到c: c = a ^ b
     * 拼接得到新的二进制形式： ca
     * 解码的时候同样的操作流程不过需要进行两遍：
     * b = c ^ a  得到 bc
     * a = b ^ c  得到 ab
     * @param {Number} dec 
     */
    bitXorAndSwap(dec) {
        const bin = this.toBitCountBinary(dec)
        const splitPoint = Math.floor(this.bitCount / 2)
        const left = bin.slice(0, splitPoint)
        const right = bin.slice(this.isOdd ? splitPoint + 1 : splitPoint)
        const middle = this.isOdd ? bin[splitPoint] : '';
        const newLeft = (parseInt(left, 2) ^ parseInt(right, 2)).toString(2)
        return parseInt(newLeft + middle + left, 2)
    }
}

有了62进制转换方式和位运算操作方法，我们就可以来实现encode和decode了：


class MyEncoder {

    static getEncoder(targetLen, salt) {
        return new this(targetLen, salt)
    }

    // 计算targetLen长度的62进制最多用多少位二进制表示
    static getBitCount(targetLen) {
        // targetLen长度的62进制数字容量
        let volume = 62 ** targetLen
        let bitCount = volume.toString(2).length
        // bitCount位的二进制不能溢出
        if (2 ** bitCount >= volume) bitCount--
        return bitCount
    }

    constructor(targetLen, salt) {
        this.targetLen = targetLen
        this.bitCount = this.constructor.getBitCount(targetLen)
        this.bitHanler = BitHanler.getBitHanle(this.bitCount)
        this.max = 2 ** this.bitCount // 能处理的最大数值
        this.moveBits = 3
        this.loops = 6
        //TODO 根据 salt 计算 moveBits 与 loops
    }

    encode(dec) {
        if (dec < 0 || dec >= this.max)
            throw new RangeError(`待编码的数值超出范围：[0, ${this.max})`)
        let i = 0
        while (i++ < this.loops) {
            dec = this.bitHanler.rightMov(this.bitHanler.bitXorAndSwap(dec), this.moveBits)
        }
        return radix62.encode(dec)
    }

    decode(str) {
        if (str.length < 1 || str.length > this.targetLen)
            throw new RangeError(`待解码的字符长度超出了设定的长度: 0 < len < ${this.targetLen + 1}`)
        let dec = radix62.decode(str)
        if (dec >= this.max) throw new RangeError(`待解码字符解码过程中溢出了，请确认该字符是否正确：${str}`)
        let i = 0
        while (i++ < this.loops) {
            dec = this.bitHanler.bitXorAndSwap(
                this.bitHanler.bitXorAndSwap(
                    this.bitHanler.leftMov(dec, this.moveBits)
                )
            )
        }
        return dec
    }
}

验证：

const encoder = MyEncoder.getEncoder(5)
const str0 = encoder.encode(965432)
const str1 = encoder.encode(965433)
const dec0 = encoder.decode(str0)
const dec1 = encoder.decode(str1)
console.log(str0, dec0)
console.log(str1, dec1)
// p4Eoy 965432
// hOrac 965433

标签：

您可能还喜欢...