编程语言中的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字符的具体实现和字符索引策略。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20190726A0FHF500?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券