如果您是一名开发人员并且面临选择编码的任务，那么 Unicode 几乎总是正确的解决方案。 具体的表示方法取决于上下文，但大多数情况下这里也有一个通用答案 - UTF-8。 它的好处是它允许你使用所有 Unicode 字符而无需花费 太多了 大多数情况下有很多字节。 确实，对于不仅仅使用拉丁字母的语言，“不要太多”至少是 每个字符两个字节。 我们能否做得更好，而不回到将我们限制为只有 256 个可用字符的史前编码？
下面我建议您熟悉一下我回答这个问题的尝试，并实现一个相对简单的算法，该算法允许您存储世界上大多数语言的行，而无需添加 UTF-8 中的冗余。
免责声明。 我将立即做出一些重要的保留： 所描述的解决方案不作为 UTF-8 的通用替代品提供，它只适用于一小部分情况（下面会详细介绍），并且在任何情况下都不应该使用它与第三方 API（他们甚至不知道）进行交互。 大多数情况下，通用压缩算法（例如 deflate）适用于大量文本数据的紧凑存储。 此外，在创建我的解决方案的过程中，我发现了 Unicode 本身的现有标准，它解决了同样的问题 - 它有点复杂（而且通常更糟），但它仍然是一个公认的标准，而不仅仅是把一起放在膝盖上。 我也会告诉你关于他的事。
关于 Unicode 和 UTF-8
首先，简单介绍一下它是什么 统一 и UTF-8.
如您所知，8 位编码曾经很流行。 有了它们，一切就变得简单了：256 个字符可以用 0 到 255 之间的数字进行编号，而 0 到 255 之间的数字显然可以表示为一个字节。 如果我们回到最开始，ASCII 编码完全限制为 7 位，因此其字节表示中的最高有效位为零，并且大多数 8 位编码与其兼容（它们的不同之处仅在于“上”）部分，其中最高有效位是 XNUMX ）。
Unicode 与这些编码有何不同？为什么有这么多与其相关的特定表示形式 - UTF-8、UTF-16（BE 和 LE）、UTF-32？ 我们按顺序来整理一下吧。
基本的 Unicode 标准仅描述字符（在某些情况下，字符的各个组成部分）与其数字之间的对应关系。 这个标准中有很多可能的数字 - 从 0x00 对 0x10FFFF （1 件）。 如果我们想将这样一个范围内的数字放入一个变量中，114 个或 112 个字节对我们来说都不够。 而且由于我们的处理器并不是专门为处理三字节数字而设计的，因此我们将被迫每个字符使用多达 1 个字节！ 这就是UTF-2，但正是因为这种“浪费”，所以这种格式并不流行。
幸运的是，Unicode 中的字符顺序不是随机的。 他们的整套分为17“飞机”，每个包含 65536 (0x10000）“代码点” 这里“代码点”的概念很简单 字符数，由 Unicode 分配给它。 但是，如上所述，在 Unicode 中，不仅单个字符被编号，而且它们的组成部分和服务标记也被编号（有时根本没有任何东西与数字相对应 - 也许暂时，但对我们来说这并不那么重要），所以更正确的做法是始终具体谈论数字本身的数量，而不是符号。 然而，在下文中，为了简洁起见，我将经常使用“符号”一词，暗示术语“代码点”。
Unicode 平面。 正如您所看到的，其中大部分（平面 4 到 13）仍然未使用。
最引人注目的是，所有的主要“纸浆”都位于零平面，被称为“基本的多语言平面”。如果一行包含一种现代语言（包括中文）的文本，你不会超出这个平面。但你也不能切断 Unicode 的其余部分 - 例如，表情符号主要位于下一班飞机，”补充多语言平面“（它延伸自 0x10000 对 0x1FFFF）。 所以 UTF-16 是这样做的：所有字符都在 基本的多语言平面，用相应的两字节数字“按原样”编码。 然而，这个范围内的一些数字根本不表示特定的字符，而是表明在这对字节之后我们需要考虑另一个字节——通过将这四个字节的值组合在一起，我们得到一个涵盖的数字整个有效的 Unicode 范围。 这个想法被称为“代孕夫妇”——你可能听说过。
因此，UTF-16 每个“代码点”需要两个或（在极少数情况下）四个字节。 这比始终使用四个字节要好，但以这种方式编码的拉丁语（和其他 ASCII 字符）会在零上浪费一半的空间。 UTF-8 的设计就是为了纠正这个问题：它的 ASCII 和以前一样只占用一个字节； 代码来自 0x80 对 0x7FF - 两个字节； 从 0x800 对 0xFFFF - 三，并且从 0x10000 对 0x10FFFF - 四。 一方面，拉丁字母已经变得很好：与 ASCII 的兼容性已经恢复，并且分布更加均匀地从 1 到 4 个字节“展开”。 但遗憾的是，与 UTF-16 相比，拉丁语以外的字母表并没有任何优势，而且许多字母现在需要三个字节而不是两个字节 - 两字节记录覆盖的范围已缩小了 32 倍， 0xFFFF 对 0x7FF，其中既不包括汉语，也不包括格鲁吉亚语。 西里尔字母和其他五个字母 - hurray - lucky，每个字符 2 个字节。
为什么会出现这种情况？ 我们来看看UTF-8是如何表示字符编码的：
直接表示数字，这里使用标有符号的位 x。 可以看出，在 11 字节记录中，只有 16 个这样的位（共 21 个）。 这里的前导位仅具有辅助功能。 在四字节记录的情况下，32 位中的 24 位被分配给代码点编号 - 看起来三个字节（总共 XNUMX 位）就足够了，但服务标记消耗了太多。
这很糟糕吗？ 并不真地。 一方面，如果我们非常关心空间，我们就有可以轻松消除所有额外熵和冗余的压缩算法。 另一方面，Unicode 的目标是提供尽可能通用的编码。 例如，我们可以将用 UTF-8 编码的行委托给以前仅适用于 ASCII 的代码，而不必担心它会看到实际上不存在的 ASCII 范围中的字符（毕竟，在 UTF-8 中所有字符）从零位开始的字节 - 这正是 ASCII 的含义）。 而如果我们突然想从一个大字符串中切掉一个小尾部而不从头开始解码（或者在损坏的部分后恢复部分信息），我们很容易找到一个字符开始的偏移量（这就足够了）跳过具有位前缀的字节 10).
那么为什么要发明一些新东西呢？
同时，偶尔也会出现像deflate这样的压缩算法不太适用，但又想实现字符串的紧凑存储的情况。 就我个人而言，我在考虑构建时遇到了这个问题 包含任意语言单词的大型词典。 一方面，每个单词都很短，所以压缩它是无效的。 另一方面，我考虑的树实现被设计为存储字符串的每个字节都会生成一个单独的树顶点，因此最小化它们的数量非常有用。 在我的图书馆里 （如 ，它所基于的）类似的问题可以简单地解决 - 字符串打包到 - 字典，存储在 。 但是，很容易理解，这仅适用于有限的字母表 - 不能将中文一行添加到这样的字典中。
另外，我想指出在这样的数据结构中使用 UTF-8 时出现的另一个令人不快的细微差别。 上图显示，当一个字符被写成两个字节时，与其编号相关的位并不是连续出现的，而是由一对位分隔开 10 在中间： 110xxxxx 10xxxxxx。 因此，当字符代码中第二个字节的低 6 位溢出时（即发生转换） 10111111 → 10000000），那么第一个字节也会改变。 原来字母“p”是用字节来表示的 0xD0 0xBF，下一个“r”已经是 0xD1 0x80。 在前缀树中，这会导致父节点分裂为两个 - 一个用于前缀 0xD0，另一个为 0xD1 （尽管整个西里尔字母只能由第二个字节编码）。
我得到了什么
面对这个问题，我决定练习用位玩游戏，同时稍微熟悉一下Unicode的整体结构。 结果是 UTF-C 编码格式（“C”代表 紧凑），每个代码点花费不超过 3 个字节，并且通常只允许您花费 整个编码行多一个字节。 这导致这样一个事实：在许多非 ASCII 字母表上，这种编码结果是 比 UTF-30 紧凑 60-8%.
我以以下形式展示了编码和解码算法的实现示例 ，您可以在代码中自由使用它们。 但我还是要强调，从某种意义上来说，这种格式仍然是“自行车”，我不建议使用它 没有意识到为什么你需要它。 这仍然更像是一次实验，而不是认真的“UTF-8 改进”。 尽管如此，那里的代码写得工整、简洁，有大量的注释和测试覆盖率。
测试结果以及与UTF-8的比较
我也做了 ，在这里你可以评估算法的性能，然后我会告诉你更多关于它的原理和开发过程。
消除冗余位
当然，我以UTF-8为基础。 其中可以改变的第一个也是最明显的事情是减少每个字节中的服务位数。 例如，UTF-8 中的第一个字节始终以 0，或与 11 - 前缀 10 只有以下字节有它。 我们来替换一下前缀 11 上 1，对于接下来的字节，我们将完全删除前缀。 会发生什么？
0xxxxxxx — 1 字节
10xxxxxx xxxxxxxx - 2字节
110xxxxx xxxxxxxx xxxxxxxx - 3字节
等等，四字节记录在哪里？ 但不再需要了 - 当写入三个字节时，我们现在有 21 位可用，这对于所有数字来说已经足够了 0x10FFFF.
我们在这里牺牲了什么？ 最重要的是从缓冲区中的任意位置检测字符边界。 我们无法指向任意字节并从中找到下一个字符的开头。 这是我们格式的限制，但实际上很少有必要。 我们通常能够从一开始就遍历缓冲区（特别是当涉及到短行时）。
用 2 字节覆盖语言的情况也变得更好：现在两字节格式给出了 14 位的范围，这些代码高达 0x3FFF。 中国人很不幸（他们的性格大多是 0x4E00 对 0x9FFF），但格鲁吉亚人和许多其他民族有更多乐趣 - 他们的语言也适合每个字符 2 个字节。
进入编码器状态
现在让我们考虑一下线条本身的属性。 字典中通常包含用相同字母表的字符书写的单词，对于许多其他文本也是如此。 最好先指示该字母表一次，然后仅指示其中字母的编号。 让我们看看 Unicode 表中的字符排列是否对我们有帮助。
如上所述，Unicode 分为 飞机 每个有 65536 个代码。 但这不是一个非常有用的划分（正如已经说过的，大多数情况下我们处于零平面）。 更有趣的是除法 块。 这些范围不再具有固定长度，并且更有意义 - 通常，每个范围都组合来自同一字母表的字符。
包含孟加拉语字母表字符的块。 不幸的是，由于历史原因，这是一个包装不是很密集的示例 - 96 个字符混乱地分散在 128 个块代码点中。
块的开头及其大小始终是 16 的倍数 - 这样做只是为了方便。 此外，许多块的开始和结束值都是 128 甚至 256 的倍数 - 例如，基本的西里尔字母占用 256 个字节 0x0400 对 0x04FF。 这非常方便：如果我们保存一次前缀 0x04，那么任何西里尔字符都可以写在一个字节中。 确实，这样我们将失去返回 ASCII（以及一般的任何其他字符）的机会。 因此我们这样做：
- 两个字节
10yyyyyy yxxxxxxx不仅用数字表示符号yyyyyy yxxxxxxx，而且还要改变 当前字母表 上yyyyyy y0000000（即我们记住除了最不重要的位之外的所有位 7位); - 一字节
0xxxxxxx这是当前字母表的字符。 只需将其添加到我们在步骤 1 中记住的偏移量即可。虽然我们没有更改字母表，但偏移量为零，因此我们保持了与 ASCII 的兼容性。
同样对于需要 3 个字节的代码：
- 三个字节
110yyyyy yxxxxxxx xxxxxxxx用数字表示一个符号yyyyyy yxxxxxxx xxxxxxxx， 改变 当前字母表 上yyyyyy y0000000 00000000（除了年轻的，什么都记得 15位），然后选中我们现在所在的框 长的 模式（当将字母表更改回双字节字母表时，我们将重置此标志）； - 两个字节
0xxxxxxx xxxxxxxx在长模式下，它是当前字母表的字符。 同样，我们将其与步骤 1 中的偏移量相加。唯一的区别是现在我们读取了两个字节（因为我们切换到了这种模式）。
听起来不错：现在，虽然我们需要对同一 7 位 Unicode 范围内的字符进行编码，但我们在开头多花费了 1 个字节，每个字符总共花费了 XNUMX 个字节。
从早期版本之一开始工作。 它已经经常击败 UTF-8，但仍有改进的空间。
更糟糕的是？ 首先我们有一个条件，即 当前字母表偏移量 和复选框 长模式。 这进一步限制了我们：现在相同的字符在不同的上下文中可以进行不同的编码。 例如，搜索子字符串时必须考虑到这一点，而不仅仅是比较字节。 其次，一旦我们改变了字母表，ASCII字符的编码就变得很糟糕（这不仅是拉丁字母，而且还包括基本标点符号，包括空格）——它们需要再次将字母表更改为0，即，又是一个额外的字节（然后是另一个字节回到我们的要点）。
一个字母表好，两个字母表更好
让我们尝试稍微改变一下我们的位前缀，将一个位前缀压缩为上述三个：
0xxxxxxx — 正常模式下为 1 个字节，长模式下为 2 个字节
11xxxxxx — 1 字节
100xxxxx xxxxxxxx - 2字节
101xxxxx xxxxxxxx xxxxxxxx - 3字节
现在，在两字节记录中，少了一位可用位 - 代码点高达 0x1FFF而且不 0x3FFF。 然而，它仍然明显大于双字节 UTF-8 代码，大多数常见语言仍然适合，最明显的损失已经消失 и ，日本人很伤心。
这个新代码是什么？ 11xxxxxx？ 这是一个 64 个字符大小的小“存储”，它补充了我们的主要字母表，所以我称其为辅助（辅） 字母。 当我们切换当前字母表时，旧字母表的一部分将成为辅助字母表。 例如，我们从 ASCII 切换为西里尔文 - 存储现在包含 64 个字符，其中包含 拉丁字母、数字、空格和逗号 （非 ASCII 文本中最常见的插入）。 切换回 ASCII - 西里尔字母的主要部分将成为辅助字母。
由于可以访问两个字母表，我们可以以最小的切换字母表成本处理大量文本（标点符号通常会导致返回 ASCII，但之后我们将从附加字母表中获得许多非 ASCII 字符，而无需再次切换）。
奖励：为子字母添加前缀 11xxxxxx 并选择其初始偏移量为 0xC0，我们获得了与 CP1252 的部分兼容性。 换句话说，许多（但不是全部）以 CP1252 编码的西欧文本在 UTF-C 中看起来是一样的。
然而，这里出现了一个难题：如何从主字母中获得辅助字母？ 您可以保留相同的偏移量，但是 - 唉 - 这里 Unicode 结构已经在与我们作对了。 很多时候，字母表的主要部分不在块的开头（例如，俄语大写字母“A”的代码是 0x0410，尽管西里尔字母块开头为 0x0400）。 因此，将前 64 个字符放入存储中后，我们可能无法访问字母表的尾部。
为了解决这个问题，我手动检查了一些与不同语言相对应的块，并为它们指定了辅助字母在主字母中的偏移量。 作为一个例外，拉丁字母通常会像 base64 一样重新排序。
最后的润色
最后让我们想想还有哪些地方可以改进。
注意格式 101xxxxx xxxxxxxx xxxxxxxx 允许您对数字进行编码最多 0x1FFFFF，并且 Unicode 结束得更早，位于 0x10FFFF。 换句话说，最后一个代码点将表示为 10110000 11111111 11111111。 因此，我们可以说，如果第一个字节的形式为 1011xxxx （其中 xxxx 大于0），那么它就意味着别的东西。 例如，您可以在那里添加另外 15 个字符，这些字符始终可用于以一个字节进行编码，但我决定采用不同的方式。
现在让我们看看那些需要三个字节的 Unicode 块。 基本上，正如已经提到的，这些都是汉字 - 但很难用它们做任何事情，它们有 21 个。 但平假名和片假名也飞到了那里——而且数量不再那么多了，不到两百个。 而且，自从我们记住了日语以来，还有表情符号（事实上，它们分散在 Unicode 中的许多地方，但主要块在范围内 0x1F300 – 0x1FBFF）。 如果你想一想，现在有一些表情符号是由多个代码点同时组合而成的（例如，表情符号 由多达 7 个代码组成！），那么在每个代码上花费 7 个字节就变得完全是一种耻辱（为了一个图标，3×21 = XNUMX 个字节，一场噩梦）。
因此，我们选择几个与表情符号、平假名和片假名相对应的选定范围，将它们重新编号为一个连续列表，并将它们编码为两个字节而不是三个字节：
1011xxxx xxxxxxxx
太棒了：前面提到的表情符号，由 7 个代码点组成，在 UTF-8 中占用 25 个字节，我们将其放入 14 （每个代码点正好两个字节）。 顺便说一句，哈布尔拒绝消化它（无论是在旧编辑器中还是在新编辑器中），所以我不得不将其与图片一起插入。
让我们尝试解决另一个问题。 我们记得，基本字母表本质上是 高6位，我们牢记这一点并将其粘贴到每个下一个解码符号的代码上。 对于块内有汉字的情况 0x4E00 – 0x9FFF，这要么是位 0，要么是位 1。这不是很方便：我们需要不断地在这两个值之间切换字母表（即花费三个字节）。 但请注意，在长模式下，我们可以从代码本身中减去使用短模式编码的字符数（经过上述所有技巧后，这是 10240） - 然后象形文字的范围将转移到 0x2600 – 0x77FF，在这种情况下，在整个范围内，最高有效的 6 位（21 位中）将等于 0。因此，象形文字序列将每个象形文字使用两个字节（这对于如此大的范围来说是最佳的），而无需导致字母切换。
替代解决方案：SCSU、BOCU-1
刚刚读完文章标题的 Unicode 专家很可能会赶紧提醒您，在 Unicode 标准中直接有 （SCSU），它描述了一种与文章中描述的非常相似的编码方法。
我诚实地承认：我是在深深地埋头写下我的决定之后才知道它的存在的。 如果我从一开始就知道这一点，我可能会尝试编写一个实现，而不是提出自己的方法。
有趣的是，SCSU 使用的想法与我自己提出的想法非常相似（他们使用“窗口”而不是“字母表”的概念，而且可用的窗口数量比我多）。 同时，这种格式也有缺点：它比编码算法更接近压缩算法。 特别是，该标准给出了许多表示方法，但没有说明如何选择最佳的表示方法 - 为此，编码器必须使用某种启发式方法。 因此，产生良好封装的 SCSU 编码器将比我的算法更复杂、更麻烦。
为了进行比较，我将 SCSU 的一个相对简单的实现转移到 JavaScript - 就代码量而言，它与我的 UTF-C 相当，但在某些情况下，结果差了百分之几十（有时可能会超过它，但是不是很多）。 例如，希伯来语和希腊语的文本采用 UTF-C 编码 比 SCSU 好 60% （可能是由于它们的字母表紧凑）。
另外，我要补充一点，除了 SCSU 之外，还有另一种紧凑表示 Unicode 的方法 - ，但它的目标是 MIME 兼容性（我不需要），并采用稍微不同的编码方法。 我没有评估过它的有效性，但在我看来，它不太可能比 SCSU 更高。
可能的改进
我提出的算法在设计上并不是通用的（这可能是我的目标与 Unicode 联盟的目标最大分歧的地方）。 我已经提到过，它主要是为了一项任务（在前缀树中存储多语言词典）而开发的，并且它的某些功能可能不太适合其他任务。 但它不是标准这一事实可能是一个优点 - 您可以轻松修改它以满足您的需求.
例如，以明显的方式，您可以摆脱状态的存在，进行无状态编码 - 只是不更新变量 offs, auxOffs и is21Bit 在编码器和解码器中。 在这种情况下，不可能有效地打包相同字母表的字符序列，但可以保证相同的字符始终使用相同的字节进行编码，而不管上下文如何。
此外，您可以通过更改默认状态将编码器定制为特定语言 - 例如，专注于俄语文本，在开始时设置编码器和解码器 offs = 0x0400 и auxOffs = 0。 这在无状态模式的情况下尤其有意义。 一般来说，这与使用旧的八位编码类似，但不会删除根据需要插入所有 Unicode 字符的功能。
前面提到的另一个缺点是，在以 UTF-C 编码的大文本中，没有快速方法可以找到最接近任意字节的字符边界。 如果您从编码缓冲区中截断最后（例如 100 个字节），您可能会面临收到无法处理的垃圾的风险。 该编码不是为存储多千兆字节的日志而设计的，但通常可以纠正。 字节 0xBF 绝不能作为第一个字节出现（但可以是第二个或第三个字节）。 因此，在编码时，可以插入序列 0xBF 0xBF 0xBF 例如，每 10 KB - 那么，如果您需要找到边界，则扫描所选片段就足够了，直到找到类似的标记。 继最后一个 0xBF 保证是一个字符的开始。 （解码时，这三个字节的序列当然需要被忽略。）
总结
如果您已经读到这里，那么恭喜您！ 我希望您像我一样，学到一些关于 Unicode 结构的新知识（或刷新您的记忆）。
演示页面。 希伯来语的示例显示了相对于 UTF-8 和 SCSU 的优势。
上述研究不应被视为对标准的侵犯。 不过，我对自己的工作成果总体还是满意的，所以我对他们感到满意 ：例如，一个缩小的 JS 库仅重 1710 字节（当然，没有依赖项）。 正如我上面提到的，她的作品可以在 （还有一组文本可以与 UTF-8 和 SCSU 进行比较）。
最后，再次提醒大家注意使用UTF-C的情况 不值得:
- 如果你的行足够长（100-200 个字符）。 在这种情况下，您应该考虑使用像 deflate 这样的压缩算法。
- 如果你需要 ASCII 透明度，也就是说，编码序列不包含原始字符串中不存在的 ASCII 代码对您来说很重要。 如果在与第三方 API 交互（例如，使用数据库）时，将编码结果作为抽象字节集而不是字符串传递，则可以避免这种需要。 否则，您可能会面临意外漏洞的风险。
- 如果您希望能够快速找到任意偏移处的字符边界（例如，当行的一部分损坏时）。 这是可以完成的，但只能通过从头开始扫描该行（或应用上一节中描述的修改）。
- 如果您需要快速对字符串内容执行操作（对它们进行排序、搜索其中的子字符串、连接）。 这需要首先对字符串进行解码，因此在这些情况下 UTF-C 将比 UTF-8 慢（但比压缩算法快）。 由于相同的字符串总是以相同的方式编码，因此不需要解码的精确比较，并且可以逐字节地进行。
更新： 用户 发布了一张图表，强调了 UTF-C 的适用性限制。 它表明，只要打包的字符串较短，UTF-C 就比通用压缩算法（LZW 的变体）更有效 约 140 个字符 （但是，我注意到比较是在一种文本上进行的；对于其他语言，结果可能有所不同）。
来源： habr.com
