DictionaryBasedBreakIterator


1   /*
2    *******************************************************************************
3    * Copyright (C) 1996-2006, International Business Machines Corporation and    *
4    * others. All Rights Reserved.                                                *
5    *******************************************************************************
6    */
7   
8   package com.ibm.icu.text;
9   
10  import java.util.Vector  ;
11  import java.util.Stack  ;
12  import com.ibm.icu.impl.Assert;
13  import java.text.CharacterIterator  ;
14  import java.io.InputStream  ;
15  import java.io.IOException  ;
16  
17  
18  /**
19   * A subclass of RuleBasedBreakIterator that adds the ability to use a dictionary
20   * to further subdivide ranges of text beyond what is possible using just the
21   * state-table-based algorithm.  This is necessary, for example, to handle
22   * word and line breaking in Thai, which doesn't use spaces between words.  The
23   * state-table-based algorithm used by RuleBasedBreakIterator_Old is used to divide
24   * up text as far as possible, and then contiguous ranges of letters are
25   * repeatedly compared against a list of known words (i.e., the dictionary)
26   * to divide them up into words.
27   *
28   * DictionaryBasedBreakIterator uses the same rule language as RuleBasedBreakIterator_Old,
29   * but adds one more special substitution name: _dictionary_.  This substitution
30   * name is used to identify characters in words in the dictionary.  The idea is that
31   * if the iterator passes over a chunk of text that includes two or more characters
32   * in a row that are included in _dictionary_, it goes back through that range and
33   * derives additional break positions (if possible) using the dictionary.
34   *
35   * DictionaryBasedBreakIterator is also constructed with the filename of a dictionary
36   * file.  It uses Class.getResource() to locate the dictionary file.  The
37   * dictionary file is in a serialized binary format.  We have a very primitive (and
38   * slow) BuildDictionaryFile utility for creating dictionary files, but aren't
39   * currently making it public.  Contact us for help.
40   *
41   * @stable ICU 2.0
42   */
43  public class DictionaryBasedBreakIterator extends RuleBasedBreakIterator {
44  
45      /**
46       * a list of known words that is used to divide up contiguous ranges of letters,
47       * stored in a compressed, indexed, format that offers fast access
48       */
49      private BreakDictionary dictionary;
50  
51      /**
52       * a list of flags indicating which character categories are contained in
53       * the dictionary file (this is used to determine which ranges of characters
54       * to apply the dictionary to)
55       */
56      private boolean[] categoryFlags;
57  
58  
59      /**
60       * when a range of characters is divided up using the dictionary, the break
61       * positions that are discovered are stored here, preventing us from having
62       * to use either the dictionary or the state table again until the iterator
63       * leaves this range of text
64       */
65      private int[] cachedBreakPositions;
66  
67      /**
68       * if cachedBreakPositions is not null, this indicates which item in the
69       * cache the current iteration position refers to
70       */
71      private int positionInCache;
72  
73      /**
74       * Special variable name for characters in words in dictionary
75       */
76   
77      /**
78       * Constructs a DictionaryBasedBreakIterator.
79       * @param rules Same as the rules parameter on RuleBasedBreakIterator,
80       * except for the special meaning of "_dictionary_".  This parameter is just
81       * passed through to RuleBasedBreakIterator constructor.
82       * @param dictionaryStream the stream containing the dictionary data
83       * @stable ICU 2.0
84       */
85      public DictionaryBasedBreakIterator(String   rules,
86                                          InputStream   dictionaryStream) throws IOException   {
87          super(rules);
88          dictionary = new BreakDictionary(dictionaryStream);
89      }
90  
91      
92      /**
93       * Construct a DictionarBasedBreakIterator from precompiled rules.
94       * @param compiledRules an input stream containing the binary (flattened) compiled rules.
95       * @param dictionaryStream an input stream containing the dictionary data
96       * @internal
97       * @deprecated This API is ICU internal only.
98       */
99      public DictionaryBasedBreakIterator(InputStream   compiledRules,
100                                          InputStream   dictionaryStream) throws IOException   {
101        fRData = RBBIDataWrapper.get(compiledRules);   // Init the RBBI part of this iterator.
102        dictionary = new BreakDictionary(dictionaryStream);
103     }
104                     
105 
106     /** @stable ICU 2.0 */
107     public void setText(CharacterIterator   newText) {
108         super.setText(newText);
109         cachedBreakPositions = null;
110         fDictionaryCharCount = 0;
111         positionInCache = 0;
112     }
113 
114     /**
115      * Sets the current iteration position to the beginning of the text.
116      * (i.e., the CharacterIterator's starting offset).
117      * @return The offset of the beginning of the text.
118      * @stable ICU 2.0
119      */
120     public int first() {
121         cachedBreakPositions = null;
122         fDictionaryCharCount = 0;
123         positionInCache = 0;
124         return super.first();
125     }
126 
127     /**
128      * Sets the current iteration position to the end of the text.
129      * (i.e., the CharacterIterator's ending offset).
130      * @return The text's past-the-end offset.
131      * @stable ICU 2.0
132      */
133     public int last() {
134         cachedBreakPositions = null;
135         fDictionaryCharCount = 0;
136         positionInCache = 0;
137         return super.last();
138     }
139 
140     /**
141      * Advances the iterator one step backwards.
142      * @return The position of the last boundary position before the
143      * current iteration position
144      * @stable ICU 2.0
145      */
146     public int previous() {
147         CharacterIterator   text = getText();
148 
149         // if we have cached break positions and we're still in the range
150         // covered by them, just move one step backward in the cache
151         if (cachedBreakPositions != null && positionInCache > 0) {
152             --positionInCache;
153             text.setIndex(cachedBreakPositions[positionInCache]);
154             return cachedBreakPositions[positionInCache];
155         }
156 
157         // otherwise, dump the cache and use the inherited previous() method to move
158         // backward.  This may fill up the cache with new break positions, in which
159         // case we have to mark our position in the cache. If it doesn't, use next()
160         // to move forward until we hit or pass the current position. This *will* fill
161         // the cache.
162         else {
163             cachedBreakPositions = null;
164             int offset = current();
165             int result = super.previous();
166             
167             if (cachedBreakPositions != null) {
168                 positionInCache = cachedBreakPositions.length - 2;
169                 return result;
170             }
171             
172             while (result < offset) {
173                 int nextResult = next();
174                 
175                 if (nextResult >= offset) {
176                     break;
177                 }
178                 
179                 result = nextResult;
180             }
181             
182             if (cachedBreakPositions != null) {
183                 positionInCache = cachedBreakPositions.length - 2;
184             }
185             
186             if (result != BreakIterator.DONE) {
187                 text.setIndex(result);
188             }
189             
190             return result;
191         }
192     }
193 
194     /**
195      * Sets the current iteration position to the last boundary position
196      * before the specified position.
197      * @param offset The position to begin searching from
198      * @return The position of the last boundary before "offset"
199      * @stable ICU 2.0
200      */
201     public int preceding(int offset) {
202         CharacterIterator   text = getText();
203         checkOffset(offset, text);
204 
205         // if we have no cached break positions, or "offset" is outside the
206         // range covered by the cache, we can just call the inherited routine
207         // (which will eventually call other routines in this class that may
208         // refresh the cache)
209         if (cachedBreakPositions == null || offset <= cachedBreakPositions[0] ||
210                 offset > cachedBreakPositions[cachedBreakPositions.length - 1]) {
211             cachedBreakPositions = null;
212             return super.preceding(offset);
213         }
214 
215         // on the other hand, if "offset" is within the range covered by the cache,
216         // then all we have to do is search the cache for the last break position
217         // before "offset"
218         else {
219             positionInCache = 0;
220             while (positionInCache < cachedBreakPositions.length
221                    && offset > cachedBreakPositions[positionInCache])
222                 ++positionInCache;
223             --positionInCache;
224             text.setIndex(cachedBreakPositions[positionInCache]);
225             return text.getIndex();
226         }
227     }
228 
229     /**
230      * Sets the current iteration position to the first boundary position after
231      * the specified position.
232      * @param offset The position to begin searching forward from
233      * @return The position of the first boundary after "offset"
234      * @stable ICU 2.0
235      */
236     public int following(int offset) {
237         CharacterIterator   text = getText();
238         checkOffset(offset, text);
239 
240         // if we have no cached break positions, or if "offset" is outside the
241         // range covered by the cache, then dump the cache and call our
242         // inherited following() method.  This will call other methods in this
243         // class that may refresh the cache.
244         if (cachedBreakPositions == null || offset < cachedBreakPositions[0] ||
245                 offset >= cachedBreakPositions[cachedBreakPositions.length - 1]) {
246             cachedBreakPositions = null;
247             return super.following(offset);
248         }
249 
250         // on the other hand, if "offset" is within the range covered by the
251         // cache, then just search the cache for the first break position
252         // after "offset"
253         else {
254             positionInCache = 0;
255             while (positionInCache < cachedBreakPositions.length
256                    && offset >= cachedBreakPositions[positionInCache])
257                 ++positionInCache;
258             text.setIndex(cachedBreakPositions[positionInCache]);
259             return text.getIndex();
260         }
261     }
262     
263     
264     /**
265      * Return the status tag from the break rule that determined the most recently
266      * returned break position. 
267      * 
268      * TODO:  not supported with dictionary based break iterators.
269      *
270      * @return the status from the break rule that determined the most recently
271      * returned break position.
272      * @draft ICU 3.0
273      * @provisional This API might change or be removed in a future release.
274      */
275      public int getRuleStatus() {
276         return 0;
277      }
278 
279 
280     /**
281      * Get the status (tag) values from the break rule(s) that determined the most 
282      * recently returned break position.  The values appear in the rule source
283      * within brackets, {123}, for example.  The default status value for rules
284      * that do not explicitly provide one is zero.
285      * <p>
286      * TODO: not supported for dictionary based break iterator. 
287      *
288      * @param fillInArray an array to be filled in with the status values.  
289      * @return          The number of rule status values from rules that determined 
290      *                  the most recent boundary returned by the break iterator.
291      *                  In the event that the array is too small, the return value
292      *                  is the total number of status values that were available,
293      *                  not the reduced number that were actually returned.
294      * @draft ICU 3.0
295      * @provisional This API might change or be removed in a future release.
296      */
297     public int getRuleStatusVec(int[] fillInArray) {
298         if (fillInArray != null && fillInArray.length>=1) {  
299             fillInArray[0] = 0;
300         }
301         return 1;
302     }
303 
304 
305 
306     /**
307      * This is the implementation function for next().
308      * @internal
309      * @deprecated This API is ICU internal only.
310      */
311     protected int handleNext() {
312         CharacterIterator   text = getText();
313 
314         // if there are no cached break positions, or if we've just moved
315         // off the end of the range covered by the cache, we have to dump
316         // and possibly regenerate the cache
317         if (cachedBreakPositions == null || positionInCache == cachedBreakPositions.length - 1) {
318 
319             // start by using the inherited handleNext() to find a tentative return
320             // value.   dictionaryCharCount tells us how many dictionary characters
321             // we passed over on our way to the tentative return value
322             int startPos = text.getIndex();
323             fDictionaryCharCount = 0;
324             int result = super.handleNext();
325 
326             // if we passed over more than one dictionary character, then we use
327             // divideUpDictionaryRange() to regenerate the cached break positions
328             // for the new range
329             if (fDictionaryCharCount > 1 && result - startPos > 1) {
330                 divideUpDictionaryRange(startPos, result);
331             }
332 
333             // otherwise, the value we got back from the inherited fuction
334             // is our return value, and we can dump the cache
335             else {
336                 cachedBreakPositions = null;
337                 return result;
338             }
339         }
340 
341         // if the cache of break positions has been regenerated (or existed all
342         // along), then just advance to the next break position in the cache
343         // and return it
344         if (cachedBreakPositions != null) {
345             ++positionInCache;
346             text.setIndex(cachedBreakPositions[positionInCache]);
347             return cachedBreakPositions[positionInCache];
348         }
349         Assert.assrt(false);
350         return -9999;   // SHOULD NEVER GET HERE!
351     }
352 
353     /**
354      * This is the function that actually implements the dictionary-based
355      * algorithm.  Given the endpoints of a range of text, it uses the
356      * dictionary to determine the positions of any boundaries in this
357      * range.  It stores all the boundary positions it discovers in
358      * cachedBreakPositions so that we only have to do this work once
359      * for each time we enter the range.
360      */
361     private void divideUpDictionaryRange(int startPos, int endPos) {
362         CharacterIterator   text = getText();
363 
364         // the range we're dividing may begin or end with non-dictionary characters
365         // (i.e., for line breaking, we may have leading or trailing punctuation
366         // that needs to be kept with the word).  Seek from the beginning of the
367         // range to the first dictionary character
368         text.setIndex(startPos);
369         int c = CICurrent32(text);
370         while (isDictionaryChar(c) == false) {  
371             c = CINext32(text);
372         }
373         
374         //System.out.println("\nDividing up range from " + (text.getIndex() + 1) + " to " + endPos);
375 
376         // initialize.  We maintain two stacks: currentBreakPositions contains
377         // the list of break positions that will be returned if we successfully
378         // finish traversing the whole range now.  possibleBreakPositions lists
379         // all other possible word ends we've passed along the way.  (Whenever
380         // we reach an error [a sequence of characters that can't begin any word
381         // in the dictionary], we back up, possibly delete some breaks from
382         // currentBreakPositions, move a break from possibleBreakPositions
383         // to currentBreakPositions, and start over from there.  This process
384         // continues in this way until we either successfully make it all the way
385         // across the range, or exhaust all of our combinations of break
386         // positions.)
387         Stack   currentBreakPositions = new Stack  ();
388         Stack   possibleBreakPositions = new Stack  ();
389         Vector   wrongBreakPositions = new Vector  ();
390 
391         // the dictionary is implemented as a trie, which is treated as a state
392         // machine.  -1 represents the end of a legal word.  Every word in the
393         // dictionary is represented by a path from the root node to -1.  A path
394         // that ends in state 0 is an illegal combination of characters.
395         int state = 0;
396 
397         // these two variables are used for error handling.  We keep track of the
398         // farthest we've gotten through the range being divided, and the combination
399         // of breaks that got us that far.  If we use up all possible break
400         // combinations, the text contains an error or a word that's not in the
401         // dictionary.  In this case, we "bless" the break positions that got us the
402         // farthest as real break positions, and then start over from scratch with
403         // the character where the error occurred.
404         int farthestEndPoint = text.getIndex();
405         Stack   bestBreakPositions = null;
406 
407         // initialize (we always exit the loop with a break statement)
408         c = CICurrent32(text);
409         while (true) {
410 //System.out.print("c = " + Integer.toString(c, 16) + ", pos = " + text.getIndex());
411 
412             // if we can transition to state "-1" from our current state, we're
413             // on the last character of a legal word.  Push that position onto
414             // the possible-break-positions stack
415             if (dictionary.at(state, 0) == -1) {
416                 possibleBreakPositions.push(new Integer  (text.getIndex()));
417             }
418 
419             // look up the new state to transition to in the dictionary
420             //    There will be no supplementaries here because the Thai dictionary
421             //     does not include any.  This code is going away soon, not worth
422             //     fixing.
423             state = (dictionary.at(state, (char)c)) & 0xFFFF;  // TODO: fix supplementaries
424 //System.out.print(", state = " + state);
425 
426             // if the character we're sitting on causes us to transition to
427             // the "end of word" state, then it was a non-dictionary character
428             // and we've successfully traversed the whole range.  Drop out
429             // of the loop.
430             if (state == /*-1*/ 0xFFFF) {
431                 currentBreakPositions.push(new Integer  (text.getIndex()));
432                 break;
433             }
434 
435             // if the character we're sitting on causes us to transition to
436             // the error state, or if we've gone off the end of the range
437             // without transitioning to the "end of word" state, we've hit
438             // an error...
439             else if (state == 0 || text.getIndex() >= endPos) {
440 
441                 // if this is the farthest we've gotten, take note of it in
442                 // case there's an error in the text
443                 if (text.getIndex() > farthestEndPoint) {
444                     farthestEndPoint = text.getIndex();
445                     bestBreakPositions = (Stack  )(currentBreakPositions.clone());
446                 }
447 
448                 // wrongBreakPositions is a list of all break positions we've tried starting
449                 // that didn't allow us to traverse all the way through the text.  Every time
450                 // we pop a break position off of currentBreakPositions, we put it into
451                 // wrongBreakPositions to avoid trying it again later.  If we make it to this
452                 // spot, we're either going to back up to a break in possibleBreakPositions
453                 // and try starting over from there, or we've exhausted all possible break
454                 // positions and are going to do the fallback procedure.  This loop prevents
455                 // us from messing with anything in possibleBreakPositions that didn't work as
456                 // a starting point the last time we tried it (this is to prevent a bunch of
457                 // repetitive checks from slowing down some extreme cases)
458                 // variable not used Integer newStartingSpot = null;
459                 while (!possibleBreakPositions.isEmpty() && wrongBreakPositions.contains(
460                             possibleBreakPositions.peek())) {
461                     possibleBreakPositions.pop();
462                 }
463 
464                 // if we've used up all possible break-position combinations, there's
465                 // an error or an unknown word in the text.  In this case, we start
466                 // over, treating the farthest character we've reached as the beginning
467                 // of the range, and "blessing" the break positions that got us that
468                 // far as real break positions
469                 if (possibleBreakPositions.isEmpty()) {
470                     if (bestBreakPositions != null) {
471                         currentBreakPositions = bestBreakPositions;
472                         if (farthestEndPoint < endPos) {
473                             text.setIndex(farthestEndPoint + 1);
474                         }
475                         else {
476                             break;
477                         }
478                     }
479                     else {
480                         if ((currentBreakPositions.size() == 0
481                                 || ((Integer  )(currentBreakPositions.peek())).intValue() != text.getIndex())
482                                 && text.getIndex() != startPos) {
483                             currentBreakPositions.push(new Integer  (text.getIndex()));
484                         }
485                         CINext32(text);
486                         currentBreakPositions.push(new Integer  (text.getIndex()));
487                     }
488                 }
489 
490                 // if we still have more break positions we can try, then promote the
491                 // last break in possibleBreakPositions into currentBreakPositions,
492                 // and get rid of all entries in currentBreakPositions that come after
493                 // it.  Then back up to that position and start over from there (i.e.,
494                 // treat that position as the beginning of a new word)
495                 else {
496                     Integer   temp = (Integer  )possibleBreakPositions.pop();
497                     Object   temp2 = null;
498                     while (!currentBreakPositions.isEmpty() && temp.intValue() <
499                            ((Integer  )currentBreakPositions.peek()).intValue()) {
500                         temp2 = currentBreakPositions.pop();
501                         wrongBreakPositions.addElement(temp2);
502                     }
503                     currentBreakPositions.push(temp);
504                     text.setIndex(((Integer  )currentBreakPositions.peek()).intValue());
505                 }
506 
507                 // re-sync "c" for the next go-round, and drop out of the loop if
508                 // we've made it off the end of the range
509                 c = CICurrent32(text);
510                 state = 0;
511                 if (text.getIndex() >= endPos) {
512                     break;
513                 }
514             }
515 
516             // if we didn't hit any exceptional conditions on this last iteration,
517             // just advance to the next character and loop
518             else {
519                 c = CINext32(text);
520             }
521 //System.out.print(", possibleBreakPositions = { "); for (int i = 0; i < possibleBreakPositions.size(); i++) System.out.print(possibleBreakPositions.elementAt(i) + " "); System.out.print("}");
522 //System.out.print(", currentBreakPositions = { "); for (int i = 0; i < currentBreakPositions.size(); i++) System.out.print(currentBreakPositions.elementAt(i) + " "); System.out.println("}");
523         }
524 
525         // dump the last break position in the list, and replace it with the actual
526         // end of the range (which may be the same character, or may be further on
527         // because the range actually ended with non-dictionary characters we want to
528         // keep with the word)
529         if (!currentBreakPositions.isEmpty()) {
530             currentBreakPositions.pop();
531         }
532         currentBreakPositions.push(new Integer  (endPos));
533 
534         // create a regular array to hold the break positions and copy
535         // the break positions from the stack to the array (in addition,
536         // our starting position goes into this array as a break position).
537         // This array becomes the cache of break positions used by next()
538         // and previous(), so this is where we actually refresh the cache.
539         cachedBreakPositions = new int[currentBreakPositions.size() + 1];
540         cachedBreakPositions[0] = startPos;
541 
542         for (int i = 0; i < currentBreakPositions.size(); i++) {
543             cachedBreakPositions[i + 1] = ((Integer  )currentBreakPositions.elementAt(i)).intValue();
544         }
545         positionInCache = 0;
546     }
547 }
548
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags