Giriş

Her şey adres bilgilerini birleştirmesi gereken kısa bir komut dosyasıyla başladı E-posta İK departmanı veri tabanından elde edilen çalışan pozisyonları ile posta listesi kullanıcıları listesinden elde edilen çalışanlar. Her iki liste de Unicode metin dosyalarına aktarıldı UTF-8 ve Unix satır sonlarıyla kaydedildi.

içindekiler posta.txt

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

içindekiler buhg.txt

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

Birleştirmek için dosyalar Unix komutuna göre sıralandı tür ve Unix programının girdisine gönderildi kaydolbeklenmedik bir şekilde bir hatayla başarısız olan:

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

Sıralama sonucuna gözlerinizle bakıldığında genel olarak sıralamanın doğru olduğu ancak kadın ve erkek soyadlarının çakışması durumunda kadın soyadlarının erkek soyadlarından önce geldiği görüldü:

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

Unicode'daki bir sıralama hatasına veya sıralama algoritmasındaki feminizmin bir tezahürüne benziyor. Elbette ilki daha makul.

Şimdilik bunu erteleyelim kaydol ve odaklan tür. Sorunu bilimsel dürtmeyi kullanarak çözmeye çalışalım. Öncelikle yerel ayarı değiştirelim tr üzerinde ru_ru. Sıralamak için ortam değişkenini ayarlamak yeterli olacaktır. LC_COLLATE, ama önemsiz şeylerle zaman kaybetmeyeceğiz:

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

Hiçbir şey değişmedi.

Dosyaları tek baytlık bir kodlamaya yeniden kodlamayı deneyelim:

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

Yine hiçbir şey değişmedi.

Yapabileceğiniz hiçbir şey yok, internette çözüm aramanız gerekecek. Doğrudan Rus soyadlarıyla ilgili hiçbir şey yok, ancak diğer sıralama tuhaflıkları hakkında sorular var. Örneğin burada bir sorun var: unix sort '-' (tire) karakterlerini görünmez olarak kabul eder. Kısaca "ab", "aa", "ac" dizeleri "aa", "ab", "ac" şeklinde sıralanır.

Cevap her yerde standarttır: programcının yerel ayarını kullanın "C" ve mutlu olacaksın. Hadi deneyelim:

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

Bir şeyler değişti. Yolkina bir yere kaymasına rağmen Ivanov'lar doğru sıraya dizildi. Asıl soruna dönelim:

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

İnternetin vaat ettiği gibi hatasız çalıştı. Ve bu Yolkina'nın ilk sıralarda olmasına rağmen.

Sorun çözülmüş gibi görünüyor, ancak her ihtimale karşı başka bir Rus kodlamasını deneyelim - Windows CP1251:

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

Garip bir şekilde, sıralama sonucu yerel ayarla çakışacak "C"ve buna göre tüm örnek hatasız çalışır. Bir çeşit mistisizm.

Programlamada mistisizmi sevmiyorum çünkü genellikle hataları maskeliyor. Bunun nasıl çalıştığını ciddi olarak araştırmamız gerekecek. tür ve neyi etkiler? LC_COLLATE .

Sonunda şu soruları yanıtlamaya çalışacağım:

kadın soyadları neden yanlış sıralandı?
neden LANG=ru_RU.CP1251 eşdeğer olduğu ortaya çıktı DİL=C
neden tür и kaydol sıralanmış dizelerin sırası hakkında farklı fikirler
neden bütün örneklerimde hatalar var?
nihayet dizeleri beğeninize göre nasıl sıralayabilirsiniz?

Unicode'da sıralama

İlk durak 10 numaralı teknik rapor olacak. Unicode harmanlama algoritması çevrimiçi unicode.org. Rapor çok fazla teknik detay içeriyor, bu yüzden ana fikirlerin kısa bir özetini vermeme izin verin.

Karşılaştırma — Dizeleri “karşılaştırmak” herhangi bir sıralama algoritmasının temelidir. Algoritmaların kendileri farklılık gösterebilir ("balon", "birleştirme", "hızlı"), ancak hepsi göründükleri sırayı belirlemek için bir çift dizenin karşılaştırmasını kullanır.

