또 다른 자전거: UTF-30보다 60-8% 더 컴팩트한 유니코드 문자열을 저장합니다.

당신이 개발자이고 인코딩을 선택해야 하는 과제에 직면했다면 유니코드가 거의 항상 올바른 솔루션이 될 것입니다. 구체적인 표현 방법은 상황에 따라 다르지만 대부분의 경우 여기에도 보편적인 대답인 UTF-8이 있습니다. 좋은 점은 비용을 들이지 않고도 모든 유니코드 문자를 사용할 수 있다는 것입니다. 너무 많이 대부분의 경우 많은 바이트입니다. 사실, 라틴 알파벳 이상을 사용하는 언어의 경우 "너무 많지 않음"은 최소한입니다. 문자당 XNUMX바이트. 사용 가능한 문자를 256자로 제한하는 선사 시대 인코딩으로 돌아가지 않고도 더 잘할 수 있을까요?

아래에서는 이 질문에 답하려는 시도에 익숙해지고 UTF-8에 있는 중복성을 추가하지 않고도 전 세계 대부분의 언어로 줄을 저장할 수 있는 비교적 간단한 알고리즘을 구현할 것을 제안합니다.

부인 성명. 즉시 몇 가지 중요한 예약을 하겠습니다. 설명된 솔루션은 UTF-8의 보편적인 대체품으로 제공되지 않습니다., 이는 제한된 사례 목록에만 적합하며(자세한 내용은 아래 참조) 어떤 경우에도 타사 API(이에 대해 알지도 못하는)와 상호 작용하는 데 사용해서는 안 됩니다. 대부분의 경우 범용 압축 알고리즘(예: deflate)은 대용량 텍스트 데이터를 컴팩트하게 저장하는 데 적합합니다. 또한 이미 솔루션을 만드는 과정에서 동일한 문제를 해결하는 유니코드 자체의 기존 표준을 찾았습니다. 이는 다소 더 복잡하고 (종종 더 나쁩니다) 여전히 허용되는 표준이며 단순히 넣어 두는 것이 아닙니다. 무릎에 함께. 그에 대해서도 말씀드리겠습니다.

유니코드 및 UTF-8 정보

우선, 그것이 무엇인지에 대한 몇 마디 유니 코드 и UTF-8.

아시다시피, 8비트 인코딩이 널리 사용되었습니다. 이를 사용하면 모든 것이 간단해졌습니다. 256개의 문자에 0부터 255까지의 숫자를 지정할 수 있고, 0부터 255까지의 숫자를 7바이트로 표시할 수 있습니다. 맨 처음으로 돌아가면 ASCII 인코딩은 완전히 8비트로 제한되어 있으므로 바이트 표현의 최상위 비트는 XNUMX이고 대부분의 XNUMX비트 인코딩은 이와 호환됩니다("상위"만 다릅니다). 부분, 여기서 가장 중요한 비트는 XNUMX입니다).

유니코드는 이러한 인코딩과 어떻게 다르며 왜 UTF-8, UTF-16(BE 및 LE), UTF-32와 같은 특정 표현이 그렇게 많이 연결되어 있습니까? 순서대로 정리해보자.

기본 유니코드 표준은 문자(경우에 따라 문자의 개별 구성 요소)와 숫자 간의 대응 관계만 설명합니다. 그리고 이 표준에는 가능한 많은 숫자가 있습니다. 0x00 에 0x10FFFF (1개). 그러한 범위의 숫자를 변수에 넣으려면 114바이트도 112바이트도 충분하지 않습니다. 그리고 우리 프로세서는 1바이트 숫자 작업용으로 설계되지 않았기 때문에 문자당 최대 2바이트를 사용해야 합니다! 이것은 UTF-4이지만 이 형식이 인기가 없는 것은 바로 이러한 "낭비" 때문입니다.

