Bevezetés

Minden egy rövid szkripttel kezdődött, amelynek az volt a célja, hogy összevonja az e-mail címet e-mail a munkatársakról, amelyeket a hírlevél felhasználói listájából kaptunk, a munkatársak beosztásaival, amelyeket a HR adatbázisból nyertünk. Mindkét lista szövegfájlokba lett exportálva Unicode kódolásban UTF-8 és Unix-os sorvégződésekkel lettek mentve.

Tartalom mail.txt

Ivanov András;ia@example.com

Tartalom buhg.txt

Ivanova Alla;festő
Yolkina Ella;darukezelő
Ivanov András;szerelő
Abakanov Mihály;festő

Az egyesítéshez a fájlokat a Unix parancs segítségével rendezték sort és a Unix program bemenetére kerültek join, amely váratlanul hibával zárult:

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: nincs rendezve: Ivanov András;szerelő

A rendezés eredményének szemmel történő áttekintése arra mutatott, hogy a rendezés általában helyes, de a férfiak és nők neveinek ütközése esetén a női nevek megelőzik a férfiakat:

$> sort buhg.txt
Abakanov Mihály;festő
Yolkina Ella;darukezelő
Ivanova Alla;festő
Ivanov András;szerelő

Úgy tűnik, ez a Unicode rendezés bugja, vagy a feminizmus megnyilvánulása a rendezési algoritmusban. Az első, természetesen, valószínűbb.

Hagyjuk most join és koncentráljunk sort. Próbáljuk meg megoldani a problémát a kísérletezés módszerével. Először is, változtassuk meg a nyelvi beállítást en_US Gyorsan emlékezzünk vissza, hogyan működik a moduláris aritmetika. Az óra már egy ismert koncepció. Az órák használata ru_RU. A rendezéshez elegendő lenne a környezeti változó beállítása LC_COLLATE, de nem fogunk fukarkodni:

$> LANG=ru_RU.UTF-8 sort buhg.txt
Abakanov Mihály;festő
Yolkina Ella;darukezelő
Ivanova Alla;festő
Ivanov András;szerelő

Semmi sem változott.

Próbáljuk meg a fájlokat egy bájtos kódolásra átkonvertálni:

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

Megint semmi sem változott.

Nem tehetünk mást, interneten kell megoldást keresnünk. Kifejezetten orosz nevekről nincsenek információk, de vannak kérdések más rendezési furcsaságokról. Például a következő probléma: a unix rendező a ‘-’ (tömörített) karaktereket láthatatlannak tekinti. Röviden: a "a-b", "aa", "ac" sorok rendezettként jelennek meg, mint "aa", "a-b", "ac".

A válasz mindenhol standard: használj programozói nyelvet "C" és boldog leszel. Próbáljuk:

$> LANG=C sort buhg.txt
Yolkina Ella;darukezelő
Abakanov Mihály;festő
Ivanov András;szerelő
Ivanova Alla;ügyvéd

Valami megváltozott. Ivanovok a helyes sorrendbe álltak, bár Yolkina valahová eltűnt. Visszatérünk az eredeti feladathoz:

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

Hibátlanul működött, ahogy az internet ígérte. És ez mal a Ёlkin első sorához képest.

A probléma úgy tűnik megoldódott, de azért próbáljunk ki még egy orosz kódolást – a Windows-it. CP1251:

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

A rendezés eredménye, meglepő módon, egybeesik a lokálissal "C", és az egész példa ennek megfelelően hibák nélkül átmegy. Valamilyen misztika.

Nem szeretem a misztikát a programozásban, mert általában a hibák elrejtésére szolgál. Komolyan foglalkoznom kell azzal, hogyan működik sort és milyen hatással van LC_COLLATE .

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

miért rendezték hibásan a női vezetékneveket
miért LANG=hu_HU.CP1251 egyenértékűnek bizonyult LANG=C
miért van sort és join különböző elképzelései az összesorolt sorok sorrendjéről
miért vannak hibák minden példámban
végül, hogyan lehet rendezni a sorokat saját ízlés szerint

Rendezés Unicode-ban

Az első megálló a 10-es számú műszaki jelentés lesz Unicode rendezési algoritmus a weboldalon unicode.org. A jelentés sok műszaki részletet tartalmaz, ezért megengedem magamnak, hogy egy rövid összefoglalót adjak az alapvető ötletekről.

