Bevezetés

Az egész egy rövid szkripttel kezdődött, aminek a címinformációkat kellett volna kombinálnia E-mail a levelezőlista-felhasználók listájáról szerzett munkatársak, a HR osztály adatbázisából nyert alkalmazotti pozíciókkal. Mindkét lista Unicode szövegfájlba lett exportálva UTF-8 és Unix sorvéggel mentve.

Tartalom mail.txt

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

Tartalom buhg.txt

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

Az egyesítéshez a fájlokat a Unix paranccsal rendeztük fajta és benyújtották a Unix program bemenetére csatlakozik, amely váratlanul meghiúsult egy hibával:

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

A rendezési eredményt szemmel nézve kiderült, hogy általában a rendezés helyes, de a férfi és női vezetéknevek egybeesése esetén a nőiek a férfiak elé kerülnek:

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

Úgy néz ki, mint egy rendezési hiba a Unicode-ban, vagy a feminizmus megnyilvánulása a rendezési algoritmusban. Az első természetesen hihetőbb.

Egyelőre halasszuk el csatlakozik és összpontosítani fajta. Próbáljuk meg megoldani a problémát tudományos piszkálással. Először változtassuk meg a területi beállítást hu on ru_RU. A rendezéshez elég lenne beállítani a környezeti változót LC_COLLATE, de nem vesztegetjük az időt apróságokra:

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

Semmi sem változott.

Próbáljuk meg átkódolni a fájlokat egybájtos kódolásba:

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

Ismét semmi sem változott.

Nem tudsz mit tenni, az interneten kell megoldást keresned. Közvetlenül az orosz vezetéknevekről nincs szó, de vannak kérdések más rendezési furcsaságokkal kapcsolatban. Például itt van egy probléma: A unix sort a '-' (kötőjel) karaktereket láthatatlanként kezeli. Röviden, az "ab", "aa", "ac" karakterláncok "aa", "ab", "ac" sorrendben vannak rendezve.

A válasz mindenhol szabványos: használja a programozó területi beállítását "C" és boldog leszel. Próbáljuk meg:

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

Valami megváltozott. Ivanovék a megfelelő sorrendben sorakoztak fel, bár Yolkina valahol megcsúszott. Térjünk vissza az eredeti problémához:

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

Hiba nélkül működött, ahogy az Internet ígérte. És ez annak ellenére, hogy Yolkina az első sorban.

Úgy tűnik, a probléma megoldódott, de minden esetre próbáljunk meg egy másik orosz kódolást - a Windowst CP1251:

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

A rendezés eredménye, furcsa módon, egybeesik a területi beállítással "C", és ennek megfelelően az egész példa hiba nélkül fut. Valamiféle miszticizmus.

Nem szeretem a misztikát a programozásban, mert általában elfedi a hibákat. Komolyan meg kell vizsgálnunk, hogyan működik. fajta és mit érint? LC_COLLATE .

A végén megpróbálok válaszolni a kérdésekre:

miért lettek rosszul rendezve a női vezetéknevek?
miért LANG=ru_RU.CP1251 egyenértékűnek bizonyult LANG=C
miért fajta и csatlakozik különböző elképzelések a rendezett karakterláncok sorrendjéről
miért vannak hibák az összes példámban?
végül hogyan kell a húrokat ízlés szerint rendezni

Rendezés Unicode-ban

Az első állomás a 10. számú műszaki jelentés lesz Unicode leválogatási algoritmus online unicode.org. A jelentés sok technikai részletet tartalmaz, ezért engedjék meg, hogy röviden összefoglaljam a főbb gondolatokat.

Egyeztetés — A karakterláncok „összehasonlítása” minden rendezési algoritmus alapja. Maguk az algoritmusok eltérőek lehetnek ("buborék", "egyesítés", "gyors"), de mindegyik karakterláncpár összehasonlítását fogja használni a megjelenési sorrend meghatározásához.

A karakterláncok rendezése természetes nyelven meglehetősen összetett probléma. Még a legegyszerűbb egybájtos kódolásoknál is az ábécé betűinek sorrendje, még akkor sem, ha valamilyen módon eltér az angol latin ábécétől, többé nem esik egybe azoknak a számértékeknek a sorrendjével, amelyekkel ezeket a betűket kódolják. Tehát a német ábécében a betű Ö között áll О и P, és a kódolásban CP850 közé kerül ÿ и Ü.

Megpróbálhat elvonatkoztatni egy adott kódolástól, és fontolóra veheti az „ideális” betűket, amelyek valamilyen sorrendben vannak elrendezve, ahogy az Unicode-ban is történik. Kódolások UTF8, UTF16 vagy egybájtos KOI8-R (ha a Unicode korlátozott részhalmazára van szükség) a betűk különböző numerikus megjelenítését adja meg, de az alaptábla ugyanazokra az elemeire hivatkozik.

Kiderült, hogy hiába építünk fel egy szimbólumtáblázatot a semmiből, nem tudunk hozzá univerzális szimbólumsorrendet rendelni. A különböző nemzeti ábécékben, amelyek ugyanazokat a betűket használják, a betűk sorrendje eltérő lehet. Például franciául Æ ligatúrának tekintjük, és karakterláncként rendezzük AE. norvégul Æ egy külön levél lesz, amely után található Z. By the way, amellett, hogy ligatúrák, mint Æ Többféle szimbólummal írt betűk vannak. Tehát a cseh ábécében van egy betű Ch, amely között áll H и I.

Az ábécé különbségein kívül más nemzeti hagyományok is befolyásolják a válogatást. Konkrétan felmerül a kérdés: milyen sorrendben jelenjenek meg a nagy- és kisbetűkből álló szavak a szótárban? A rendezést az írásjelek használata is befolyásolhatja. Spanyolban fordított kérdőjelet használnak a kérdő mondat elején (Szereted a zenét?). Ebben az esetben nyilvánvaló, hogy a kérdő mondatokat nem szabad az ábécén kívül külön csoportba csoportosítani, de hogyan kell sorba rendezni a többi írásjelet?

Nem foglalkozom a karakterláncok rendezésével olyan nyelveken, amelyek nagyon különböznek az európaiaktól. Ne feledje, hogy a jobbról balra vagy fentről lefelé írási iránnyal rendelkező nyelvekben a sorok karakterei nagy valószínűséggel olvasási sorrendben vannak tárolva, és még a nem alfabetikus írásrendszereknek is megvannak a maguk módjai a sorok karakterenkénti rendezésére. . Például a hieroglifák stílus szerint rendezhetők (Kínai karakterek billentyűi) vagy kiejtéssel. Hogy őszinte legyek, fogalmam sincs, hogyan kell az emojikat elrendezni, de ezekhez is kitalálhatsz valamit.

A fent felsorolt jellemzők alapján megfogalmazásra kerültek a karakterláncok Unicode táblákon alapuló összehasonlításának alapvető követelményei:

a karakterláncok összehasonlítása nem függ a karakterek helyétől a kódtáblázatban;
az egyetlen karaktert alkotó karaktersorozatok kanonikus formára redukálódnak (A + a felső kör ugyanaz, mint Å);
A karakterláncok összehasonlításakor egy karaktert a karakterlánc kontextusában veszünk figyelembe, és ha szükséges, a szomszédaival kombináljuk egy összehasonlítási egységgé (Ch csehül) vagy több részre oszlik (Æ franciául);
minden nemzeti jellemzőt (ábécé, nagy-/kisbetűk, írásjelek, írástípusok sorrendje) konfigurálni kell a sorrend kézi hozzárendeléséig (emoji);
az összehasonlítás nem csak a rendezésnél fontos, hanem sok más helyen is, például sortartományok megadásakor ({A... z} helyett horpadás);
az összehasonlítást elég gyorsan meg kell tenni.

Ezenkívül a jelentés készítői olyan összehasonlítási tulajdonságokat fogalmaztak meg, amelyekre az algoritmusfejlesztőknek nem szabad támaszkodniuk:

az összehasonlító algoritmus nem igényel külön karakterkészletet minden nyelvhez (az orosz és az ukrán nyelvek a legtöbb cirill karaktert használják);
az összehasonlítás nem támaszkodhat a Unicode-táblázatok karaktereinek sorrendjére;
a karakterlánc súlya nem lehet a karakterlánc attribútuma, mivel ugyanaz a karakterlánc különböző kulturális kontextusokban eltérő súlyú lehet;
A sorok súlya változhat egyesítéskor vagy felosztáskor (a x < y ebből nem következik xz < yz);
a különböző, azonos súlyú karakterláncokat a rendezési algoritmus szempontjából egyenlőnek tekintjük. Az ilyen karakterláncok további sorrendjének bevezetése lehetséges, de ez ronthatja a teljesítményt;
Az ismételt rendezés során az azonos súlyú sorok felcserélődhetnek. A robusztusság egy adott rendezési algoritmus tulajdonsága, nem pedig egy karakterlánc-összehasonlító algoritmus tulajdonsága (lásd az előző bekezdést);
A rendezési szabályok idővel változhatnak, ahogy a kulturális hagyományok finomodnak/változnak.

Azt is előírják, hogy az összehasonlító algoritmus semmit sem tud a feldolgozott karakterláncok szemantikájáról. Így a csak számjegyekből álló karakterláncokat nem szabad számként összehasonlítani, és az angol nevek listájában a cikk (Beatles, The).

Az összes meghatározott követelmény kielégítésére egy többszintű (valójában négyszintű) táblázatrendezési algoritmust javasolunk.

Korábban a karakterlánc karaktereit kanonikus formára redukálták, és összehasonlítási egységekre csoportosították. Minden összehasonlítási egységhez több súlyozás van hozzárendelve, amelyek több összehasonlítási szintnek felelnek meg. Az összehasonlítási egységek súlyai rendezett halmazok elemei (jelen esetben egész számok), amelyek többé-kevésbé összehasonlíthatók. Különleges jelentés FIGYELMEZTETVE (0x0) azt jelenti, hogy a megfelelő összehasonlítási szinten ez az egység nem vesz részt az összehasonlításban. A húrok összehasonlítása többször is megismételhető, a megfelelő szintek súlyozásával. Minden szinten két sor összehasonlító egységeinek súlyát egymás után hasonlítják össze.

A különböző nemzeti hagyományokhoz tartozó algoritmus különböző megvalósításaiban az együtthatók értékei eltérhetnek, de az Unicode szabvány tartalmaz egy alapvető súlytáblázatot - "Alapértelmezett Unicode leválogatási elemtábla" (DUCET). Szeretném megjegyezni, hogy a változó beállítása LC_COLLATE valójában a súlytáblázat kiválasztását jelzi a karakterlánc-összehasonlító függvényben.

Súlyozási együtthatók DUCET a következőképpen rendezve:

az első szinten az összes betűt ugyanarra a kis- és nagybetűre redukálják, a diakritikus jeleket elvetik, az írásjeleket (nem mindegyiket) figyelmen kívül hagyják;
a második szinten csak a diakritikusokat veszik figyelembe;
a harmadik szinten csak az esetet veszik figyelembe;
a negyedik szinten csak az írásjeleket veszik figyelembe.

Az összehasonlítás több menetben történik: először az első szint együtthatóit hasonlítják össze; ha a súlyok egybeesnek, akkor ismételt összehasonlítást kell végezni a második szintű súlyokkal; aztán talán egy harmadik és egy negyedik.

