Collation

In computer science and library and information science, collation is the assembly of written information into a standard order. In common usage, this is called alphabetisation, though collation is not limited to ordering letters of the alphabet. Collating lists of words or names into alphabetical order is the basis of most office filing systems, library catalogues, and books of reference. Collation differs from classification in that classification is concerned with arranging information into logical categories, while collation is concerned with the partial ordering of those categories. Collation differs from a sort algorithm in that whereas sort algorithms decide which pairs of elements to compare, collation defines a partial order <= on pairs that the sort algorithm uses to determine when to swap the elements.

The simplest collation system is numerical sorting: ordering numbers by their magnitude. For example, 4 7 3 5 colates to 3 4 5 7. While this might appear to work only for numbers, computers can use this method for any information since everything is a number to a computer. For example, a computer using ASCII code (or any of its supersets such as Unicode) and numerical sorting would collate a b C d $ to $ C a b d. Why the curious "ASCIIbetical order[?]"? The numerical values that ASCII uses are $ = 36, a = 97, b = 98, C = 67, and d = 100. This style of collation is commonly used, often with the refinement of converting uppercase letters to lowercase before comparing ASCII values, since most people do not expect capitalised words to jump the head of the list. This system fails to properly sort numbers written as text because a human-readable number stored in a computer text string is a sequence of numeric codes for numerals. For example, 156.1 (a string) is represented by ASCII code as the five ordered numbers 49, 53, 54, 46, and 49; 35.29 corresponds to 51, 53, 46, 50, and 57; because 49 comes before 51, 156.1 comes before 35.29.

A more elaborate collation system is alphabetical sorting, which orders words or names based on the order of letters in an alphabet or abjad. Each nth letter is compared with the nth letter of other words in the list, starting at the first letter of each word and advancing to the second, third, fourth, etc until the order is established. For example, foo bar bibble collates to bar bibble foo because (1) f comes after b so bar and bibble both precede foo and (2) a comes before i so bar precedes bibble.

Numeric sorting on a computer and alphabetical sorting often produce the same ordering for English. The difference between computer-style numerical sorting and true alphabetical sorting becomes obvious in languages with alphabets larger than twenty-six letters. For example, the thirty-letter alphabet of Spanish treats ñ as basic letter following n, and formerly treated ch and ll as basic letters following c, l, respectively. Ch and ll are still considered letters, but are alphabetized as digraphs. (The new alphabetization rule was issued by the Royal Spanish Academy in 1994.) (On the other hand, the letter rr follows rqu as expected.) A numeric sort would order ñ incorrectly following z and treat ch as c + h, also incorrect. Similar differences between computer numeric sorting and alphabetic sorting occur in Danish and Norwegian (aa is ordered as å at the end of the alphabet), German (ß is ordered as s + s), Icelandic (ð follows d), English (æ is ordered as a + e), and many other languages. Usually the spaces or hyphens between words are ignored.

See also Latin alphabet for a list of collating rules for latin based alphabets.

Languages that used a syllabary or abugida instead of an alphabet (for example, Cherokee[?]) can use approximately the same system if there is a set ordering for the symbols.

Another form of collation is radical-and-stroke sorting, used for non-alphabetic writing systems such as Chinese logographs and Japanese kanji, whose thousands of symbols defy ordering by convention. In this system, common components of characters (radicals) are identified. Character are then grouped by their primary radical, then order by number of pen strokes within radicals. When there is no obvious radical or more than one radical, convention governs which is used for collation. For example, the Chinese character for "mother" (媽) is sorted as a thirteen-stroke character under the three-stroke primary radical (女).

The radical-and-stroke system is cumbersome compared to an alphabetical system in which there are a few characters, all unambiguous. As a result, logographic languages often supplement radical-and-stroke ordering with alphabetic sorting of a phonetic conversion of the logographs. For example, the kanji word Tokyo (東京) can be sorted as if it is spelled out in the Japanese alphabet sequence "to-u-ki-_yo-u" (とうきょう). Nevertheless, the radical-and-stroke system is the only practical method for constructing dictionaries that someone may use to look up a logograph whose pronunciation is unknown.

External links and references

• Collation in Spanish (http://spanish.about.com/library/weekly/aa092099.htm#letters)