Dizeleri doğal dilde sıralamak oldukça karmaşık bir sorundur. En basit tek baytlık kodlamalarda bile, alfabedeki harflerin sırası, İngiliz Latin alfabesinden bir şekilde farklı olsa bile, artık bu harflerin kodlandığı sayısal değerlerin sırası ile çakışmayacaktır. Yani Alman alfabesinde harf Ö arasında duruyor О и Pve kodlamada CP850 o araya giriyor ÿ и Ü.

Belirli bir kodlamadan soyutlamayı deneyebilir ve Unicode'da yapıldığı gibi belirli bir sıraya göre düzenlenmiş "ideal" harfleri düşünebilirsiniz. Kodlamalar utf8, utf16 veya bir bayt KOI8-R (Sınırlı bir Unicode alt kümesine ihtiyaç duyulursa) harflerin farklı sayısal temsillerini verecektir, ancak temel tablonun aynı öğelerine atıfta bulunacaktır.

Sıfırdan bir sembol tablosu oluştursak bile ona evrensel bir sembol sırası atayamayacağımız ortaya çıktı. Aynı harfleri kullanan farklı ulusal alfabelerde bu harflerin sırası farklılık gösterebilir. Örneğin, Fransızca'da Æ bir bağ olarak kabul edilecek ve bir dize olarak sıralanacak AE. Norveççe Æ sonra yer alan ayrı bir mektup olacak Z. Bu arada, bitişik harflere ek olarak Æ Çeşitli sembollerle yazılmış harfler vardır. Yani Çek alfabesinde bir harf var Charasında duran H и I.

Alfabelerdeki farklılıklara ek olarak sıralamayı etkileyen başka ulusal gelenekler de vardır. Özellikle şu soru ortaya çıkıyor: Büyük ve küçük harflerden oluşan kelimeler sözlükte hangi sırayla görünmeli? Sıralama noktalama işaretlerinin kullanımından da etkilenebilir. İspanyolca'da soru cümlesinin başında ters soru işareti kullanılır (Müzik sever misin?). Bu durumda soru cümlelerinin alfabenin dışında ayrı bir kümede gruplanmaması gerektiği açıktır ancak diğer noktalama işaretlerinin bulunduğu satırlar nasıl sıralanır?

Avrupa dillerinden çok farklı dillerdeki dizeleri sıralama üzerinde durmayacağım. Sağdan sola veya yukarıdan aşağıya yazma yönüne sahip dillerde, satırlardaki karakterlerin büyük olasılıkla okuma sırasına göre saklandığını ve hatta alfabetik olmayan yazı sistemlerinin bile satırları karakter karakter sıralamak için kendi yöntemleri olduğunu unutmayın. . Örneğin hiyeroglifler stile göre sıralanabilir (Çince karakter tuşları) veya telaffuz yoluyla. Dürüst olmak gerekirse emojilerin nasıl düzenlenmesi gerektiği hakkında hiçbir fikrim yok ama onlar için de bir şeyler bulabilirsiniz.

Yukarıda listelenen özelliklere dayanarak, dizeleri Unicode tablolarına göre karşılaştırmaya yönelik temel gereksinimler formüle edildi:

dize karşılaştırması, kod tablosundaki karakterlerin konumuna bağlı değildir;
Tek bir karakteri oluşturan karakter dizileri kanonik forma indirgenir (A + üst daire şununla aynıdır Å);
Dizeleri karşılaştırırken, bir karakter dize bağlamında dikkate alınır ve gerekirse komşularıyla birlikte tek bir karşılaştırma biriminde birleştirilir (Ch Çekçe) veya birkaç bölüme ayrılmıştır (Æ Fransızcada);
tüm ulusal özellikler (alfabe, büyük/küçük harf, noktalama işaretleri, yazı tipleri sırası), sıranın (emoji) manuel olarak atanmasına kadar yapılandırılmalıdır;
karşılaştırma yalnızca sıralama için değil, aynı zamanda diğer birçok yerde de önemlidir; örneğin satır aralıklarını belirtmek için ({A... z} yerine darbe);
karşılaştırma oldukça hızlı bir şekilde yapılmalıdır.