다행히도 유니코드 내의 문자 순서는 무작위가 아닙니다. 전체 세트는 17 "로 나뉩니다.비행기", 각각 65536(0x10000)«코드 포인트" 여기서 "코드 포인트"의 개념은 간단합니다. 문자번호, 유니코드로 할당됩니다. 그러나 위에서 언급했듯이 유니코드에서는 개별 문자뿐만 아니라 해당 구성 요소 및 서비스 표시도 번호가 매겨져 있습니다(때로는 번호와 일치하는 것이 전혀 없을 수도 있습니다. 당분간은 그럴 수도 있지만 우리에게는 그다지 중요하지 않습니다). 더 정확합니다. 항상 기호가 아닌 숫자 자체의 수에 대해 구체적으로 이야기하십시오. 그러나 이하에서는 간결함을 위해 "코드 포인트"라는 용어를 암시하는 "기호"라는 단어를 자주 사용하겠습니다.

유니코드 비행기. 보시다시피 대부분(평면 4~13)은 아직 사용되지 않은 상태입니다.

가장 주목할만한 점은 모든 주요 "펄프"가 제로 평면에 있다는 것입니다.기본 다국어 비행기". 한 줄에 현대 언어(중국어 포함) 중 하나로 된 텍스트가 포함되어 있으면 이 평면을 넘어갈 수 없습니다. 그러나 나머지 유니코드도 잘라낼 수 없습니다. 예를 들어 이모티콘은 주로 끝 부분에 있습니다. 다음 비행기"보충 다국어 비행기"(다음부터 연장됩니다. 0x10000 에 0x1FFFF). 따라서 UTF-16은 다음을 수행합니다. 기본 다국어 비행기, 해당 XNUMX바이트 숫자를 사용하여 "있는 그대로" 인코딩됩니다. 그러나 이 범위의 숫자 중 일부는 특정 문자를 전혀 나타내지 않지만 이 바이트 쌍 이후에 다른 바이트 쌍을 고려해야 함을 나타냅니다. 이 XNUMX바이트의 값을 함께 결합하여 다음을 포함하는 숫자를 얻습니다. 유효한 전체 유니코드 범위. 이 아이디어를 "대리 커플"이라고 합니다. 여러분도 들어보셨을 것입니다.

따라서 UTF-16에는 "코드 포인트"당 8바이트 또는 (매우 드문 경우) XNUMX바이트가 필요합니다. 이는 항상 XNUMX바이트를 사용하는 것보다 낫지만 이 방식으로 인코딩하면 라틴어(및 기타 ASCII 문자)가 XNUMX에 공간의 절반을 낭비하게 됩니다. UTF-XNUMX은 이를 수정하도록 설계되었습니다. UTF-XNUMX의 ASCII는 이전과 마찬가지로 XNUMX바이트만 차지합니다. 코드 0x80 에 0x7FF - XNUMX바이트; ~에서 0x800 에 0xFFFF - 세 개, 그리고 0x10000 에 0x10FFFF - 1개. 한편으로는 라틴 알파벳이 좋아졌습니다. ASCII와의 호환성이 다시 돌아왔고 분포가 4바이트에서 16바이트까지 더욱 고르게 "확산"되었습니다. 그러나 라틴어 이외의 알파벳은 UTF-32에 비해 어떤 이점도 얻지 못하며 이제 많은 알파벳이 XNUMX바이트가 아닌 XNUMX바이트를 요구합니다. XNUMX바이트 레코드가 포함하는 범위는 XNUMX배로 좁아졌습니다. 0xFFFF 에 0x7FF, 중국어나 예를 들어 조지아어는 포함되지 않습니다. 키릴 문자 및 기타 2개 알파벳 - 만세 - 행운, 문자당 XNUMX바이트.

왜 이런 일이 발생합니까? UTF-8이 문자 코드를 어떻게 나타내는지 살펴보겠습니다.

숫자를 직접 표현하기 위해 기호로 표시된 비트가 여기에 사용됩니다. x. 11바이트 레코드에는 이러한 비트가 16개(21개 중)만 있음을 알 수 있습니다. 여기의 선행 비트에는 보조 기능만 있습니다. 32바이트 레코드의 경우 24비트 중 XNUMX비트가 코드 포인트 번호로 할당됩니다. XNUMX바이트(총 XNUMX비트 제공)이면 충분해 보이지만 서비스 마커가 너무 많이 차지합니다.

