Abstract

This document builds upon on Character Model for the World Wide Web 1.0: Fundamentals [CHARMOD] to provide authors of specifications, software developers, and content developers a common reference on string identity matching on the World Wide Web and thereby increase interoperability.

Status of This Document

This section describes the status of this document at the time of its publication. Other documents may supersede this document. A list of current W3C publications and the latest revision of this technical report can be found in the W3C technical reports index at http://www.w3.org/TR/.

This version of this document represents a significant change from its previous edition. Much of the content is changed and the recommendations are significantly altered. This fact is reflected in a change to the name of the document from "Character Model: Normalization".

This is a work in progress!For the latest updates from the Internationalization WG, possibly including important bug fixes, please review the editor's draft instead.

This document was published by the Internationalization Working Group as a Working Draft. This document is intended to become a W3C Working Group Note. If you wish to make comments regarding this document, please send them to www-international@w3.org (subscribe, archives). All comments are welcome.

Publication as a Working Draft does not imply endorsement by the W3C Membership. This is a draft document and may be updated, replaced or obsoleted by other documents at any time. It is inappropriate to cite this document as other than work in progress.

This document was produced by a group operating under the 5 February 2004 W3C Patent Policy. W3C maintains a public list of any patent disclosures made in connection with the deliverables of the group; that page also includes instructions for disclosing a patent. An individual who has actual knowledge of a patent which the individual believes contains Essential Claim(s) must disclose the information in accordance with section 6 of the W3C Patent Policy.

Table of Contents

1. Introduction

1.1 Goals and Scope

The goal of the Character Model for the World Wide Web is to facilitate use of the Web by all people, regardless of their language, script, writing system, and cultural conventions, in accordance with the W3C goal of universal access. One basic prerequisite to achieve this goal is to be able to transmit and process the characters used around the world in a well-defined and well-understood way.

Note

This document builds on Character Model for the World Wide Web: Fundamentals [CHARMOD]. Understanding the concepts in that document are important to being able to understand and apply this document successfully.

This part of the Character Model for the World Wide Web covers string matching—the process by which a specification or implementation defines whether two string values are the same or different from one another. It describes the ways in which texts that are semantically equivalent can be encoded differently and the impact this has on matching operations important to formal languages (such as those used in the formats and protocols that make up the Web). Finally, it discusses the problem of substring searching within documents.

The main target audience of this specification is W3C specification developers. This specification and parts of it can be referenced from other W3C specifications and it defines conformance criteria for W3C specifications, as well as other specifications.

Other audiences of this specification include software developers, content developers, and authors of specifications outside the W3C. Software developers and content developers implement and use W3C specifications. This specification defines some conformance criteria for implementations (software) and content that implement and use W3C specifications. It also helps software developers and content developers to understand the character-related provisions in W3C specifications.

The character model described in this specification provides authors of specifications, software developers, and content developers with a common reference for consistent, interoperable text manipulation on the World Wide Web. Working together, these three groups can build a globally accessible Web.

1.2 Structure of this Document

This document defines two basic building blocks for the Web related to this problem. First, it defines rules and processes for String Identity Matching in document formats. These rules are designed for the identifiers and structural markup (markup) used in document formats to ensure consistent processing of each and are targeted to Specification writers. Second, it defines broader guidelines for handling user visible text (the "Shakespeare"), such as natural language text that forms most of the content of the Web. This section is targeted to implementers.

This document is divided into three main sections.

The first section lays out the problems involved in string matching; the effects of Unicode and casefolding on these problems; and outlines the various issues and normalization mechanisms that might be used to address these issues.

The second section provides requirements and recommendations for string identity matching for use in format languages, such as document formats defined by W3C Specifications. This primarily is concerned with making the Web functional and providing document authors with consistent results.

The third section discusses considerations for the handling of content by implementations, such as browsers or text editors on the Web. This mainly is related to how and why to preserve the author's original sequences and how to search or find content in natural language text.

1.3 Background

This section provides some historical background on the topics addressed in this specification.

At the core of the character model is the Universal Character Set (UCS), defined jointly by the Unicode Standard [UNICODE] and ISO/IEC 10646 [ISO10646]. In this document, Unicode is used as a synonym for the Universal Character Set. A successful character model allows Web documents authored in the world's writing systems, scripts, and languages (and on different platforms) to be exchanged, read, and searched by the Web's users around the world.

The first few chapters of the Unicode Standard [UNICODE] provide useful background reading.

For information about the requirements that informed the development of important parts of this specification, see Requirements for String Identity Matching and String Indexing [CHARREQ].

1.4 Terminology and Notation

This section contains terminology and notation specific to this document.

The Web is built on text-based formats and protocols. In order to describe string matching or searching effectively, it is necessary to establish terminology that allows us to talk about the different kinds of text within a given format or protocol, as the requirements and details vary significantly.

Unicode code points are denoted as U+hhhh, where hhhh is a sequence of at least four, and at most six hexadecimal digits. For example, the character € EURO SIGN has the code point U+20AC.

Some characters that are used in the various examples might not appear as intended unless you have the appropriate font. Care has been taken to ensure that the examples nevertheless remain understandable.

A legacy character encoding is a character encoding not based on the Unicode character set.

define grapheme and grapheme cluster

A grapheme is ...

A grapheme cluster is ...

Shakespeare is a temporary placeholder term referring only to the natural language content in a document and not to any of the surrounding markup or identifiers that form part of the document structure. You can think of the Shakespeare as the actual "content" of the document or the "message" in a given protocol. Note that the Shakespeare includes items like the document title ("Much Ado About Nothing") as well as prose content within the document.

