Tento článek vznikl jako reakce na diskuzi v
javovské konferenci [email protected] v listopadu 2009. Předmětem
diskuze zde bylo řazení podle ČSN 97 6030. V dalším
textu se nebudeme této normy striktně držet. Cílem
článku není popsat implementaci řazení podle normy,
ale spíše ukázat možnosti, které máme v Javě k
dispozici pro abecední řazení řetězců.

Chceme-li seřadit množinu řetězců, musíme umět
řetězce porovnávat. Tj. musíme umět rozhodnout, zda
je jeden řetězec „menší než“ druhý. Při porovnávání
dvou řetězců postupujeme po znacích zleva doprava a
znaky v jednom řetězci srovnáváme se znaky na stejné
pozici ve druhém řetězci. Uspořádání českých znaků
definuje česká abeceda:

a, á, b, c, č, d, ď, e, é, ě, f, g, h, ch,
i, í, j, k, l, m, n, ň, o, ó, p, q, r, ř, s, š, t, ť,
u, ú, ů, v, w, x, y, ý, z, ž.

Rozlišujeme tzv. primární, sekundární a terciární
řadicí platnost znaků. Primární řadicí platnost mají
znaky

a, b, c, č, d, e, f, g, h, ch, i, j, k, l,
m, n, o, p, q, r, ř, s, š, t, u, v, w, x, y, z, ž.


Sekundární řadicí platnost mají znaky

á, ď, é, ě, í, ň, ó, ť, ú, ů, ý.

Nejprve hledáme rozdílné znaky s primární řadicí
platností. Znaky se sekundární řadicí platností
nahradíme pro tuto fázi znaky bez diakritiky (á nahradíme a, ď
nahradíme d, atd.) a nepřihlížíme k
rozdílům ve velikosti písmen (a je stejné
jako A, b jako B,
atd.). Pokud najdeme různé znaky s primární řadicí
platností, je uspořádání řetězců dáno první (tj.
nejlevější) dvojicí takových znaků. Např. slovo drak bude před slovem vlak, protože
d je v abecedě před v, slovo
kanoe bude před slovem kánon,
protože e je před n a s á se v této fázi pracuje jako s a a
slovo káď bude před slovem kat,
protože d je před t (s ď pracujeme jako s d). Pokud
nenajdeme rozdíly ve znacích s primární řadicí
platností a řetězce mají různou délku, bude kratší
řetězec před delším. Např. slovo kůň bude
před slovem kuna, protože ů a
ň mají sekundární řadicí platnost. Jsou-li
řetězce stejně dlouhé, hledáme rozdíly ve znacích se
sekundární řadicí platností, přičemž opět
nepřihlížíme k rozdílům ve velikosti písmen.
Uspořádání řetězců je, stejně jako u znaků s primární
řadicí platností, dáno první dvojicí rozdílných
znaků. Např. slovo kanón bude před slovem
kaňon, protože n je v abecedě
před ň.

Nenajdeme-li rozdíly ve znacích s primární ani
sekundární řadicí platností, hledáme rozdíly ve
velikosti písmen (terciární řadicí platnost). Velká
písmena obvykle řadíme před malá. Např. slovo Brod bude před slovem brod.

Písmena z jiných národních abeced obvykle řadíme
takto:

à, â, ä, ą, ç, è, ê, ľ, ł, ô, ö, ŕ, ü, ż.


Číslice řadíme podle jejich číselné hodnoty za
poslední písmeno abecedy. Mají primární řadicí
platnost. Skupiny číslic řadíme podle číselné hodnoty
číslic. Např. 2 bude před 21 a
to bude před 3.

Písmena některých abeced, např. řecké a azbuky,
řadíme podle přepisu do české abecedy. Např. α
přepisujeme jako alfa.

Mezeru řadíme před první znak abecedy. Další znaky
řadíme za číslice obvykle v tomto pořadí:

• interpunkční znaménka,
• všechny tvary uvozovek,
• ustálené značky,
• matematické symboly.

Řazení v Javě

K řazení řetězců podle pravidel národních abeced
slouží v Javě třídy Collator a RuleBasedCollator z balíku java.text.

List<String> p = ...;