이게 나쁜가요? 설마. 한편으로 공간에 많은 관심을 갖고 있다면 모든 추가 엔트로피와 중복성을 쉽게 제거할 수 있는 압축 알고리즘이 있습니다. 반면에 유니코드의 목표는 가능한 가장 보편적인 코딩을 제공하는 것이었습니다. 예를 들어, 이전에 ASCII로만 작동했던 코드에 UTF-8로 인코딩된 라인을 맡길 수 있으며, 실제로 존재하지 않는 ASCII 범위의 문자를 보게 될 것을 두려워하지 않을 수 있습니다(결국 UTF-8에서는 모두 XNUMX비트부터 시작하는 바이트 - 이것이 바로 ASCII입니다. 그리고 처음부터 디코딩하지 않고 갑자기 큰 문자열에서 작은 꼬리를 잘라내려는 경우(또는 손상된 섹션 이후 정보의 일부를 복원하려는 경우) 문자가 시작되는 오프셋을 쉽게 찾을 수 있습니다. 비트 접두사가 있는 바이트를 건너뛰려면 10).

그렇다면 왜 새로운 것을 발명합니까?

동시에 deflate와 같은 압축 알고리즘을 제대로 적용할 수 없지만 문자열을 컴팩트하게 저장하려는 경우가 가끔 있습니다. 개인적으로 저는 건물을 짓는 것에 대해 생각할 때 이 문제에 직면했습니다. 압축된 접두사 트리 임의의 언어로 된 단어를 포함하는 대규모 사전의 경우. 한편으로, 각 단어는 매우 짧기 때문에 압축하는 것은 효과적이지 않습니다. 반면에 제가 고려한 트리 구현은 저장된 문자열의 각 바이트가 별도의 트리 정점을 생성하도록 설계되었으므로 그 수를 최소화하는 것이 매우 유용했습니다. 내 도서관에서 Az.js (에서와 같이 비형성2, 이를 기반으로 함) 유사한 문제는 간단히 해결할 수 있습니다. 도그-사전, 거기에 저장됨 좋은 오래된 CP1251. 그러나 이해하기 쉽듯이 이것은 제한된 알파벳에 대해서만 잘 작동합니다. 중국어로 된 줄은 그러한 사전에 추가될 수 없습니다.

이와 별도로, 이러한 데이터 구조에서 UTF-8을 사용할 때 발생하는 불쾌한 뉘앙스를 하나 더 언급하고 싶습니다. 위 그림을 보면 문자를 XNUMX바이트로 쓸 때 해당 숫자와 관련된 비트가 연속으로 나오지 않고 한 쌍의 비트로 분리되어 있는 것을 알 수 있습니다. 10 중간에: 110xxxxx 10xxxxxx. 이로 인해 두 번째 바이트의 하위 6비트가 문자 코드에서 오버플로되는 경우(즉, 전환이 발생함) 10111111 → 10000000), 첫 번째 바이트도 변경됩니다. 문자 "p"는 바이트로 표시되는 것으로 나타났습니다. 0xD0 0xBF, 다음 "r"은 이미 0xD1 0x80. 접두사 트리에서 이로 인해 부모 노드가 두 개로 분할됩니다. 하나는 접두사에 대한 것입니다. 0xD0, 그리고 또 다른 0xD1 (전체 키릴 문자는 두 번째 바이트로만 인코딩될 수 있지만)

내가 무엇을 얻었나요?

이 문제에 직면하여 나는 비트를 가지고 게임을 연습하는 동시에 유니코드 전체의 구조에 대해 좀 더 잘 알기로 결정했습니다. 그 결과 UTF-C 인코딩 형식("C")이 탄생했습니다. 팩트), 이는 코드 포인트당 3바이트 이하를 소비하며 매우 자주 전체 인코딩 라인에 대해 XNUMX바이트 추가. 이로 인해 많은 비ASCII 알파벳에서 이러한 인코딩은 다음과 같이 나타납니다. UTF-30보다 60-8% 더 컴팩트합니다..

