编程语言中的UTF-8字符串引策略

现在越来越多的语言都内在支持Unicode编码了。但是对其内部表示机制可能略有差异。如何在内存中表示或编码这些字符串的需要权衡取舍，要考虑的一个问题是字符串通常具有对其编码点的随机访问索引，其时间复杂度类似于恒定时间O（1）。但是，并非所有字符串表示都能支持。当使用可变长度编码的字符串（例如UTF-8或UTF-16）时具有O(n)时间复杂度。实现O(1)时间复杂度的最简单选择就是使用一个32位数组，例如在UCS-4的UTF32编码，但是由于UTF32中绝大多数位置都是空置，使用该编码会导致内存的使用非常低效，非常不合算。

一般来说，大多数编程语言编码中都会选用比较均衡的UTF-8编码。在本文中，虫虫将来大家说说Unicode编码，以及实例讨论UTF-8在Emacs Lisp，Julia和Golang语言的编码和索引策略。

Unicode和编码空间

虫虫以前文章中，我们提到了为了表示世界上上使用的各种语言和符号，开发了一个通用的编码体系Unicode。刚开始Unicode 编码是16位设计，可以表达65536个字符，后来发现该设计空间有限不能表示所有的符号，比如古汉语中的字和一些很少使用的汉字。所以Unicode 编码扩展到了 21 位（从 U+0000 到 U+10FFFF）。

Unicode 中基本的元素叫编码点（Code Point）。编码点通过16进制数字来编码加上"U+"前缀来表示。比如，U+0041 表示"A"、 U+866B表示 "虫"。Unicode中所有的编码点构成编码空间（Code Space）。Unicode 位编码空间由0~16个平面组成，每个平面有65536个编码点，总共有1114112 个编码点。

这么多编码点中只有大概三个平面位的128237 编码点被使用 ，还有137468 字符作为保留空间，可以个人用户自定用。

Unicode编码空间的图示如下：

其中：白色表示未用空间，蓝色表示已用空间，绿色表示保留空间，小的红色区域是代理区（surrogates）用于实现Unicode的扩容转化。

第一平面位叫做基本多语言面板（Basic Multilingual Plane，简称 BMP）。BMP包含现代基本所有文本字符，各国语言等。该平面就是最初16位Unicode设计所占用的空间。

UTF8和UTF16

我们前面说过基于1对1的UTF-32编码低效浪费空间。据有关研究统计Unidoce字符的使用频率如下图：

频率大小由高到低的顺序为：黑（没出现）、红、黄、白。

根据使用频率图可以得出：绝大多数文本都位于BMP平面，有些零散的使用来自二和三个面板。第二个面板下高频率使用的字符为emoji表情。

由于使用频度有差异，为了避免不用的unicode编码占据多余的内存和空间，unicode通常使用紧凑型的可变编码 。最常见的是UTF-8和UTF-16。。

UTF8

在 UTF-8 中，每个编码点依据下标的整数值被存储为1~4个字节。

UTF-8 使用二进制前缀，字符的最高位的几个比特标志该字符是单个字节，多字节序列的开始或者中间字节，剩余的比特连接起来表示编码点的下标：

0000 0000-0000 007F | 0xxxxxxx U+0080–U+07FF

0000 0080-0000 07FF | 110xxxxx 10xxxxxx U+0080–U+07FF

0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx U+0800–U+FFFF

0001 0000-0010 FFFF| 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx U+10000–U+10FFFF

UTF8优点：

对于很常见的拉丁字符，采用该编码不用额外的空间。

UTF-8 是基于8 位的码元，无需关心字节顺序。

任何已经是 ASCII 编码的字符串和文件无需转换就可以被 UTF-8 识别。

编程中常用的符号，比如 NULL 结尾，分隔符（n,t,',',")等UTF-8 中也是可用的。

总结：UTF-8 是存储和交流 Unicode 文本方面的最好和最常用编码。UTF-8目前是通用文件格式、网络协议以及 Web API编码标准。

UTF16

和 UTF-8 一样，也用二进制前缀的形式表示 UTF-16 的编码规则：

上面我们介绍了Unicode编码以其编码空间，介绍了UTF8和UTF16两种常用Unicode的编码实现，下面我们实例介绍下在编程语言中UTF-8编码是如何具体实现的：

Emacs Lisp

Emacs Lisp有两种不同类型的字符串：unibyte和multibyte，通常可以互换。