Collator c = Collator.getInstance(new Locale("cs"));

Collections.sort(p, c);

Metoda Collator.getInstance vrátí
instanci třídy RuleBasedCollator.
Nevýhodou tohoto způsobu řazení je, že jsou
ignorovány mezery a velká písmena jsou řazena za
malá. Např. ulice Na Zbořenci bude řazena
za ulicí Navrátilova a městská část Újezd bude za slovem újezd.

Třída RuleBasedCollator používá při
porovnávání řetězců uspořádání znaků, které dostane
jako parametr do konstruktoru. Uspořádání znaků
definujeme pomocí relace „menší než“, přičemž máme na
výběr mezi primární, sekundární a terciární relací.
Primární relaci definujeme pomocí menšítka (<),
sekundární pomocí středníku (;) a terciární pomocí
čárky (,). Např.

• x<y definuje primární relaci mezi
  znaky x a y,
• i;í definuje sekundární relaci mezi
  znaky i a í,
• T,t definuje terciární relaci mezi
  znaky T a t.

Tyto relace lze kombinovat. Např. A,a;Á,á<B,b říká, že

• A je menší než a
  (terciární relace),
• Á je menší než á
  (terciární relace),
• B je menší než b
  (terciární relace),
• A, a jsou menší než Á, á
  (sekundární relace),
• A, a, Á, á jsou menší než B,
  b (primární relace).

 

Pomocí těchto relací můžeme definovat uspořádání
všech znaků, které se vyskytují v řazených řetězcích.
Uspořádání písmen může vypadat takto:

"< A,a;Á,á;À,à;Â,â;Ä,ä;Ą,ą < B,b
< C,c;Ç,ç < Č,č < D,d;Ď,ď <
E,e;É,é;È,è;Ê,ê;Ě,ě < F,f < G,g < H,h <
CH,Ch,cH,ch < I,i;Í,í < J,j < K,k <
L,l;Ľ,ľ;Ł,ł < M,m < N,n;Ň,ň <
O,o;Ó,ó;Ô,ô;Ö,ö < P,p < Q,q < R,r;Ŕ,ŕ <
Ř,ř < S,s < Š,š < T,t;Ť,ť <
U,u;Ú,ú;Ů,ů;Ü,ü < V,v < W,w < X,x <
Y,y;Ý,ý < Z,z;Ż,ż < Ž,ž"

Mezeru zařadíme před první písmeno:

"< ' ' < A,a..."

Za poslední písmeno abecedy přidáme číslice,
interpunkční znaménka, uvozovky a další symboly:

"< 0 < 1 < 2 < 3 < 4 < 5
< 6 < 7 < 8 < 9 < '.' < ',' <
';' < '?' < '¿' < '!' < '¡' < ':' <
'\"' < '\'' < '«' < '»'..."

Český komparátor tedy může vypadat takto:

public class CzechComparator implements Comparator<String> {

    private static String rules =

            "< ' ' < A,a;Á,á;À,à;Â,â;Ä,ä;Ą,ą < B,b < C,c;Ç,ç < Č,č < D,d;Ď,ď < E,e;É,é;È,è;Ê,ê;Ě,ě" +

            "< F,f < G,g < H,h < CH,Ch,cH,ch < I,i;Í,í < J,j < K,k < L,l;Ľ,ľ;Ł,ł < M,m < N,n;Ň,ň" +

            "< O,o;Ó,ó;Ô,ô;Ö,ö < P,p < Q,q < R,r;Ŕ,ŕ < Ř,ř < S,s < Š,š < T,t;Ť,ť" +

            "< U,u;Ú,ú;Ů,ů;Ü,ü < V,v < W,w < X,x < Y,y;Ý,ý < Z,z;Ż,ż < Ž,ž" +

            "< 0 < 1 < 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9" +

            "< '.' < ',' < ';' < '?' < '¿' < '!' < '¡' < ':' < '\"' < '\'' < '«' < '»'" +

            "< '-' < '|' < '/' < '\\' < '(' < ')' < '[' < ']' < '<' < '>' < '{' < '}'" +

            "< '&' < '¢' < '£' < '¤' < '¥' < '§' < '©' < '®' < '%' < '‰' < '$'" +

            "< '=' < '+' < '×' < '*' < '÷' < '~'";

    private RuleBasedCollator comparator = new RuleBasedCollator(rules);

    public CzechComparator() throws ParseException {

    }

    public int compare(String s1, String s2) {

        return comparator.compare(s1, s2);

    }

}

Přepis písmen z jiných abeced zajistíme pomocí
návrhového vzoru Dekorátor. V metodě compare dekorátoru nejprve nahradíme každé
písmeno jeho přepisem (např. „α“ přepíšeme na „alfa“)
a pak přepsané řetězce porovnáme pomocí českého
komparátoru. Pokud český komparátor vyhodnotí řetězce
jako stejné, porovnáme původní řetězce pomocí
sekundárního komparátoru, který řadí řecká písmena
před jejich přepis (např. „β částice“ bude před „beta
částice“) a řecké písmeno „σ“ (sigma) řadí před „ς“
(sigma).

V kódu pozor na rozdíl mezi písmenem o
a řeckým omicron. Ačkoliv vypadají stejně, jde o dva
rozdílné znaky. Písmeno o je v tabulce
Unicode na pozici 006f a omicron je na pozici 03bf.

public class GreekLetters implements Comparator<String> {

    private static String[] greek = {

        "α", "β", "γ", "δ", "ε",

        "ζ", "η", "θ", "ι", "κ",

        "λ", "μ", "ν", "ξ", "ο",

        "π", "ρ", "σ", "ς", "τ",

        "υ", "φ", "χ", "ψ", "ω"

    };

    private static String[] transcript = {

        "alfa", "beta", "gamma", "delta", "epsilon",

        "zéta", "éta", "théta", "ióta", "kappa",

        "lambda", "mí", "ný", "ksí", "omicron",

        "pí", "rhó", "sigma", "sigma", "tau",

        "upsilon", "fí", "chí", "psí", "omega"

    };

    private static String rules =

            // alfa beta gamma delta epsilon

            "< 'α' < a < 'β' < b < 'γ' < g < 'δ' < d < 'ε' < e" +

            // éta fí chí ióta kappa

            "< 'η' < é < 'φ' < f < 'χ' < ch < 'ι' < i < 'κ' < k" +

            // ksí lambda mí ný omega omicron

            "< 'ξ' < k < 'λ' < l < 'μ' < m < 'ν' < n < 'ω' < 'ο' < o" +

            // pí psí rhó sigma sigma

            "< 'π' < 'ψ' < p < 'ρ' < r < 'σ' < 'ς' < s" +

            // tau théta upsilon zéta

            "< 'τ' < 'θ' < t < 'υ' < u < 'ζ' < z";

    private Comparator<String> decoratee;

    private RuleBasedCollator secondaryComparator = new RuleBasedCollator(rules);

    private Map<String, String> cache = new HashMap<String, String>();

    public GreekLetters(Comparator<String> decoratee) throws ParseException {

        this.decoratee = decoratee;

    }

    String transcribe(String s) {

        String p = cache.get(s);

        if (p == null) {

            p = s;

            for (int i = 0; i < greek.length; i++) {

                p = p.replaceAll(greek[i], transcript[i]);

            }

            cache.put(s, p);

        }

        return p;

    }

    public int compare(String s1, String s2) {

        String t1 = transcribe(s1);

        String t2 = transcribe(s2);

        int c = decoratee.compare(t1, t2);

        if (c != 0) {

            return c;

        }

        return secondaryComparator.compare(s1, s2);

    }

}

Chcete-li si tento kód vyzkoušet, stáhněte si zdrojáky
nebo jar s přeloženými třídami. Jar pustíte takto:

java -jar Sorting.jar inputFile outputFile

Ve vstupním souboru budou řetězce, které chceme
seřadit, vždy jeden řetězec na řádku. Např.:

Nad Popelkou

Nad Santoškou

náměstí Kinských

Na Pláni

Nad Klamovkou

Na Hřebenkách

Výstupní soubor bude obsahovat uspořádané řetězce:

Na Hřebenkách

Na Pláni

Nad Klamovkou

Nad Popelkou

Nad Santoškou

náměstí Kinských