michael@0: /** michael@0: ******************************************************************************* michael@0: * Copyright (C) 2006-2013, International Business Machines Corporation michael@0: * and others. All Rights Reserved. michael@0: ******************************************************************************* michael@0: */ michael@0: michael@0: #include "unicode/utypes.h" michael@0: michael@0: #if !UCONFIG_NO_BREAK_ITERATION michael@0: michael@0: #include "brkeng.h" michael@0: #include "dictbe.h" michael@0: #include "unicode/uniset.h" michael@0: #include "unicode/chariter.h" michael@0: #include "unicode/ubrk.h" michael@0: #include "uvector.h" michael@0: #include "uassert.h" michael@0: #include "unicode/normlzr.h" michael@0: #include "cmemory.h" michael@0: #include "dictionarydata.h" michael@0: michael@0: U_NAMESPACE_BEGIN michael@0: michael@0: /* michael@0: ****************************************************************** michael@0: */ michael@0: michael@0: DictionaryBreakEngine::DictionaryBreakEngine(uint32_t breakTypes) { michael@0: fTypes = breakTypes; michael@0: } michael@0: michael@0: DictionaryBreakEngine::~DictionaryBreakEngine() { michael@0: } michael@0: michael@0: UBool michael@0: DictionaryBreakEngine::handles(UChar32 c, int32_t breakType) const { michael@0: return (breakType >= 0 && breakType < 32 && (((uint32_t)1 << breakType) & fTypes) michael@0: && fSet.contains(c)); michael@0: } michael@0: michael@0: int32_t michael@0: DictionaryBreakEngine::findBreaks( UText *text, michael@0: int32_t startPos, michael@0: int32_t endPos, michael@0: UBool reverse, michael@0: int32_t breakType, michael@0: UStack &foundBreaks ) const { michael@0: int32_t result = 0; michael@0: michael@0: // Find the span of characters included in the set. michael@0: int32_t start = (int32_t)utext_getNativeIndex(text); michael@0: int32_t current; michael@0: int32_t rangeStart; michael@0: int32_t rangeEnd; michael@0: UChar32 c = utext_current32(text); michael@0: if (reverse) { michael@0: UBool isDict = fSet.contains(c); michael@0: while((current = (int32_t)utext_getNativeIndex(text)) > startPos && isDict) { michael@0: c = utext_previous32(text); michael@0: isDict = fSet.contains(c); michael@0: } michael@0: rangeStart = (current < startPos) ? startPos : current+(isDict ? 0 : 1); michael@0: rangeEnd = start + 1; michael@0: } michael@0: else { michael@0: while((current = (int32_t)utext_getNativeIndex(text)) < endPos && fSet.contains(c)) { michael@0: utext_next32(text); // TODO: recast loop for postincrement michael@0: c = utext_current32(text); michael@0: } michael@0: rangeStart = start; michael@0: rangeEnd = current; michael@0: } michael@0: if (breakType >= 0 && breakType < 32 && (((uint32_t)1 << breakType) & fTypes)) { michael@0: result = divideUpDictionaryRange(text, rangeStart, rangeEnd, foundBreaks); michael@0: utext_setNativeIndex(text, current); michael@0: } michael@0: michael@0: return result; michael@0: } michael@0: michael@0: void michael@0: DictionaryBreakEngine::setCharacters( const UnicodeSet &set ) { michael@0: fSet = set; michael@0: // Compact for caching michael@0: fSet.compact(); michael@0: } michael@0: michael@0: /* michael@0: ****************************************************************** michael@0: * PossibleWord michael@0: */ michael@0: michael@0: // Helper class for improving readability of the Thai/Lao/Khmer word break michael@0: // algorithm. The implementation is completely inline. michael@0: michael@0: // List size, limited by the maximum number of words in the dictionary michael@0: // that form a nested sequence. michael@0: #define POSSIBLE_WORD_LIST_MAX 20 michael@0: michael@0: class PossibleWord { michael@0: private: michael@0: // list of word candidate lengths, in increasing length order michael@0: int32_t lengths[POSSIBLE_WORD_LIST_MAX]; michael@0: int32_t count; // Count of candidates michael@0: int32_t prefix; // The longest match with a dictionary word michael@0: int32_t offset; // Offset in the text of these candidates michael@0: int mark; // The preferred candidate's offset michael@0: int current; // The candidate we're currently looking at michael@0: michael@0: public: michael@0: PossibleWord(); michael@0: ~PossibleWord(); michael@0: michael@0: // Fill the list of candidates if needed, select the longest, and return the number found michael@0: int candidates( UText *text, DictionaryMatcher *dict, int32_t rangeEnd ); michael@0: michael@0: // Select the currently marked candidate, point after it in the text, and invalidate self michael@0: int32_t acceptMarked( UText *text ); michael@0: michael@0: // Back up from the current candidate to the next shorter one; return TRUE if that exists michael@0: // and point the text after it michael@0: UBool backUp( UText *text ); michael@0: michael@0: // Return the longest prefix this candidate location shares with a dictionary word michael@0: int32_t longestPrefix(); michael@0: michael@0: // Mark the current candidate as the one we like michael@0: void markCurrent(); michael@0: }; michael@0: michael@0: inline michael@0: PossibleWord::PossibleWord() { michael@0: offset = -1; michael@0: } michael@0: michael@0: inline michael@0: PossibleWord::~PossibleWord() { michael@0: } michael@0: michael@0: inline int michael@0: PossibleWord::candidates( UText *text, DictionaryMatcher *dict, int32_t rangeEnd ) { michael@0: // TODO: If getIndex is too slow, use offset < 0 and add discardAll() michael@0: int32_t start = (int32_t)utext_getNativeIndex(text); michael@0: if (start != offset) { michael@0: offset = start; michael@0: prefix = dict->matches(text, rangeEnd-start, lengths, count, sizeof(lengths)/sizeof(lengths[0])); michael@0: // Dictionary leaves text after longest prefix, not longest word. Back up. michael@0: if (count <= 0) { michael@0: utext_setNativeIndex(text, start); michael@0: } michael@0: } michael@0: if (count > 0) { michael@0: utext_setNativeIndex(text, start+lengths[count-1]); michael@0: } michael@0: current = count-1; michael@0: mark = current; michael@0: return count; michael@0: } michael@0: michael@0: inline int32_t michael@0: PossibleWord::acceptMarked( UText *text ) { michael@0: utext_setNativeIndex(text, offset + lengths[mark]); michael@0: return lengths[mark]; michael@0: } michael@0: michael@0: inline UBool michael@0: PossibleWord::backUp( UText *text ) { michael@0: if (current > 0) { michael@0: utext_setNativeIndex(text, offset + lengths[--current]); michael@0: return TRUE; michael@0: } michael@0: return FALSE; michael@0: } michael@0: michael@0: inline int32_t michael@0: PossibleWord::longestPrefix() { michael@0: return prefix; michael@0: } michael@0: michael@0: inline void michael@0: PossibleWord::markCurrent() { michael@0: mark = current; michael@0: } michael@0: michael@0: /* michael@0: ****************************************************************** michael@0: * ThaiBreakEngine michael@0: */ michael@0: michael@0: // How many words in a row are "good enough"? michael@0: #define THAI_LOOKAHEAD 3 michael@0: michael@0: // Will not combine a non-word with a preceding dictionary word longer than this michael@0: #define THAI_ROOT_COMBINE_THRESHOLD 3 michael@0: michael@0: // Will not combine a non-word that shares at least this much prefix with a michael@0: // dictionary word, with a preceding word michael@0: #define THAI_PREFIX_COMBINE_THRESHOLD 3 michael@0: michael@0: // Ellision character michael@0: #define THAI_PAIYANNOI 0x0E2F michael@0: michael@0: // Repeat character michael@0: #define THAI_MAIYAMOK 0x0E46 michael@0: michael@0: // Minimum word size michael@0: #define THAI_MIN_WORD 2 michael@0: michael@0: // Minimum number of characters for two words michael@0: #define THAI_MIN_WORD_SPAN (THAI_MIN_WORD * 2) michael@0: michael@0: ThaiBreakEngine::ThaiBreakEngine(DictionaryMatcher *adoptDictionary, UErrorCode &status) michael@0: : DictionaryBreakEngine((1< 1) { michael@0: // If we're already at the end of the range, we're done michael@0: if ((int32_t)utext_getNativeIndex(text) >= rangeEnd) { michael@0: goto foundBest; michael@0: } michael@0: do { michael@0: int wordsMatched = 1; michael@0: if (words[(wordsFound + 1) % THAI_LOOKAHEAD].candidates(text, fDictionary, rangeEnd) > 0) { michael@0: if (wordsMatched < 2) { michael@0: // Followed by another dictionary word; mark first word as a good candidate michael@0: words[wordsFound%THAI_LOOKAHEAD].markCurrent(); michael@0: wordsMatched = 2; michael@0: } michael@0: michael@0: // If we're already at the end of the range, we're done michael@0: if ((int32_t)utext_getNativeIndex(text) >= rangeEnd) { michael@0: goto foundBest; michael@0: } michael@0: michael@0: // See if any of the possible second words is followed by a third word michael@0: do { michael@0: // If we find a third word, stop right away michael@0: if (words[(wordsFound + 2) % THAI_LOOKAHEAD].candidates(text, fDictionary, rangeEnd)) { michael@0: words[wordsFound % THAI_LOOKAHEAD].markCurrent(); michael@0: goto foundBest; michael@0: } michael@0: } michael@0: while (words[(wordsFound + 1) % THAI_LOOKAHEAD].backUp(text)); michael@0: } michael@0: } michael@0: while (words[wordsFound % THAI_LOOKAHEAD].backUp(text)); michael@0: foundBest: michael@0: wordLength = words[wordsFound % THAI_LOOKAHEAD].acceptMarked(text); michael@0: wordsFound += 1; michael@0: } michael@0: michael@0: // We come here after having either found a word or not. We look ahead to the michael@0: // next word. If it's not a dictionary word, we will combine it withe the word we michael@0: // just found (if there is one), but only if the preceding word does not exceed michael@0: // the threshold. michael@0: // The text iterator should now be positioned at the end of the word we found. michael@0: if ((int32_t)utext_getNativeIndex(text) < rangeEnd && wordLength < THAI_ROOT_COMBINE_THRESHOLD) { michael@0: // if it is a dictionary word, do nothing. If it isn't, then if there is michael@0: // no preceding word, or the non-word shares less than the minimum threshold michael@0: // of characters with a dictionary word, then scan to resynchronize michael@0: if (words[wordsFound % THAI_LOOKAHEAD].candidates(text, fDictionary, rangeEnd) <= 0 michael@0: && (wordLength == 0 michael@0: || words[wordsFound%THAI_LOOKAHEAD].longestPrefix() < THAI_PREFIX_COMBINE_THRESHOLD)) { michael@0: // Look for a plausible word boundary michael@0: //TODO: This section will need a rework for UText. michael@0: int32_t remaining = rangeEnd - (current+wordLength); michael@0: UChar32 pc = utext_current32(text); michael@0: int32_t chars = 0; michael@0: for (;;) { michael@0: utext_next32(text); michael@0: uc = utext_current32(text); michael@0: // TODO: Here we're counting on the fact that the SA languages are all michael@0: // in the BMP. This should get fixed with the UText rework. michael@0: chars += 1; michael@0: if (--remaining <= 0) { michael@0: break; michael@0: } michael@0: if (fEndWordSet.contains(pc) && fBeginWordSet.contains(uc)) { michael@0: // Maybe. See if it's in the dictionary. michael@0: // NOTE: In the original Apple code, checked that the next michael@0: // two characters after uc were not 0x0E4C THANTHAKHAT before michael@0: // checking the dictionary. That is just a performance filter, michael@0: // but it's not clear it's faster than checking the trie. michael@0: int candidates = words[(wordsFound + 1) % THAI_LOOKAHEAD].candidates(text, fDictionary, rangeEnd); michael@0: utext_setNativeIndex(text, current + wordLength + chars); michael@0: if (candidates > 0) { michael@0: break; michael@0: } michael@0: } michael@0: pc = uc; michael@0: } michael@0: michael@0: // Bump the word count if there wasn't already one michael@0: if (wordLength <= 0) { michael@0: wordsFound += 1; michael@0: } michael@0: michael@0: // Update the length with the passed-over characters michael@0: wordLength += chars; michael@0: } michael@0: else { michael@0: // Back up to where we were for next iteration michael@0: utext_setNativeIndex(text, current+wordLength); michael@0: } michael@0: } michael@0: michael@0: // Never stop before a combining mark. michael@0: int32_t currPos; michael@0: while ((currPos = (int32_t)utext_getNativeIndex(text)) < rangeEnd && fMarkSet.contains(utext_current32(text))) { michael@0: utext_next32(text); michael@0: wordLength += (int32_t)utext_getNativeIndex(text) - currPos; michael@0: } michael@0: michael@0: // Look ahead for possible suffixes if a dictionary word does not follow. michael@0: // We do this in code rather than using a rule so that the heuristic michael@0: // resynch continues to function. For example, one of the suffix characters michael@0: // could be a typo in the middle of a word. michael@0: if ((int32_t)utext_getNativeIndex(text) < rangeEnd && wordLength > 0) { michael@0: if (words[wordsFound%THAI_LOOKAHEAD].candidates(text, fDictionary, rangeEnd) <= 0 michael@0: && fSuffixSet.contains(uc = utext_current32(text))) { michael@0: if (uc == THAI_PAIYANNOI) { michael@0: if (!fSuffixSet.contains(utext_previous32(text))) { michael@0: // Skip over previous end and PAIYANNOI michael@0: utext_next32(text); michael@0: utext_next32(text); michael@0: wordLength += 1; // Add PAIYANNOI to word michael@0: uc = utext_current32(text); // Fetch next character michael@0: } michael@0: else { michael@0: // Restore prior position michael@0: utext_next32(text); michael@0: } michael@0: } michael@0: if (uc == THAI_MAIYAMOK) { michael@0: if (utext_previous32(text) != THAI_MAIYAMOK) { michael@0: // Skip over previous end and MAIYAMOK michael@0: utext_next32(text); michael@0: utext_next32(text); michael@0: wordLength += 1; // Add MAIYAMOK to word michael@0: } michael@0: else { michael@0: // Restore prior position michael@0: utext_next32(text); michael@0: } michael@0: } michael@0: } michael@0: else { michael@0: utext_setNativeIndex(text, current+wordLength); michael@0: } michael@0: } michael@0: michael@0: // Did we find a word on this iteration? If so, push it on the break stack michael@0: if (wordLength > 0) { michael@0: foundBreaks.push((current+wordLength), status); michael@0: } michael@0: } michael@0: michael@0: // Don't return a break for the end of the dictionary range if there is one there. michael@0: if (foundBreaks.peeki() >= rangeEnd) { michael@0: (void) foundBreaks.popi(); michael@0: wordsFound -= 1; michael@0: } michael@0: michael@0: return wordsFound; michael@0: } michael@0: michael@0: /* michael@0: ****************************************************************** michael@0: * LaoBreakEngine michael@0: */ michael@0: michael@0: // How many words in a row are "good enough"? michael@0: #define LAO_LOOKAHEAD 3 michael@0: michael@0: // Will not combine a non-word with a preceding dictionary word longer than this michael@0: #define LAO_ROOT_COMBINE_THRESHOLD 3 michael@0: michael@0: // Will not combine a non-word that shares at least this much prefix with a michael@0: // dictionary word, with a preceding word michael@0: #define LAO_PREFIX_COMBINE_THRESHOLD 3 michael@0: michael@0: // Minimum word size michael@0: #define LAO_MIN_WORD 2 michael@0: michael@0: // Minimum number of characters for two words michael@0: #define LAO_MIN_WORD_SPAN (LAO_MIN_WORD * 2) michael@0: michael@0: LaoBreakEngine::LaoBreakEngine(DictionaryMatcher *adoptDictionary, UErrorCode &status) michael@0: : DictionaryBreakEngine((1< 1) { michael@0: // If we're already at the end of the range, we're done michael@0: if ((int32_t)utext_getNativeIndex(text) >= rangeEnd) { michael@0: goto foundBest; michael@0: } michael@0: do { michael@0: int wordsMatched = 1; michael@0: if (words[(wordsFound + 1) % LAO_LOOKAHEAD].candidates(text, fDictionary, rangeEnd) > 0) { michael@0: if (wordsMatched < 2) { michael@0: // Followed by another dictionary word; mark first word as a good candidate michael@0: words[wordsFound%LAO_LOOKAHEAD].markCurrent(); michael@0: wordsMatched = 2; michael@0: } michael@0: michael@0: // If we're already at the end of the range, we're done michael@0: if ((int32_t)utext_getNativeIndex(text) >= rangeEnd) { michael@0: goto foundBest; michael@0: } michael@0: michael@0: // See if any of the possible second words is followed by a third word michael@0: do { michael@0: // If we find a third word, stop right away michael@0: if (words[(wordsFound + 2) % LAO_LOOKAHEAD].candidates(text, fDictionary, rangeEnd)) { michael@0: words[wordsFound % LAO_LOOKAHEAD].markCurrent(); michael@0: goto foundBest; michael@0: } michael@0: } michael@0: while (words[(wordsFound + 1) % LAO_LOOKAHEAD].backUp(text)); michael@0: } michael@0: } michael@0: while (words[wordsFound % LAO_LOOKAHEAD].backUp(text)); michael@0: foundBest: michael@0: wordLength = words[wordsFound % LAO_LOOKAHEAD].acceptMarked(text); michael@0: wordsFound += 1; michael@0: } michael@0: michael@0: // We come here after having either found a word or not. We look ahead to the michael@0: // next word. If it's not a dictionary word, we will combine it withe the word we michael@0: // just found (if there is one), but only if the preceding word does not exceed michael@0: // the threshold. michael@0: // The text iterator should now be positioned at the end of the word we found. michael@0: if ((int32_t)utext_getNativeIndex(text) < rangeEnd && wordLength < LAO_ROOT_COMBINE_THRESHOLD) { michael@0: // if it is a dictionary word, do nothing. If it isn't, then if there is michael@0: // no preceding word, or the non-word shares less than the minimum threshold michael@0: // of characters with a dictionary word, then scan to resynchronize michael@0: if (words[wordsFound % LAO_LOOKAHEAD].candidates(text, fDictionary, rangeEnd) <= 0 michael@0: && (wordLength == 0 michael@0: || words[wordsFound%LAO_LOOKAHEAD].longestPrefix() < LAO_PREFIX_COMBINE_THRESHOLD)) { michael@0: // Look for a plausible word boundary michael@0: //TODO: This section will need a rework for UText. michael@0: int32_t remaining = rangeEnd - (current+wordLength); michael@0: UChar32 pc = utext_current32(text); michael@0: int32_t chars = 0; michael@0: for (;;) { michael@0: utext_next32(text); michael@0: uc = utext_current32(text); michael@0: // TODO: Here we're counting on the fact that the SA languages are all michael@0: // in the BMP. This should get fixed with the UText rework. michael@0: chars += 1; michael@0: if (--remaining <= 0) { michael@0: break; michael@0: } michael@0: if (fEndWordSet.contains(pc) && fBeginWordSet.contains(uc)) { michael@0: // Maybe. See if it's in the dictionary. michael@0: int candidates = words[(wordsFound + 1) % LAO_LOOKAHEAD].candidates(text, fDictionary, rangeEnd); michael@0: utext_setNativeIndex(text, current + wordLength + chars); michael@0: if (candidates > 0) { michael@0: break; michael@0: } michael@0: } michael@0: pc = uc; michael@0: } michael@0: michael@0: // Bump the word count if there wasn't already one michael@0: if (wordLength <= 0) { michael@0: wordsFound += 1; michael@0: } michael@0: michael@0: // Update the length with the passed-over characters michael@0: wordLength += chars; michael@0: } michael@0: else { michael@0: // Back up to where we were for next iteration michael@0: utext_setNativeIndex(text, current+wordLength); michael@0: } michael@0: } michael@0: michael@0: // Never stop before a combining mark. michael@0: int32_t currPos; michael@0: while ((currPos = (int32_t)utext_getNativeIndex(text)) < rangeEnd && fMarkSet.contains(utext_current32(text))) { michael@0: utext_next32(text); michael@0: wordLength += (int32_t)utext_getNativeIndex(text) - currPos; michael@0: } michael@0: michael@0: // Look ahead for possible suffixes if a dictionary word does not follow. michael@0: // We do this in code rather than using a rule so that the heuristic michael@0: // resynch continues to function. For example, one of the suffix characters michael@0: // could be a typo in the middle of a word. michael@0: // NOT CURRENTLY APPLICABLE TO LAO michael@0: michael@0: // Did we find a word on this iteration? If so, push it on the break stack michael@0: if (wordLength > 0) { michael@0: foundBreaks.push((current+wordLength), status); michael@0: } michael@0: } michael@0: michael@0: // Don't return a break for the end of the dictionary range if there is one there. michael@0: if (foundBreaks.peeki() >= rangeEnd) { michael@0: (void) foundBreaks.popi(); michael@0: wordsFound -= 1; michael@0: } michael@0: michael@0: return wordsFound; michael@0: } michael@0: michael@0: /* michael@0: ****************************************************************** michael@0: * KhmerBreakEngine michael@0: */ michael@0: michael@0: // How many words in a row are "good enough"? michael@0: #define KHMER_LOOKAHEAD 3 michael@0: michael@0: // Will not combine a non-word with a preceding dictionary word longer than this michael@0: #define KHMER_ROOT_COMBINE_THRESHOLD 3 michael@0: michael@0: // Will not combine a non-word that shares at least this much prefix with a michael@0: // dictionary word, with a preceding word michael@0: #define KHMER_PREFIX_COMBINE_THRESHOLD 3 michael@0: michael@0: // Minimum word size michael@0: #define KHMER_MIN_WORD 2 michael@0: michael@0: // Minimum number of characters for two words michael@0: #define KHMER_MIN_WORD_SPAN (KHMER_MIN_WORD * 2) michael@0: michael@0: KhmerBreakEngine::KhmerBreakEngine(DictionaryMatcher *adoptDictionary, UErrorCode &status) michael@0: : DictionaryBreakEngine((1 << UBRK_WORD) | (1 << UBRK_LINE)), michael@0: fDictionary(adoptDictionary) michael@0: { michael@0: fKhmerWordSet.applyPattern(UNICODE_STRING_SIMPLE("[[:Khmr:]&[:LineBreak=SA:]]"), status); michael@0: if (U_SUCCESS(status)) { michael@0: setCharacters(fKhmerWordSet); michael@0: } michael@0: fMarkSet.applyPattern(UNICODE_STRING_SIMPLE("[[:Khmr:]&[:LineBreak=SA:]&[:M:]]"), status); michael@0: fMarkSet.add(0x0020); michael@0: fEndWordSet = fKhmerWordSet; michael@0: fBeginWordSet.add(0x1780, 0x17B3); michael@0: //fBeginWordSet.add(0x17A3, 0x17A4); // deprecated vowels michael@0: //fEndWordSet.remove(0x17A5, 0x17A9); // Khmer independent vowels that can't end a word michael@0: //fEndWordSet.remove(0x17B2); // Khmer independent vowel that can't end a word michael@0: fEndWordSet.remove(0x17D2); // KHMER SIGN COENG that combines some following characters michael@0: //fEndWordSet.remove(0x17B6, 0x17C5); // Remove dependent vowels michael@0: // fEndWordSet.remove(0x0E31); // MAI HAN-AKAT michael@0: // fEndWordSet.remove(0x0E40, 0x0E44); // SARA E through SARA AI MAIMALAI michael@0: // fBeginWordSet.add(0x0E01, 0x0E2E); // KO KAI through HO NOKHUK michael@0: // fBeginWordSet.add(0x0E40, 0x0E44); // SARA E through SARA AI MAIMALAI michael@0: // fSuffixSet.add(THAI_PAIYANNOI); michael@0: // fSuffixSet.add(THAI_MAIYAMOK); michael@0: michael@0: // Compact for caching. michael@0: fMarkSet.compact(); michael@0: fEndWordSet.compact(); michael@0: fBeginWordSet.compact(); michael@0: // fSuffixSet.compact(); michael@0: } michael@0: michael@0: KhmerBreakEngine::~KhmerBreakEngine() { michael@0: delete fDictionary; michael@0: } michael@0: michael@0: int32_t michael@0: KhmerBreakEngine::divideUpDictionaryRange( UText *text, michael@0: int32_t rangeStart, michael@0: int32_t rangeEnd, michael@0: UStack &foundBreaks ) const { michael@0: if ((rangeEnd - rangeStart) < KHMER_MIN_WORD_SPAN) { michael@0: return 0; // Not enough characters for two words michael@0: } michael@0: michael@0: uint32_t wordsFound = 0; michael@0: int32_t wordLength; michael@0: int32_t current; michael@0: UErrorCode status = U_ZERO_ERROR; michael@0: PossibleWord words[KHMER_LOOKAHEAD]; michael@0: UChar32 uc; michael@0: michael@0: utext_setNativeIndex(text, rangeStart); michael@0: michael@0: while (U_SUCCESS(status) && (current = (int32_t)utext_getNativeIndex(text)) < rangeEnd) { michael@0: wordLength = 0; michael@0: michael@0: // Look for candidate words at the current position michael@0: int candidates = words[wordsFound%KHMER_LOOKAHEAD].candidates(text, fDictionary, rangeEnd); michael@0: michael@0: // If we found exactly one, use that michael@0: if (candidates == 1) { michael@0: wordLength = words[wordsFound%KHMER_LOOKAHEAD].acceptMarked(text); michael@0: wordsFound += 1; michael@0: } michael@0: michael@0: // If there was more than one, see which one can take us forward the most words michael@0: else if (candidates > 1) { michael@0: // If we're already at the end of the range, we're done michael@0: if ((int32_t)utext_getNativeIndex(text) >= rangeEnd) { michael@0: goto foundBest; michael@0: } michael@0: do { michael@0: int wordsMatched = 1; michael@0: if (words[(wordsFound + 1) % KHMER_LOOKAHEAD].candidates(text, fDictionary, rangeEnd) > 0) { michael@0: if (wordsMatched < 2) { michael@0: // Followed by another dictionary word; mark first word as a good candidate michael@0: words[wordsFound % KHMER_LOOKAHEAD].markCurrent(); michael@0: wordsMatched = 2; michael@0: } michael@0: michael@0: // If we're already at the end of the range, we're done michael@0: if ((int32_t)utext_getNativeIndex(text) >= rangeEnd) { michael@0: goto foundBest; michael@0: } michael@0: michael@0: // See if any of the possible second words is followed by a third word michael@0: do { michael@0: // If we find a third word, stop right away michael@0: if (words[(wordsFound + 2) % KHMER_LOOKAHEAD].candidates(text, fDictionary, rangeEnd)) { michael@0: words[wordsFound % KHMER_LOOKAHEAD].markCurrent(); michael@0: goto foundBest; michael@0: } michael@0: } michael@0: while (words[(wordsFound + 1) % KHMER_LOOKAHEAD].backUp(text)); michael@0: } michael@0: } michael@0: while (words[wordsFound % KHMER_LOOKAHEAD].backUp(text)); michael@0: foundBest: michael@0: wordLength = words[wordsFound % KHMER_LOOKAHEAD].acceptMarked(text); michael@0: wordsFound += 1; michael@0: } michael@0: michael@0: // We come here after having either found a word or not. We look ahead to the michael@0: // next word. If it's not a dictionary word, we will combine it with the word we michael@0: // just found (if there is one), but only if the preceding word does not exceed michael@0: // the threshold. michael@0: // The text iterator should now be positioned at the end of the word we found. michael@0: if ((int32_t)utext_getNativeIndex(text) < rangeEnd && wordLength < KHMER_ROOT_COMBINE_THRESHOLD) { michael@0: // if it is a dictionary word, do nothing. If it isn't, then if there is michael@0: // no preceding word, or the non-word shares less than the minimum threshold michael@0: // of characters with a dictionary word, then scan to resynchronize michael@0: if (words[wordsFound % KHMER_LOOKAHEAD].candidates(text, fDictionary, rangeEnd) <= 0 michael@0: && (wordLength == 0 michael@0: || words[wordsFound % KHMER_LOOKAHEAD].longestPrefix() < KHMER_PREFIX_COMBINE_THRESHOLD)) { michael@0: // Look for a plausible word boundary michael@0: //TODO: This section will need a rework for UText. michael@0: int32_t remaining = rangeEnd - (current+wordLength); michael@0: UChar32 pc = utext_current32(text); michael@0: int32_t chars = 0; michael@0: for (;;) { michael@0: utext_next32(text); michael@0: uc = utext_current32(text); michael@0: // TODO: Here we're counting on the fact that the SA languages are all michael@0: // in the BMP. This should get fixed with the UText rework. michael@0: chars += 1; michael@0: if (--remaining <= 0) { michael@0: break; michael@0: } michael@0: if (fEndWordSet.contains(pc) && fBeginWordSet.contains(uc)) { michael@0: // Maybe. See if it's in the dictionary. michael@0: int candidates = words[(wordsFound + 1) % KHMER_LOOKAHEAD].candidates(text, fDictionary, rangeEnd); michael@0: utext_setNativeIndex(text, current+wordLength+chars); michael@0: if (candidates > 0) { michael@0: break; michael@0: } michael@0: } michael@0: pc = uc; michael@0: } michael@0: michael@0: // Bump the word count if there wasn't already one michael@0: if (wordLength <= 0) { michael@0: wordsFound += 1; michael@0: } michael@0: michael@0: // Update the length with the passed-over characters michael@0: wordLength += chars; michael@0: } michael@0: else { michael@0: // Back up to where we were for next iteration michael@0: utext_setNativeIndex(text, current+wordLength); michael@0: } michael@0: } michael@0: michael@0: // Never stop before a combining mark. michael@0: int32_t currPos; michael@0: while ((currPos = (int32_t)utext_getNativeIndex(text)) < rangeEnd && fMarkSet.contains(utext_current32(text))) { michael@0: utext_next32(text); michael@0: wordLength += (int32_t)utext_getNativeIndex(text) - currPos; michael@0: } michael@0: michael@0: // Look ahead for possible suffixes if a dictionary word does not follow. michael@0: // We do this in code rather than using a rule so that the heuristic michael@0: // resynch continues to function. For example, one of the suffix characters michael@0: // could be a typo in the middle of a word. michael@0: // if ((int32_t)utext_getNativeIndex(text) < rangeEnd && wordLength > 0) { michael@0: // if (words[wordsFound%KHMER_LOOKAHEAD].candidates(text, fDictionary, rangeEnd) <= 0 michael@0: // && fSuffixSet.contains(uc = utext_current32(text))) { michael@0: // if (uc == KHMER_PAIYANNOI) { michael@0: // if (!fSuffixSet.contains(utext_previous32(text))) { michael@0: // // Skip over previous end and PAIYANNOI michael@0: // utext_next32(text); michael@0: // utext_next32(text); michael@0: // wordLength += 1; // Add PAIYANNOI to word michael@0: // uc = utext_current32(text); // Fetch next character michael@0: // } michael@0: // else { michael@0: // // Restore prior position michael@0: // utext_next32(text); michael@0: // } michael@0: // } michael@0: // if (uc == KHMER_MAIYAMOK) { michael@0: // if (utext_previous32(text) != KHMER_MAIYAMOK) { michael@0: // // Skip over previous end and MAIYAMOK michael@0: // utext_next32(text); michael@0: // utext_next32(text); michael@0: // wordLength += 1; // Add MAIYAMOK to word michael@0: // } michael@0: // else { michael@0: // // Restore prior position michael@0: // utext_next32(text); michael@0: // } michael@0: // } michael@0: // } michael@0: // else { michael@0: // utext_setNativeIndex(text, current+wordLength); michael@0: // } michael@0: // } michael@0: michael@0: // Did we find a word on this iteration? If so, push it on the break stack michael@0: if (wordLength > 0) { michael@0: foundBreaks.push((current+wordLength), status); michael@0: } michael@0: } michael@0: michael@0: // Don't return a break for the end of the dictionary range if there is one there. michael@0: if (foundBreaks.peeki() >= rangeEnd) { michael@0: (void) foundBreaks.popi(); michael@0: wordsFound -= 1; michael@0: } michael@0: michael@0: return wordsFound; michael@0: } michael@0: michael@0: #if !UCONFIG_NO_NORMALIZATION michael@0: /* michael@0: ****************************************************************** michael@0: * CjkBreakEngine michael@0: */ michael@0: static const uint32_t kuint32max = 0xFFFFFFFF; michael@0: CjkBreakEngine::CjkBreakEngine(DictionaryMatcher *adoptDictionary, LanguageType type, UErrorCode &status) michael@0: : DictionaryBreakEngine(1 << UBRK_WORD), fDictionary(adoptDictionary) { michael@0: // Korean dictionary only includes Hangul syllables michael@0: fHangulWordSet.applyPattern(UNICODE_STRING_SIMPLE("[\\uac00-\\ud7a3]"), status); michael@0: fHanWordSet.applyPattern(UNICODE_STRING_SIMPLE("[:Han:]"), status); michael@0: fKatakanaWordSet.applyPattern(UNICODE_STRING_SIMPLE("[[:Katakana:]\\uff9e\\uff9f]"), status); michael@0: fHiraganaWordSet.applyPattern(UNICODE_STRING_SIMPLE("[:Hiragana:]"), status); michael@0: michael@0: if (U_SUCCESS(status)) { michael@0: // handle Korean and Japanese/Chinese using different dictionaries michael@0: if (type == kKorean) { michael@0: setCharacters(fHangulWordSet); michael@0: } else { //Chinese and Japanese michael@0: UnicodeSet cjSet; michael@0: cjSet.addAll(fHanWordSet); michael@0: cjSet.addAll(fKatakanaWordSet); michael@0: cjSet.addAll(fHiraganaWordSet); michael@0: cjSet.add(0xFF70); // HALFWIDTH KATAKANA-HIRAGANA PROLONGED SOUND MARK michael@0: cjSet.add(0x30FC); // KATAKANA-HIRAGANA PROLONGED SOUND MARK michael@0: setCharacters(cjSet); michael@0: } michael@0: } michael@0: } michael@0: michael@0: CjkBreakEngine::~CjkBreakEngine(){ michael@0: delete fDictionary; michael@0: } michael@0: michael@0: // The katakanaCost values below are based on the length frequencies of all michael@0: // katakana phrases in the dictionary michael@0: static const int kMaxKatakanaLength = 8; michael@0: static const int kMaxKatakanaGroupLength = 20; michael@0: static const uint32_t maxSnlp = 255; michael@0: michael@0: static inline uint32_t getKatakanaCost(int wordLength){ michael@0: //TODO: fill array with actual values from dictionary! michael@0: static const uint32_t katakanaCost[kMaxKatakanaLength + 1] michael@0: = {8192, 984, 408, 240, 204, 252, 300, 372, 480}; michael@0: return (wordLength > kMaxKatakanaLength) ? 8192 : katakanaCost[wordLength]; michael@0: } michael@0: michael@0: static inline bool isKatakana(uint16_t value) { michael@0: return (value >= 0x30A1u && value <= 0x30FEu && value != 0x30FBu) || michael@0: (value >= 0xFF66u && value <= 0xFF9fu); michael@0: } michael@0: michael@0: // A very simple helper class to streamline the buffer handling in michael@0: // divideUpDictionaryRange. michael@0: template michael@0: class AutoBuffer { michael@0: public: michael@0: AutoBuffer(size_t size) : buffer(stackBuffer), capacity(N) { michael@0: if (size > N) { michael@0: buffer = reinterpret_cast(uprv_malloc(sizeof(T)*size)); michael@0: capacity = size; michael@0: } michael@0: } michael@0: ~AutoBuffer() { michael@0: if (buffer != stackBuffer) michael@0: uprv_free(buffer); michael@0: } michael@0: michael@0: T* elems() { michael@0: return buffer; michael@0: } michael@0: michael@0: const T& operator[] (size_t i) const { michael@0: return buffer[i]; michael@0: } michael@0: michael@0: T& operator[] (size_t i) { michael@0: return buffer[i]; michael@0: } michael@0: michael@0: // resize without copy michael@0: void resize(size_t size) { michael@0: if (size <= capacity) michael@0: return; michael@0: if (buffer != stackBuffer) michael@0: uprv_free(buffer); michael@0: buffer = reinterpret_cast(uprv_malloc(sizeof(T)*size)); michael@0: capacity = size; michael@0: } michael@0: michael@0: private: michael@0: T stackBuffer[N]; michael@0: T* buffer; michael@0: AutoBuffer(); michael@0: size_t capacity; michael@0: }; michael@0: michael@0: michael@0: /* michael@0: * @param text A UText representing the text michael@0: * @param rangeStart The start of the range of dictionary characters michael@0: * @param rangeEnd The end of the range of dictionary characters michael@0: * @param foundBreaks Output of C array of int32_t break positions, or 0 michael@0: * @return The number of breaks found michael@0: */ michael@0: int32_t michael@0: CjkBreakEngine::divideUpDictionaryRange( UText *text, michael@0: int32_t rangeStart, michael@0: int32_t rangeEnd, michael@0: UStack &foundBreaks ) const { michael@0: if (rangeStart >= rangeEnd) { michael@0: return 0; michael@0: } michael@0: michael@0: const size_t defaultInputLength = 80; michael@0: size_t inputLength = rangeEnd - rangeStart; michael@0: // TODO: Replace by UnicodeString. michael@0: AutoBuffer charString(inputLength); michael@0: michael@0: // Normalize the input string and put it in normalizedText. michael@0: // The map from the indices of the normalized input to the raw michael@0: // input is kept in charPositions. michael@0: UErrorCode status = U_ZERO_ERROR; michael@0: utext_extract(text, rangeStart, rangeEnd, charString.elems(), inputLength, &status); michael@0: if (U_FAILURE(status)) { michael@0: return 0; michael@0: } michael@0: michael@0: UnicodeString inputString(charString.elems(), inputLength); michael@0: // TODO: Use Normalizer2. michael@0: UNormalizationMode norm_mode = UNORM_NFKC; michael@0: UBool isNormalized = michael@0: Normalizer::quickCheck(inputString, norm_mode, status) == UNORM_YES || michael@0: Normalizer::isNormalized(inputString, norm_mode, status); michael@0: michael@0: // TODO: Replace by UVector32. michael@0: AutoBuffer charPositions(inputLength + 1); michael@0: int numChars = 0; michael@0: UText normalizedText = UTEXT_INITIALIZER; michael@0: // Needs to be declared here because normalizedText holds onto its buffer. michael@0: UnicodeString normalizedString; michael@0: if (isNormalized) { michael@0: int32_t index = 0; michael@0: charPositions[0] = 0; michael@0: while(index < inputString.length()) { michael@0: index = inputString.moveIndex32(index, 1); michael@0: charPositions[++numChars] = index; michael@0: } michael@0: utext_openUnicodeString(&normalizedText, &inputString, &status); michael@0: } michael@0: else { michael@0: Normalizer::normalize(inputString, norm_mode, 0, normalizedString, status); michael@0: if (U_FAILURE(status)) { michael@0: return 0; michael@0: } michael@0: charPositions.resize(normalizedString.length() + 1); michael@0: Normalizer normalizer(charString.elems(), inputLength, norm_mode); michael@0: int32_t index = 0; michael@0: charPositions[0] = 0; michael@0: while(index < normalizer.endIndex()){ michael@0: /* UChar32 uc = */ normalizer.next(); michael@0: charPositions[++numChars] = index = normalizer.getIndex(); michael@0: } michael@0: utext_openUnicodeString(&normalizedText, &normalizedString, &status); michael@0: } michael@0: michael@0: if (U_FAILURE(status)) { michael@0: return 0; michael@0: } michael@0: michael@0: // From this point on, all the indices refer to the indices of michael@0: // the normalized input string. michael@0: michael@0: // bestSnlp[i] is the snlp of the best segmentation of the first i michael@0: // characters in the range to be matched. michael@0: // TODO: Replace by UVector32. michael@0: AutoBuffer bestSnlp(numChars + 1); michael@0: bestSnlp[0] = 0; michael@0: for(int i = 1; i <= numChars; i++) { michael@0: bestSnlp[i] = kuint32max; michael@0: } michael@0: michael@0: // prev[i] is the index of the last CJK character in the previous word in michael@0: // the best segmentation of the first i characters. michael@0: // TODO: Replace by UVector32. michael@0: AutoBuffer prev(numChars + 1); michael@0: for(int i = 0; i <= numChars; i++){ michael@0: prev[i] = -1; michael@0: } michael@0: michael@0: const size_t maxWordSize = 20; michael@0: // TODO: Replace both with UVector32. michael@0: AutoBuffer values(numChars); michael@0: AutoBuffer lengths(numChars); michael@0: michael@0: // Dynamic programming to find the best segmentation. michael@0: bool is_prev_katakana = false; michael@0: for (int32_t i = 0; i < numChars; ++i) { michael@0: //utext_setNativeIndex(text, rangeStart + i); michael@0: utext_setNativeIndex(&normalizedText, i); michael@0: if (bestSnlp[i] == kuint32max) michael@0: continue; michael@0: michael@0: int32_t count; michael@0: // limit maximum word length matched to size of current substring michael@0: int32_t maxSearchLength = (i + maxWordSize < (size_t) numChars)? maxWordSize : (numChars - i); michael@0: michael@0: fDictionary->matches(&normalizedText, maxSearchLength, lengths.elems(), count, maxSearchLength, values.elems()); michael@0: michael@0: // if there are no single character matches found in the dictionary michael@0: // starting with this charcter, treat character as a 1-character word michael@0: // with the highest value possible, i.e. the least likely to occur. michael@0: // Exclude Korean characters from this treatment, as they should be left michael@0: // together by default. michael@0: if((count == 0 || lengths[0] != 1) && michael@0: !fHangulWordSet.contains(utext_current32(&normalizedText))) { michael@0: values[count] = maxSnlp; michael@0: lengths[count++] = 1; michael@0: } michael@0: michael@0: for (int j = 0; j < count; j++) { michael@0: uint32_t newSnlp = bestSnlp[i] + values[j]; michael@0: if (newSnlp < bestSnlp[lengths[j] + i]) { michael@0: bestSnlp[lengths[j] + i] = newSnlp; michael@0: prev[lengths[j] + i] = i; michael@0: } michael@0: } michael@0: michael@0: // In Japanese, michael@0: // Katakana word in single character is pretty rare. So we apply michael@0: // the following heuristic to Katakana: any continuous run of Katakana michael@0: // characters is considered a candidate word with a default cost michael@0: // specified in the katakanaCost table according to its length. michael@0: //utext_setNativeIndex(text, rangeStart + i); michael@0: utext_setNativeIndex(&normalizedText, i); michael@0: bool is_katakana = isKatakana(utext_current32(&normalizedText)); michael@0: if (!is_prev_katakana && is_katakana) { michael@0: int j = i + 1; michael@0: utext_next32(&normalizedText); michael@0: // Find the end of the continuous run of Katakana characters michael@0: while (j < numChars && (j - i) < kMaxKatakanaGroupLength && michael@0: isKatakana(utext_current32(&normalizedText))) { michael@0: utext_next32(&normalizedText); michael@0: ++j; michael@0: } michael@0: if ((j - i) < kMaxKatakanaGroupLength) { michael@0: uint32_t newSnlp = bestSnlp[i] + getKatakanaCost(j - i); michael@0: if (newSnlp < bestSnlp[j]) { michael@0: bestSnlp[j] = newSnlp; michael@0: prev[j] = i; michael@0: } michael@0: } michael@0: } michael@0: is_prev_katakana = is_katakana; michael@0: } michael@0: michael@0: // Start pushing the optimal offset index into t_boundary (t for tentative). michael@0: // prev[numChars] is guaranteed to be meaningful. michael@0: // We'll first push in the reverse order, i.e., michael@0: // t_boundary[0] = numChars, and afterwards do a swap. michael@0: // TODO: Replace by UVector32. michael@0: AutoBuffer t_boundary(numChars + 1); michael@0: michael@0: int numBreaks = 0; michael@0: // No segmentation found, set boundary to end of range michael@0: if (bestSnlp[numChars] == kuint32max) { michael@0: t_boundary[numBreaks++] = numChars; michael@0: } else { michael@0: for (int i = numChars; i > 0; i = prev[i]) { michael@0: t_boundary[numBreaks++] = i; michael@0: } michael@0: U_ASSERT(prev[t_boundary[numBreaks - 1]] == 0); michael@0: } michael@0: michael@0: // Reverse offset index in t_boundary. michael@0: // Don't add a break for the start of the dictionary range if there is one michael@0: // there already. michael@0: if (foundBreaks.size() == 0 || foundBreaks.peeki() < rangeStart) { michael@0: t_boundary[numBreaks++] = 0; michael@0: } michael@0: michael@0: // Now that we're done, convert positions in t_bdry[] (indices in michael@0: // the normalized input string) back to indices in the raw input string michael@0: // while reversing t_bdry and pushing values to foundBreaks. michael@0: for (int i = numBreaks-1; i >= 0; i--) { michael@0: foundBreaks.push(charPositions[t_boundary[i]] + rangeStart, status); michael@0: } michael@0: michael@0: utext_close(&normalizedText); michael@0: return numBreaks; michael@0: } michael@0: #endif michael@0: michael@0: U_NAMESPACE_END michael@0: michael@0: #endif /* #if !UCONFIG_NO_BREAK_ITERATION */ michael@0: