2 *******************************************************************************
\r
3 * Copyright (C) 1996-2007, International Business Machines Corporation and *
\r
4 * others. All Rights Reserved. *
\r
5 *******************************************************************************
\r
7 package com.ibm.icu.text;
\r
9 import java.io.InputStream;
\r
10 import java.io.DataInputStream;
\r
11 import java.io.FileNotFoundException;
\r
12 import java.io.UnsupportedEncodingException;
\r
13 import java.io.IOException;
\r
14 import java.io.FileInputStream;
\r
15 import java.io.OutputStreamWriter;
\r
16 import java.io.PrintWriter;
\r
17 import java.io.FileOutputStream;
\r
19 import com.ibm.icu.util.CompactByteArray;
\r
22 * This is the class that represents the list of known words used by
\r
23 * DictionaryBasedBreakIterator. The conceptual data structure used
\r
24 * here is a trie: there is a node hanging off the root node for every
\r
25 * letter that can start a word. Each of these nodes has a node hanging
\r
26 * off of it for every letter that can be the second letter of a word
\r
27 * if this node is the first letter, and so on. The trie is represented
\r
28 * as a two-dimensional array that can be treated as a table of state
\r
29 * transitions. Indexes are used to compress this array, taking
\r
30 * advantage of the fact that this array will always be very sparse.
\r
32 * @deprecated This API is ICU internal only.
\r
34 public class BreakDictionary {
\r
35 //=================================================================================
\r
36 // testing and debugging
\r
37 //=================================================================================
\r
40 * @deprecated This API is ICU internal only.
\r
42 public static void main(String args[])
\r
43 throws FileNotFoundException, UnsupportedEncodingException, IOException {
\r
44 String filename = args[0];
\r
46 BreakDictionary dictionary = new BreakDictionary(new FileInputStream(filename));
\r
48 PrintWriter out = null;
\r
50 if(args.length >= 2) {
\r
51 out = new PrintWriter(new OutputStreamWriter(new FileOutputStream(args[1]), "UnicodeLittle"));
\r
54 dictionary.printWordList("", 0, out);
\r
63 * @deprecated This API is ICU internal only.
\r
65 public void printWordList(String partialWord, int state, PrintWriter out)
\r
66 throws IOException {
\r
67 if (state == 0xFFFF) {
\r
68 System.out.println(partialWord);
\r
70 out.println(partialWord);
\r
74 for (int i = 0; i < numCols; i++) {
\r
75 int newState = (at(state, i)) & 0xFFFF;
\r
77 if (newState != 0) {
\r
78 char newChar = reverseColumnMap[i];
\r
79 String newPartialWord = partialWord;
\r
82 newPartialWord += newChar;
\r
85 printWordList(newPartialWord, newState, out);
\r
92 * A map used to go from column numbers to characters. Used only
\r
93 * for debugging right now.
\r
95 private char[] reverseColumnMap = null;
\r
97 //=================================================================================
\r
99 //=================================================================================
\r
102 * Maps from characters to column numbers. The main use of this is to
\r
103 * avoid making room in the array for empty columns.
\r
105 private CompactByteArray columnMap = null;
\r
108 * The number of actual columns in the table
\r
110 private int numCols;
\r
113 * Columns are organized into groups of 32. This says how many
\r
114 * column groups. (We could calculate this, but we store the
\r
115 * value to avoid having to repeatedly calculate it.)
\r
117 //private int numColGroups;
\r
120 * The actual compressed state table. Each conceptual row represents
\r
121 * a state, and the cells in it contain the row numbers of the states
\r
122 * to transition to for each possible letter. 0 is used to indicate
\r
123 * an illegal combination of letters (i.e., the error state). The
\r
124 * table is compressed by eliminating all the unpopulated (i.e., zero)
\r
125 * cells. Multiple conceptual rows can then be doubled up in a single
\r
126 * physical row by sliding them up and possibly shifting them to one
\r
127 * side or the other so the populated cells don't collide. Indexes
\r
128 * are used to identify unpopulated cells and to locate populated cells.
\r
130 private short[] table = null;
\r
133 * This index maps logical row numbers to physical row numbers
\r
135 private short[] rowIndex = null;
\r
138 * A bitmap is used to tell which cells in the comceptual table are
\r
139 * populated. This array contains all the unique bit combinations
\r
140 * in that bitmap. If the table is more than 32 columns wide,
\r
141 * successive entries in this array are used for a single row.
\r
143 private int[] rowIndexFlags = null;
\r
146 * This index maps from a logical row number into the bitmap table above.
\r
147 * (This keeps us from storing duplicate bitmap combinations.) Since there
\r
148 * are a lot of rows with only one populated cell, instead of wasting space
\r
149 * in the bitmap table, we just store a negative number in this index for
\r
150 * rows with one populated cell. The absolute value of that number is
\r
151 * the column number of the populated cell.
\r
153 private short[] rowIndexFlagsIndex = null;
\r
156 * For each logical row, this index contains a constant that is added to
\r
157 * the logical column number to get the physical column number
\r
159 private byte[] rowIndexShifts = null;
\r
161 //=================================================================================
\r
163 //=================================================================================
\r
167 * @deprecated This API is ICU internal only.
\r
169 public BreakDictionary(InputStream dictionaryStream) throws IOException {
\r
170 readDictionaryFile(new DataInputStream(dictionaryStream));
\r
175 * @deprecated This API is ICU internal only.
\r
177 public void readDictionaryFile(DataInputStream in) throws IOException {
\r
180 // read in the version number (right now we just ignore it)
\r
183 // read in the column map (this is serialized in its internal form:
\r
184 // an index array followed by a data array)
\r
186 char[] temp = new char[l];
\r
187 for (int i = 0; i < temp.length; i++)
\r
188 temp[i] = (char)in.readShort();
\r
190 byte[] temp2 = new byte[l];
\r
191 for (int i = 0; i < temp2.length; i++)
\r
192 temp2[i] = in.readByte();
\r
193 columnMap = new CompactByteArray(temp, temp2);
\r
195 // read in numCols and numColGroups
\r
196 numCols = in.readInt();
\r
197 /*numColGroups = */in.readInt();
\r
199 // read in the row-number index
\r
201 rowIndex = new short[l];
\r
202 for (int i = 0; i < rowIndex.length; i++)
\r
203 rowIndex[i] = in.readShort();
\r
205 // load in the populated-cells bitmap: index first, then bitmap list
\r
207 rowIndexFlagsIndex = new short[l];
\r
208 for (int i = 0; i < rowIndexFlagsIndex.length; i++)
\r
209 rowIndexFlagsIndex[i] = in.readShort();
\r
211 rowIndexFlags = new int[l];
\r
212 for (int i = 0; i < rowIndexFlags.length; i++)
\r
213 rowIndexFlags[i] = in.readInt();
\r
215 // load in the row-shift index
\r
217 rowIndexShifts = new byte[l];
\r
218 for (int i = 0; i < rowIndexShifts.length; i++)
\r
219 rowIndexShifts[i] = in.readByte();
\r
221 // finally, load in the actual state table
\r
223 table = new short[l];
\r
224 for (int i = 0; i < table.length; i++)
\r
225 table[i] = in.readShort();
\r
227 // this data structure is only necessary for testing and debugging purposes
\r
228 reverseColumnMap = new char[numCols];
\r
229 for (char c = 0; c < 0xffff; c++) {
\r
230 int col = columnMap.elementAt(c);
\r
232 reverseColumnMap[col] = c;
\r
236 // close the stream
\r
240 //=================================================================================
\r
241 // access to the words
\r
242 //=================================================================================
\r
245 * Uses the column map to map the character to a column number, then
\r
246 * passes the row and column number to the other version of at()
\r
247 * @param row The current state
\r
248 * @param ch The character whose column we're interested in
\r
249 * @return The new state to transition to
\r
251 * @deprecated This API is ICU internal only.
\r
253 public final short at(int row, char ch) {
\r
254 int col = columnMap.elementAt(ch);
\r
255 return at(row, col);
\r
259 * Returns the value in the cell with the specified (logical) row and
\r
260 * column numbers. In DictionaryBasedBreakIterator, the row number is
\r
261 * a state number, the column number is an input, and the return value
\r
262 * is the row number of the new state to transition to. (0 is the
\r
263 * "error" state, and -1 is the "end of word" state in a dictionary)
\r
264 * @param row The row number of the current state
\r
265 * @param col The column number of the input character (0 means "not a
\r
266 * dictionary character")
\r
267 * @return The row number of the new state to transition to
\r
269 * @deprecated This API is ICU internal only.
\r
271 public final short at(int row, int col) {
\r
272 if (cellIsPopulated(row, col)) {
\r
273 // we map from logical to physical row number by looking up the
\r
274 // mapping in rowIndex; we map from logical column number to
\r
275 // physical column number by looking up a shift value for this
\r
276 // logical row and offsetting the logical column number by
\r
277 // the shift amount. Then we can use internalAt() to actually
\r
278 // get the value out of the table.
\r
279 return internalAt(rowIndex[row], col + rowIndexShifts[row]);
\r
287 * Given (logical) row and column numbers, returns true if the
\r
288 * cell in that position is populated
\r
290 private final boolean cellIsPopulated(int row, int col) {
\r
291 // look up the entry in the bitmap index for the specified row.
\r
292 // If it's a negative number, it's the column number of the only
\r
293 // populated cell in the row
\r
294 if (rowIndexFlagsIndex[row] < 0) {
\r
295 return col == -rowIndexFlagsIndex[row];
\r
298 // if it's a positive number, it's the offset of an entry in the bitmap
\r
299 // list. If the table is more than 32 columns wide, the bitmap is stored
\r
300 // successive entries in the bitmap list, so we have to divide the column
\r
301 // number by 32 and offset the number we got out of the index by the result.
\r
302 // Once we have the appropriate piece of the bitmap, test the appropriate
\r
303 // bit and return the result.
\r
305 int flags = rowIndexFlags[rowIndexFlagsIndex[row] + (col >> 5)];
\r
306 return (flags & (1 << (col & 0x1f))) != 0;
\r
311 * Implementation of at() when we know the specified cell is populated.
\r
312 * @param row The PHYSICAL row number of the cell
\r
313 * @param col The PHYSICAL column number of the cell
\r
314 * @return The value stored in the cell
\r
316 private final short internalAt(int row, int col) {
\r
317 // the table is a one-dimensional array, so this just does the math necessary
\r
318 // to treat it as a two-dimensional array (we don't just use a two-dimensional
\r
319 // array because two-dimensional arrays are inefficient in Java)
\r
320 return table[row * numCols + col];
\r