FileDocCategorySizeDatePackage
DictionaryBasedBreakIterator.javaAPI DocJava SE 5 API22109Fri Aug 26 14:57:20 BST 2005java.text

DictionaryBasedBreakIterator

public class DictionaryBasedBreakIterator extends RuleBasedBreakIterator
A subclass of RuleBasedBreakIterator that adds the ability to use a dictionary to further subdivide ranges of text beyond what is possible using just the state-table-based algorithm. This is necessary, for example, to handle word and line breaking in Thai, which doesn't use spaces between words. The state-table-based algorithm used by RuleBasedBreakIterator is used to divide up text as far as possible, and then contiguous ranges of letters are repeatedly compared against a list of known words (i.e., the dictionary) to divide them up into words. DictionaryBasedBreakIterator uses the same rule language as RuleBasedBreakIterator, but adds one more special substitution name: <dictionary>. This substitution name is used to identify characters in words in the dictionary. The idea is that if the iterator passes over a chunk of text that includes two or more characters in a row that are included in <dictionary>, it goes back through that range and derives additional break positions (if possible) using the dictionary. DictionaryBasedBreakIterator is also constructed with the filename of a dictionary file. It follows a prescribed search path to locate the dictionary (right now, it looks for it in /com/ibm/text/resources in each directory in the classpath, and won't find it in JAR files, but this location is likely to change). The dictionary file is in a serialized binary format. We have a very primitive (and slow) BuildDictionaryFile utility for creating dictionary files, but aren't currently making it public. Contact us for help.

Fields Summary
private BreakDictionary
dictionary
a list of known words that is used to divide up contiguous ranges of letters, stored in a compressed, indexed, format that offers fast access
private boolean[]
categoryFlags
a list of flags indicating which character categories are contained in the dictionary file (this is used to determine which ranges of characters to apply the dictionary to)
private int
dictionaryCharCount
a temporary hiding place for the number of dictionary characters in the last range passed over by next()
private int[]
cachedBreakPositions
when a range of characters is divided up using the dictionary, the break positions that are discovered are stored here, preventing us from having to use either the dictionary or the state table again until the iterator leaves this range of text
private int
positionInCache
if cachedBreakPositions is not null, this indicates which item in the cache the current iteration position refers to
Constructors Summary
public DictionaryBasedBreakIterator(String dataFile, String dictionaryFile)
Constructs a DictionaryBasedBreakIterator.

param
description Same as the description parameter on RuleBasedBreakIterator, except for the special meaning of "". This parameter is just passed through to RuleBasedBreakIterator's constructor.
param
dictionaryFilename The filename of the dictionary file to use

        super(dataFile);
        byte[] tmp = super.getAdditionalData();
        if (tmp != null) {
            prepareCategoryFlags(tmp);
            super.setAdditionalData(null);
        }
        dictionary = new BreakDictionary(dictionaryFile);