Rendezés – a sorok "összehasonlítása" – bármely rendezési algoritmus alapja. Maguk az algoritmusok különbözhetnek ("buborék", "összefésülés", "gyors"), de mindegyik a sorok párba állítását fogja használni a sorrendjük meghatározásához.

A természetes nyelven történő sorba állítás meglehetősen bonyolult probléma. Még a legegyszerűbb, egybájtos kódolások esetén is, a betűk sorrendje az ábécében, ha eltér az angol latin ábécétől, már nem fog egybeesni azoknak a numerikus értékeivel, amelyek ezt a betűt kódolják. Így például a német ábécében az "Ö" betű között áll , míg a "CP850" kódolásban A és Pa következőnél landol: ÿ Ü Megpróbálhatunk elvonatkoztatni a konkrét kódolástól, és "ideális" betűket vizsgálni, amelyek valamilyen sorrendben helyezkednek el, ahogy a Unicode-ban is történik. A "UTF8", "UTF16" és vagy az egységes, egybájtos.

KOI8-R (ha korlátozott Unicode részhalmazra van szükség) különböző numerikus megjelenítést ad a betűknek, de ugyanakkor az alap táblázat ugyanazokat az elemeket hivatkozza., (ha korlátozott Unicode részhalmazra van szükség) különböző numerikus megjelenítést ad a betűknek, de ugyanakkor az alap táblázat ugyanazokat az elemeket hivatkozza. (ha korlátozott Unicode részhalmazra van szükség) különböző numerikus megjelenítést ad a betűknek, de ugyanakkor az alap táblázat ugyanazokat az elemeket hivatkozza. (ha korlátozott Unicode részhalmazra van szükség) különböző numerikus megjelenítést ad a betűknek, de ugyanakkor az alap táblázat ugyanazokat az elemeket hivatkozza. (ha korlátozott Unicode részhalmazra van szükség) különböző numerikus megjelenítést ad a betűknek, de ugyanakkor az alap táblázat ugyanazokat az elemeket hivatkozza.

Kiderül, hogy még ha nulláról építünk is egy karaktertáblát, nem tudunk univerzális karakterrendet rendelni hozzá. Különböző nemzeti ábécék, amelyek ugyanazokat a betűket használják, eltérő rendben tartalmazhatják ezeket a betűket. Például a francia nyelvben Æ ligatúrának számít, és sztringként sorszámozódik AL. A norvég nyelvben viszont Æ különálló betű, amely a következő helyen áll: Z. Egyébként a ligatúrákon kívül vannak olyan betűk is, amelyeket több karakterrel írnak. Ilyen például a cseh ábécében található Æ Ch , amely a következő kettő között helyezkedik el:Az ábécék közötti eltérések mellett más nemzeti hagyományok is befolyásolják a sorszámozást. Például felmerül a kérdés: milyen sorrendben kell következniük a szótárban a nagy- és kisbetűs szavaknak? A sorszámozásra hatással lehet a írásjelek használata is. A spanyol nyelvben a kérdőmondat elején fordított kérdőjelet tesznek ( H és I.

¿Te gusta la música?). Nyilvánvaló, hogy a kérdőmondatoknak nem szabad külön klaszterbe tömörülniük az ábécén kívül, de hogyan kell sorszámozni az egyéb írásjeleket tartalmazó sztringeket?Nem szeretnék a sztringek sorszámozására összpontosítani sokkal eltérőbb nyelvek esetén. Csak megjegyzem, hogy a jobbról balra vagy fentről lefelé író nyelvekben a sztringek valószínűleg az olvasási sorrendben vannak tárolva, és még a nem ábécé alapú írásokban is léteznek saját karakterenkénti sorszámozási módszereik. Például a hieroglifák lehetnek a rajz szerint (

a kínai karakterek kulcsai) vagy a kiejtés alapján sorszámozva. Őszintén szólva, nem tudom, hogyan kellene a hangulatjeleket sorszámozni, de számukra is lehet valamit kitalálni.A fenti jellemzők alapján a Unicode táblákon alapuló sztringek összehasonlítására vonatkozó alapvető követelményeket fogalmazták meg:

sztring összehasonlítása nem függ a karakterek helyzetétől a kódolt táblázatban;