Markup is any text in a document format or protocol that belongs to the structure of the format or protocol. This definition can include values that are not typically thought of as "markup", such as the name of a field in an HTTP header, as well as all of the characters that form the structure of a format or protocol. For example, < or > are part of the markup in an HTML document.

Markup usually is defined by a specification or specifications and includes both the defined, reserved keywords for the given protocol or format as well as string tokens and identifiers that are defined by document authors to form the structure of the document (rather than the "content" of the document).

XML [XML10] defines specific elements, attributes, and values that are reserved across all XML documents. Thus, the word encoding has a defined meaning inside the XML document declaration: it is a reserved name. XML also allows a user to define elements and attributes for a given document using a DTD. In a document that uses a DTD that defines an element called <muffin>, "muffin" is a part of the markup.

Wildebeest is a temporary placeholder term signifying a document or protocol including both the contained text (the "Shakespeare") and the markup such as identifiers surrounding or containing it. For example, in an HTML document that also has some CSS and a few script tags with embedded JavaScript, the entire HTML document, considered as a file, is the Wildebeest.

The WG is considering changing the term "namespace", which is heavily overloaded, to "vocabulary"

A namespace provides the list of reserved names as well as the set of rules and specifications controlling how user values (such as identifiers) can be assigned in a format or protocol. This can include restrictions on range, order, or type of characters that can appear in different places. For example, HTML defines the names of its elements and attributes, which defines the "namespace" of HTML markup. ECMAScript restricts the range of characters that can appear at the start or in the body of an identifier or variable name (while different rules apply to the values of, say, string literals). The term "namespace" ought not be confused with similar terminology in, for example, the definition of URLs [RFC3986].

Following example has accessibility issues and is hard to use in hardcopy

Figure 1: Terminology examples

<html>
<head>
  <title>
Shakespeare</title>
</head>
<body>
  <img src="shakespeare.jpg" alt="William Shakespeare" id="shakespeare image">

  <p>
What&#x2019;s in a name? That which we call a rose by any other name would smell as sweet.</p>
</body>
</html>

Examples: Text with a gray background is markup. Text in blue is Shakespeare. Text in magenta are user values.

All of the text above (all text in a text file) makes up the Wildebeest. It's possible that a given Wildebeest will contain no Shakespeare at all (consider an HTML document consisting of four empty div elements styled to be orange rectangles). It's also possible that a Wildebeest will contain no markup and consist solely of Shakespeare: for example, a plain text file with a soliloquy from Hamlet in it. Notice too that the HTML entity &#x2019; appears in the Shakespeare and belongs to both Shakespeare and markup.

1.5 Conformance

As well as sections marked as non-normative, all authoring guidelines, diagrams, examples, and notes in this specification are non-normative. Everything else in this specification is normative.

The key words MUST, MUST NOT, REQUIRED, SHOULD, SHOULD NOT, RECOMMENDED, MAY, and OPTIONAL in this specification are to be interpreted as described in [RFC2119].

Conformance

This specification places conformance criteria on specifications, on software (implementations) and on Web content. To aid the reader, all conformance criteria are preceded by '[X]' where 'X' is one of 'S' for specifications, 'I' for software implementations, and 'C' for Web content. These markers indicate the relevance of the conformance criteria and allow the reader to quickly locate relevant conformance criteria by searching through this document.

Specifications conform to this document if they:

  1. do not violate any conformance criteria preceded by [S],

  2. document the reason for any deviation from criteria where the imperative is SHOULD, SHOULD NOT, or RECOMMENDED,

  3. make it a conformance requirement for implementations to conform to this document,

  4. make it a conformance requirement for content to conform to this document.

Software conforms to this document if it does not violate any conformance criteria preceded by [I].

Content conforms to this document if it does not violate any conformance criteria preceded by [C].

Note

NOTE: Requirements placed on specifications might indirectly cause requirements to be placed on implementations or content that claim to conform to those specifications.

Where this specification contains a procedural description, it is to be understood as a way to specify the desired external behavior. Implementations can use other means of achieving the same results, as long as observable behavior is not affected.

2. The String Matching Problem

The basis for most Web document formats and protocols is text that includes some form of structural markup. When processing document formats based on text, operations such as string matching, indexing, searching, sorting, regular expression matching, and so forth become sensitive to the different ways in which text might be represented in the document. The proper functioning of the Web (and of much other software) depends to a large extent on string matching. A specification or implementation that does not consider these different ways of representing text could confuse users or behave in an unexpected or frustrating manner.

2.1 Legacy Character Encodings

Different character encoding schemes, including legacy character encodings, can be used to serialize document formats on the Web. Each character encoding scheme uses different byte values and sequences to represent a given subset of the Universal Character Set.

As a further complication, document formats or protocols usually also have escape mechanisms. These allow for the encoding of characters not represented in the character encoding scheme used by the document or for convenience of the editor). Escape mechanisms introduce additional equivalent representations.

For example, € (U+20AC EURO SIGN) is encoded as 0x80 in the windows-1252 encoding, but as the byte sequence 0xE2.82.AC in UTF-8.

Specifications mainly address these resulting variations by considering each document to be a sequence of Unicode characters after converting from the document's character encoding (be it a legacy character encoding or a Unicode encoding such as UTF-8) and then unescaping any character escapes before proceeding to process the document. But even a single character encoding that has been unescaped can provide multiple representations for the 'same' string.

