SortKit

České řazení

Pod pojmem řazení se rozumí takové přeuspořádání struktury, aby její prvky tvořily monotónní posloupnost. Často se též používá méně správný výraz třídění. Srdcem každého řadicího algoritmu [1], [2] je příkaz k porovnání dvou prvků. Je-li kritériem monotónnosti (třídicím klíčem) číslo, je porovnání triviální. Podívejme se na obtížnější případ, kdy se mají porovnávat textové řetězce obsahující znaky s diakritickými znaménky.

Procesory Intel mají pro porovnávání řetězců strojovou instrukci REP CMPS, ta však porovnává podle pořadí znaků, v jakém jsou definovány v použité kódové stránce, tedy nesprávně.
Způsob řazení, které se v praxi používá ve slovnících, rejstřících a lepších programech, u nás kodifikuje státní norma [3]. Vzhledem k obtížné algoritmizovatelnosti některých požadavků normy se v osobních počítačích zpravidla implementuje zjednodušená varianta, viz [4], [5], [6], [7].

Pořadí písmen určuje v první řadě jejich sémantika, nikoli jejich kódová hodnota v tabulce ASCII. To znamená, že slovo začínající písmenem A bude řazeno před slovo začínající B bez ohledu na to, je-li zapsáno jako velké či malé a má-li čárku, přehlásku nebo jiné diakritické znaménko. Oba porovnávané řetězce je tedy nutno nejprve převést do redukované abecedy, která stírá rozdíly ve velikosti písmen a odstraňuje diakritiku. Kromě 10 číslic a 26 písmen obsahuje redukovaná abeceda ještě čtyři souhlásky s háčkem ČŘŠŽ, které mají také primární řadicí platnost. Po překódování do této omezené abecedy již lze oba řetězce porovnat strojově podle kódových hodnot znaků redukované abecedy. Není podstatné, jakým znakům v ASCII tabulce odpovídá překódovaný text, důležitá je jen jejich relativní hodnota - řadicí váha.

Řazené
slovo
Stav po
I.vážení
Výsledné
pořadí
sijeSIJE1.
šijeŠIJE2.?
šíjeŠIJE2.?
ŠíjeŠIJE2.?

Jsou-li po převodu do redukované abecedy oba řetězce různé, je tím jejich pořadí určeno, jinak musíme uplatnit jemnější kritérium, kterým jsou diakritická znaménka. Velikost písmen se v této druhé fázi ještě neuplatňuje. Výskyt diakritického znaménka zvyšuje řadicí váhu znaku takto:

  1. bez diakritiky
  2. tečka nad písmenem (dot above)
  3. čárka (acute)
  4. vokáň (circumflex)
  5. breve
  6. háček (caron) pokud nemá i primární řadicí platnost
  7. přehláska (diaeresis)
  8. dlouhá přehláska (double acute)
  9. kroužek (ring above)
  10. ocásek (ogonek)
  11. přeškrtnutí (stroke)
  12. cedilla
Řazené
slovo
Stav po
I.vážení
Stav po
II.vážení
Výsledné
pořadí
sijeSIJESIJE1.
šijeŠIJEŠIJE2.
šíjeŠIJEŠÍJE3.?
ŠíjeŠIJEŠÍJE3.?

Pokud ani ve druhém průchodu nedojde k určení pořadí, následuje transformace řetězců podle třetí tabulky vah, která již rozlišuje jak diakritiku, tak i velká a malá písmena. Pro zjednodušení se již v této třetí fázi obvykle rozlišují také nealfanumerické znaky.

Řazené
slovo
Stav po
I.vážení
Stav po
II.vážení
Stav po
III.vážení
Výsledné
pořadí
sijeSIJESIJEsije1.
šijeŠIJEŠIJEšije2.
šíjeŠIJEŠÍJEšíje3.
ŠíjeŠIJEŠÍJEŠíje4.

K uspokojivému řazení tedy potřebujeme nejméně tři tabulky řadicích vah pro každé z možných kódování češtiny. Ruční sestavování takových tabulek je zdlouhavé, proto vznikl program SortKit, který je umí vygenerovat z uživatelsky mnohem příjemnějšího zadání požadovaného pořadí znaků. SortKit generuje nejen samotné váhové tabulky, ale rovnou celý zjednodušený trojfázový řadicí program, takže je snadné správnou funkci navrhované tabulky ihned po jeho kompilaci ověřit.

