ISO

ORGANIZATION INTERNATIONALE DE NORMALISATION

INTERNATIONAL ORGANIZATION FOR STANDARDIZATION

CEI (IEC)

COMMISSION ÉLECTROTECHNIQUE INTERNATIONALE

INTERNATIONAL ELECTROTECHNICAL COMMISSION

GUIDE SHARE Europe

ISO (the International Organization for Standardization) and IEC (the International Electrotechnical Commission) form the specialized system for worldwide standardization. National bodies that are members of ISO or IEC participate in the development of International Standards through technical committees established by the respective organization to deal with particular fields of technical activity. ISO and IEC technical committees collaborate in fields of mutual interest. Other international organizations, governmental and non-governmental, in liaison with ISO and IEC, also take part in the work.

In the field of information technology, ISO and IEC have established a joint technical committee known as ISO/IEC JTC1. Draft International Standards adopted by the joint technical committee are circulated to the national bodies for voting. Publication as an international standard requires approval by at least 75% of the national bodies that cast a vote.

The ISO/IEC 14651 International Standard has been prepared by the Joint Technical Committee ISO/IEC JTC1, Information Technology.

This International Standard provides a method for ordering text data worldwide, and provides a Common Template Table whose tailoring eases adaptation of a specific script while retaining universal properties for other scripts. The purpose of such a mechanism is to correct errors of the past regarding collation done only on binary coded character values. Past approaches have often not respected cultural preferences for collation. English is one exception, although a poor one, when only upper case alphabetic data was used instead of other characters including punctuation and spacing.

This is one of the major flaws that affect portability between countries and between applications. (Traditionally, different programs use different ordering specifications.) Therefore, it has been considered feasible to design a Common Template Table for ordering and a comparison method that can be used as a reference for the results to be achieved by implementations. This Standard is the achievement of this challenge.

The Common Template Table requires some tailoring in different local environments. However conformance to this International Standard requires that the deviations to the Template, called "deltas", be declared to document result discrepancies.

This Standard describes a method to order text data independently of context. It has provisions to allow a lot of flexibility in implementations, while remaining an excellent international reference for ordering to which all technical and cultural environments can commonly refer to.

This International Standard defines:

This International Standard does not mandate:

• a specific comparison method; any equivalent method giving the same results is acceptable;
• a specific format for describing or tailoring tables in a given implementation;
• specific symbols to be used by implementations except the name of the Common Template Table;
• a specific user interface for choosing options;
• a specific internal format for intermediate keys used in comparisons nor for the table used. The use of numeric keys is not mandated either
• a context-dependent ordering which would require complex transformation of data to order

An application is conformant to this International Standard if it meets the requirements prescribed in section §6.

Any declaration of confomance to this International Standard shall be accompanied by a declaration of the tailoring delta described in clause §6.3 in case tailoring is not provided by the concerned application. In case tailoring is provided, the declaration shall indicate which elements of clause §6.3 it is possible to tailor in the concerned application and which ones have no tailoring provisions. More specifically it is the responsibility of implementers to show how their delta declaration is related to the table syntax described in clause §6.2 and how the comparison method they use, if different from the one mentioned in clause §6.1, can be considered as giving the same results as those prescribed by the method specified in clause §6.1.

The following standards contain provisions which, through reference in this text, constitute provisions of this International Standard. At the time of publication, the editions indicated were valid. All standards are subject to revision, and parties to agreements based on this International Standard are encouraged to investigate the possibility of applying the most recent editions of the standards listed below.

Members of IEC and ISO maintain registers of currently valid International Standards.

For the purposes of this International Standard, the following definitions apply:

Identification of characters of the ISO/IEC 10646-1 (Universal multiple-octet-coded Character Set or UCS) repertoire is made in this edition of this International Standard by means of symbols of the form <UXXXX>. The occurrences of XXXX which follow the letter "U" represent the hexadecimal value (using upper case letters when applicable) of a coded character as defined in ISO/IEC 10646 but no specific coded value is intended. What is being referenced is a graphic character, independently of its coding, and any character set whose subrepertoire is taken into account in ISO/IEC 10646-1 is covered in this way.

This symbolism is a means to be code-independent (the same value being possibly used even if the coded character set in use in a given implementation is not ISO/IEC 10646). At the same time, this is a means to keep a straightforward link with the Universal multiple-octet Coded Character Set (UCS), which is assumed to contain all the coded graphic characters ever defined by ISO/IEC. Addenda to ISO/IEC 10646 will be published from time to time; these addenda may then also give way to addenda in this International Standard if necessary.

By convention, if a character outside of the standard repertoire of ISO/IEC 10646 is to be used in tailored ordering tables, it is recommended that the code-independent symbol identifying this character use the form <Pyyyyyyyy> for documentary purposes indicating its nonstandard nature. The binding to actual coding of these symbols for nonstandard characters is left to implementation and to tailoring. If, for example, actual UCS coding is used, then private zones of this character set will normally be used for meeting such special requirements, and binding could then be specified so that the sequence yyyyyyyy used in the symbol represent private-zone UCS coding.

In the Common Template Table arbitrary symbols representing weights are used according to the BNF notation description in §6.2.1.

It may be necessary to transform character strings before these character strings are fed into the comparison method (see annex § for an example of such preparation). Although not part of the scope of this International Standard, context-sentitive preparation may be an important part of the ordering process, as for example in telephone-book ordering, a complex case in point.

An application conformant to this international standard shall at the minimum prepare the standard so that sequences using either combining sequences or using precomposed characters be presented to the comparison method described in §6.1. An application is also conformant if it uses a comparison method for forming ordering keys which, without making any such preparation, is demonstarted to produce results identical to the ones resulting from the use of such a preparation.

Note 1: In this International Standard, the Common Template Table is built so that, with minimum effort, precomposed characters will be ordered in the same way as when canonically-equivalent combining sequences of characters are used, provided that the preparation prescribed in the previous paragraph is made. It is demonstrated that by tailoring the Common Template Table to add extra token values at level 2 for all precomposed characters affected by a diacritics, it is possible to accomplish identical results for combining sequences without requiring that preparation. However as it is not typically the case that such double-coding will be used, it is not considered required to add extra tokens for keeping a reasonable economy of means in the general case.

Note 2: Escape sequences constitute very sensitive data to interpret, and it is highly recommended that preparation should filter out or transform these sequences. Ideally, all control characters should be filtered out before comparison and reintroduced afterward in case of absolute homography to distinguish two character strings being compared.

Any application conformant to this international standard shall be give identical results to the following method of comparing two character strings:

1. In considering a compiled table describing m weights for each of n characters in the implementation

character set, build a numeric key for each of any two character strings being compared according to the algorithm of key formation described in annex B of this International Standard.

2. Compare the two character strings numerically. The character string whose ordering key is

numerically smaller shall be ordered before the other one. If the two ordering keys are identical then the two character strings compared shall be considered as equal according to this International Standard.

The table used in this reference method for comparison is the result of the numeric compilation of the Common Template Table or of a tailored table using the syntax and interpretation of section 6.2 into a table of n by m elements (n characters by m levels described per character). In the Common Template Table, the number of levels m described per character is equal to 4.

This section specifies:

Definitions between curly brackets make use of terms not defined in this BNF syntax, and assume general English usage.

Other conventions:

* means 0 or more repetitions of a token.

Parentheses indicate optional occurrence of a token.

WF1. Any simple_symbol occurring in a multiple_level_token must occur in a symbol_definition in the same symbol_weight_entry that the multiple_level_token occurs in, or in a symbol_weight_entry that occurs earlier in the sequence of table_line’s that constitute a tailored_table. [I.e., all simple_symbol’s must be "defined" before they are "used". Note that hex_symbol’s are all assumed to be predefined.]

WF2.All multiple_level_token’s in a tailored_table must contain the same number of delimited_level_token’s. [I.e., a tailorable table must be consistent in its use of levels throughout.]

WF3. A tailored_table may not contain a multiple_level_direction if it does not also contain a multiple_level_token. [I.e., no order_start statement can be used in a table which defines no multi-level weights.]

WF4. A multiple_level_direction in a tailored_table must contain the same number of delimited_direction’s as the number of delimited_level_token’s of any multiple_level_token in that tailored_table. [I.e., any order_start must have the same number of levels as is generally used in the table.]

WF5. If a level_token in a multiple_level_token consists of a symbol_group, all successive level_token’s in that multiple_level_token must also consist of a symbol_group. [I.e., don’t use IGNORE at a level after an explicit symbol for a weighting.]

WF6. Any section_identifier occurring in a reorder_section_after_entry must occur in a section_definition_entry that occurs earlier in the sequence of table_line’s that constitute a tailored_table. [I.e., all section_identifier’s must be "defined" before they are "used".]

