OKsort

 

je program pro trojprůchodové řazení textových nebo databázových typových souborů podle textového klíče v českém jazyce.

Stručná charakteristika

Syntaxe

Názvy vstupního a výstupního souboru se zadávají v tomto pořadí jako parametry příkazu OKsort. Cestu k souborům není nutné uvádět, pak se pracuje v aktuálně nastaveném adresáři. Dlouhé názvy souborů nejsou podporovány. Pokud výstupní soubor při zahájení řazení již existuje, bude obsluha varována dotazem Výstupní soubor už existuje. Přepsat (A/N) ? Tento interaktivní dotaz lze potlačit parametrem /O.

Nebudou-li názvy souborů zadány, OKsort pracuje jako filtr, tzn. čte věty ze systémového vstupu a po seřazení je zapisuje na systémový výstup. Pokud je na příkazové řádce zadán jen jeden soubor, považuje se za vstupní a výsledek jde na systémový výstup. Následující příkazy jsou tedy funkčně shodné:

OKsort  vstup.txt  vystup.txt
OKsort <vstup.txt >vystup.txt

Při použití přesměrovacích operátorů < a > je třeba případné doplňující parametry programu OKsort zadávat před zapsáním prvního přesměrování. Pozor také na to, že při přesměrování výstupu do již existujícího souboru se žádné varovné upozornění nevydává.

Parametry programu OKsort začínají lomítkem, za kterým následuje rozlišující písmeno (na velikost se nehledí). Případné další znaky až do dalšího lomítka jsou považovány za komentář. Některé parametry vyžadují zadání dekadické číselné hodnoty, např. /PositionOfKey=10 znamená, že text, podle něhož se věty řadí, je posunut o 10 bajtů od prvního znaku věty. Tentýž parametr bychom mohli zadat i některým z následujících způsobů:

/Position 10, /pozice:10.znak /P=10, -p10. 
Uvnitř čísla nesmějí být nečíselné znaky (žádné oddělovací mezery). Namísto lomítek mohou parametry začínat i znakem minus.

Typy řazených souborů

Vstupní soubor je složen ze záznamů neboli vět, jejichž pořadí v souboru se seřazením změní. Typový soubor je složen ze záznamů konstantní délky, kterou je nutné zadat jako parametr /R(ecord size)=. Typickým příkladem jsou databázové soubory.

OKsort umí řadit také textové soubory s proměnnou délkou věty. V takovém případě se parametr /R= neuvádí. Za větu je pak považován řádek ukončený znakem LineFeed (ASCII 10).

Specifikace klíče

Při řazení se přeskupuje pořadí záznamů v souboru tak, aby jejich klíče tvořily monotónní posloupnost. Klíč může být podmnožinou záznamu; pokud neurčíme jinak, bere se jako řadicí klíč celá věta. Délku klíče lze zkrátit parametrem /SizeOfKey= a jeho případný posun od počáteční pozice věty parametrem /PositionOfKey=. Pokud bychom chtěli níže uvedenou databázi seřadit podle rodného čísla, bude třeba zadat parametry /P=22 /S=11

0        10        20        30        40        50
|+++++++++|+++++++++|+++++++++|+++++++++|+++++++++|+++
Jana     Nováková     816028/2575 Kolín
Jitka    Novotná      795419/7525 Pečky
Jiřina   Nosková      685821/2755 Praha

Nebyl-li zadán parametr /PositionOfKey=, považuje se posun klíče za nulový. Nebyla-li omezena délka klíče parametrem /SizeOfKey=, je za klíč považován celý zbytek věty až do jejího konce, avšak ne delší než 16384 znaky.

Specifikace řazení

Uvedením parametru /D(escending) způsobí, že OKsort řadí sestupně, tj. věty s klíčem začínajícím písmenem "A" budou na konci. Default je vzestupné řazení.

Dvojice znaků "ch", "Ch" a "CH" jsou považovány za dvojhlásku, která se ve shodě s českým pravopisem řadí mezi "H" a "I". Parametrem /C lze tuto vlastnost vyřadit, např. pokud bychom třídili anglický rejstřík. "CH" se pak řadí mezi "CG" a "CI".

OKsort před porovnáním klíčů kondenzuje nadbytečné mezery a nahrazuje je mezerou jedinou. Mezery na počátku klíče jsou také vynechávány. Díky tomu se následující záznamy řadí podle významových znaků, v tomto případě tedy pořadových číslic:

0        10        20        30        40        50
|+++++++++|+++++++++|+++++++++|+++++++++|+++++++++|+++
  Karel 1.
