Collation

Alphabetical redirects here. For the alphabet, click here. For the meal, see collations.

In textual criticism and bibliography, collation is the reading of two (or more) texts side-by-side in order to note their differences.

In printing and photocopying, collation is the arrangement of pages in order when several copies of a document are bound after printing or copying.

Collation can also refer to the detailed bibliographical description of a book or the comparison of the physical makeup of two copies of a book.

In library and information science and computer 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 sorting algorithm in that whereas sorting algorithms decide which pairs of elements to compare, collation defines a total order ≤ on pairs that the sorting algorithm uses to determine when to swap the elements (usually a lexicographical order). In fact, sorting algorithms are often implemented to take a collation as an input.

Collation systems

Numerical sorting, sorting of single characters

The simplest collation system is numerical sorting: ordering numbers by their magnitude. For example, the list of numbers 4 · 17 · 3 · 5 collates to 3 · 4 · 5 · 17.

While this might appear to work only for numbers, computers can use this method for any textual information since computers internally use character sets which assign a numeric code point to each letter or glyph. For example, a computer using ASCII code (or any of its supersets such as Unicode) and numerical sorting would collate the list of characters a · b · C · d · $ to $ · C · a · b · d.

The numerical values that ASCII uses are $ = 36, a = 97, b = 98, C = 67, and d = 100, resulting in ASCIIbetical order.

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.

Alphabetical sorting

A collation system for multiple-character words is alphabetical sorting in lexicographical order, based on the conventional order of letters in an alphabet or abjad (most of which have a single conventional order). 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, and so on, until the order is established.

For example, the list of words 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.

Numerical sorting (not to be confused with sorting of numbers, see below) 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 using an extended Latin alphabet.

For example, the thirty-letter alphabet of Spanish treats ñ as a 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, both with and without the 1994 alphabetization rule.) A numeric sort may order ñ incorrectly following z and treat ch as c + h, also incorrect when using pre-1994 alphabetization.

Similar differences between computer numeric sorting and alphabetic sorting occur in Danish and Norwegian (in some cases, aa is ordered as å at the end of the alphabet), German (ß is ordered as s + s; ä, ö, ü are ordered as a + e, o + e, u + e in phone books, but as o elsewhere, and behind o in Austria), 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.

Radical-and-stroke sorting

Another form of collation is radical-and-stroke sorting, used for non-alphabetic writing systems such as Chinese hanzi and Japanese kanji, whose thousands of symbols defy ordering by convention. In this system, common components of characters are identified; these are called radicals in Chinese and logographic systems derived from Chinese. Characters are then grouped by their primary radical, then ordered 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. The choice of which components of a logograph comprise separate radicals and which radical is primary is not clear-cut. 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 Tōkyō'' (東京), the Japanese name of Tokyo can be sorted as if it were spelled out in the Japanese alphabet as "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.

Multilingual ordering

When lists of names or words need to be ordered, but the context does not define a particular single language or alphabet, the Unicode Collation Algorithm provides a way to put them in sequence.

Complications

Compound words and special characters

A complication in alphabetical sorting can arise due to disagreements over how groups of words (separated compound words, names, titles, etc.) should be ordered. One rule is to remove spaces for purposes of ordering, another is to consider a space as a character that is ordered before numbers and letters (this method is consistent with ordering by ASCII or Unicode codepoint), and a third is to order a space after numbers and letters. Given the following strings to alphabetize — "catch", "cattle", "cat food" — the first rule produces "catch" "cat food" "cattle", the second "cat food" "catch" "cattle", and the third "catch" "cattle" "cat food". The first rule is used in most (but not all) dictionaries, the second in telephone directories (so that Wilson, Jim K appears with other people named Wilson, Jim and not after Wilson, Jimbo). The third rule is rarely used.

A similar complication arises when special characters such as hyphens or apostrophes appear in words or names. Any of the same rules as above can be used in this case as well; however, the strict ASCII sorting no longer corresponds exactly to any of the rules.

Name/Surname ordering

The telephone directory example sheds light on another complication. In cultures where family names are written after given names, it is usually still desired to sort by family name first. In this case, names need to be reordered to be sorted properly. For example, Juan Hernandes and Brian O'Leary should be sorted as Hernandes, Juan and O'Leary, Brian even if they are not written this way. Capturing this rule in a computer collation algorithm is difficult, and simple attempts will necessarily fail. For example, unless the algorithm has at its disposal an extensive list of family names, there is no way to decide if "Gillian Lucille van der Waal" is "van der Waal, Gillian Lucille", "Waal, Gillian Lucille van der", or even "Lucille van der Waal, Gillian".

In telephone directories in English speaking countries, surnames beginning with Mc are sometimes sorted as if starting with Mac and placed between "Mabxxx" and "Madxxx". Under these rules, the telephone directory order of the following names would be: Maam, McAllan, Macbeth, MacCarthy, McDonald, Macy, Mboko.

Abbreviations and common words

When abbreviations are used, it is sometimes desired to expand the abbreviations for sorting. In this case, "St. Paul" comes before "Shanghai". Obviously, to capture this behavior in a collation algorithm, we need a list of abbreviations. It may be more practical in some cases to store two sets of strings, one for sorting and one display. A similar problem arises when letters are replaced by numbers or special symbols in an irregular manner, for example 1337 for leet or the movie Se7en. In this case, proper sorting necessitates keeping two sets of strings.

In certain contexts, very common words (such as articles) at the beginning of a sequence of words are not considered for ordering, or are moved to the end. So "The Shining" is considered "Shining" or "Shining, The" when alphabetizing and therefore is ordered before "Summer of Sam". This rule is fairly easy to capture in an algorithm, but many programs rely instead on simple lexicographic ordering. One fairly quaint exception to this rule is the flying of the flag of The Former Yugoslav Republic of Macedonia at the United Nations between those of Thailand and Timor Leste.

Numerical sorting of strings

Sometimes, it is desired to order text with embedded numbers using proper numerical order. For example, "Figure 7b" goes before "Figure 11a", even though 'b' comes after '1' in Unicode. This can be extended to Roman numerals. This behavior is not particularly difficult to produce as long as only integers are to be sorted, although it can slow down sorting significantly.

For example, Windows XP does this when sorting file names. Sorting decimals properly is a bit more difficult, due to the fact that different locales use different symbols for a decimal point, and sometimes the same character used as a decimal point is also used as a separator, for example "Section 3.2.5". There is no universal answer for how to sort such strings; any rules are application dependent.

Sorting of numbers

Ascending order of numbers differs from alphabetical order, e.g. 11 comes alphabetically before 2. This can be fixed with leading zeros: 02 comes alphabetically before 11. See e.g. ISO 8601.

Also -13 comes alphabetically after -12 although it is less. With negative numbers, to make ascending order correspond with alphabetical sorting, more drastic measures are needed such as adding a constant to all numbers to make them all positive.

External links and references

Unicode Collation Algorithm: Unicode Technical Standard #10
Collation in Spanish (http://spanish.about.com/library/weekly/aa092099.htm#letters)
^* Collation of the names of the member states of the United Nations

Tools

sort The GNU implementation of the standard Unix sort utility.
msort A sort program that provides an unusual level of flexibility in defining collations and extracting keys.

Orthography | Information science

Gourt Home::Gourt :: Collation