소개

모든 것은 주소 정보를 결합하는 짧은 스크립트로 시작되었습니다. 이메일 HR 부서 데이터베이스에서 얻은 직원 직위와 메일링 리스트 사용자 목록에서 얻은 직원. 두 목록 모두 유니코드 텍스트 파일로 내보내졌습니다. UTF-8 Unix 줄 끝으로 저장됩니다.

함유량 메일.txt

Иванов Андрей;[email protected]

함유량 buhg.txt

Иванова Алла;маляр
Ёлкина Элла;крановщица
Иванов Андрей;слесарь
Абаканов Михаил;маляр

병합하기 위해 파일은 Unix 명령으로 정렬되었습니다. 종류 Unix 프로그램의 입력에 제출되었습니다. 어울리다, 오류로 인해 예기치 않게 실패했습니다.

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: is not sorted: Иванов Андрей;слесарь

정렬 결과를 눈으로 보면 대체적으로 정렬이 맞는 것으로 나타났으나, 남성과 여성의 성이 일치하는 경우에는 여성의 성이 남성보다 먼저 옵니다.

$> sort buhg.txt
Абаканов Михаил;маляр
Ёлкина Элла;крановщица
Иванова Алла;маляр
Иванов Андрей;слесарь

유니코드의 정렬 결함처럼 보이거나 정렬 알고리즘에서 페미니즘의 표현처럼 보입니다. 물론 첫 번째가 더 그럴듯합니다.

일단은 미루자 어울리다 에 집중하고 종류. 과학적인 찌르기를 이용하여 문제를 해결해 봅시다. 먼저 로케일을 다음과 같이 변경해 보겠습니다. ko 페이지 에 ru_RU. 정렬하려면 환경 변수를 설정하는 것으로 충분합니다. LC_COLLATE, 그러나 우리는 사소한 일에 시간을 낭비하지 않을 것입니다:

$> LANG=ru_RU.UTF-8 sort buhg.txt
Абаканов Михаил;маляр
Ёлкина Элла;крановщица
Иванова Алла;маляр
Иванов Андрей;слесарь

아무것도 바뀌지 않았습니다.

파일을 단일 바이트 인코딩으로 다시 코딩해 보겠습니다.

$> iconv -f UTF-8 -t KOI8-R buhg.txt 
 | LANG=ru_RU.KOI8-R sort 
 | iconv -f KOI8-R -t UTF8

이번에도 아무것도 변하지 않았습니다.

당신이 할 수 있는 일은 아무것도 없습니다. 인터넷에서 해결책을 찾아야 합니다. 러시아 성에 관한 직접적인 내용은 없지만 다른 분류 이상한 점에 대한 질문이 있습니다. 예를 들어, 여기에 문제가 있습니다: 유닉스 정렬은 '-'(대시) 문자를 보이지 않는 문자로 처리합니다.. 즉, 문자열 "ab", "aa", "ac"는 "aa", "ab", "ac"로 정렬됩니다.

대답은 어디에서나 표준입니다. 프로그래머 로캘을 사용하세요. "C" 그러면 당신은 행복해질 것입니다. 해보자:

$> LANG=C sort buhg.txt
Ёлкина Элла;крановщица
Абаканов Михаил;маляр
Иванов Андрей;слесарь
Иванова Алла;адвокат

뭔가가 바뀌었습니다. Ivanovs는 올바른 순서로 줄을 섰지 만 Yolkina는 어딘가에 미끄러졌습니다. 원래 문제로 돌아가 보겠습니다.

$> LANG=C sort buhg.txt > buhg.srt
$> LANG=C sort mail.txt > mail.srt
$> LANG=C join buhg.srt mail.srt > result

인터넷이 약속한 대로 오류 없이 작동했습니다. 그리고 이것은 첫 번째 줄의 Yolkina에도 불구하고입니다.

문제가 해결된 것 같지만 혹시 모르니 다른 러시아어 인코딩을 시도해 보겠습니다. - Windows CP1251:

$> iconv -f UTF-8 -t CP1251 buhg.txt 
 | LANG=ru_RU.CP1251 sort 
 | iconv -f CP1251 -t UTF8 

이상하게도 정렬 결과는 로케일과 일치합니다. "C", 따라서 전체 예제는 오류 없이 실행됩니다. 일종의 신비주의.

나는 프로그래밍의 신비주의를 좋아하지 않습니다. 신비주의는 대개 실수를 가리기 때문입니다. 우리는 그것이 어떻게 작동하는지 진지하게 조사해야 할 것입니다. 종류 그리고 그것은 어떤 영향을 미치나요? LC_COLLATE .

마지막으로 나는 다음 질문에 답하려고 노력할 것입니다.

• 왜 여자 성이 잘못 정렬되었나요?
• 이유 LANG=ru_RU.CP1251 동등한 것으로 판명되었습니다 LAN=C
• 왜 이렇게 종류 и 어울리다 정렬된 문자열의 순서에 대한 다른 생각
• 왜 모든 예시에 오류가 있나요?
• 마지막으로 원하는 대로 문자열을 정렬하는 방법

유니코드로 정렬

