Esittely

Kaikki alkoi lyhyellä skriptillä, jonka piti yhdistää osoitetiedot sähköposti postituslistan käyttäjien listalta saadut työntekijät, henkilöstöosaston tietokannasta saadut työntekijäpaikat. Molemmat luettelot vietiin Unicode-tekstitiedostoihin UTF-8 ja tallennettu Unix-rivinpäätteillä.

Sisältö mail.txt

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

Sisältö buhg.txt

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

Yhdistämistä varten tiedostot lajiteltiin Unix-komennolla lajitella ja lähetetty Unix-ohjelman syötteeseen yhdistää, joka epäonnistui odottamatta virheen vuoksi:

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

Lajittelutuloksen silmällä katsominen osoitti, että lajittelu on pääsääntöisesti oikea, mutta miesten ja naisten sukunimien yhteensattumissa naispuoliset tulevat miesten edelle:

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

Näyttää lajitteluhäiriöltä Unicodessa tai feminismin ilmentymiseltä lajittelualgoritmissa. Ensimmäinen on tietysti uskottavampi.

Siirretään se toistaiseksi yhdistää ja keskittyä lajitella. Yritetään ratkaista ongelma tieteellisellä näkemisellä. Vaihdetaan ensin kielialue fi päälle ru_ru. Lajitteluun riittäisi ympäristömuuttujan asettaminen LC_COLLATE, mutta emme tuhlaa aikaa pikkuasioihin:

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

Mikään ei muuttunut.

Yritetään koodata tiedostot uudelleen yksitavuiseksi koodaukseksi:

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

Mikään ei ole taaskaan muuttunut.

Et voi tehdä mitään, sinun on etsittävä ratkaisua Internetistä. Venäläisistä sukunimistä ei suoraan puhuta, mutta muista lajittelun oudoista on kysymyksiä. Esimerkiksi tässä on ongelma: unix sort käsittelee "-" (viiva) -merkkejä näkymättöminä. Lyhyesti sanottuna merkkijonot "a-b", "aa", "ac" on lajiteltu "aa", "a-b", "ac".

Vastaus on vakio kaikkialla: käytä ohjelmoijan aluetta "C" ja tulet olemaan onnellinen. Kokeillaan:

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

Jokin on muuttunut. Ivanovit asettuivat riviin oikeassa järjestyksessä, vaikka Yolkina lipsahti jonnekin. Palataan alkuperäiseen ongelmaan:

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

Se toimi ilman virheitä, kuten Internet lupasi. Ja tämä huolimatta Yolkinasta ensimmäisessä rivissä.

Ongelma näyttää olevan ratkaistu, mutta varmuuden vuoksi kokeillaan toista venäläistä koodausta - Windowsia CP1251:

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

Lajittelutulos on kummallista kyllä, sama kuin maa-asetus "C", ja vastaavasti koko esimerkki toimii ilman virheitä. Jonkinlaista mystiikkaa.

En pidä ohjelmoinnin mystiikasta, koska se yleensä peittää virheet. Meidän on tutkittava vakavasti, miten se toimii. lajitella ja mihin se vaikuttaa? LC_COLLATE .

Lopuksi yritän vastata kysymyksiin:

Miksi naisten sukunimet lajiteltiin väärin?
miksi LANG=ru_RU.CP1251 osoittautui vastaavaksi LANG=C
miksi tehdä lajitella и yhdistää erilaisia ideoita lajiteltujen merkkijonojen järjestyksestä
miksi kaikissa esimerkeissäni on virheitä?
vihdoin kuinka lajitella merkkijonot mielesi mukaan

Lajittelu Unicodessa

Ensimmäinen pysähdyspaikka on tekninen raportti nro 10 nimeltään Unicode-lajittelualgoritmi verkossa unicode.org. Raportti sisältää paljon teknisiä yksityiskohtia, joten haluan esittää lyhyen yhteenvedon tärkeimmistä ajatuksista.

Kevyt ateria — merkkijonojen "vertailu" on minkä tahansa lajittelualgoritmin perusta. Algoritmit itsessään voivat erota toisistaan ("kupla", "yhdistä", "nopea"), mutta ne kaikki käyttävät merkkijonoparin vertailua määrittääkseen järjestyksen, jossa ne esiintyvät.

Merkkijonojen lajittelu luonnollisella kielellä on melko monimutkainen ongelma. Jopa yksinkertaisimmissa yksitavuisissa koodauksissa aakkosten kirjainten järjestys, jopa jollain tavalla poikkeava englannin latinalaisista aakkosista, ei enää vastaa numeroarvojen järjestystä, jolla nämä kirjaimet on koodattu. Joten saksan aakkosissa kirjain Ö seisoo välissä О и P, ja koodauksessa CP850 hän pääsee väliin ÿ и Ü.

Voit yrittää irrottaa tietystä koodauksesta ja harkita "ihanteellisia" kirjaimia, jotka on järjestetty johonkin järjestykseen, kuten Unicodessa tehdään. Koodaukset UTF8, UTF16 tai yksitavuinen KOI8-R (jos tarvitaan rajoitettu Unicode-osajoukko) antaa kirjaimille erilaisia numeerisia esityksiä, mutta viittaa samoihin perustaulukon elementteihin.

Osoittautuu, että vaikka rakentaisimme symbolitaulukon tyhjästä, emme voi määrittää sille universaalia symbolijärjestystä. Eri kansallisissa aakkosissa, joissa käytetään samoja kirjaimia, näiden kirjainten järjestys voi vaihdella. Esimerkiksi ranskaksi Æ pidetään ligatuurina ja lajitellaan merkkijonona AE. norjaksi Æ on erillinen kirje, joka sijaitsee jälkeen Z. Muuten, lisäksi ligatuureja kuten Æ Kirjaimia on kirjoitettu useilla symboleilla. Joten tšekin aakkosissa on kirjain Ch, joka on välissä H и I.

Aakkosten erojen lisäksi lajitteluun vaikuttavat muutkin kansalliset perinteet. Erityisesti herää kysymys: missä järjestyksessä isoista ja pienistä kirjaimista koostuvat sanat tulee esiintyä sanakirjassa? Myös välimerkkien käyttö voi vaikuttaa lajitteluun. Espanjan kielessä käänteistä kysymysmerkkiä käytetään kyselylauseen alussa (Pidätkö sinä musiikista?). Tässä tapauksessa on selvää, että kyselylauseita ei pidä ryhmitellä erilliseen klusteriin aakkosten ulkopuolella, mutta kuinka lajitella rivit muiden välimerkkien kanssa?

En aio jäädä lajittelemaan merkkijonoja kielillä, jotka poikkeavat suuresti eurooppalaisista. Huomaa, että kielissä, joissa kirjoitussuunta on oikealta vasemmalle tai ylhäältä alas, rivien merkit tallennetaan todennäköisimmin lukujärjestyksessä, ja jopa ei-aakkoskirjoitusjärjestelmillä on omat tapansa järjestää rivit merkki merkiltä. . Esimerkiksi hieroglyfit voidaan järjestää tyylin mukaan (Kiinan merkkien näppäimet) tai ääntämisellä. Ollakseni rehellinen, minulla ei ole aavistustakaan kuinka emojit pitäisi järjestää, mutta voit myös keksiä jotain niille.

Yllä lueteltujen ominaisuuksien perusteella muotoiltiin Unicode-taulukoihin perustuvien merkkijonojen vertailun perusvaatimukset:

merkkijonojen vertailu ei riipu merkkien sijainnista kooditaulukossa;
yhden merkin muodostavat merkkisarjat pelkistetään kanoniseen muotoon (A + yläympyrä on sama kuin Å);
Merkkijonoja verrattaessa merkki otetaan huomioon merkkijonon kontekstissa ja tarvittaessa yhdistetään sen naapureihin yhdeksi vertailuyksiköksi (Ch tšekin kielellä) tai on jaettu useisiin (Æ ranskaksi);
kaikki kansalliset ominaisuudet (aakkoset, isot/pienet kirjaimet, välimerkit, kirjoitustyyppien järjestys) on määritettävä järjestyksen manuaaliseen määritykseen (emoji) asti;
vertailu on tärkeä paitsi lajittelun kannalta, myös monissa muissa paikoissa, esimerkiksi rivivälien määrittämisessä (korvaa {A... z} kemut);
vertailu pitäisi tehdä melko nopeasti.