az egyetlen karaktert alkotó karakterek sorrendje kanonikus formába kerül (
+ a felső kör az megegyezik azzal, hogyA Å sztringek összehasonlítása során a karaktert a sztring kontextusába helyezik, és szükség esetén összevonják szomszédaival egy összehasonlítási egységbe ();
cseh nyelven), vagy szétbontják több részre (, amely a következő kettő között helyezkedik el: franciául);Æ franciai);
Minden nemzeti sajátosság (betűrend, nagybetűk/kisbetűk, írásjelek, írásstílusok sorrendje) beállítható egészen a manuális rendelésig (emojik);
A rendezéshez szükséges összehasonlítás nemcsak a rendezésnél fontos, hanem sok más helyen is, például a sorok tartományának megadásakor ({A… я} behelyettesítéssel bash);
Az összehasonlításnak elég gyorsnak kell lennie.

Ezen kívül a jelentés írói megfogalmazták azokat az összehasonlítási tulajdonságokat, amelyekre a algoritmus fejlesztőinek nem szabad támaszkodniuk:

Az összehasonlító algoritmusnak nem kell külön karakterkészletet igényelnie minden nyelvhez (orosz és ukrán nyelvek közösen használják a cirill ábécé többségét);
Az összehasonlításnak nem szabad támaszkodnia a Unicode táblázatok karaktereinek sorrendjére;
A sor súlya nem lehet a sor attribútuma, mivel ugyanaz a sor különböző kulturális kontextusokban eltérő súlyú lehet;
A sorok súlya megváltozhat egyesülés vagy feldarabolás esetén (a x < y nem jelenti azt, hogy xz < yz);
Az azonos súlyú sorok az algoritmus szempontjából egyenlőnek minősülnek. További rendezés bevezetése ezekre a sorokra lehetséges, de ronthatja a teljesítményt;
Többszörös rendezések esetén az azonos súlyú sorok felcserélhetők. A stabilitás egy konkrét rendezési algoritmus tulajdonsága, nem pedig a karakterek összehasonlításának tulajdonsága (lásd az előző pontot);
A rendezési szabályok idővel változhatnak a kulturális hagyományok finomítása/módosítása során.

Ugyancsak meg van jegyezve, hogy az összehasonlító algoritmus semmit sem tud a feldolgozott szövegek szemantikájáról. Így a kizárólag számjegyekből álló szövegeket nem szabad számként összehasonlítani, és az angol elnevezések listáján a névellet nem szabad eltávolítani (Beatles, The).

A fenti követelmények teljesítése érdekében egy többrétegű (valójában négy rétegű) táblázatos rendezési algoritmust javasoltak.

Először a karaktereket a szövegben kanonikus formára alakítják, és hasonlósági egységekre csoportosítják. Minden hasonlósági egység több súlyt kap, amelyek különböző összehasonlítási szintekhez tartoznak. A hasonlósági egységek súlyai rendezett halmazok elemei (ebben az esetben egész számok), amelyeket össze lehet hasonlítani nagyság szerint. Különleges érték IGNORED (0x0) azt jelenti, hogy az adott szintű összehasonlításban ez az egység nem vesz részt. A karakterláncok összehasonlítása többször is megismételhető, a megfelelő szintek súlyainak felhasználásával. Minden egyes szinten a karakterláncok összehasonlítása során az összehasonlító egységek súlyait fokozatosan hasonlítják össze egymással.

A különböző algoritmusmegvalósítások során, a különböző nemzeti hagyományok esetén a súlyok nagysága eltérhet, de a Unicode szabvány részét képező alap súlytáblázat — "Alapértelmezett Unicode Összehasonlítási Elem Tábla" (DUCET). Szeretném megjegyezni, hogy a változó beállítása LC_COLLATE tulajdonképpen arra utal, hogy a súlytáblázat kiválasztását a karakterláncok összehasonlító függvényében határozzuk meg.

Súlyozási tényezők DUCET a következőképpen épülnek fel:

az első szinten minden betűt egy szabályos formára hoznak, a diakritikus jeleket figyelmen kívül hagyják, a (nem minden) írásjelet ignorálják;
a második szinten csak a diakritikus jelek vehetők figyelembe;
a harmadik szinten csak a nagybetű és kisbetű figyelhető meg;
a negyedik szinten pedig csak az írásjelek számítanak.

Az összehasonlítás több lépésben történik: először az első szint súlyait hasonlítják össze; ha a súlyok megegyeznek, akkor újbóli összehasonlításra kerül sor a második szint súlyaival; ezt követően, szükség szerint, a harmadik és negyedik szint súlyaival is.

Az összehasonlítás akkor ér véget, amikor a karakterláncokban megfelelően elhelyezkedő összehasonlító egységek találhatók eltérő súlyokkal. Azok a karakterláncok, amelyek minden négy szinten azonos súlyokkal rendelkeznek, egymással egyenlőek.