첫 번째 목적지는 기술 보고서 ​​10번입니다. 유니코드 대조 알고리즘 온라인으로 unicode.org. 보고서에는 기술적 세부사항이 많이 포함되어 있으므로 주요 아이디어를 간략하게 요약하겠습니다.

정렬 — 문자열 "비교"는 모든 정렬 알고리즘의 기초입니다. 알고리즘 자체는 다를 수 있지만("버블", "병합", "빠름") 모두 문자열 쌍의 비교를 사용하여 표시되는 순서를 결정합니다.

자연어로 문자열을 정렬하는 것은 상당히 복잡한 문제입니다. 가장 단순한 단일 바이트 인코딩에서도 알파벳 문자 순서는 영어 라틴 알파벳과 어떤 방식으로든 다르더라도 해당 문자가 인코딩되는 숫자 값의 순서와 더 이상 일치하지 않습니다. 그래서 독일어 알파벳에서 문자는 Ö 사이에 서있다 О и P, 그리고 인코딩에서 CP850 그녀는 사이에 끼어 ÿ и Ü.

특정 인코딩을 추상화하고 유니코드에서와 같이 특정 순서로 배열된 "이상적인" 문자를 고려할 수 있습니다. 인코딩 UTF8, UTF16 또는 XNUMX바이트 KOI8-R (유니코드의 제한된 하위 집합이 필요한 경우) 문자의 다른 숫자 표현을 제공하지만 기본 테이블의 동일한 요소를 참조합니다.

처음부터 기호 테이블을 구축하더라도 보편적인 기호 순서를 여기에 할당할 수는 없다는 것이 밝혀졌습니다. 동일한 문자를 사용하는 다른 국가 알파벳에서는 이러한 문자의 순서가 다를 수 있습니다. 예를 들어 프랑스어에서는 Æ 합자로 간주되어 문자열로 정렬됩니다. AE. 노르웨이어 Æ 별도의 편지가 될 것입니다. Z. 그건 그렇고, 다음과 같은 합자 외에도 Æ 여러 기호로 쓰여진 편지가 있습니다. 체코 알파벳에는 문자가 있습니다 Ch, 사이에 서 있는 H и I.

알파벳의 차이 외에도 정렬에 영향을 미치는 다른 국가 전통이 있습니다. 특히, 대문자와 소문자로 구성된 단어가 사전에 어떤 순서로 나타나야 하는가라는 질문이 생깁니다. 구두점 사용으로 인해 정렬이 영향을 받을 수도 있습니다. 스페인어에서는 의문문의 시작 부분에 거꾸로 된 물음표를 사용합니다.음악을 좋아해요?). 이 경우 의문문을 알파벳 외부에서 별도의 묶음으로 묶어서는 안 된다는 점은 분명한데, 다른 구두점으로 줄을 어떻게 정렬해야 할까요?

나는 유럽 언어와 매우 다른 언어로 문자열을 정렬하는 것에 머물지 않을 것입니다. 오른쪽에서 왼쪽 또는 위에서 아래로 쓰기 방향을 사용하는 언어에서는 줄의 문자가 읽기 순서로 저장될 가능성이 높으며 알파벳이 아닌 쓰기 시스템에도 줄을 문자별로 정렬하는 고유한 방식이 있습니다. . 예를 들어, 상형문자는 스타일(한자 키) 또는 발음으로. 솔직히 말해서 이모티콘을 어떻게 배열해야 할지 모르겠지만 이모티콘을 위한 뭔가를 생각해 낼 수도 있습니다.

위에 나열된 기능을 기반으로 유니코드 테이블을 기반으로 문자열을 비교하기 위한 기본 요구 사항이 공식화되었습니다.

• 문자열 비교는 코드 테이블의 문자 위치에 의존하지 않습니다.
• 단일 문자를 구성하는 문자 시퀀스는 표준 형식으로 축소됩니다(A + 위쪽 원은 다음과 같습니다. Å);
• 문자열을 비교할 때 문자는 문자열의 맥락에서 고려되며 필요한 경우 이웃 문자와 하나의 비교 단위로 결합됩니다(Ch 체코어로) 또는 여러 개로 나누어집니다(Æ 프랑스어);
• 모든 국가별 기능(알파벳, 대문자/소문자, 구두점, 쓰기 유형 순서)은 순서(이모지) 수동 지정까지 구성되어야 합니다.
• 비교는 정렬뿐만 아니라 행 범위 지정({A... z}로 대체)과 같은 다른 여러 위치에서도 중요합니다. 세게 때리다);
• 비교는 상당히 빨리 이루어져야합니다.

또한 보고서 작성자는 알고리즘 개발자가 의존해서는 안 되는 비교 속성을 다음과 같이 공식화했습니다.

• 비교 알고리즘은 각 언어에 대해 별도의 문자 집합을 요구해서는 안 됩니다(러시아어와 우크라이나어는 대부분의 키릴 문자를 공유함).
• 비교 시 유니코드 테이블의 문자 순서에 의존해서는 안 됩니다.
• 문자열 가중치는 문자열의 속성이 되어서는 안 됩니다. 왜냐하면 서로 다른 문화적 맥락에서 동일한 문자열이 서로 다른 가중치를 가질 수 있기 때문입니다.
• 행 가중치는 병합 또는 분할 시 변경될 수 있습니다( x < y 그건 그에 따르지 않아 xz < yz);
• 동일한 가중치를 갖는 다른 문자열은 정렬 알고리즘의 관점에서 동일한 것으로 간주됩니다. 이러한 문자열의 추가 순서를 도입하는 것은 가능하지만 성능이 저하될 수 있습니다.
• 반복 정렬 중에 동일한 가중치를 가진 행이 바뀔 수 있습니다. 견고성은 문자열 비교 알고리즘의 속성이 아니라 특정 정렬 알고리즘의 속성입니다(이전 단락 참조).
• 문화적 전통이 개선/변화함에 따라 시간이 지남에 따라 정렬 규칙이 변경될 수 있습니다.

또한 비교 알고리즘은 처리되는 문자열의 의미에 대해 아무것도 모른다고 명시되어 있습니다. 따라서 숫자로만 구성된 문자열을 숫자로 비교해서는 안 되며, 영어 이름 목록에서는 관사(비틀즈,).

명시된 모든 요구사항을 만족시키기 위해 다중 레벨(실제로는 XNUMX레벨) 테이블 정렬 알고리즘이 제안되었습니다.

이전에는 문자열의 문자가 표준 형식으로 축소되어 비교 단위로 그룹화되었습니다. 각 비교 단위에는 여러 비교 수준에 해당하는 여러 가중치가 할당됩니다. 비교 단위의 가중치는 어느 정도 비교할 수 있는 순서 집합(이 경우 정수)의 요소입니다. 특별한 의미 무시 (0x0)은 해당 비교 수준에서 이 단위가 비교에 포함되지 않음을 의미합니다. 문자열 비교는 해당 수준의 가중치를 사용하여 여러 번 반복될 수 있습니다. 각 레벨에서는 두 문자열의 비교 단위의 가중치를 순차적으로 비교합니다.

다양한 국가 전통에 대한 알고리즘의 다양한 구현에서 계수 값은 다를 수 있지만 유니코드 표준에는 기본 가중치 테이블이 포함되어 있습니다. "기본 유니코드 데이터 정렬 요소 테이블" (듀셋). 변수 설정에 주목하고 싶습니다 LC_COLLATE 실제로 문자열 비교 기능에서 가중치 테이블 선택을 나타냅니다.

가중치 계수 듀셋 다음과 같이 정리되었습니다.

• 첫 번째 수준에서는 모든 문자가 동일한 대소문자로 축소되고 발음 구별 부호가 삭제되며 구두점(모두는 아님)이 무시됩니다.
• 두 번째 수준에서는 발음 구별 부호만 고려됩니다.
• 세 번째 수준에서는 대소문자만 고려됩니다.
• 네 번째 수준에서는 구두점만 고려됩니다.

비교는 여러 단계로 이루어집니다. 먼저 첫 번째 수준의 계수가 비교됩니다. 가중치가 일치하면 두 번째 수준 가중치와의 반복 비교가 수행됩니다. 그러면 아마도 세 번째와 네 번째가 될 것입니다.

행에 서로 다른 가중치를 갖는 일치하는 비교 단위가 포함되면 비교가 종료됩니다. 네 가지 수준 모두에서 동일한 가중치를 갖는 행은 서로 동일한 것으로 간주됩니다.

이 알고리즘(많은 추가 기술 세부 사항 포함)은 보고서 번호 10에 이름을 부여했습니다. "유니코드 대조 알고리즘" (ACU).

여기에서 예제의 정렬 동작이 좀 더 명확해집니다. 유니코드 표준과 비교해보면 좋을 것 같습니다.

구현을 테스트하려면 ACU 특별한 것이 있습니다 тест, 사용 가중치 파일, 구현 듀셋. scales 파일에서 온갖 종류의 재미있는 것들을 찾을 수 있습니다. 예를 들어, 마작과 유럽식 도미노의 순서가 있고, 카드 덱의 무늬 순서도 있습니다(기호). 1F000 그리고 더). 카드 슈트는 브리지 - PCBT 규칙에 따라 배치되며 슈트의 카드는 T, 2,3, XNUMX...K 순서로 배치됩니다.

다음에 따라 행이 올바르게 정렬되었는지 수동으로 확인합니다. 듀셋 상당히 지루할 수 있지만 다행히도 유니코드 작업을 위한 라이브러리의 예시적인 구현이 있습니다.유니코드용 국제 구성 요소"(ICU).

에서 개발된 이 도서관의 웹사이트에서 IBM, 다음을 포함한 데모 페이지가 있습니다. 문자열 비교 알고리즘 페이지. 우리는 기본 설정으로 테스트 라인을 입력했고, 보라, 완벽한 러시아어 정렬을 얻었습니다.

Абаканов Михаил;маляр
Ёлкина Элла;крановщица
Иванов Андрей;слесарь
Иванова Алла;адвокат

참고로 홈페이지 ICU 구두점을 처리할 때 비교 알고리즘에 대한 설명을 찾을 수 있습니다. 예제에서는 대조 FAQ 아포스트로피와 하이픈은 무시됩니다.

유니코드가 도움이 되었지만 이상한 동작의 원인을 찾아보세요. 종류 в Linux 다른 곳으로 가야 할 것이다.

glibc에서 정렬

유틸리티 소스 코드 빠르게 보기 종류 으로 GNU 핵심 유틸리티 유틸리티 자체에서 현지화는 변수의 현재 값을 인쇄하는 것으로 귀결됩니다. LC_COLLATE 디버그 모드에서 실행할 때:

$ sort --debug buhg.txt > buhg.srt
sort: using ‘en_US.UTF8’ sorting rules

문자열 비교는 표준 함수를 사용하여 수행됩니다. 스트콜, 이는 흥미로운 모든 것이 도서관에 있다는 것을 의미합니다. glibc에.

에 위키 계획 glibc에 문자열 비교 전용 한 문단. 이 단락에서 다음과 같이 이해될 수 있습니다. glibc에 정렬은 이미 우리에게 알려진 알고리즘을 기반으로 합니다. ACU (유니코드 대조 알고리즘) 및/또는 이에 가까운 표준에서 ISO 14651 (국제 문자열 순서 및 비교). 최신 표준과 관련하여 사이트에 나와 있는 내용을 참고하시기 바랍니다. 표준.iso.org ISO 14651 공식적으로 공개적으로 사용 가능하다고 선언되었지만 해당 링크는 존재하지 않는 페이지로 연결됩니다. Google은 XNUMX유로에 표준의 전자 사본을 구매할 수 있는 공식 사이트에 대한 링크가 포함된 여러 페이지를 반환하지만 검색 결과의 세 번째 또는 네 번째 페이지에는 다음 페이지로 직접 연결되는 링크도 있습니다. PDF. 일반적으로 표준은 실질적으로 다음과 다르지 않습니다. ACU, 그러나 문자열 정렬의 국가적 특징에 대한 명확한 예가 포함되어 있지 않기 때문에 읽기가 더 지루합니다.

가장 흥미로운 정보는 위키 에 대한 링크가있었습니다 버그 추적기 문자열 비교 구현에 대한 논의와 함께 glibc에. 토론을 통해 다음을 알 수 있습니다. glibc에 문자열을 비교하는 데 사용 ISO개인 테이블 공통 템플릿 테이블 (CTT), 주소는 신청서에서 확인할 수 있습니다. A 기준 ISO 14651. 2000년에서 2015년 사이에 이 표는 glibc에 관리자가 없었고 (적어도 외부적으로는) 현재 버전의 표준과 상당히 달랐습니다. 2015년부터 2018년까지 새 버전의 테이블에 대한 적응이 이루어졌으며 이제 새 버전의 테이블을 실물로 만날 수 있는 기회가 생겼습니다.8 CentOS에) 및 이전 (7 CentOS에).

이제 알고리즘과 보조 테이블에 대한 모든 정보를 얻었으므로 원래 문제로 돌아가 러시아어 로케일에서 문자열을 올바르게 정렬하는 방법을 이해할 수 있습니다.

ISO 14651 / 14652

우리가 관심 있는 테이블의 소스 코드 CTT 대부분의 배포판에서 Linux 디렉토리에 있습니다 /usr/share/i18n/locales/. 테이블 자체가 파일에 있습니다. iso14651_t1_common. 다음은 파일 지시어입니다. iso14651_t1_common 복사 파일에 포함됨 iso14651_t1, 이는 다음을 포함하여 국가 파일에 포함됩니다. ko 페이지 и ru_RU. 대부분의 배포판에서 Linux 모든 소스 파일은 기본 설치에 포함되어 있지만, 없으면 배포판에서 추가 패키지를 설치해야 합니다.

파일 구조 iso14651_t1 이름 구성에 대한 명확하지 않은 규칙으로 인해 매우 장황해 보일 수 있지만 살펴보면 모든 것이 매우 간단합니다. 구조는 표준에 설명되어 있습니다. ISO 14652, 웹사이트에서 사본을 다운로드할 수 있음 open-std.org. 파일 형식에 대한 또 다른 설명은 다음에서 읽을 수 있습니다. 명세서 POSIX 부터 오픈그룹. 표준을 읽는 대신 함수의 소스 코드를 연구할 수 있습니다. 대조_읽기 в glibc/locale/programs/ld-collate.c.

파일 구조는 다음과 같습니다.

기본적으로 해당 문자는 이스케이프 문자로 사용되며, # 문자 뒤의 줄 끝은 주석입니다. 두 기호 모두 재정의할 수 있으며 이는 새 버전의 테이블에서 수행됩니다.

escape_char /
comment_char %

파일에는 다음 형식의 토큰이 포함됩니다. 또는 (어디 x - XNUMX진수). 이는 인코딩에서 유니코드 코드 포인트의 XNUMX진수 표현입니다. UCS-4 (UTF-32). 꺾쇠 괄호 안의 다른 모든 요소(포함) , 등)은 문맥 밖에서는 거의 의미가 없는 단순한 문자열 상수로 간주됩니다.

선 LC_COLLATE 다음으로 문자열 비교를 설명하는 데이터가 시작된다는 것을 알려줍니다.

먼저, 비교표의 가중치에 대한 이름과 기호 조합에 대한 이름을 지정합니다. 일반적으로 두 가지 유형의 이름은 서로 다른 두 엔터티에 속하지만 실제 파일에서는 혼합되어 있습니다. 가중치의 이름은 키워드로 지정됩니다. 조합 기호 (비교 문자) 비교 시 동일한 가중치를 갖는 유니코드 문자는 동등한 문자로 간주되기 때문입니다.

현재 파일 개정판의 섹션 전체 길이는 약 900줄입니다. 이름의 임의성과 여러 유형의 구문을 보여주기 위해 여러 곳에서 예제를 가져왔습니다.

LC_COLLATE

collating-symbol <RES-1>
collating-symbol <BLK>
collating-symbol <MIN>
collating-symbol <WIDE>
...
collating-symbol <ARABIC>
collating-symbol <ETHPC>
collating-symbol <OSMANYA>
...
collating-symbol <S1D000>..<S1D35F>
collating-symbol <SFFFF> % Guaranteed largest symbol value. Keep at end of this list
...
collating-element <U0413_0301> from "<U0413><U0301>"
collating-element <U0413_0341> from "<U0413><U0341>"

• 조합 기호 문자열을 기록합니다 오스마냐 저울 이름표에
• 조합 기호 .. 접두사로 구성된 일련의 이름을 등록합니다. S 및 XNUMX진수 숫자 접미사 1D000 에 1D35F.
• Ffff в 조합 기호 XNUMX진수로 된 부호 없는 큰 정수처럼 보이지만 그냥 그렇게 보일 수도 있는 이름이에요
• 이름 인코딩의 코드 포인트를 의미합니다. UCS-4
• 대조 요소 에서 " " 유니코드 도트 쌍에 대한 새 이름을 등록합니다.

가중치 이름이 정의되면 실제 가중치가 지정됩니다. 비교에서는 보다 큼 관계만 중요하므로 가중치는 목록 이름의 간단한 순서에 따라 결정됩니다. "가벼운" 무게가 먼저 나열되고 그 다음에는 "무거운" 무게가 나열됩니다. 각 유니코드 문자에는 네 가지 다른 가중치가 할당된다는 점을 상기시켜 드리겠습니다. 여기에서는 단일 순서로 결합됩니다. 이론적으로는 모든 기호 이름을 네 가지 수준 중 어느 곳에서나 사용할 수 있지만 개발자가 정신적으로 이름을 수준별로 분리한다는 의견이 있습니다.

% Symbolic weight assignments

% Third-level weight assignments
<RES-1>
<BLK>
<MIN>
<WIDE>
...
% Second-level weight assignments
<BASE>
<LOWLINE> % COMBINING LOW LINE
<PSILI> % COMBINING COMMA ABOVE
<DASIA> % COMBINING REVERSED COMMA ABOVE
...
% First-level weight assignments
<S0009> % HORIZONTAL TABULATION 
<S000A> % LINE FEED
<S000B> % VERTICAL TABULATION
...
<S0434> % CYRILLIC SMALL LETTER DE
<S0501> % CYRILLIC SMALL LETTER KOMI DE
<S0452> % CYRILLIC SMALL LETTER DJE
<S0503> % CYRILLIC SMALL LETTER KOMI DJE
<S0453> % CYRILLIC SMALL LETTER GJE
<S0499> % CYRILLIC SMALL LETTER ZE WITH DESCENDER
<S0435> % CYRILLIC SMALL LETTER IE
<S04D7> % CYRILLIC SMALL LETTER IE WITH BREVE
<S0454> % CYRILLIC SMALL LETTER UKRAINIAN IE
<S0436> % CYRILLIC SMALL LETTER ZHE

마지막으로 실제 체중표입니다.

가중치 섹션은 키워드 줄로 묶여 있습니다. 주문_시작 и 주문_끝. 추가 옵션 주문_시작 각 비교 수준에서 행이 스캔되는 방향을 결정합니다. 기본 설정은 앞으로. 섹션의 본문은 기호 코드와 해당 네 가지 가중치를 포함하는 줄로 구성됩니다. 문자 코드는 문자 자체, 코드 포인트 또는 이전에 정의된 기호 이름으로 표시될 수 있습니다. 가중치는 기호 이름, 코드 포인트 또는 기호 자체에 부여될 수도 있습니다. 코드 포인트 또는 문자가 사용되는 경우 해당 가중치는 코드 포인트의 숫자 값(유니코드 테이블의 위치)과 동일합니다. 명시적으로 지정되지 않은 문자는(내가 이해한 대로) 유니코드 테이블의 위치와 일치하는 기본 가중치를 사용하여 테이블에 할당된 것으로 간주됩니다. 특별 중량 값 무시 이는 적절한 비교 수준에서 기호가 무시된다는 것을 의미합니다.

저울의 구조를 보여주기 위해 저는 매우 분명한 세 가지 조각을 선택했습니다.

• 완전히 무시되는 문자
• 처음 두 레벨의 숫자 XNUMX에 해당하는 기호
• 발음 구별 부호가 포함되어 있지 않으므로 주로 첫 번째와 세 번째 수준으로 정렬되는 키릴 문자의 시작 부분입니다.

order_start forward;forward;forward;forward,position
<U0000> IGNORE;IGNORE;IGNORE;IGNORE % NULL (in 6429)
<U0001> IGNORE;IGNORE;IGNORE;IGNORE % START OF HEADING (in 6429)
<U0002> IGNORE;IGNORE;IGNORE;IGNORE % START OF TEXT (in 6429)
...
<U0033> <S0033>;<BASE>;<MIN>;<U0033> % DIGIT THREE
<UFF13> <S0033>;<BASE>;<WIDE>;<UFF13> % FULLWIDTH DIGIT THREE
<U2476> <S0033>;<BASE>;<COMPAT>;<U2476> % PARENTHESIZED DIGIT THREE
<U248A> <S0033>;<BASE>;<COMPAT>;<U248A> % DIGIT THREE FULL STOP
<U1D7D1> <S0033>;<BASE>;<FONT>;<U1D7D1> % MATHEMATICAL BOLD DIGIT THREE
...
<U0430> <S0430>;<BASE>;<MIN>;<U0430> % CYRILLIC SMALL LETTER A
<U0410> <S0430>;<BASE>;<CAP>;<U0410> % CYRILLIC CAPITAL LETTER A
<U04D1> <S04D1>;<BASE>;<MIN>;<U04D1> % CYRILLIC SMALL LETTER A WITH BREVE
<U0430_0306> <S04D1>;<BASE>;<MIN>;<U04D1> % CYRILLIC SMALL LETTER A WITH BREVE
...
<U0431> <S0431>;<BASE>;<MIN>;<U0431> % CYRILLIC SMALL LETTER BE
<U0411> <S0431>;<BASE>;<CAP>;<U0411> % CYRILLIC CAPITAL LETTER BE
<U0432> <S0432>;<BASE>;<MIN>;<U0432> % CYRILLIC SMALL LETTER VE
<U0412> <S0432>;<BASE>;<CAP>;<U0412> % CYRILLIC CAPITAL LETTER VE
...
order_end

이제 기사의 시작 부분부터 예제 정렬로 돌아갈 수 있습니다. 매복은 가중치 표의 다음 부분에 있습니다.

<U0020> IGNORE;IGNORE;IGNORE;<U0020> % SPACE
<U0021> IGNORE;IGNORE;IGNORE;<U0021> % EXCLAMATION MARK
<U0022> IGNORE;IGNORE;IGNORE;<U0022> % QUOTATION MARK
...

이 표에서 표의 구두점을 볼 수 있습니다. ASCII (공백 포함)은 문자열을 비교할 때 거의 항상 무시됩니다. 유일한 예외는 일치하는 위치에 있는 구두점을 제외한 모든 항목에서 일치하는 행입니다. 비교 알고리즘에 대한 내 예제(정렬 후)의 행은 다음과 같습니다.

АбакановМихаилмаляр
ЁлкинаЭллакрановщица
ИвановаАлламаляр
ИвановАндрейслесарь

천칭표에서 러시아어 대문자가 소문자 뒤에 오는 것을 고려하면(세 번째 수준에서) 보다 무거운 ), 정렬이 완전히 올바른 것 같습니다.

변수를 설정할 때 LC_COLLATE=C 바이트별 비교를 지정하는 특수 테이블이 로드됩니다.

static const uint32_t collseqwc[] =
{
  8, 1, 8, 0x0, 0xff,
  /* 1st-level table */
  6 * sizeof (uint32_t),
  /* 2nd-level table */
  7 * sizeof (uint32_t),
  /* 3rd-level table */
  L'x00', L'x01', L'x02', L'x03', L'x04', L'x05', L'x06', L'x07',
  L'x08', L'x09', L'x0a', L'x0b', L'x0c', L'x0d', L'x0e', L'x0f',

...
  L'xf8', L'xf9', L'xfa', L'xfb', L'xfc', L'xfd', L'xfe', L'xff'
};

유니코드에서는 코드 포인트 Ё가 A 앞에 오기 때문에 문자열은 그에 따라 정렬됩니다.

텍스트 및 이진 테이블

분명히 문자열 비교는 매우 일반적인 작업이며 테이블 구문 분석은 CTT 꽤 비용이 많이 드는 절차입니다. 테이블에 대한 액세스를 최적화하기 위해 다음 명령을 사용하여 바이너리 형식으로 컴파일됩니다. 로컬 데프.

팀 로컬 데프 국가 특성 테이블이 포함된 파일을 매개변수로 허용합니다(옵션 -i), 모든 문자는 유니코드 도트로 표시되며 유니코드 도트와 특정 인코딩 문자 간의 대응 파일(옵션) -f). 작업 결과, 마지막 매개변수에 지정된 이름을 가진 로케일에 대한 바이너리 파일이 생성됩니다.

글리빅 "전통"과 "현대"라는 두 가지 바이너리 파일 형식을 지원합니다.

