Prohoster > Blog > quản lý > Cách sắp xếp chuỗi của Linux

Cách sắp xếp chuỗi của Linux

Giới thiệu

Tất cả bắt đầu bằng một đoạn script ngắn được cho là kết hợp thông tin địa chỉ e-mail nhân viên có được từ danh sách người dùng danh sách gửi thư, với các vị trí nhân viên có được từ cơ sở dữ liệu của bộ phận nhân sự. Cả hai danh sách đều được xuất sang tệp văn bản Unicode UTF-8 và được lưu với phần cuối dòng Unix.

Nội dung thư.txt

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

Nội dung buhg.txt

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

Để hợp nhất, các tập tin đã được sắp xếp theo lệnh Unix loại và gửi đến đầu vào của chương trình Unix tham gia, không ngờ xảy ra lỗi: 

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

Xem kết quả phân loại bằng mắt cho thấy, nhìn chung cách phân loại là đúng, tuy nhiên trong trường hợp trùng họ nam và họ nữ thì họ nữ đứng trước họ nam:

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

Trông giống như một trục trặc trong việc sắp xếp trong Unicode hoặc giống như một biểu hiện của chủ nghĩa nữ quyền trong thuật toán sắp xếp. Tất nhiên, điều đầu tiên hợp lý hơn.

Hãy tạm gác nó lại bây giờ tham gia và tập trung vào loại. Hãy thử giải quyết vấn đề bằng cách chọc khoa học. Đầu tiên, hãy thay đổi ngôn ngữ từ en_US trên ru_ru. Để sắp xếp, chỉ cần đặt biến môi trường là đủ LC_THU THẬP, nhưng chúng tôi sẽ không lãng phí thời gian vào những chuyện vặt vãnh:

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

Không có gì thay đổi.

Hãy thử mã hóa lại các tệp thành mã hóa một byte: 

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

Một lần nữa không có gì thay đổi.

Bạn không thể làm gì được, bạn sẽ phải tìm kiếm giải pháp trên Internet. Không có gì trực tiếp về họ của người Nga, nhưng có những câu hỏi về những điều kỳ lạ trong cách sắp xếp khác. Ví dụ: đây là một vấn đề: sắp xếp unix coi các ký tự '-' (dấu gạch ngang) là vô hình. Tóm lại, các chuỗi "ab", "aa", "ac" được sắp xếp thành "aa", "ab", "ac".

Câu trả lời là tiêu chuẩn ở mọi nơi: sử dụng ngôn ngữ lập trình viên "C" và bạn sẽ được hạnh phúc. Hãy thử:

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

Có gì đó đã thay đổi. Các Ivanov xếp hàng theo đúng thứ tự, mặc dù Yolkina đã trượt đi đâu đó. Hãy quay trở lại vấn đề ban đầu:

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

Nó hoạt động không có lỗi như Internet đã hứa. Và điều này bất chấp Yolkina ở dòng đầu tiên.

Vấn đề dường như đã được giải quyết, nhưng để đề phòng, hãy thử một bảng mã tiếng Nga khác - Windows CP1251:

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

Kết quả sắp xếp, thật kỳ lạ, sẽ trùng với miền địa phương "C"và toàn bộ ví dụ chạy không có lỗi. Một loại chủ nghĩa thần bí nào đó.

Tôi không thích sự huyền bí trong lập trình vì nó thường che giấu những sai sót. Chúng ta sẽ phải nghiêm túc xem xét cách thức hoạt động của nó. loại và nó có tác dụng gì? LC_THU THẬP .

Cuối cùng tôi sẽ cố gắng trả lời các câu hỏi:

  • tại sao họ nữ lại được sắp xếp sai?
  • tại sao LANG=ru_RU.CP1251 hóa ra là tương đương LANG = C
  • tại sao loại и tham gia ý tưởng khác nhau về thứ tự của chuỗi được sắp xếp
  • tại sao có lỗi trong tất cả các ví dụ của tôi?
  • cuối cùng là cách sắp xếp chuỗi theo ý thích của bạn

Sắp xếp theo Unicode

Điểm dừng đầu tiên sẽ là báo cáo kỹ thuật số 10 mang tên Thuật toán đối chiếu Unicode trực tuyến unicode.org. Báo cáo chứa nhiều chi tiết kỹ thuật, vì vậy hãy để tôi tóm tắt ngắn gọn các ý chính.