Ez az algoritmus (sok további technikai részlettel) adta a 10. számú jelentés nevét — "Unicode Összehasonlító Algoritmus" (UCA).

Ez a helyzet a példánkban a rendezés viselkedése kicsit érthetőbbé válik. Jó lenne összehasonlítani a Unicode szabvánnyal.

A megvalósítások tesztelésére UCA létezik egy speciális teszt, amely a súlytáblázatot, megvalósító DUCET. A súlytáblázatban különböző érdekességek találhatók. Például ott van a mahjong kockák és az európai dominó, valamint a kártyapakliban a színek sorrendje (jelvény 1F000 és tovább). A kártyák a bridzs szabályai szerint vannak elhelyezve — PČBT, a színekben pedig a T,2,3...K sorrendben.

A karakterláncok megfelelő rendezésének manuális ellenőrzése DUCET elég fárasztó lenne, de szerencsére van egy példamutató megvalósítás a Unicode könyvtárból - "Nemzetközi Unicode Komponensek" (ICU).

Ennek a könyvtárnak a weboldalán, amelyet a IBM, különböző bemutató oldalak találhatók, többek között a karakterláncok összehasonlító algoritmusának oldalán.Beírjuk a tesztelő karakterláncainkat az alapértelmezett beállításokkal, és lám, tökéletes orosz rendezést kapunk.

Abakanov Mihail;festő
Jolkina Ella;darukezelő
Ivanov Andrej;szakember
Ivanova Alla;ügyvéd

Egyébként a weboldalon ICU megtalálható a karakterláncok összehasonlításának működésével kapcsolatos pontosítás. A példákban Collation FAQ figyelmen kívül hagyják az aposztrófot és a kötőjelet.

A Unicode segített, de a furcsa viselkedés okait máshol kell keresnünk. sort be. Linux A rendezés a glibc-ben

A GNU Core Utils segédprogram forráskódjának gyors áttekintése

megmutatta, hogy a program lokalizálása lényegében a változó jelenlegi értékének kiíratására korlátozódik sort a hibakeresési módban: $ sort --debug buhg.txt > buhg.srt sort: használva az ‘en_US.UTF8’ rendezési szabályokat LC_COLLATE A karakterláncok összehasonlítása a standard

strcoll

függvénnyel történik, ami azt jelenti, hogy minden érdekes a könyvtárban található. A karakterláncok összehasonlításánakegy bekezdése glibc-t.

Ezen wiki Ez a backend az analitika számára. glibc-t . Ebből a bekezdésből megérthetjük, hogy a rendezés a már ismert algoritmuson alapul,A Unicode rendezési algoritmus glibc-t ) és/vagy egy ahhoz közeli szabványon UCA (ISO 14651Nemzetközi karakterlánc sorrend és összehasonlítás ). Az utóbbi szabványról meg kell jegyezni, hogy a weboldalon (standards.iso.orghivatalosan is nyilvánosnak van nyilvánítva, de a megfelelő link egy nem létező oldalra mutat. A Google néhány oldalt ad a hivatalos oldalak linkjeivel, amelyek elektronikus példányt kínálnak a szabványról több mint száz euróért, de a keresési találatok harmadik-négyedik oldalán közvetlen linkek is találhatók . Összességében a szabvány szinte nem különbözik a ). Az utóbbi szabványról meg kell jegyezni, hogy a weboldalon -tól, de unalmasabban olvasható, mivel nem tartalmaz élénk példákat a karakterláncok sorrendjének nemzeti sajátosságaira. PDFA legérdekesebb információ a UCAvolt, amely egy linket tartalmazott a

bugkövetőhöz wiki a karakterláncok összehasonlításának megvalósításával kapcsolatosan a . A megbeszélésből megtudhatjuk, hogy a karakterláncok összehasonlításához glibc-tegy táblázatot használnak, glibc-t A Közös Sablon Táblázat ISOCTT ), amelynek címe az (szabvány mellékletében. 2000 és 2015 között ez a táblázat a A beli kódra vonatkozik. ). Az utóbbi szabványról meg kell jegyezni, hogy a weboldalon. 2000 és 2015 között ez a táblázat glibc-t nem volt karbantartója, és elég sokban eltért (legalábbis külsőleg) a jelenlegi szabvány változatától. 2015 és 2018 között zajlott az új táblázat verziójára való alkalmazkodás, és jelenleg van esélyed találkozni a valós életben akár az új táblázat (CentOS 8), akár a régi (verzióban).

