二维码笔记系列:

唠唠闲话

上篇介绍了二维码的构成和编码过程,本篇对前两个步骤(数据分析和数据编码)进行详细的介绍。

跳转链接:

二维码规范

在进入正题之前,需了解二维码规范问题。二维码存在许多规范,比如国际标准组织 ISO/IEC 18004 已迭代了三个标准 2000, 2006, 2015. 此外,根据场景需求,编码细节上也存在差异。

比如下边的二维码,用微信/支付宝扫将得到字符 ゥョア,而用浏览器扫则得到 ©®±.
vague

出现差异的原因在字节模式,前者使用 ISO-8859-1 字符,后者则用 UTF-8 的前 256 个字符。

尽管如此,对于数字模式,数字字母模式,汉字模式和字节模式中的 ASCII 字符,识别通常不会有歧义。

本系列所做的取舍:

  • ISO/IEC 18004:2000 为基础
  • 字节模式使用 UTF-8 的前 256 个字符
  • 支持 UTF-8 字节模式
  • 不考虑 ECI 模式

数据分析

回顾二维码的编码步骤:

步骤 描述
数据分析 确定编码模式,选择纠错等级,确定最小版本
数据编码 将数据转换为二进制
纠错编码 生成纠错码并与原始数据交织构成数据区
构建二维码矩阵 功能区数据区填入矩阵
版本和掩码 将版本数据(若≥7)填入版本区;计算最佳掩码并处理数据区;最后将格式数据填入格式区

其中数据分析主要目的是确定二维码编码模式,本节内容:

二维码模式

二维码的编码模式:

  1. 数字模式(Numeric mode):十进制数字 0-9

  2. 字母数字模式(Alphanumeric mode),包括以下内容:

    • 数字 0-9
    • 大写字母(不包含小写!!)
    • 符号 $, %, *, +, -, ., /, : 以及空格
  3. 字节模式(Byte mode),默认指 8(位)字节模式,即 ISO-8859-1 字符集,其为 ASCII 码的补充;此外还有 UTF-8 字节模式,但有的二维码识别器可能不支持。

  4. 汉字模式(Kanji mode),适用于 Shift JIS(Shift Japanese Industrial Standards) 字符集的部分双字节字符。虽然用 UTF-8 编码也能编码汉字字符,但需使用 3-4 字节。原则上,生成二维码应尽可能使用字符集更小的模式,以减少二维码的大小。

  5. 扩展通道解释模式(ECI, Extended Channel Interpretation),直接指定字符集(例如 UTF-8)。但一些二维码阅读器不支持 ECI 模式,因而无法理解使用该模式的二维码。

  6. 结构化链接(Structured Append)模式,跨多个二维码码对数据进行编码,最多 16 个二维码码。本教程不会讨论这种模式,但以后可能会添加更多信息。

  7. FNC1 模式,允许二维码码用作 GS1 条码。本教程不会讨论这种模式,但以后可能会添加更多信息。

总的来说,本系列考虑的编码模式包括这几种:

编码模式 支持字符
数字模式 0-9
数字字母模式 0-9A-Z+-*/.%$:和空格
字节模式 ISO-8859-1单字节字符
utf-8字节模式 utf-8 字符
汉字模式 Shift JIS 部分双字节字符

注释说明

  1. 某些二维码阅读器可以识别在字节模式下哪些字符用了 UTF-8 编码,由于所有 Shift JIS 字符都可以用 UTF-8 表示,因此可以用字节模式编码 Kanji 字符。

  2. 但是 UTF-8 中的 Kanji 字符用三个字节(或在极少数情况下为四个)编码,而 Shift JIS 字符用两个或一个字节编码,开销更小。

  3. 某些二维码阅读器会自动检测是否在字节模式下使用了 UTF-8,但如果在字节模式下使用 UTF-8,则可能会显示不正确的字符。为了解决这个问题,可以使用 ECI 模式。如上所述,它可以在字节模式下指定与默认 ISO-8859-1 字符集不同的字符集。遗憾的是,并非所有二维码阅读器都支持 ECI 模式。

  4. 另一种选择是将 UTF-8 字节的顺序标记 (BOM, Byte Order Mark) 放在输入文本之前。一些 QR 码阅读器会通过读取 BOM 理解文本是以 UTF-8 编码的。但并非所有 QR 码阅读器都能正确解释这一点。