Đối chiếu — Các chuỗi “so sánh” là cơ sở của bất kỳ thuật toán sắp xếp nào. Bản thân các thuật toán có thể khác nhau ("bong bóng", "hợp nhất", "nhanh"), nhưng tất cả chúng sẽ sử dụng so sánh một cặp chuỗi để xác định thứ tự chúng xuất hiện.

Sắp xếp chuỗi trong ngôn ngữ tự nhiên là một bài toán khá phức tạp. Ngay cả trong các mã hóa một byte đơn giản nhất, thứ tự các chữ cái trong bảng chữ cái, thậm chí khác với bảng chữ cái Latinh tiếng Anh theo một cách nào đó, sẽ không còn trùng với thứ tự của các giá trị số mà các chữ cái này được mã hóa. Vì vậy trong bảng chữ cái tiếng Đức chữ cái Ö đứng giữa О и P, và trong mã hóa CP850 cô ấy ở giữa ÿ и Ü.

Bạn có thể thử trừu tượng hóa khỏi một bảng mã cụ thể và xem xét các chữ cái “lý tưởng” được sắp xếp theo thứ tự nào đó, như được thực hiện trong Unicode. Mã hóa UTF8, UTF16 hoặc một byte KOI8-R (nếu cần một tập con Unicode giới hạn) sẽ đưa ra các cách biểu thị bằng số khác nhau của các chữ cái, nhưng đề cập đến cùng các thành phần của bảng cơ sở.

Hóa ra là ngay cả khi chúng ta xây dựng một bảng ký hiệu từ đầu, chúng ta sẽ không thể gán thứ tự ký hiệu chung cho nó. Trong bảng chữ cái quốc gia khác nhau sử dụng cùng một chữ cái, thứ tự của các chữ cái này có thể khác nhau. Ví dụ, trong tiếng Pháp Æ sẽ được coi là một chữ ghép và được sắp xếp thành một chuỗi AE. bằng tiếng Na Uy Æ sẽ là một chữ cái riêng biệt, nằm sau Z. Nhân tiện, ngoài các chữ ghép như Æ Có những chữ cái được viết bằng nhiều ký hiệu. Vậy trong bảng chữ cái tiếng Séc có một chữ cái Ch, đứng giữa H и I.

Ngoài sự khác biệt trong bảng chữ cái, còn có những truyền thống dân tộc khác ảnh hưởng đến việc sắp xếp. Đặc biệt, câu hỏi được đặt ra: các từ bao gồm chữ hoa và chữ thường sẽ xuất hiện trong từ điển theo thứ tự nào? Việc sắp xếp cũng có thể bị ảnh hưởng bởi việc sử dụng dấu chấm câu. Trong tiếng Tây Ban Nha, dấu hỏi ngược được dùng ở đầu câu nghi vấn (Bạn có thích âm nhạc không?). Trong trường hợp này, rõ ràng là các câu nghi vấn không nên nhóm thành một cụm riêng biệt ngoài bảng chữ cái mà làm cách nào để sắp xếp các dòng có dấu chấm câu khác?

Tôi sẽ không tập trung vào việc sắp xếp các chuỗi bằng các ngôn ngữ rất khác với các ngôn ngữ ở Châu Âu. Lưu ý rằng trong các ngôn ngữ có hướng viết từ phải sang trái hoặc từ trên xuống dưới, các ký tự trong dòng rất có thể được lưu trữ theo thứ tự đọc và ngay cả các hệ thống chữ viết không phải chữ cái cũng có cách sắp xếp dòng riêng theo từng ký tự. . Ví dụ: chữ tượng hình có thể được sắp xếp theo kiểu (phím chữ Hán) hoặc bằng cách phát âm. Thành thật mà nói, tôi không biết nên sắp xếp các biểu tượng cảm xúc như thế nào, nhưng bạn cũng có thể nghĩ ra thứ gì đó cho chúng.

Dựa trên các tính năng được liệt kê ở trên, các yêu cầu cơ bản để so sánh chuỗi dựa trên bảng Unicode đã được hình thành:

  • so sánh các chuỗi không phụ thuộc vào vị trí các ký tự trong bảng mã;
  • chuỗi các ký tự tạo thành một ký tự đơn được rút gọn thành dạng chuẩn (A + vòng tròn phía trên giống như Å);
  • Khi so sánh các chuỗi, một ký tự được xem xét trong ngữ cảnh của chuỗi và, nếu cần, được kết hợp với các ký tự lân cận của nó thành một đơn vị so sánh (Ch bằng tiếng Séc) hoặc được chia thành nhiều (Æ ở Pháp);
  • tất cả các đặc điểm quốc gia (bảng chữ cái, chữ hoa/chữ thường, dấu câu, thứ tự kiểu viết) phải được cấu hình theo cách gán thứ tự thủ công (biểu tượng cảm xúc);
  • so sánh không chỉ quan trọng trong việc sắp xếp mà còn ở nhiều nơi khác, ví dụ như để chỉ định phạm vi hàng (thay thế {A... z} trong bash);
  • việc so sánh nên được thực hiện khá nhanh chóng.