전통적인 형식은 로케일 이름이 하위 디렉토리의 이름임을 의미합니다. /usr/lib/로케일/. 이 하위 디렉터리에는 바이너리 파일이 저장됩니다. LC_COLLATE, LC_CTYPE, LC_TIME 등등. 파일 LC_IDENTIFICATION 로케일의 공식 이름(디렉토리 이름과 다를 수 있음)과 주석을 포함합니다.

최신 형식에는 모든 로케일을 단일 아카이브에 저장하는 것이 포함됩니다. /usr/lib/locale/locale-아카이브, 이는 다음을 사용하여 모든 프로세스의 가상 메모리에 매핑됩니다. glibc에. 최신 형식의 로케일 이름은 일부 정식화의 대상입니다. 인코딩 이름에는 소문자로 축소된 숫자와 문자만 남습니다. 그래서 ru_RU.KOI8-R, 다음 이름으로 저장됩니다. ru_RU.koi8r.

입력 파일은 현재 디렉터리뿐만 아니라 디렉터리에서도 검색됩니다. /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ 파일용 CTT 및 인코딩 파일이 각각 있습니다.

예를 들어 다음 명령은

localedef -i ru_RU -f MAC-CYRILLIC ru_RU.MAC-CYRILLIC

파일을 컴파일합니다 /usr/share/i18n/locales/ru_RU 인코딩 파일을 사용하여 /usr/share/i18n/charmaps/MAC-CYRILLIC.gz 결과를 저장합니다. /usr/lib/locale/locale-아카이브 이름으로 ru_RU.maccyrillic

변수를 설정하면 LANG = en_US.UTF-8 то glibc에 다음과 같은 파일 및 디렉터리 순서로 로케일 바이너리를 찾습니다.

/usr/lib/locale/locale-archive
/usr/lib/locale/en_US.UTF-8/
/usr/lib/locale/en_US/
/usr/lib/locale/enUTF-8/
/usr/lib/locale/en/

로캘이 전통적인 형식과 현대적인 형식 모두에 해당하는 경우 현대적인 형식에 우선순위가 부여됩니다.

다음 명령을 사용하여 컴파일된 로캘 목록을 볼 수 있습니다. 로케일 -a.

비교표 준비

이제 이러한 지식을 바탕으로 자신만의 이상적인 문자열 비교표를 만들 수 있습니다. 이 표는 문자 Ё를 포함한 러시아어 문자를 정확하게 비교해야 하며 동시에 표에 따라 구두점을 고려해야 합니다. ASCII.

자신만의 정렬 테이블을 준비하는 과정은 가중치 테이블을 편집하고 명령을 사용하여 이진 형식으로 컴파일하는 두 단계로 구성됩니다. 로컬 데프.

최소한의 편집 비용으로 비교표를 조정할 수 있도록 다음 형식으로 ISO 14652 기존 테이블의 가중치를 조정하는 섹션이 제공됩니다. 섹션은 키워드로 시작됩니다. 이후 재주문 그리고 교체가 수행된 이후의 위치를 ​​표시하는 단계를 포함한다. 섹션은 다음 줄로 끝납니다. 재주문 종료. 테이블의 여러 섹션을 수정해야 하는 경우 각 섹션에 대해 섹션이 생성됩니다.

새 버전의 파일을 복사했습니다. iso14651_t1_common и ru_RU 저장소에서 glibc에 내 홈 디렉토리 ~/.local/share/i18n/locales/로 이동하고 섹션을 약간 편집했습니다. LC_COLLATE в ru_RU. 새 버전의 파일이 내 버전과 완벽하게 호환됩니다. glibc에. 이전 버전의 파일을 사용하려면 기호 이름과 테이블에서 교체가 시작되는 위치를 변경해야 합니다.

LC_COLLATE
% Copy the template from ISO/IEC 14651
copy "iso14651_t1"
reorder-after <U000D>
<U0020> <S0020>;<BASE>;<MIN>;<U0020> % SPACE
<U0021> <S0021>;<BASE>;<MIN>;<U0021> % EXCLAMATION MARK
<U0022> <S0022>;<BASE>;<MIN>;<U0022> % QUOTATION MARK
...
<U007D> <S007D>;<BASE>;<MIN>;<U007D> % RIGHT CURLY BRACKET
<U007E> <S007E>;<BASE>;<MIN>;<U007E> % TILDE
reorder-end
END LC_COLLATE

실제로 필드를 변경해야 할 수도 있습니다. LC_IDENTIFICATION 로케일을 가리키도록 ru_MY, 그러나 제 예에서는 로케일 검색에서 아카이브를 제외했기 때문에 이것이 필요하지 않았습니다. 로케일 아카이브.

그 로컬 데프 변수를 통해 내 폴더의 파일로 작업했습니다. I18NPATH 입력 파일을 검색하기 위해 추가 디렉터리를 추가할 수 있으며, 바이너리 파일을 저장할 디렉터리는 슬래시를 사용하여 경로로 지정할 수 있습니다.

$> I18NPATH=~/.local/share/i18n localedef -i ru_RU -f UTF-8 ~/.local/lib/locale/ru_MY.UTF-8