인코딩 및 디코딩 알고리즘의 구현 예를 다음과 같은 형식으로 제시했습니다. JavaScript 및 Go 라이브러리, 코드에서 자유롭게 사용할 수 있습니다. 그러나 나는 이 형식이 어떤 의미에서는 "자전거"로 남아 있다는 점을 강조할 것이며 이 형식을 사용하는 것을 권장하지 않습니다. 왜 필요한지 깨닫지 못한 채. 이것은 심각한 "UTF-8 개선"이라기보다는 여전히 실험에 가깝습니다. 그럼에도 불구하고 코드는 깔끔하고 간결하게 작성되었으며 수많은 주석과 테스트 범위도 포함되어 있습니다.

테스트 결과 및 UTF-8과의 비교

나도 그랬어 데모 페이지, 알고리즘의 성능을 평가할 수 있는 곳에서는 알고리즘의 원리와 개발 프로세스에 대해 자세히 설명하겠습니다.

중복 비트 제거

물론 UTF-8을 기본으로 사용했습니다. 여기서 변경할 수 있는 첫 번째이자 가장 분명한 것은 각 바이트의 서비스 비트 수를 줄이는 것입니다. 예를 들어 UTF-8의 첫 번째 바이트는 항상 다음 중 하나로 시작합니다. 0, 또는 11 - 접두사 10 다음 바이트에만 해당됩니다. 접두사를 바꾸자 11 에 1, 다음 바이트에서는 접두사를 완전히 제거합니다. 무슨 일이 일어날 것?

0xxxxxxx — 1바이트
10xxxxxx xxxxxxxx - 2바이트
110xxxxx xxxxxxxx xxxxxxxx - 3바이트

잠깐만요, 21바이트 레코드는 어디에 있나요? 그러나 더 이상 필요하지 않습니다. XNUMX바이트로 쓸 때 이제 XNUMX비트를 사용할 수 있으며 이는 다음의 모든 숫자에 충분합니다. 0x10FFFF.

여기서 우리는 무엇을 희생했습니까? 가장 중요한 것은 버퍼의 임의 위치에서 문자 경계를 감지하는 것입니다. 임의의 바이트를 가리키고 그 바이트에서 다음 문자의 시작 부분을 찾을 수 없습니다. 이는 형식의 제한 사항이지만 실제로는 거의 필요하지 않습니다. 일반적으로 처음부터 버퍼를 통해 실행할 수 있습니다(특히 짧은 줄의 경우).

2바이트로 언어를 다루는 상황도 좋아졌습니다. 이제 14바이트 형식은 XNUMX비트 범위를 제공하며 이는 최대 XNUMX비트의 코드입니다. 0x3FFF. 중국인은 운이 좋지 않습니다. (그들의 성격은 대부분 다음과 같습니다. 0x4E00 에 0x9FFF), 그러나 조지아인과 다른 많은 사람들은 더 재미있습니다. 그들의 언어도 문자당 2바이트에 맞습니다.

인코더 상태를 입력하세요

이제 선 자체의 속성에 대해 생각해 보겠습니다. 사전에는 동일한 알파벳 문자로 작성된 단어가 포함되어 있는 경우가 가장 많으며 이는 다른 많은 텍스트에도 해당됩니다. 이 알파벳을 한 번 표시하고 그 안에 들어 있는 문자의 번호만 표시하는 것이 좋습니다. 유니코드 테이블의 문자 배열이 도움이 되는지 살펴보겠습니다.

위에서 언급했듯이 유니코드는 다음과 같이 구분됩니다. 비행기 각각 65536개의 코드. 그러나 이것은 매우 유용한 분할이 아닙니다(이미 말했듯이 대부분의 경우 우리는 영점 평면에 있습니다). 더 흥미로운 것은 다음과 같이 나누는 것입니다. 블록. 이러한 범위는 더 이상 고정된 길이를 갖지 않으며 더 의미가 있습니다. 일반적으로 각 범위는 동일한 알파벳의 문자를 결합합니다.