Most, hogy minden információnk megvan az algoritmusról és a segédtáblázatokról, visszatérhetünk az eredeti problémához, és megérthetjük, hogyan is kell megfelelően rendezni a sorokat orosz lokalizációban.

ISO 14651/14652

A minket érdeklő táblázat forráskódja szabvány mellékletében a legtöbb disztribúcióban Linux a könyvtárban található /usr/share/i18n/locales/. Maga a táblázat a fájlban található iso14651_t1_common. Aztán ez a fájl a direktívával copy iso14651_t1_common bele van illesztve a fájlba iso14651_t1, amely viszont be van ágyazva a nemzeti fájlokba, többek között a en_US és ru_RU. A legtöbb disztribúcióban Linux minden forrásfájl benne van az alaptelepítésben, de ha nincsenek ott, akkor egy további csomag telepítésére lesz szükséged a disztribúcióból.

A fájl struktúrája iso14651_t1 elsőre rettenetesen szószátyárnak tűnhet, nem nyilvánvaló névadási szabályokkal, de ha jobban megnézed, akkor minden elég egyszerű. A struktúrát a szabvány írja le ISO 14652, amelynek másolatát letöltheted a open-std.orgweboldalról. Egy másik fájlformátum leírását a specifikációkban POSIX tól OpenGroupoldalon olvashatod. Alternatívaként a szabvány olvasása helyett a collate_read be. glibc/locale/programs/ld-collate.c.

funkció forráskódját tanulmányozhatod. A fájl struktúrája a következőképpen néz ki:

Alapértelmezés szerint a karaktert escape karakterként használjuk, és a sor vége a # karakter után kommentként szerepel. Mindkét karaktert felül lehet írni, ahogyan ez a táblázat új verziójában is megtörtént:

escape_char /
comment_char %

A fájlban találkozhatsz tokens formátumával <Uxxxx> vagy <Uxxxxxxxx> (ahol — hexadecimális számjegy). Ez a hexadecimális ábrázolás a Unicode kódpontjaira a x UCS-4 UTF-32 (). Minden egyéb elem szögletes zárójelben (beleértve a). Minden egyéb elem szögletes zárójelben (beleértve <Uxxxx_xxxx>, és hasonlók) egyszerű szöveges konstansnak számítanak, amelyeknek nincs különösebb értelmük a kontextuson kívül. Azt mondja nekünk, hogy a következő adatok az összehasonlító szövegek leírását kezdik.

A sor LC_COLLATE Először meg kell határozni a súlyok neveit az összehasonlító táblázatban és a karakterkombinációk neveit. Általánosságban kétféle név tartozik két különböző entitáshoz, de a tényleges fájlban ezek keverve vannak. A súlyok neveit a következő kulcsszó határozza meg:

collating-symbol kollekciós szimbólum (összehasonlító jel), mivel az azonos súlyú Unicode karakterek egyenértékűnek számítanak az összehasonlítás során.

A szakasz teljes hossza a fájl aktuális revíziójában körülbelül 900 sor. Példákat gyűjtöttem több helyről, hogy megmutassam a nevek önkényességét és néhány nyelvtani mintát.

LC_COLLATE

collating-symbol 
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol ..
collating-symbol  % Garantáltan a legnagyobb szimbólumérték. Tartsa a lista végén
...
collating-element  from ""
collating-element  from ""

collating-symbol regisztrálja a karakterláncot OSMANYA a súlynevek táblájában
collating-symbol .. regisztrálja a nevek szekvenciáját, amely egy előtagból áll S és egy hexadecimális numerikus utótagból 1D000 tól 1D35F.
FFFF be. collating-symbol nagy pozitív egész számnak tűnik hexadecimális számrendszerben, de <SFFFF> ez csak egy név, ami úgy nézhet ki, mint <VERYBIGVAL>
név <U0413> a kódpont kódolása jelenti UTF-32
collating-element from "" új nevet regisztrál a két Unicode pont számára.

Amikor a súlynevek meg vannak határozva, akkor a tényleges súlyok beállításra kerülnek. Mivel az összehasonlítás során csak a nagyobb-kisebb viszonyok számítanak, a súlyokat egyszerű névlistázási sorrendben határozzák meg. Először a "könnyebb" súlyokat, aztán a "nehezebbeket" sorolják fel. Emlékeztetnék, hogy minden Unicode karakternek négy különböző súlyt rendelnek, melyek itt egyetlen rendezett sorrendbe kerülnek. Elméletileg bármely szimbolikus név használható bármelyik négy szinten, de a megjegyzések azt mutatják, hogy a fejlesztők elképzelésükben szétválasztják a neveket szintek szerint.

