Normalization, sorting and searching

Collator normalisation

• Collator applies the normalization rules of compose/decompose/compatable/non-compatable of Normalizer
• Normalisation can be set by setDecomposition(int decompositionMode)
• Values are CANONICAL_DECOMPOSITION (Normalization Form D) FULL_DECOMPOSITION (Normalization Form KD) NO_DECOMPOSITION (default)

Strength

• In addition, it applies strength rules

  Strength	Description	Example
  PRIMARY	The base letters are different	A versus B
  SECONDARY	The base letters are the same, but the accents are different	A versus Á
  TERTIARY	The letters are the same but differ by case	A versus a
  IDENTICAL	The letters are identical	A versus A

String comparison

• In ASCII one string is less than another if a left-to-right scan finds a byte in the first string less than a byte in the second
• In ASCII, "Abc" is less than "abc" because 'A' < 'a'
• Other orders are possible, even in English
  • In ASCII ordering,
    'A' < 'B' < ... < 'a' < 'b'
  • A dictionary ordering might be
    'a' < 'A' < 'b' < 'B' < 'c' ...
  • In telephone books, "Saint" < "St" < "San"

String comparison in German

• German has the special character LATIN SMALL LETTER SHARP S U+00DF which is "SS" in uppercase
• The lower case character is treated as "ss" in sorting
• Other characters are also treated as pairs of characters for comparison

String comparison in French

• Strings are first compared as strings with no accents on any character
• Strings that compare as equal are then compared for accents from right to left

Ordering in Chinese

• Ordering may be in Pinyin - with or without accents
• Ordering may be on radicals first, then on stroke count for non-radical component
• Ordering may be on coded character set values, like the default ASCII ordering

Collator comparison

• The Collator class has a factory method that takes a Locale

  Collator.getInstance(Locale)

• The resultant Collator orders string according to the locale rules and collator strength and canonicalisation

• if (collate.compare(str1, str2) > 0) ...

Making your own rules

You can make your own rules for RuleBasedCollator

Sorting

• Sorting is based on string comparison: if one string is "less than" another, then order it earlier
• For example, the class Collections has a static method sort(List list, Comparator c) and Collator implements Comparator
• String sorting algorithms are not changed by i18n - they just rely on comparing string values
• Most sorting algorithms measure complexity based on the number of comparisons. This is valid for Unicode, since comparisons can be expensive

Text boundaries

• In English, words are separated by whitespace or punctuation characters
• Sometimes it can be hard to decide what a punctuation character is: e.g. "e.g." is an abbreviation and is a single word; 1.23 is a number that should be treated as a single word in English (but in French it would be two numbers with punctuation)
• Chinese and other languages have no concept of whitespace, and words of one or more characters just run into each other
• Possible boundaries are character, word, line and sentence (but not paragraph)

BreakIterator class

• The BreakIterator class can be used to segment text
• There are factory methods to get iterators:

  
        BreakIterator.getCharacterInstance(Locale l);
        BreakIterator.getWordInstance(Locale l);
        BreakIterator.getLneInstance(Locale l);
        BreakIterator.getSentenceInstance(Locale l);
        

• Any of the break iterators need to told the text it uses

  iterator.setText(String s)

• This doesn't act like a standard Java iterator: it has methods

  
        int iterator.first();
        int iterator.next();
        int iterator.DONE
        

  which return indexes into the current text string, and DONE when there are no more

Word break in Chinese

• Chinese words/phrases are made up of one or more characters
• The characters are run together with no spaces between them
• A possible sentence might be consisting of a one-character word and a two-character word.
• The break iterator classes supplied just give this as one word
• Finding word breaks in Chinese is still a research problem
• e.g. see http://bar.austlii.edu.au/au/other/CompLRes/2003/4.html

Regular expressions

• Regular expressions are a powerful way of doing pattern matching on strings
• Originally from the Unix editors, they are used by sed, awk, perl, ...
• You have a pattern such as "a*b" which means "zero or more 'a's followed by a 'b'"
• Then strings such as "b", "ab", "aab" etc all match
• Java has regexp support, but it does not seem to support decompositions, strength, etc