The Tor Browser / file comparison

comparison: intl/icu/source/common/dictbe.cpp

intl/icu/source/common/dictbe.cpp

branch
TOR_BUG_9701
changeset 15
b8a032363ba2
equal deleted inserted replaced
-1:000000000000 0:550a64365968
1 /**
2 *******************************************************************************
3 * Copyright (C) 2006-2013, International Business Machines Corporation
4 * and others. All Rights Reserved.
5 *******************************************************************************
6 */
7
8 #include "unicode/utypes.h"
9
10 #if !UCONFIG_NO_BREAK_ITERATION
11
12 #include "brkeng.h"
13 #include "dictbe.h"
14 #include "unicode/uniset.h"
15 #include "unicode/chariter.h"
16 #include "unicode/ubrk.h"
17 #include "uvector.h"
18 #include "uassert.h"
19 #include "unicode/normlzr.h"
20 #include "cmemory.h"
21 #include "dictionarydata.h"
22
23 U_NAMESPACE_BEGIN
24
25 /*
26 ******************************************************************
27 */
28
29 DictionaryBreakEngine::DictionaryBreakEngine(uint32_t breakTypes) {
30 fTypes = breakTypes;
31 }
32
33 DictionaryBreakEngine::~DictionaryBreakEngine() {
34 }
35
36 UBool
37 DictionaryBreakEngine::handles(UChar32 c, int32_t breakType) const {
38 return (breakType >= 0 && breakType < 32 && (((uint32_t)1 << breakType) & fTypes)
39 && fSet.contains(c));
40 }
41
42 int32_t
43 DictionaryBreakEngine::findBreaks( UText *text,
44 int32_t startPos,
45 int32_t endPos,
46 UBool reverse,
47 int32_t breakType,
48 UStack &foundBreaks ) const {
49 int32_t result = 0;
50
51 // Find the span of characters included in the set.
52 int32_t start = (int32_t)utext_getNativeIndex(text);
53 int32_t current;
54 int32_t rangeStart;
55 int32_t rangeEnd;
56 UChar32 c = utext_current32(text);
57 if (reverse) {
58 UBool isDict = fSet.contains(c);
59 while((current = (int32_t)utext_getNativeIndex(text)) > startPos && isDict) {
60 c = utext_previous32(text);
61 isDict = fSet.contains(c);
62 }
63 rangeStart = (current < startPos) ? startPos : current+(isDict ? 0 : 1);
64 rangeEnd = start + 1;
65 }
66 else {
67 while((current = (int32_t)utext_getNativeIndex(text)) < endPos && fSet.contains(c)) {
68 utext_next32(text); // TODO: recast loop for postincrement
69 c = utext_current32(text);
70 }
71 rangeStart = start;
72 rangeEnd = current;
73 }
74 if (breakType >= 0 && breakType < 32 && (((uint32_t)1 << breakType) & fTypes)) {
75 result = divideUpDictionaryRange(text, rangeStart, rangeEnd, foundBreaks);
76 utext_setNativeIndex(text, current);
77 }
78
79 return result;
80 }
81
82 void
83 DictionaryBreakEngine::setCharacters( const UnicodeSet &set ) {
84 fSet = set;
85 // Compact for caching
86 fSet.compact();
87 }
88
89 /*
90 ******************************************************************
91 * PossibleWord
92 */
93
94 // Helper class for improving readability of the Thai/Lao/Khmer word break
95 // algorithm. The implementation is completely inline.
96
97 // List size, limited by the maximum number of words in the dictionary
98 // that form a nested sequence.
99 #define POSSIBLE_WORD_LIST_MAX 20
100
101 class PossibleWord {
102 private:
103 // list of word candidate lengths, in increasing length order
104 int32_t lengths[POSSIBLE_WORD_LIST_MAX];
105 int32_t count; // Count of candidates
106 int32_t prefix; // The longest match with a dictionary word
107 int32_t offset; // Offset in the text of these candidates
108 int mark; // The preferred candidate's offset
109 int current; // The candidate we're currently looking at
110
111 public:
112 PossibleWord();
113 ~PossibleWord();
114
115 // Fill the list of candidates if needed, select the longest, and return the number found
116 int candidates( UText *text, DictionaryMatcher *dict, int32_t rangeEnd );
117
118 // Select the currently marked candidate, point after it in the text, and invalidate self
119 int32_t acceptMarked( UText *text );
120
121 // Back up from the current candidate to the next shorter one; return TRUE if that exists
122 // and point the text after it
123 UBool backUp( UText *text );
124
125 // Return the longest prefix this candidate location shares with a dictionary word
126 int32_t longestPrefix();
127
128 // Mark the current candidate as the one we like
129 void markCurrent();
130 };
131
132 inline
133 PossibleWord::PossibleWord() {
134 offset = -1;
135 }
136
137 inline
138 PossibleWord::~PossibleWord() {
139 }
140
141 inline int
142 PossibleWord::candidates( UText *text, DictionaryMatcher *dict, int32_t rangeEnd ) {
143 // TODO: If getIndex is too slow, use offset < 0 and add discardAll()
144 int32_t start = (int32_t)utext_getNativeIndex(text);
145 if (start != offset) {
146 offset = start;
147 prefix = dict->matches(text, rangeEnd-start, lengths, count, sizeof(lengths)/sizeof(lengths[0]));
148 // Dictionary leaves text after longest prefix, not longest word. Back up.
149 if (count <= 0) {
150 utext_setNativeIndex(text, start);
151 }
152 }
153 if (count > 0) {
154 utext_setNativeIndex(text, start+lengths[count-1]);
155 }
156 current = count-1;
157 mark = current;
158 return count;
159 }
160
161 inline int32_t
162 PossibleWord::acceptMarked( UText *text ) {
163 utext_setNativeIndex(text, offset + lengths[mark]);
164 return lengths[mark];
165 }
166
167 inline UBool
168 PossibleWord::backUp( UText *text ) {
169 if (current > 0) {
170 utext_setNativeIndex(text, offset + lengths[--current]);
171 return TRUE;
172 }
173 return FALSE;
174 }
175
176 inline int32_t
177 PossibleWord::longestPrefix() {
178 return prefix;
179 }
180
181 inline void
182 PossibleWord::markCurrent() {
183 mark = current;
184 }
185
186 /*
187 ******************************************************************
188 * ThaiBreakEngine
189 */
190
191 // How many words in a row are "good enough"?
192 #define THAI_LOOKAHEAD 3
193
194 // Will not combine a non-word with a preceding dictionary word longer than this
195 #define THAI_ROOT_COMBINE_THRESHOLD 3
196
197 // Will not combine a non-word that shares at least this much prefix with a
198 // dictionary word, with a preceding word
199 #define THAI_PREFIX_COMBINE_THRESHOLD 3
200
201 // Ellision character
202 #define THAI_PAIYANNOI 0x0E2F
203
204 // Repeat character
205 #define THAI_MAIYAMOK 0x0E46
206
207 // Minimum word size
208 #define THAI_MIN_WORD 2
209
210 // Minimum number of characters for two words
211 #define THAI_MIN_WORD_SPAN (THAI_MIN_WORD * 2)
212
213 ThaiBreakEngine::ThaiBreakEngine(DictionaryMatcher *adoptDictionary, UErrorCode &status)
214 : DictionaryBreakEngine((1<<UBRK_WORD) | (1<<UBRK_LINE)),
215 fDictionary(adoptDictionary)
216 {
217 fThaiWordSet.applyPattern(UNICODE_STRING_SIMPLE("[[:Thai:]&[:LineBreak=SA:]]"), status);
218 if (U_SUCCESS(status)) {
219 setCharacters(fThaiWordSet);
220 }
221 fMarkSet.applyPattern(UNICODE_STRING_SIMPLE("[[:Thai:]&[:LineBreak=SA:]&[:M:]]"), status);
222 fMarkSet.add(0x0020);
223 fEndWordSet = fThaiWordSet;
224 fEndWordSet.remove(0x0E31); // MAI HAN-AKAT
225 fEndWordSet.remove(0x0E40, 0x0E44); // SARA E through SARA AI MAIMALAI
226 fBeginWordSet.add(0x0E01, 0x0E2E); // KO KAI through HO NOKHUK
227 fBeginWordSet.add(0x0E40, 0x0E44); // SARA E through SARA AI MAIMALAI
228 fSuffixSet.add(THAI_PAIYANNOI);
229 fSuffixSet.add(THAI_MAIYAMOK);
230
231 // Compact for caching.
232 fMarkSet.compact();
233 fEndWordSet.compact();
234 fBeginWordSet.compact();
235 fSuffixSet.compact();
236 }
237
238 ThaiBreakEngine::~ThaiBreakEngine() {
239 delete fDictionary;
240 }
241
242 int32_t
243 ThaiBreakEngine::divideUpDictionaryRange( UText *text,
244 int32_t rangeStart,
245 int32_t rangeEnd,
246 UStack &foundBreaks ) const {
247 if ((rangeEnd - rangeStart) < THAI_MIN_WORD_SPAN) {
248 return 0; // Not enough characters for two words
249 }
250
251 uint32_t wordsFound = 0;
252 int32_t wordLength;
253 int32_t current;
254 UErrorCode status = U_ZERO_ERROR;
255 PossibleWord words[THAI_LOOKAHEAD];
256 UChar32 uc;
257
258 utext_setNativeIndex(text, rangeStart);
259
260 while (U_SUCCESS(status) && (current = (int32_t)utext_getNativeIndex(text)) < rangeEnd) {
261 wordLength = 0;
262
263 // Look for candidate words at the current position
264 int candidates = words[wordsFound%THAI_LOOKAHEAD].candidates(text, fDictionary, rangeEnd);
265
266 // If we found exactly one, use that
267 if (candidates == 1) {
268 wordLength = words[wordsFound % THAI_LOOKAHEAD].acceptMarked(text);
269 wordsFound += 1;
270 }
271 // If there was more than one, see which one can take us forward the most words
272 else if (candidates > 1) {
273 // If we're already at the end of the range, we're done
274 if ((int32_t)utext_getNativeIndex(text) >= rangeEnd) {
275 goto foundBest;
276 }
277 do {
278 int wordsMatched = 1;
279 if (words[(wordsFound + 1) % THAI_LOOKAHEAD].candidates(text, fDictionary, rangeEnd) > 0) {
280 if (wordsMatched < 2) {
281 // Followed by another dictionary word; mark first word as a good candidate
282 words[wordsFound%THAI_LOOKAHEAD].markCurrent();
283 wordsMatched = 2;
284 }
285
286 // If we're already at the end of the range, we're done
287 if ((int32_t)utext_getNativeIndex(text) >= rangeEnd) {
288 goto foundBest;
289 }
290
291 // See if any of the possible second words is followed by a third word
292 do {
293 // If we find a third word, stop right away
294 if (words[(wordsFound + 2) % THAI_LOOKAHEAD].candidates(text, fDictionary, rangeEnd)) {
295 words[wordsFound % THAI_LOOKAHEAD].markCurrent();
296 goto foundBest;
297 }
298 }
299 while (words[(wordsFound + 1) % THAI_LOOKAHEAD].backUp(text));
300 }
301 }
302 while (words[wordsFound % THAI_LOOKAHEAD].backUp(text));
303 foundBest:
304 wordLength = words[wordsFound % THAI_LOOKAHEAD].acceptMarked(text);
305 wordsFound += 1;
306 }
307
308 // We come here after having either found a word or not. We look ahead to the
309 // next word. If it's not a dictionary word, we will combine it withe the word we
310 // just found (if there is one), but only if the preceding word does not exceed
311 // the threshold.
312 // The text iterator should now be positioned at the end of the word we found.
313 if ((int32_t)utext_getNativeIndex(text) < rangeEnd && wordLength < THAI_ROOT_COMBINE_THRESHOLD) {
314 // if it is a dictionary word, do nothing. If it isn't, then if there is
315 // no preceding word, or the non-word shares less than the minimum threshold
316 // of characters with a dictionary word, then scan to resynchronize
317 if (words[wordsFound % THAI_LOOKAHEAD].candidates(text, fDictionary, rangeEnd) <= 0
318 && (wordLength == 0
319 || words[wordsFound%THAI_LOOKAHEAD].longestPrefix() < THAI_PREFIX_COMBINE_THRESHOLD)) {
320 // Look for a plausible word boundary
321 //TODO: This section will need a rework for UText.
322 int32_t remaining = rangeEnd - (current+wordLength);
323 UChar32 pc = utext_current32(text);
324 int32_t chars = 0;
325 for (;;) {
326 utext_next32(text);
327 uc = utext_current32(text);
328 // TODO: Here we're counting on the fact that the SA languages are all
329 // in the BMP. This should get fixed with the UText rework.
330 chars += 1;
331 if (--remaining <= 0) {
332 break;
333 }
334 if (fEndWordSet.contains(pc) && fBeginWordSet.contains(uc)) {
335 // Maybe. See if it's in the dictionary.
336 // NOTE: In the original Apple code, checked that the next
337 // two characters after uc were not 0x0E4C THANTHAKHAT before
338 // checking the dictionary. That is just a performance filter,
339 // but it's not clear it's faster than checking the trie.
340 int candidates = words[(wordsFound + 1) % THAI_LOOKAHEAD].candidates(text, fDictionary, rangeEnd);
341 utext_setNativeIndex(text, current + wordLength + chars);
342 if (candidates > 0) {
343 break;
344 }
345 }
346 pc = uc;
347 }
348
349 // Bump the word count if there wasn't already one
350 if (wordLength <= 0) {
351 wordsFound += 1;
352 }
353
354 // Update the length with the passed-over characters
355 wordLength += chars;
356 }
357 else {
358 // Back up to where we were for next iteration
359 utext_setNativeIndex(text, current+wordLength);
360 }
361 }
362
363 // Never stop before a combining mark.
364 int32_t currPos;
365 while ((currPos = (int32_t)utext_getNativeIndex(text)) < rangeEnd && fMarkSet.contains(utext_current32(text))) {
366 utext_next32(text);
367 wordLength += (int32_t)utext_getNativeIndex(text) - currPos;
368 }
369
370 // Look ahead for possible suffixes if a dictionary word does not follow.
371 // We do this in code rather than using a rule so that the heuristic
372 // resynch continues to function. For example, one of the suffix characters
373 // could be a typo in the middle of a word.
374 if ((int32_t)utext_getNativeIndex(text) < rangeEnd && wordLength > 0) {
375 if (words[wordsFound%THAI_LOOKAHEAD].candidates(text, fDictionary, rangeEnd) <= 0
376 && fSuffixSet.contains(uc = utext_current32(text))) {
377 if (uc == THAI_PAIYANNOI) {
378 if (!fSuffixSet.contains(utext_previous32(text))) {
379 // Skip over previous end and PAIYANNOI
380 utext_next32(text);
381 utext_next32(text);
382 wordLength += 1; // Add PAIYANNOI to word
383 uc = utext_current32(text); // Fetch next character
384 }
385 else {
386 // Restore prior position
387 utext_next32(text);
388 }
389 }
390 if (uc == THAI_MAIYAMOK) {
391 if (utext_previous32(text) != THAI_MAIYAMOK) {
392 // Skip over previous end and MAIYAMOK
393 utext_next32(text);
394 utext_next32(text);
395 wordLength += 1; // Add MAIYAMOK to word
396 }
397 else {
398 // Restore prior position
399 utext_next32(text);
400 }
401 }
402 }
403 else {
404 utext_setNativeIndex(text, current+wordLength);
405 }
406 }
407
408 // Did we find a word on this iteration? If so, push it on the break stack
409 if (wordLength > 0) {
410 foundBreaks.push((current+wordLength), status);
411 }
412 }
413
414 // Don't return a break for the end of the dictionary range if there is one there.
415 if (foundBreaks.peeki() >= rangeEnd) {
416 (void) foundBreaks.popi();
417 wordsFound -= 1;
418 }
419
420 return wordsFound;
421 }
422
423 /*
424 ******************************************************************
425 * LaoBreakEngine
426 */
427
428 // How many words in a row are "good enough"?
429 #define LAO_LOOKAHEAD 3
430
431 // Will not combine a non-word with a preceding dictionary word longer than this
432 #define LAO_ROOT_COMBINE_THRESHOLD 3
433
434 // Will not combine a non-word that shares at least this much prefix with a
435 // dictionary word, with a preceding word
436 #define LAO_PREFIX_COMBINE_THRESHOLD 3
437
438 // Minimum word size
439 #define LAO_MIN_WORD 2
440
441 // Minimum number of characters for two words
442 #define LAO_MIN_WORD_SPAN (LAO_MIN_WORD * 2)
443
444 LaoBreakEngine::LaoBreakEngine(DictionaryMatcher *adoptDictionary, UErrorCode &status)
445 : DictionaryBreakEngine((1<<UBRK_WORD) | (1<<UBRK_LINE)),
446 fDictionary(adoptDictionary)
447 {
448 fLaoWordSet.applyPattern(UNICODE_STRING_SIMPLE("[[:Laoo:]&[:LineBreak=SA:]]"), status);
449 if (U_SUCCESS(status)) {
450 setCharacters(fLaoWordSet);
451 }
452 fMarkSet.applyPattern(UNICODE_STRING_SIMPLE("[[:Laoo:]&[:LineBreak=SA:]&[:M:]]"), status);
453 fMarkSet.add(0x0020);
454 fEndWordSet = fLaoWordSet;
455 fEndWordSet.remove(0x0EC0, 0x0EC4); // prefix vowels
456 fBeginWordSet.add(0x0E81, 0x0EAE); // basic consonants (including holes for corresponding Thai characters)
457 fBeginWordSet.add(0x0EDC, 0x0EDD); // digraph consonants (no Thai equivalent)
458 fBeginWordSet.add(0x0EC0, 0x0EC4); // prefix vowels
459
460 // Compact for caching.
461 fMarkSet.compact();
462 fEndWordSet.compact();
463 fBeginWordSet.compact();
464 }
465
466 LaoBreakEngine::~LaoBreakEngine() {
467 delete fDictionary;
468 }
469
470 int32_t
471 LaoBreakEngine::divideUpDictionaryRange( UText *text,
472 int32_t rangeStart,
473 int32_t rangeEnd,
474 UStack &foundBreaks ) const {
475 if ((rangeEnd - rangeStart) < LAO_MIN_WORD_SPAN) {
476 return 0; // Not enough characters for two words
477 }
478
479 uint32_t wordsFound = 0;
480 int32_t wordLength;
481 int32_t current;
482 UErrorCode status = U_ZERO_ERROR;
483 PossibleWord words[LAO_LOOKAHEAD];
484 UChar32 uc;
485
486 utext_setNativeIndex(text, rangeStart);
487
488 while (U_SUCCESS(status) && (current = (int32_t)utext_getNativeIndex(text)) < rangeEnd) {
489 wordLength = 0;
490
491 // Look for candidate words at the current position
492 int candidates = words[wordsFound%LAO_LOOKAHEAD].candidates(text, fDictionary, rangeEnd);
493
494 // If we found exactly one, use that
495 if (candidates == 1) {
496 wordLength = words[wordsFound % LAO_LOOKAHEAD].acceptMarked(text);
497 wordsFound += 1;
498 }
499 // If there was more than one, see which one can take us forward the most words
500 else if (candidates > 1) {
501 // If we're already at the end of the range, we're done
502 if ((int32_t)utext_getNativeIndex(text) >= rangeEnd) {
503 goto foundBest;
504 }
505 do {
506 int wordsMatched = 1;
507 if (words[(wordsFound + 1) % LAO_LOOKAHEAD].candidates(text, fDictionary, rangeEnd) > 0) {
508 if (wordsMatched < 2) {
509 // Followed by another dictionary word; mark first word as a good candidate
510 words[wordsFound%LAO_LOOKAHEAD].markCurrent();
511 wordsMatched = 2;
512 }
513
514 // If we're already at the end of the range, we're done
515 if ((int32_t)utext_getNativeIndex(text) >= rangeEnd) {
516 goto foundBest;
517 }
518
519 // See if any of the possible second words is followed by a third word
520 do {
521 // If we find a third word, stop right away
522 if (words[(wordsFound + 2) % LAO_LOOKAHEAD].candidates(text, fDictionary, rangeEnd)) {
523 words[wordsFound % LAO_LOOKAHEAD].markCurrent();
524 goto foundBest;
525 }
526 }
527 while (words[(wordsFound + 1) % LAO_LOOKAHEAD].backUp(text));
528 }
529 }
530 while (words[wordsFound % LAO_LOOKAHEAD].backUp(text));
531 foundBest:
532 wordLength = words[wordsFound % LAO_LOOKAHEAD].acceptMarked(text);
533 wordsFound += 1;
534 }
535
536 // We come here after having either found a word or not. We look ahead to the
537 // next word. If it's not a dictionary word, we will combine it withe the word we
538 // just found (if there is one), but only if the preceding word does not exceed
539 // the threshold.
540 // The text iterator should now be positioned at the end of the word we found.
541 if ((int32_t)utext_getNativeIndex(text) < rangeEnd && wordLength < LAO_ROOT_COMBINE_THRESHOLD) {
542 // if it is a dictionary word, do nothing. If it isn't, then if there is
543 // no preceding word, or the non-word shares less than the minimum threshold
544 // of characters with a dictionary word, then scan to resynchronize
545 if (words[wordsFound % LAO_LOOKAHEAD].candidates(text, fDictionary, rangeEnd) <= 0
546 && (wordLength == 0
547 || words[wordsFound%LAO_LOOKAHEAD].longestPrefix() < LAO_PREFIX_COMBINE_THRESHOLD)) {
548 // Look for a plausible word boundary
549 //TODO: This section will need a rework for UText.
550 int32_t remaining = rangeEnd - (current+wordLength);
551 UChar32 pc = utext_current32(text);
552 int32_t chars = 0;
553 for (;;) {
554 utext_next32(text);
555 uc = utext_current32(text);
556 // TODO: Here we're counting on the fact that the SA languages are all
557 // in the BMP. This should get fixed with the UText rework.
558 chars += 1;
559 if (--remaining <= 0) {
560 break;
561 }
562 if (fEndWordSet.contains(pc) && fBeginWordSet.contains(uc)) {
563 // Maybe. See if it's in the dictionary.
564 int candidates = words[(wordsFound + 1) % LAO_LOOKAHEAD].candidates(text, fDictionary, rangeEnd);
565 utext_setNativeIndex(text, current + wordLength + chars);
566 if (candidates > 0) {
567 break;
568 }
569 }
570 pc = uc;
571 }
572
573 // Bump the word count if there wasn't already one
574 if (wordLength <= 0) {
575 wordsFound += 1;
576 }
577
578 // Update the length with the passed-over characters
579 wordLength += chars;
580 }
581 else {
582 // Back up to where we were for next iteration
583 utext_setNativeIndex(text, current+wordLength);
584 }
585 }
586
587 // Never stop before a combining mark.
588 int32_t currPos;
589 while ((currPos = (int32_t)utext_getNativeIndex(text)) < rangeEnd && fMarkSet.contains(utext_current32(text))) {
590 utext_next32(text);
591 wordLength += (int32_t)utext_getNativeIndex(text) - currPos;
592 }
593
594 // Look ahead for possible suffixes if a dictionary word does not follow.
595 // We do this in code rather than using a rule so that the heuristic
596 // resynch continues to function. For example, one of the suffix characters
597 // could be a typo in the middle of a word.
598 // NOT CURRENTLY APPLICABLE TO LAO
599
600 // Did we find a word on this iteration? If so, push it on the break stack
601 if (wordLength > 0) {
602 foundBreaks.push((current+wordLength), status);
603 }
604 }
605
606 // Don't return a break for the end of the dictionary range if there is one there.
607 if (foundBreaks.peeki() >= rangeEnd) {
608 (void) foundBreaks.popi();
609 wordsFound -= 1;
610 }
611
612 return wordsFound;
613 }
614
615 /*
616 ******************************************************************
617 * KhmerBreakEngine
618 */
619
620 // How many words in a row are "good enough"?
621 #define KHMER_LOOKAHEAD 3
622
623 // Will not combine a non-word with a preceding dictionary word longer than this
624 #define KHMER_ROOT_COMBINE_THRESHOLD 3
625
626 // Will not combine a non-word that shares at least this much prefix with a
627 // dictionary word, with a preceding word
628 #define KHMER_PREFIX_COMBINE_THRESHOLD 3
629
630 // Minimum word size
631 #define KHMER_MIN_WORD 2
632
633 // Minimum number of characters for two words
634 #define KHMER_MIN_WORD_SPAN (KHMER_MIN_WORD * 2)
635
636 KhmerBreakEngine::KhmerBreakEngine(DictionaryMatcher *adoptDictionary, UErrorCode &status)
637 : DictionaryBreakEngine((1 << UBRK_WORD) | (1 << UBRK_LINE)),
638 fDictionary(adoptDictionary)
639 {
640 fKhmerWordSet.applyPattern(UNICODE_STRING_SIMPLE("[[:Khmr:]&[:LineBreak=SA:]]"), status);
641 if (U_SUCCESS(status)) {
642 setCharacters(fKhmerWordSet);
643 }
644 fMarkSet.applyPattern(UNICODE_STRING_SIMPLE("[[:Khmr:]&[:LineBreak=SA:]&[:M:]]"), status);
645 fMarkSet.add(0x0020);
646 fEndWordSet = fKhmerWordSet;
647 fBeginWordSet.add(0x1780, 0x17B3);
648 //fBeginWordSet.add(0x17A3, 0x17A4); // deprecated vowels
649 //fEndWordSet.remove(0x17A5, 0x17A9); // Khmer independent vowels that can't end a word
650 //fEndWordSet.remove(0x17B2); // Khmer independent vowel that can't end a word
651 fEndWordSet.remove(0x17D2); // KHMER SIGN COENG that combines some following characters
652 //fEndWordSet.remove(0x17B6, 0x17C5); // Remove dependent vowels
653 // fEndWordSet.remove(0x0E31); // MAI HAN-AKAT
654 // fEndWordSet.remove(0x0E40, 0x0E44); // SARA E through SARA AI MAIMALAI
655 // fBeginWordSet.add(0x0E01, 0x0E2E); // KO KAI through HO NOKHUK
656 // fBeginWordSet.add(0x0E40, 0x0E44); // SARA E through SARA AI MAIMALAI
657 // fSuffixSet.add(THAI_PAIYANNOI);
658 // fSuffixSet.add(THAI_MAIYAMOK);
659
660 // Compact for caching.
661 fMarkSet.compact();
662 fEndWordSet.compact();
663 fBeginWordSet.compact();
664 // fSuffixSet.compact();
665 }
666
667 KhmerBreakEngine::~KhmerBreakEngine() {
668 delete fDictionary;
669 }
670
671 int32_t
672 KhmerBreakEngine::divideUpDictionaryRange( UText *text,
673 int32_t rangeStart,
674 int32_t rangeEnd,
675 UStack &foundBreaks ) const {
676 if ((rangeEnd - rangeStart) < KHMER_MIN_WORD_SPAN) {
677 return 0; // Not enough characters for two words
678 }
679
680 uint32_t wordsFound = 0;
681 int32_t wordLength;
682 int32_t current;
683 UErrorCode status = U_ZERO_ERROR;
684 PossibleWord words[KHMER_LOOKAHEAD];
685 UChar32 uc;
686
687 utext_setNativeIndex(text, rangeStart);
688
689 while (U_SUCCESS(status) && (current = (int32_t)utext_getNativeIndex(text)) < rangeEnd) {
690 wordLength = 0;
691
692 // Look for candidate words at the current position
693 int candidates = words[wordsFound%KHMER_LOOKAHEAD].candidates(text, fDictionary, rangeEnd);
694
695 // If we found exactly one, use that
696 if (candidates == 1) {
697 wordLength = words[wordsFound%KHMER_LOOKAHEAD].acceptMarked(text);
698 wordsFound += 1;
699 }
700
701 // If there was more than one, see which one can take us forward the most words
702 else if (candidates > 1) {
703 // If we're already at the end of the range, we're done
704 if ((int32_t)utext_getNativeIndex(text) >= rangeEnd) {
705 goto foundBest;
706 }
707 do {
708 int wordsMatched = 1;
709 if (words[(wordsFound + 1) % KHMER_LOOKAHEAD].candidates(text, fDictionary, rangeEnd) > 0) {
710 if (wordsMatched < 2) {
711 // Followed by another dictionary word; mark first word as a good candidate
712 words[wordsFound % KHMER_LOOKAHEAD].markCurrent();
713 wordsMatched = 2;
714 }
715
716 // If we're already at the end of the range, we're done
717 if ((int32_t)utext_getNativeIndex(text) >= rangeEnd) {
718 goto foundBest;
719 }
720
721 // See if any of the possible second words is followed by a third word
722 do {
723 // If we find a third word, stop right away
724 if (words[(wordsFound + 2) % KHMER_LOOKAHEAD].candidates(text, fDictionary, rangeEnd)) {
725 words[wordsFound % KHMER_LOOKAHEAD].markCurrent();
726 goto foundBest;
727 }
728 }
729 while (words[(wordsFound + 1) % KHMER_LOOKAHEAD].backUp(text));
730 }
731 }
732 while (words[wordsFound % KHMER_LOOKAHEAD].backUp(text));
733 foundBest:
734 wordLength = words[wordsFound % KHMER_LOOKAHEAD].acceptMarked(text);
735 wordsFound += 1;
736 }
737
738 // We come here after having either found a word or not. We look ahead to the
739 // next word. If it's not a dictionary word, we will combine it with the word we
740 // just found (if there is one), but only if the preceding word does not exceed
741 // the threshold.
742 // The text iterator should now be positioned at the end of the word we found.
743 if ((int32_t)utext_getNativeIndex(text) < rangeEnd && wordLength < KHMER_ROOT_COMBINE_THRESHOLD) {
744 // if it is a dictionary word, do nothing. If it isn't, then if there is
745 // no preceding word, or the non-word shares less than the minimum threshold
746 // of characters with a dictionary word, then scan to resynchronize
747 if (words[wordsFound % KHMER_LOOKAHEAD].candidates(text, fDictionary, rangeEnd) <= 0
748 && (wordLength == 0
749 || words[wordsFound % KHMER_LOOKAHEAD].longestPrefix() < KHMER_PREFIX_COMBINE_THRESHOLD)) {
750 // Look for a plausible word boundary
751 //TODO: This section will need a rework for UText.
752 int32_t remaining = rangeEnd - (current+wordLength);
753 UChar32 pc = utext_current32(text);
754 int32_t chars = 0;
755 for (;;) {
756 utext_next32(text);
757 uc = utext_current32(text);
758 // TODO: Here we're counting on the fact that the SA languages are all
759 // in the BMP. This should get fixed with the UText rework.
760 chars += 1;
761 if (--remaining <= 0) {
762 break;
763 }
764 if (fEndWordSet.contains(pc) && fBeginWordSet.contains(uc)) {
765 // Maybe. See if it's in the dictionary.
766 int candidates = words[(wordsFound + 1) % KHMER_LOOKAHEAD].candidates(text, fDictionary, rangeEnd);
767 utext_setNativeIndex(text, current+wordLength+chars);
768 if (candidates > 0) {
769 break;
770 }
771 }
772 pc = uc;
773 }
774
775 // Bump the word count if there wasn't already one
776 if (wordLength <= 0) {
777 wordsFound += 1;
778 }
779
780 // Update the length with the passed-over characters
781 wordLength += chars;
782 }
783 else {
784 // Back up to where we were for next iteration
785 utext_setNativeIndex(text, current+wordLength);
786 }
787 }
788
789 // Never stop before a combining mark.
790 int32_t currPos;
791 while ((currPos = (int32_t)utext_getNativeIndex(text)) < rangeEnd && fMarkSet.contains(utext_current32(text))) {
792 utext_next32(text);
793 wordLength += (int32_t)utext_getNativeIndex(text) - currPos;
794 }
795
796 // Look ahead for possible suffixes if a dictionary word does not follow.
797 // We do this in code rather than using a rule so that the heuristic
798 // resynch continues to function. For example, one of the suffix characters
799 // could be a typo in the middle of a word.
800 // if ((int32_t)utext_getNativeIndex(text) < rangeEnd && wordLength > 0) {
801 // if (words[wordsFound%KHMER_LOOKAHEAD].candidates(text, fDictionary, rangeEnd) <= 0
802 // && fSuffixSet.contains(uc = utext_current32(text))) {
803 // if (uc == KHMER_PAIYANNOI) {
804 // if (!fSuffixSet.contains(utext_previous32(text))) {
805 // // Skip over previous end and PAIYANNOI
806 // utext_next32(text);
807 // utext_next32(text);
808 // wordLength += 1; // Add PAIYANNOI to word
809 // uc = utext_current32(text); // Fetch next character
810 // }
811 // else {
812 // // Restore prior position
813 // utext_next32(text);
814 // }
815 // }
816 // if (uc == KHMER_MAIYAMOK) {
817 // if (utext_previous32(text) != KHMER_MAIYAMOK) {
818 // // Skip over previous end and MAIYAMOK
819 // utext_next32(text);
820 // utext_next32(text);
821 // wordLength += 1; // Add MAIYAMOK to word
822 // }
823 // else {
824 // // Restore prior position
825 // utext_next32(text);
826 // }
827 // }
828 // }
829 // else {
830 // utext_setNativeIndex(text, current+wordLength);
831 // }
832 // }
833
834 // Did we find a word on this iteration? If so, push it on the break stack
835 if (wordLength > 0) {
836 foundBreaks.push((current+wordLength), status);
837 }
838 }
839
840 // Don't return a break for the end of the dictionary range if there is one there.
841 if (foundBreaks.peeki() >= rangeEnd) {
842 (void) foundBreaks.popi();
843 wordsFound -= 1;
844 }
845
846 return wordsFound;
847 }
848
849 #if !UCONFIG_NO_NORMALIZATION
850 /*
851 ******************************************************************
852 * CjkBreakEngine
853 */
854 static const uint32_t kuint32max = 0xFFFFFFFF;
855 CjkBreakEngine::CjkBreakEngine(DictionaryMatcher *adoptDictionary, LanguageType type, UErrorCode &status)
856 : DictionaryBreakEngine(1 << UBRK_WORD), fDictionary(adoptDictionary) {
857 // Korean dictionary only includes Hangul syllables
858 fHangulWordSet.applyPattern(UNICODE_STRING_SIMPLE("[\\uac00-\\ud7a3]"), status);
859 fHanWordSet.applyPattern(UNICODE_STRING_SIMPLE("[:Han:]"), status);
860 fKatakanaWordSet.applyPattern(UNICODE_STRING_SIMPLE("[[:Katakana:]\\uff9e\\uff9f]"), status);
861 fHiraganaWordSet.applyPattern(UNICODE_STRING_SIMPLE("[:Hiragana:]"), status);
862
863 if (U_SUCCESS(status)) {
864 // handle Korean and Japanese/Chinese using different dictionaries
865 if (type == kKorean) {
866 setCharacters(fHangulWordSet);
867 } else { //Chinese and Japanese
868 UnicodeSet cjSet;
869 cjSet.addAll(fHanWordSet);
870 cjSet.addAll(fKatakanaWordSet);
871 cjSet.addAll(fHiraganaWordSet);
872 cjSet.add(0xFF70); // HALFWIDTH KATAKANA-HIRAGANA PROLONGED SOUND MARK
873 cjSet.add(0x30FC); // KATAKANA-HIRAGANA PROLONGED SOUND MARK
874 setCharacters(cjSet);
875 }
876 }
877 }
878
879 CjkBreakEngine::~CjkBreakEngine(){
880 delete fDictionary;
881 }
882
883 // The katakanaCost values below are based on the length frequencies of all
884 // katakana phrases in the dictionary
885 static const int kMaxKatakanaLength = 8;
886 static const int kMaxKatakanaGroupLength = 20;
887 static const uint32_t maxSnlp = 255;
888
889 static inline uint32_t getKatakanaCost(int wordLength){
890 //TODO: fill array with actual values from dictionary!
891 static const uint32_t katakanaCost[kMaxKatakanaLength + 1]
892 = {8192, 984, 408, 240, 204, 252, 300, 372, 480};
893 return (wordLength > kMaxKatakanaLength) ? 8192 : katakanaCost[wordLength];
894 }
895
896 static inline bool isKatakana(uint16_t value) {
897 return (value >= 0x30A1u && value <= 0x30FEu && value != 0x30FBu) ||
898 (value >= 0xFF66u && value <= 0xFF9fu);
899 }
900
901 // A very simple helper class to streamline the buffer handling in
902 // divideUpDictionaryRange.
903 template<class T, size_t N>
904 class AutoBuffer {
905 public:
906 AutoBuffer(size_t size) : buffer(stackBuffer), capacity(N) {
907 if (size > N) {
908 buffer = reinterpret_cast<T*>(uprv_malloc(sizeof(T)*size));
909 capacity = size;
910 }
911 }
912 ~AutoBuffer() {
913 if (buffer != stackBuffer)
914 uprv_free(buffer);
915 }
916
917 T* elems() {
918 return buffer;
919 }
920
921 const T& operator[] (size_t i) const {
922 return buffer[i];
923 }
924
925 T& operator[] (size_t i) {
926 return buffer[i];
927 }
928
929 // resize without copy
930 void resize(size_t size) {
931 if (size <= capacity)
932 return;
933 if (buffer != stackBuffer)
934 uprv_free(buffer);
935 buffer = reinterpret_cast<T*>(uprv_malloc(sizeof(T)*size));
936 capacity = size;
937 }
938
939 private:
940 T stackBuffer[N];
941 T* buffer;
942 AutoBuffer();
943 size_t capacity;
944 };
945
946
947 /*
948 * @param text A UText representing the text
949 * @param rangeStart The start of the range of dictionary characters
950 * @param rangeEnd The end of the range of dictionary characters
951 * @param foundBreaks Output of C array of int32_t break positions, or 0
952 * @return The number of breaks found
953 */
954 int32_t
955 CjkBreakEngine::divideUpDictionaryRange( UText *text,
956 int32_t rangeStart,
957 int32_t rangeEnd,
958 UStack &foundBreaks ) const {
959 if (rangeStart >= rangeEnd) {
960 return 0;
961 }
962
963 const size_t defaultInputLength = 80;
964 size_t inputLength = rangeEnd - rangeStart;
965 // TODO: Replace by UnicodeString.
966 AutoBuffer<UChar, defaultInputLength> charString(inputLength);
967
968 // Normalize the input string and put it in normalizedText.
969 // The map from the indices of the normalized input to the raw
970 // input is kept in charPositions.
971 UErrorCode status = U_ZERO_ERROR;
972 utext_extract(text, rangeStart, rangeEnd, charString.elems(), inputLength, &status);
973 if (U_FAILURE(status)) {
974 return 0;
975 }
976
977 UnicodeString inputString(charString.elems(), inputLength);
978 // TODO: Use Normalizer2.
979 UNormalizationMode norm_mode = UNORM_NFKC;
980 UBool isNormalized =
981 Normalizer::quickCheck(inputString, norm_mode, status) == UNORM_YES ||
982 Normalizer::isNormalized(inputString, norm_mode, status);
983
984 // TODO: Replace by UVector32.
985 AutoBuffer<int32_t, defaultInputLength> charPositions(inputLength + 1);
986 int numChars = 0;
987 UText normalizedText = UTEXT_INITIALIZER;
988 // Needs to be declared here because normalizedText holds onto its buffer.
989 UnicodeString normalizedString;
990 if (isNormalized) {
991 int32_t index = 0;
992 charPositions[0] = 0;
993 while(index < inputString.length()) {
994 index = inputString.moveIndex32(index, 1);
995 charPositions[++numChars] = index;
996 }
997 utext_openUnicodeString(&normalizedText, &inputString, &status);
998 }
999 else {
1000 Normalizer::normalize(inputString, norm_mode, 0, normalizedString, status);
1001 if (U_FAILURE(status)) {
1002 return 0;
1003 }
1004 charPositions.resize(normalizedString.length() + 1);
1005 Normalizer normalizer(charString.elems(), inputLength, norm_mode);
1006 int32_t index = 0;
1007 charPositions[0] = 0;
1008 while(index < normalizer.endIndex()){
1009 /* UChar32 uc = */ normalizer.next();
1010 charPositions[++numChars] = index = normalizer.getIndex();
1011 }
1012 utext_openUnicodeString(&normalizedText, &normalizedString, &status);
1013 }
1014
1015 if (U_FAILURE(status)) {
1016 return 0;
1017 }
1018
1019 // From this point on, all the indices refer to the indices of
1020 // the normalized input string.
1021
1022 // bestSnlp[i] is the snlp of the best segmentation of the first i
1023 // characters in the range to be matched.
1024 // TODO: Replace by UVector32.
1025 AutoBuffer<uint32_t, defaultInputLength> bestSnlp(numChars + 1);
1026 bestSnlp[0] = 0;
1027 for(int i = 1; i <= numChars; i++) {
1028 bestSnlp[i] = kuint32max;
1029 }
1030
1031 // prev[i] is the index of the last CJK character in the previous word in
1032 // the best segmentation of the first i characters.
1033 // TODO: Replace by UVector32.
1034 AutoBuffer<int, defaultInputLength> prev(numChars + 1);
1035 for(int i = 0; i <= numChars; i++){
1036 prev[i] = -1;
1037 }
1038
1039 const size_t maxWordSize = 20;
1040 // TODO: Replace both with UVector32.
1041 AutoBuffer<int32_t, maxWordSize> values(numChars);
1042 AutoBuffer<int32_t, maxWordSize> lengths(numChars);
1043
1044 // Dynamic programming to find the best segmentation.
1045 bool is_prev_katakana = false;
1046 for (int32_t i = 0; i < numChars; ++i) {
1047 //utext_setNativeIndex(text, rangeStart + i);
1048 utext_setNativeIndex(&normalizedText, i);
1049 if (bestSnlp[i] == kuint32max)
1050 continue;
1051
1052 int32_t count;
1053 // limit maximum word length matched to size of current substring
1054 int32_t maxSearchLength = (i + maxWordSize < (size_t) numChars)? maxWordSize : (numChars - i);
1055
1056 fDictionary->matches(&normalizedText, maxSearchLength, lengths.elems(), count, maxSearchLength, values.elems());
1057
1058 // if there are no single character matches found in the dictionary
1059 // starting with this charcter, treat character as a 1-character word
1060 // with the highest value possible, i.e. the least likely to occur.
1061 // Exclude Korean characters from this treatment, as they should be left
1062 // together by default.
1063 if((count == 0 || lengths[0] != 1) &&
1064 !fHangulWordSet.contains(utext_current32(&normalizedText))) {
1065 values[count] = maxSnlp;
1066 lengths[count++] = 1;
1067 }
1068
1069 for (int j = 0; j < count; j++) {
1070 uint32_t newSnlp = bestSnlp[i] + values[j];
1071 if (newSnlp < bestSnlp[lengths[j] + i]) {
1072 bestSnlp[lengths[j] + i] = newSnlp;
1073 prev[lengths[j] + i] = i;
1074 }
1075 }
1076
1077 // In Japanese,
1078 // Katakana word in single character is pretty rare. So we apply
1079 // the following heuristic to Katakana: any continuous run of Katakana
1080 // characters is considered a candidate word with a default cost
1081 // specified in the katakanaCost table according to its length.
1082 //utext_setNativeIndex(text, rangeStart + i);
1083 utext_setNativeIndex(&normalizedText, i);
1084 bool is_katakana = isKatakana(utext_current32(&normalizedText));
1085 if (!is_prev_katakana && is_katakana) {
1086 int j = i + 1;
1087 utext_next32(&normalizedText);
1088 // Find the end of the continuous run of Katakana characters
1089 while (j < numChars && (j - i) < kMaxKatakanaGroupLength &&
1090 isKatakana(utext_current32(&normalizedText))) {
1091 utext_next32(&normalizedText);
1092 ++j;
1093 }
1094 if ((j - i) < kMaxKatakanaGroupLength) {
1095 uint32_t newSnlp = bestSnlp[i] + getKatakanaCost(j - i);
1096 if (newSnlp < bestSnlp[j]) {
1097 bestSnlp[j] = newSnlp;
1098 prev[j] = i;
1099 }
1100 }
1101 }
1102 is_prev_katakana = is_katakana;
1103 }
1104
1105 // Start pushing the optimal offset index into t_boundary (t for tentative).
1106 // prev[numChars] is guaranteed to be meaningful.
1107 // We'll first push in the reverse order, i.e.,
1108 // t_boundary[0] = numChars, and afterwards do a swap.
1109 // TODO: Replace by UVector32.
1110 AutoBuffer<int, maxWordSize> t_boundary(numChars + 1);
1111
1112 int numBreaks = 0;
1113 // No segmentation found, set boundary to end of range
1114 if (bestSnlp[numChars] == kuint32max) {
1115 t_boundary[numBreaks++] = numChars;
1116 } else {
1117 for (int i = numChars; i > 0; i = prev[i]) {
1118 t_boundary[numBreaks++] = i;
1119 }
1120 U_ASSERT(prev[t_boundary[numBreaks - 1]] == 0);
1121 }
1122
1123 // Reverse offset index in t_boundary.
1124 // Don't add a break for the start of the dictionary range if there is one
1125 // there already.
1126 if (foundBreaks.size() == 0 || foundBreaks.peeki() < rangeStart) {
1127 t_boundary[numBreaks++] = 0;
1128 }
1129
1130 // Now that we're done, convert positions in t_bdry[] (indices in
1131 // the normalized input string) back to indices in the raw input string
1132 // while reversing t_bdry and pushing values to foundBreaks.
1133 for (int i = numBreaks-1; i >= 0; i--) {
1134 foundBreaks.push(charPositions[t_boundary[i]] + rangeStart, status);
1135 }
1136
1137 utext_close(&normalizedText);
1138 return numBreaks;
1139 }
1140 #endif
1141
1142 U_NAMESPACE_END
1143
1144 #endif /* #if !UCONFIG_NO_BREAK_ITERATION */
1145

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial