Efficient Text Searching in Java: Finding the Right String in Any Language

By Laura Werner
2003-05-25


Finding the right string in any language

Text searching and sorting is one of the most well researched areas in computer science. It is covered in an introductory algorithms course in nearly every engineering school, and there are entire books devoted to the subject. Why, you might ask, am I writing yet another article about searching?

The answer is that most of the well-known, efficient search algorithms don't work very well in Unicode, which includes the char type in Java. Algorithms such as Knuth-Morris-Pratt and Boyer-Moore utilize tables that tell them what to do when a particular character is seen in the text being searched. That's fine for a traditional character set such as ASCII or ISO Latin-1 where there are only 128 or 256 possible characters.

Java, however, uses Unicode as its character set. In Unicode, there are 65,535 distinct characters that cover all modern languages of the world, including ideographic languages such as Chinese. In general, this is good; it makes the task of developing global applications a great deal easier. However, algorithms like Boyer-Moore that rely on an array indexed by character codes are very wasteful of memory and take a long time to initialize in this environment.

And it gets worse. Sorting and searching non-English text presents a number of challenges that many English speakers are not even aware of. The primary source of difficulty is accents, which have very different meanings in different languages, and sometimes even within the same language:

• Many accented letters, such as "é" in "café", are treated as minor variants on the letter that is accented, in this case "e".
• Sometimes the accented form of a letter is treated as a distinct letter for the purposes of comparison. For example, "Å" in Danish is treated as a separate letter that sorts near the end of the alphabet after "Z" and "Æ".
• In some cases, an accented letter is treated as if it were two letters. In traditional German, for example, "ä" is compared as if it were "ae".

Other difficulties arise when multiple characters compare as if they were one, such as in traditional Spanish where "ch" is treated as a single letter that sorts just after "c" and before "d", or when single characters such as the "Æ" ligature or the German "ß"are treated as if they were spelled out as "AE" or "ss".

All of the above might make the problem of sorting and searching international text seem hopeless. While not impossible, it is a difficult problem. Do not despair, however. Starting in JDK 1.1, the class java.text.Collator is here to help.

Tutorial Pages:
» Finding the right string in any language
» Text searching and sorting is one of the most well researched areas in computer science. It is covered in an introductory algorithms course in nearly
» Under the Hood
» Text Searching in JDK 1.1
» Ignore That Character!
» It's Better in 1.2
» Optimized Searching
» Boyer-Moore and Unicode
» But wait! At the very beginning of this article, I said that this kind of algorithm doesn't work well with Unicode because it has 65,535 possible char
» I hope this article has given you a good idea of how you can use collators to add language-sensitive sorting and searching to your own Java applicatio


First published by IBM DeveloperWorks

Related Tutorials: » All about JAXP, Part 1 » Make Database Queries Without the Database » Load List Values for Improved Efficiency » 2 Ways To Implement Session Tracking » A Simple Way to Read an XML File in Java » Develop Aspect-Oriented Java Applications with Eclipse and AJDT