Az összehasonlítás akkor ér véget, amikor a sorok különböző súllyal rendelkező összehasonlítási egységeket tartalmaznak. Azok a sorok, amelyek mind a négy szinten azonos súllyal rendelkeznek, egyenlőnek számítanak egymással.

Ez az algoritmus (egy csomó további technikai részlettel) adta a 10. számú jelentés nevét - "Unicode Collation Algorithm" (ACU).

Itt válik egy kicsit világosabbá a példánk szerinti rendezési viselkedés. Jó lenne összehasonlítani az Unicode szabvánnyal.

A megvalósítások tesztelésére ACU van egy különleges teszt, segítségével súlyok fájl, megvalósítása DUCET. A mérleg fájlban mindenféle vicces dolgot találhatsz. Például ott van a mahjong és az európai dominó sorrendje, valamint a színek sorrendje a kártyapakliban (szimbólum 1F000 és tovább). A kártyaszínek a bridzs - PCBT szabályai szerint vannak elhelyezve, a színben lévő lapok pedig T, 2,3, XNUMX... K sorrendben vannak.

Manuális ellenőrzése, hogy a sorok megfelelően vannak-e rendezve DUCET elég fárasztó lenne, de szerencsére van a könyvtár példamutató megvalósítása a Unicode-dal való együttműködéshez - "Nemzetközi komponensek a Unicode-hoz"(ICU).

Ennek a könyvtárnak a weboldalán, amelyet ben fejlesztettek ki IBM, vannak bemutató oldalak, köztük karakterlánc-összehasonlító algoritmus oldal. Alapbeállításokkal lépünk be tesztsorainkba, és lám, tökéletes orosz rendezést kapunk.

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

Mellesleg a honlap ICU Az összehasonlító algoritmus pontosítását az írásjelek feldolgozásakor találhatja meg. Példákban Összeállítás GYIK az aposztrófot és a kötőjelet figyelmen kívül hagyja.

A Unicode segített nekünk, de keressük a furcsa viselkedés okait fajta в Linux máshova kell mennie.

Rendezés glibc-ben

A segédprogramok forráskódjainak gyors áttekintése fajta A GNU Core Utils megmutatta, hogy magában a segédprogramban a lokalizáció a változó aktuális értékének kinyomtatásán múlik LC_COLLATE ha hibakeresési módban fut:

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

A karakterlánc-összehasonlításokat a szabványos függvény segítségével hajtják végre strcoll, ami azt jelenti, hogy minden érdekes a könyvtárban van glibc.

tovább wiki program glibc a húr-összehasonlításnak szentelt egy bekezdés. Ebből a bekezdésből érthető, hogy in glibc a rendezés egy általunk már ismert algoritmuson alapul ACU (Az Unicode leválogatási algoritmus) és/vagy egy ahhoz közeli szabványon ISO 14651 (Nemzetközi karakterláncok rendezése és összehasonlítása). A legújabb szabványt illetően meg kell jegyezni, hogy az oldalon standards.iso.org ISO 14651 hivatalosan nyilvánosan elérhetővé nyilvánították, de a megfelelő link egy nem létező oldalra vezet. A Google több olyan oldalt is visszaad, amelyeken olyan hivatalos oldalakra mutató linkek találhatók, amelyek száz euróért kínálják a szabvány elektronikus példányának megvásárlását, de a keresési eredmények harmadik-negyedik oldalán közvetlen linkek is találhatók PDF. Általában a szabvány gyakorlatilag nem különbözik ACU, de unalmasabb olvasni, mert nem tartalmaz egyértelmű példákat a sztringrendezés nemzeti sajátosságaira.