Karel          2.
        Karel 3.
   Karel  4.

Kondenzaci mezer lze vypnout parametrem /V, pak dostane každá mezera svou řadicí váhu a může tak ovlivňovat pořadí.

Ošetření začátku souboru

Mnohé formáty typových souborů (např. dBIII) začínají hlavičkou, která by měla zůstat tříděním nedotčena. Proto OKsort umožňuje číselným parametrem /HeaderSize= stanovit počet znaků vstupního souboru, které se neúčastní řazení a budou pouze zkopírovány na výstup.

V případě textových souborů parametr /HeaderSize= určuje velikost hlavičky v řádcích, nikoli v bajtech.

Implicitní hodnota parametru /HeaderSize=0.

Ošetření konce souboru

Pokud délka vstupního typového souboru není celočíselným násobkem zadané velikosti věty /RecordSize=, bude poslední neúplný záznam doplněn znaky NULL (ASCII 0).

U textových souborů si OKsort automaticky doplní znak LineFeed v případě, že jím nebyl zakončen poslední řádek vstupního souboru. Některé textové editory doplňují na konec textového souboru ukončující znak ASCII 26, neboli ^Z. Při načítání vstupního textu programem OKsort je koncový znak ^Z vždy odstraňován a připojuje se až po seřazení na konec výstupního souboru. Zadáním parametru /Y se zabrání připojování znaku ^Z na konec textu, naopak parametr /Z zajistí, že tento znak bude vždy připojen. Pokud neuvedeme žádný z parametrů /Y, /Z, bude ^Z připojen pouze v případě, že jím byl zakončen i vstupní soubor.

Řazení českých znaků s diakritikou

OKsort implementuje trojprůchodové řazení podle ČSN 01 0181. V prvním průchodu se klíče redukují odstraněním diakritiky a velikosti do zjednodušené abecedy obsahující písmena ABCČDEFGHCHIJKLMNOPQRŘSŠTUVWXYZŽ. Pouze v případě, že takto redukované klíče jsou shodné, se bere do úvahy ostatní diakritika. Nelze-li klíče rozlišit ani po této druhé transformaci, rozlišuje se ve třetím průchodu i velikost písmen. Číslice se řadí za písmena, ostatní znaky s výjimkou netisknutelných mezerotvorných oddělovačů (white spaces) až za číslice. Řídicím znakům (ASCII < 32) s výjimkou mezerotvorných ASCII 9..13 je přidělena speciální řadicí váha 0, která se ignoruje, a proto jejich případný výskyt v klíči pořadí vůbec neovlivňuje.

Parametrem /I, /K, /L nebo /W se definuje, že klíče obsahují text v kódování ISO-8859-2, Kamenických, PC Latin 2 nebo Windows CP1250. Při potřebě jiného kódování musí uživatel vyrobit vlastní tabulku řadicích vah.

Zdrojový kód váhových tabulek interně používaných programem OKsort je uveden v utilitě SORTKIT dostupné na vit$oft freeware. Pomocí SORTKIT lze vygenerovat řadicí váhové tabulky s odlišným kódováním nebo pořadím znaků a aplikovat je parametrem OKsort /T=TABULKA.BIN. Externí tabulka musí mít délku 3*256=768 bajtů.

Neobsahuje-li vstupní soubor znaky ASCII > 127, můžeme urychlit řazení zadáním parametru /ASCII. V tomto případě se vynechává druhý porovnávací průchod. Pokud by se ovšem nějaké znaky s diakritikou přece jen vyskytly, budou zařazeny až na konec a jejich pořadí nebude definováno.

Nezadáme-li žádný z parametrů /A,/I,/K,/L,/W,/T, OKsort se pokusí detekovat použité kódování porovnáním frekvencí výskytů českých diakritických znaků v celém vstupním souboru.

Hlášení programu

Jakmile je načten vstupní soubor, OKsort ohlásí na obrazovce zjištěné služební údaje: názvy vstupního a výstupního souboru, zadané nebo detekované kódování, velikost souboru, počet vět, spotřebu paměti a nakonec i dobu potřebnou k seřazení. Tyto informace vystupují na standardní chybový výstup, k jejich případnému potlačení slouží parametr /N. Pokud dojde v průběhu řazení k chybě, parametr /N bude ignorován a chybová zpráva se vždy zobrazí. Chyba je indikována také nenulovou hodnotou návratového kódu ERRORLEVEL.

Při zadání chybného parametru, např. /?, se zobrazí stručná nápověda na standardní výstup. Podrobnější návod (tento text) se vypíše po zadání parametru /Manuál. Kódování češtiny ve stručné nápovědě a v manuálu je buď Kamenických nebo PC Latin 2, podle zadání parametru /K nebo /L. Nebylo-li OEM kódování specifikováno, určí se autodetekcí podle fontu zavedeného ve videoadaptéru.

Omezení programu OKsort

Program vyžaduje DOS nebo kompatibilní dosovou konzoli, procesor i386 nebo vyšší a alespoň 256 KB konvenční paměti. Je-li k dispozici víc konvenční paměti, bude využita jako vyrovnávací a urychlí se běh programu. Pro svou činnost vyžaduje OKsort další pomocnou paměť. Její objem lze odhadnout tak, že k délce vstupního souboru přičteme na každý záznam 4 bajty (při pevné délce) nebo 8 bajtů při proměnné délce záznamu, minimálně 128 KB. Např. textový soubor obsahující 1 048 576 řádků o průměrné délce 7 znaků vyžaduje alokaci 1048576*(7+8) = 15 MB pomocné paměti. OKsort umožňuje alokovat až 256 MB pomocné paměti, ovšem řazení tak velkých souborů je pak omezeno spíše neúnosně dlouhou dobou zpracování.

Další omezení:
max. délka věty           268 402 688 bajtů
max. délka klíče               16 384 znaky
max.počet záznamů          13 420 544 (proměnná délka)
max.počet záznamů          44 736 512 (pevná délka)

Hospodaření s pamětí

Pomocná paměť se nejprve alokuje v rozšířené paměti (XMS), po jejím vyčerpání v přídavné paměti (EMS), pak ve formě odkládacího souboru ve virtuální paměti - paměťovém disku a nakonec jako pomocný soubor na pevném disku. OKsort tak využije v DOSu veškerou operační paměť bez ohledu na to, zda ji uživatel konfiguroval jako rozšířenou XMS (ovladačem HIMEM), přídavnou EMS (EMM386), virtuální VMS (RAMDRIVE) nebo diskovou odkládací DMS (SMARTDRV).

Množství alokované paměti OKsort vypisuje v úvodním hlášení. Pomocí parametrů /XMS= a /EMS= lze využití těchto prostředků omezit na určený počet kilobajtů (zaokrouhluje se na násobky 16KB dolů). Např. /X=0 /E=50 zakáže používání paměti XMS a limituje využití paměti EMS na 48 KB.

V případě, že je vyčerpán volný diskový prostor pro paměť DMS, řazení se zruší s chybovým hlášením

Chyba alokace paměti, málo místa pro odkládací soubor D:\BDCOJABF

Diskový odkládací soubor se dočasně vytváří pod náhodně generovaným jménem na disku specifikovaném v environmentu proměnnou TMP= nebo TEMP=. Pokud tato proměnná není nastavena nebo pokud ukazuje na RAMDISK, zkouší všechny logické disky počínaje C:. Při chybě alokace pak může pomoci nastavení SET TMP=D:\ na disk s dostatkem volného prostoru.

Použitý algoritmus

Pro předtřídění načtených paměťových stránek používá OKsort algoritmus Quick Shell Sort, pro spojování stránek do výstupního souboru algoritmus binárního zatřiďování.

Průběh obou fází řazení je zobrazován procentním ukazatelem.

Abecední přehled parametrů

/A Řazení podle kódu ASCII (bez diakritiky)
/C CH nepovažovat za dvojhlásku, řadit mezi CG a CI
/D Sestupné řazení, tj od Ž po A
/E= Omezit využití přídavné (expanded) paměti EMS na zadaný počet KB
/H= velikost hlavičky ve znacích (je-li definováno /R=) nebo v řádcích
/I Řazení podle kódu ISO-8859-2
/K Řazení podle kódu Kamenických (CP 895)
/L Řazení podle kódu PC Latin2 (CP 852)
/M Zobrazit tento manuál k programu OKsort na systémový výstup
/N Nezobrazovat žádné pomocné služební informace
/O Nežádat o povolení k přepisu existujícího výstupního souboru
/P= Posun klíče od počátku záznamu
/R= Řazený soubor obsahuje záznamy pevné délky
/S= Počet znaků v klíči
/T= Řazení podle trojfázové tabulky řadicích vah uložené v ext.souboru
/V vícenásobné mezery v řadicím klíči nespojovat do jedné
/W Řazení podle kódu Windows (CP 1250)
/X= Omezit využití rozšířené (extended) paměti XMS na zadaný počet KB
/Y Na konec seřazeného textu nepřidávat znak EOF=^Z
/Z Na konec seřazeného textu vždy přidat znak EOF=^Z