WF7. No two section_definition_entry’s in a tailored_table may contain the same values in their section_identifier’s. [I.e. multiple definition of section’s is prohibited; section_identifier’s must be unique.]

WF8. Each reorder_after_entry in a tailored_table must be followed by a reorder_end_entry.

WF9. If a tailored_table contains one or more order_start_entry’s, it must be terminated with an order_end_entry.

WF10. No reorder_section_after_entry may contain a target_symbol whose value is the same as any symbol in the section_definition_list_entry whose section_identifier is the same as the section_identifier in that reorder_section_after_entry. [I.e., a section cannot be reordered after a line which the section itself contains; prohibit attempts at recursive relocation of lines.]

I1. A section consists of the list of simple_line’s which contain a symbol_definition whose value is equal to any symbol contained in the symbol_list in a section_definition_list_entry OR consists of the list of simple_line’s following a section_definition_simple_entry in a tailored_table. [I.e., a section is defined by a specific symbol_list, or just by taking all the lines following the section_definition_entry until you hit another tailoring line such as an order_start_entry, a reorder_section_after_entry, another section_definition_entry, or the end of the entire table.]

I2. A tailored_table containing a reorder_after_entry is equivalent to the same tailored_table with the table_line’s between that reorder_after_entry and the first subsequent reorder_end_entry reordered to immediately follow the last table_line in the tailored_table containing a symbol_definition whose symbol is the same as the target_symbol in the reorder_after_entry, and with that reorder_after_entry and that reorder_end_entry removed. [I.e., move the block of lines between the reorder_after_entry and the reorder_end_entry to follow the target_symbol and remove the reorder_after_entry and reorder_end_entry themselves.]

I3. A tailored_table containing a section_reorder_after_entry is equivalent to the same tailored_table with the section associated with that section-reorder_after_entry reordered (in the same relative order as the table_line’s have in that section) to immediately follow the last table_line in the tailored_table containing a symbol_definition whose symbol is the same as the target_symbol in the section_reorder_after_entry, and with that section_reorder_after_entry removed.

I4. A weight_table is said to be in normal form when it contains no reorder_after_entry’s or section_reorder_after_entry’s. [In general, a tailored_table can be put into normal form by the operations implied by I1 and I2.]