Ngoài ra, các tác giả của báo cáo đã xây dựng các thuộc tính so sánh mà các nhà phát triển thuật toán không nên dựa vào:

  • thuật toán so sánh không được yêu cầu một bộ ký tự riêng cho từng ngôn ngữ (ngôn ngữ tiếng Nga và tiếng Ukraina chia sẻ hầu hết các ký tự Cyrillic);
  • việc so sánh không nên dựa vào thứ tự các ký tự trong bảng Unicode;
  • trọng số chuỗi không phải là một thuộc tính của chuỗi, vì cùng một chuỗi trong các bối cảnh văn hóa khác nhau có thể có các trọng số khác nhau;
  • trọng số hàng có thể thay đổi khi hợp nhất hoặc chia tách (từ x < y nó không tuân theo điều đó xz < yz);
  • các chuỗi khác nhau có cùng trọng số được coi là bằng nhau theo quan điểm của thuật toán sắp xếp. Có thể giới thiệu thứ tự bổ sung của các chuỗi như vậy, nhưng nó có thể làm giảm hiệu suất;
  • Trong quá trình sắp xếp lặp đi lặp lại, các hàng có cùng trọng số có thể được hoán đổi. Tính mạnh mẽ là thuộc tính của thuật toán sắp xếp cụ thể chứ không phải thuộc tính của thuật toán so sánh chuỗi (xem đoạn trước);
  • Quy tắc sắp xếp có thể thay đổi theo thời gian khi truyền thống văn hóa được tinh chỉnh/thay đổi.

Người ta cũng quy định rằng thuật toán so sánh không biết gì về ngữ nghĩa của chuỗi đang được xử lý. Do đó, các chuỗi chỉ bao gồm các chữ số không nên được so sánh dưới dạng số và trong danh sách tên tiếng Anh bài viết (Ban nhạc The Beatles).

Để đáp ứng tất cả các yêu cầu đã chỉ định, thuật toán sắp xếp bảng đa cấp (thực tế là bốn cấp) được đề xuất.

Trước đây, các ký tự trong chuỗi được rút gọn về dạng chuẩn và được nhóm thành các đơn vị so sánh. Mỗi đơn vị so sánh được ấn định một số trọng số tương ứng với nhiều mức độ so sánh. Trọng số của các đơn vị so sánh là các phần tử của tập hợp có thứ tự (trong trường hợp này là số nguyên) có thể được so sánh nhiều hơn hoặc ít hơn. Ý nghĩa đặc biệt MẶC KỆ (0x0) có nghĩa là ở mức so sánh tương ứng, đơn vị này không tham gia vào việc so sánh. Việc so sánh các chuỗi có thể được lặp lại nhiều lần bằng cách sử dụng trọng số của các cấp độ tương ứng. Ở mỗi cấp độ, trọng số của các đơn vị so sánh của hai hàng được so sánh tuần tự với nhau.

Trong các cách triển khai thuật toán khác nhau cho các truyền thống dân tộc khác nhau, các giá trị của các hệ số có thể khác nhau, nhưng tiêu chuẩn Unicode bao gồm một bảng trọng số cơ bản - "Bảng phần tử đối chiếu Unicode mặc định" (DUCET). Tôi muốn lưu ý rằng việc đặt biến LC_THU THẬP thực tế là một dấu hiệu cho thấy việc lựa chọn bảng trọng số trong hàm so sánh chuỗi.

Hệ số trọng số DUCET được sắp xếp như sau:

  • ở cấp độ đầu tiên, tất cả các chữ cái được rút gọn về cùng một kiểu chữ, dấu phụ bị loại bỏ, dấu chấm câu (không phải tất cả) bị bỏ qua;
  • ở cấp độ thứ hai, chỉ tính đến dấu phụ;
  • ở cấp độ thứ ba, chỉ tính đến trường hợp;
  • ở cấp độ thứ tư, chỉ tính đến dấu chấm câu.

Việc so sánh diễn ra theo nhiều bước: đầu tiên, các hệ số của cấp độ đầu tiên được so sánh; nếu các trọng số trùng nhau thì tiến hành so sánh lặp lại với các trọng số cấp hai; rồi có lẽ là thứ ba và thứ tư.