Methods Summary
private voiddivideUpDictionaryRange(int startPos, int endPos)
This is the function that actually implements the dictionary-based algorithm. Given the endpoints of a range of text, it uses the dictionary to determine the positions of any boundaries in this range. It stores all the boundary positions it discovers in cachedBreakPositions so that we only have to do this work once for each time we enter the range.

        CharacterIterator text = getText();

        // the range we're dividing may begin or end with non-dictionary characters
        // (i.e., for line breaking, we may have leading or trailing punctuation
        // that needs to be kept with the word).  Seek from the beginning of the
        // range to the first dictionary character
        text.setIndex(startPos);
        int c = getCurrent();
        int category = lookupCategory(c);
        while (category == IGNORE || !categoryFlags[category]) {
            c = getNext();
            category = lookupCategory(c);
        }

        // initialize.  We maintain two stacks: currentBreakPositions contains
        // the list of break positions that will be returned if we successfully
        // finish traversing the whole range now.  possibleBreakPositions lists
        // all other possible word ends we've passed along the way.  (Whenever
        // we reach an error [a sequence of characters that can't begin any word
        // in the dictionary], we back up, possibly delete some breaks from
        // currentBreakPositions, move a break from possibleBreakPositions
        // to currentBreakPositions, and start over from there.  This process
        // continues in this way until we either successfully make it all the way
        // across the range, or exhaust all of our combinations of break
        // positions.)
        Stack currentBreakPositions = new Stack();
        Stack possibleBreakPositions = new Stack();
        Vector wrongBreakPositions = new Vector();

        // the dictionary is implemented as a trie, which is treated as a state
        // machine.  -1 represents the end of a legal word.  Every word in the
        // dictionary is represented by a path from the root node to -1.  A path
        // that ends in state 0 is an illegal combination of characters.
        int state = 0;

        // these two variables are used for error handling.  We keep track of the
        // farthest we've gotten through the range being divided, and the combination
        // of breaks that got us that far.  If we use up all possible break
        // combinations, the text contains an error or a word that's not in the
        // dictionary.  In this case, we "bless" the break positions that got us the
        // farthest as real break positions, and then start over from scratch with
        // the character where the error occurred.
        int farthestEndPoint = text.getIndex();
        Stack bestBreakPositions = null;

        // initialize (we always exit the loop with a break statement)
        c = getCurrent();
        while (true) {

            // if we can transition to state "-1" from our current state, we're
            // on the last character of a legal word.  Push that position onto
            // the possible-break-positions stack
            if (dictionary.getNextState(state, 0) == -1) {
                possibleBreakPositions.push(new Integer(text.getIndex()));
            }

            // look up the new state to transition to in the dictionary
            state = dictionary.getNextStateFromCharacter(state, c);

            // if the character we're sitting on causes us to transition to
            // the "end of word" state, then it was a non-dictionary character
            // and we've successfully traversed the whole range.  Drop out
            // of the loop.
            if (state == -1) {
                currentBreakPositions.push(new Integer(text.getIndex()));
                break;
            }

            // if the character we're sitting on causes us to transition to
            // the error state, or if we've gone off the end of the range
            // without transitioning to the "end of word" state, we've hit
            // an error...
            else if (state == 0 || text.getIndex() >= endPos) {

                // if this is the farthest we've gotten, take note of it in
                // case there's an error in the text
                if (text.getIndex() > farthestEndPoint) {
                    farthestEndPoint = text.getIndex();
                    bestBreakPositions = (Stack)(currentBreakPositions.clone());
                }

                // wrongBreakPositions is a list of all break positions 
		// we've tried starting that didn't allow us to traverse
		// all the way through the text.  Every time we pop a
		//break position off of currentBreakPositions, we put it
		// into wrongBreakPositions to avoid trying it again later.
		// If we make it to this spot, we're either going to back
		// up to a break in possibleBreakPositions and try starting
		// over from there, or we've exhausted all possible break
                // positions and are going to do the fallback procedure.
		// This loop prevents us from messing with anything in
		// possibleBreakPositions that didn't work as a starting
		// point the last time we tried it (this is to prevent a bunch of
                // repetitive checks from slowing down some extreme cases)
                Integer newStartingSpot = null;
                while (!possibleBreakPositions.isEmpty() && wrongBreakPositions.contains(
                            possibleBreakPositions.peek())) {
                    possibleBreakPositions.pop();
                }
                
                // if we've used up all possible break-position combinations, there's
                // an error or an unknown word in the text.  In this case, we start
                // over, treating the farthest character we've reached as the beginning
                // of the range, and "blessing" the break positions that got us that
                // far as real break positions
                if (possibleBreakPositions.isEmpty()) {
                    if (bestBreakPositions != null) {
                        currentBreakPositions = bestBreakPositions;
                        if (farthestEndPoint < endPos) {
                            text.setIndex(farthestEndPoint + 1);
                        }
                        else {
                            break;
                        }
                    }
                    else {
                        if ((currentBreakPositions.size() == 0 ||
			     ((Integer)(currentBreakPositions.peek())).intValue() != text.getIndex())
			    && text.getIndex() != startPos) {
                            currentBreakPositions.push(new Integer(text.getIndex()));
                        }
                        getNext();
                        currentBreakPositions.push(new Integer(text.getIndex()));
                    }
                }

                // if we still have more break positions we can try, then promote the
                // last break in possibleBreakPositions into currentBreakPositions,
                // and get rid of all entries in currentBreakPositions that come after
                // it.  Then back up to that position and start over from there (i.e.,
                // treat that position as the beginning of a new word)
                else {
                    Integer temp = (Integer)possibleBreakPositions.pop();
                    Object temp2 = null;
                    while (!currentBreakPositions.isEmpty() && temp.intValue() <
                           ((Integer)currentBreakPositions.peek()).intValue()) {
                        temp2 = currentBreakPositions.pop();
                        wrongBreakPositions.addElement(temp2);
                    }
                    currentBreakPositions.push(temp);
                    text.setIndex(((Integer)currentBreakPositions.peek()).intValue());
                }

                // re-sync "c" for the next go-round, and drop out of the loop if
                // we've made it off the end of the range
                c = getCurrent();
                if (text.getIndex() >= endPos) {
                    break;
                }
            }

            // if we didn't hit any exceptional conditions on this last iteration,
            // just advance to the next character and loop
            else {
                c = getNext();
            }
        }

        // dump the last break position in the list, and replace it with the actual
        // end of the range (which may be the same character, or may be further on
        // because the range actually ended with non-dictionary characters we want to
        // keep with the word)
        if (!currentBreakPositions.isEmpty()) {
            currentBreakPositions.pop();
        }
        currentBreakPositions.push(new Integer(endPos));

        // create a regular array to hold the break positions and copy
        // the break positions from the stack to the array (in addition,
        // our starting position goes into this array as a break position).
        // This array becomes the cache of break positions used by next()
        // and previous(), so this is where we actually refresh the cache.
        cachedBreakPositions = new int[currentBreakPositions.size() + 1];
        cachedBreakPositions[0] = startPos;

        for (int i = 0; i < currentBreakPositions.size(); i++) {
            cachedBreakPositions[i + 1] = ((Integer)currentBreakPositions.elementAt(i)).intValue();
        }
        positionInCache = 0;