Lisäksi raportin laatijat muotoilivat vertailuominaisuudet, joihin algoritmien kehittäjien ei pitäisi luottaa:

vertailualgoritmin ei pitäisi vaatia erillistä merkkijoukkoa jokaiselle kielelle (venäjän ja ukrainan kielet jakavat useimmat kyrilliset merkit);
vertailun ei pitäisi perustua Unicode-taulukoiden merkkijärjestykseen;
merkkijonon paino ei saa olla merkkijonon attribuutti, koska samalla merkkijonolla eri kulttuurikonteksteissa voi olla eri painot;
rivien painot voivat muuttua yhdistettäessä tai jaettaessa (alkaen x < y se ei seuraa sitä xz < yz);
eri merkkijonoja, joilla on sama paino, pidetään samanlaisina lajittelualgoritmin kannalta. Tällaisten merkkijonojen lisäjärjestäminen on mahdollista, mutta se voi heikentää suorituskykyä;
Toistuvan lajittelun aikana voidaan vaihtaa samanpainoisia rivejä. Robustiteetti on tietyn lajittelualgoritmin ominaisuus, ei merkkijonojen vertailualgoritmin ominaisuus (katso edellinen kappale);
Lajittelusäännöt voivat muuttua ajan myötä, kun kulttuuriperinteet tarkentuvat/muuttuvat.

On myös määrätty, että vertailualgoritmi ei tiedä mitään käsiteltävien merkkijonojen semantiikasta. Siksi vain numeroista koostuvia merkkijonoja ei pidä verrata numeroiksi, ja englanninkielisissä nimiluetteloissa artikkeli (Beatles, The).

Kaikkien määriteltyjen vaatimusten täyttämiseksi ehdotetaan monitasoista (itse asiassa nelitasoista) taulukoiden lajittelualgoritmia.

Aiemmin merkkijonon merkit on pelkistetty kanoniseen muotoon ja ryhmitelty vertailuyksiköiksi. Jokaiselle vertailuyksikölle on määritetty useita painotuksia, jotka vastaavat useita vertailutasoja. Vertailuyksiköiden painot ovat järjestettyjen joukkojen elementtejä (tässä tapauksessa kokonaislukuja), joita voidaan verrata enemmän tai vähemmän. Erityinen merkitys OHITETTU (0x0) tarkoittaa, että vastaavalla vertailutasolla tämä yksikkö ei ole mukana vertailussa. Merkkijonojen vertailu voidaan toistaa useita kertoja käyttämällä vastaavien tasojen painoja. Jokaisella tasolla kahden rivin vertailuyksiköiden painoja verrataan peräkkäin toisiinsa.

Algoritmin eri toteutuksissa eri kansallisille perinteille kertoimien arvot voivat vaihdella, mutta Unicode-standardi sisältää peruspainotaulukon - "Unicode-lajitteluelementtien oletustaulukko" (DUCET). Haluaisin huomauttaa, että muuttujan asettaminen LC_COLLATE on itse asiassa osoitus painotaulukon valinnasta merkkijonojen vertailufunktiossa.

Painotuskertoimet DUCET järjestetty seuraavasti:

ensimmäisellä tasolla kaikki kirjaimet pelkistetään samaan kirjainkokoon, diakriittiset merkit hylätään, välimerkit (ei kaikki) jätetään huomiotta;
toisella tasolla vain diakriittiset sanat otetaan huomioon;
kolmannella tasolla vain tapaus otetaan huomioon;
neljännellä tasolla vain välimerkit otetaan huomioon.

Vertailu tapahtuu useissa ajoissa: ensin verrataan ensimmäisen tason kertoimia; jos painot ovat samat, suoritetaan toistuva vertailu toisen tason painoihin; sitten ehkä kolmas ja neljäs.

Vertailu päättyy, kun rivit sisältävät vastaavia vertailuyksiköitä eri painoilla. Rivejä, joilla on sama paino kaikilla neljällä tasolla, pidetään toistensa samanarvoisina.

Tämä algoritmi (jossa on joukko muita teknisiä yksityiskohtia) antoi nimen raportille nro 10 - "Unicode-lajittelualgoritmi" (ACU).

Tässä esimerkkimme lajittelukäyttäytyminen tulee hieman selvemmäksi. Olisi mukava verrata sitä Unicode-standardiin.

Testaa toteutuksia ACU on erikoista тест, käyttämällä painotiedostot, toteuttaminen DUCET. Vaakatiedostosta löytyy kaikenlaisia hauskoja juttuja. Esimerkiksi mahjongin ja eurooppalaisen dominon järjestys sekä korttipakan maakuntien järjestys (symboli 1F000 ja kauemmas). Kortin maat asetetaan sillan - PCBT:n sääntöjen mukaan, ja puvun kortit ovat järjestyksessä T, 2,3, XNUMX... K.

Tarkistamalla manuaalisesti, että rivit on lajiteltu oikein DUCET olisi melko tylsää, mutta onneksi meillä on kirjaston esimerkillinen toteutus Unicoden kanssa työskennellä - "Kansainväliset komponentit Unicodelle"(ICU).

Tämän kirjaston verkkosivustolla, joka on kehitetty vuonna IBM, on esittelysivuja, mukaan lukien merkkijonojen vertailualgoritmisivu. Menemme testilinjoillemme oletusasetuksilla ja katso, saamme täydellisen venäläisen lajittelun.

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

Muuten, verkkosivusto ICU Vertailualgoritmista löytyy selvennystä välimerkkejä käsiteltäessä. Esimerkeissä Lajittelun UKK heittomerkki ja yhdysmerkki jätetään huomiotta.

Unicode auttoi meitä, mutta etsi syitä oudolle käytökselle lajitella в Linux täytyy mennä jonnekin muualle.

Lajittelu glibc:ssä

Pikanäkymä apuohjelman lähdekoodeista lajitella ja GNU Core Utils osoitti, että itse apuohjelmassa lokalisointi laskee muuttujan nykyisen arvon tulostamiseen LC_COLLATE kun suoritetaan virheenkorjaustilassa:

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

Merkkijonovertailu suoritetaan vakiofunktiolla strcoll, mikä tarkoittaa, että kaikki kiinnostava on kirjastossa glibc.

Päälle wiki projekti glibc omistettu merkkijonojen vertailulle yksi kappale. Tästä kappaleesta voidaan ymmärtää, että in glibc lajittelu perustuu jo tuntemamme algoritmiin ACU (Unicode-lajittelualgoritmi) ja/tai sitä lähellä olevalla standardilla ISO 14651 (Kansainvälinen merkkijonojen järjestys ja vertailu). Mitä tulee uusimpaan standardiin, on huomattava, että sivustolla standards.iso.org ISO 14651 virallisesti julistettu julkisesti saataville, mutta vastaava linkki johtaa olemattomalle sivulle. Google palauttaa useita sivuja, joilla on linkkejä virallisille sivustoille, jotka tarjoavat ostettua standardin sähköisen kopion sadalla eurolla, mutta hakutulosten kolmannella tai neljännellä sivulla on myös suoria linkkejä PDF. Yleensä standardi ei käytännössä eroa ACU, mutta on tylsempää lukea, koska se ei sisällä selkeitä esimerkkejä merkkijonojen lajittelun kansallisista piirteistä.