A legérdekesebb információk a wiki volt egy link hibakövető a karakterlánc-összehasonlítás megvalósításának tárgyalásával glibc. A beszélgetésből megtudható, hogy glibc karakterláncok összehasonlítására szolgál ISOszemélyes asztal A közös sablontáblázat (CTT), melynek címe a pályázatban található A alapértelmezett ISO 14651. 2000 és 2015 között ez a táblázat glibc nem volt karbantartója, és eléggé különbözött (legalábbis külsőleg) a szabvány jelenlegi verziójától. 2015 és 2018 között az asztal új verziójához való alkalmazkodás megtörtént, és most lehetősége van a valóságban is találkozni a táblázat új verziójával (8 CentOS), és régi (7 CentOS).

Most, hogy minden információval rendelkezünk az algoritmusról és a segédtáblázatokról, visszatérhetünk az eredeti problémához, és megérthetjük, hogyan kell helyesen rendezni a karakterláncokat az orosz nyelvterületen.

ISO 14651 / 14652

A minket érdeklő táblázat forráskódja CTT a legtöbb disztribúción Linux szerepel a katalógusban /usr/share/i18n/locales/. Maga a táblázat a fájlban van iso14651_t1_common. Akkor ez a fájl direktíva másolja az iso14651_t1_common szerepel a fájlban iso14651_t1, amely viszont szerepel a nemzeti aktákban, beleértve hu и ru_RU. A legtöbb disztribúción Linux minden forrásfájl benne van az alaptelepítésben, de ha nincsenek, akkor telepítenie kell egy további csomagot a disztribúcióból.

Fájlszerkezet iso14651_t1 borzasztóan bőbeszédűnek tűnhet, nem nyilvánvaló szabályokkal a nevek felépítésére, de ha megnézzük, minden nagyon egyszerű. A szerkezetet a szabvány írja le ISO 14652, melynek egy példánya letölthető a weboldalról open-std.org. A fájlformátum másik leírása olvasható specifikációk POSIX -tól OpenGroup. A szabvány olvasásának alternatívájaként tanulmányozhatja a függvény forráskódját összeválogatás_olvasott в glibc/locale/programs/ld-collate.c.

A fájl szerkezete így néz ki:

Alapértelmezés szerint a karakter escape karakterként használatos, és a # karakter utáni sor vége egy megjegyzés. Mindkét szimbólum újradefiniálható, ami a táblázat új verziójában történik:

escape_char /
comment_char %

A fájl a következő formátumú tokeneket fogja tartalmazni vagy (ahol x - hexadecimális számjegy). Ez a Unicode kódpontok hexadecimális ábrázolása a kódolásban UCS-4 (UTF-32). Minden más elem szögletes zárójelben (beleértve , <2> és hasonlók) egyszerű karakterlánc-állandóknak tekintendők, amelyeknek a kontextuson kívül kevés jelentése van.

Vonal LC_COLLATE azt mondja nekünk, hogy ezután kezdődik a karakterláncok összehasonlítását leíró adat.

Először az összehasonlító táblázatban szereplő súlyok nevei, a szimbólumkombinációk nevei vannak megadva. Általánosságban elmondható, hogy a két névtípus két különböző entitáshoz tartozik, de a tényleges fájlban keverednek. A súlyok nevét a kulcsszó adja meg összeválogató-szimbólum (összehasonlító karakter), mert összehasonlításkor az azonos súllyal rendelkező Unicode karaktereket egyenértékű karaktereknek tekintjük.

A szakasz teljes hossza a jelenlegi fájlváltozatban körülbelül 900 sor. Több helyről húztam példákat, hogy bemutassam a nevek önkényességét és többféle szintaxist.

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

összeválogató-szimbólum naplóz egy karakterláncot OSMANYA a mérlegek névtáblázatában
összeválogató-szimbólum .. előtagból álló névsort regisztrál S és hexadecimális numerikus utótag -ból 1D000 a 1D35F.
FFFF в összeválogató-szimbólum úgy néz ki, mint egy nagy előjel nélküli egész szám hexadecimális formában, de ez csak egy név, ami így nézhet ki
név kódpontot jelent a kódolásban UCS-4
összeválogató-elem tól től " " új nevet regisztrál egy pár Unicode ponthoz.

