go

[Dictionary.git] / jars / icu4j-4_4_2-src / main / classes / core / src / com / ibm / icu / text / DictionaryBasedBreakIterator.java

/*\r
 *******************************************************************************\r
 * Copyright (C) 1996-2010, International Business Machines Corporation and    *\r
 * others. All Rights Reserved.                                                *\r
 *******************************************************************************\r
 */\r
\r
package com.ibm.icu.text;\r
\r
import java.io.IOException;\r
import java.io.InputStream;\r
import java.text.CharacterIterator;\r
import java.util.Stack;\r
import java.util.Vector;\r
\r
import com.ibm.icu.impl.Assert;\r
\r
\r
/**\r
 * A subclass of RuleBasedBreakIterator that adds the ability to use a dictionary\r
 * to further subdivide ranges of text beyond what is possible using just the\r
 * state-table-based algorithm.  This is necessary, for example, to handle\r
 * word and line breaking in Thai, which doesn't use spaces between words.  The\r
 * state-table-based algorithm used by RuleBasedBreakIterator_Old is used to divide\r
 * up text as far as possible, and then contiguous ranges of letters are\r
 * repeatedly compared against a list of known words (i.e., the dictionary)\r
 * to divide them up into words.\r
 *\r
 * DictionaryBasedBreakIterator uses the same rule language as RuleBasedBreakIterator_Old,\r
 * but adds one more special substitution name: _dictionary_.  This substitution\r
 * name is used to identify characters in words in the dictionary.  The idea is that\r
 * if the iterator passes over a chunk of text that includes two or more characters\r
 * in a row that are included in _dictionary_, it goes back through that range and\r
 * derives additional break positions (if possible) using the dictionary.\r
 *\r
 * DictionaryBasedBreakIterator is also constructed with the filename of a dictionary\r
 * file.  It uses Class.getResource() to locate the dictionary file.  The\r
 * dictionary file is in a serialized binary format.  We have a very primitive (and\r
 * slow) BuildDictionaryFile utility for creating dictionary files, but aren't\r
 * currently making it public.  Contact us for help.\r
 *\r
 * @stable ICU 2.0\r
 */\r