I5. A weight_table in normal form is said to be evaluated when each symbol_definition in the weight_table is mapped to a positive integral numeric value such that those values are monotonically increasing by the order that the symbol_definition’s occur in the weight_table. (The table_line’s of the weight_table are first mapped to the set of positive integers, by sequential order in the file. This mapping defines an ordered set of line numbers. The symbol_definition’s are then mapped to a set of positive integers that varies monotonically with the set of line numbers.) [Note that this does not restrict the starting number for the weight of the first symbol_definition, nor does it require that the numbers for these weights be immediately consecutive.

I6. An evaluated weight_table is said to be collation-element-weighted when each simple_symbol occurring in each multiple_level_token in that evaluated weight_table has been mapped to the integral value which corresponds to the symbol_definition that contains the same simple_symbol. [I.e., each multiple_level_token can now be interpreted as containing either symbol’s mapped to integral weight values or instances of the string ‘IGNORE’. All hex_symbol’s are assumed to map to an integral weight value equal to that hex_symbol interpreted as a hexadecimal number. At this point the mathematical injection of strings can be defined using the weight_table.]

C1 Two collation weighting tables W1 and W2 are said to be equivalent if for all strings S defined on a repertoire R, any comparison of any two of the strings S1 and S2 based on their corresponding numbers from the injection P1 produced on W1 is exactly matched by the comparison of S1 and S2 based on their corresponding numbers from the injection P2 produced on W2. [I.e., if one takes two strings, builds keys for each based on table 1 and compares them, one should always get the same results as when one builds keys for them based on table 2 and compare them.]

C2. An implementation of international string ordering is conformant with this standard if for any set of strings S defined on a repertoire R, the implementation can duplicate the same comparisons as those resulting from comparison of the numbers from an injection constructed according to the rules of Section X.X of this standard.

C3. An implementation of international string ordering is conformant with this standard if any tailoring it uses can be demonstrated to be equivalent to a weight_table constructed according to the rules of clause §6.1.2 of this standard.

It is recommended that tailoring be done starting with the Common Template table described in annex 1. If the format used in the Common Template Table is used then tailoring can be accomplished using, for example, ISO/IEC 14652, which uses a syntax that is compatible with the one described in this International Standard.

Any declaration of conformance to this International Standard shall be accompanied with a declaration of the differences that occur in the comparison table used relatively to the Common Template Table if a fixed table is used by the application. These differences are called a delta according to this International Standard. Such a delta shall contain:

In cases where the applications has provision to allow the end-user to tailor the table himself, any statement of conformance shall indicate which ones of the 4 elements of the previous list are tailorable and which ones are not tailorable. For those not tailorable, the delta of fixed elements relatively to the Common Template Table shall be declared.

Annex A -- Common Template Table (normative)

Name used for refering to this table in this version of this  : ISO14651_1998_TABLE1

Annex B -- Building the Ordering key used in the reference comparison method (normative)

The ordering table is a transformation table which can be considered as a matrix of n lines. N is the number of characters in the repertoire used. In each line 4 levels are described in the Common Template Table. This number of levels can be extended in the tailoring phase by the end-user. The user shall take care that in case of tailoring, levels be adjusted so that the last level be processed in a special way accoring to what is described in what follows. Normally the last level is intended to specify "special" characters, i.e. characters normally not part of the orthography of any script, currently so-called "ignorable" characters by specialists of computerized ordering.

A tailored table may be separated into blocks. Each block has specific scanning and ordering properties.

One of the tailoring possibilities is to assign a given order to each block and to change the relative order of a whole block relatively to other blocks.

The scanning direction (forward or backward) used to process the string at each level is a property of each block. These properties can be changed.

A specific property of the last level of comparison is that before comparing weights of each "ignorable" character, a comparison on the numeric position of each such character of two strings is effected (in other words, for two strings equivalent at all levels except the last one, the string having an ignorable in the lowest position comes before the other one. In case ignorables share the same positions, then weights are considered, and this until a difference is found).

Generally, (and in the Common Template Table), levels represent the following decomposition for basic characters:

Annex C -- Benchmark (informative)

Note: the last two letters are not used in the benchmark but are part of the Canadian delta.

1 Unordered list

ou

lésé

péché

vice-président

9999

OÙ

haïe

coop

caennais

lèse

dû

air@@@

côlon

bohème

gêné

lamé

pêche

LÈS

vice versa

C.A.F.

cæsium

resumé

Bohémien

co-op

pêcher

les

CÔTÉ

résumé

Ålborg

cañon

du

haie

pécher

Mc Arthur

cote

colon

l'âme

resume

élève

Canon

lame

Bohême

0000

relève

gène

casanier

élevé

COTÉ

relevé

Grossist

vice-presidents' offices

Copenhagen

côte

McArthur

Mc Mahon

Aalborg

Größe

vice-president's offices

cølibat

PÉCHÉ

COOP

@@@air

VICE-VERSA

gêne

CO-OP

révélé

révèle

çà et là

Noël

île

aïeul

Île d'Orléans

nôtre

notre

août

NOËL

@@@@@

L'Haÿ-les-Roses

CÔTE

COTE

côté

coté

aide

air

vice-president

modelé

MODÈLE

maçon

MÂCON

pèche

pêché

ovoïde

pechère

ode

péchère

œil

Annex D Preparation (informative)

Preparation is essentially for modification and/or duplication of original records to render their fields context-independent prior to the comparison phase. Examples are:

Gaulle (de)

De Gaulle

A numeral is a string representing a number. We will here only deal with numerals that represent values in R, the real numbers, or subsets of R, as these have a total order. We will also only be dealing with decimal numerals in the examples given here.

The same principles apply to, for example, hexadecimal numerals, with the caveat that there are some words that look like hexadecimal numerals, and one must be careful to distinguish which are words and which are hexadecimal numerals. In some cases one uses run-together numerals, perhaps mixed with other substrings. This may happen for instance for part numbers, some date formats, and the like, where it is not obvious which substrings are really separate numerals. Run-together numerals will not be discussed below.

The presentation below will start with positional system decimal numerals for natural numbers using the digits 0-9. It will progress to numerals for whole numbers, numerals with a fraction part, a fraction part and an exponent. There is also a brief discussion on numerals with digits from other scripts, scripts which sometimes uses another syntax with digits for numerals (like Hàn numerals), and Roman numerals.

The Common Template Table has no means of sorting strings with numbers in such a way that the resulting order reflects the number value represented by the numerals. For example, given the following strings:

Release 1
Release 20
Release 12
Release 2
Release 9

the method described in this International Standard gives the following list of "sorted" strings:

Release 1
Release 12
Release 2
Release 20
Release 9

(It is sufficient to positionally look at just the first digit in each numeral to see why one gets this order.) A more acceptable ordering is:

Release 1
Release 2
Release 9
Release 12
Release 20

The Common Template Table defined in this International Standard cannot be tailored to give this result. However, preparation can be done prior to the basic collation step to achieve desired results in cases where ordering of a word equivalent of numbers or where positional numeric ordering is not desired. The prepared strings are normally not presented to the user, only the original strings are. The prepared strings are normally only used for the collation key construction. A simple, very primitive and not very general, way of preparing numerals for natural numbers is to zero-pad them to a given number of digits. If one zero-pads up to three digits the numerals in our original example strings one gets:

Release 001
Release 020
Release 012
Release 002
Release 009

Using the Common Template Table defined in this International Standard one then gets the strings in better order (here showing the strings as they are after preparation, which are normally not shown in the result):

Release 001
Release 002
Release 009
Release 012
Release 020

However, there are two problems with this approach:

For example:

Dated: July 19, 1955, at 1 p.m. GMT
Dated: January, 20 B.C.
Dated: Sept. 20, 1995, at 1 p.m. PST
Dated: 11-june/345 A.D.

After preparation:

Dated: +41955-07-19T13:00Z July 19, 1955, at 1 p.m. GMT
Dated: –780-01 January, 20 B.C.
Dated: +1995-09-20T10:00Z Sept. 20, 1995, at 1 p.m. PST
Dated: +3345-06-11 11-june/345 A.D.

After sorting

Dated: –780-01 January, 20 B.C.
Dated: +3345-06-11 11-june/345 A.D.
Dated: +41955-07-19T13:00Z July 19, 1955, at 1 p.m. GMT
Dated: +41995-09-20T10:00Z Sept. 20, 1995, at 1 p.m. PST

As presented to the user:

Dated: January, 20 B.C.
Dated: 11-june/345 A.D.
Dated: July 19, 1955, at 1 p.m. GMT
Dated: Sept. 20, 1995, at 1 p.m. PST

As noted above in several cases, we have duplicated part of the string to maintain determinacy in collation, when the original strings are different, but when preparation may otherwise turn different strings into identical strings.

This method of duplicating for determinacy can be used more generally, so if there are several preparations affecting different parts of the strings, one may simply duplicate the original strings to begin with, and only do the preparation (without additional duplication) on the first half of the "doubled" string.

One disadvantage with just concatenating the two copies is that the base letters of the second half of the "doubled" string count as more significant than the accents and case of the resulting first half of the "doubled" string. The present standard has no mechanism for handling this in a better way, where the "original" (the second half of the "doubled" string) would count as less significant than the entire first half of the "doubled" string.

Note that the string after preparation is used only for the collation key construction. The original string is not intended to be retrievable form from the prehandled string, though that is possible with this way of attaining determinacy. The strings presented to the user are the original, by preparation untouched, strings.

To maintain determinacy when some of the original strings to be collated are identical, is out of scope for this standard.

In case of equality established according to this International Standard on two character strings, it may be necessary to establish a posteriori an ultimate differentiation based on the original record being processed which may contain additional data. Although this posthandling is not part of the scope of this International Standard, consideration is given here on an informative basis to this ultimate stage of ordering.

Posthandling is essentially for modifying a resulting ordering key, or appending the original character string to an ordering key so that the results of comparisons can determine differences particularly in cases where homography results from the preparation phase. For example, there could be equivalencies if numerical values (for example, "010" and "10") may have been rendered identical in the preparation phase. A strict implementation of this International Standard has no knowledge that the original strings are different in such cases, but the predictability requirement may still exist and posthandling will then be required to achieve this specific requirement.

Another case in point exists, for example, where different coding methods have been used in the original strings to be ordered in the same process. An optional posthandling phase can then determine internal differences even when results would appear exactly the same on paper for end-users (for example, an ISO 2022 input stream intermixing ISO/IEC 6937 and ISO/IEC 8859-2 coded characters). This may be required for internal processing of applications and maintaining integrity of comparison between records and even entire files.

Annex E -- Tutorial on solutions brought by this standard to problems of lexical ordering (informative)

Why aren't existing standard codes, character by character comparisons and commercial sort programs appropriate for sorting and what must be done to solve the problem? For clarity, this discussion will start with the Latin script.

Sorted Internal

List Values

aaaa 01010101

abbb 01030303

Aaaa 02010101

Abbb 02030303