public intfirst()
Sets the current iteration position to the beginning of the text. (i.e., the CharacterIterator's starting offset).

return
The offset of the beginning of the text.

        cachedBreakPositions = null;
        dictionaryCharCount = 0;
        positionInCache = 0;
        return super.first();
public intfollowing(int offset)
Sets the current iteration position to the first boundary position after the specified position.

param
offset The position to begin searching forward from
return
The position of the first boundary after "offset"

        CharacterIterator text = getText();
        checkOffset(offset, text);

        // if we have no cached break positions, or if "offset" is outside the
        // range covered by the cache, then dump the cache and call our
        // inherited following() method.  This will call other methods in this
        // class that may refresh the cache.
        if (cachedBreakPositions == null || offset < cachedBreakPositions[0] ||
                offset >= cachedBreakPositions[cachedBreakPositions.length - 1]) {
            cachedBreakPositions = null;
            return super.following(offset);
        }

        // on the other hand, if "offset" is within the range covered by the
        // cache, then just search the cache for the first break position
        // after "offset"
        else {
            positionInCache = 0;
            while (positionInCache < cachedBreakPositions.length
                   && offset >= cachedBreakPositions[positionInCache]) {
                ++positionInCache;
            }
            text.setIndex(cachedBreakPositions[positionInCache]);
            return text.getIndex();
        }
protected inthandleNext()
This is the implementation function for next().

        CharacterIterator text = getText();

        // if there are no cached break positions, or if we've just moved
        // off the end of the range covered by the cache, we have to dump
        // and possibly regenerate the cache
        if (cachedBreakPositions == null || 
	    positionInCache == cachedBreakPositions.length - 1) {

            // start by using the inherited handleNext() to find a tentative return
            // value.   dictionaryCharCount tells us how many dictionary characters
            // we passed over on our way to the tentative return value
            int startPos = text.getIndex();
            dictionaryCharCount = 0;
            int result = super.handleNext();

            // if we passed over more than one dictionary character, then we use
            // divideUpDictionaryRange() to regenerate the cached break positions
            // for the new range
            if (dictionaryCharCount > 1 && result - startPos > 1) {
                divideUpDictionaryRange(startPos, result);
            }

            // otherwise, the value we got back from the inherited fuction
            // is our return value, and we can dump the cache
            else {
                cachedBreakPositions = null;
                return result;
            }
        }

        // if the cache of break positions has been regenerated (or existed all
        // along), then just advance to the next break position in the cache
        // and return it
        if (cachedBreakPositions != null) {
            ++positionInCache;
            text.setIndex(cachedBreakPositions[positionInCache]);
            return cachedBreakPositions[positionInCache];
        }
        return -9999;   // SHOULD NEVER GET HERE!
public intlast()
Sets the current iteration position to the end of the text. (i.e., the CharacterIterator's ending offset).

return
The text's past-the-end offset.

        cachedBreakPositions = null;
        dictionaryCharCount = 0;
        positionInCache = 0;
        return super.last();
protected intlookupCategory(int c)
Looks up a character category for a character.

        // this override of lookupCategory() exists only to keep track of whether we've
        // passed over any dictionary characters.  It calls the inherited lookupCategory()
        // to do the real work, and then checks whether its return value is one of the
        // categories represented in the dictionary.  If it is, bump the dictionary-
        // character count.
        int result = super.lookupCategory(c);
        if (result != RuleBasedBreakIterator.IGNORE && categoryFlags[result]) {
            ++dictionaryCharCount;
        }
        return result;
public intpreceding(int offset)
Sets the current iteration position to the last boundary position before the specified position.

param
offset The position to begin searching from
return
The position of the last boundary before "offset"

        CharacterIterator text = getText();
        checkOffset(offset, text);

        // if we have no cached break positions, or "offset" is outside the
        // range covered by the cache, we can just call the inherited routine
        // (which will eventually call other routines in this class that may
        // refresh the cache)
        if (cachedBreakPositions == null || offset <= cachedBreakPositions[0] ||
                offset > cachedBreakPositions[cachedBreakPositions.length - 1]) {
            cachedBreakPositions = null;
            return super.preceding(offset);
        }

        // on the other hand, if "offset" is within the range covered by the cache,
        // then all we have to do is search the cache for the last break position
        // before "offset"
        else {
            positionInCache = 0;
            while (positionInCache < cachedBreakPositions.length
                   && offset > cachedBreakPositions[positionInCache]) {
                ++positionInCache;
            }
            --positionInCache;
            text.setIndex(cachedBreakPositions[positionInCache]);
            return text.getIndex();
        }
private voidprepareCategoryFlags(byte[] data)

	categoryFlags = new boolean[data.length];
        for (int i = 0; i < data.length; i++) {
            categoryFlags[i] = (data[i] == (byte)1) ? true : false;
        }
public intprevious()
Advances the iterator one step backwards.

return
The position of the last boundary position before the current iteration position

        CharacterIterator text = getText();

        // if we have cached break positions and we're still in the range
        // covered by them, just move one step backward in the cache
        if (cachedBreakPositions != null && positionInCache > 0) {
            --positionInCache;
            text.setIndex(cachedBreakPositions[positionInCache]);
            return cachedBreakPositions[positionInCache];
        }

        // otherwise, dump the cache and use the inherited previous() method to move
        // backward.  This may fill up the cache with new break positions, in which
        // case we have to mark our position in the cache
        else {
            cachedBreakPositions = null;
            int result = super.previous();
            if (cachedBreakPositions != null) {
                positionInCache = cachedBreakPositions.length - 2;
            } 
            return result;
        }
public voidsetText(java.text.CharacterIterator newText)

        super.setText(newText);
        cachedBreakPositions = null;
        dictionaryCharCount = 0;
        positionInCache = 0;