Ayrıca raporun yazarları, algoritma geliştiricilerin güvenmemesi gereken karşılaştırma özelliklerini formüle etti:

karşılaştırma algoritması, her dil için ayrı bir karakter kümesi gerektirmemelidir (Rusça ve Ukraynaca dilleri Kiril karakterlerinin çoğunu paylaşır);
karşılaştırma Unicode tablolarındaki karakterlerin sırasına bağlı olmamalıdır;
dize ağırlığı dizenin bir özelliği olmamalıdır, çünkü aynı dize farklı kültürel bağlamlarda farklı ağırlıklara sahip olabilir;
satır ağırlıkları birleştirme veya bölme sırasında değişebilir ( x < y bunu takip etmiyor xz < yz);
aynı ağırlığa sahip farklı dizeler, sıralama algoritması açısından eşit kabul edilir. Bu tür dizilerin ek sıralamasının getirilmesi mümkündür, ancak bu, performansı düşürebilir;
Tekrarlanan sıralama sırasında aynı ağırlığa sahip satırlar değiştirilebilir. Sağlamlık, dize karşılaştırma algoritmasının değil, belirli bir sıralama algoritmasının bir özelliğidir (önceki paragrafa bakın);
Sıralama kuralları, kültürel gelenekler geliştikçe/değiştikçe zamanla değişebilir.

Ayrıca karşılaştırma algoritmasının, işlenen dizelerin semantiği hakkında hiçbir şey bilmediği de şart koşulmuştur. Bu nedenle, yalnızca rakamlardan oluşan dizeler sayı olarak karşılaştırılmamalı ve İngilizce ad listelerinde makale (Beatles,).

Belirtilen tüm gereksinimleri karşılamak için çok seviyeli (aslında dört seviyeli) bir tablo sıralama algoritması önerilmektedir.

Önceden, dizedeki karakterler kanonik forma indirgeniyor ve karşılaştırma birimleri halinde gruplandırılıyordu. Her bir karşılaştırma birimine, çeşitli karşılaştırma düzeylerine karşılık gelen çeşitli ağırlıklar atanır. Karşılaştırma birimlerinin ağırlıkları, az ya da çok karşılaştırılabilecek sıralı kümelerin (bu durumda tamsayılar) elemanlarıdır. Özel anlam GÖZDEN GEÇİRİLMİŞ (0x0), karşılık gelen karşılaştırma seviyesinde bu birimin karşılaştırmaya dahil olmadığı anlamına gelir. Dizilerin karşılaştırılması, ilgili seviyelerin ağırlıkları kullanılarak birkaç kez tekrarlanabilir. Her seviyede iki sıranın karşılaştırma birimlerinin ağırlıkları sırayla birbirleriyle karşılaştırılır.

Algoritmanın farklı ulusal gelenekler için farklı uygulamalarında katsayıların değerleri farklı olabilir, ancak Unicode standardı temel bir ağırlık tablosu içerir - "Varsayılan Unicode Harmanlama Öğesi Tablosu" (DUKET). Değişkeni ayarlamanın şunu belirtmek isterim LC_COLLATE aslında string karşılaştırma fonksiyonundaki ağırlık tablosunun seçiminin bir göstergesidir.

Ağırlık katsayıları DUKET şu şekilde düzenlenmiştir:

ilk seviyede, tüm harfler aynı büyük/küçük harfe indirgenir, aksan işaretleri atılır, noktalama işaretleri (hepsi değil) göz ardı edilir;
ikinci düzeyde yalnızca aksan işaretleri dikkate alınır;
üçüncü düzeyde yalnızca durum dikkate alınır;
dördüncü düzeyde yalnızca noktalama işaretleri dikkate alınır.

Karşılaştırma birkaç aşamada gerçekleştirilir: ilk önce birinci düzeyin katsayıları karşılaştırılır; ağırlıkların çakışması durumunda ikinci seviye ağırlıklarla tekrarlı bir karşılaştırma gerçekleştirilir; sonra belki üçüncü ve dördüncü.

