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

BreakDictionary

public class BreakDictionary extends Object
This is the class that represents the list of known words used by DictionaryBasedBreakIterator. The conceptual data structure used here is a trie: there is a node hanging off the root node for every letter that can start a word. Each of these nodes has a node hanging off of it for every letter that can be the second letter of a word if this node is the first letter, and so on. The trie is represented as a two-dimensional array that can be treated as a table of state transitions. Indexes are used to compress this array, taking advantage of the fact that this array will always be very sparse.

Fields Summary
private static int
supportedVersion
The version of the dictionary that was read in.
private CompactByteArray
columnMap
Maps from characters to column numbers. The main use of this is to avoid making room in the array for empty columns.
private SupplementaryCharacterData
supplementaryCharColumnMap
private int
numCols
The number of actual columns in the table
private int
numColGroups
Columns are organized into groups of 32. This says how many column groups. (We could calculate this, but we store the value to avoid having to repeatedly calculate it.)
private short[]
table
The actual compressed state table. Each conceptual row represents a state, and the cells in it contain the row numbers of the states to transition to for each possible letter. 0 is used to indicate an illegal combination of letters (i.e., the error state). The table is compressed by eliminating all the unpopulated (i.e., zero) cells. Multiple conceptual rows can then be doubled up in a single physical row by sliding them up and possibly shifting them to one side or the other so the populated cells don't collide. Indexes are used to identify unpopulated cells and to locate populated cells.
private short[]
rowIndex
This index maps logical row numbers to physical row numbers
private int[]
rowIndexFlags
A bitmap is used to tell which cells in the comceptual table are populated. This array contains all the unique bit combinations in that bitmap. If the table is more than 32 columns wide, successive entries in this array are used for a single row.
private short[]
rowIndexFlagsIndex
This index maps from a logical row number into the bitmap table above. (This keeps us from storing duplicate bitmap combinations.) Since there are a lot of rows with only one populated cell, instead of wasting space in the bitmap table, we just store a negative number in this index for rows with one populated cell. The absolute value of that number is the column number of the populated cell.
private byte[]
rowIndexShifts
For each logical row, this index contains a constant that is added to the logical column number to get the physical column number
Constructors Summary
public BreakDictionary(String dictionaryName)


    //=========================================================================
    // deserialization
    //=========================================================================

      
           

        readDictionaryFile(dictionaryName);
Methods Summary
private final booleancellIsPopulated(int row, int col)
Given (logical) row and column numbers, returns true if the cell in that position is populated

        // look up the entry in the bitmap index for the specified row.
        // If it's a negative number, it's the column number of the only
        // populated cell in the row
        if (rowIndexFlagsIndex[row] < 0) {
            return col == -rowIndexFlagsIndex[row];
        }

        // if it's a positive number, it's the offset of an entry in the bitmap
        // list.  If the table is more than 32 columns wide, the bitmap is stored
        // successive entries in the bitmap list, so we have to divide the column
        // number by 32 and offset the number we got out of the index by the result.
        // Once we have the appropriate piece of the bitmap, test the appropriate
        // bit and return the result.
        else {
            int flags = rowIndexFlags[rowIndexFlagsIndex[row] + (col >> 5)];
            return (flags & (1 << (col & 0x1f))) != 0;
        }
public final shortgetNextState(int row, int col)
Returns the value in the cell with the specified (logical) row and column numbers. In DictionaryBasedBreakIterator, the row number is a state number, the column number is an input, and the return value is the row number of the new state to transition to. (0 is the "error" state, and -1 is the "end of word" state in a dictionary)

param
row The row number of the current state
param
col The column number of the input character (0 means "not a dictionary character")
return
The row number of the new state to transition to

        if (cellIsPopulated(row, col)) {
            // we map from logical to physical row number by looking up the
            // mapping in rowIndex; we map from logical column number to
            // physical column number by looking up a shift value for this
            // logical row and offsetting the logical column number by
            // the shift amount.  Then we can use internalAt() to actually
            // get the value out of the table.
            return internalAt(rowIndex[row], col + rowIndexShifts[row]);
        }
        else {
            return 0;
        }
public final shortgetNextStateFromCharacter(int row, int ch)
Uses the column map to map the character to a column number, then passes the row and column number to getNextState()