A súlyok nevének meghatározása után a tényleges súlyok is megadásra kerülnek. Mivel csak a kisebbnél nagyobb relációk számítanak az összehasonlításban, a súlyokat egy egyszerű felsorolási névsor határozza meg. Először a „könnyebb” súlyokat, majd a „nehezebbeket” soroljuk fel. Hadd emlékeztesselek arra, hogy minden Unicode karakterhez négy különböző súly tartozik. Itt egyetlen rendezett szekvenciává egyesülnek. Elméletileg bármilyen szimbolikus név használható a négy szint bármelyikén, de a megjegyzések azt mutatják, hogy a fejlesztők mentálisan szintekre osztják a neveket.

% 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

Végül a tényleges súlytáblázat.

A súlyok szakasz kulcsszósorokba van zárva order_start и order_end. Extra lehetőségek order_start meghatározza, hogy a sorokat milyen irányban vizsgálja a rendszer az összehasonlítás egyes szintjén. Az alapértelmezett beállítás a előre. A szakasz törzse olyan sorokból áll, amelyek a szimbólumkódot és annak négy súlyát tartalmazzák. A karakterkódot képviselheti maga a karakter, egy kódpont vagy egy korábban meghatározott szimbolikus név. A szimbolikus nevek, kódpontok vagy maguk a szimbólumok is súlyozhatók. Ha kódpontokat vagy karaktereket használunk, akkor azok súlya megegyezik a kódpont számértékével (pozíció a Unicode táblázatban). A kifejezetten nem meghatározott karakterek (ahogy megértem) a táblához vannak hozzárendelve, olyan elsődleges súllyal, amely megegyezik a Unicode tábla pozíciójával. Különleges súlyérték FIGYELMEN KÍVÜL HAGYNI azt jelenti, hogy a szimbólumot figyelmen kívül hagyják az összehasonlítás megfelelő szintjén.

A mérleg szerkezetének bemutatására három meglehetősen nyilvánvaló töredéket választottam:

teljesen figyelmen kívül hagyott karakterek
az első két szinten a hármas számmal egyenértékű szimbólumok
a cirill ábécé eleje, amely nem tartalmaz diakritikusokat, ezért elsősorban az első és a harmadik szint szerint van rendezve.

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

Most visszatérhet a példák rendezéséhez a cikk elejétől. A les a súlytáblázat ezen részében rejlik:

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

Látható, hogy ebben a táblázatban az írásjelek a táblázatból ASCII (beleértve a szóközt is) szinte mindig figyelmen kívül hagyja a karakterláncok összehasonlításakor. Az egyetlen kivételt azok a sorok jelentik, amelyek mindenben megegyeznek, kivéve az egyező pozíciókban található írásjeleket. A példám sorai (rendezés után) az összehasonlító algoritmushoz így néznek ki:

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

Figyelembe véve, hogy a skálatáblázatban az orosz nagybetűk a kisbetűk után jönnek (a harmadik szinten nehezebb, mint ), a rendezés teljesen helyesnek tűnik.

Változó beállításakor LC_COLLATE=C egy speciális tábla töltődik be, amely byte-byte összehasonlítást ad meg

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

Mivel a Unicode-ban a Ё kódpont A elé kerül, a karakterláncok ennek megfelelően vannak rendezve.

Szöveges és bináris táblázatok

Nyilvánvaló, hogy a karakterlánc-összehasonlítás rendkívül gyakori művelet, és a táblázat elemzése CTT meglehetősen költséges eljárás. A táblához való hozzáférés optimalizálása érdekében a paranccsal bináris formátumba fordítjuk localdef.