Karşılaştırma, satırlar farklı ağırlıklara sahip eşleşen karşılaştırma birimlerini içerdiğinde sona erer. Dört düzeyde de eşit ağırlığa sahip satırlar birbirine eşit kabul edilir.

Bu algoritma (bir dizi ek teknik ayrıntıyla birlikte) 10 numaralı rapora adını verdi - "Unicode Harmanlama Algoritması" (TDM).

Örneğimizdeki sıralama davranışının biraz daha netleştiği yer burasıdır. Unicode standardıyla karşılaştırmak güzel olurdu.

Uygulamaları test etmek TDM özel bir şey var test, kullanarak ağırlıklar dosyası, uygulamak DUKET. Terazi dosyasında her türlü komik şeyi bulabilirsiniz. Örneğin, mahjong ve Avrupa dominolarının sırasının yanı sıra bir kart destesindeki renklerin sırası da vardır (sembol) 1F000 ve ilerisi). Kart takımları briç - PCBT kurallarına göre yerleştirilir ve takımdaki kartlar T, 2,3, XNUMX... K sırasına göre dizilir.

Satırların aşağıdakilere göre doğru şekilde sıralandığının manuel olarak kontrol edilmesi: DUKET oldukça sıkıcı olurdu, ama neyse ki bizim için kütüphanenin Unicode ile çalışmaya yönelik örnek bir uygulaması var - "Unicode İçin Uluslararası Bileşenler"(YBÜ).

Bu kütüphanenin web sitesinde geliştirilen IBM, dahil olmak üzere demo sayfaları var dize karşılaştırma algoritması sayfası. Test satırlarımıza varsayılan ayarlarla giriyoruz ve bir bakıyoruz, mükemmel Rusça sıralama elde ediyoruz.

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

Bu arada, web sitesi YBÜ Noktalama işaretlerini işlerken karşılaştırma algoritmasının açıklamasını bulabilirsiniz. Örneklerde Harmanlama SSS kesme işareti ve kısa çizgi dikkate alınmaz.

Unicode bize yardımcı oldu ancak tuhaf davranışların nedenlerini arayın tür в Linux başka bir yere gitmek zorunda kalacak.

Glibc'de sıralama

Yardımcı program kaynak kodlarına hızlı bakış tür arasında GNU Çekirdek Yardımcı Programları yardımcı programın kendisinde yerelleştirmenin değişkenin mevcut değerini yazdırmaktan ibaret olduğunu gösterdi LC_COLLATE hata ayıklama modunda çalışırken:

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

Dize karşılaştırmaları standart işlev kullanılarak gerçekleştirilir strcolBu, ilginç olan her şeyin kütüphanede olduğu anlamına gelir glibc.

Üzerinde wiki proje glibc dize karşılaştırmasına adanmış bir paragraf. Bu paragraftan anlaşılacağı üzere glibc sıralama bizim zaten bildiğimiz bir algoritmaya dayanmaktadır TDM (Unicode harmanlama algoritması) ve/veya buna yakın bir standartta ISO 14651 (Uluslararası dizi sıralaması ve karşılaştırması). En son standartla ilgili olarak sitede şunu belirtmek gerekir: standartlar.iso.org ISO 14651 resmi olarak kamuya açık olarak ilan edildi, ancak ilgili bağlantı var olmayan bir sayfaya yönlendiriyor. Google, standardın elektronik bir kopyasını yüz avro karşılığında satın almayı teklif eden resmi sitelere bağlantılar içeren birkaç sayfa döndürür, ancak arama sonuçlarının üçüncü veya dördüncü sayfasında ayrıca doğrudan bağlantılar da vardır. PDF. Genel olarak standart pratikte farklı değildir TDMancak dize sıralamanın ulusal özelliklerine ilişkin net örnekler içermediği için okunması daha sıkıcıdır.