选择高效的模式

  1. 如果输入字符串仅包含数字 0-9,请使用数字模式

  2. 如果数字模式不适用,且输入字符可在字母数字表中找到,则使用字母数字模式,注意不含小写字母。

  3. 如果字符不在字母数字表,但可以用 ISO-8859-1 编码,请使用字节模式

  4. 如果所有字符都在 Shift JIS 字符集中,请使用 Kanji 模式。当然也可以用 UTF-8 编码的字节模式,但通常为 Kanji 字符使用 Kanji 模式能更好利用空间。

  5. 如果输入字符不能用前边的模式编码,则考虑用 UTF-8 字节编码模式。

  6. 此外,单个二维码也可以使用多种编码方式,只需在相应编码字节部分的前边追加模式指示符(暂不考虑)。

小结

  1. 根据数据内容选择最佳的编码模式
  2. 并非所有二维码阅读器都符合标准,选择模式时需考虑所用二维码阅读器
  3. 包含关系:数字模式 < 字母数字模式 < 字节模式 < UTF-8 字节模式;以及 Kanji 模式 < UTF-8 字节模式

数据编码

确定好了模式后,下一步是数据编码,每种编码模式都旨在为该模式中使用的字符创建尽可能短的位串。

内容概要:

第 1 步,选择纠错级别

在对数据进行编码之前,请选择纠错级别。二维码使用里得所罗门码(Reed-Solomon)进行纠错。此过程基于编码数据创建纠错码。二维码码阅读器可以使用这些纠错字节来确定它是否没有正确读取数据,并且可以使用纠错码字来纠正这些错误。

纠错有四个级别:L、M、Q、H,下表列出了级别及其纠错能力。

纠错等级 纠错能力
Error Correction Level Error Correction Capability
L(Low) 恢复 7% 的数据
M(Medium) 恢复 15% 的数据
Q(Quartile) 恢复 25% 的数据
H(High) 恢复 30% 的数据

第 2 步,确定数据的最小版本

  1. 不同大小的二维码称为版本,有四十个版本可用。最小的版本是版本 1,大小为 21 x 21 像素。版本 2 为 25 x 25。最大的版本是 40,大小为 177 x 177 像素,每个版本都比以前的版本大 4 个像素。每个版本都有最大容量,具体取决于使用的模式。此外,纠错级别进一步限制了容量。附录的字符容量表列出了给定编码模式和纠错级别的所有版本的容量。

  2. 如何确定最小版本:例如,短语 HELLO WORLD 有 11 个字符。如果使用 Q 级纠错对其进行编码,查表发现 Q 级纠错的版本 1 代码可以包含 16 个字母数字模式的字符,因此版本 1 是可以包含此字符数的最小版本。如果短语超过 16 个字符,例如 HELLO THERE WORLD(即 17 个字符),版本 2 将是最小的版本。

  3. 容量上限:最大容量的二维码版本为 40-L(版本 40,纠错级别 L)。下表列出了四种编码模式下 40-L 二维码的容量。这是单个二维码可以包含的最大可能字符数。

编码方式 40-L 版本在该模式下的可包含最大字符数
数字模式 7089 个字符
字母数字模式 4296 个字符
字节模式 2953 个字符
汉字模式 1817 个字符

第 3 步,添加模式指示符

每个编码模式都有一个**四位模式指示符(Mode Indicator)**来标识它。编码数据必须以适当的模式指示符开始,该指示符指定用于其后位的模式。下表列出了每种模式的模式指示符。

例如,如果以字母数字模式编码 HELLO WORLD,则模式指示符为 0010。

