KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > java > text > DictionaryBasedBreakIterator


1 /*
2  * @(#)DictionaryBasedBreakIterator.java 1.13 03/12/19
3  *
4  * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5  * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6  */

7
8 /*
9  * @(#)DictionaryBasedBreakIterator.java 1.3 99/05/03
10  *
11  * (C) Copyright Taligent, Inc. 1996, 1997 - All Rights Reserved
12  * (C) Copyright IBM Corp. 1996 - 2002 - All Rights Reserved
13  *
14  * The original version of this source code and documentation
15  * is copyrighted and owned by Taligent, Inc., a wholly-owned
16  * subsidiary of IBM. These materials are provided under terms
17  * of a License Agreement between Taligent and Sun. This technology
18  * is protected by multiple US and International patents.
19  *
20  * This notice and attribution to Taligent may not be removed.
21  * Taligent is a registered trademark of Taligent, Inc.
22  */

23
24 package java.text;
25
26 import java.util.Vector JavaDoc;
27 import java.util.Stack JavaDoc;
28 import java.util.Hashtable JavaDoc;
29 import java.text.CharacterIterator JavaDoc;
30 import java.io.InputStream JavaDoc;
31 import java.io.IOException JavaDoc;
32
33 /**
34  * A subclass of RuleBasedBreakIterator that adds the ability to use a dictionary
35  * to further subdivide ranges of text beyond what is possible using just the
36  * state-table-based algorithm. This is necessary, for example, to handle
37  * word and line breaking in Thai, which doesn't use spaces between words. The
38  * state-table-based algorithm used by RuleBasedBreakIterator is used to divide
39  * up text as far as possible, and then contiguous ranges of letters are
40  * repeatedly compared against a list of known words (i.e., the dictionary)
41  * to divide them up into words.
42  *
43  * DictionaryBasedBreakIterator uses the same rule language as RuleBasedBreakIterator,
44  * but adds one more special substitution name: <dictionary>. This substitution
45  * name is used to identify characters in words in the dictionary. The idea is that
46  * if the iterator passes over a chunk of text that includes two or more characters
47  * in a row that are included in <dictionary>, it goes back through that range and
48  * derives additional break positions (if possible) using the dictionary.
49  *
50  * DictionaryBasedBreakIterator is also constructed with the filename of a dictionary
51  * file. It follows a prescribed search path to locate the dictionary (right now,
52  * it looks for it in /com/ibm/text/resources in each directory in the classpath,
53  * and won't find it in JAR files, but this location is likely to change). The
54  * dictionary file is in a serialized binary format. We have a very primitive (and
55  * slow) BuildDictionaryFile utility for creating dictionary files, but aren't
56  * currently making it public. Contact us for help.
57  */