Hakkında en ilginç bilgiler wiki bir bağlantı vardı hata izleyici dize karşılaştırmasının uygulanmasına ilişkin bir tartışma ile glibc. Tartışmadan şunu öğrenebiliriz glibc dizeleri karşılaştırmak için kullanılır ISOkişisel masa Ortak Şablon Tablosu (CTT), adresi başvuruda bulunabilir A standart ISO 14651. 2000 ile 2015 yılları arasında bu tablo glibc bir bakıcısı yoktu ve standardın mevcut versiyonundan (en azından harici olarak) oldukça farklıydı. 2015'ten 2018'e kadar tablonun yeni versiyonuna adaptasyon gerçekleşti ve artık gerçek hayatta tablonun yeni versiyonuyla tanışma şansınız var (8 CentOS), Ve yaşlı (7 CentOS).

Artık algoritma ve yardımcı tablolar hakkında tüm bilgilere sahip olduğumuza göre, orijinal soruna dönebilir ve Rus yerel ayarında dizelerin nasıl doğru şekilde sıralanacağını anlayabiliriz.

ISO 14651 / 14652

İlgilendiğimiz tablonun kaynak kodu CTT çoğu dağıtımda Linux katalogda var /usr/share/i18n/locales/. Tablonun kendisi dosyadadır iso14651_t1_common. O zaman bu dosya direktifidir iso14651_t1_common'u kopyala dosyaya dahil iso14651_t1, bu da ulusal dosyalara dahil edilmiştir; tr и ru_ru. Çoğu dağıtımda Linux Tüm kaynak dosyalar temel kuruluma dahildir, ancak mevcut değilse dağıtımdan ek bir paket kurmanız gerekecektir.

Dosya yapısı iso14651_t1 İsim oluşturma konusunda açık olmayan kurallara sahip, son derece ayrıntılı görünebilir, ancak ona bakarsanız her şey oldukça basittir. Yapı standartta açıklanmıştır ISO 14652bir kopyası web sitesinden indirilebilir. open-std.org. Dosya formatının başka bir açıklaması şurada okunabilir: özellikler POSIX itibaren AçıkGrup. Standardı okumaya alternatif olarak fonksiyonun kaynak kodunu inceleyebilirsiniz. harmanla_oku в glibc/locale/programs/ld-collate.c.

Dosya yapısı şöyle görünür:

Varsayılan olarak karakter bir kaçış karakteri olarak kullanılır ve # karakterinden sonraki satırın sonu bir açıklamadır. Tablonun yeni versiyonunda yapılan gibi, her iki sembol de yeniden tanımlanabilir:

escape_char /
comment_char %

Dosya şu formatta belirteçler içerecektir: veya (burada x - onaltılık basamak). Bu, kodlamadaki Unicode kod noktalarının onaltılık gösterimidir. UCS-4 (UTF-32). Köşeli parantez içindeki diğer tüm öğeler (dahil , ve benzerleri) bağlam dışında çok az anlamı olan basit dize sabitleri olarak kabul edilir.

Hat LC_COLLATE bize bundan sonra dizelerin karşılaştırılmasını açıklayan verilerin başladığını söyler.

Öncelikle karşılaştırma tablosundaki ağırlıklar için isimler, sembol kombinasyonları için isimler belirtilir. Genel olarak konuşursak, iki tür ad iki farklı varlığa aittir, ancak gerçek dosyada bunlar karıştırılmıştır. Ağırlıkların adları anahtar kelimeyle belirtilir harmanlama-sembol (karşılaştırma karakteri) çünkü karşılaştırma sırasında aynı ağırlığa sahip Unicode karakterler eşdeğer karakterler olarak kabul edilecektir.

Mevcut dosya revizyonundaki bölümün toplam uzunluğu yaklaşık 900 satırdır. İsimlerin ve çeşitli sözdizimi türlerinin keyfiliğini göstermek için çeşitli yerlerden örnekler aldım.

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

harmanlama sembolü bir dize günlüğe kaydeder OSMANYA terazi adları tablosunda
harmanlama sembolü .. bir önekten oluşan bir ad dizisini kaydeder S ve onaltılık sayısal sonek 1D000 karşı 1D35F.
FFFF в harmanlama sembolü onaltılık sistemde büyük bir işaretsiz tamsayıya benziyor, ancak bu sadece şuna benzeyebilecek bir isim
İsim kodlamadaki kod noktası anlamına gelir UCS-4
harmanlama öğesi itibaren " " bir çift Unicode nokta için yeni bir ad kaydeder.