Ne všechny požadavky korektního řazení jsou splnitelné pouhou volbou vah a komplikují proto porovnávací algoritmus. Znaky ch,Ch a CH se v českém jazyce považují za dvojhlásky řazené mezi H a I. Pro zpracování této anomálie je třeba v porovnávací proceduře zavést pomocnou dvouznakovou proměnnou (v generovaných kódech je nazývána Diphtong), která si pamatuje právě načtený a předchozí znak a umožňuje tak detekovat dvojhlásky. V případě výskytu dvojice ch,Ch nebo CH se změní váha znaku c uložená v předchozím kroku za váhu znaku i. Místo váhy druhého písmene dvojhlásky (h) se uloží nejnižší možná váha 0, případně (je-li to třetí průchod) váha 0,1 nebo 2 podle velikosti dvojhlásky. Dvojice znaků cH se za dvojhlásku nepovažuje. Aby nedocházelo ke konfliktu takto "zvážené" dvojhlásky CH s případnou dvojicí imezera, program SortKit rezervuje první tři váhy jako postfix dvojhlásky a normálním znakům včetně mezery přiděluje váhy od 4 nahoru.

Jsou-li slova v porovnávaném řetězci oddělena více než jednou mezerou, mají se řadit tak, jako by byla oddělena právě jednou mezerou. Případné počáteční mezery se rovněž ignorují. K implementaci této vlastnosti lze využít výše zmíněnou proměnnou Diphtong, kterou na počátku překladu inicializujeme mezerami a načítané znaky ignorujeme, dokud jsou v této proměnné dvě mezery.

Cizojazyčná písmena by měla být řazena podle jejich fonetického přepisu do češtiny, např. řecké písmeno alfa α jako alfa, německé ostré ß jako ss apod. Tato vlastnost je v generovaných příkladech splněna jen částečně, přiřazením váhy odpovídající fonetickému ekvivalentu.

Někdy je vhodné při porovnávání určité znaky vynechávat. Například při sestavování rejstříku chceme mít hesla řazena bez ohledu na to, zda jsou či nejsou uzavřena v úhlových závorkách. Podle normy se ale závorky a podobné symboly mají řadit až za všechna písmena a číslice. Přiřaďme tedy znakům < a > v rozporu s normou řadicí váhu 0. Pokud porovnávací program bude znaky s nulovou vahou ignorovat, dostáváme očekávané pořadí podle následující tabulky:

Řazené
slovo
Po zvážení Výsledné
pořadí
<TABLE>TABLE1.
TABULKATABULKA2.
<TBODY>TBODY3.
TEXTYTEXTY4.

Popis programu SortKit

SortKit je pomocná utilita pro programátory, kteří potřebují implementovat ve svých výtvorech české řazení. Pracuje jako kompilátor, který načítá definice řadicích vah ze vstupního textového souboru a vytváří z nich tabulku vah v syntaxi zvoleného cílového jazyka. Název vstupního souboru je třeba zadat jako parametr, implicitní přípona je .DSW. Výstupem je nejen samotná váhová tabulka trojfázového řazení, ale obsahuje i jednoduchou implementaci bublinkového třídění včetně procedury pro porovnání textových řetězců podle výše uvedených zásad.
Cílový programovací jazyk se volí parametrem z těchto možností:

ParametrJazykGenerovaná
přípona
Odladěno programem
/AAssembler.ASMTurbo Assembler 2
/NNetwide Assembler.NASNASMW 0.98
/CC.CMicrosoft C/C++ 7.0
/PPascal.PASTurbo Pascal 5
/B-.BIN-

Pozn. Varianta /N produkuje 32bitovou konsolovou aplikaci pro Windows. K jejímu sestavení je kromě assembleru NASM [8] zapotřebí knihovník ALIB [9] a linker ALINK [10], vše freeware.
Při použití parametru /B se negeneruje zdrojový kód, ale pouze binární data tabulky vah. Výstupní soubor má délku 3*256=768.

Pokyny ke kompilaci jsou uvedeny jako poznámka v záhlaví cílového programu. Nevybereme-li žádný cílový jazyk, SortKit provede pouze syntaktickou kontrolu vstupního souboru. Cílový soubor má název shodný se vstupním souborem, jen přípona .DSW je změněna podle zvoleného programovacího jazyka.

Dalšími parametry programu SortKit lze volit kódování češtiny použité v komentářích výsledného programu:

ParametrKódování komentářů
/ISOISO-8859-2
/KAMCP895 Kamenických
/LATCP852 PC Latin2
/WINCP1250 Windows CE

Bez ohledu na zvolené kódování poznámek by uživatel měl zajistit, aby vstupní soubor obsahoval definice pouze těch znaků, které jsou obsaženy v kódu, pro který je tabulka zamýšlena. Vzorové definice vah přiložené v distribuci SortKit tento požadavek splňují, viz např. soubor VAHY1KAM.DSW.

Syntaktická pravidla pro zdrojový soubor DSW

Znaky se stejnou řadicí vahou musejí být definovány na jednom řádku. Mohou být definovány dekadicky (0..255), hexadecimálně (0x00..0xFF nebo 00h..FFh) nebo řetězcem ohraničeným apostrofy či uvozovkami. Definice na jednom řádku se oddělují čárkou ',' nebo výpustkou '..'.
Zalamování řádků není podporováno, ale délka řádku není omezena a zápis lze zkracovat používáním výpustek, které reprezentují souvislou řadu znaků včetně krajních. Za definicí může být umístěna poznámka odělená středníkem.
Příklad platného řádku: "()",0x5B..0x5D,123..125 ; kulaté,hranaté,složené závorky a lomítka

Všechny znaky uvedené na prvním řádku dostanou řadicí váhu 0. Váhy 1 až 3 jsou rezervovány pro rozlišení dvojhlásek, takže znaky na druhém řádku dostanou váhu 4, na třetím řádku 5 atd.
Zdrojový soubor musí obsahovat definice vah pro tři průchody, tabulka každého průchodu musí být v souboru DSW zahájena řádkem obsahujícím hvězdičku * v prvním sloupci.
V distribuci SortKit jsou přibaleny výchozí definiční soubory pro čtyři nejběžnější kódování češtiny (soubory VAHY1???.DSW). Repertoár znaků v českých kódových stránkách a jejich anglické názvy uvedené jako komentář vycházejí z upravené definice Unicode [11],[12],[13],[16].

Chybová hlášení programu SortKit

SortKit kontroluje správnost syntaxe zadaných znaků, jejich jedinečnost v rámci každé ze tří tabulek a varuje při vynechání definice některého z 3*256 znaků. Příklady chybových zpráv:
**Error** BADFILE.DSW(8) sloupec 6: chyba syntaxe. *Warning* BADFILE.DSW(14) sloupec 10: vícenásobná definice znaku 17 *Warning* BADFILE.DSW(17) Tab.2: nedefinovaná váha znaku 252..255

Formát chybových hlášení programu SortKit je kompatibilní s Turbo Assemblerem pro snadnou integraci do programátorských editorů. Za názvem zdrojového souboru je v závorce uvedeno číslo chybného řádku, což např. při spouštění SortKitu z editoru MultiEdit [14] umožňuje automaticky nastavovat kurzor na chybný řádek zdrojového textu.

Licenční ujednání k programu SortKit

Tento program je volně šířitelný, za jeho používání nejsou vyžadovány žádné poplatky. Distribuce by měla obsahovat tyto soubory:

 SORTKIT.COM   kompilátor řadicích vah
 SORTKITC.HTM  tento manuál
 SORTKIT.HTM   anglický manuál
 VITSOFT.CSS   stylopis k manuálu
 VAHY1ISO.DSW  vzorové váhy pro kód ISO-8859-2
 VAHY1KAM.DSW  vzorové váhy pro kód CP895 Kamenických
 VAHY1LAT.DSW  vzorové váhy pro kód CP852 DOS Latin 2
 VAHY1WIN.DSW  vzorové váhy pro kód CP1250 Windows
 VZOREK.TXT    pro vyzkoušení správnosti řazení v kódu Kamenických
 VZOREKW.TXT   pro vyzkoušení správnosti řazení v kódu Windows CP1250
 CPP.ZIP       úprava řadicího programu pro jazyk C++
 FILE_ID.DIZ   indentifikátor distribuce pro FTP/BBS

Nové verze SortKit hledejte na stránkách vit$oft freeware [15]. Tamtéž můžete získat univerzální řadicí program OKSORT, který umí využívat binární tabulky produkované utilitou SortKit a nemá omezení co do rozsahu řazených souborů.

[1] Skřivan, J.: Řadicí metody a algoritmy www.fi.muni.cz/~xskrivan/prog/alg/razeni.html
[2] Sort algorithm www.nist.gov/dads/HTML/sort.html
[3] ČSN 01 0181 Abecední řazení. ÚNM Praha 1977.
[4] Havránek, Z.: České třídění pod lupou. BAJT 6/1992.
[5] Herles, I.: SORT česky. BAJT 6/1992.
[6] Dvořák, S.: Čs. norma pro řazení a její realizace ve FoxPro. BAJT listopad 1993.
[7] Pazdziora, J.: České lokalizační projekty www.fi.muni.cz/~adelton/l10n
[8] Netwide Assembler nasm.sourceforge.net
[9] Win32 Import Library generator ALIB alink.sourceforge.net
[10] Linker ALINK alink.sourceforge.net
[11] Unicode character map www.unicode.org
[12] Codepages and Glyphs www.eki.ee/letter
[13] Oblíbené programátorské tabulky www.vitsoft.info/#OPTA
[14] Text Editor MultiEdit www.amcyber.com
[15] vit$oft freeware www.vitsoft.info
[16] Čeština www.cestina.cz