Csapat localdef paraméterként elfogad egy fájlt a nemzeti jellemzők táblázatával (opció -i), amelyben az összes karaktert Unicode pontok jelölik, valamint egy fájl, amely megfelel a Unicode pontok és egy adott kódolás karakterei között (opció -f). A munka eredményeként bináris fájlok jönnek létre a területi beállításhoz az utolsó paraméterben megadott néven.

glibc két bináris fájlformátumot támogat: "hagyományos" és "modern".

A hagyományos formátum azt jelenti, hogy a területi beállítás neve a benne lévő alkönyvtár neve /usr/lib/locale/. Ez az alkönyvtár bináris fájlokat tárol LC_COLLATE, LC_CTYPE, LC_TIME stb. Fájl LC_IDENTIFICATION tartalmazza a területi beállítás formális nevét (amely eltérhet a könyvtár nevétől) és megjegyzéseket.

A modern formátum magában foglalja az összes területi beállítás egyetlen archívumban való tárolását /usr/lib/locale/locale-archive, amely az összes használó folyamat virtuális memóriájába van leképezve glibc. A modern formátumban használt területnév bizonyos kanonizálásnak van kitéve - csak a kisbetűsre csökkentett számok és betűk maradnak a kódolási nevekben. Így ru_RU.KOI8-R, néven lesz elmentve ru_RU.koi8r.

A bemeneti fájlok keresése az aktuális könyvtárban, valamint a könyvtárakban történik /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ fájlokhoz CTT és kódoló fájlok, ill.

Például a parancs

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

lefordítja a fájlt /usr/share/i18n/locales/ru_RU kódoló fájl használatával /usr/share/i18n/charmaps/MAC-CYRILLIC.gz és mentse el az eredményt /usr/lib/locale/locale-archive néven ru_RU.maccyrillic

Ha beállítja a változót LANG = en_US.UTF-8 hogy glibc a következő fájlok és könyvtárak sorrendjében keresi a locale binárisokat:

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

Ha egy területi beállítás hagyományos és modern formátumban is előfordul, akkor a modern formátum elsőbbséget élvez.

A paranccsal megtekintheti a lefordított területi beállítások listáját locale -a.

Összehasonlító táblázat elkészítése

Most a tudással felvértezve elkészítheti saját ideális karakterlánc-összehasonlító táblázatát. Ebben a táblázatban helyesen kell összehasonlítani az orosz betűket, beleértve az Ё betűt is, és ugyanakkor figyelembe kell vennie az írásjeleket a táblázatnak megfelelően ASCII.

A saját rendezési táblázat elkészítésének folyamata két lépésből áll: a súlytáblázat szerkesztése és bináris formátumba fordítása a paranccsal localdef.

Annak érdekében, hogy az összehasonlító táblázat minimális szerkesztési költséggel igazodjon, formátumban ISO 14652 A meglévő asztalok súlyának beállítására szolgáló szakaszok rendelkezésre állnak. A szakasz egy kulcsszóval kezdődik átrendezni-utána és megjelölve azt a pozíciót, amely után a csere történik. A szakasz a vonallal végződik reorder-end. Ha a táblázat több szakaszát kell javítani, akkor minden ilyen szakaszhoz létrejön egy szakasz.

A fájlok új verzióit másoltam iso14651_t1_common и ru_RU az adattárból glibc a ~/.local/share/i18n/locales/ kezdőkönyvtáramba, és kissé szerkesztettem a részt LC_COLLATE в ru_RU. A fájlok új verziói teljes mértékben kompatibilisek az én verziómmal glibc. Ha a fájlok régebbi verzióit kívánja használni, módosítania kell a szimbolikus neveket és a táblázatban a csere kezdési helyét.

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

Valójában módosítani kellene a mezőket LC_IDENTIFICATION hogy a területre mutassanak ru_MY, de az én példámban erre nem volt szükség, mivel kizártam az archívumot a locales kereséséből locale-archívum.

