二维码位流长度最小化算法

目的 快速响应矩阵码(quick response code,QR code)简称二维码,是一种由深色和浅色模块组成的正方形符号。给定输入数据,不同编码算法可能输出不同的位流。位流长度决定了二维码的版本,进而决定了二维码每条边上的模块数量。减小二维码的版本能够在不减小模块大小的前提下节省面积,或者在不改变面积的前提下增大模块大小。为了减小二维码面积、提高二维码识读率,本文提出了位流长度最小化算法。方法 首先,根据二维码位流可以分段切换编码模式的特点,归纳了6种编码状态;然后,根据二维码位流编码标准推导了状态转移关系,从而将位流长度最小化问题转换成动态规划问题;最后,通过求解动态规划问题,计算出最短位流。针对统一资源定位符(uniform resource locator,URL)类型数据,利用其部分字段对大小写不敏感、部分字段可以转义的性质,提出了统一资源定位符的最短位流计算算法,进一步缩短位流。结果 本文构建了一个测试集,包含603个编码了非URL数据的二维码,以及1 679个编码了URL数据的二维码。实验结果表明,本文算法与二维码标准相比,对于非URL测试集,位流长度减小的二维码占比9.1%,版本减小的二维码占比1.2%;对于URL测试集,位流长度减小的二维码占比98.4%,版本减小的二维码占比31.7%。结论 二维码位流长度最小化算法输出的位流长度最短,输出的二维码版本最小,能在兼容标准二维码解码器且不影响纠错能力的前提下提升二维码的数据容量。同时,本文算法运行速度快,易于使用,没有需要调节的参数。