如果您是開發人員並且面臨選擇編碼的任務，那麼 Unicode 幾乎總是正確的解決方案。 具體的表示方法取決於上下文，但大多數情況下這裡也有一個通用答案 - UTF-8。 它的好處是它允許你使用所有 Unicode 字元而無需花費 太多了 大多數情況下有很多位元組。 確實，對於不僅僅使用拉丁字母的語言，“不要太多”至少是 每個字元兩個位元組。 我們能否做得更好，而不回到將我們限制為只有 256 個可用字符的史前編碼？
下面我建議您熟悉我回答這個問題的嘗試，並實作一個相對簡單的演算法，該演算法允許您儲存世界上大多數語言的行，而無需添加 UTF-8 中的冗餘。
免責聲明。 我將立即做出一些重要的保留： 所描述的解決方案不作為 UTF-8 的通用替代品提供，它只適用於一小部分情況（下面會詳細介紹），並且在任何情況下都不應該使用它與第三方 API（他們甚至不知道）進行交互。 大多數情況下，通用壓縮演算法（例如 deflate）適用於大量文字資料的緊湊儲存。 此外，在創建我的解決方案的過程中，我發現了Unicode 本身的現有標準，它解決了相同的問題- 它有點複雜（而且通常更糟），但它仍然是一個公認的標準，而不僅只是把一起放在膝蓋上。 我也會告訴你關於他的事。
關於 Unicode 和 UTF-8
首先，簡單介紹一下它是什麼 Unicode的 и 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”代表 Compact single），每個代碼點花費不超過 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 個字符 （但是，我注意到比較是在一種文本上進行的；對於其他語言，結果可能有所不同）。
來源： www.habr.com