模式名称 模式指示器
数字模式 0001
字母数字模式 0010
字节模式 0100
UTF8字节模式 0100
汉字模式 1000
ECI 模式 0111

第 4 步,添加字符计数指示符

  1. 字符计数指示符是一串比特(位),记录编码数据的字符数。

  2. 计算文本的字符数,并将该数字转换为二进制指示符。指示符的长度取决于编码模式二维码版本

  3. 例如,如果以字母数字模式在版本 1 的二维码中编码 HELLO WORLD,根据下表可知,字符计数指示符长度为 9。而HELLO WORLD 的字符数为 11,将 11 写为长度 9 的二进制得到 000001011,并将其放在步骤 3 中的模式指示符之后,得到位串:0010 000001011

下表包含每种模式版本的字符计数指示符的位长

数据模式 版本 1-9 版本 10-26 版本 27-40
数字模式 10 12 14
字母数字模式 9 11 13
字节模式 8 16 16
汉字模式 8 10 12

第 5 步,使用所选模式进行编码

上一节通过数据分析选择编码模式后,根据所选模式编码数据,每种模式规则在下一节介绍。

比如用字母数字模式编码 HELLO WORLD ,目前已得的位串如下

模式指示器 字符计数指示器 编码数据
0010 000001011 01100001011 01111000110 10001011100 10110111000 10011010100 001101

注意数字模式和字母数字模式不是按照字节编码进行的,所以数据位长不一定被 8 整除。

第 6 步,填充为 8 位代码,并在必要时添加字节

前几步得到由模式指示符、字符计数指示符和编码数据组成的位串,因为二维码规范要求位串必须填满二维码的总容量,可能还要添加 0 和填充字节。填充规则如下

  1. 根据编码版本和纠错级别,查阅纠错表,将表格第一列的数字乘以 8 得到需要的位长。比如,版本 1-Q 对应数值为 13,因而总位长为 13 * 8 = 104

  2. 如果位串长度小于总位数,则必须在右侧补 0 作为终止符,若小的长度大于等于 4,则补上 4 个0, 否则小多少补多少。比如用版本 1-Q 的二维码编码 HELLO WORLD,前边已求得位串总长为 74,但实际需要的总长为 104,104 - 74 >= 4,因而补上 4 位。

  3. 加上终止字符后,如果字符串位数不是 8 的倍数,继续补 0 使其成为 8 的倍数。

  4. 如果字符串仍然太短,则在末尾反复添加以下两个字节,直到字节长度达到最大:11101100, 00010001,这两个字节对应十进制数为 236 和 17。

例子总结

最后,用一个例子总结数据分析数据编码这两步操作的内容,

目标:编码短语 HELLO WORLD

  1. 通过数据分析确定使用数字字母模式

  2. 选择纠错级别 Q

  3. 字符总长为 11,通过查阅字符容量表,确定使用版本 1

  4. 由于选择了字母数字模式,添加模式指示符 0010

  5. 根据编码模式和版本,确定计数字符的位长为 9;当前数据字符数为 11,计数字符写为位长 9 的二进制数 000001011

  6. 使用字母数字模式编码字符串,得到二进制数 01100001011 01111000110 10001011100 10110111000 10011010100 001101

  7. 补位补字节操作:

    • 查阅纠错表,版本 1-Q 的总位长为 13 * 8 = 104
    • 目前位串长度为 4 + 9 + 61 = 74,缺少长度大于 4,补充终止字符 0000
    • 此时总长度为 78,不是 8 的倍数,继续补充 0 到长度为 80
    • 此时仍然达不到总位长 104,交错补充字节 11101100, 00010001

综上,最后输出字节为下边几部分的拼接

  • 模式指示符 0010
  • 位长信息 000001011
  • 编码数据 01100001011 01111000110 10001011100 10110111000 10011010100 001101
  • 终止符 0000
  • 用 0 补齐为 8 的倍数 00
  • 将长度补到总长度,补充字节 11101100 00010001 11101100

