Nếu bạn là nhà phát triển và bạn phải đối mặt với nhiệm vụ chọn bảng mã, thì Unicode hầu như sẽ luôn là giải pháp phù hợp. Phương pháp biểu diễn cụ thể phụ thuộc vào ngữ cảnh, nhưng hầu hết thường có một câu trả lời chung ở đây - UTF-8. Điểm hay của nó là nó cho phép bạn sử dụng tất cả các ký tự Unicode mà không tốn nhiều chi phí. quá nhiều rất nhiều byte trong hầu hết các trường hợp. Đúng, đối với những ngôn ngữ không chỉ sử dụng bảng chữ cái Latinh, ít nhất “không quá nhiều” là hai byte cho mỗi ký tự. Chúng ta có thể làm tốt hơn mà không quay lại bảng mã thời tiền sử vốn giới hạn chúng ta chỉ ở 256 ký tự có sẵn không?
Dưới đây tôi khuyên bạn nên tự làm quen với nỗ lực trả lời câu hỏi này và triển khai một thuật toán tương đối đơn giản cho phép bạn lưu trữ các dòng bằng hầu hết các ngôn ngữ trên thế giới mà không cần thêm phần dư thừa có trong UTF-8.
Tuyên bố từ chối trách nhiệm. Tôi sẽ ngay lập tức thực hiện một số đặt phòng quan trọng: giải pháp được mô tả không được cung cấp dưới dạng giải pháp thay thế chung cho UTF-8, nó chỉ phù hợp trong một danh sách hẹp các trường hợp (xem thêm ở bên dưới) và trong mọi trường hợp không nên sử dụng nó để tương tác với API của bên thứ ba (những người thậm chí không biết về nó). Thông thường, các thuật toán nén có mục đích chung (ví dụ: giảm phát) phù hợp để lưu trữ nhỏ gọn khối lượng lớn dữ liệu văn bản. Ngoài ra, trong quá trình tạo giải pháp của mình, tôi đã tìm thấy một tiêu chuẩn hiện có trong chính Unicode, tiêu chuẩn này giải quyết được vấn đề tương tự - nó phức tạp hơn một chút (và thường tệ hơn), nhưng nó vẫn là một tiêu chuẩn được chấp nhận và không chỉ đặt cùng nhau trên đầu gối. Tôi cũng sẽ kể cho bạn nghe về anh ấy.
Giới thiệu về Unicode và UTF-8
Để bắt đầu, một vài lời về nó là gì Unicode и UTF-8.
Như bạn đã biết, mã hóa 8 bit từng rất phổ biến. Với họ, mọi thứ thật đơn giản: 256 ký tự có thể được đánh số từ 0 đến 255 và các số từ 0 đến 255 rõ ràng có thể được biểu diễn dưới dạng một byte. Nếu chúng ta quay lại từ đầu, mã hóa ASCII hoàn toàn bị giới hạn ở 7 bit, do đó bit quan trọng nhất trong biểu diễn byte của nó bằng 8 và hầu hết các mã hóa XNUMX bit đều tương thích với nó (chúng chỉ khác nhau ở phần “trên” phần, trong đó bit quan trọng nhất là một ).
Unicode khác với các bảng mã đó như thế nào và tại sao lại có nhiều cách biểu diễn cụ thể liên quan đến nó - UTF-8, UTF-16 (BE và LE), UTF-32? Hãy sắp xếp nó theo thứ tự.
Tiêu chuẩn Unicode cơ bản chỉ mô tả sự tương ứng giữa các ký tự (và trong một số trường hợp, các thành phần riêng lẻ của ký tự) và số của chúng. Và có rất nhiều con số có thể có trong tiêu chuẩn này - từ 0x00 để 0x10FFFF (1 miếng). Nếu chúng ta muốn đặt một số trong một phạm vi như vậy vào một biến thì cả 114 và 112 byte đều không đủ đối với chúng ta. Và vì bộ xử lý của chúng tôi không được thiết kế phù hợp để làm việc với các số có 1 byte nên chúng tôi buộc phải sử dụng tối đa 2 byte cho mỗi ký tự! Đây là UTF-4, nhưng chính vì sự “lãng phí” này mà định dạng này không được ưa chuộng.
May mắn thay, thứ tự các ký tự trong Unicode không phải là ngẫu nhiên. Toàn bộ bộ của họ được chia thành 17 "máy bay", mỗi cái chứa 65536 (0x10000) «điểm mã" Khái niệm “điểm mã” ở đây chỉ đơn giản là số ký tự, được gán cho nó bằng Unicode. Tuy nhiên, như đã đề cập ở trên, trong Unicode không chỉ các ký tự riêng lẻ được đánh số mà còn cả các thành phần và nhãn hiệu dịch vụ của chúng (và đôi khi không có gì tương ứng với số đó - có lẽ là ở thời điểm hiện tại, nhưng đối với chúng tôi điều này không quá quan trọng), vì vậy thì đúng hơn là hãy luôn nói cụ thể về số lượng các con số chứ không phải các ký hiệu. Tuy nhiên, sau đây để cho ngắn gọn, tôi sẽ thường dùng từ “ký hiệu”, ngụ ý thuật ngữ “điểm mã”.
Mặt phẳng Unicode. Như bạn có thể thấy, hầu hết trong số đó (mặt phẳng 4 đến 13) vẫn chưa được sử dụng.
Điều đáng chú ý nhất là toàn bộ “bột giấy” chính đều nằm trong mặt phẳng số XNUMX nên gọi là "Mặt phẳng đa ngôn ngữ cơ bản". Nếu một dòng chứa văn bản bằng một trong các ngôn ngữ hiện đại (bao gồm cả tiếng Trung Quốc), bạn sẽ không vượt ra ngoài mặt phẳng này. Nhưng bạn cũng không thể cắt bỏ phần còn lại của Unicode - ví dụ: biểu tượng cảm xúc chủ yếu nằm ở cuối máy bay tiếp theo"Mặt phẳng đa ngôn ngữ bổ sung"(nó kéo dài từ 0x10000 để 0x1FFFF). Vì vậy, UTF-16 thực hiện điều này: tất cả các ký tự nằm trong Mặt phẳng đa ngôn ngữ cơ bản, được mã hóa “nguyên trạng” với số hai byte tương ứng. Tuy nhiên, một số số trong phạm vi này hoàn toàn không biểu thị các ký tự cụ thể mà chỉ ra rằng sau cặp byte này, chúng ta cần xem xét một số khác - bằng cách kết hợp các giá trị của bốn byte này với nhau, chúng ta sẽ có được một số bao gồm toàn bộ phạm vi Unicode hợp lệ. Ý tưởng này được gọi là “cặp đôi thay thế” - bạn có thể đã nghe nói về họ.
Vì vậy, UTF-16 yêu cầu hai hoặc (trong những trường hợp rất hiếm) bốn byte cho mỗi "điểm mã". Điều này tốt hơn so với việc sử dụng bốn byte mọi lúc, nhưng tiếng Latin (và các ký tự ASCII khác) khi được mã hóa theo cách này sẽ lãng phí một nửa không gian trên các số 8. UTF-XNUMX được thiết kế để sửa lỗi này: ASCII trong đó, như trước đây, chỉ chiếm một byte; mã từ 0x80 để 0x7FF - hai byte; từ 0x800 để 0xFFFF - ba, và từ 0x10000 để 0x10FFFF - bốn. Một mặt, bảng chữ cái Latinh đã trở nên tốt: khả năng tương thích với ASCII đã trở lại và sự phân bổ được “trải ra” đồng đều hơn từ 1 đến 4 byte. Tuy nhiên, than ôi, các bảng chữ cái không phải tiếng Latinh không được hưởng lợi gì so với UTF-16 và nhiều bảng chữ cái hiện yêu cầu ba byte thay vì hai - phạm vi được bao phủ bởi bản ghi hai byte đã thu hẹp 32 lần, với 0xFFFF để 0x7FF, và cả tiếng Trung lẫn tiếng Georgia đều không được đưa vào đó. Cyrillic và năm bảng chữ cái khác - hoan hô - may mắn, 2 byte cho mỗi ký tự.
Lý do tại sao điều này xảy ra? Hãy xem UTF-8 thể hiện mã ký tự như thế nào:
Trực tiếp để biểu diễn các con số, các bit được đánh dấu bằng ký hiệu được sử dụng ở đây x. Có thể thấy rằng trong một bản ghi hai byte chỉ có 11 bit như vậy (trong tổng số 16). Các bit dẫn đầu ở đây chỉ có chức năng phụ trợ. Trong trường hợp bản ghi bốn byte, 21 trong số 32 bit được phân bổ cho số điểm mã - có vẻ như ba byte (cung cấp tổng cộng 24 bit) là đủ, nhưng các điểm đánh dấu dịch vụ đã ngốn quá nhiều.
Điều này có tệ không? Không thực sự. Một mặt, nếu chúng ta quan tâm nhiều đến không gian, chúng ta có các thuật toán nén có thể dễ dàng loại bỏ tất cả entropy và dư thừa thừa. Mặt khác, mục tiêu của Unicode là cung cấp cách mã hóa phổ quát nhất có thể. Ví dụ: chúng ta có thể ủy thác một dòng được mã hóa bằng UTF-8 cho mã mà trước đây chỉ hoạt động với ASCII và không sợ rằng nó sẽ nhìn thấy một ký tự trong phạm vi ASCII mà thực tế không có ở đó (xét cho cùng, trong UTF-8 tất cả byte bắt đầu từ bit XNUMX - đây chính xác là ASCII). Và nếu chúng ta đột nhiên muốn cắt một phần đuôi nhỏ khỏi một chuỗi lớn mà không giải mã nó ngay từ đầu (hoặc khôi phục một phần thông tin sau một phần bị hỏng), chúng ta dễ dàng tìm thấy phần bù nơi một ký tự bắt đầu (thế là đủ). để bỏ qua các byte có tiền tố bit 10).
Tại sao sau đó lại phát minh ra một cái gì đó mới?
Đồng thời, đôi khi có những tình huống khi các thuật toán nén như giảm phát khó áp dụng được, nhưng bạn muốn đạt được khả năng lưu trữ chuỗi nhỏ gọn. Cá nhân tôi gặp phải vấn đề này khi nghĩ đến việc xây dựng cho một từ điển lớn bao gồm các từ trong các ngôn ngữ tùy ý. Một mặt, mỗi từ rất ngắn nên việc nén nó sẽ không hiệu quả. Mặt khác, việc triển khai cây mà tôi đang xem xét được thiết kế sao cho mỗi byte của chuỗi được lưu trữ tạo ra một đỉnh cây riêng biệt, do đó việc giảm thiểu số lượng của chúng là rất hữu ích. Trong thư viện của tôi (Như trong , dựa trên đó) một vấn đề tương tự có thể được giải quyết một cách đơn giản - các chuỗi được gói thành -từ điển, được lưu trữ ở đó trong . Tuy nhiên, để dễ hiểu, điều này chỉ hiệu quả với một bảng chữ cái hạn chế - không thể thêm một dòng tiếng Trung vào từ điển như vậy.
Riêng biệt, tôi muốn lưu ý thêm một sắc thái khó chịu khác phát sinh khi sử dụng UTF-8 trong cấu trúc dữ liệu như vậy. Hình trên cho thấy khi một ký tự được viết dưới dạng hai byte, các bit liên quan đến số của nó không xếp thành một hàng mà được phân tách bằng một cặp bit. 10 ở giữa: 110xxxxx 10xxxxxx. Bởi vì điều này, khi 6 bit thấp hơn của byte thứ hai tràn vào mã ký tự (tức là xảy ra quá trình chuyển đổi 10111111 → 10000000), thì byte đầu tiên cũng thay đổi. Hóa ra chữ “p” được ký hiệu là byte 0xD0 0xBF, và chữ “r” tiếp theo đã là 0xD1 0x80. Trong cây tiền tố, điều này dẫn đến việc chia nút cha thành hai - một cho tiền tố 0xD0, và một cái khác cho 0xD1 (mặc dù toàn bộ bảng chữ cái Cyrillic chỉ có thể được mã hóa bằng byte thứ hai).
Tôi đã nhận được gì
Đối mặt với vấn đề này, tôi quyết định thực hành chơi trò chơi với bit, đồng thời làm quen tốt hơn một chút với cấu trúc của Unicode nói chung. Kết quả là định dạng mã hóa UTF-C ("C" cho nhỏ gọn), chi tiêu không quá 3 byte cho mỗi điểm mã và thường chỉ cho phép bạn chi tiêu thêm một byte cho toàn bộ dòng được mã hóa. Điều này dẫn đến thực tế là trên nhiều bảng chữ cái không phải ASCII việc mã hóa như vậy hóa ra là Nhỏ gọn hơn 30-60% so với UTF-8.
Tôi đã trình bày các ví dụ thực hiện thuật toán mã hóa và giải mã dưới dạng , bạn có thể tự do sử dụng chúng trong mã của mình. Nhưng tôi vẫn sẽ nhấn mạnh rằng ở một khía cạnh nào đó, định dạng này vẫn là một “chiếc xe đạp” và tôi không khuyên bạn nên sử dụng nó mà không nhận ra tại sao bạn cần nó. Đây vẫn là một thử nghiệm hơn là một "sự cải tiến nghiêm túc của UTF-8". Tuy nhiên, mã ở đó được viết gọn gàng, chính xác, với số lượng lớn nhận xét và phạm vi kiểm tra.
Kết quả kiểm tra và so sánh với UTF-8
tôi cũng đã làm , nơi bạn có thể đánh giá hiệu suất của thuật toán và sau đó tôi sẽ cho bạn biết thêm về các nguyên tắc và quá trình phát triển của nó.
Loại bỏ các bit dư thừa
Tất nhiên, tôi lấy UTF-8 làm cơ sở. Điều đầu tiên và rõ ràng nhất có thể thay đổi trong đó là giảm số lượng bit dịch vụ trong mỗi byte. Ví dụ: byte đầu tiên trong UTF-8 luôn bắt đầu bằng một trong hai 0, Hoặc với 11 - tiền tố 10 Chỉ các byte sau có nó. Hãy thay thế tiền tố 11 trên 1và đối với các byte tiếp theo, chúng tôi sẽ loại bỏ hoàn toàn các tiền tố. Chuyện gì sẽ xảy ra?
0xxxxxxx - 1 byte
10xxxxxx xxxxxxxx - 2 byte
110xxxxx xxxxxxxx xxxxxxxx - 3 byte
Đợi đã, bản ghi bốn byte ở đâu? Nhưng nó không còn cần thiết nữa - khi ghi bằng ba byte, hiện tại chúng ta có sẵn 21 bit và điều này là đủ cho tất cả các số lên đến 0x10FFFF.
Chúng ta đã hy sinh điều gì ở đây? Điều quan trọng nhất là việc phát hiện ranh giới ký tự từ một vị trí tùy ý trong bộ đệm. Chúng ta không thể trỏ vào một byte tùy ý và tìm phần đầu của ký tự tiếp theo từ nó. Đây là một hạn chế trong định dạng của chúng tôi, nhưng trong thực tế điều này hiếm khi cần thiết. Chúng ta thường có thể chạy qua bộ đệm ngay từ đầu (đặc biệt khi nói đến các dòng ngắn).
Tình hình bao phủ các ngôn ngữ có 2 byte cũng trở nên tốt hơn: giờ đây định dạng hai byte cung cấp phạm vi 14 bit và đây là những mã lên tới 0x3FFF. Người Trung Quốc không may mắn (tính cách của họ chủ yếu từ 0x4E00 để 0x9FFF), nhưng người Georgia và nhiều dân tộc khác còn thú vị hơn - ngôn ngữ của họ cũng có kích thước 2 byte cho mỗi ký tự.
Nhập trạng thái bộ mã hóa
Bây giờ chúng ta hãy nghĩ về các thuộc tính của chính các đường đó. Từ điển thường chứa các từ được viết bằng các ký tự của cùng một bảng chữ cái và điều này cũng đúng với nhiều văn bản khác. Sẽ tốt hơn nếu chỉ ra bảng chữ cái này một lần và sau đó chỉ cho biết số lượng chữ cái bên trong nó. Hãy xem việc sắp xếp các ký tự trong bảng Unicode có giúp ích gì cho chúng ta không.
Như đã đề cập ở trên, Unicode được chia thành chiếc máy bay Mỗi mã 65536. Nhưng đây không phải là phép chia hữu ích lắm (như đã nói, hầu hết chúng ta thường ở trong mặt phẳng số XNUMX). Thú vị hơn là việc chia cho các khối. Các phạm vi này không còn có độ dài cố định và có ý nghĩa hơn - theo quy luật, mỗi phạm vi kết hợp các ký tự từ cùng một bảng chữ cái.
Một khối chứa các ký tự của bảng chữ cái Bengali. Thật không may, vì lý do lịch sử, đây là một ví dụ về cách đóng gói không quá dày đặc - 96 ký tự nằm rải rác một cách hỗn loạn trên 128 điểm mã khối.
Phần đầu của các khối và kích thước của chúng luôn là bội số của 16 - điều này được thực hiện đơn giản để thuận tiện. Ngoài ra, nhiều khối bắt đầu và kết thúc trên các giá trị là bội số của 128 hoặc thậm chí 256 - ví dụ: bảng chữ cái Cyrillic cơ bản chiếm 256 byte từ 0x0400 để 0x04FF. Điều này khá thuận tiện: nếu chúng ta lưu tiền tố một lần 0x04, thì bất kỳ ký tự Cyrillic nào cũng có thể được viết bằng một byte. Đúng, theo cách này, chúng ta sẽ mất cơ hội quay lại ASCII (và bất kỳ ký tự nào khác nói chung). Vì vậy chúng tôi làm điều này:
- Hai byte
10yyyyyy yxxxxxxxkhông chỉ biểu thị một biểu tượng bằng một con sốyyyyyy yxxxxxxx, nhưng cũng thay đổi bảng chữ cái hiện tại trênyyyyyy y0000000(tức là chúng ta nhớ tất cả các bit ngoại trừ những bit ít quan trọng nhất 7 bit); - Một byte
0xxxxxxxđây là ký tự của bảng chữ cái hiện tại. Nó chỉ cần được thêm vào phần bù mà chúng tôi đã nhớ ở bước 1. Mặc dù chúng tôi không thay đổi bảng chữ cái nhưng phần bù bằng XNUMX, vì vậy chúng tôi vẫn duy trì khả năng tương thích với ASCII.
Tương tự như vậy đối với các mã yêu cầu 3 byte:
- Ba byte
110yyyyy yxxxxxxx xxxxxxxxchỉ ra một biểu tượng với một sốyyyyyy yxxxxxxx xxxxxxxx, thay đổi bảng chữ cái hiện tại trênyyyyyy y0000000 00000000(nhớ tất cả mọi thứ ngoại trừ những người trẻ hơn 15 bit) và chọn hộp mà chúng ta hiện đang ở dài chế độ (khi thay đổi bảng chữ cái về dạng byte kép, chúng tôi sẽ đặt lại cờ này); - Hai byte
0xxxxxxx xxxxxxxxở chế độ dài, đó là ký tự của bảng chữ cái hiện tại. Tương tự, chúng tôi thêm nó với phần bù từ bước 1. Điểm khác biệt duy nhất là bây giờ chúng tôi đọc hai byte (vì chúng tôi đã chuyển sang chế độ này).
Nghe có vẻ hay: bây giờ, trong khi chúng tôi cần mã hóa các ký tự trong cùng một phạm vi Unicode 7 bit, chúng tôi dành thêm 1 byte ở đầu và tổng cộng một byte cho mỗi ký tự.
Làm việc từ một trong những phiên bản trước đó. Nó thường đánh bại UTF-8 nhưng vẫn còn chỗ cần cải thiện.
Điều gì tệ hơn? Đầu tiên, chúng ta có một điều kiện, đó là bù đắp bảng chữ cái hiện tại và hộp kiểm chế độ dài. Điều này càng hạn chế chúng tôi: giờ đây, các ký tự giống nhau có thể được mã hóa khác nhau trong các ngữ cảnh khác nhau. Ví dụ, việc tìm kiếm các chuỗi con sẽ phải được thực hiện có tính đến điều này chứ không chỉ bằng cách so sánh các byte. Thứ hai, ngay khi chúng tôi thay đổi bảng chữ cái, việc mã hóa các ký tự ASCII trở nên tồi tệ (và đây không chỉ là bảng chữ cái Latinh mà còn cả dấu câu cơ bản, bao gồm cả dấu cách) - chúng yêu cầu thay đổi lại bảng chữ cái thành 0, nghĩa là, lại thêm một byte nữa (và sau đó là một byte khác để quay lại điểm chính của chúng ta).
Một bảng chữ cái là tốt, hai bảng chữ cái thì tốt hơn
Hãy thử thay đổi tiền tố bit một chút, thêm một vào ba tiền tố được mô tả ở trên:
0xxxxxxx - 1 byte ở chế độ bình thường, 2 byte ở chế độ dài
11xxxxxx - 1 byte
100xxxxx xxxxxxxx - 2 byte
101xxxxx xxxxxxxx xxxxxxxx - 3 byte
Bây giờ trong bản ghi hai byte có ít hơn một bit khả dụng - mã trỏ tới 0x1FFF, А не 0x3FFF. Tuy nhiên, nó vẫn lớn hơn đáng kể so với mã UTF-8 XNUMX byte, hầu hết các ngôn ngữ phổ biến vẫn phù hợp, sự mất mát đáng chú ý nhất đã rơi ra и , người Nhật buồn.
Mã mới này là gì? 11xxxxxx? Đây là một “kho lưu trữ” nhỏ có kích thước 64 ký tự, nó bổ sung cho bảng chữ cái chính của chúng ta, vì vậy tôi gọi nó là phụ trợ (phụ trợ) bảng chữ cái. Khi chúng ta chuyển đổi bảng chữ cái hiện tại, một phần của bảng chữ cái cũ sẽ trở thành bảng chữ cái phụ trợ. Ví dụ: chúng tôi đã chuyển từ ASCII sang Cyrillic - kho lưu trữ hiện chứa 64 ký tự chứa Bảng chữ cái Latinh, số, dấu cách và dấu phẩy (các phần chèn thường xuyên nhất trong các văn bản không phải ASCII). Chuyển về ASCII - và phần chính của bảng chữ cái Cyrillic sẽ trở thành bảng chữ cái phụ.
Nhờ truy cập vào hai bảng chữ cái, chúng tôi có thể xử lý một số lượng lớn văn bản với chi phí chuyển đổi bảng chữ cái tối thiểu (dấu câu thường dẫn đến việc quay trở lại ASCII, nhưng sau đó chúng tôi sẽ nhận được nhiều ký tự không phải ASCII từ bảng chữ cái bổ sung mà không cần chuyển đổi lại).
Phần thưởng: thêm tiền tố vào bảng chữ cái phụ 11xxxxxx và chọn phần bù ban đầu của nó là 0xC0, chúng tôi có được khả năng tương thích một phần với CP1252. Nói cách khác, nhiều (nhưng không phải tất cả) văn bản Tây Âu được mã hóa bằng CP1252 sẽ trông giống nhau ở UTF-C.
Tuy nhiên, ở đây nảy sinh một khó khăn: làm thế nào để có được một chữ phụ từ bảng chữ cái chính? Bạn có thể để lại phần bù tương tự, nhưng - than ôi - ở đây cấu trúc Unicode đã chống lại chúng ta. Rất thường phần chính của bảng chữ cái không nằm ở đầu khối (ví dụ: chữ “A” viết hoa của Nga có mã 0x0410, mặc dù khối Cyrillic bắt đầu bằng 0x0400). Do đó, sau khi đưa 64 ký tự đầu tiên vào kho, chúng ta có thể mất quyền truy cập vào phần đuôi của bảng chữ cái.
Để khắc phục vấn đề này, tôi đã đi qua một số khối tương ứng với các ngôn ngữ khác nhau theo cách thủ công và chỉ định độ lệch của bảng chữ cái phụ trong khối chính cho chúng. Ngoại lệ, bảng chữ cái Latinh thường được sắp xếp lại giống như base64.
Lần chỉnh sửa cuối cùng
Cuối cùng chúng ta hãy nghĩ xem chúng ta có thể cải thiện điều gì ở đâu nữa.
Lưu ý rằng định dạng 101xxxxx xxxxxxxx xxxxxxxx cho phép bạn mã hóa số lên đến 0x1FFFFF, và Unicode kết thúc sớm hơn, tại 0x10FFFF. Nói cách khác, điểm mã cuối cùng sẽ được biểu diễn dưới dạng 10110000 11111111 11111111. Vì vậy, chúng ta có thể nói rằng nếu byte đầu tiên có dạng 1011xxxx (ở đâu xxxx lớn hơn 0), thì nó có nghĩa khác. Ví dụ: bạn có thể thêm 15 ký tự khác vào đó luôn có sẵn để mã hóa theo một byte, nhưng tôi đã quyết định làm khác đi.
Bây giờ chúng ta hãy xem các khối Unicode yêu cầu ba byte. Về cơ bản, như đã đề cập, đây là những ký tự Trung Quốc - nhưng rất khó để làm bất cứ điều gì với chúng, có tới 21 nghìn ký tự trong số đó. Nhưng hiragana và katakana cũng bay đến đó - và số lượng chúng không còn nhiều nữa, chưa đến hai trăm. Và, vì chúng tôi nhớ đến tiếng Nhật nên cũng có các biểu tượng cảm xúc (trên thực tế, chúng nằm rải rác ở nhiều nơi trong Unicode, nhưng các khối chính nằm trong phạm vi 0x1F300 – 0x1FBFF). Nếu bạn nghĩ về thực tế là hiện nay có những biểu tượng cảm xúc được tập hợp từ nhiều điểm mã cùng một lúc (ví dụ: biểu tượng cảm xúc bao gồm tối đa 7 mã!), thì sẽ thật xấu hổ khi dành ba byte cho mỗi mã (7 × 3 = 21 byte vì một biểu tượng, một cơn ác mộng).
Do đó, chúng tôi chọn một số phạm vi được chọn tương ứng với biểu tượng cảm xúc, chữ hiragana và katakana, đánh số lại chúng thành một danh sách liên tục và mã hóa chúng thành hai byte thay vì ba:
1011xxxx xxxxxxxx
Tuyệt vời: biểu tượng cảm xúc đã nói ở trên, bao gồm 7 điểm mã, chiếm 8 byte trong UTF-25 và chúng tôi ghép nó vào 14 (chính xác là hai byte cho mỗi điểm mã). Nhân tiện, Habr từ chối tiêu hóa nó (cả ở trình soạn thảo cũ và mới), nên tôi phải chèn một bức ảnh vào.
Hãy thử khắc phục một vấn đề nữa. Như chúng ta nhớ, bảng chữ cái cơ bản về cơ bản là cao 6 bit, chúng tôi ghi nhớ và dán vào mã của từng ký hiệu được giải mã tiếp theo. Trong trường hợp ký tự tiếng Trung nằm trong khối 0x4E00 – 0x9FFF, đây là bit 0 hoặc 1. Điều này không thuận tiện lắm: chúng ta sẽ cần liên tục chuyển đổi bảng chữ cái giữa hai giá trị này (tức là tiêu tốn ba byte). Nhưng lưu ý rằng ở chế độ dài, từ chính mã, chúng ta có thể trừ số ký tự mà chúng ta mã hóa bằng chế độ ngắn (sau tất cả các thủ thuật được mô tả ở trên, đây là 10240) - khi đó phạm vi chữ tượng hình sẽ chuyển sang 0x2600 – 0x77FFvà trong trường hợp này, trong toàn bộ phạm vi này, 6 bit có ý nghĩa nhất (trong số 21) sẽ bằng 0. Do đó, các chuỗi chữ tượng hình sẽ sử dụng hai byte cho mỗi chữ tượng hình (tối ưu cho một phạm vi lớn như vậy), không có gây ra sự chuyển đổi bảng chữ cái.
Giải pháp thay thế: SCSU, BOCU-1
Các chuyên gia về Unicode, vừa đọc tiêu đề của bài viết, rất có thể sẽ vội nhắc nhở bạn rằng trực tiếp trong số các tiêu chuẩn Unicode có (SCSU), mô tả phương pháp mã hóa rất giống với phương pháp được mô tả trong bài viết.
Tôi thành thật thừa nhận: Tôi chỉ biết về sự tồn tại của nó sau khi tôi đắm chìm trong việc viết ra quyết định của mình. Nếu tôi biết về nó ngay từ đầu, có lẽ tôi đã cố gắng viết một bản triển khai thay vì nghĩ ra cách tiếp cận của riêng mình.
Điều thú vị là SCSU sử dụng những ý tưởng rất giống với những ý tưởng mà tôi tự nghĩ ra (thay vì khái niệm “bảng chữ cái” họ sử dụng “windows” và có nhiều ý tưởng hơn tôi có). Đồng thời, định dạng này cũng có nhược điểm: nó gần với thuật toán nén hơn một chút so với thuật toán mã hóa. Đặc biệt, tiêu chuẩn đưa ra nhiều phương pháp biểu diễn, nhưng không cho biết cách chọn phương pháp tối ưu - để làm được điều này, bộ mã hóa phải sử dụng một số loại phương pháp phỏng đoán. Vì vậy, một bộ mã hóa SCSU tạo ra bao bì tốt sẽ phức tạp và cồng kềnh hơn thuật toán của tôi.
Để so sánh, tôi đã chuyển cách triển khai SCSU tương đối đơn giản sang JavaScript - về mặt khối lượng mã, nó có thể so sánh được với UTF-C của tôi, nhưng trong một số trường hợp, kết quả còn tệ hơn hàng chục phần trăm (đôi khi nó có thể vượt quá nó, nhưng trong một số trường hợp, kết quả còn tệ hơn hàng chục phần trăm). không nhiều). Ví dụ: văn bản bằng tiếng Do Thái và tiếng Hy Lạp được mã hóa bằng UTF-C Tốt hơn 60% so với SCSU (có lẽ là do bảng chữ cái nhỏ gọn của họ).
Riêng biệt, tôi sẽ nói thêm rằng ngoài SCSU còn có một cách khác để biểu diễn Unicode một cách gọn gàng - , nhưng nó nhằm mục đích tương thích MIME (điều mà tôi không cần) và có cách tiếp cận mã hóa hơi khác. Tôi chưa đánh giá hiệu quả của nó nhưng có vẻ như nó khó có thể cao hơn SCSU.
Những cải tiến có thể có
Thuật toán mà tôi trình bày không phổ biến về mặt thiết kế (đây có lẽ là điểm mà mục tiêu của tôi khác xa nhất với mục tiêu của Hiệp hội Unicode). Tôi đã đề cập rằng nó được phát triển chủ yếu cho một nhiệm vụ (lưu trữ từ điển đa ngôn ngữ trong cây tiền tố) và một số tính năng của nó có thể không phù hợp cho các nhiệm vụ khác. Nhưng việc nó không phải là tiêu chuẩn có thể là một điểm cộng - bạn có thể dễ dàng sửa đổi nó cho phù hợp với nhu cầu của bạn.
Ví dụ: theo cách rõ ràng, bạn có thể loại bỏ sự hiện diện của trạng thái, tạo mã hóa không trạng thái - chỉ cần không cập nhật các biến offs, auxOffs и is21Bit trong bộ mã hóa và giải mã. Trong trường hợp này, sẽ không thể đóng gói một cách hiệu quả các chuỗi ký tự của cùng một bảng chữ cái, nhưng sẽ có sự đảm bảo rằng cùng một ký tự luôn được mã hóa với cùng một byte, bất kể ngữ cảnh.
Ngoài ra, bạn có thể điều chỉnh bộ mã hóa theo một ngôn ngữ cụ thể bằng cách thay đổi trạng thái mặc định - ví dụ: tập trung vào văn bản tiếng Nga, đặt bộ mã hóa và bộ giải mã ngay từ đầu offs = 0x0400 и auxOffs = 0. Điều này đặc biệt có ý nghĩa trong trường hợp chế độ không trạng thái. Nói chung, điều này sẽ tương tự như việc sử dụng mã hóa XNUMX bit cũ nhưng không loại bỏ khả năng chèn các ký tự từ tất cả Unicode nếu cần.
Một nhược điểm khác được đề cập trước đó là trong văn bản lớn được mã hóa bằng UTF-C, không có cách nào nhanh chóng để tìm ra ranh giới ký tự gần nhất với một byte tùy ý. Nếu bạn cắt đi 100 byte cuối cùng khỏi bộ đệm được mã hóa, bạn có nguy cơ nhận được rác mà bạn không thể làm gì được. Mã hóa không được thiết kế để lưu trữ nhật ký nhiều gigabyte, nhưng nói chung điều này có thể sửa được. Byte 0xBF không bao giờ được xuất hiện dưới dạng byte đầu tiên (nhưng có thể là byte thứ hai hoặc thứ ba). Vì vậy, khi mã hóa, bạn có thể chèn dãy 0xBF 0xBF 0xBF ví dụ, mỗi 10 KB - sau đó, nếu bạn cần tìm ranh giới, chỉ cần quét phần đã chọn cho đến khi tìm thấy điểm đánh dấu tương tự là đủ. Theo sau cuối cùng 0xBF được đảm bảo là sự khởi đầu của một nhân vật. (Tất nhiên, khi giải mã, chuỗi ba byte này sẽ cần được bỏ qua.)
Tổng hợp
Nếu bạn đã đọc đến đây, xin chúc mừng! Tôi hy vọng bạn cũng như tôi, đã học được điều gì đó mới (hoặc làm mới trí nhớ của bạn) về cấu trúc của Unicode.
Trang demo. Ví dụ về tiếng Do Thái cho thấy những ưu điểm so với cả UTF-8 và SCSU.
Nghiên cứu được mô tả ở trên không nên được coi là sự xâm phạm các tiêu chuẩn. Tuy nhiên, nhìn chung tôi hài lòng với kết quả công việc của mình nên tôi hài lòng với chúng : ví dụ: một thư viện JS được rút gọn chỉ nặng 1710 byte (và tất nhiên không có phần phụ thuộc). Như tôi đã đề cập ở trên, tác phẩm của cô ấy có thể được tìm thấy tại (cũng có một bộ văn bản có thể so sánh với UTF-8 và SCSU).
Cuối cùng, một lần nữa tôi sẽ thu hút sự chú ý đến các trường hợp sử dụng UTF-C không đáng:
- Nếu dòng của bạn đủ dài (từ 100-200 ký tự). Trong trường hợp này, bạn nên nghĩ đến việc sử dụng các thuật toán nén như giảm phát.
- Nếu bạn cần tính minh bạch của ASCII, nghĩa là, điều quan trọng đối với bạn là các chuỗi được mã hóa không chứa các mã ASCII không có trong chuỗi gốc. Có thể tránh được nhu cầu này nếu khi tương tác với API của bên thứ ba (ví dụ: làm việc với cơ sở dữ liệu), bạn chuyển kết quả mã hóa dưới dạng tập hợp byte trừu tượng chứ không phải dưới dạng chuỗi. Nếu không, bạn có nguy cơ gặp phải những lỗ hổng không mong muốn.
- Nếu bạn muốn có thể nhanh chóng tìm thấy ranh giới ký tự ở một độ lệch tùy ý (ví dụ: khi một phần của dòng bị hỏng). Điều này có thể được thực hiện nhưng chỉ bằng cách quét dòng từ đầu (hoặc áp dụng sửa đổi được mô tả trong phần trước).
- Nếu bạn cần thực hiện nhanh các thao tác trên nội dung của chuỗi (sắp xếp chúng, tìm kiếm chuỗi con trong đó, nối chuỗi). Điều này yêu cầu các chuỗi phải được giải mã trước, vì vậy UTF-C sẽ chậm hơn UTF-8 trong những trường hợp này (nhưng nhanh hơn thuật toán nén). Vì cùng một chuỗi luôn được mã hóa theo cùng một cách nên không cần phải so sánh chính xác quá trình giải mã và có thể được thực hiện trên cơ sở từng byte.
Cập nhật: người sử dụng đã đăng một biểu đồ nêu bật các giới hạn khả năng áp dụng của UTF-C. Nó cho thấy UTF-C hiệu quả hơn thuật toán nén đa năng (một biến thể của LZW) miễn là chuỗi được đóng gói ngắn hơn ~140 ký tự (tuy nhiên, tôi lưu ý rằng việc so sánh được thực hiện trên một văn bản; đối với các ngôn ngữ khác, kết quả có thể khác).
Nguồn: www.habr.com