go

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

/*\r
 *******************************************************************************\r
 * Copyright (C) 1996-2010, International Business Machines Corporation and    *\r
 * others. All Rights Reserved.                                                *\r
 *******************************************************************************\r
 */\r
package com.ibm.icu.text;\r
\r
import java.io.DataInputStream;\r
import java.io.FileInputStream;\r
import java.io.FileNotFoundException;\r
import java.io.FileOutputStream;\r
import java.io.IOException;\r
import java.io.InputStream;\r
import java.io.OutputStreamWriter;\r
import java.io.PrintWriter;\r
import java.io.UnsupportedEncodingException;\r
\r
import com.ibm.icu.util.CompactByteArray;\r
\r
/**\r
 * This is the class that represents the list of known words used by\r
 * DictionaryBasedBreakIterator.  The conceptual data structure used\r
 * here is a trie: there is a node hanging off the root node for every\r
 * letter that can start a word.  Each of these nodes has a node hanging\r
 * off of it for every letter that can be the second letter of a word\r
 * if this node is the first letter, and so on.  The trie is represented\r
 * as a two-dimensional array that can be treated as a table of state\r
 * transitions.  Indexes are used to compress this array, taking\r
 * advantage of the fact that this array will always be very sparse.\r
 */\r
class BreakDictionary {\r
    //=================================================================================\r
    // testing and debugging\r
    //=================================================================================\r
    ///CLOVER:OFF\r
    //The main method looks like it was useful once but now seems worthless. It is not used by any method or class.\r
    public static void main(String args[])\r
            throws FileNotFoundException, UnsupportedEncodingException, IOException {\r
        String filename = args[0];\r
\r
        BreakDictionary dictionary = new BreakDictionary(new FileInputStream(filename));\r
\r
        PrintWriter out = null;\r
\r
        if(args.length >= 2) {\r
            out = new PrintWriter(new OutputStreamWriter(new FileOutputStream(args[1]), "UnicodeLittle"));\r
        }\r
\r
        dictionary.printWordList("", 0, out);\r
\r
        if (out != null) {\r
            out.close();\r
        }\r
    }\r
    ///CLOVER:ON\r
\r
    ///CLOVER:OFF\r
    /* public */ void printWordList(String partialWord, int state, PrintWriter out)\r
            throws IOException {\r
        if (state == 0xFFFF) {\r
            System.out.println(partialWord);\r
            if (out != null) {\r
                out.println(partialWord);\r
            }\r
        }\r
        else {\r
            for (int i = 0; i < numCols; i++) {\r
                int newState = (at(state, i)) & 0xFFFF;\r
\r
                if (newState != 0) {\r
                    char newChar = reverseColumnMap[i];\r
                    String newPartialWord = partialWord;\r
\r
                    if (newChar != 0) {\r
                        newPartialWord += newChar;\r
                    }\r
\r
                    printWordList(newPartialWord, newState, out);\r
                }\r
            }\r
        }\r
    }\r
    ///CLOVER:ON\r
\r
    /**\r
     * A map used to go from column numbers to characters.  Used only\r
     * for debugging right now.\r
     */\r
    private char[] reverseColumnMap = null;\r
\r
    //=================================================================================\r
    // data members\r
    //=================================================================================\r
\r
    /**\r
     * Maps from characters to column numbers.  The main use of this is to\r
     * avoid making room in the array for empty columns.\r
     */\r
    private CompactByteArray columnMap = null;\r
\r
    /**\r
     * The number of actual columns in the table\r
     */\r
    private int numCols;\r
\r
    /*\r
     * Columns are organized into groups of 32.  This says how many\r
     * column groups.  (We could calculate this, but we store the\r
     * value to avoid having to repeatedly calculate it.)\r
     */\r
    //private int numColGroups;\r
\r
    /**\r
     * The actual compressed state table.  Each conceptual row represents\r
     * a state, and the cells in it contain the row numbers of the states\r
     * to transition to for each possible letter.  0 is used to indicate\r
     * an illegal combination of letters (i.e., the error state).  The\r
     * table is compressed by eliminating all the unpopulated (i.e., zero)\r
     * cells.  Multiple conceptual rows can then be doubled up in a single\r
     * physical row by sliding them up and possibly shifting them to one\r
     * side or the other so the populated cells don't collide.  Indexes\r
     * are used to identify unpopulated cells and to locate populated cells.\r
     */\r
    private short[] table = null;\r
\r
    /**\r
     * This index maps logical row numbers to physical row numbers\r
     */\r
    private short[] rowIndex = null;\r
\r
    /**\r
     * A bitmap is used to tell which cells in the comceptual table are\r
     * populated.  This array contains all the unique bit combinations\r
     * in that bitmap.  If the table is more than 32 columns wide,\r
     * successive entries in this array are used for a single row.\r
     */\r
    private int[] rowIndexFlags = null;\r
\r
    /**\r
     * This index maps from a logical row number into the bitmap table above.\r
     * (This keeps us from storing duplicate bitmap combinations.)  Since there\r
     * are a lot of rows with only one populated cell, instead of wasting space\r
     * in the bitmap table, we just store a negative number in this index for\r
     * rows with one populated cell.  The absolute value of that number is\r
     * the column number of the populated cell.\r
     */\r
    private short[] rowIndexFlagsIndex = null;\r
\r
    /**\r
     * For each logical row, this index contains a constant that is added to\r
     * the logical column number to get the physical column number\r
     */\r
    private byte[] rowIndexShifts = null;\r
\r
    //=================================================================================\r
    // deserialization\r
    //=================================================================================\r
\r
    /* public */ BreakDictionary(InputStream dictionaryStream) throws IOException {\r
        readDictionaryFile(new DataInputStream(dictionaryStream));\r
    }\r
\r
    /* public */ void readDictionaryFile(DataInputStream in) throws IOException {\r
        int l;\r
\r
        // read in the version number (right now we just ignore it)\r
        in.readInt();\r
\r
        // read in the column map (this is serialized in its internal form:\r
        // an index array followed by a data array)\r
        l = in.readInt();\r
        char[] temp = new char[l];\r
        for (int i = 0; i < temp.length; i++)\r
            temp[i] = (char)in.readShort();\r
        l = in.readInt();\r
        byte[] temp2 = new byte[l];\r
        for (int i = 0; i < temp2.length; i++)\r
            temp2[i] = in.readByte();\r
        columnMap = new CompactByteArray(temp, temp2);\r
\r
        // read in numCols and numColGroups\r
        numCols = in.readInt();\r
        /*numColGroups = */in.readInt();\r
\r
        // read in the row-number index\r
        l = in.readInt();\r
        rowIndex = new short[l];\r
        for (int i = 0; i < rowIndex.length; i++)\r
            rowIndex[i] = in.readShort();\r
\r
        // load in the populated-cells bitmap: index first, then bitmap list\r
        l = in.readInt();\r
        rowIndexFlagsIndex = new short[l];\r
        for (int i = 0; i < rowIndexFlagsIndex.length; i++)\r
            rowIndexFlagsIndex[i] = in.readShort();\r
        l = in.readInt();\r
        rowIndexFlags = new int[l];\r
        for (int i = 0; i < rowIndexFlags.length; i++)\r
            rowIndexFlags[i] = in.readInt();\r
\r
        // load in the row-shift index\r
        l = in.readInt();\r
        rowIndexShifts = new byte[l];\r
        for (int i = 0; i < rowIndexShifts.length; i++)\r
            rowIndexShifts[i] = in.readByte();\r
\r
        // finally, load in the actual state table\r
        l = in.readInt();\r
        table = new short[l];\r
        for (int i = 0; i < table.length; i++)\r
            table[i] = in.readShort();\r
\r
        // this data structure is only necessary for testing and debugging purposes\r
        reverseColumnMap = new char[numCols];\r
        for (char c = 0; c < 0xffff; c++) {\r
            int col = columnMap.elementAt(c);\r
            if (col != 0) {\r
               reverseColumnMap[col] = c;\r
            }\r
        }\r
\r
        // close the stream\r
        in.close();\r
    }\r
\r
    //=================================================================================\r
    // access to the words\r
    //=================================================================================\r
\r
    /**\r
     * Uses the column map to map the character to a column number, then\r
     * passes the row and column number to the other version of at()\r
     * @param row The current state\r
     * @param ch The character whose column we're interested in\r
     * @return The new state to transition to\r
     */\r
    /* public */ final short at(int row, char ch) {\r
        int col = columnMap.elementAt(ch);\r
        return at(row, col);\r
    }\r
\r
    /**\r
     * Returns the value in the cell with the specified (logical) row and\r
     * column numbers.  In DictionaryBasedBreakIterator, the row number is\r
     * a state number, the column number is an input, and the return value\r
     * is the row number of the new state to transition to.  (0 is the\r
     * "error" state, and -1 is the "end of word" state in a dictionary)\r
     * @param row The row number of the current state\r
     * @param col The column number of the input character (0 means "not a\r
     * dictionary character")\r
     * @return The row number of the new state to transition to\r
     */\r
    /* public */ final short at(int row, int col) {\r
        if (cellIsPopulated(row, col)) {\r
            // we map from logical to physical row number by looking up the\r
            // mapping in rowIndex; we map from logical column number to\r
            // physical column number by looking up a shift value for this\r
            // logical row and offsetting the logical column number by\r
            // the shift amount.  Then we can use internalAt() to actually\r
            // get the value out of the table.\r
            return internalAt(rowIndex[row], col + rowIndexShifts[row]);\r
        }\r
        else {\r
            return 0;\r
        }\r
    }\r
\r
    /**\r
     * Given (logical) row and column numbers, returns true if the\r
     * cell in that position is populated\r
     */\r
    private final boolean cellIsPopulated(int row, int col) {\r
        // look up the entry in the bitmap index for the specified row.\r
        // If it's a negative number, it's the column number of the only\r
        // populated cell in the row\r
        if (rowIndexFlagsIndex[row] < 0) {\r
            return col == -rowIndexFlagsIndex[row];\r
        }\r
\r
        // if it's a positive number, it's the offset of an entry in the bitmap\r
        // list.  If the table is more than 32 columns wide, the bitmap is stored\r
        // successive entries in the bitmap list, so we have to divide the column\r
        // number by 32 and offset the number we got out of the index by the result.\r
        // Once we have the appropriate piece of the bitmap, test the appropriate\r
        // bit and return the result.\r
        else {\r
            int flags = rowIndexFlags[rowIndexFlagsIndex[row] + (col >> 5)];\r
            return (flags & (1 << (col & 0x1f))) != 0;\r
        }\r
    }\r
\r
    /**\r
     * Implementation of at() when we know the specified cell is populated.\r
     * @param row The PHYSICAL row number of the cell\r
     * @param col The PHYSICAL column number of the cell\r
     * @return The value stored in the cell\r
     */\r
    private final short internalAt(int row, int col) {\r
        // the table is a one-dimensional array, so this just does the math necessary\r
        // to treat it as a two-dimensional array (we don't just use a two-dimensional\r
        // array because two-dimensional arrays are inefficient in Java)\r
        return table[row * numCols + col];\r
    }\r
}\r
\r