Việc so sánh kết thúc khi các hàng chứa các đơn vị so sánh phù hợp với các trọng số khác nhau. Các hàng có trọng số bằng nhau ở cả XNUMX cấp độ đều được coi là bằng nhau.

Thuật toán này (với một loạt các chi tiết kỹ thuật bổ sung) đã đặt tên cho báo cáo số 10 - "Thuật toán đối chiếu Unicode" (ACU).

Đây là lúc hành vi sắp xếp từ ví dụ của chúng ta trở nên rõ ràng hơn một chút. Sẽ thật tuyệt nếu so sánh nó với tiêu chuẩn Unicode.

Để kiểm tra việc triển khai ACU có một điều đặc biệt kiểm tra, sử dụng tập tin trọng lượng, thực thi DUCET. Bạn có thể tìm thấy đủ thứ hài hước trong tập tin thang âm. Ví dụ: có thứ tự mạt chược và quân domino châu Âu, cũng như thứ tự các chất trong bộ bài (ký hiệu 1F000 và xa hơn). Các bộ bài được xếp theo quy tắc đánh bài - PCBT, các quân bài trong bộ theo thứ tự T, 2,3, XNUMX... K.

Kiểm tra thủ công xem các hàng có được sắp xếp chính xác theo DUCET sẽ khá tẻ nhạt, nhưng may mắn thay cho chúng ta, có một triển khai mẫu mực của thư viện để làm việc với Unicode - "Các thành phần quốc tế cho Unicode"(ICU).

Trên trang web của thư viện này, được phát triển ở IBM, có các trang demo, bao gồm trang thuật toán so sánh chuỗi. Chúng tôi nhập các dòng thử nghiệm của mình với cài đặt mặc định và, lạ thay, chúng tôi có được cách sắp xếp hoàn hảo theo tiếng Nga.

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

Nhân tiện, trang web ICU Bạn có thể tìm thấy phần giải thích về thuật toán so sánh khi xử lý dấu chấm câu. Trong các ví dụ Câu hỏi thường gặp về đối chiếu dấu nháy đơn và dấu gạch nối được bỏ qua.

Unicode đã giúp chúng tôi nhưng hãy tìm lý do cho hành vi kỳ lạ loại в Linux sẽ phải đi nơi khác.

Sắp xếp trong glibc

Xem nhanh mã nguồn tiện ích loại của Các ứng dụng cốt lõi của GNU cho thấy rằng trong chính tiện ích, việc bản địa hóa phụ thuộc vào việc in giá trị hiện tại của biến LC_THU THẬP khi chạy ở chế độ gỡ lỗi:

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

So sánh chuỗi được thực hiện bằng hàm tiêu chuẩn sải bước, có nghĩa là mọi thứ thú vị đều có trong thư viện glibc.

Trên wiki dự án glibc dành riêng cho việc so sánh chuỗi một đoạn văn. Từ đoạn này có thể hiểu rằng trong glibc việc sắp xếp dựa trên một thuật toán mà chúng ta đã biết ACU (Thuật toán đối chiếu Unicode) và/hoặc ở tiêu chuẩn gần với nó ISO 14651 (Thứ tự và so sánh chuỗi quốc tế). Về tiêu chuẩn mới nhất, cần lưu ý rằng trên trang web tiêu chuẩn.iso.org ISO 14651 được tuyên bố chính thức là có sẵn công khai, nhưng liên kết tương ứng dẫn đến một trang không tồn tại. Google trả lại một số trang có liên kết đến các trang web chính thức đề nghị mua bản sao điện tử của tiêu chuẩn với giá một trăm euro, nhưng trên trang thứ ba hoặc thứ tư của kết quả tìm kiếm cũng có các liên kết trực tiếp đến PDF. Nhìn chung, tiêu chuẩn thực tế không khác gì ACU, nhưng đọc sẽ nhàm chán hơn vì nó không có ví dụ rõ ràng về đặc điểm quốc gia của việc sắp xếp chuỗi.

Thông tin thú vị nhất về wiki đã có một liên kết đến theo dõi lỗi với một cuộc thảo luận về việc thực hiện so sánh chuỗi trong glibc. Từ cuộc thảo luận có thể biết được rằng glibc dùng để so sánh các chuỗi ISObàn cá nhân Bảng mẫu chung (CTT), địa chỉ có thể được tìm thấy trong ứng dụng A Tiêu chuẩn ISO 14651. Từ năm 2000 đến năm 2015, bảng này ở glibc không có bộ bảo trì và khá khác biệt (ít nhất là ở bên ngoài) so với phiên bản hiện tại của tiêu chuẩn. Từ năm 2015 đến năm 2018, quá trình chuyển đổi sang phiên bản mới của bảng đã diễn ra và bây giờ bạn có cơ hội gặp ngoài đời một phiên bản mới của bảng (CentOS 8), và cũ (CentOS 7).