The following paragraphs about normalization transcoders are "at risk". The WG feels that this requirement is difficult for content authors or implementers to verify. Needed action: verify if all of [Encoding] spec's transcoders are normalizing.

Note

Even within a single legacy character encoding there can be variations in implementation. One famous example is the legacy Japanese encoding Shift_JIS. Different transcoder implementations faced choices about how to map specific byte sequences to Unicode. So the byte sequence 0x80.60 (0x2141 in the JIS X 0208 character set) was mapped by some implementations to U+301C WAVE DASH while others chose U+FF5E FULL WIDTH TILDE. This means that two reasonable, self-consistent, transcoders could produce different Unicode character sequences from the same input. The [Encoding] specification exists, in part, to ensure that Web implementations use interoperable and identical mappings. However, extant transcoders might be applied to documents found on the Web.

For content authors and implementations, it is RECOMMENDED that conversions from legacy character encodings use a "normalizing transcoder".

A normalizing transcoder is a transcoder that converts from a legacy character encoding to a Unicode encoding form and ensures that the result is in Unicode Normalization Form C. For most legacy character encodings, it is possible to construct a normalizing transcoder (by using any transcoder followed by a normalizer); it is not possible to do so if the encoding's repertoire contains characters not represented in Unicode.

2.2 Character Escapes

Document formats or protocols also add escape mechanisms, providing additional means of representing characters inside a given Wildebeest. These allow for the encoding of characters not represented in the character encoding scheme used by the document or for convenience of the editor. Escape mechanisms introduce additional equivalent representations.

For example, € (U+20AC EURO SIGN) can also be encoded in HTML as the hexadecimal entity &#x20ac; or as the decimal entity &#8364;. In a JavaScript or JSON file, it can appear as \u20ac while in a CSS stylesheet it can appear as \20ac. All of these representations encode the same literal character value: "€".

Character escapes are normally interpreted before a document is processed and strings within the format or protocol are matched. Consider this HTML fragment:

<style type="text/css">

  span.h\e9llo {
     color: red;
  }
</style>

<span class="h&#xe9;llo">Hello World!</span>

You would expect that text to display like the following: Hello world!

In order for this to work, the user-agent (browser) had to match two strings representing the class name héllo, even though the CSS and HTML didn't encode them in exactly the same way. The above fragment demonstrates one way that text can vary and still be considered "the same" according to a specification: the class name h\e9llo matched the class name in the HTML mark-up h&#xe9;llo (and would also match the literal value héllo using the code point U+00E9).

2.3 Unicode Normalization

Variations in character encoding or escaping syntax are not the only variations that can occur in Unicode text. Some "characters" or graphemes can be represented by several different Unicode code point sequences. Consider the character Ǻ LATIN LETTER CAPITAL A WITH RING ABOVE AND ACUTE. Here are some of the different ways that an HTML document could represent this character:

Code Points Description
Ǻ U+01FA A "precomposed" character.
Ǻ A + ̊ (U+030A) +  ́ (U+0301) A "base" letter "A" with two combining marks
Ǻ Å (U+00C5) +  ́ (U+0301) An accented letter (U+00C5) with combining mark
Ǻ Å (U+212B) +  ́ (U+0301) Compatibility character (U+212B ANGSTROM SIGN) with combining mark
Ǻ A (U+FF21) +  ̊ (U+030A) +  ́ (U+0301) Compatibility character U+FF21 FULLWIDTH LATIN LETTER CAPITAL A) with combining marks

As in the first example, each of the above strings contains the same apparent semantic meaning (Ǻ), but each one is encoded slightly differently. More variations are possible, but are omitted for brevity: for example, any of the characters could be replaced with an HTML entity.

Because applications need to find the semantic equivalence in texts that use different code point sequences, Unicode defines a means of making two semantically equivalent texts identical: the Unicode Normalization Forms [UAX15].