벵골어 알파벳 문자가 포함된 블록입니다. 불행하게도 역사적인 이유로 인해 이는 그다지 조밀하지 않은 패키징의 예입니다. 96개의 문자가 128개의 블록 코드 포인트에 혼란스럽게 흩어져 있습니다.

블록의 시작과 크기는 항상 16의 배수입니다. 이는 단순히 편의를 위해 수행됩니다. 또한 많은 블록이 128 또는 256의 배수인 값에서 시작하고 끝납니다. 예를 들어 기본 키릴 문자는 에서 256바이트를 차지합니다. 0x0400 에 0x04FF. 이것은 매우 편리합니다. 접두사를 한 번 저장하면 0x04, 모든 키릴 문자를 XNUMX바이트로 쓸 수 있습니다. 사실, 이렇게 하면 ASCII(및 일반적으로 다른 문자)로 돌아갈 기회를 잃게 됩니다. 그러므로 우리는 이렇게 합니다:

1. XNUMX바이트 10yyyyyy yxxxxxxx 숫자로 기호를 나타낼 뿐만 아니라 yyyyyy yxxxxxxx, 또한 변경 현재 알파벳 에 yyyyyy y0000000 (즉, 우리는 가장 중요하지 않은 비트를 제외한 모든 비트를 기억합니다. 7 비트);
2. XNUMX바이트 0xxxxxxx 이것이 현재 알파벳의 문자이다. 1단계에서 기억한 오프셋에 추가하면 됩니다. 알파벳을 바꾸지는 않았지만 오프셋은 XNUMX이므로 ASCII와의 호환성을 유지했습니다.

마찬가지로 3바이트가 필요한 코드의 경우:

1. XNUMX바이트 110yyyyy yxxxxxxx xxxxxxxx 숫자로 기호를 나타내다 yyyyyy yxxxxxxx xxxxxxxx, 변화 현재 알파벳 에 yyyyyy y0000000 00000000 (어린애 빼고 다 기억함 15 비트), 지금 있는 상자를 선택하세요. 긴 모드(알파벳을 다시 XNUMX바이트 문자로 변경하면 이 플래그가 재설정됩니다)
2. XNUMX바이트 0xxxxxxx xxxxxxxx 긴 모드에서는 현재 알파벳의 문자입니다. 마찬가지로 1단계의 오프셋을 추가합니다. 유일한 차이점은 이제 XNUMX바이트를 읽는다는 것입니다(이 모드로 전환했기 때문에).

좋습니다. 이제 동일한 7비트 유니코드 범위의 문자를 인코딩해야 하지만 시작 부분에 1바이트를 추가로 사용하고 문자당 총 XNUMX바이트를 사용합니다.

이전 버전 중 하나에서 작업합니다. 이미 UTF-8을 능가하는 경우가 많지만 여전히 개선의 여지가 있습니다.

더 나쁜 것은 무엇입니까? 먼저, 조건이 있습니다. 현재 알파벳 오프셋 및 확인란 장거리 모드. 이는 우리를 더욱 제한합니다. 이제 동일한 문자가 다른 컨텍스트에서 다르게 인코딩될 수 있습니다. 예를 들어 하위 문자열 검색은 바이트 비교뿐만 아니라 이를 고려하여 수행되어야 합니다. 둘째, 알파벳을 변경하자마자 ASCII 문자 인코딩이 잘못되었습니다(라틴 알파벳뿐만 아니라 공백을 포함한 기본 구두점도 포함). 알파벳을 다시 0으로 변경해야 합니다. 다시 한 번 추가 바이트(그리고 주요 요점으로 돌아가기 위한 또 다른 바이트)입니다.

알파벳 하나가 좋고, 두 개가 더 좋습니다

위에서 설명한 세 가지에 하나 더 추가하여 비트 접두사를 조금 변경해 보겠습니다.

0xxxxxxx — 일반 모드에서는 1바이트, 긴 모드에서는 2바이트
11xxxxxx — 1바이트
100xxxxx xxxxxxxx - 2바이트
101xxxxx xxxxxxxx xxxxxxxx - 3바이트