Bây giờ chúng ta đã có tất cả thông tin về thuật toán và các bảng phụ trợ, chúng ta có thể quay lại vấn đề ban đầu và hiểu cách sắp xếp chính xác các chuỗi theo ngôn ngữ tiếng Nga.

ISO 14651 / 14652

Mã nguồn của bảng chúng tôi quan tâm CTT trên hầu hết các bản phân phối Linux có trong danh mục /usr/share/i18n/locales/. Bản thân bảng nằm trong tập tin iso14651_t1_common. Sau đó, đây là chỉ thị tập tin sao chép iso14651_t1_common có trong tập tin iso14651_t1, do đó, được đưa vào hồ sơ quốc gia, bao gồm en_US и ru_ru. Trên hầu hết các bản phân phối Linux Tất cả các tệp nguồn đều được bao gồm trong cài đặt cơ bản, nhưng nếu chúng không có, bạn sẽ phải cài đặt gói bổ sung từ bản phân phối.

Cấu trúc tập tin iso14651_t1 có thể có vẻ dài dòng khủng khiếp, với các quy tắc xây dựng tên không rõ ràng, nhưng nếu bạn nhìn vào nó, mọi thứ khá đơn giản. Cấu trúc được mô tả trong tiêu chuẩn ISO 14652, một bản sao có thể được tải xuống từ trang web open-std.org. Một mô tả khác về định dạng tập tin có thể được đọc trong thông số kỹ thuật POSIX từ nhóm mở. Thay thế cho việc đọc tiêu chuẩn, bạn có thể nghiên cứu mã nguồn của hàm đối chiếu_đọc в glibc/locale/chương trình/ld-collate.c.

Cấu trúc tập tin trông như thế này:

Theo mặc định, ký tự được sử dụng làm ký tự thoát và cuối dòng sau ký tự # là nhận xét. Cả hai ký hiệu đều có thể được xác định lại, đó là những gì được thực hiện trong phiên bản mới của bảng:

escape_char /
comment_char %

Tệp sẽ chứa mã thông báo ở định dạng hoặc (ở đâu x - chữ số thập lục phân). Đây là cách biểu diễn thập lục phân của các điểm mã Unicode trong bảng mã UCS-4 (UTF-32). Tất cả các phần tử khác trong dấu ngoặc nhọn (bao gồm cả , <2> và tương tự) được coi là các hằng chuỗi đơn giản, ít có ý nghĩa ngoài ngữ cảnh.

Chuỗi LC_THU THẬP cho chúng ta biết rằng tiếp theo bắt đầu dữ liệu mô tả việc so sánh các chuỗi.

Đầu tiên, tên được chỉ định cho các trọng số trong bảng so sánh và tên cho các tổ hợp ký hiệu. Nói chung, hai loại tên này thuộc về hai thực thể khác nhau nhưng trong tệp thực tế chúng được trộn lẫn với nhau. Tên của các trọng số được chỉ định bởi từ khóa đối chiếu-biểu tượng (ký tự so sánh) vì khi so sánh, các ký tự Unicode có cùng trọng số sẽ được coi là ký tự tương đương.

Tổng chiều dài của phần trong bản sửa đổi tệp hiện tại là khoảng 900 dòng. Tôi lấy ví dụ từ nhiều nơi để cho thấy tính tùy tiện của tên và một số loại cú pháp.

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>"

  • biểu tượng đối chiếu ghi lại một chuỗi OSMANYA trong bảng tên các thang đo
  • biểu tượng đối chiếu .. đăng ký một chuỗi tên bao gồm tiền tố S và hậu tố số thập lục phân từ 1D000 để 1D35F.
  • FFFF в biểu tượng đối chiếu trông giống như một số nguyên lớn không dấu ở dạng thập lục phân, nhưng đó chỉ là một cái tên có thể trông giống như
  • tên có nghĩa là điểm mã trong mã hóa UCS-4
  • phần tử đối chiếu từ " " đăng ký tên mới cho một cặp dấu chấm Unicode.

