Chwilowo myślałem więc że problem ten powiązany jest z kodowaniem znaków (np Unicode lub ASCI). Dopiero gdy zauważyłem że każdy język na świecie ma własne zasady ortografii i gramatyki tak więc nie ma czegoś takiego jak jedna kolejność znaków. Innymi słowy gdyby spisać wszystkie nazwy miast na świecie w ich oryginalnej pisowni i posortować je wg zasad Niemieckich, Francuz powiedział by że ta kolejność jest nieprawidłowa. Tak więc jeśli każdemu znakowi przypiszemy unikalną liczbę (co zresztą robi Unicode) to i tak kolejność sortowania nie jest zdefiniowana bez podania konkretnego języka wg zasad którego będziemy sortować. Jak widać kodowanie znaków dla maszyny cyfrowej jest całkiem odrębnym problemem.
Generalnie po kilku godzinach spędzonych nad tematem dogrzebałem się do jednego wniosku: Sortowanie napisów to bardzo skomplikowany problem. Nawet istnieje generalny standard:
http://www.unicode.org/reports/tr10/
Oraz narzędzia do testowania implementacji:
http://demo.icu-project.org/icu-bin/locexp?_=en_US&d_=en&x=col
W szczególności zacytuje poniższy fragment opisujący najczęstsze nieporozumienia wokoło sortowania napisów:
There are a number of common misperceptions about collation.
1. Collation is not aligned with character sets or repertoires of characters. Swedish and German share most of the same characters, for example, but have very different sorting orders.
2. Collation is not code point (binary) order. The simplest case of this is capital Z versus lowercase a. As noted above, beginners may complain about Unicode that a particular character is “not in the right place in the code chart”. That is a misunderstanding of the role of the character encoding in collation. While the Unicode Standard does not gratuitously place characters such that the binary ordering is odd, the only way to get the linguistically-correct order is to use a language-sensitive collation, not a binary ordering.
3. Collation is not a property of strings. Consider a list of cities, with each city correctly tagged with its language. Despite this, a German user will expect to see the cities all sorted according to German order, and not expect to see a word with ö appear after z, simply because the city has a Swedish name. As mentioned above it is of crucial importance that if a German businessman makes a database selection, such as to sum up revenue in each of of the cities from O... to P... for planning purposes, then cities starting with Ö must not be excluded.
4. Collation order is not preserved under concatenation or substring operations, in general. For example, the fact that x is less than y does not mean that x + z is less than y + z. This is because characters may form contractions across the substring or concatenation boundaries. In summary, the following shows which implications not to expect.
x < y does not imply that x+z y+z x < y does not imply that z+x < z+y x+z < y+z does not imply that x < y z+x < z+y does not imply that x < y 5. Collation order is not preserved when comparing sort keys generated from different collation sequences. Remember that sort keys are a preprocessing of strings according to a given set of collation features. From different features, you will get different binary sequences. For example, suppose we have two collations, F and G, where F is a French collation (with accents compared from the end), and G is a German phonebook ordering. Then:
* A ? B according to F if and only if sortkey(F, A) ? sortkey(F, B), and
* A ? B according to G if and only if sortkey(G, A) ? sortkey(G, B)
* But the relation between sortkey(F, A) and sortkey(G, B) says nothing about whether A ? B according to F, or whether A ? B according to G.
6. Collation order is not a stable sort; that is a property of a sort algorithm, not a collation sequence. For more information, see Section 3.4, Stability.
7. Collation order is not fixed. Over time, collation order will vary: there may be fixes that are discovered as more information becomes available about languages; there may be new government or industry standards for the language that require changes; and finally, the new characters that are added to Unicode periodically will interleave with the previously-defined ones. Thus collations must be carefully versioned.
Jeszcze co nieco po Polsku w temacie: http://www.eioba.pl/a87655/sortowanie_leksykograficzne
Brak komentarzy:
Prześlij komentarz