이제 XNUMX바이트 레코드에는 사용 가능한 비트가 하나 줄어듭니다. 즉, 최대 코드 포인트는 다음과 같습니다. 0x1FFF아니라 0x3FFF. 그러나 더블바이트 UTF-8 코드보다 여전히 눈에 띄게 크고, 대부분의 일반적인 언어가 여전히 적합하며, 가장 눈에 띄는 손실은 사라졌습니다. 히라가나 и 가타카나, 일본인은 슬프다.

이 새로운 코드는 무엇입니까? 11xxxxxx? 이것은 64자 크기의 작은 "스태시"이며 기본 알파벳을 보완하므로 보조(보조자) 알파벳. 현재 알파벳을 바꾸면 이전 알파벳의 일부가 보조 알파벳이 됩니다. 예를 들어, ASCII에서 키릴 문자로 전환했습니다. 이제 숨김에는 다음을 포함하는 64개의 문자가 포함됩니다. 라틴 알파벳, 숫자, 공백 및 쉼표 (ASCII가 아닌 텍스트에 가장 자주 삽입됨) 다시 ASCII로 전환하면 키릴 문자의 주요 부분이 보조 알파벳이 됩니다.

두 개의 알파벳에 대한 접근 덕분에 우리는 알파벳 전환에 드는 비용을 최소화하면서 많은 수의 텍스트를 처리할 수 있습니다. 다시 전환).

보너스: 하위 알파벳 접두사 추가 11xxxxxx 초기 오프셋을 다음과 같이 선택합니다. 0xC0, CP1252와 부분적인 호환성을 얻습니다. 즉, CP1252로 인코딩된 많은(전부는 아님) 서유럽 텍스트가 UTF-C에서도 동일하게 보입니다.

그러나 여기에는 어려움이 있습니다. 기본 알파벳에서 보조 알파벳을 얻는 방법은 무엇입니까? 동일한 오프셋을 그대로 둘 수 있지만 아쉽게도 여기서는 유니코드 구조가 이미 우리에게 불리하게 작용하고 있습니다. 알파벳의 주요 부분이 블록의 시작 부분에 없는 경우가 많습니다. 예를 들어 러시아 대문자 "A"에는 다음과 같은 코드가 있습니다. 0x0410, 키릴 문자 블록은 다음으로 시작하지만 0x0400). 따라서 처음 64자를 숨겨두면 알파벳의 꼬리 부분에 액세스하지 못할 수 있습니다.

이 문제를 해결하기 위해 다른 언어에 해당하는 일부 블록을 수동으로 살펴보고 해당 언어의 기본 알파벳 내에서 보조 알파벳의 오프셋을 지정했습니다. 예외적으로 라틴 알파벳은 일반적으로 base64처럼 재정렬되었습니다.

최종 손질

마지막으로 우리가 뭔가를 개선할 수 있는 부분에 대해 생각해 봅시다.

형식에 유의하세요. 101xxxxx xxxxxxxx xxxxxxxx 최대 숫자를 인코딩할 수 있습니다. 0x1FFFFF, 유니코드는 더 일찍 종료됩니다. 0x10FFFF. 즉, 마지막 코드 포인트는 다음과 같이 표시됩니다. 10110000 11111111 11111111. 따라서 첫 번째 바이트가 다음과 같은 형식이라고 말할 수 있습니다. 1011xxxx (어디 xxxx 0보다 큼), 이는 다른 의미를 갖습니다. 예를 들어, 15바이트로 인코딩하는 데 지속적으로 사용할 수 있는 문자 XNUMX개를 추가할 수 있지만 저는 다르게 하기로 결정했습니다.