Khi tên của các trọng số được xác định, các trọng số thực tế cũng được chỉ định. Vì chỉ có quan hệ lớn hơn nhỏ mới quan trọng khi so sánh, nên các trọng số được xác định bằng một chuỗi tên liệt kê đơn giản. Trọng lượng “nhẹ hơn” được liệt kê đầu tiên, sau đó là trọng lượng “nặng hơn”. Hãy để tôi nhắc bạn rằng mỗi ký tự Unicode được gán bốn trọng số khác nhau. Ở đây chúng được kết hợp thành một chuỗi có thứ tự duy nhất. Về lý thuyết, bất kỳ tên biểu tượng nào cũng có thể được sử dụng ở bất kỳ cấp độ nào trong số bốn cấp độ, nhưng các nhận xét chỉ ra rằng các nhà phát triển đã phân tách tên thành các cấp độ một cách tinh thần.

% 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

Cuối cùng là bảng cân nặng thực tế.

Phần trọng số được đính kèm trong dòng từ khóa đặt hàng_bắt đầu и order_end. Tùy chọn bổ sung đặt hàng_bắt đầu xác định các hàng được quét theo hướng nào ở mỗi cấp độ so sánh. Cài đặt mặc định là phía trước. Phần thân của phần này bao gồm các dòng chứa mã ký hiệu và bốn trọng số của nó. Mã ký tự có thể được biểu thị bằng chính ký tự đó, điểm mã hoặc tên tượng trưng được xác định trước đó. Trọng số cũng có thể được gán cho tên tượng trưng, ​​​​điểm mã hoặc chính các ký hiệu. Nếu sử dụng điểm mã hoặc ký tự thì trọng số của chúng bằng giá trị số của điểm mã (vị trí trong bảng Unicode). Các ký tự không được chỉ định rõ ràng (theo tôi hiểu) được coi là được gán cho bảng có trọng số chính khớp với vị trí trong bảng Unicode. Giá trị trọng lượng đặc biệt VÒI có nghĩa là ký hiệu bị bỏ qua ở mức độ so sánh thích hợp.

Để chứng minh cấu trúc của thang âm, tôi đã chọn ba đoạn khá rõ ràng:

  • các ký tự hoàn toàn bị bỏ qua
  • ký hiệu tương đương với số ba ở hai cấp độ đầu tiên
  • phần đầu của bảng chữ cái Cyrillic, không chứa dấu phụ và do đó được sắp xếp chủ yếu theo cấp độ thứ nhất và thứ ba.

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

Bây giờ bạn có thể quay lại sắp xếp các ví dụ từ đầu bài viết. Cuộc phục kích nằm ở phần này của bảng trọng lượng:

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

Có thể thấy trong bảng này các dấu chấm câu từ bảng ASCII (bao gồm cả khoảng trắng) hầu như luôn bị bỏ qua khi so sánh các chuỗi. Ngoại lệ duy nhất là các dòng khớp với mọi thứ ngoại trừ dấu chấm câu được tìm thấy ở các vị trí khớp. Các dòng trong ví dụ của tôi (sau khi sắp xếp) cho thuật toán so sánh trông như thế này:

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

Xét rằng trong bảng thang đo, chữ in hoa trong tiếng Nga đứng sau chữ thường (ở cấp độ thứ ba nặng hơn ), việc sắp xếp có vẻ hoàn toàn chính xác.

Khi thiết lập một biến LC_COLLATE=C một bảng đặc biệt được tải để chỉ định so sánh từng byte

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'
};

Vì trong Unicode, điểm mã Ё đứng trước A nên các chuỗi được sắp xếp tương ứng.

Bảng văn bản và nhị phân

Rõ ràng, so sánh chuỗi là một thao tác cực kỳ phổ biến và việc phân tích bảng CTT một thủ tục khá tốn kém. Để tối ưu hóa quyền truy cập vào bảng, nó được biên dịch thành dạng nhị phân bằng lệnh localdef.

Đội localdef chấp nhận làm tham số một tệp có bảng đặc điểm quốc gia (tùy chọn -i), trong đó tất cả các ký tự được biểu thị bằng các dấu chấm Unicode và một tệp tương ứng giữa các dấu chấm Unicode và các ký tự của một bảng mã cụ thể (tùy chọn -f). Kết quả của công việc là các tệp nhị phân được tạo cho ngôn ngữ có tên được chỉ định trong tham số cuối cùng.

glibc hỗ trợ hai định dạng tệp nhị phân: "truyền thống" và "hiện đại".