Ağırlıkların isimleri tanımlandıktan sonra gerçek ağırlıklar belirtilir. Karşılaştırmada yalnızca küçükten büyük ilişkileri önemli olduğundan, ağırlıklar basit bir liste adları dizisiyle belirlenir. Önce “hafif” ağırlıklar, ardından “daha ağır” olanlar listelenir. Her Unicode karaktere dört farklı ağırlığın atandığını hatırlatayım. Burada tek bir sıralı dizi halinde birleştirilirler. Teorik olarak herhangi bir sembolik isim dört seviyeden herhangi birinde kullanılabilir, ancak yorumlar geliştiricilerin isimleri zihinsel olarak seviyelere ayırdığını göstermektedir.

% 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

Son olarak gerçek ağırlık tablosu.

Ağırlıklar bölümü anahtar kelime satırlarının içine alınır sipariş_başlangıcı и sipariş_end. Ekstra seçenekler sipariş_başlangıcı Her karşılaştırma düzeyinde satırların hangi yönde taranacağını belirleyin. Varsayılan ayar: ileri. Bölümün gövdesi sembol kodunu ve onun dört ağırlığını içeren çizgilerden oluşur. Karakter kodu, karakterin kendisi, bir kod noktası veya önceden tanımlanmış bir sembolik ad ile temsil edilebilir. Ağırlıklar ayrıca sembolik adlara, kod noktalarına veya sembollerin kendilerine de verilebilir. Kod noktaları veya karakterler kullanılıyorsa bunların ağırlığı, kod noktasının sayısal değeriyle (Unicode tablosundaki konum) aynıdır. Açıkça belirtilmeyen karakterlerin (anladığım kadarıyla), Unicode tablosundaki konumla eşleşen birincil ağırlığa sahip tabloya atandığı kabul edilir. Özel ağırlık değeri YOKSAY sembolün uygun karşılaştırma düzeyinde göz ardı edildiği anlamına gelir.

Ölçeklerin yapısını göstermek için oldukça belirgin üç parça seçtim:

tamamen göz ardı edilen karakterler
ilk iki seviyedeki üç rakamına eşdeğer semboller
aksan içermeyen ve bu nedenle esas olarak birinci ve üçüncü seviyelere göre sıralanan Kiril alfabesinin başlangıcı.

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

Artık makalenin başından itibaren örnekleri sıralamaya dönebilirsiniz. Pusu ağırlık tablosunun bu bölümünde yatıyor:

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

Bu tabloda tablodan noktalama işaretlerinin olduğu görülmektedir. ASCII (boşluk dahil) dizeleri karşılaştırırken neredeyse her zaman göz ardı edilir. Tek istisna, eşleşen konumlarda bulunan noktalama işaretleri dışında her şeyde eşleşen çizgilerdir. Karşılaştırma algoritması için örneğimdeki satırlar (sıralamadan sonra) şöyle görünür:

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

Ölçek tablosunda Rusçada büyük harflerin küçük harflerden sonra geldiği dikkate alındığında (üçüncü düzeyde) daha ağır ), sıralama kesinlikle doğru görünüyor.

Bir değişken ayarlarken LC_COLLATE=C bayt bayt karşılaştırmasını belirten özel bir tablo yüklenir

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

Unicode'da Ё kod noktası A'dan önce geldiğinden, dizeler buna göre sıralanır.

Metin ve ikili tablolar

Açıkçası, dize karşılaştırması son derece yaygın bir işlemdir ve tablo ayrıştırma CTT oldukça maliyetli bir prosedür. Tabloya erişimi optimize etmek için komutla ikili biçimde derlenir yereldef.