Hogy localdef a mappámban lévő fájlokkal dolgoztam egy változón keresztül I18NPATH Hozzáadhat egy további könyvtárat a bemeneti fájlok kereséséhez, és a bináris fájlok mentési könyvtára megadható perjelekkel ellátott útvonalként:

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

POSIX azt javasolja, hogy be NYELV a területi fájlokat tartalmazó könyvtárak abszolút elérési útját írhatja, perjellel kezdve, de glibc в Linux minden elérési út az alapkönyvtárból történik, amely egy változón keresztül felülbírálható LOCPATH. Telepítés után LOCPATH=~/.local/lib/locale/ a lokalizációval kapcsolatos összes fájl csak az én mappámban lesz keresve. A beállított változóval rendelkező területi beállítások archívuma LOCPATH figyelmen kívül hagyva.

Íme a döntő teszt:

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

Hurrá! Megcsináltuk!

Néhány hiba

Már válaszoltam az elején feltett kérdésekre a karakterlánc-rendezéssel kapcsolatban, de van még néhány kérdés a hibákkal kapcsolatban - látható és láthatatlan.

Térjünk vissza az eredeti problémához.

És a program fajta és a program csatlakozik ugyanazokat a karakterlánc-összehasonlító függvényeket használja glibc. Hogy történt ez csatlakozik rendezési hibát adott a paranccsal rendezett sorokon fajta nyelven hu_US.UTF-8? A válasz egyszerű: fajta összehasonlítja a teljes karakterláncot, és csatlakozik csak a kulcsot hasonlítja össze, amely alapértelmezés szerint a karakterlánc eleje az első szóköz karakterig. Példámban ez hibaüzenetet eredményezett, mert a sorok első szavainak rendezése nem egyezik a teljes sorok rendezésével.

Nyelv "C" garantálja, hogy rendezett karakterláncokban a kezdeti részkarakterláncok az első szóközig is rendezve lesznek, de ez csak elfedi a hibát. Lehetőség van olyan adatok (azonos vezetéknevű, de eltérő keresztnevű személyek) kiválasztására, amelyek hibaüzenet nélkül hibás fájlegyesítési eredményt adnának. Ha akarjuk csatlakozik egyesített fájlsorokat teljes név szerint, akkor a helyes módja az lenne, ha kifejezetten megadná a mezőelválasztót, és a kulcsmező szerint rendezné a rendezést, nem pedig a teljes sor szerint. Ebben az esetben az egyesítés megfelelően megy végbe, és nem lesz hiba egyetlen nyelvben sem:

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

A példa sikeresen végrehajtva a kódolásban CP1251 egy másik hibát tartalmaz. A helyzet az, hogy minden általam ismert disztribúcióban Linux a csomagokból hiányzik a lefordított területi beállítás ru_RU.CP1251. Ha a lefordított területi beállítás nem található, akkor fajta csendben byte-byte összehasonlítást használ, amit mi is megfigyeltünk.

Egyébként van még egy apró hiba, ami a lefordított locales elérhetetlenségével kapcsolatos. Csapat LOCPATH=/tmp területi beállítás -a listát ad az összes területről locale-archívum, hanem a változókészlettel LOCPATH minden programhoz (beleértve a legtöbbet is helyszín) ezek a nyelvek nem lesznek elérhetők.

$> 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övetkeztetés

Ha Ön programozó, aki megszokta, hogy a karakterláncok bájtok halmazai, akkor az Ön választása LC_COLLATE=C.

Ha Ön nyelvész vagy szótárfordító, akkor jobb, ha a saját nyelvén fordítja le.

Ha egyszerű felhasználó vagy, akkor csak meg kell szoknod, hogy a parancs ls -a ponttal kezdődő fájlokat ad ki betűvel kezdődő fájlokkal keverve, és Éjfél parancsnok, amely belső funkcióit használja a nevek rendezésére, a ponttal kezdődő fájlokat a lista elejére helyezi.