Mielenkiintoisinta tietoa aiheesta wiki siellä oli linkki bugien seuranta keskustelun merkkijonovertailun käyttöönotosta glibc. Keskustelusta sen voi oppia glibc käytetään merkkijonojen vertailuun ISOhenkilökohtainen pöytä Yhteinen mallitaulukko (CTT), jonka osoite löytyy hakemuksesta A standardi ISO 14651. Vuosina 2000-2015 tämä taulukko sisään glibc sillä ei ollut ylläpitäjää ja se oli melko erilainen (ainakin ulkoisesti) standardin nykyisestä versiosta. Vuodesta 2015 vuoteen 2018 sopeutuminen pöydän uuteen versioon tapahtui, ja nyt sinulla on mahdollisuus tavata tosielämässä uusi versio taulukosta (8 CentOS), ja vanha (7 CentOS).

Nyt kun meillä on kaikki tiedot algoritmista ja aputaulukoista, voimme palata alkuperäiseen ongelmaan ja ymmärtää, kuinka merkkijonot lajitellaan oikein venäjän kielellä.

ISO 14651 / 14652

Meitä kiinnostavan taulukon lähdekoodi CTT useimmissa jakeluissa Linux on hakemistossa /usr/share/i18n/locales/. Itse taulukko on tiedostossa iso14651_t1_common. Sitten tämä on tiedostodirektiivi kopioi iso14651_t1_common sisältyvät tiedostoon iso14651_t1, joka puolestaan sisältyy kansallisiin tiedostoihin, mukaan lukien fi и ru_ru. Useimmissa jakeluissa Linux kaikki lähdetiedostot sisältyvät perusasennukseen, mutta jos niitä ei ole, sinun on asennettava lisäpaketti jakelusta.

Tiedoston rakenne iso14651_t1 saattaa tuntua hirveän monisanaiselta, ja nimien rakentamiseen on epäselviä sääntöjä, mutta jos katsot sitä, kaikki on melko yksinkertaista. Rakenne on kuvattu standardissa ISO 14652, jonka kopion voi ladata verkkosivustolta open-std.org. Toinen tiedostomuodon kuvaus voidaan lukea tekniset tiedot POSIX alkaen OpenGroup. Vaihtoehtona standardin lukemiselle voit tutkia funktion lähdekoodia lajitella_luettu в glibc/locale/programs/ld-collate.c.

Tiedoston rakenne näyttää tältä:

Oletuksena merkkiä käytetään pakomerkkinä, ja rivin loppu #-merkin jälkeen on kommentti. Molemmat symbolit voidaan määritellä uudelleen, mikä on tehty taulukon uudessa versiossa:

escape_char /
comment_char %

Tiedosto sisältää tunnisteita muodossa tai (Missä x - heksadesimaaliluku). Tämä on koodauksen Unicode-koodipisteiden heksadesimaaliesitys UCS-4 (UTF-32). Kaikki muut elementit kulmasuluissa (mukaan lukien , ja vastaavat) pidetään yksinkertaisina merkkijonovakioksi, joilla on vain vähän merkitystä kontekstin ulkopuolella.

Linja LC_COLLATE kertoo, että seuraavaksi alkaa merkkijonojen vertailua kuvaava data.

Ensin määritellään nimet vertailutaulukon painoille ja nimet symboliyhdistelmille. Yleisesti ottaen nämä kaksi nimetyyppiä kuuluvat kahdelle eri entiteetille, mutta varsinaisessa tiedostossa ne ovat sekoittuneet. Painojen nimet määritellään avainsanalla yhdistävä symboli (vertailumerkki), koska vertailussa Unicode-merkkejä, joilla on sama paino, pidetään vastaavina merkeinä.

Osion kokonaispituus nykyisessä tiedostoversiossa on noin 900 riviä. Hain esimerkkejä useista paikoista osoittamaan nimien mielivaltaisuutta ja erityyppisiä syntaksia.

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

lajittelusymboli kirjaa merkkijonon OSMANYA asteikkojen nimien taulukossa
lajittelusymboli .. rekisteröi etuliitteestä koostuvan nimisarjan S ja heksadesimaalinen numeerinen pääte 1D000 до 1D35F.
FFFF в lajittelusymboli näyttää suurelta etumerkitttömältä kokonaisluvulta heksadesimaalimuodossa, mutta se on vain nimi, joka saattaa näyttää
Nimi tarkoittaa koodipistettä koodauksessa UCS-4
lajitteluelementti kohteesta rekisteröi uuden nimen Unicode-pisteparille.