Document formats or protocols are sensitive to these variations because their specifications and implementations on the Web generally do not supply Unicode Normalization of the content being exchanged or in the string matching algorithms used when processing the markup and content later. Users and Wildebeest need to ensure that they have provided a consistent representation in order to avoid problems later. It can be difficult for users to assure that a given Wildebeest or set of Wildebeests uses a consistent textual representation because the differences are usually not visible when viewing Wildebeest as text. Tools and implementations thus need to consider the difficulties experienced by users when visually or logically equivalent strings that "ought to" match (in the user's mind) are considered to be distinct values. Providing a means for users to see these differences and/or normalize them as appropriate makes it possible for end users to avoid failures that spring from invisible differences in their source documents. For example, the W3C Validator warns when an HTML document is not fully in Unicode Normalization Form C.

2.3.1 Unicode Normalization Forms

Unicode defines two types of equivalence between characters: canonical equivalence and compatibility equivalence.

Canonical equivalence is a fundamental equivalency between Unicode characters or sequences of Unicode characters that represent the same abstract character. When correctly displayed, these should always have the same visual appearance and behavior. Generally speaking, two canonically equivalent Unicode texts should be considered to be identical as text. Canonical decomposition removes primary distinctions between two texts.

Canonical Equivalence
Combining sequence Ç C ◌̧
Ordering of combining marks q + ̇ + ̣ q + ̣ + ̇
Hangul ᄀ + ᅡ
Singleton Ω Ω

Add Unicode code points to above table. Add clarifying text. Potentially add a sidebar note about Hangul's specific complexity.

Compatibility equivalence is a weaker equivalence between characters or sequences of characters that represent the same abstract character, but may have a different visual appearance or behavior. Generally a compatibility decomposition removes formatting variations, such as superscript, subscript, rotated, circled, and so forth, but other variations also occur. In many cases, characters with compatibility decompositions represent a distinction of a semantic nature; replacing the use of distinct characters with their compatibility decomposition can therefore cause problems and texts that are equivalent after compatibility decomposition often were not perceived as being identical beforehand and usually should not be treated as equivalent by a formal language.

The following table illustrates various kinds of compatibility equivalence in Unicode:

Compatibility Equivalence
Font variants
Non-breaking U+00A0 NON-BREAKING SPACE
Presentation forms of Arabic (initial, medial, final, isolated)
Circled
East Asian Width, size, rotated presentation forms {
Superscripts/subscripts
"Squared" characters
Fractions ¼
Others dž
Note

In the above table, it is important to note that the characters illustrated are actual Unicode codepoints. They were encoded into Unicode for compatibility with various legacy character encodings. They should not be confused with the normal kinds of presentational processing used on their non-compatibility counterparts.

For example, most Arabic-script text uses the characters in the Arabic script block of Unicode (around U+0600). The actual glyphs used in the text are selected using fonts and text processing logic based on the position inside a word (initial, medial, final, or isolated), in a process called "shaping". In the table above, the four presentation forms of the Arabic letter NOON are shown. The characters shown are compatibility characters in the U+FE00 block, each of which represents a specific "positional" shape and each of the four code points shown have a compatibility decomposition to the "regular" Arabic letter NOON (U+0646).

Similarly, the variations in East Asian width and the rotated bracket (for use in vertical text) are encoded as separate code points.

In the case of characters with compatibility decompositions, such as those shown above, the "K" Unicode Normalization forms convert the text to the "normal" or "expected" Unicode code point. But the existence of these compatibility characters cannot be taken to imply that similar appearance variations produced in the normal course of text layout and presentation are affected by Unicode Normalization. They are not.

Improve above examples, which are taken from UAX15, by adding more of each type and clarifying the "breaking differences" item. The table seems to be confused with "normal" character sequences—which isn't the point. Perhaps a better illustration than Unicode's is needed. 😿

These two types of Unicode-defined equivalence are then grouped by another pair of variations: "decomposition" and "composition". In "decomposition", separable logical parts of a visual character are broken out into a sequence of base characters and combining marks and the resulting code points are put into a fixed, canonical order. In "composition", the decomposition is performed and then any combining marks are recombined, if possible, with their base characters. Note that this does not mean that all of the combining marks have been removed from the resulting normalized text.

The Unicode Normalization Forms are named using letter codes, with 'C' standing for Composition, 'D' for Decomposition, and 'K' for Compatibility decomposition. Having converted a Wildebeest to a sequence of Unicode characters and unescaped any escape sequences, we can finally "normalize" the Unicode texts given in the example above. Here are the resulting sequences in each Unicode Normalization form for the U+01FA example given earlier:

Original Codepoints NFC NFD NFKC NFKD
Ǻ
U+01FA
Ǻ
U+01FA
Ǻ
U+0041 U+030A U+0301
Ǻ
U+01FA
Ǻ
U+0041 U+030A U+0301
Ǻ
U+00C5 U+0301
Ǻ
U+01FA
Ǻ
U+0041 U+030A U+0301
Ǻ
U+01FA
Ǻ
U+0041 U+030A U+0301
Ǻ
U+212B U+0301
Ǻ
U+01FA
Ǻ
U+0041 U+030A U+0301
Ǻ
U+01FA
Ǻ
U+0041 U+030A U+0301
Ǻ
U+0041 U+030A U+0301
Ǻ
U+01FA
Ǻ
U+0041 U+030A U+0301
Ǻ
U+01FA
Ǻ
U+0041 U+030A U+0301
Ǻ
U+FF21 U+030A U+0301
Ǻ
U+FF21 U+030A U+0301
Ǻ
U+FF21 U+030A U+0301
Ǻ
U+01FA
Ǻ
U+0041 U+030A U+0301

Unicode Normalization reduces these (and other potential sequences of escapes representing the same character) to just three possible variations. However, Unicode Normalization doesn't remove all textual distinctions and sometimes the application of Unicode Normalization can remove meaning that is distinctive or meaningful in a given context. For example:

  • Not all compatibility characters have a compatibility decomposition.
  • Some characters that look alike or have similar semantics are actually distinct in Unicode and don't have canonical or compatibility decompositions to link them together. For example, U+3001 IDEOGRAPHIC FULL STOP is used as a "period" at the end of sentences in languages such as Chinese or Japanese. However, it is not considered equivalent to the ASCII "period" character U+002E FULL STOP.
  • Some character variations are not handled by normalization. For example, UPPER, Title, and lowercase variations are a separate and distinct textual variation that must be separately normalized.
  • Normalization can remove meaning. For example, (including the character U+00BD VULGAR FRACTION ONE HALF), when normalized using one of the "compatibility" normalization forms, becomes a character sequence that looks more like: 81/2.

2.3.2 Choice of Normalization Form

Given that there are many character sequences that content authors or applications could choose when inputting or exchanging text, and that when providing text in a normalized form, there are different options for the normalization form to be used, what form is most appropriate for content on the Web?

For use on the Web, it is important not to lose compatibility distinctions, which are often important to the content (see [UNICODE-XML] Chapter 5 for a discussion). The NFKD and NFKC normalization forms are therefore excluded. Among the remaining two forms, NFC has the advantage that almost all legacy data (if transcoded trivially, one-to-one, to a Unicode encoding), as well as data created by current software, is already in this form; NFC also has a slight compactness advantage and is a better match to user expectations with respect to the character vs. grapheme issue. This document therefore recommends, when possible, that all content be stored and exchanged in Unicode Normalization Form C (NFC).

Note

Roughly speaking, NFC is defined such that each combining character sequence (a base character followed by one or more combining characters) is replaced, as far as possible, by a canonically equivalent precomposed character. Text in a Unicode encoding form is said to be in NFC if it doesn't contain any combining sequence that could be replaced and if any remaining combining sequence is in canonical order.

2.4 Casefolding

A different form of text normalization that can be applied to content on the Web is casefolding. Some scripts and writing systems have a distinction between upper, lower, and title case characters (Latin script, used in the majority of this document, is one of them). Other scripts, such as Brahmic scripts of India, the Arabic script, and the non-Latin scripts used to write Chinese, Japanese, or Korean do not have a case distinction. In fact, most of the scripts encoded in Unicode do not have a concept of case distinction.

The process of making two texts which differ in case but are otherwise "the same" identical is called "casefolding". Casefolding might, at first, appear simple, but, as with Unicode Normalization, there are variations and considerations that need to be considered when treating the full range of Unicode in diverse languages. Unicode [UNICODE] Section 5.18 discusses casefolding in detail.

Case folding in Unicode has a number of side-effects or potential side-effects on the source content. One is that case folding may not preserve the length of the original text: some mappings increase or decrease the total number of characters needed. In addition, case folding, like Unicode Normalization, removes information from a string which cannot be recovered later.

Another aspect of case folding is that it can be language sensitive. Unicode defines default case mappings for each encoded character, but these are only defaults. Some languages need case-folding to be tailored to meet specific linguistic needs. One common example of this are Turkic languages written in the Latin script.

The Turkish word "Diyarbakır" contains both the dotted and dotless letters "i". When rendered into upper case, this word appears like this: "DİYARBAKIR". Notice that the ASCII letter "i" maps to U+0130 (LATIN CAPITAL LETTER I WITH DOT ABOVE), while the letter "ı" (U+0131 LATIN SMALL LETTER DOTLESS I) maps to the ASCII uppercase "I".

Case-sensitive matching is the easiest to implement and introduces the least potential for confusion, since it generally consists of a comparison of the underlying Unicode code point sequence. Because it is not affected by considerations such as language-specific case mappings, it produces the least surprise for document authors that have included words (such as the Turkish example above) in their markup.

Case-insensitive matching is useful in contexts where case may vary in a way that is not semantically meaningful or in which case distinctions cannot be controlled by the user. This is particularly true when searching a document, but also applies when defining rules for matching user- or content-generated values, such as identifiers.

3. String Matching of Markup in Document Formats and Protocols

This chapter defines the implementation and requirements for string matching in markup.

3.1 The Matching Algorithm

This section defines the algorithm for matching strings. String identity matching MUST be performed as if the following steps were followed:

  1. Conversion to a common Unicode encoding form of the strings to be compared [Encoding].
  2. Expansion of all character escapes and includes.

    Note

    The expansion of character escapes and includes is dependent on context, that is, on which markup or programming language is considered to apply when the string matching operation is performed. Consider a search for the string 'suçon' in an XML document containing su&#xE7;on but not suçon. If the search is performed in a plain text editor, the context is plain text (no markup or programming language applies), the &#xE7; character escape is not recognized, hence not expanded and the search fails. If the search is performed in an XML browser, the context is XML, the character escape (defined by XML) is expanded and the search succeeds.

    An intermediate case would be an XML editor that purposefully provides a view of an XML document with entity references left unexpanded. In that case, a search over that pseudo-XML view will deliberately not expand entities: in that particular context, entity references are not considered includes and need not be expanded

  3. Perform the appropriate case folding:
    1. Case sensitive: Go to step 4.
    2. ASCII case folding: map all code points in the range 0x41 to 0x5A (A to Z) to the corresponding code points in the range 0x61 to 0x7A (a to z).
    3. Unicode case folding: map all code points to their Unicode C+F case fold equivalents. Note that this can change the length of the string.
  4. Test the resulting sequences of code points bit-by-bit for identity.

There are three types of casefold matching defined for the purposes of string identity matching in document formats or protocols:

Case sensitive matching: code points are compared directly with no case folding. Case sensitive matching is RECOMMENDED as the default for any new protocol or format.

Unicode case-insensitive matching compares a sequence of code points as-if one of the Unicode-defined language-independent default case folding forms (see [UNICODE], Section 5.18) had been applied to both input sequences. These forms are:

  1. Unicode Full Casefold (C+F). This case-fold form is RECOMMENDED for Web specifications and implementations. This case-fold uses the "common" plus the "full" case-fold.
  2. Unicode Simple Casefold (C+S). Unicode also defines a "common" plus "simple" case-fold. This form is not appropriate for string identity matching on the Web.
Note

In the rare case where a document format or protocol contains information about the language of the markup and where language-sensitive processing might sensibly be applied, tailoring of the Unicode case-fold mappings above to match the expectations of that language might be specified and applied. These case-fold mappings are defined in the Common Locale Data Repository [UAX35] project of the Unicode Consortium.

However, language-sensitive case-sensitive matching in document formats and protocols is NOT RECOMMENDED because language information can be hard to obtain, verify, or manage and the resulting operations can produce results that frustrate users.

ASCII case-insensitive matching compares a sequence of code points as if all ASCII code points in the range 0x41 to 0x5A (A to Z) were mapped to the corresponding code points in the range 0x61 to 0x7A (a to z).

3.2 Requirements for String Identity Matching

In the Web environment, where multiple character encodings are used to represent strings, including some character encodings which allow multiple representations for the same thing, it's important to establish a consistent process for evaluating string identity.

One main consideration in string identity matching is whether the comparison is case sensitive or case insensitive.

[S] Case sensitive matching is RECOMMENDED as the default for new protocols and formats.

However, cases exist in which case-insensitivity is desirable.

Where case-insensitive matching is desired, there are several implementation choices that a formal language needs to consider. If the namespace of strings to be compared is limited to the Basic Latin (ASCII) subset of Unicode, ASCII-case-insensitive matching MAY be used.

If the namespace of strings to be compared is not limited, then ASCII case-insensitive matching MUST NOT be used. Unicode case-insensitive matching MUST be applied, even if the namespace does not allow the full range of Unicode.

Unicode case-insensitive matching can take several forms. Unicode defines the "common" (C) casefoldings for characters that always have 1:1 mappings of the character to its case folded form and this covers the majority of characters that have a case folding. A few characters in Unicode have a 1:many case folding. This 1:many mapping is called the "full" (F) case fold mapping. For compatibility with certain types of implementation, Unicode also defines a "simple" (S) case fold that is always 1:1.

Because the "simple" case-fold mapping removes information that can be important to forming an identity match, the "Common plus Full" (or CF) case fold mapping is RECOMMENDED for Unicode case-insensitive matching.

A namespace is considered to be "ASCII-only" if and only if all tokens and identifiers are defined by the specification directly and these identifiers or tokens use only the Basic Latin subset of Unicode. If user-defined identifiers are permitted, the full range of Unicode characters (limited, as appropriate, for security or interchange concerns, see [UTR36]) SHOULD be allowed and Unicode case insensitivity used for identity matching.

ASCII case-insensitive matching MUST only be applied to namespaces that are restricted to ASCII. Unicode case-insensitivity MUST be used for all other namespaces.

Note that an ASCII-only namespace can exist inside a document format or protocol that allows a larger range of Unicode in identifiers or values.

Insert example from CSS here.

3.2.1 Requirements for Wildebeest

These requirements pertain to the authoring and creation of documents and are intended as guidelines for wildebeest authors.

[C] Wildebeest SHOULD be produced, stored, and exchanged in Unicode Normalization Form C (NFC).

Note

In order to be processed correctly wildebeest must use a consistent sequence of code points to represent text. While content can be in any normalization form or may use a de-normalized (but valid) Unicode character sequence, inconsistency of representation will cause implementations to treat the different sequence as "different". The best way to ensure consistent selection, access, extraction, processing, or display is to always use NFC.

[I] Implementations MUST NOT normalize any wildebeest during processing, storage, or exchange except with explicit permission from the user.

[I] Implementations which transcode text from a legacy character encoding to a Unicode encoding form SHOULD use a normalizing transcoder that produces Unicode Normalization Form C (NFC).

[C] Authors SHOULD NOT include combining marks without a preceding base character in Wildebeest.

Following examples need improvement.

There can be exceptions to this, for example, when making a list of characters (such as a Unicode demo). This avoids problems with unintentional display or with naive implementations that combine the combining mark with adjacent markup or other Shakespeare. For example, if you were to use U+301 as the start of a "class" attribute value in HTML, the class name might not display properly in your editor.

[C] Identifiers SHOULD use consistent case (upper, lower, mixed case) to facilitate matching, even if case-insensitive matching is supported by the format or implementation.

3.2.2 Requirements for Specifications

These requirements pertain to specifications for document formats or programming/scripting languages and their implementations.

[S] Specifications of text-based formats and protocols MAY specify that all or part of the textual content of that format or protocol is normalized using Unicode Normalization Form C (NFC).

Specifications are generally discouraged from requiring formats or protocols to store or exchange data in a normalized form unless there are specific, clear reasons why the additional requirement is necessary. As many document formats on the Web do not require normalization, content authors might occasionally rely on denormalized character sequences and a normalization step could negatively affect such content.

Note

Requiring NFC requires additional care on the part of the specification developer, as content on the Web generally is not in a known normalization state. Boundary and error conditions for denormalized content need to be carefully considered and well specified in these cases.

[S][I] Specifications and implementations that define string matching as part of the definition of a format, protocol, or formal language (which might include operations such as parsing, matching, tokenizing, etc.) MUST define the criteria and matching forms used. These MUST be one of:

  • Case-sensitive
  • Unicode case-insensitive using Unicode case-folding C+F
  • ASCII case-insensitive

[S] Specifications SHOULD NOT specify case-insensitive comparison of strings.

[S] Specifications that specify case-insensitive comparison for non-ASCII namespaces SHOULD specify Unicode case-folding C+F.

In some limited cases, locale- or language-specific tailoring might also be appropriate. However, such cases are generally linked to natural language processing operations. Because they produce potentially different results from the generic case folding rules, these should be avoided in formal languages, where predictability is at a premium.

[S] Specifications MAY specify ASCII case-insensitive comparison for portions of a format or protocol that are restricted to an ASCII-only namespace.

This requirement applies to formal languages whose keywords are all ASCII and which do not allow user-defined names or identifiers. An example of this is HTML, which defines the use of ASCII case-insensitive comparison for element and attribute names defined by the HTML specification.

[S][I] Specifications and implementations MUST NOT specify ASCII-only case-insensitive matching for values or constructs that permit non-ASCII characters.

3.2.3 Non-Normalizing Specification Requirements

The following requirements pertain to any specification that specifies normalization explicitly (which SHOULD include all new specifications):

[S] Specifications that do not normalize MUST document or provide a health-warning if canonically equivalent but disjoint Unicode character sequences represent a security issue.

[S][I] Specifications and implementations MUST NOT assume that content is in any particular normalization form.

The normalization form or lack of normalization for any given content has to be considered intentional in these cases.

[S][I] For namespaces and values that are not restricted to Basic Latin (ASCII), case-insensitive matching MUST specify either UniCF or locale-sensitive string comparison.

[I] Implementations MUST NOT alter the normalization form of content being exchanged, read, parsed, or processed except when required to do so as a side-effect of transcoding the content to a Unicode character encoding, as content might depend on the de-normalized representation.

[S] Specifications MUST specify that string matching takes the form of "code point-by-code point" comparison of the Unicode character sequence, or, if a specific Unicode character encoding is specified, code unit-by-code unit comparison of the sequences.

Following requirements added 2013-10-29. Needs discussion of regular expressions.

[S][I] Specifications that define a regular expression syntax MUST provide at least Basic Unicode Level 1 support per [UTS18] and SHOULD provide Extended or Tailored (Levels 2 and 3) support.

3.2.4 Unicode Normalizing Specification Requirements

For specifications of text-based formats and protocols that define Unicode Normalization as a requirement, the following requirements apply:

[S] Specifications of text-based formats and protocols that, as part of their syntax definition, require that the text be in normalized form MUST define string matching in terms of normalized string comparison and MUST define the normalized form to be NFC.

[S] [I] A normalizing text-processing component which receives suspect text MUST NOT perform any normalization-sensitive operations unless it has first either confirmed through inspection that the text is in normalized form or it has re-normalized the text itself. Private agreements MAY, however, be created within private systems which are not subject to these rules, but any externally observable results MUST be the same as if the rules had been obeyed.

[I] A normalizing text-processing component which modifies text and performs normalization-sensitive operations MUST behave as if normalization took place after each modification, so that any subsequent normalization-sensitive operations always behave as if they were dealing with normalized text.

[S] Specifications of text-based languages and protocols SHOULD define precisely the construct boundaries necessary to obtain a complete definition of full-normalization. These definitions SHOULD include at least the boundaries between markup and character data as well as entity boundaries (if the language has any include mechanism) , SHOULD include any other boundary that may create denormalization when instances of the language are processed, but SHOULD NOT include character escapes designed to express arbitrary characters.

[I] Authoring tool implementations for a formal language that does not mandate full-normalization SHOULD either prevent users from creating content with composing characters at the beginning of constructs that may be significant, such as at the beginning of an entity that will be included, immediately after a construct that causes inclusion or immediately after markup, or SHOULD warn users when they do so.

[S] Where operations can produce denormalized output from normalized text input, specifications of API components (functions/methods) that implement these operations MUST define whether normalization is the responsibility of the caller or the callee. Specifications MAY state that performing normalization is optional for some API components; in this case the default SHOULD be that normalization is performed, and an explicit option SHOULD be used to switch normalization off. Specifications SHOULD NOT make the implementation of normalization optional.

[S] Specifications that define a mechanism (for example an API or a defining language) for producing textual data object SHOULD require that the final output of this mechanism be normalized.

4. String Searching in Shakespeare

Many Web implementations and applications have a different sort of string matching requirement from the one described above: the need for users to search documents for particular words or phrases of text. This section addresses the various considerations that an implementer might need to consider when implementing natural language text processing on the Web other than that mandated by a formal language or document format.

There are several different kinds of string searching.

When you are using a search engine, you are generally using a form of full text search. Full text search generally breaks natural language text into word segments and may apply complex processing to get at the semantic "root" values of words. For example, if the user searches for "run", you might want to find words like "running", "ran", or "runs" in addition to the actual search term "run". This process, naturally, is sensitive to language, context, and many other aspects of textual variation. It is also beyond the scope of this document.

Another form of string searching, which we'll concern ourselves with here, is sub-string matching or "find" operations. This is the direct searching of the body or "corpus" of a document with the user's input. Find operations can have different options or implementation details, such as the addition or removal of case sensitivity, or whether the feature supports different aspects of a regular expression language or "wildcards".

4.1 Considerations for Matching Natural Language Content

This section was identified as a new area needing document as part of the overall rearchitecting of the document. The text here is incomplete and needs further development. Contributions from the community are invited.

Searching content (one example is using the "find" command in your browser) generates different user expectations and thus has different requirements from the need for absolute identity matching needed by document formats and protocols. Searching text has different contextual needs and often provides different features.

One description of Unicode string searching can be found in Section 8 (Searching and Matching) of [UTS10].

One of the primary considerations for string searching is that, quite often, the user's input is not identical to the way that the text is encoded in the text being searched. Users generally expect matching to be more "promiscuous", particularly when they don't add additional effort to their input. For example, they expect a term entered in lowercase to match uppercase equivalents. Conversely, when the user expends more effort on the input—by using the shift key to produce uppercase or by entering a letter with diacritics instead of just the base letter—they expect their search results to match (only) their more-specific input.

This effect might vary depending on context as well. For example, a person using a physical keyboard may have direct access to accented letters, while a virtual or on-screen keyboard may require extra effort to access and select the same letters.

Consider a document containing these strings: "re-resume", "RE-RESUME", "re-rèsumé", and "RE-RÈSUMÉ".

In the table below, the user's input (on the left) might be considered a match for the above items as follows:

User Input Matched Strings
e (lowercase 'e') "re-resume", "RE-RESUME", "re-rèsumé", and "RE-RÈSUMÉ"
E (uppercase 'E') "RE-RESUME" and "RE-RÈSUMÉ"
è (lowercase 'e' with accent grave) "re-rèsumé" and "RE-RÈSUMÉ"
È "RE-RÈSUMÉ"

In addition to variations of case or the use of accents, Unicode also has an array of canonical equivalents or compatibility characters (as described in the sections above) that might impact string searching.

For example, consider the letter "K". Characters with a compatibility mapping to U+004B LATIN CAPITAL LETTER K include:

  1. Ķ U+0136
  2. Ǩ U+01E8
  3. ᴷ U+1D37
  4. Ḱ U+1E30
  5. Ḳ U+1E32
  6. Ḵ U+1E34
  7. K U+212A
  8. Ⓚ U+24C0
  9. ㎅ U+3385
  10. ㏍ U+33CD
  11. ㏎ U+33CE
  12. K U+FF2B
  13. (a variety of mathematical symbols such as U+1D40A,U+1D43E,U+1D472,U+1D4A6,U+1D4DA)
  14. 🄚 U+1F11A
  15. 🄺 U+1F13A.

Other differences include Unicode Normalization forms (or lack thereof). There are also ignorable characters (such as the variation selectors), whitespace differences, bidirectional controls, and other code points that can interfere with a match.

Users might also expect certain kinds of equivalence to be applied to matching. For example, a Japanese user might expect that hiragana, katakana, and half-width compatibility katakana equivalents all match each other (regardless of which is used to perform the selection or encoded in the text).

When searching text, the concept of "grapheme boundaries" and "user-perceived characters" can be important. See Section 3 of [CHARMOD] for a description. For example, if the user has entered a capital "A" into a search box, should the software find the character À (U+00C0 LATIN CAPITAL LETTER A WITH ACCENT GRAVE)? What about the character "A" followed by U+0300 (a combining accent grave)? What about writing systems, such as Devanagari, which use combining marks to suppress or express certain vowels?

5. Acknowledgements

The W3C Internationalization Working Group and Interest Group, as well as others, provided many comments and suggestions. The Working Group would like to thank: Mati Allouche, John Klensin,

The previous version of this document was edited by:

A. References

A.1 Normative references

[CHARMOD]
Martin Dürst; François Yergeau; Richard Ishida; Misha Wolf; Tex Texin et al. Character Model for the World Wide Web 1.0: Fundamentals. 15 February 2005. W3C Recommendation. URL: http://www.w3.org/TR/charmod/
[ISO10646]
Information Technology - Universal Multiple- Octet Coded CharacterSet (UCS) - Part 1: Architecture and Basic Multilingual Plane. ISO/IEC10646-1:1993. The current specification also takes into consideration the first five amendments to ISO/IEC 10646-1:1993. Useful <a href="http://www.egt.ie/standards/iso10646/ucs-roadmap.html">roadmaps</a>show which scripts sit at which numeric ranges.
[RFC2119]
S. Bradner. Key words for use in RFCs to Indicate Requirement Levels. March 1997. Best Current Practice. URL: http://www.ietf.org/rfc/rfc2119.txt
[UAX15]
Mark Davis; Ken Whistler. Unicode Normalization Forms. 31 August 2012. Unicode Standard Annex #15. URL: http://www.unicode.org/reports/tr15/
[UNICODE]
The Unicode Standard. URL: http://www.unicode.org/versions/latest/
[UTS18]
Mark Davis; Andy Heninger. Unicode Technical Standard #18: Unicode Regular Expressions. URL: http://unicode.org/reports/tr18/

A.2 Informative references

[CHARREQ]
Martin Dürst. Requirements for String Identity Matching and String Indexing. 15 September 2009. W3C Note. URL: http://www.w3.org/TR/charreq/
[Encoding]
Anne van Kesteren; Joshua Bell; Addison Phillips. Encoding. URL: http://www.w3.org/TR/encoding/
[RFC3986]
T. Berners-Lee; R. Fielding; L. Masinter. Uniform Resource Identifier (URI): Generic Syntax. January 2005. Internet Standard. URL: http://www.ietf.org/rfc/rfc3986.txt
[UAX35]
Mark Davis; CLDR committee members. Unicode Locale Data Markup Language (LDML). 15 March 2013. Unicode Standard Annex #35. URL: http://www.unicode.org/reports/tr35/tr35-31/tr35.html
[UNICODE-XML]
Richard Ishida. Unicode in XML and other Markup Languages. 24 January 2013. W3C Note. URL: http://www.w3.org/TR/unicode-xml/
[UTR36]
Mark Davis; Michel Suignard. Unicode Technical Report #36: Unicode Security Considerations. URL: http://www.unicode.org/reports/tr36/
[UTS10]
Mark Davis; Ken Whistler; Markus Scherer. Unicode Technical Standard #10: Unicode Collation Algorithm. URL: http://www.unicode.org/reports/tr10/
[XML10]
Tim Bray; Jean Paoli; Michael Sperberg-McQueen; Eve Maler; François Yergeau et al. Extensible Markup Language (XML) 1.0 (Fifth Edition). 26 November 2008. W3C Recommendation. URL: http://www.w3.org/TR/xml/