POSIX 다음과 같이 가정합니다. 랑 슬래시로 시작하여 로캘 파일이 있는 디렉터리에 대한 절대 경로를 작성할 수 있지만 glibc에 в Linux 모든 경로는 변수를 통해 재정의될 수 있는 기본 디렉터리에서 계산됩니다. 위치. 설치 후 LOCPATH=~/.local/lib/locale/ 현지화 관련 파일은 모두 내 폴더에서만 검색됩니다. 변수 세트가 있는 로케일 아카이브 위치 무시했다.

결정적인 테스트는 다음과 같습니다.

$> LANG=ru_MY.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
Абаканов Михаил;маляр
Ёлкина Элла;крановщица
Иванов Андрей;слесарь
Иванова Алла;адвокат

만세! 우리는 해냈다!

일부 오류

처음에 제기된 문자열 정렬에 대한 질문에 이미 답변했지만 표시되는 오류와 보이지 않는 오류에 대한 몇 가지 질문이 여전히 남아 있습니다.

원래 문제로 돌아가 보겠습니다.

그리고 프로그램 종류 그리고 프로그램 어울리다 동일한 문자열 비교 함수를 사용하십시오. glibc에. 어쩌다 그런 일이 일어난 걸까 어울리다 명령으로 정렬된 행에 정렬 오류가 발생했습니다. 종류 로케일에서 ko_US.UTF-8? 대답은 간단합니다. 종류 전체 문자열을 비교하고 어울리다 기본적으로 첫 번째 공백 문자까지 문자열의 시작인 키만 비교합니다. 내 예에서는 줄의 첫 번째 단어 정렬이 전체 줄의 정렬과 일치하지 않기 때문에 오류 메시지가 발생했습니다.

장소 "C" 정렬된 문자열에서 첫 번째 공백까지의 초기 하위 문자열도 정렬되도록 보장하지만 이는 오류를 마스킹할 뿐입니다. 오류 메시지 없이 잘못된 파일 병합 결과를 제공하는 데이터(성은 같지만 이름이 다른 사람)를 선택할 수 있습니다. 우리가 원한다면 어울리다 전체 이름으로 파일 행을 병합한 경우 올바른 방법은 필드 구분 기호를 명시적으로 지정하고 전체 행이 아닌 키 필드를 기준으로 정렬하는 것입니다. 이 경우 병합은 올바르게 진행되며 어떤 로케일에도 오류가 없습니다.

$> sort -t ; -k 1 buhg.txt > buhg.srt
$> sort -t ; -k 1 mail.txt > mail.srt
$> join -t ; buhg.srt mail.srt > result

인코딩에서 성공적으로 실행된 예 CP1251 다른 오류가 포함되어 있습니다. 사실은 나에게 알려진 모든 배포판에서 Linux 패키지에 컴파일된 로캘이 없습니다. ru_RU.CP1251. 컴파일된 로캘을 찾을 수 없는 경우 종류 우리가 관찰한 대로 바이트별 비교를 자동으로 사용합니다.

그건 그렇고, 컴파일된 로캘에 접근할 수 없는 것과 관련된 또 다른 작은 결함이 있습니다. 팀 LOCPATH=/tmp 로케일 -a 모든 로케일 목록을 제공합니다 로케일 아카이브, 그러나 변수가 설정된 경우 위치 모든 프로그램에 대해(대부분의 프로그램 포함) 장소) 이러한 로케일은 사용할 수 없습니다.

$> LOCPATH=/tmp locale -a | grep en_US
locale: Cannot set LC_CTYPE to default locale: No such file or directory
locale: Cannot set LC_MESSAGES to default locale: No such file or directory
locale: Cannot set LC_COLLATE to default locale: No such file or directory
en_US
en_US.iso88591
en_US.iso885915
en_US.utf8

$> LC_COLLATE=en_US.UTF-8 sort --debug
sort: using ‘en_US.UTF-8’ sorting rules

$> LOCPATH=/tmp LC_COLLATE=en_US.UTF-8 sort --debug
sort: using simple byte comparison

결론

문자열이 바이트 집합이라고 생각하는 데 익숙한 프로그래머라면 다음을 선택하십시오. LC_COLLATE=C.

당신이 언어학자이거나 사전 컴파일러라면, 당신의 로케일로 컴파일하는 것이 더 좋습니다.

단순한 사용자라면 명령이 다음과 같다는 사실에 익숙해지기만 하면 됩니다. ls -a 점으로 시작하는 파일과 문자로 시작하는 파일이 혼합되어 출력됩니다. 자정 사령관내부 기능을 사용하여 이름을 정렬하는 는 점으로 시작하는 파일을 목록의 시작 부분에 배치합니다.

참조

보고서 10호 유니코드 대조 알고리즘

unicode.org의 문자 가중치

ICU — IBM의 유니코드 작업을 위한 라이브러리 구현.

다음을 이용한 정렬 테스트 ICU

캐릭터 가중치 ISO 14651

축척이 있는 파일 형식에 대한 설명 ISO 14652

문자열 비교에 대한 토론 glibc에

출처 : habr.com