이제 21바이트가 필요한 유니코드 블록을 살펴보겠습니다. 기본적으로 이미 언급했듯이 이것들은 한자입니다. 그러나 그것들로 무엇이든하기가 어렵습니다. XNUMX 개가 있습니다. 그러나 히라가나와 가타카나도 그곳으로 날아갔습니다. 더 이상 XNUMX도 안되는 숫자가 많지 않습니다. 그리고 일본어를 기억했기 때문에 이모티콘도 있습니다(사실 유니코드에서는 여러 곳에 흩어져 있지만 주요 블록은 범위에 있습니다). 0x1F300 - 0x1FBFF). 이제 여러 코드 포인트에서 동시에 조합된 이모티콘이 있다는 사실을 생각해 보면(예: 이모티콘 ‍‍‍ 최대 7개의 코드로 구성됩니다!), 각각에 7바이트를 소비하는 것은 완전히 부끄러운 일이 됩니다(하나의 아이콘을 위해 3×21 = XNUMX바이트, 악몽입니다).

따라서 우리는 이모티콘, 히라가나 및 가타카나에 해당하는 몇 가지 선택된 범위를 선택하고 하나의 연속 목록으로 번호를 다시 매기고 XNUMX바이트가 아닌 XNUMX바이트로 인코딩합니다.

1011xxxx xxxxxxxx

좋아요: 앞서 언급한 ‍‍‍ 이모티콘7개의 코드 포인트로 구성된 는 UTF-8에서 25바이트를 사용하며 이를 14 (각 코드 포인트에 대해 정확히 XNUMX바이트) 그런데 Habr이 (이전 편집기와 새 편집기 모두에서) 소화를 거부했기 때문에 사진과 함께 삽입해야 했습니다.

한 가지 문제를 더 해결해 보겠습니다. 우리가 기억하는 것처럼 기본 알파벳은 본질적으로 상위 6비트, 우리는 이를 염두에 두고 다음 디코딩된 각 기호의 코드에 붙입니다. 블록에 포함된 한자의 경우 0x4E00 - 0x9FFF, 이는 비트 0 또는 1입니다. 이는 그다지 편리하지 않습니다. 이 두 값 사이에서 알파벳을 지속적으로 전환해야 합니다(즉, 10240바이트를 소비합니다). 그러나 긴 모드에서는 코드 자체에서 짧은 모드를 사용하여 인코딩하는 문자 수를 뺄 수 있습니다(위에서 설명한 모든 트릭을 적용한 후에는 XNUMX입니다). 그러면 상형 문자의 범위가 다음으로 이동합니다. 0x2600 - 0x77FF, 이 경우 전체 범위에서 가장 중요한 6비트(21개 중)는 0과 같습니다. 따라서 상형 문자 시퀀스는 상형 문자당 XNUMX바이트를 사용합니다(이는 넓은 범위에 최적임). 알파벳 스위치를 유발합니다.

대체 솔루션: SCSU, BOCU-1

방금 기사 제목을 읽은 유니코드 전문가는 유니코드 표준 중에 직접적으로 다음이 있다는 점을 서둘러 상기시켜 줄 것입니다. 유니코드용 표준 압축 방식 (SCSU)는 기사에 설명된 것과 매우 유사한 인코딩 방법을 설명합니다.

나는 솔직히 인정합니다. 나는 내 결정을 쓰는 데 깊이 몰입한 후에야 그 존재를 알게 되었습니다. 처음부터 이에 대해 알고 있었다면 아마도 나만의 접근 방식을 고안하는 대신 구현을 작성하려고 시도했을 것입니다.

흥미로운 점은 SCSU가 제가 스스로 생각해낸 아이디어와 매우 유사한 아이디어를 사용한다는 것입니다(“알파벳” 개념 대신에 그들은 “창”을 사용하며 제가 가지고 있는 것보다 더 많은 아이디어를 사용할 수 있습니다). 동시에 이 형식에는 단점도 있습니다. 인코딩보다 압축 알고리즘에 조금 더 가깝습니다. 특히, 표준은 다양한 표현 방법을 제공하지만 최적의 표현 방법을 선택하는 방법에 대해서는 언급하지 않습니다. 이를 위해 인코더는 일종의 경험적 방법을 사용해야 합니다. 따라서 좋은 패키징을 생성하는 SCSU 인코더는 내 알고리즘보다 더 복잡하고 번거롭습니다.