% Szimbolikus súly besorolások

% Harmadik szintű súly besorolások




...
% Második szintű súly besorolások

 % ÖSSZEFŰZŐ ALACSONY VONAL
 % ÖSSZEFŰZŐ FELSŐ VESSZŐ
 % ÖSSZEFŰZŐ FORDÍTOTT FELSŐ VESSZŐ
...
% Első szintű súly besorolások
 % HORIZONTÁLIS TABULÁCIÓ
 % ÚJSOR
 % VERTIKÁLIS TABULÁCIÓ
...
 % CIRILL KIS BETŰ DE
 % CIRILL KIS BETŰ KOMI DE
 % CIRILL KIS BETŰ DJE
 % CIRILL KIS BETŰ KOMI DJE
 % CIRILL KIS BETŰ GJE
 % CIRILL KIS BETŰ ZE LEFOKOZÓVAL
 % CIRILL KIS BETŰ IE
 % CIRILL KIS BETŰ IE BREVE-TEL
 % CIRILL KIS BETŰ UKRÁN IE
 % CIRILL KIS BETŰ ZHE

Végre itt a súlytáblázat.

A súly szakasz kulcsszavakkal van zárva sorokba order_start és order_end. További paraméterek order_start meghatározzák, hogy az egyes összehasonlítási szinteken melyik irányba néznek a sorok. Alapértelmezetten a forwardparaméter van használatban. A szakasz törzse olyan sorokból áll, amelyek a karakterkódot és négy súlyát tartalmazzák. A karakterkódot a karakter maga, a kódpont vagy egy korábban meghatározott szimbolikus név képviselheti. A súlyok szintén megadhatók szimbolikus nevekkel, kódpontokkal vagy magukkal a karakterekkel. Ha kódpontokat vagy karaktereket használnak, akkor a súlyuk megegyezik a kódpont numerikus értékével (a Unicode táblázat pozíciójával). Az egyértelműen nem feltüntetett karaktereket (ahogyan én értem) úgy kezelik, hogy a táblázatban az elsődleges súlyuk megegyezik a Unicode táblázat pozíciójával. A speciális súlyérték IGNORE azt jelenti, hogy az adott összehasonlítási szinten az adott karaktert figyelmen kívül hagyják.

A súlyok szerkezetének bemutatásához három eléggé nyilvánvaló szakaszt választottam:

azok a karakterek, amelyeket teljesen figyelmen kívül hagynak
a háromszámmal egyenértékű karakterek az első két szinten
a cirill ábécé kezdete, amely nem tartalmaz diakritikus jeleket, ezért alapvetően az első és harmadik szint szerint rendeződik.

order_start forward;forward;forward;forward,position
 IGNORE;IGNORE;IGNORE;IGNORE % NULL (in 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % START OF HEADING (in 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % START OF TEXT (in 6429)
...
 ;;; % DIGIT THREE
 ;;; % FULLWIDTH DIGIT THREE
 ;;; % PARENTHESIZED DIGIT THREE
 ;;; % DIGIT THREE FULL STOP
 ;;; % MATHEMATICAL BOLD DIGIT THREE
...
 ;;; % CYRILLIC SMALL LETTER A
 ;;; % CYRILLIC CAPITAL LETTER A
 ;;; % CYRILLIC SMALL LETTER A WITH BREVE
 ;;; % CYRILLIC SMALL LETTER A WITH BREVE
...
 ;;; % CYRILLIC SMALL LETTER BE
 ;;; % CYRILLIC CAPITAL LETTER BE
 ;;; % CYRILLIC SMALL LETTER VE
 ;;; % CYRILLIC CAPITAL LETTER VE
...
order_end

Most visszatérhetünk a cikk elején található példák rendezéséhez. A csapda itt rejlik a súlytábla ezen részében:

IGNORE;IGNORE;IGNORE; % SPACE
 IGNORE;IGNORE;IGNORE; % EXCLAMATION MARK
 IGNORE;IGNORE;IGNORE; % QUOTATION MARK
...

Nyilvánvaló, hogy ebben a táblázatban a írásjelek a táblázatból származnak. ASCII (a szóközt is beleértve) a karakterek összehasonlításánál szinte mindig figyelmen kívül van hagyva. Kivételt képeznek azok a karakterláncok, amelyek mindenben megegyeznek, kivéve az azonos pozíciókban található írásjeleket. Az én példám karakterláncai (a rendezés után) a következőképpen néznek ki az összehasonlító algoritmus számára:

Abakanov Mihály festő
Jelkin Andréa lakatos
Ivanov Anna festő
Ivanov András ács

Figyelembe véve, hogy a súlytáblázatban a nagybetűk a cirill ábécében a kisbetűk után következnek (a harmadik szinten <CAP> nehezebb, mint <MIN>), a rendezés teljesen helyesnek tűnik.

Amikor a változót LC_COLLATE=C beállítjuk, egy speciális táblázat töltődik be, amely byte-alapú összehasonlítást határoz 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'fe', L'xff'
};

Mivel a Unicode-ban a Ё kódpont megelőzi az A betűt, az azonosítható karakterláncok ennek megfelelően rendeződnek.

Szöveges és bináris táblák.

Nyilvánvaló, hogy a karakterláncok összehasonlítása egy rendkívül gyakori művelet, míg a táblázat elemzése szabvány mellékletében meglehetősen költséges eljárás. A táblához való hozzáférés optimalizálásához a parancsot bináris formába fordítja. localedef.

A parancs localedef paraméterekként egy nemzeti jellemzőit tartalmazó fájlt (opció -i), amelyben az összes karakter Unicode-pontokkal van ábrázolva, és egy fájlt, amely a Unicode-pontok meghatározott karakterkódolására vonatkozik (opció -f). A művelet során bináris fájlokat hozhatunk létre az adott nyelvhez, az utolsó paraméterben megadott névvel.

Glibc kétféle bináris fájlt támogat: "hagyományos" és "modern".

A hagyományos formátumot feltételezi, hogy a nyelvi név egy almappa neve a /usr/lib/locale/. Ebben az almappában találhatók a bináris fájlok. LC_COLLATE, LC_CTYPE, LC_TIME stb. A fájl LC_IDENTIFICATION tartalmazza a nyelvi környezet hivatalos nevét (amely eltérhet az almappa nevétől) és megjegyzéseket.

A modern formátum azt feltételezi, hogy minden nyelvi környezet egy közös archívumban lesz tárolva, /usr/lib/locale/locale-archive, amelyet a virtuális memória minden olyan folyamat számára elérhetővé tesz, amely használja. glibc-t. A modern locale name undergoes some canonicalization — only digits and letters, converted to lowercase, remain in encoding names. Thus hu_HU.KOI8-R, it will be saved as hu_HU.koi8r.

Input files are searched in the current directory as well as in the directories /usr/share/i18n/locales/ és /usr/share/i18n/charmaps/ for files szabvány mellékletében and encoding files, respectively.

For example, the command

localedef -i hu_HU -f MAC-CYRILLIC hu_HU.MAC-CYRILLIC

will compile a file /usr/share/i18n/locales/ru_RU using the encoding file /usr/share/i18n/charmaps/MAC-CYRILLIC.gz and will save the result in /usr/lib/locale/locale-archive under the name hu_HU.maccyrillic

If you set the variable LANG=en_US.UTF-8 then glibc-t it will look for binary locale files in the following sequence of files and directories:

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

If a locale appears in both traditional and modern formats, priority is given to the modern one.

You can view the list of compiled locales with the command locale -a.

Preparing your comparison table

Now, armed with knowledge, you can create your own ideal string comparison table. This table should correctly compare Russian letters, including the letter Ё, while considering punctuation marks according to the table. ASCII.

The process of preparing your sorting table consists of two stages: editing the weight table and compiling it into binary form with the command localedef.

To allow the comparison table to be adjusted with minimal editing costs, the format ISO 14652 provides sections for adjusting the weights of the existing table. The section begins with the keyword reorder-after and an indication of the position after which the replacement is made. The section ends with the line reorder-end. If you need to adjust multiple sections of the table, a section is created for each of these areas.

I copied the new versions of the files iso14651_t1_common és ru_RU from the repository glibc-t to my home directory ~/local/share/i18n/locales/ and slightly edited the section LC_COLLATE be. ru_RU. The new versions of the files are fully compatible with my version glibc-t. If you want to use the old versions of the files, you will need to change the symbolic names and the place from which the replacement in the table begins.

LC_COLLATE
% Másolja a sablont az ISO/IEC 14651 alapján
copy "iso14651_t1"
reorder-after 
 ;;; % SPACE
 ;;; % FELKIÁLTOJEL
 ;;; % IDÉZŐJEL
...
 ;;; % JOBB FONÓ KAPCSOLÓJEL
 ;;; % TILDE
reorder-end
END LC_COLLATE

Valójában a mezőket kellett volna megváltoztatni LC_IDENTIFICATION úgy, hogy a helyi beállításra mutassanak hu_HU, de az én példámban nem volt szükség rá, mivel kizártam a helyi beállítások kereséséből a locale-archive.

Ahhoz, hogy localedef a fájlokat a mappámban a I18NPATH változón keresztül, egy további könyvtár hozzáadásával lehet keresni a bemeneti fájlokhoz, és a bináris fájlok tárolására szolgáló könyvtár megadható '/'-al elválasztott útként:

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

POSIX azt feltételezi, hogy a LANG teljes útvonalakat lehet írni a helyi beállítások fájlok könyvtáraihoz, amelyek a '/'-ral kezdődnek, de glibc-t be. Linux minden útvonalat az alap könyvtártól számít, amelyet a LOCPATHváltozó segítségével lehet felülírni. A beállítás után LOCPATH=~/.local/lib/locale/ minden, a lokalizálással kapcsolatos fájl csak a mappámban lesz keresve. A helyi beállítások archívumát a beállított változóval LOCPATH figyelmen kívül hagyásra kerül.

Íme a döntő teszt:

$> LANG=hu_HU.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
Abakánov Mihály;festő
Jelkinina Ella;darukezelő
Ivanov András;kovács
Ivanova Alla;ügyvéd

Hurrá! Sikerült!

A hibák javítása

Már válaszoltam a szálak rendezésével kapcsolatos kérdésekre, de még mindig van néhány kérdés a látható és láthatatlan hibákról.

Térjünk vissza az eredeti feladathoz.

És a program sort és a program join ugyanazokat a szövegösszehasonlító funkciókat használja a glibc-t. Hogyan lehetett az, hogy join hibát adott a rendezés során a sort mellett a helyi beállításokban en_US.UTF-8? Ответ прост: sort teljesen hasonlít, míg join csak a kulcsot hasonlítja össze, amely alapértelmezetten a sor első szóközig terjed. Az én példámban ez hibaüzenethez vezetett, mivel a kezdeti szavak rendezése nem egyezett meg a teljes sorok rendezésével.

A helyi beállítás "C" garantálja, hogy a rendezett szálak első részei az első szóközig rendezve lesznek, de ez csak eltakarja a hibát. Olyan adatokat lehet találni (azonos vezetéknevű emberek, de különböző keresztnevekkel), amelyek hibaüzenet nélkül is helytelen eredményt adnak a fájlok összefűzéséhez. Ha azt szeretnénk, hogy join Ha a fájlok sorait név szerint egyesíti, a helyes módszer a mezőelválasztó egyértelmű megadása és a kulcsmező szerinti rendezés, nem pedig az egész sor szerint. Ebben az esetben a fúzió helyesen fog végbemenni, és egyetlen lokalizációban sem lesz hiba:

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

Sikeresen végrehajtott példa a kódolásban CP1251 további egy hibát tartalmaz. A helyzet az, hogy az általam ismert összes disztribúcióban Linux a csomagokból hiányzik a lefordított lokalitás hu_HU.CP1251. Ha a lefordított lokalitás nem található, akkor sort csendben byte-összehasonlítást végez, ahogyan ezt észleltük.

Egyébként van egy kis hiba is, ami a lefordított lokalitások hiányához kapcsolódik. A parancs LOCPATH=/tmp locale -a felnőtt minden lokalitás listáját fogja kiadni locale-archive, de a beállított változóval LOCPATH minden program számára (beleértve magát is locale) ezek a lokalitások 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

Zárás

Ha Ön programozó, aki azt hiszi, hogy a sorok byte-ok halmaza, akkor az Ön választása LC_COLLATE=C.

Ha Ön nyelvész vagy szótárszerkesztő, akkor jobb, ha saját lokalitását lefordítja.

Ha Ön egyszerű felhasználó, akkor meg kell szoknia, hogy a parancs ls -a fájlokat ad ki, amelyek ponttal kezdődnek, amig a betűvel kezdődő fájlokkal vegyesen, és Midnight Commander, ami saját belső funkcióit használja a nevek rendezésére, a ponttal kezdődő fájlokat a lista elejére helyezi.