Định dạng truyền thống có nghĩa là tên của miền địa phương là tên của thư mục con trong /usr/lib/locale/. Thư mục con này lưu trữ các tập tin nhị phân LC_THU THẬP, LC_CTYPE, LC_TIME và như thế. Tài liệu LC_IDENTIFICATION chứa tên chính thức của miền địa phương (có thể khác với tên thư mục) và các nhận xét.

Định dạng hiện đại liên quan đến việc lưu trữ tất cả các ngôn ngữ trong một kho lưu trữ duy nhất / usr / lib / locale / locale-archive, được ánh xạ tới bộ nhớ ảo của tất cả các tiến trình bằng cách sử dụng glibc. Tên ngôn ngữ ở định dạng hiện đại phải tuân theo một số chuẩn hóa - chỉ các số và chữ cái được giảm thành chữ thường vẫn còn trong tên mã hóa. Vì thế ru_RU.KOI8-R, sẽ được lưu dưới dạng ru_RU.koi8r.

Các tập tin đầu vào được tìm kiếm trong thư mục hiện tại, cũng như trong các thư mục /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ cho các tập tin CTT và mã hóa các tập tin tương ứng.

Ví dụ, lệnh

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

sẽ biên dịch tập tin /usr/share/i18n/locales/ru_RU sử dụng tập tin mã hóa /usr/share/i18n/charmaps/MAC-CYRILLIC.gz và lưu kết quả vào / usr / lib / locale / locale-archive dưới tên ru_RU.maccyrillic

Nếu bạn đặt biến LANG = en_US.UTF-8 mà glibc sẽ tìm kiếm các tệp nhị phân miền địa phương theo chuỗi tệp và thư mục sau:

/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/

Nếu một ngôn ngữ xuất hiện ở cả định dạng truyền thống và hiện đại thì ưu tiên cho ngôn ngữ hiện đại.

Bạn có thể xem danh sách các ngôn ngữ được biên dịch bằng lệnh miền địa phương -a.

Chuẩn bị bảng so sánh của bạn

Giờ đây, được trang bị kiến ​​thức, bạn có thể tạo bảng so sánh chuỗi lý tưởng của riêng mình. Bảng này cần so sánh chính xác các chữ cái tiếng Nga, trong đó có chữ Ё, đồng thời tính đến dấu chấm câu theo bảng ASCII.

Quá trình chuẩn bị bảng sắp xếp của riêng bạn bao gồm hai giai đoạn: chỉnh sửa bảng trọng số và biên dịch nó thành dạng nhị phân bằng lệnh localdef.

Để bảng so sánh được điều chỉnh với chi phí chỉnh sửa tối thiểu, ở định dạng ISO 14652 Các phần để điều chỉnh trọng số của một bảng hiện có được cung cấp. Phần này bắt đầu bằng một từ khóa sắp xếp lại sau và chỉ ra vị trí sau đó việc thay thế được thực hiện. Phần kết thúc bằng dòng sắp xếp lại kết thúc. Nếu cần sửa một số phần của bảng thì một phần sẽ được tạo cho mỗi phần đó.

Tôi đã sao chép phiên bản mới của tập tin iso14651_t1_common и ru_ru từ kho lưu trữ glibc vào thư mục chính của tôi ~/.local/share/i18n/locales/ và chỉnh sửa một chút phần này LC_THU THẬP в ru_ru. Các phiên bản mới của tệp hoàn toàn tương thích với phiên bản của tôi glibc. Nếu bạn muốn sử dụng các phiên bản cũ hơn của tệp, bạn sẽ phải thay đổi tên tượng trưng và vị trí bắt đầu thay thế trong bảng.

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

Trên thực tế, cần phải thay đổi các trường trong LC_IDENTIFICATION để họ trỏ đến miền địa phương ru_MY, nhưng trong ví dụ của tôi, điều này không bắt buộc vì tôi đã loại trừ kho lưu trữ khỏi quá trình tìm kiếm ngôn ngữ kho lưu trữ miền địa phương.

Đó localdef đã làm việc với các tập tin trong thư mục của tôi thông qua một biến I18NPATH Bạn có thể thêm một thư mục bổ sung để tìm kiếm các tệp đầu vào và thư mục lưu tệp nhị phân có thể được chỉ định dưới dạng đường dẫn có dấu gạch chéo:

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

POSIX gợi ý rằng trong NGÔN NGỮ bạn có thể ghi đường dẫn tuyệt đối tới các thư mục chứa tệp ngôn ngữ, bắt đầu bằng dấu gạch chéo lên, nhưng glibc в Linux tất cả các đường dẫn được tính từ thư mục cơ sở, có thể được ghi đè thông qua một biến ĐỊA ĐIỂM. Sau khi cài đặt LỘCPATH=~/.local/lib/locale/ tất cả các tệp liên quan đến bản địa hóa sẽ chỉ được tìm kiếm trong thư mục của tôi. Lưu trữ các ngôn ngữ với tập hợp biến ĐỊA ĐIỂM làm ngơ.