58 class DictionaryBasedBreakIterator extends RuleBasedBreakIterator JavaDoc {
59
60     /**
61      * a list of known words that is used to divide up contiguous ranges of letters,
62      * stored in a compressed, indexed, format that offers fast access
63      */

64     private BreakDictionary JavaDoc dictionary;
65
66     /**
67      * a list of flags indicating which character categories are contained in
68      * the dictionary file (this is used to determine which ranges of characters
69      * to apply the dictionary to)
70      */

71     private boolean[] categoryFlags;
72
73     /**
74      * a temporary hiding place for the number of dictionary characters in the
75      * last range passed over by next()
76      */

77     private int dictionaryCharCount;
78
79     /**
80      * when a range of characters is divided up using the dictionary, the break
81      * positions that are discovered are stored here, preventing us from having
82      * to use either the dictionary or the state table again until the iterator
83      * leaves this range of text
84      */

85     private int[] cachedBreakPositions;
86
87     /**
88      * if cachedBreakPositions is not null, this indicates which item in the
89      * cache the current iteration position refers to
90      */

91     private int positionInCache;
92
93     /**
94      * Constructs a DictionaryBasedBreakIterator.
95      * @param description Same as the description parameter on RuleBasedBreakIterator,
96      * except for the special meaning of "<dictionary>". This parameter is just
97      * passed through to RuleBasedBreakIterator's constructor.
98      * @param dictionaryFilename The filename of the dictionary file to use
99      */

100     public DictionaryBasedBreakIterator(String JavaDoc dataFile, String JavaDoc dictionaryFile)
101                                         throws IOException JavaDoc {
102         super(dataFile);
103         byte[] tmp = super.getAdditionalData();
104         if (tmp != null) {
105             prepareCategoryFlags(tmp);
106             super.setAdditionalData(null);
107         }
108         dictionary = new BreakDictionary JavaDoc(dictionaryFile);
109     }
110
111     private void prepareCategoryFlags(byte[] data) {
112     categoryFlags = new boolean[data.length];
113         for (int i = 0; i < data.length; i++) {
114             categoryFlags[i] = (data[i] == (byte)1) ? true : false;
115         }
116     }
117
118     public void setText(CharacterIterator JavaDoc newText) {
119         super.setText(newText);
120         cachedBreakPositions = null;
121         dictionaryCharCount = 0;
122         positionInCache = 0;
123     }
124
125     /**
126      * Sets the current iteration position to the beginning of the text.
127      * (i.e., the CharacterIterator's starting offset).
128      * @return The offset of the beginning of the text.
129      */

130     public int first() {
131         cachedBreakPositions = null;
132         dictionaryCharCount = 0;
133         positionInCache = 0;
134         return super.first();
135     }
136
137     /**
138      * Sets the current iteration position to the end of the text.
139      * (i.e., the CharacterIterator's ending offset).
140      * @return The text's past-the-end offset.
141      */

142     public int last() {
143         cachedBreakPositions = null;
144         dictionaryCharCount = 0;
145         positionInCache = 0;
146         return super.last();
147     }
148
149     /**
150      * Advances the iterator one step backwards.
151      * @return The position of the last boundary position before the
152      * current iteration position
153      */

154     public int previous() {
155         CharacterIterator JavaDoc text = getText();
156
157         // if we have cached break positions and we're still in the range
158
// covered by them, just move one step backward in the cache
159
if (cachedBreakPositions != null && positionInCache > 0) {
160             --positionInCache;
161             text.setIndex(cachedBreakPositions[positionInCache]);
162             return cachedBreakPositions[positionInCache];
163         }
164
165         // otherwise, dump the cache and use the inherited previous() method to move
166
// backward. This may fill up the cache with new break positions, in which
167
// case we have to mark our position in the cache
168
else {
169             cachedBreakPositions = null;
170             int result = super.previous();
171             if (cachedBreakPositions != null) {
172                 positionInCache = cachedBreakPositions.length - 2;
173             }
174             return result;
175         }
176     }
177
178     /**
179      * Sets the current iteration position to the last boundary position
180      * before the specified position.
181      * @param offset The position to begin searching from
182      * @return The position of the last boundary before "offset"
183      */

184     public int preceding(int offset) {
185         CharacterIterator JavaDoc text = getText();
186         checkOffset(offset, text);
187
188         // if we have no cached break positions, or "offset" is outside the
189
// range covered by the cache, we can just call the inherited routine
190
// (which will eventually call other routines in this class that may
191
// refresh the cache)
192
if (cachedBreakPositions == null || offset <= cachedBreakPositions[0] ||
193                 offset > cachedBreakPositions[cachedBreakPositions.length - 1]) {
194             cachedBreakPositions = null;
195             return super.preceding(offset);
196         }
197
198         // on the other hand, if "offset" is within the range covered by the cache,
199
// then all we have to do is search the cache for the last break position
200
// before "offset"
201
else {
202             positionInCache = 0;
203             while (positionInCache < cachedBreakPositions.length
204                    && offset > cachedBreakPositions[positionInCache]) {
205                 ++positionInCache;
206             }
207             --positionInCache;
208             text.setIndex(cachedBreakPositions[positionInCache]);
209             return text.getIndex();
210         }
211     }
212
213     /**
214      * Sets the current iteration position to the first boundary position after
215      * the specified position.
216      * @param offset The position to begin searching forward from
217      * @return The position of the first boundary after "offset"
218      */

219     public int following(int offset) {
220         CharacterIterator JavaDoc text = getText();
221         checkOffset(offset, text);
222
223         // if we have no cached break positions, or if "offset" is outside the
224
// range covered by the cache, then dump the cache and call our
225
// inherited following() method. This will call other methods in this
226
// class that may refresh the cache.
227
if (cachedBreakPositions == null || offset < cachedBreakPositions[0] ||
228                 offset >= cachedBreakPositions[cachedBreakPositions.length - 1]) {
229             cachedBreakPositions = null;
230             return super.following(offset);
231         }
232
233         // on the other hand, if "offset" is within the range covered by the
234
// cache, then just search the cache for the first break position
235
// after "offset"
236
else {
237             positionInCache = 0;
238             while (positionInCache < cachedBreakPositions.length
239                    && offset >= cachedBreakPositions[positionInCache]) {
240                 ++positionInCache;
241             }
242             text.setIndex(cachedBreakPositions[positionInCache]);
243             return text.getIndex();
244         }
245     }
246
247     /**
248      * This is the implementation function for next().
249      */

250     protected int handleNext() {
251         CharacterIterator JavaDoc text = getText();
252
253         // if there are no cached break positions, or if we've just moved
254
// off the end of the range covered by the cache, we have to dump
255
// and possibly regenerate the cache
256
if (cachedBreakPositions == null ||
257         positionInCache == cachedBreakPositions.length - 1) {
258
259             // start by using the inherited handleNext() to find a tentative return
260
// value. dictionaryCharCount tells us how many dictionary characters
261
// we passed over on our way to the tentative return value
262
int startPos = text.getIndex();
263             dictionaryCharCount = 0;
264             int result = super.handleNext();
265
266             // if we passed over more than one dictionary character, then we use
267
// divideUpDictionaryRange() to regenerate the cached break positions
268
// for the new range
269
if (dictionaryCharCount > 1 && result - startPos > 1) {
270                 divideUpDictionaryRange(startPos, result);
271             }
272
273             // otherwise, the value we got back from the inherited fuction
274
// is our return value, and we can dump the cache
275
else {
276                 cachedBreakPositions = null;
277                 return result;
278             }
279         }
280
281         // if the cache of break positions has been regenerated (or existed all
282
// along), then just advance to the next break position in the cache
283
// and return it
284
if (cachedBreakPositions != null) {
285             ++positionInCache;
286             text.setIndex(cachedBreakPositions[positionInCache]);
287             return cachedBreakPositions[positionInCache];
288         }
289         return -9999; // SHOULD NEVER GET HERE!
290
}
291
292     /**
293      * Looks up a character category for a character.
294      */

295     protected int lookupCategory(int c) {
296         // this override of lookupCategory() exists only to keep track of whether we've
297
// passed over any dictionary characters. It calls the inherited lookupCategory()
298
// to do the real work, and then checks whether its return value is one of the
299
// categories represented in the dictionary. If it is, bump the dictionary-
300
// character count.
301
int result = super.lookupCategory(c);
302         if (result != RuleBasedBreakIterator.IGNORE && categoryFlags[result]) {
303             ++dictionaryCharCount;
304         }
305         return result;
306     }
307
308     /**
309      * This is the function that actually implements the dictionary-based
310      * algorithm. Given the endpoints of a range of text, it uses the
311      * dictionary to determine the positions of any boundaries in this
312      * range. It stores all the boundary positions it discovers in
313      * cachedBreakPositions so that we only have to do this work once
314      * for each time we enter the range.
315      */

316     private void divideUpDictionaryRange(int startPos, int endPos) {
317         CharacterIterator JavaDoc text = getText();
318
319         // the range we're dividing may begin or end with non-dictionary characters
320
// (i.e., for line breaking, we may have leading or trailing punctuation
321
// that needs to be kept with the word). Seek from the beginning of the
322
// range to the first dictionary character
323
text.setIndex(startPos);
324         int c = getCurrent();
325         int category = lookupCategory(c);
326         while (category == IGNORE || !categoryFlags[category]) {
327             c = getNext();
328             category = lookupCategory(c);
329         }
330
331         // initialize. We maintain two stacks: currentBreakPositions contains
332
// the list of break positions that will be returned if we successfully
333
// finish traversing the whole range now. possibleBreakPositions lists
334
// all other possible word ends we've passed along the way. (Whenever
335
// we reach an error [a sequence of characters that can't begin any word
336
// in the dictionary], we back up, possibly delete some breaks from
337
// currentBreakPositions, move a break from possibleBreakPositions
338
// to currentBreakPositions, and start over from there. This process
339
// continues in this way until we either successfully make it all the way
340
// across the range, or exhaust all of our combinations of break
341
// positions.)
342
Stack JavaDoc currentBreakPositions = new Stack JavaDoc();
343         Stack JavaDoc possibleBreakPositions = new Stack JavaDoc();
344         Vector JavaDoc wrongBreakPositions = new Vector JavaDoc();
345
346         // the dictionary is implemented as a trie, which is treated as a state
347
// machine. -1 represents the end of a legal word. Every word in the
348
// dictionary is represented by a path from the root node to -1. A path
349
// that ends in state 0 is an illegal combination of characters.
350
int state = 0;
351
352         // these two variables are used for error handling. We keep track of the
353
// farthest we've gotten through the range being divided, and the combination
354
// of breaks that got us that far. If we use up all possible break
355
// combinations, the text contains an error or a word that's not in the
356
// dictionary. In this case, we "bless" the break positions that got us the
357
// farthest as real break positions, and then start over from scratch with
358
// the character where the error occurred.
359
int farthestEndPoint = text.getIndex();
360         Stack JavaDoc bestBreakPositions = null;
361
362         // initialize (we always exit the loop with a break statement)
363
c = getCurrent();
364         while (true) {
365
366             // if we can transition to state "-1" from our current state, we're
367
// on the last character of a legal word. Push that position onto
368
// the possible-break-positions stack
369
if (dictionary.getNextState(state, 0) == -1) {
370                 possibleBreakPositions.push(new Integer JavaDoc(text.getIndex()));
371             }
372
373             // look up the new state to transition to in the dictionary
374
state = dictionary.getNextStateFromCharacter(state, c);
375
376             // if the character we're sitting on causes us to transition to
377
// the "end of word" state, then it was a non-dictionary character
378
// and we've successfully traversed the whole range. Drop out
379
// of the loop.
380
if (state == -1) {
381                 currentBreakPositions.push(new Integer JavaDoc(text.getIndex()));
382                 break;
383             }
384
385             // if the character we're sitting on causes us to transition to
386
// the error state, or if we've gone off the end of the range
387
// without transitioning to the "end of word" state, we've hit
388
// an error...
389
else if (state == 0 || text.getIndex() >= endPos) {
390
391                 // if this is the farthest we've gotten, take note of it in
392
// case there's an error in the text
393
if (text.getIndex() > farthestEndPoint) {
394                     farthestEndPoint = text.getIndex();
395                     bestBreakPositions = (Stack JavaDoc)(currentBreakPositions.clone());
396                 }
397
398                 // wrongBreakPositions is a list of all break positions
399
// we've tried starting that didn't allow us to traverse
400
// all the way through the text. Every time we pop a
401
//break position off of currentBreakPositions, we put it
402
// into wrongBreakPositions to avoid trying it again later.
403
// If we make it to this spot, we're either going to back
404
// up to a break in possibleBreakPositions and try starting
405
// over from there, or we've exhausted all possible break
406
// positions and are going to do the fallback procedure.
407
// This loop prevents us from messing with anything in
408
// possibleBreakPositions that didn't work as a starting
409
// point the last time we tried it (this is to prevent a bunch of
410
// repetitive checks from slowing down some extreme cases)
411
Integer JavaDoc newStartingSpot = null;
412                 while (!possibleBreakPositions.isEmpty() && wrongBreakPositions.contains(
413                             possibleBreakPositions.peek())) {
414                     possibleBreakPositions.pop();
415                 }
416                 
417                 // if we've used up all possible break-position combinations, there's
418
// an error or an unknown word in the text. In this case, we start
419
// over, treating the farthest character we've reached as the beginning
420
// of the range, and "blessing" the break positions that got us that
421
// far as real break positions
422
if (possibleBreakPositions.isEmpty()) {
423                     if (bestBreakPositions != null) {
424                         currentBreakPositions = bestBreakPositions;
425                         if (farthestEndPoint < endPos) {
426                             text.setIndex(farthestEndPoint + 1);
427                         }
428                         else {
429                             break;
430                         }
431                     }
432                     else {
433                         if ((currentBreakPositions.size() == 0 ||
434                  ((Integer JavaDoc)(currentBreakPositions.peek())).intValue() != text.getIndex())
435                 && text.getIndex() != startPos) {
436                             currentBreakPositions.push(new Integer JavaDoc(text.getIndex()));
437                         }
438                         getNext();
439                         currentBreakPositions.push(new Integer JavaDoc(text.getIndex()));
440                     }
441                 }
442
443                 // if we still have more break positions we can try, then promote the
444
// last break in possibleBreakPositions into currentBreakPositions,
445
// and get rid of all entries in currentBreakPositions that come after
446
// it. Then back up to that position and start over from there (i.e.,
447
// treat that position as the beginning of a new word)
448
else {
449                     Integer JavaDoc temp = (Integer JavaDoc)possibleBreakPositions.pop();
450                     Object JavaDoc temp2 = null;
451                     while (!currentBreakPositions.isEmpty() && temp.intValue() <
452                            ((Integer JavaDoc)currentBreakPositions.peek()).intValue()) {
453                         temp2 = currentBreakPositions.pop();
454                         wrongBreakPositions.addElement(temp2);
455                     }
456                     currentBreakPositions.push(temp);
457                     text.setIndex(((Integer JavaDoc)currentBreakPositions.peek()).intValue());
458                 }
459
460                 // re-sync "c" for the next go-round, and drop out of the loop if
461
// we've made it off the end of the range
462
c = getCurrent();
463                 if (text.getIndex() >= endPos) {
464                     break;
465                 }
466             }
467
468             // if we didn't hit any exceptional conditions on this last iteration,
469
// just advance to the next character and loop
470
else {
471                 c = getNext();
472             }
473         }
474
475         // dump the last break position in the list, and replace it with the actual
476
// end of the range (which may be the same character, or may be further on
477
// because the range actually ended with non-dictionary characters we want to
478
// keep with the word)
479
if (!currentBreakPositions.isEmpty()) {
480             currentBreakPositions.pop();
481         }
482         currentBreakPositions.push(new Integer JavaDoc(endPos));
483
484         // create a regular array to hold the break positions and copy
485
// the break positions from the stack to the array (in addition,
486
// our starting position goes into this array as a break position).
487
// This array becomes the cache of break positions used by next()
488
// and previous(), so this is where we actually refresh the cache.
489
cachedBreakPositions = new int[currentBreakPositions.size() + 1];
490         cachedBreakPositions[0] = startPos;
491
492         for (int i = 0; i < currentBreakPositions.size(); i++) {
493             cachedBreakPositions[i + 1] = ((Integer JavaDoc)currentBreakPositions.elementAt(i)).intValue();
494         }
495         positionInCache = 0;
496     }
497 }
498
Popular Tags