Kun painojen nimet on määritetty, todelliset painot määritetään. Koska vain suurempi kuin vähemmän -relaatioilla on merkitystä vertailussa, painot määritetään yksinkertaisella listausnimisarjalla. "Kevyemmät" painot luetellaan ensin, sitten "raskavammat". Haluan muistuttaa, että jokaiselle Unicode-merkille on määritetty neljä eri painoarvoa. Tässä ne yhdistetään yhdeksi järjestetyksi sarjaksi. Teoriassa mitä tahansa symbolista nimeä voitaisiin käyttää millä tahansa neljästä tasosta, mutta kommentit osoittavat, että kehittäjät jakavat nimet henkisesti tasoiksi.

% 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

Lopuksi todellinen painotaulukko.

Painot-osio on avainsanarivien sisällä tilaus_aloitus и tilaus_loppu. Lisävaihtoehdot tilaus_aloitus määrittää, mihin suuntaan rivit skannataan kullakin vertailutasolla. Oletusasetus on eteenpäin. Osion runko koostuu riveistä, jotka sisältävät symbolikoodin ja sen neljä painoarvoa. Merkkikoodi voidaan esittää itse merkillä, koodipisteellä tai aiemmin määritellyllä symbolisella nimellä. Painoja voidaan antaa myös symbolisille nimille, koodipisteille tai itse symboleille. Jos käytetään koodipisteitä tai merkkejä, niiden paino on sama kuin koodipisteen numeerinen arvo (sijainti Unicode-taulukossa). Merkkejä, joita ei ole määritelty nimenomaisesti (kuten ymmärrän), katsotaan olevan taulukossa määritetty ensisijaisella painolla, joka vastaa sijaintia Unicode-taulukossa. Erityinen painoarvo sivuuttaa tarkoittaa, että symboli jätetään huomioimatta sopivalla vertailutasolla.

Asteikkojen rakenteen havainnollistamiseksi valitsin kolme melko ilmeistä fragmenttia:

hahmoja, jotka jätetään kokonaan huomiotta
symbolit, jotka vastaavat numeroa kolme kahdella ensimmäisellä tasolla
kyrillisten aakkosten alku, joka ei sisällä diakriittisiä merkkejä ja on siksi lajiteltu pääasiassa ensimmäisen ja kolmannen tason mukaan.

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

Nyt voit palata esimerkkien lajitteluun artikkelin alusta. Väijytys on tässä painotaulukon osassa:

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

Voidaan nähdä, että tässä taulukossa välimerkit taulukosta ASCII (mukaan lukien välilyönti) jätetään melkein aina huomioimatta merkkijonoja verrattaessa. Ainoat poikkeukset ovat rivit, jotka täsmäävät kaikessa paitsi vastaavissa paikoissa löydetyt välimerkit. Esimerkkini rivit (lajittelun jälkeen) vertailualgoritmia varten näyttävät tältä:

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

Ottaen huomioon, että asteikkotaulukossa venäjän isot kirjaimet tulevat pienten kirjainten jälkeen (kolmannella tasolla painavampi kuin ), lajittelu näyttää täysin oikealta.

Kun asetat muuttujan LC_COLLATE=C ladataan erityinen taulukko, joka määrittää tavukohtaisen vertailun

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

Koska Unicodessa koodipiste Ё tulee ennen A:ta, merkkijonot lajitellaan sen mukaan.

Teksti- ja binääritaulukot

Ilmeisesti merkkijonojen vertailu on erittäin yleinen operaatio ja taulukon jäsentäminen CTT melko kallis menettely. Taulukon käytön optimoimiseksi se käännetään binäärimuotoon komennolla localdef.

