Python Unicode Collation Algorithm
My preliminary attempt at a Python implementation of the Unicode Collation Algorithm (UCA) is done and available at:
http://jtauber.com/2006/01/27/pyuca.py (old version—see UPDATE below)
This only implements the simple parts of the algorithm but I have successfully tested it using the Default Unicode Collation Element Table (DUCET) to collate Ancient Greek correctly.
The core of the algorithm, which is what I have implemented, basically just involves multi-level comparison. For example, café comes before caff because at the primary level, the accent is ignored and the first word is treated as if it were cafe. The secondary level (which considers accents) only applies then to words that are equivalent at the primary level.
The UCA (and my code) also support contraction and expansion. Contraction is where multiple letters are treated as a single unit—in Spanish, ch is treated as a letter coming between c and d so that, for example, words beginning ch should sort after all other words beginnings with c. Expansion is where a single letter is treated as though it were multiple letters—in German, ä is sorted as if it were ae, i.e. after ad but before af.
Here is how to use the pyuca module.
Usage example:
from pyuca import Collator c = Collator("allkeys.txt")
sorted_words = sorted(words, key=c.sort_key)
allkeys.txt (1 MB) is available at
but you can always subset this for just the characters you are dealing with (and you will need to do this if any language-specific tailoring is needed)
UPDATE (2006-02-13): Now see bug fix
Comments (1)
Last Modified: Feb. 12, 2006
Author: James Tauber
Kostik on Dec. 11, 2008:
First I'd like to thank you for the PyUCA algorithm, it some helps me in my Py-based Esperanto-parser.
But the problem is that I didn't get how to use contraction and expansion. Should it be defined obviously? The problem is that the collation results as if it thinks the letters "c" and "ĉ" the same, while the latter should be considered after the first.
So, it results in "ĉambr, ĉar, car', carin', ĉe, ĉef', centjar', centr', cerb', cert', ĉes', ceter'" instead of "car', carin', centjar', centr', cerb', cert', ceter', ĉambr, ĉar, ĉe, ĉef', ĉes'".
Or, in some letter conventions, "cx" must follow "c" (like "ch" after "c" in Spanish).
Could you please clarify using contraction and expansion?