param
row The current state
param
ch The character whose column we're interested in
return
The new state to transition to

        int col;
        if (ch < Character.MIN_SUPPLEMENTARY_CODE_POINT) {
            col = columnMap.elementAt((char)ch);
        } else {
            col = supplementaryCharColumnMap.getValue(ch);
        }
        return getNextState(row, col);
private final shortinternalAt(int row, int col)
Implementation of getNextState() when we know the specified cell is populated.

param
row The PHYSICAL row number of the cell
param
col The PHYSICAL column number of the cell
return
The value stored in the cell

        // the table is a one-dimensional array, so this just does the math necessary
        // to treat it as a two-dimensional array (we don't just use a two-dimensional
        // array because two-dimensional arrays are inefficient in Java)
        return table[row * numCols + col];
private voidreadDictionaryFile(java.lang.String dictionaryName)


        BufferedInputStream in;
        try {
            in = (BufferedInputStream)AccessController.doPrivileged(
                new PrivilegedExceptionAction() {
                    public Object run() throws Exception {
                        return new BufferedInputStream(getClass().getResourceAsStream("/sun/text/resources/" + dictionaryName));
                    }
                }
            );
        }
        catch (PrivilegedActionException e) {
            throw new InternalError(e.toString());
        }
 
        byte[] buf = new byte[8];
        if (in.read(buf) != 8) {
            throw new MissingResourceException("Wrong data length",
                                               dictionaryName, "");
        }

        // check vesion
        int version = BreakIterator.getInt(buf, 0);
        if (version != supportedVersion) {
            throw new MissingResourceException("Dictionary version(" + version + ") is unsupported", 
                                                           dictionaryName, "");
        }

        // get data size
        int len = BreakIterator.getInt(buf, 4);
        buf = new byte[len];
        if (in.read(buf) != len) {
            throw new MissingResourceException("Wrong data length",
                                               dictionaryName, "");
        }

        // close the stream
        in.close();

        int l;
        int offset = 0;

        // read in the column map for BMP characteres (this is serialized in
        // its internal form: an index array followed by a data array)
        l = BreakIterator.getInt(buf, offset);
        offset += 4;
        short[] temp = new short[l];
        for (int i = 0; i < l; i++, offset+=2) {
            temp[i] = BreakIterator.getShort(buf, offset);
        }
        l = BreakIterator.getInt(buf, offset);
        offset += 4;
        byte[] temp2 = new byte[l];
        for (int i = 0; i < l; i++, offset++) {
            temp2[i] = buf[offset];
        }
        columnMap = new CompactByteArray(temp, temp2);

        // read in numCols and numColGroups
        numCols = BreakIterator.getInt(buf, offset);
        offset += 4;
        numColGroups = BreakIterator.getInt(buf, offset);
        offset += 4;

        // read in the row-number index
        l = BreakIterator.getInt(buf, offset);
        offset += 4;
        rowIndex = new short[l];
        for (int i = 0; i < l; i++, offset+=2) {
            rowIndex[i] = BreakIterator.getShort(buf, offset);
        }

        // load in the populated-cells bitmap: index first, then bitmap list
        l = BreakIterator.getInt(buf, offset);
        offset += 4;
        rowIndexFlagsIndex = new short[l];
        for (int i = 0; i < l; i++, offset+=2) {
            rowIndexFlagsIndex[i] = BreakIterator.getShort(buf, offset);
        }
        l = BreakIterator.getInt(buf, offset);
        offset += 4;
        rowIndexFlags = new int[l];
        for (int i = 0; i < l; i++, offset+=4) {
            rowIndexFlags[i] = BreakIterator.getInt(buf, offset);
        }

        // load in the row-shift index
        l = BreakIterator.getInt(buf, offset);
        offset += 4;
        rowIndexShifts = new byte[l];
        for (int i = 0; i < l; i++, offset++) {
            rowIndexShifts[i] = buf[offset];
        }

        // load in the actual state table
        l = BreakIterator.getInt(buf, offset);
        offset += 4;
        table = new short[l];
        for (int i = 0; i < l; i++, offset+=2) {
            table[i] = BreakIterator.getShort(buf, offset);
        }

        // finally, prepare the column map for supplementary characters
        l = BreakIterator.getInt(buf, offset);
        offset += 4;
        int[] temp3 = new int[l];
        for (int i = 0; i < l; i++, offset+=4) {
            temp3[i] = BreakIterator.getInt(buf, offset);
        }
        supplementaryCharColumnMap = new SupplementaryCharacterData(temp3);