Joukkue localdef hyväksyy parametreiksi tiedoston, jossa on kansallisten ominaisuuksien taulukko (valinnainen -i), jossa kaikki merkit esitetään Unicode-pisteillä, ja tiedosto, joka vastaa Unicode-pisteiden ja tietyn koodauksen merkkejä (valinnainen -f). Työn tuloksena lokaalille luodaan binääritiedostot viimeisessä parametrissa määritetyllä nimellä.

glibc tukee kahta binaaritiedostomuotoa: "perinteinen" ja "moderni".

Perinteinen muoto tarkoittaa, että alueen nimi on alihakemiston nimi /usr/lib/locale/. Tämä alihakemisto tallentaa binääritiedostoja LC_COLLATE, LC_CTYPE, LC_TIME ja niin edelleen. Tiedosto LC_IDENTIFICATION sisältää alueen virallisen nimen (joka voi poiketa hakemiston nimestä) ja kommentteja.

Nykyaikainen muoto sisältää kaikkien alueiden tallentamisen yhteen arkistoon /usr/lib/locale/locale-archive, joka on kartoitettu kaikkien käyttävien prosessien virtuaalimuistiin glibc. Nykyaikaisessa muodossa oleva maa-alueen nimi on jonkin verran kanonisoitunut - vain numerot ja kirjaimet, jotka on pienennetty pieniksi, jäävät koodauksen nimiin. Niin ru_RU.KOI8-R, tallennetaan nimellä ru_RU.koi8r.

Syöttötiedostoja etsitään nykyisestä hakemistosta sekä hakemistoista /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ tiedostoille CTT ja koodaustiedostot, vastaavasti.

Esimerkiksi komento

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

kokoaa tiedoston /usr/share/i18n/locales/ru_RU käyttämällä koodaustiedostoa /usr/share/i18n/charmaps/MAC-CYRILLIC.gz ja tallenna tulos /usr/lib/locale/locale-archive nimellä ru_RU.maccyrillic

Jos asetat muuttujan LANG = en_US.UTF-8 то glibc etsii alue-binaaritiedostoja seuraavasta tiedosto- ja hakemistosarjasta:

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

Jos kielialue esiintyy sekä perinteisessä että modernissa muodossa, etusija annetaan nykyaikaiselle.

Voit tarkastella koottujen kieliasetusten luetteloa komennolla locale -a.

Vertailutaulukon valmistelu

Nyt tiedolla varustettuna voit luoda oman ihanteellisen merkkijonovertailutaulukon. Tässä taulukossa tulee oikein verrata venäläisiä kirjaimia, mukaan lukien kirjain Ё, ja samalla ottaa huomioon välimerkit taulukon mukaisesti ASCII.

Oman lajittelutaulukon valmistelu koostuu kahdesta vaiheesta: painotaulukon muokkaaminen ja sen kääntäminen binäärimuotoon komennolla localdef.

Jotta vertailutaulukkoa voidaan muokata minimaalisilla muokkauskustannuksilla, muodossa ISO 14652 Tarjolla on osiot olemassa olevan pöydän painojen säätämiseksi. Osio alkaa avainsanalla tilata uudelleen ja osoittaa asennon, jonka jälkeen vaihto suoritetaan. Osio päättyy riviin uudelleenjärjestämisen loppu. Jos on tarpeen korjata useita taulukon osia, jokaiselle tällaiselle osalle luodaan osio.

Kopioin uudet versiot tiedostoista iso14651_t1_common и ru_ru arkistosta glibc kotihakemistooni ~/.local/share/i18n/locales/ ja muokkasin osiota hieman LC_COLLATE в ru_ru. Uudet tiedostoversiot ovat täysin yhteensopivia minun versioni kanssa glibc. Jos haluat käyttää vanhempia tiedostoversioita, sinun on muutettava symbolisia nimiä ja paikkaa, josta korvaaminen alkaa taulukossa.

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

Itse asiassa kenttiä pitäisi muuttaa LC_IDENTIFICATION niin, että ne osoittavat aluetta ru_MY, mutta esimerkissäni tätä ei vaadittu, koska jätin arkiston pois alueiden hausta alue-arkisto.