Emacs Lisp在内部通过UTF-8编码表示"多字节"字符串和缓冲区。为了完全支持正在编辑的文件中的字节序列，Emacs使用其自己的Unicode扩展来精确且明确地表示与文本混合的原始字节。任意字节序列都可以解码为Emacs的内部表示，然后无损地重新编码回完全相同的字节序列。

Unibyte字符串和缓冲区实际上只是字节字符串。在实践中，它们基本上是ISO/ IEC 8859-1，a.k.a. Latin-1。它是一个Unicode字符串，其中所有代码点在256以内。Emacs会尽最大可能用最小和最简单的字符串表示（类似于CPython 3.3+）。

Emacs Lisp中字符串是可变的，其中诀窍是，只要你插入的字符代码点高于255，Emacs就会自动将其转换为多字节。

对unibyte字符串进行o(1) 恒定时间索引很简单，当索引到unibyte字符串时，Emacs做了很明显的事情，保证Emacs中的大多数字符串都是unibyte，即使用户不使用英语也是如此。

大多数缓冲区都是多字节的，即使这些缓冲区通常只是ASCII。由于Emacs使用间隙缓冲区，因此通常无关紧要。几乎所有访问都紧密地聚集在该点周围，因此O(n)索引通常也没关系。

对于多字节字符串。考虑这些习惯用于迭代Emacs Lisp中的字符串：

后者扩展与前者基本相同：使用aref索引到该代码点的递增索引。那么迭代多字节字符串，是一个O（n^2）的操作？

事实上，在这种情况下，该操作基本上与迭代unibyte字符串一样高效。在讨论为什么之前，请考虑这个小难题。这是一个小字符串比较函数，它一次比较两个字符串代码点，返回它们的第一个区别：

让我们用一些长字符串（100,000个代码点）来基准测试：

使用两个零的unibyte字符串需要13ms。如果将其中一个中的最后一个代码点更改为256，将其转换为多字节字符串呢：

还是大概相同的运行时间，因此多字节字符串不是逐节迭代的。

我们来对比下如果两个都是多字节字符的情况呢：

大概需要2.3秒：运行时间大概是之前的2000倍！同时迭代两个多字节字符串似乎破坏了内置的优化。为什么这样呢？

为避免通常多字节索引操作的O(n)时间成本，Emacs为多字节字符串最后一次索引位置内部设置了一个书签。如果再次访问该位置附近，则可以从该书签开始向前或向后查看。与间隙缓冲区一样，这为集群访问提供了很大的优势，其中包括迭代。

但是，内置的字符书签是全局性的，每个Emacs实例共用一个，而不是对每个字符串的设置。因此在后一个基准测试中，两个多字节字符串不断争夺单个字符串书签，导致比较函数中的索引为O（n^2）时间复杂度。

因此，Emacs是假设它是可以持续UTF-8文本数据，但它是通过一些简单的优化来伪装它。这通常很好。

Julia

另一种方法是不会假设，在界面中明确限制了UTF-8。Julia语言是采取了这种方法。虽然这并不是一个糟糕的选择，但考虑到Julia的目标受众（即Matlab用户），可能这样有点不合时宜。

Julia字符串是包含有效UTF-8数据的显式字节字符。所有索引都是在字节上，所以是恒定的O(1)时间，并始终从索引字节开始的多字节代码点解码。如果索引到非开始代码点的字节时候就会报错。

切片可以超过字节，但它们"向上舍入"到当前代码点的末尾：

迭代字符串需要辅助函数，这些函数保留内部"书签"，所以每次访问都是恒定时间o(1)：

Golang

Go与Julia非常相似，但对字符串的表达更为明确。所有字符串都是字节字符串，其内容没有限制。通常，字符串包含UTF-8编码的文本，但对此没有严格要求。Golang提供了一个unicode/utf8包用于处理包含UTF-8数据的字符串。

除了约定之外，range子句还假定字符串包含UTF-8数据，如果不包含，也不会报错。不包含有效UTF-8数据的字节为被显示为REPLACEMENT CHARACTER（U+FFFD）。

有利于UTF-8的另一种语言是将字符串转换为[]rune，将字符串解码为代码点，比如UCS-4，再次使用REPLACEMENT CHARACTER：

和Julia一样，没有假设，程序员要注意明确指明UTF-8编码。

总结

本文介绍了现代Unicode编码和UTF8、UTF16编码规则，并通过三种语言Emacs Lisp、Golang和Julia语言为实例介绍了编程语言中UTF-8字符的具体实现和字符索引策略。