一次自定义编码的探索

  • 2019-10-21
  • 0
  • 0

朋友给了个题:
对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. 两个连续数字的二进制如:100110100111 需要通过何种变换让其结果不明显连续?考虑位运算:
    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进制转换方式和位运算操作方法,我们就可以来实现encodedecode了:


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
上一篇:    下一篇:

me@ccc5.cc - 衫小寨