Että localdef työskennellyt kansiossani olevien tiedostojen kanssa muuttujan kautta I18NPATH Voit lisätä ylimääräisen hakemiston syötetiedostojen etsimistä varten, ja binääritiedostojen tallennushakemisto voidaan määrittää poluksi vinoviivalla:

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

POSIX olettaa, että sisään PITKÄ voit kirjoittaa absoluuttisia polkuja hakemistoihin, joissa on kielialuetiedostoja, alkaen vinoviivasta, mutta glibc в Linux kaikki polut lasketaan perushakemistosta, joka voidaan ohittaa muuttujan avulla LOCPATH. Asennuksen jälkeen LOCPATH=~/.local/lib/locale/ kaikki lokalisointiin liittyvät tiedostot haetaan vain kansiostani. Arkisto kielialueet muuttujajoukon kanssa LOCPATH huomiotta.

Tässä ratkaiseva testi:

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

Hurraa! Me teimme sen!

Joitakin virheitä

Olen jo vastannut alussa esitettyihin kysymyksiin merkkijonojen lajittelusta, mutta vielä on pari kysymystä virheistä - näkyvistä ja näkymättömistä.

Palataan alkuperäiseen ongelmaan.

Ja ohjelma lajitella ja ohjelma yhdistää käytä samoja merkkijonojen vertailufunktioita glibc. Miten niin kävikään yhdistää antoi lajitteluvirheen komennolla lajiteltuihin riveihin lajitella paikallisesti fi_US.UTF-8? Vastaus on yksinkertainen: lajitella vertaa koko merkkijonoa ja yhdistää vertaa vain avainta, joka oletuksena on merkkijonon alku ensimmäiseen välilyöntimerkkiin asti. Esimerkissäni tämä johti virheilmoitukseen, koska rivien ensimmäisten sanojen lajittelu ei vastannut kokonaisten rivien lajittelua.

Alue "C" takaa, että lajitetuissa merkkijonoissa myös alkuperäiset osamerkkijonot ensimmäiseen välilyöntiin asti lajitellaan, mutta tämä vain peittää virheen. On mahdollista valita tietoja (henkilöitä, joilla on sama sukunimi, mutta eri etunimet), jotka ilman virheilmoitusta antaisivat virheellisen tiedoston yhdistämistuloksen. Jos haluamme yhdistää yhdistetyt tiedostorivit koko nimellä, oikea tapa olisi määrittää kentän erotin ja lajitella avainkentän mukaan, ei koko rivin mukaan. Tässä tapauksessa yhdistäminen etenee oikein, eikä virheitä tapahdu millään kielialueella:

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

Onnistuneesti suoritettu esimerkki koodauksessa CP1251 sisältää toisen virheen. Tosiasia on, että kaikissa tuntemissani jakeluissa Linux paketeista puuttuu käännetty alue ru_RU.CP1251. Jos käännettyä aluetta ei löydy, niin lajitella käyttää hiljaa tavu-tavulta vertailua, minkä havaitsimme.

Muuten, on toinen pieni häiriö, joka liittyy koottujen alueiden saavuttamattomuuteen. Tiimi LOCPATH=/tmp maa-asetus -a antaa luettelon kaikista alueista alue-arkisto, mutta muuttujajoukolla LOCPATH kaikille ohjelmille (mukaan lukien useimmat locale) nämä alueet eivät ole käytettävissä.

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

Johtopäätös

Jos olet ohjelmoija, joka on tottunut ajattelemaan, että merkkijonot ovat tavuja, valintasi on sinun LC_COLLATE=C.

Jos olet kielitieteilijä tai sanakirjan kääntäjä, sinun on parempi kääntää omalla alueellasi.

Jos olet yksinkertainen käyttäjä, sinun täytyy vain tottua siihen, että komento ls -a tulostaa pisteellä alkavat tiedostot sekoitettuna kirjaimella alkaviin tiedostoihin ja Keskiyön komentaja, joka käyttää sisäisiä toimintojaan nimien lajitteluun, sijoittaa pisteellä alkavat tiedostot luettelon alkuun.