Ekip yereldef ulusal özellikler tablosunu içeren bir dosyayı parametre olarak kabul eder (seçenek -i), tüm karakterlerin Unicode noktalarıyla temsil edildiği ve Unicode noktaları ile belirli bir kodlamanın karakterleri arasında bir yazışma dosyası (seçenek) -f). Çalışma sonucunda locale ait son parametrede belirtilen isimle ikili dosyalar oluşturulur.

glibc iki ikili dosya formatını destekler: "geleneksel" ve "modern".

Geleneksel biçim, yerel ayarın adının içindeki alt dizinin adı olduğu anlamına gelir. /usr/lib/yerel/. Bu alt dizin ikili dosyaları saklar LC_COLLATE, LC_CTYPE, LC_TIME ve benzeri. Dosya LC_TANIMLAMA yerel ayarın resmi adını (dizin adından farklı olabilir) ve açıklamaları içerir.

Modern format, tüm yerel ayarların tek bir arşivde saklanmasını içerir /usr/lib/locale/yerel-arşivkullanılarak tüm işlemlerin sanal belleğine eşlenir. glibc. Modern formattaki yerel ayar adı bazı kurallara tabidir; kodlama adlarında yalnızca küçük harflere indirgenmiş sayılar ve harfler kalır. Bu yüzden ru_RU.KOI8-Rolarak kaydedilecek ru_RU.koi8r.

Giriş dosyaları hem geçerli dizinde hem de dizinlerde aranır /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ dosyalar için CTT ve sırasıyla dosyaları kodlama.

Örneğin, komut

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

dosyayı derleyecek /usr/share/i18n/locales/ru_RU kodlama dosyasını kullanma /usr/share/i18n/charmaps/MAC-CYRILLIC.gz ve sonucu kaydedin /usr/lib/locale/yerel-arşiv adı altında ru_RU.maccyrillic

Değişkeni ayarlarsanız LANG = en_US.UTF-8 o glibc yerel ayar ikili dosyalarını aşağıdaki dosya ve dizin dizisinde arayacaktır:

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

Bir yerel ayar hem geleneksel hem de modern formatta bulunuyorsa öncelik modern olana verilir.

Komutla derlenmiş yerel ayarların listesini görüntüleyebilirsiniz. locale -a.

Karşılaştırma tablonuzun hazırlanması

Artık bilgiyle donanmış olarak kendi ideal dizi karşılaştırma tablonuzu oluşturabilirsiniz. Bu tablo, Ё harfi de dahil olmak üzere Rusça harfleri doğru bir şekilde karşılaştırmalı ve aynı zamanda tabloya uygun olarak noktalama işaretlerini de dikkate almalıdır. ASCII.

Kendi sıralama tablonuzu hazırlama süreci iki aşamadan oluşur: ağırlık tablosunun düzenlenmesi ve komutla ikili forma derlenmesi yereldef.

Karşılaştırma tablosunun minimum düzenleme maliyetiyle uyarlanabilmesi için aşağıdaki formatta ISO 14652 Mevcut bir tablonun ağırlıklarının ayarlanmasına yönelik bölümler sağlanmıştır. Bölüm bir anahtar kelimeyle başlıyor sonra yeniden sipariş ver ve değiştirmenin gerçekleştirileceği konumun belirtilmesi. Bölüm şu satırla bitiyor yeniden sıralama sonu. Tablonun birkaç bölümünü düzeltmek gerekiyorsa, bu bölümlerin her biri için bir bölüm oluşturulur.

Dosyaların yeni versiyonlarını kopyaladım iso14651_t1_common и ru_ru depodan glibc ~/.local/share/i18n/locales/ ana dizinime götürdüm ve bölümü biraz düzenledim LC_COLLATE в ru_ru. Dosyaların yeni sürümleri benim sürümümle tamamen uyumlu glibc. Dosyaların eski sürümlerini kullanmak istiyorsanız sembolik adları ve tabloda değiştirme işleminin başlayacağı yeri değiştirmeniz gerekecektir.

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

Aslında alanları değiştirmek gerekecekti. LC_TANIMLAMA böylece yerel ayarı işaret ederler ru_MY, ancak benim örneğimde arşivi yerel ayar aramasının dışında bıraktığım için bu gerekli değildi yerel arşiv.

