RE: Implementing NFC

From: Philippe Verdy (
Date: Thu Mar 15 2007 - 22:42:29 CST

  • Next message: Hans Aberg: "Re: Arabic numbers"

    Note that for NFD (and NFKD) it's not enough to decompose the characters
    recursively; you also need to reorder them according to their combining
    class (except for those whose combining class is 0 that are limiting the
    span of characters that can be reordered). You also have to decompose the
    Hangul syllables algorithmically (they are absent from the UCD tables)

    For NFC (and NFKC), it's also not enough to only recompose the pairs,
    because some decomposable characters followed by a combining characters will
    have to be recomposed in another way, by permuting the combining characters
    if they have different non-zero combining classes, and then recompose the
    first one.

    Note also that when composing pairs, the NFC or NFKC forms will sometime
    have to compose non-adjacent characters, where there may be an intermediate
    combining character with a non-zero combining class between the base
    character and the combining character selected for combination: this occurs
    when there's no composition possible with the first combining character, but
    the composition is possible with the next one, provided that it has a
    *different* non-zero combining class.

    Suppose that the combining classes of characters are like this in a string
    in NFD form:
            [0, 220, 230, 0]
    If composition is not possible with the first two characters, it may be
    possible with the (0, 230) pair and the result will be the string whose
    character combining classes will be [0, 220, 0] where the first zero results
    of the composition of the first and third character. This still preserves
    the canonical equivalence because this composed string will still be
    reordered when decomposed...

    There are also a few combining characters that are precomposed pairs but
    must be decomposed first because one of them will recompose with a prior
    base character. This occurs for example with the Greek character block)

    When computing NFC and NFKC, you still need to compute the reordering of
    combining characters even if there's no way to assemble them in pairs,
    because not all of them are composable in pairs (or triples for algorithmic
    Hangul syllables but these do not require reordering).

    Finally when composing characters, be warned that some precomposed
    characters are excluded from recomposition (so they must be decomposed in
    NFD or NFKD, but not be recomposed in NFC or NFKC; these characters are then
    necessarily absent from strings in all four normalized forms, and they are
    present in Unicode only for round-trip compatibility with past encodings, or
    sometimes excluded of recompositions for stability of the normalized forms
    across Unicode versions). You may eventually compose them without breaking
    the canonical equivalence, but the resulting string will not be in the
    stable normalized form (this means that a string in NFC form is not
    necessarily the shorted one within the set of canonically equivalent
    strings: NFC is not a compression algorithm).

    > -----Message d'origine-----
    > De : [] De la
    > part de Daniel Ehrenberg
    > Envoyé : vendredi 16 mars 2007 03:49
    > À :
    > Objet : Implementing NFC
    > Hi,
    > I'm working on adding Unicode support (possibly eventually conformace)
    > to an obscure programming language called Factor, which is sort of a
    > cross between Forth and Lisp (see for more
    > information). One thing that I'm doing is that all strings will always
    > be kept in Normalization Form D (as defined in UAX #15: Normalization
    > Forms) for processing. That way all canonically equivalent strings
    > return true when tested for equality. It wasn't difficult to implement
    > NFD (or NFKD); I just needed to read the transformations from
    > UnicodeData.txt and apply them recursively to get a hash table of
    > characters to canonical/compatability-decomposed strings. But for most
    > I/O purposes, I need to use NFC, re-composing all decomposed
    > characters. I have no idea how to do this efficiently. In many cases,
    > it's more complicated than just turning two adjacent characters into
    > one character.
    > I looked at both the Glib source (which defines basic unicode
    > operations) and the Normalizer demo that UAX 15 links to (which, btw,
    > only works properly for the BMP, which is bad). They both appear to
    > use generally the same strategy: perform as many pairwise compositions
    > on adjacent characters as possible. I wonder if I'm reading it wrong,
    > because if that's how it operates, then one of the examples in the UAX
    > wouldn't work properly: NFC(U+017F U+0323 U+0307) = U+1E9B U+0323.
    > This composes two non-adjacent characters. Is there any efficient way
    > to do this composition without messing up canonical ordering while
    > making sure to compose non-adjacent characters like this? It's an edge
    > case, I know, but I want my implementation to be correct.
    > In many places, the Unicode standard provides clues for
    > implementation, but I see none for NFC (or NFKC) and how to compose
    > characters. Can anyone help me?

    This archive was generated by hypermail 2.1.5 : Thu Mar 15 2007 - 22:46:00 CST