Đây là bài kiểm tra quyết định:

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

Hoan hô! Chúng ta làm được rồi!

Một số lỗi

Tôi đã trả lời các câu hỏi về sắp xếp chuỗi được đặt ra ở phần đầu, nhưng vẫn còn một số câu hỏi về lỗi - hiển thị và vô hình.

Hãy quay trở lại vấn đề ban đầu.

Và chương trình loại và chương trình tham gia sử dụng các hàm so sánh chuỗi tương tự từ glibc. Làm sao chuyện đó lại xảy ra được tham gia đưa ra lỗi sắp xếp trên các hàng được sắp xếp theo lệnh loại ở địa phương vi_US.UTF-8? Đáp án đơn giản: loại so sánh toàn bộ chuỗi và tham gia chỉ so sánh khóa, theo mặc định, khóa này là phần đầu của chuỗi với ký tự khoảng trắng đầu tiên. Trong ví dụ của tôi, điều này dẫn đến một thông báo lỗi vì việc sắp xếp các từ đầu tiên trong các dòng không khớp với việc sắp xếp các dòng hoàn chỉnh.

Ngôn ngữ "C" đảm bảo rằng trong các chuỗi đã sắp xếp, các chuỗi con ban đầu cho đến khoảng trắng đầu tiên cũng sẽ được sắp xếp, nhưng điều này chỉ che giấu lỗi. Có thể chọn dữ liệu (những người có cùng họ nhưng khác tên) nếu không có thông báo lỗi sẽ cho kết quả hợp nhất tệp không chính xác. Nếu chúng ta muốn tham gia đã hợp nhất các dòng tệp theo tên đầy đủ, thì cách chính xác sẽ là chỉ định rõ ràng dấu tách trường và sắp xếp theo trường khóa chứ không phải theo toàn bộ dòng. Trong trường hợp này, quá trình hợp nhất sẽ diễn ra chính xác và sẽ không có lỗi ở bất kỳ ngôn ngữ nào:

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

Ví dụ được thực hiện thành công trong mã hóa CP1251 chứa một lỗi khác. Thực tế là trong tất cả các bản phân phối mà tôi biết Linux gói bị thiếu ngôn ngữ biên dịch ru_RU.CP1251. Nếu không tìm thấy ngôn ngữ đã biên dịch thì loại âm thầm sử dụng so sánh từng byte, đó là những gì chúng tôi quan sát được.

Nhân tiện, có một trục trặc nhỏ khác liên quan đến việc không thể truy cập được các ngôn ngữ đã biên dịch. Đội LOCPATH=/tmp miền địa phương -a sẽ đưa ra danh sách tất cả các địa phương trong kho lưu trữ miền địa phương, nhưng với tập biến ĐỊA ĐIỂM cho tất cả các chương trình (bao gồm hầu hết miền địa phương) những ngôn ngữ này sẽ không có sẵn.

$> 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

Kết luận

Nếu bạn là một lập trình viên đã quen với việc nghĩ rằng các chuỗi là một tập hợp byte, thì lựa chọn của bạn là LC_COLLATE=C.

Nếu bạn là một nhà ngôn ngữ học hoặc người biên dịch từ điển thì tốt hơn bạn nên biên dịch bằng ngôn ngữ của mình.

Nếu bạn là người dùng đơn giản thì bạn chỉ cần làm quen với thực tế là lệnh ls -a xuất các tệp bắt đầu bằng dấu chấm trộn lẫn với các tệp bắt đầu bằng một chữ cái và Chỉ huy nửa đêm, sử dụng các hàm nội bộ của nó để sắp xếp tên, đặt các tệp bắt đầu bằng dấu chấm ở đầu danh sách.

tài liệu tham khảo

Báo cáo số 10 Thuật toán đối chiếu Unicode

Trọng lượng ký tự tại unicode.org

ICU — triển khai thư viện để làm việc với Unicode của IBM.

Kiểm tra sắp xếp bằng cách sử dụng ICU

Trọng lượng ký tự trong ISO 14651

Mô tả định dạng tệp có tỷ lệ ISO 14652

Thảo luận về so sánh chuỗi trong glibc

Nguồn: www.habr.com

Thêm một lời nhận xét