编码规则

数字模式

  1. 首先将字符串三三分一组(10^3 < 2^10 = 1024),如果字符串的长度不被 3 整除,则最后一组数字长度为 1 或 2

  2. 对每一组进行编码

    • 如果该组长度为 3,则用长度为 10 的二进制数表示
    • 如果该组长度为 2,则用长为 7 的二进制数表示
    • 如果该组长度为 1,用长为 4 的二进制表示
  3. 以字符串 86775309 为例

    • 867 => 1101100011 三位数
    • 753 => 1000010010 三位数
    • 09 => 1001 一位数

数字字母模式

  1. 首先,将字符串两两一组(44^2 < 2^11 = 2048),如果长度为奇数,则最后一个自己一组

  2. 每一组中,将第一个符号的对应索引乘以 45,在加上第二个符号的索引,最后取 11 位二进制数;如果只有一个元素,直接取 6 位二进制数

  3. 以字符串 HELLO WORLD 为例

    • 分拆 HELLO WORLD => HE, LL, O , WO, RL, D
    • 计算 HE => 17 * 45 + 14 = 779 ,取 11 位二进制 01100001011
    • 其余几组类似,最后一组只有一个数,D => 13 取 6 位二进制 001101

字节模式

字节模式的默认字符集是 ISO-8859-1,当输入字符串包含无法以 ISO-8859-1 编码的字符时,可改用 UTF-8 编码。

这部分直接编码即可,比如 Hello world! 编码为

字符 二进制编码 字符 二进制编码
H 01001000 w 01110111
e 01100101 o 01101111
l 01101100 r 01110010
l 01101100 l 01101100
o 01101111 d 01100100
00100000 ! 00100001

拼接得到

1
2
01001000 01100101 01101100 01101100 01101111 00100000 
01110111 01101111 01110010 01101100 01100100 00100001

汉字模式

  1. 汉字模式只能对字节在 0x81400x9FFC0xE0400xEBBF(十六进制)范围内的双字节 Shift JIS 字符进行编码。这组字符可以在 Shift JIS 汉字代码表中找到。

  2. 汉字模式下对双字节 Shift JIS 字符进行编码,必须首先将字符转换为字节,分两部分进行。

  3. 第一部分:编码在 0x81400x9FFC 范围内的字符,以 0x89D7(荷) 为例:

    • 第一步,将编码减去 0x8140,得到数字 0x0897
    • 第二步,分成两个字节,高位字节 0x08 和低位字节 0x97
    • 第三步,将高位字节乘以 0xC0(192) 再加上低位字节,得到 0x0697
    • 最后,写成长 13 的二进制数 0 0110 1001 0111
  4. 第二部分:编码在 0xE0400xEBBF 范围内的字符,以 0xE4AA(茗) 为例:

    • 第一步,将编码减去 0xC140,得到 0x236A
    • 第二步,分为两个字节,高位字节 0x23 和低位字节 0x6A
    • 第三步,将高位字节乘以 0xC0(192) 再加上低位字节,得到 0x1AAA
    • 最后,写为长 13 的二进制数 1 1010 1010 1010
    • 两部分组合得到 11010101010100011010010111

特别注意,Shift JIS 字符的编码并不是连续的,所以第三步乘数仅为 192,而不是 256

附录表格

数字字母表(Alphanumeric)

第一行为编号,第二行为符号,其中索引 36 对应符号为空格

1
2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
0 1 2 3 4 5 6 7 8 9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z $ % * + - . / :

表格链接

  1. 字符容量表

  2. 纠错表

  3. ISO-8859-1 字符集

  4. Shift JIS(Shift Japanese Industrial Standards)

延伸阅读