public class DictionaryBasedBreakIterator extends RuleBasedBreakIterator {\r
    \r
    /**\r
     * Keeps track of if we are using the compact trie dictionary.\r
     */\r
    private boolean usingCTDictionary = false;\r
    /**\r
     * a list of known words that is used to divide up contiguous ranges of letters,\r
     * stored in a compressed, indexed, format that offers fast access\r
     */\r
    private BreakDictionary dictionary;\r
\r
    /*\r
     * a list of flags indicating which character categories are contained in\r
     * the dictionary file (this is used to determine which ranges of characters\r
     * to apply the dictionary to)\r
     */\r
    //private boolean[] categoryFlags;\r
\r
\r
    /**\r
     * when a range of characters is divided up using the dictionary, the break\r
     * positions that are discovered are stored here, preventing us from having\r
     * to use either the dictionary or the state table again until the iterator\r
     * leaves this range of text\r
     */\r
    int[] cachedBreakPositions;\r
\r
    /**\r
     * if cachedBreakPositions is not null, this indicates which item in the\r
     * cache the current iteration position refers to\r
     */\r
    int positionInCache;\r
\r
    /**\r
     * Special variable name for characters in words in dictionary\r
     */\r
    \r
    /**\r
     * Construct a DictionarBasedBreakIterator from precompiled rules. Use by ThaiBreakEngine\r
     * uses the BreakCTDictionary.\r
     * @param compiledRules an input stream containing the binary (flattened) compiled rules.\r
     * @internal\r
     * @deprecated This API is ICU internal only.\r
     */\r
    protected DictionaryBasedBreakIterator(InputStream compiledRules) throws IOException {\r
        fRData = RBBIDataWrapper.get(compiledRules);   // Init the RBBI part of this iterator.\r
        dictionary = null;\r
        usingCTDictionary = true;\r
    }\r
    /**\r
     * Constructs a DictionaryBasedBreakIterator.\r
     * @param rules Same as the rules parameter on RuleBasedBreakIterator,\r
     * except for the special meaning of "_dictionary_".  This parameter is just\r
     * passed through to RuleBasedBreakIterator constructor.\r
     * @param dictionaryStream the stream containing the dictionary data\r
     * @stable ICU 2.0\r
     */\r
    public DictionaryBasedBreakIterator(String rules,\r
                                        InputStream dictionaryStream) throws IOException {\r
        super(rules);\r
        dictionary = new BreakDictionary(dictionaryStream);\r
    }\r
\r
    \r
    /**\r
     * Construct a DictionarBasedBreakIterator from precompiled rules.\r
     * @param compiledRules an input stream containing the binary (flattened) compiled rules.\r
     * @param dictionaryStream an input stream containing the dictionary data\r
     * @internal\r
     * @deprecated This API is ICU internal only.\r
     */\r
    public DictionaryBasedBreakIterator(InputStream compiledRules,\r
                                         InputStream dictionaryStream) throws IOException {\r
       fRData = RBBIDataWrapper.get(compiledRules);   // Init the RBBI part of this iterator.\r
       dictionary = new BreakDictionary(dictionaryStream);\r
    }\r
                    \r
\r
    /** @stable ICU 2.0 */\r
    public void setText(CharacterIterator newText) {\r
        super.setText(newText);\r
        cachedBreakPositions = null;\r
        fDictionaryCharCount = 0;\r
        positionInCache = 0;\r
    }\r
\r
    /**\r
     * Sets the current iteration position to the beginning of the text.\r
     * (i.e., the CharacterIterator's starting offset).\r
     * @return The offset of the beginning of the text.\r
     * @stable ICU 2.0\r
     */\r
    public int first() {\r
        cachedBreakPositions = null;\r
        fDictionaryCharCount = 0;\r
        positionInCache = 0;\r
        return super.first();\r
    }\r
\r
    /**\r
     * Sets the current iteration position to the end of the text.\r
     * (i.e., the CharacterIterator's ending offset).\r
     * @return The text's past-the-end offset.\r
     * @stable ICU 2.0\r
     */\r
    public int last() {\r
        cachedBreakPositions = null;\r
        fDictionaryCharCount = 0;\r
        positionInCache = 0;\r
        return super.last();\r
    }\r
\r
    /**\r
     * Advances the iterator one step backwards.\r
     * @return The position of the last boundary position before the\r
     * current iteration position\r
     * @stable ICU 2.0\r
     */\r
    public int previous() {\r
        CharacterIterator text = getText();\r
\r
        // if we have cached break positions and we're still in the range\r
        // covered by them, just move one step backward in the cache\r
        if (cachedBreakPositions != null && positionInCache > 0) {\r
            --positionInCache;\r
            text.setIndex(cachedBreakPositions[positionInCache]);\r
            return cachedBreakPositions[positionInCache];\r
        }\r
\r
        // otherwise, dump the cache and use the inherited previous() method to move\r
        // backward.  This may fill up the cache with new break positions, in which\r
        // case we have to mark our position in the cache. If it doesn't, use next()\r
        // to move forward until we hit or pass the current position. This *will* fill\r
        // the cache.\r
        else {\r
            cachedBreakPositions = null;\r
            int offset = current();\r
            int result = super.previous();\r
            \r
            if (cachedBreakPositions != null) {\r
                positionInCache = cachedBreakPositions.length - 2;\r
                return result;\r
            }\r
            \r
            while (result < offset) {\r
                int nextResult = next();\r
                \r
                if (nextResult >= offset) {\r
                    break;\r
                }\r
                \r
                result = nextResult;\r
            }\r
            \r
            if (cachedBreakPositions != null) {\r
                positionInCache = cachedBreakPositions.length - 2;\r
            }\r
            \r
            if (result != BreakIterator.DONE) {\r
                text.setIndex(result);\r
            }\r
            \r
            return result;\r
        }\r
    }\r
\r
    /**\r
     * Sets the current iteration position to the last boundary position\r
     * before the specified position.\r
     * @param offset The position to begin searching from\r
     * @return The position of the last boundary before "offset"\r
     * @stable ICU 2.0\r
     */\r
    public int preceding(int offset) {\r
        CharacterIterator text = getText();\r
        checkOffset(offset, text);\r
\r
        // if we have no cached break positions, or "offset" is outside the\r
        // range covered by the cache, we can just call the inherited routine\r
        // (which will eventually call other routines in this class that may\r
        // refresh the cache)\r
        if (cachedBreakPositions == null || offset <= cachedBreakPositions[0] ||\r
                offset > cachedBreakPositions[cachedBreakPositions.length - 1]) {\r
            cachedBreakPositions = null;\r
            return super.preceding(offset);\r
        }\r
\r
        // on the other hand, if "offset" is within the range covered by the cache,\r
        // then all we have to do is search the cache for the last break position\r
        // before "offset"\r
        else {\r
            positionInCache = 0;\r
            while (positionInCache < cachedBreakPositions.length\r
                   && offset > cachedBreakPositions[positionInCache])\r
                ++positionInCache;\r
            --positionInCache;\r
            text.setIndex(cachedBreakPositions[positionInCache]);\r
            return text.getIndex();\r
        }\r
    }\r
\r
    /**\r
     * Sets the current iteration position to the first boundary position after\r
     * the specified position.\r
     * @param offset The position to begin searching forward from\r
     * @return The position of the first boundary after "offset"\r
     * @stable ICU 2.0\r
     */\r
    public int following(int offset) {\r
        CharacterIterator text = getText();\r
        checkOffset(offset, text);\r
\r
        // if we have no cached break positions, or if "offset" is outside the\r
        // range covered by the cache, then dump the cache and call our\r
        // inherited following() method.  This will call other methods in this\r
        // class that may refresh the cache.\r
        if (cachedBreakPositions == null || offset < cachedBreakPositions[0] ||\r
                offset >= cachedBreakPositions[cachedBreakPositions.length - 1]) {\r
            cachedBreakPositions = null;\r
            return super.following(offset);\r
        }\r
\r
        // on the other hand, if "offset" is within the range covered by the\r
        // cache, then just search the cache for the first break position\r
        // after "offset"\r
        else {\r
            positionInCache = 0;\r
            while (positionInCache < cachedBreakPositions.length\r
                   && offset >= cachedBreakPositions[positionInCache])\r
                ++positionInCache;\r
            text.setIndex(cachedBreakPositions[positionInCache]);\r
            return text.getIndex();\r
        }\r
    }\r
    \r
    \r
    /**\r
     * Return the status tag from the break rule that determined the most recently\r
     * returned break position. \r
     * \r
     * TODO:  not supported with dictionary based break iterators.\r
     *\r
     * @return the status from the break rule that determined the most recently\r
     * returned break position.\r
     * @draft ICU 3.0\r
     * @provisional This API might change or be removed in a future release.\r
     */\r
     public int getRuleStatus() {\r
        return 0;\r
     }\r
\r
\r
    /**\r
     * Get the status (tag) values from the break rule(s) that determined the most \r
     * recently returned break position.  The values appear in the rule source\r
     * within brackets, {123}, for example.  The default status value for rules\r
     * that do not explicitly provide one is zero.\r
     * <p>\r
     * TODO: not supported for dictionary based break iterator. \r
     *\r
     * @param fillInArray an array to be filled in with the status values.  \r
     * @return          The number of rule status values from rules that determined \r
     *                  the most recent boundary returned by the break iterator.\r
     *                  In the event that the array is too small, the return value\r
     *                  is the total number of status values that were available,\r
     *                  not the reduced number that were actually returned.\r
     * @draft ICU 3.0\r
     * @provisional This API might change or be removed in a future release.\r
     */\r
    public int getRuleStatusVec(int[] fillInArray) {\r
        if (fillInArray != null && fillInArray.length>=1) {  \r
            fillInArray[0] = 0;\r
        }\r
        return 1;\r
    }\r
    /**\r
     * This is the implementation function for next().\r
     * @internal\r
     * @deprecated This API is ICU internal only.\r
     */\r
    protected int handleNext() {\r
        CharacterIterator text = getText();\r
\r
        // if there are no cached break positions, or if we've just moved\r
        // off the end of the range covered by the cache, we have to dump\r
        // and possibly regenerate the cache\r
        if (cachedBreakPositions == null || positionInCache == cachedBreakPositions.length - 1) {\r
\r
            // start by using the inherited handleNext() to find a tentative return\r
            // value.   dictionaryCharCount tells us how many dictionary characters\r
            // we passed over on our way to the tentative return value\r
            int startPos = text.getIndex();\r
            fDictionaryCharCount = 0;\r
            int result = super.handleNext();\r
\r
            // if we passed over more than one dictionary character, then we use\r
            // divideUpDictionaryRange() to regenerate the cached break positions\r
            // for the new range.\r
            if (!usingCTDictionary && fDictionaryCharCount > 1 && result - startPos > 1) {\r
                divideUpDictionaryRange(startPos, result);\r
            }\r
\r
            // otherwise, the value we got back from the inherited fuction\r
            // is our return value, and we can dump the cache\r
            else {\r
                cachedBreakPositions = null;\r
                return result;\r
            }\r
        }\r
\r
        // if the cache of break positions has been regenerated (or existed all\r
        // along), then just advance to the next break position in the cache\r
        // and return it\r
        if (cachedBreakPositions != null) {\r
            ++positionInCache;\r
            text.setIndex(cachedBreakPositions[positionInCache]);\r
            return cachedBreakPositions[positionInCache];\r
        }\r
        ///CLOVER:OFF\r
        Assert.assrt(false);\r
        return -9999;   // SHOULD NEVER GET HERE!\r
        ///CLOVER:ON\r
    }\r
\r
    /**\r
     * This is the function that actually implements the dictionary-based\r
     * algorithm.  Given the endpoints of a range of text, it uses the\r
     * dictionary to determine the positions of any boundaries in this\r
     * range.  It stores all the boundary positions it discovers in\r
     * cachedBreakPositions so that we only have to do this work once\r
     * for each time we enter the range.\r
     */\r
    @SuppressWarnings("unchecked")\r
    private void divideUpDictionaryRange(int startPos, int endPos) {\r
        CharacterIterator text = getText();\r
\r
        // the range we're dividing may begin or end with non-dictionary characters\r
        // (i.e., for line breaking, we may have leading or trailing punctuation\r
        // that needs to be kept with the word).  Seek from the beginning of the\r
        // range to the first dictionary character\r
        text.setIndex(startPos);\r
        int c = CICurrent32(text);\r
        while (isDictionaryChar(c) == false) {  \r
            c = CINext32(text);\r
        }\r
        \r
        //System.out.println("\nDividing up range from " + (text.getIndex() + 1) + " to " + endPos);\r
\r
        // initialize.  We maintain two stacks: currentBreakPositions contains\r
        // the list of break positions that will be returned if we successfully\r
        // finish traversing the whole range now.  possibleBreakPositions lists\r
        // all other possible word ends we've passed along the way.  (Whenever\r
        // we reach an error [a sequence of characters that can't begin any word\r
        // in the dictionary], we back up, possibly delete some breaks from\r
        // currentBreakPositions, move a break from possibleBreakPositions\r
        // to currentBreakPositions, and start over from there.  This process\r
        // continues in this way until we either successfully make it all the way\r
        // across the range, or exhaust all of our combinations of break\r
        // positions.)\r
        Stack<Integer> currentBreakPositions = new Stack<Integer>();\r
        Stack<Integer> possibleBreakPositions = new Stack<Integer>();\r
        Vector<Integer> wrongBreakPositions = new Vector<Integer>();\r
\r
        // the dictionary is implemented as a trie, which is treated as a state\r
        // machine.  -1 represents the end of a legal word.  Every word in the\r
        // dictionary is represented by a path from the root node to -1.  A path\r
        // that ends in state 0 is an illegal combination of characters.\r
        int state = 0;\r
\r
        // these two variables are used for error handling.  We keep track of the\r
        // farthest we've gotten through the range being divided, and the combination\r
        // of breaks that got us that far.  If we use up all possible break\r
        // combinations, the text contains an error or a word that's not in the\r
        // dictionary.  In this case, we "bless" the break positions that got us the\r
        // farthest as real break positions, and then start over from scratch with\r
        // the character where the error occurred.\r
        int farthestEndPoint = text.getIndex();\r
        Stack<Integer> bestBreakPositions = null;\r
\r
        // initialize (we always exit the loop with a break statement)\r
        c = CICurrent32(text);\r
        while (true) {\r
//System.out.print("c = " + Integer.toString(c, 16) + ", pos = " + text.getIndex());\r
\r
            // if we can transition to state "-1" from our current state, we're\r
            // on the last character of a legal word.  Push that position onto\r
            // the possible-break-positions stack\r
            if (dictionary.at(state, 0) == -1) {\r
                possibleBreakPositions.push(Integer.valueOf(text.getIndex()));\r
            }\r
\r
            // look up the new state to transition to in the dictionary\r
            //    There will be no supplementaries here because the Thai dictionary\r
            //     does not include any.  This code is going away soon, not worth\r
            //     fixing.\r
            state = (dictionary.at(state, (char)c)) & 0xFFFF;  // TODO: fix supplementaries\r
//System.out.print(", state = " + state);\r
\r
            // if the character we're sitting on causes us to transition to\r
            // the "end of word" state, then it was a non-dictionary character\r
            // and we've successfully traversed the whole range.  Drop out\r
            // of the loop.\r
            if (state == /*-1*/ 0xFFFF) {\r
                currentBreakPositions.push(Integer.valueOf(text.getIndex()));\r
                break;\r
            }\r
\r
            // if the character we're sitting on causes us to transition to\r
            // the error state, or if we've gone off the end of the range\r
            // without transitioning to the "end of word" state, we've hit\r
            // an error...\r
            else if (state == 0 || text.getIndex() >= endPos) {\r
\r
                // if this is the farthest we've gotten, take note of it in\r
                // case there's an error in the text\r
                if (text.getIndex() > farthestEndPoint) {\r
                    farthestEndPoint = text.getIndex();\r
                    bestBreakPositions = (Stack<Integer>)(currentBreakPositions.clone());\r
                }\r
\r
                // wrongBreakPositions is a list of all break positions we've tried starting\r
                // that didn't allow us to traverse all the way through the text.  Every time\r
                // we pop a break position off of currentBreakPositions, we put it into\r
                // wrongBreakPositions to avoid trying it again later.  If we make it to this\r
                // spot, we're either going to back up to a break in possibleBreakPositions\r
                // and try starting over from there, or we've exhausted all possible break\r
                // positions and are going to do the fallback procedure.  This loop prevents\r
                // us from messing with anything in possibleBreakPositions that didn't work as\r
                // a starting point the last time we tried it (this is to prevent a bunch of\r
                // repetitive checks from slowing down some extreme cases)\r
                // variable not used Integer newStartingSpot = null;\r
                while (!possibleBreakPositions.isEmpty() && wrongBreakPositions.contains(\r
                            possibleBreakPositions.peek())) {\r
                    possibleBreakPositions.pop();\r
                }\r
\r
                // if we've used up all possible break-position combinations, there's\r
                // an error or an unknown word in the text.  In this case, we start\r
                // over, treating the farthest character we've reached as the beginning\r
                // of the range, and "blessing" the break positions that got us that\r
                // far as real break positions\r
                if (possibleBreakPositions.isEmpty()) {\r
                    if (bestBreakPositions != null) {\r
                        currentBreakPositions = bestBreakPositions;\r
                        if (farthestEndPoint < endPos) {\r
                            text.setIndex(farthestEndPoint + 1);\r
                        }\r
                        else {\r
                            break;\r
                        }\r
                    }\r
                    else {\r
                        if ((currentBreakPositions.size() == 0\r
                                || currentBreakPositions.peek().intValue() != text.getIndex())\r
                                && text.getIndex() != startPos) {\r
                            currentBreakPositions.push(Integer.valueOf(text.getIndex()));\r
                        }\r
                        CINext32(text);\r
                        currentBreakPositions.push(Integer.valueOf(text.getIndex()));\r
                    }\r
                }\r
\r
                // if we still have more break positions we can try, then promote the\r
                // last break in possibleBreakPositions into currentBreakPositions,\r
                // and get rid of all entries in currentBreakPositions that come after\r
                // it.  Then back up to that position and start over from there (i.e.,\r
                // treat that position as the beginning of a new word)\r
                else {\r
                    Integer temp = possibleBreakPositions.pop();\r
                    Integer temp2 = null;\r
                    while (!currentBreakPositions.isEmpty() && temp.intValue() <\r
                           currentBreakPositions.peek().intValue()) {\r
                        temp2 = currentBreakPositions.pop();\r
                        wrongBreakPositions.addElement(temp2);\r
                    }\r
                    currentBreakPositions.push(temp);\r
                    text.setIndex(currentBreakPositions.peek().intValue());\r
                }\r
\r
                // re-sync "c" for the next go-round, and drop out of the loop if\r
                // we've made it off the end of the range\r
                c = CICurrent32(text);\r
                state = 0;\r
                if (text.getIndex() >= endPos) {\r
                    break;\r
                }\r
            }\r
\r
            // if we didn't hit any exceptional conditions on this last iteration,\r
            // just advance to the next character and loop\r
            else {\r
                c = CINext32(text);\r
            }\r
//System.out.print(", possibleBreakPositions = { "); for (int i = 0; i < possibleBreakPositions.size(); i++) System.out.print(possibleBreakPositions.elementAt(i) + " "); System.out.print("}");\r
//System.out.print(", currentBreakPositions = { "); for (int i = 0; i < currentBreakPositions.size(); i++) System.out.print(currentBreakPositions.elementAt(i) + " "); System.out.println("}");\r
        }\r
\r
        // dump the last break position in the list, and replace it with the actual\r
        // end of the range (which may be the same character, or may be further on\r
        // because the range actually ended with non-dictionary characters we want to\r
        // keep with the word)\r
        if (!currentBreakPositions.isEmpty()) {\r
            currentBreakPositions.pop();\r
        }\r
        currentBreakPositions.push(Integer.valueOf(endPos));\r
\r
        // create a regular array to hold the break positions and copy\r
        // the break positions from the stack to the array (in addition,\r
        // our starting position goes into this array as a break position).\r
        // This array becomes the cache of break positions used by next()\r
        // and previous(), so this is where we actually refresh the cache.\r
        cachedBreakPositions = new int[currentBreakPositions.size() + 1];\r
        cachedBreakPositions[0] = startPos;\r
\r
        for (int i = 0; i < currentBreakPositions.size(); i++) {\r
            cachedBreakPositions[i + 1] = currentBreakPositions.elementAt(i).intValue();\r
        }\r
        positionInCache = 0;\r
    }\r
}\r