O yereldef bir değişken aracılığıyla klasörümdeki dosyalarla çalıştım I18NPATH Giriş dosyalarını aramak için ek bir dizin ekleyebilirsiniz ve ikili dosyaların kaydedileceği dizin, eğik çizgi içeren bir yol olarak belirtilebilir:

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

POSIX içinde olduğunu varsayar DİL yerel ayar dosyalarının bulunduğu dizinlere eğik çizgiyle başlayarak mutlak yollar yazabilirsiniz, ancak glibc в Linux tüm yollar, bir değişken aracılığıyla geçersiz kılınabilen temel dizinden sayılır LOCPATH. Yüklemeden sonra LOCPATH=~/.local/lib/locale/ yerelleştirmeyle ilgili tüm dosyalar yalnızca benim klasörümde aranacak. Değişken seti ile yerel ayarların arşivi LOCPATH görmezden gelindi.

İşte belirleyici test:

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

Yaşasın! Yaptık!

Bazı hatalar

Başlangıçta dize sıralamayla ilgili sorulan soruları zaten yanıtladım, ancak hala görünen ve görünmeyen hatalarla ilgili birkaç soru var.

Asıl soruna dönelim.

Ve program tür ve program kaydol aynı dize karşılaştırma işlevlerini kullanın glibc. Bu nasıl oldu kaydol komuta göre sıralanan satırlarda sıralama hatası verdi tür yerel ayarda tr_US.UTF-8? Cevap basit: tür dizenin tamamını karşılaştırır ve kaydol yalnızca varsayılan olarak dizenin başlangıcı olan ve ilk boşluk karakterine kadar olan anahtarı karşılaştırır. Örneğimde bu bir hata mesajıyla sonuçlandı çünkü satırlardaki ilk kelimelerin sıralaması tüm satırların sıralamasıyla eşleşmedi.

Yerel ayar "C" sıralanmış dizelerde ilk boşluğa kadar olan ilk alt dizelerin de sıralanacağını garanti eder, ancak bu yalnızca hatayı maskeler. Hata mesajı olmadan yanlış dosya birleştirme sonucu verecek verileri (aynı soyadlarına ancak farklı adlara sahip kişiler) seçmek mümkündür. Eğer istersek kaydol Dosya satırlarını tam isme göre birleştiriyorsanız doğru yol, alan ayırıcıyı açıkça belirtmek ve satırın tamamına göre değil, anahtar alana göre sıralamak olacaktır. Bu durumda birleştirme doğru şekilde ilerleyecek ve hiçbir yerel ayarda hata olmayacaktır:

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

Kodlamada başarıyla yürütülen örnek CP1251 başka bir hata içeriyor. Gerçek şu ki, bildiğim tüm dağıtımlarda Linux paketlerde derlenmiş yerel ayar eksik ru_RU.CP1251. Derlenmiş yerel ayar bulunamazsa, o zaman tür sessizce bayt bayt karşılaştırması kullanıyor, biz de bunu gözlemledik.

Bu arada, derlenmiş yerel ayarlara erişilememesiyle ilgili küçük bir aksaklık daha var. Takım LOCPATH=/tmp yerel ayar -a içindeki tüm yerel ayarların bir listesini verecektir yerel arşiv, ancak değişken kümesiyle LOCPATH tüm programlar için (en çok yerel) bu yerel ayarlar kullanılamayacak.

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

Sonuç

Dizelerin bir bayt kümesi olduğunu düşünmeye alışkın bir programcıysanız, o zaman seçiminiz LC_COLLATE=C.

Eğer bir dilbilimci veya sözlük derleyicisiyseniz, kendi yerel ayarınızda derleme yapsanız iyi olur.

Basit bir kullanıcıysanız, komutun olduğu gerçeğine alışmanız yeterlidir. ls bir harfle başlayan dosyalarla karıştırılmış bir noktayla başlayan dosyaların çıktısını alır ve Gece yarısı komutanıAdları sıralamak için dahili işlevlerini kullanan, nokta ile başlayan dosyaları listenin başına koyar.