비교를 위해 상대적으로 간단한 SCSU 구현을 JavaScript로 옮겼습니다. 코드 양 측면에서 UTF-C와 비슷한 것으로 나타났지만 어떤 경우에는 결과가 수십 퍼센트 더 나빴습니다(때로는 이를 초과할 수도 있지만 별로는 아닙니다). 예를 들어 히브리어와 그리스어 텍스트는 UTF-C로 인코딩되었습니다. SCSU보다 60% 더 좋음 (아마도 콤팩트한 알파벳 때문일 것입니다).

이와 별도로 SCSU 외에도 유니코드를 간결하게 표현하는 또 다른 방법이 있다는 점을 추가하겠습니다. BOCU-1, 그러나 MIME 호환성(필자는 필요하지 않음)을 목표로 하며 인코딩에 약간 다른 접근 방식을 취합니다. 나는 그 효과를 평가하지 않았지만 SCSU보다 높을 것 같지 않습니다.

가능한 개선 사항

내가 제시한 알고리즘은 설계상 보편적이지 않습니다(아마도 이것이 내 목표가 유니코드 컨소시엄의 목표와 가장 많이 다른 부분일 것입니다). 나는 이것이 주로 하나의 작업(접두사 트리에 다국어 사전 저장)을 위해 개발되었으며 그 기능 중 일부는 다른 작업에 적합하지 않을 수 있다고 이미 언급했습니다. 하지만 표준이 아니라는 점은 장점이 될 수 있습니다. 필요에 맞게 쉽게 수정할 수 있습니다..

예를 들어, 상태의 존재를 제거하고, 상태 비저장 코딩을 만들 수 있는 확실한 방법은 변수를 업데이트하지 않는 것입니다. offs, auxOffs и is21Bit 인코더와 디코더에서. 이 경우 동일한 알파벳의 문자 시퀀스를 효과적으로 묶을 수는 없지만 컨텍스트에 관계없이 동일한 문자가 항상 동일한 바이트로 인코딩된다는 보장이 있습니다.

또한 기본 상태를 변경하여 특정 언어에 맞게 인코더를 조정할 수 있습니다. 예를 들어 러시아어 텍스트에 초점을 맞추고 처음에 인코더와 디코더를 설정합니다. offs = 0x0400 и auxOffs = 0. 이는 특히 무상태 모드의 경우 의미가 있습니다. 일반적으로 이는 이전 XNUMX비트 인코딩을 사용하는 것과 유사하지만 필요에 따라 모든 유니코드에서 문자를 삽입하는 기능을 제거하지 않습니다.

앞서 언급한 또 다른 단점은 UTF-C로 인코딩된 큰 텍스트에서 임의 바이트에 가장 가까운 문자 경계를 찾는 빠른 방법이 없다는 것입니다. 인코딩된 버퍼에서 마지막 100바이트를 잘라내면 아무것도 할 수 없는 쓰레기가 생길 위험이 있습니다. 인코딩은 수 기가바이트 로그를 저장하도록 설계되지 않았지만 일반적으로 이는 수정될 수 있습니다. 바이트 0xBF 첫 번째 바이트로 표시되어서는 안 됩니다(그러나 두 번째 또는 세 번째 바이트일 수 있음). 따라서 인코딩 시 시퀀스를 삽입할 수 있습니다. 0xBF 0xBF 0xBF 예를 들어 10KB마다 - 경계를 찾아야 하는 경우 유사한 마커를 찾을 때까지 선택한 조각을 스캔하는 것으로 충분합니다. 마지막에 이어 0xBF 캐릭터의 시작이 보장됩니다. (디코딩할 때 이 XNUMX바이트 시퀀스는 물론 무시되어야 합니다.)

최대 합계

여기까지 읽으셨다면, 축하드립니다! 여러분도 저처럼 유니코드 구조에 대해 새로운 것을 배웠기를 바랍니다(또는 기억을 되살리셨기를 바랍니다).

데모 페이지. 히브리어의 예는 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