摘自博客园:ASCII码、ISO8859-1、Unicode、GBK和UTF-8 的区别

  1. 为什么要编码:计算机中最小的存储单位是字节(byte),一个字节所能表示的字符数又有限,1byte= 8 bit,一个字节最多也只能表示 255 个字符,而世界上的语种又多,都有各种不同的字符,无法用一个 byte 表示。比如 Java 中一个字符 char 需要两个字节,从 char 到最小单位 byte 之间必须经过编码,反之为解码。简单说,编码解码就是实际字符与 bit/byte 之间的翻译过程,各种编码方式就是一部部字典。

  2. ASCII 码,全称 American Standard Code for Information Interchange,美国信息交换标准代码,是世界上最通用的单字节编码系统,主要用来显示现代英语及其他西欧语言。ASCII 码用 7 位表示,只能表示 128 个字符,0~31 表示控制字符如回车、退格、删除等;32~126 表示打印字符即可以通过键盘输入并且能显示出来的字符,其中 48~57 为0到9 十个阿拉伯数字,65~90 为26个大写英文字母,97~122 号为26个小写英文字母,其余为一些标点符号、运算符号等,具体可以参考 ASCII 标准表。

  3. ISO-8859-1,该编码是在 ASCII 编码的基础扩展而来,但它仍然是单字节编码,总共只能表示256个字符。既然 ASCII 只能表示 128 个字符,没有完全利用一字节 8 比特的容量,所以 ISO-8859-1 扩展了 ASCII 编码,在 ASCII 编码之上又增加了西欧语言、希腊语、泰语、阿拉伯语、希伯来语对应的文字符号,它是向下兼容 ASCII 编码的。

  4. GB2312,全称是《信息交换用汉字编码字符集·基本集》,它是双字节编码,编码范围是 A1-F7,其中 A1-A9 是符号区,总共包含 682 个符号;B0-F7 是汉字区,包含 6763个汉字。GB2312 覆盖了汉字的大部分使用率,但不能处理像古汉语等特殊的罕用字,所以后来出现了像 GBK、GB18030 这种编码。

  5. UNICODE,为了自己的语言能在计算机中正常显示,每个国家和地区都有各自的编码,所以编码多了谁也不认识对方的编码,这时候 ISO(International Organization for Standardization) 组织提出了一种新的编码叫 UNICODE 编码让全球的文化、字符、符号都能支持。UNICODE 在制定时计算机容量已不是问题,所以设计成了固定两个字节,所有的字符都用 16 位表示,包括之前只占 8 位的英文字符等,所以会造成空间的浪费,UNICODE 在很长的一段时间内都没有得到推广应用。

  6. UTF-16,UTF-16(Unicode Transformation Format) 的出现是 ISO 想要创建一个全新的超语言字典,世界上所有的语言都可以通过这个字典来相互翻译,可想而知,这个字典是多么的复杂、庞大。UTF-16 用两个字节来表示 Unicode 的转化格式,采用的是定长的表示方法,即任何字符都可以用两个字节表示。这样表示字符就是变得的非常方便。UTF-16 适合在磁盘与内存之间使用,字符和字节的相互转换会更加简单和高效,但不适合在网络上传输,因为网络传输可能会损坏字节流。而且还有一个缺陷,就是很大一部分的字符用一个字节就可以表示了,UTF-16 却用两个字节,有些浪费存储空间。所以有另一个编码方式就出现了,也就是 UTF-8。

  7. UTF-8,UTF-8 采用了一种变长技术,每个编码区域有不同的字码长度,不同类型的字符可以由 1-6 个字节组成。UTF-8 对 ASCII 字符使用单字节存储,单个字符损坏也不会影响后面的字符,所以 UTF-8 非常适合在网络上面传统,也是现在使用最广泛的编码之一。在表示中文方面,UTF-8 是除了 GBK 之外最理想的编码方式。

以下是 UTF-8 编码的工作方式(摘自 LeetCode 习题393

1
2
3
4
5
6
   Number of Bytes  |        UTF-8 sequence
--------------------+------------------------------------
1 | 0xxxxxxx
2 | 110xxxxx 10xxxxxx
3 | 1110xxxx 10xxxxxx 10xxxxxx
4 | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx