Collation

This article is about collation in library, information, and computer science. For other uses, see Collation (disambiguation).

"Alphabetical" redirects here. For the type of writing system, see Alphabet. For the album, see Alphabetical (album).

"A–Z" redirects here. For the street atlases, see Geographer's A–Z Street Atlas. For the music singles, see A–Z Series.

"Dictionary order" redirects here. For the mathematical structure, see Lexicographical order.

Collation is the assembly of written information into a standard order. One common type of collation is called alphabetization, 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 catalogs and reference books.

Collation differs from classification in that classification is concerned with arranging information into logical categories, while collation is concerned with the ordering of those categories.

Advantages of sorted lists include:

• one can easily find the first n elements (e.g. the 5 smallest countries) and the last n elements (e.g. the 3 largest countries)
• one can easily find the elements in a given range (e.g. countries with an area between .. and .. square km)
• one can easily search for an element, and conclude whether it is in the list, e.g. with the binary search algorithm or interpolation search either automatically, or, roughly and perhaps unconsciously, manually.

A collation algorithm, e.g. the "Unicode collation algorithm", differs from a sorting algorithm: the first is a process to define the order, which corresponds to the process of just comparing two values, while a sorting algorithm is a procedure to put a list of items in this order.

Collation defines a total preorder on the set of possible items, typically by defining a total order on a sortkey. Note however that in the case of e.g. numerical sorting of strings representing numbers, the strings are only partially preordered, because e.g. 2e3 and 2000 have the same ranking, and 2 and 2.0 also. The numbers represented by the strings are totally ordered.

History

The first effective use among scholars may have been in ancient Alexandria.^[1] In the 1st century BC Varro wrote some alphabetic lists of authors and titles.^[2] In the 2nd century AD Sextus Pompeius Festus wrote an encyclopedic work with entries in alphabetic order.^[3] In the 3rd century Harpocration wrote a Homeric lexicon alphabetized by all letters.^[4] In the 10th century the author of the Suda used alphabetic order with phonetic variations. In the 14th century the author of the Fons memorabilium universi used a classification, but used alphabetical order within some of the books.^[5] In 1604 Robert Cawdrey had to explain in Table Alphabeticall: the first monolingual English dictionary "Nowe if the word, which thou art desirous to finde, begin with (a) then looke in the beginning of this Table, but if with (v) looke towards the end."^[6] Although as late as 1803 Samuel Taylor Coleridge condemned encyclopedias with "an arrangement determined by the accident of initial letters",^[7] many lists are today based on this principle.

Systems

Numerical sorting, sorting of single characters

One collation system is numerical sorting. For example, the list of numbers 4 · 17 · 3 · -5 collates to -5 · 3 · 4 · 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 what is called "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 order

Main article: Collating sequence

A collation system for multiple-character words is alphabetical order, based on the conventional order of letters in an alphabet (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.

The order of the Latin alphabet is

A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z

The principle behind extending alphabetical order to words (lexicographical order) is that all words in a list beginning with the same letter should be grouped together; within a grouping starting with a single letter, all words beginning with the same two letters shall be grouped together; and so on, maximizing the number of common initial letters between adjacent words. The ordering principle is applied at the point where the letters differ. For instance, in the sequence:

Astrolabe

Astronomy

Astrophysics

The order of the words is given according to the first letter of the words that is different from the others (shown in bold). Since n follows l in the alphabet, but precedes p, Astronomy comes after Astrolabe, but before Astrophysics.

There has historically been some variation in the application of these rules. For instance, the prefixes Mc and M' in Irish and Scottish surnames were taken to be abbreviations for Mac, and alphabetized as if they were spelled out as Mac in full. Thus one might find in a catalog the sequence:

McKinley

Mackintosh

with McKinley preceding Mackintosh, as if it had been spelled "MacKinley". Since the advent of computer-sorted lists, this type of alphabetization is less frequently encountered, though it is still used in British phone books. A variation in alphabetical principles applies to names consisting of two words. In some cases, names with identical first words are all alphabetized together under the first word, e.g., grouping together all names beginning with San, all those beginning with Santa, and those beginning with Santo:

San

San Cristobal

San Juan

San Teodoro

San Tomas

Santa Barbara

Santa Clara

Santa Cruz

Santo Domingo

But in another system, the names are alphabetized as if they had no spaces, e.g. as follows:

San

San Cristobal

San Juan

Santa Barbara

Santa Clara

Santa Cruz

San Teodoro

Santo Domingo

San Tomas

The difference between computer-style numerical sorting and true alphabetical sorting becomes obvious in languages using an extended Latin alphabet. For example, the 29-letter alphabet of Spanish treats ñ as a basic letter following n, and formerly treated ch and ll as basic letters following c and l, respectively. Ch and ll are still considered letters, but are now alphabetized as two-letter combinations. (The new alphabetization rule was issued by the Royal Spanish Academy in 1994.) On the other hand, the digraph 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 (aa is ordered at the end of the alphabet when it is pronounced like å, and at the start of the alphabet when it is pronounced like a), 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), Dutch (ij is sometimes ordered as y; see IJ: Collation), English (æ is ordered as a + e), and many other languages.

Usually the spaces or hyphens between words are ignored.

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 six-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 characters of the hiragana syllabary as "to-u-ki-_yo-u" (とうきょう), using the conventional sorting order for these characters.

In addition, in Greater China, surname stroke ordering is a convention in some official documents where peoples' names are listed without hierarchy.

The radical-and-stroke system, or some similar pattern-matching and stroke-counting method, was traditionally the only practical method for constructing dictionaries that someone could use to look up a logograph whose pronunciation was unknown. With the advent of computers, dictionary programs are now available that allow one to draw a character using a mouse or stylus.

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

Conventions in typography and in sorting systems

In typography and in the writing of scientific articles etc., such things as headers, sections, lists, pages etc. might use alphabetical numbering instead of numerical numbering. However, this does not always mean that the full alphabet of a particular language is used. Often alphabetical numbering—or enumeration—only uses a subset of the full alphabet. E.g. the Russian alphabet has 33 letters, but typically only 28 are used in typographical enumeration (and for instance Ukrainian, Belarusian and Bulgarian Cyrillic enumeration shows similar features). Two Russian letters, Ъ and Ь, are only used for modifying the preceding consonants—they naturally fall out. The last three could have been used, but mostly are not: Ы never begins a Russian word, Й almost never begins a word either, and it is perhaps too much like И—and also a relatively new character. Ё is also relatively new and much debated—sometimes in proper alphabetical sorting letters on Ё are listed under Е. (These "rules" are of course moderated, again, e.g. in phone catalogs, where foreign (non-Russian) names may frequently begin with Й or Ы.) This alludes to a simple fact: alphabets are not only tools for writing. And letters are often kept in an alphabet of a certain language even though they are not used in writing, not least because they are used in alphabetical enumeration. For instance, X, W, Z are not used in writing the Norwegian language, except in loanwords and names. Still they are kept in the Norwegian alphabet, and used in alphabetical lists. Likewise, earlier versions of the Russian alphabet contained letters which only had two purposes: they were good for writing Greek words and for using the Greek counting system in its Cyrillic form.

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 many (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".

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, a list of abbreviations is needed. It may be more practical in some cases to store two sets of strings, one for sorting and one for 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.

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.

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 '7' 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, because 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.

Alphabetical sorting of numbers

When numbers are used as names, rather than for their numerical properties, it is common^{[citation needed]} to sort them alphabetically as they would be spelled. For example, the movie 1776 would be between Seve Ballesteros and Severus Snape. If a number is in a foreign term, it is alphabetized as it would be spelled in that language; for example, 24 heures du Mans would be between Vinge's Singularity and Vinh Airport, reflecting the French "vingt-quatre".

Notes

1. ^ Daly, Lloyd. Contributions to the History of Alphabetization in Antiquity and the Middle Ages Brussels, 1967. p. 25
2. ^ O'Hara, James (1989). Messapus, Cycnus, and the Alphabetical Order of Vergil's Catalogue of Italian Heroes. JSTOR 1088539. 
3. ^ LIVRE XI - texte latin - traduction + commentaires. http://remacle.org/bloodwolf/erudits/Festus/m.htm. 
4. ^ Gibson, Craig (2002). Interpreting a classic: Demosthenes and his ancient commentators. 
5. ^ Yeo, Richard (2001). Encyclopaedic visions: scientific dictionaries and enlightenment culture. Cambridge University Press. ISBN 0521651913. http://books.google.com/books?id=8bJYm1N8bqgC&pg=PA22&lpg=PA22&dq=fons+memorabilium+universi+alphabetic+order#v=onepage&q&f=false. 
6. ^ Robert Cawdrey's - A Table Alphabetical OBERT (1604). http://www.library.utoronto.ca/utel/ret/cawdrey/cawdrey0.html#reader. 
7. ^ Coleridge's Letters, No.507. http://inamidst.com/coleridge/letters/letter507. 

External links and references

• Unicode Collation Algorithm: Unicode Technical Standard #10
• Collation in Spanish
• Collation of the names of the member states of the United Nations
• Typographical collation for many languages, as proposed in the List module of Cascading Style Sheets.
• Collation Charts: Charts demonstrating language-specific sorting orders in various operating systems and DBMS