1 /* 2 * Copyright (C) 2009 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.android.inputmethod.latin; 18 19 import android.text.TextUtils; 20 import android.util.Log; 21 22 import com.android.inputmethod.annotations.UsedForTesting; 23 import com.android.inputmethod.keyboard.ProximityInfo; 24 import com.android.inputmethod.latin.SuggestedWords.SuggestedWordInfo; 25 import com.android.inputmethod.latin.utils.CollectionUtils; 26 import com.android.inputmethod.latin.utils.UserHistoryForgettingCurveUtils.ForgettingCurveParams; 27 28 import java.util.ArrayList; 29 import java.util.LinkedList; 30 31 /** 32 * Class for an in-memory dictionary that can grow dynamically and can 33 * be searched for suggestions and valid words. 34 */ 35 // TODO: Remove after binary dictionary supports dynamic update. 36 public class ExpandableDictionary extends Dictionary { 37 private static final String TAG = ExpandableDictionary.class.getSimpleName(); 38 /** 39 * The weight to give to a word if it's length is the same as the number of typed characters. 40 */ 41 private static final int FULL_WORD_SCORE_MULTIPLIER = 2; 42 43 private char[] mWordBuilder = new char[Constants.DICTIONARY_MAX_WORD_LENGTH]; 44 private int mMaxDepth; 45 private int mInputLength; 46 47 private static final class Node { 48 char mCode; 49 int mFrequency; 50 boolean mTerminal; 51 Node mParent; 52 NodeArray mChildren; 53 ArrayList<char[]> mShortcutTargets; 54 boolean mShortcutOnly; 55 LinkedList<NextWord> mNGrams; // Supports ngram 56 } 57 58 private static final class NodeArray { 59 Node[] mData; 60 int mLength = 0; 61 private static final int INCREMENT = 2; 62 63 NodeArray() { 64 mData = new Node[INCREMENT]; 65 } 66 67 void add(final Node n) { 68 if (mLength + 1 > mData.length) { 69 Node[] tempData = new Node[mLength + INCREMENT]; 70 if (mLength > 0) { 71 System.arraycopy(mData, 0, tempData, 0, mLength); 72 } 73 mData = tempData; 74 } 75 mData[mLength++] = n; 76 } 77 } 78 79 public interface NextWord { 80 public Node getWordNode(); 81 public int getFrequency(); 82 public ForgettingCurveParams getFcParams(); 83 public int notifyTypedAgainAndGetFrequency(); 84 } 85 86 private static final class NextStaticWord implements NextWord { 87 public final Node mWord; 88 private final int mFrequency; 89 public NextStaticWord(Node word, int frequency) { 90 mWord = word; 91 mFrequency = frequency; 92 } 93 94 @Override 95 public Node getWordNode() { 96 return mWord; 97 } 98 99 @Override 100 public int getFrequency() { 101 return mFrequency; 102 } 103 104 @Override 105 public ForgettingCurveParams getFcParams() { 106 return null; 107 } 108 109 @Override 110 public int notifyTypedAgainAndGetFrequency() { 111 return mFrequency; 112 } 113 } 114 115 private static final class NextHistoryWord implements NextWord { 116 public final Node mWord; 117 public final ForgettingCurveParams mFcp; 118 119 public NextHistoryWord(Node word, ForgettingCurveParams fcp) { 120 mWord = word; 121 mFcp = fcp; 122 } 123 124 @Override 125 public Node getWordNode() { 126 return mWord; 127 } 128 129 @Override 130 public int getFrequency() { 131 return mFcp.getFrequency(); 132 } 133 134 @Override 135 public ForgettingCurveParams getFcParams() { 136 return mFcp; 137 } 138 139 @Override 140 public int notifyTypedAgainAndGetFrequency() { 141 return mFcp.notifyTypedAgainAndGetFrequency(); 142 } 143 } 144 145 private NodeArray mRoots; 146 147 private int[][] mCodes; 148 149 public ExpandableDictionary(final String dictType) { 150 super(dictType); 151 clearDictionary(); 152 mCodes = new int[Constants.DICTIONARY_MAX_WORD_LENGTH][]; 153 } 154 155 public int getMaxWordLength() { 156 return Constants.DICTIONARY_MAX_WORD_LENGTH; 157 } 158 159 /** 160 * Add a word with an optional shortcut to the dictionary. 161 * @param word The word to add. 162 * @param shortcutTarget A shortcut target for this word, or null if none. 163 * @param frequency The frequency for this unigram. 164 * @param shortcutFreq The frequency of the shortcut (0~15, with 15 = whitelist). Ignored 165 * if shortcutTarget is null. 166 */ 167 public void addWord(final String word, final String shortcutTarget, final int frequency, 168 final int shortcutFreq) { 169 if (word.length() >= Constants.DICTIONARY_MAX_WORD_LENGTH) { 170 return; 171 } 172 addWordRec(mRoots, word, 0, shortcutTarget, frequency, shortcutFreq, null); 173 } 174 175 /** 176 * Add a word, recursively searching for its correct place in the trie tree. 177 * @param children The node to recursively search for addition. Initially, the root of the tree. 178 * @param word The word to add. 179 * @param depth The current depth in the tree. 180 * @param shortcutTarget A shortcut target for this word, or null if none. 181 * @param frequency The frequency for this unigram. 182 * @param shortcutFreq The frequency of the shortcut (0~15, with 15 = whitelist). Ignored 183 * if shortcutTarget is null. 184 * @param parentNode The parent node, for up linking. Initially null, as the root has no parent. 185 */ 186 private void addWordRec(final NodeArray children, final String word, final int depth, 187 final String shortcutTarget, final int frequency, final int shortcutFreq, 188 final Node parentNode) { 189 final int wordLength = word.length(); 190 if (wordLength <= depth) return; 191 final char c = word.charAt(depth); 192 // Does children have the current character? 193 final int childrenLength = children.mLength; 194 Node childNode = null; 195 for (int i = 0; i < childrenLength; i++) { 196 final Node node = children.mData[i]; 197 if (node.mCode == c) { 198 childNode = node; 199 break; 200 } 201 } 202 final boolean isShortcutOnly = (null != shortcutTarget); 203 if (childNode == null) { 204 childNode = new Node(); 205 childNode.mCode = c; 206 childNode.mParent = parentNode; 207 childNode.mShortcutOnly = isShortcutOnly; 208 children.add(childNode); 209 } 210 if (wordLength == depth + 1) { 211 // Terminate this word 212 childNode.mTerminal = true; 213 if (isShortcutOnly) { 214 if (null == childNode.mShortcutTargets) { 215 childNode.mShortcutTargets = CollectionUtils.newArrayList(); 216 } 217 childNode.mShortcutTargets.add(shortcutTarget.toCharArray()); 218 } else { 219 childNode.mShortcutOnly = false; 220 } 221 childNode.mFrequency = Math.max(frequency, childNode.mFrequency); 222 if (childNode.mFrequency > 255) childNode.mFrequency = 255; 223 return; 224 } 225 if (childNode.mChildren == null) { 226 childNode.mChildren = new NodeArray(); 227 } 228 addWordRec(childNode.mChildren, word, depth + 1, shortcutTarget, frequency, shortcutFreq, 229 childNode); 230 } 231 232 @Override 233 public ArrayList<SuggestedWordInfo> getSuggestions(final WordComposer composer, 234 final String prevWord, final ProximityInfo proximityInfo, 235 final boolean blockOffensiveWords, final int[] additionalFeaturesOptions) { 236 if (composer.size() > 1) { 237 if (composer.size() >= Constants.DICTIONARY_MAX_WORD_LENGTH) { 238 return null; 239 } 240 final ArrayList<SuggestedWordInfo> suggestions = 241 getWordsInner(composer, prevWord, proximityInfo); 242 return suggestions; 243 } else { 244 if (TextUtils.isEmpty(prevWord)) return null; 245 final ArrayList<SuggestedWordInfo> suggestions = CollectionUtils.newArrayList(); 246 runBigramReverseLookUp(prevWord, suggestions); 247 return suggestions; 248 } 249 } 250 251 private ArrayList<SuggestedWordInfo> getWordsInner(final WordComposer codes, 252 final String prevWordForBigrams, final ProximityInfo proximityInfo) { 253 final ArrayList<SuggestedWordInfo> suggestions = CollectionUtils.newArrayList(); 254 mInputLength = codes.size(); 255 if (mCodes.length < mInputLength) mCodes = new int[mInputLength][]; 256 final InputPointers ips = codes.getInputPointers(); 257 final int[] xCoordinates = ips.getXCoordinates(); 258 final int[] yCoordinates = ips.getYCoordinates(); 259 // Cache the codes so that we don't have to lookup an array list 260 for (int i = 0; i < mInputLength; i++) { 261 // TODO: Calculate proximity info here. 262 if (mCodes[i] == null || mCodes[i].length < 1) { 263 mCodes[i] = new int[ProximityInfo.MAX_PROXIMITY_CHARS_SIZE]; 264 } 265 final int x = xCoordinates != null && i < xCoordinates.length ? 266 xCoordinates[i] : Constants.NOT_A_COORDINATE; 267 final int y = xCoordinates != null && i < yCoordinates.length ? 268 yCoordinates[i] : Constants.NOT_A_COORDINATE; 269 proximityInfo.fillArrayWithNearestKeyCodes(x, y, codes.getCodeAt(i), mCodes[i]); 270 } 271 mMaxDepth = mInputLength * 3; 272 getWordsRec(mRoots, codes, mWordBuilder, 0, false, 1, 0, -1, suggestions); 273 for (int i = 0; i < mInputLength; i++) { 274 getWordsRec(mRoots, codes, mWordBuilder, 0, false, 1, 0, i, suggestions); 275 } 276 return suggestions; 277 } 278 279 @Override 280 public synchronized boolean isValidWord(final String word) { 281 final Node node = searchNode(mRoots, word, 0, word.length()); 282 // If node is null, we didn't find the word, so it's not valid. 283 // If node.mShortcutOnly is true, then it exists as a shortcut but not as a word, 284 // so that means it's not a valid word. 285 // If node.mShortcutOnly is false, then it exists as a word (it may also exist as 286 // a shortcut, but this does not matter), so it's a valid word. 287 return (node == null) ? false : !node.mShortcutOnly; 288 } 289 290 public boolean removeBigram(final String word0, final String word1) { 291 // Refer to addOrSetBigram() about word1.toLowerCase() 292 final Node firstWord = searchWord(mRoots, word0.toLowerCase(), 0, null); 293 final Node secondWord = searchWord(mRoots, word1, 0, null); 294 LinkedList<NextWord> bigrams = firstWord.mNGrams; 295 NextWord bigramNode = null; 296 if (bigrams == null || bigrams.size() == 0) { 297 return false; 298 } else { 299 for (NextWord nw : bigrams) { 300 if (nw.getWordNode() == secondWord) { 301 bigramNode = nw; 302 break; 303 } 304 } 305 } 306 if (bigramNode == null) { 307 return false; 308 } 309 return bigrams.remove(bigramNode); 310 } 311 312 /** 313 * Returns the word's frequency or -1 if not found 314 */ 315 @UsedForTesting 316 public int getWordFrequency(final String word) { 317 // Case-sensitive search 318 final Node node = searchNode(mRoots, word, 0, word.length()); 319 return (node == null) ? -1 : node.mFrequency; 320 } 321 322 public NextWord getBigramWord(final String word0, final String word1) { 323 // Refer to addOrSetBigram() about word0.toLowerCase() 324 final Node firstWord = searchWord(mRoots, word0.toLowerCase(), 0, null); 325 final Node secondWord = searchWord(mRoots, word1, 0, null); 326 LinkedList<NextWord> bigrams = firstWord.mNGrams; 327 if (bigrams == null || bigrams.size() == 0) { 328 return null; 329 } else { 330 for (NextWord nw : bigrams) { 331 if (nw.getWordNode() == secondWord) { 332 return nw; 333 } 334 } 335 } 336 return null; 337 } 338 339 private static int computeSkippedWordFinalFreq(final int freq, final int snr, 340 final int inputLength) { 341 // The computation itself makes sense for >= 2, but the == 2 case returns 0 342 // anyway so we may as well test against 3 instead and return the constant 343 if (inputLength >= 3) { 344 return (freq * snr * (inputLength - 2)) / (inputLength - 1); 345 } else { 346 return 0; 347 } 348 } 349 350 /** 351 * Helper method to add a word and its shortcuts. 352 * 353 * @param node the terminal node 354 * @param word the word to insert, as an array of code points 355 * @param depth the depth of the node in the tree 356 * @param finalFreq the frequency for this word 357 * @param suggestions the suggestion collection to add the suggestions to 358 * @return whether there is still space for more words. 359 */ 360 private boolean addWordAndShortcutsFromNode(final Node node, final char[] word, final int depth, 361 final int finalFreq, final ArrayList<SuggestedWordInfo> suggestions) { 362 if (finalFreq > 0 && !node.mShortcutOnly) { 363 // Use KIND_CORRECTION always. This dictionary does not really have a notion of 364 // COMPLETION against CORRECTION; we could artificially add one by looking at 365 // the respective size of the typed word and the suggestion if it matters sometime 366 // in the future. 367 suggestions.add(new SuggestedWordInfo(new String(word, 0, depth + 1), finalFreq, 368 SuggestedWordInfo.KIND_CORRECTION, this /* sourceDict */, 369 SuggestedWordInfo.NOT_AN_INDEX /* indexOfTouchPointOfSecondWord */, 370 SuggestedWordInfo.NOT_A_CONFIDENCE /* autoCommitFirstWordConfidence */)); 371 if (suggestions.size() >= Suggest.MAX_SUGGESTIONS) return false; 372 } 373 if (null != node.mShortcutTargets) { 374 final int length = node.mShortcutTargets.size(); 375 for (int shortcutIndex = 0; shortcutIndex < length; ++shortcutIndex) { 376 final char[] shortcut = node.mShortcutTargets.get(shortcutIndex); 377 suggestions.add(new SuggestedWordInfo(new String(shortcut, 0, shortcut.length), 378 finalFreq, SuggestedWordInfo.KIND_SHORTCUT, this /* sourceDict */, 379 SuggestedWordInfo.NOT_AN_INDEX /* indexOfTouchPointOfSecondWord */, 380 SuggestedWordInfo.NOT_A_CONFIDENCE /* autoCommitFirstWordConfidence */)); 381 if (suggestions.size() > Suggest.MAX_SUGGESTIONS) return false; 382 } 383 } 384 return true; 385 } 386 387 /** 388 * Recursively traverse the tree for words that match the input. Input consists of 389 * a list of arrays. Each item in the list is one input character position. An input 390 * character is actually an array of multiple possible candidates. This function is not 391 * optimized for speed, assuming that the user dictionary will only be a few hundred words in 392 * size. 393 * @param roots node whose children have to be search for matches 394 * @param codes the input character codes 395 * @param word the word being composed as a possible match 396 * @param depth the depth of traversal - the length of the word being composed thus far 397 * @param completion whether the traversal is now in completion mode - meaning that we've 398 * exhausted the input and we're looking for all possible suffixes. 399 * @param snr current weight of the word being formed 400 * @param inputIndex position in the input characters. This can be off from the depth in 401 * case we skip over some punctuations such as apostrophe in the traversal. That is, if you type 402 * "wouldve", it could be matching "would've", so the depth will be one more than the 403 * inputIndex 404 * @param suggestions the list in which to add suggestions 405 */ 406 // TODO: Share this routine with the native code for BinaryDictionary 407 private void getWordsRec(final NodeArray roots, final WordComposer codes, final char[] word, 408 final int depth, final boolean completion, final int snr, final int inputIndex, 409 final int skipPos, final ArrayList<SuggestedWordInfo> suggestions) { 410 final int count = roots.mLength; 411 final int codeSize = mInputLength; 412 // Optimization: Prune out words that are too long compared to how much was typed. 413 if (depth > mMaxDepth) { 414 return; 415 } 416 final int[] currentChars; 417 if (codeSize <= inputIndex) { 418 currentChars = null; 419 } else { 420 currentChars = mCodes[inputIndex]; 421 } 422 423 for (int i = 0; i < count; i++) { 424 final Node node = roots.mData[i]; 425 final char c = node.mCode; 426 final char lowerC = toLowerCase(c); 427 final boolean terminal = node.mTerminal; 428 final NodeArray children = node.mChildren; 429 final int freq = node.mFrequency; 430 if (completion || currentChars == null) { 431 word[depth] = c; 432 if (terminal) { 433 final int finalFreq; 434 if (skipPos < 0) { 435 finalFreq = freq * snr; 436 } else { 437 finalFreq = computeSkippedWordFinalFreq(freq, snr, mInputLength); 438 } 439 if (!addWordAndShortcutsFromNode(node, word, depth, finalFreq, suggestions)) { 440 // No space left in the queue, bail out 441 return; 442 } 443 } 444 if (children != null) { 445 getWordsRec(children, codes, word, depth + 1, true, snr, inputIndex, 446 skipPos, suggestions); 447 } 448 } else if ((c == Constants.CODE_SINGLE_QUOTE 449 && currentChars[0] != Constants.CODE_SINGLE_QUOTE) || depth == skipPos) { 450 // Skip the ' and continue deeper 451 word[depth] = c; 452 if (children != null) { 453 getWordsRec(children, codes, word, depth + 1, completion, snr, inputIndex, 454 skipPos, suggestions); 455 } 456 } else { 457 // Don't use alternatives if we're looking for missing characters 458 final int alternativesSize = skipPos >= 0 ? 1 : currentChars.length; 459 for (int j = 0; j < alternativesSize; j++) { 460 final int addedAttenuation = (j > 0 ? 1 : 2); 461 final int currentChar = currentChars[j]; 462 if (currentChar == Constants.NOT_A_CODE) { 463 break; 464 } 465 if (currentChar == lowerC || currentChar == c) { 466 word[depth] = c; 467 468 if (codeSize == inputIndex + 1) { 469 if (terminal) { 470 final int finalFreq; 471 if (skipPos < 0) { 472 finalFreq = freq * snr * addedAttenuation 473 * FULL_WORD_SCORE_MULTIPLIER; 474 } else { 475 finalFreq = computeSkippedWordFinalFreq(freq, 476 snr * addedAttenuation, mInputLength); 477 } 478 if (!addWordAndShortcutsFromNode(node, word, depth, finalFreq, 479 suggestions)) { 480 // No space left in the queue, bail out 481 return; 482 } 483 } 484 if (children != null) { 485 getWordsRec(children, codes, word, depth + 1, 486 true, snr * addedAttenuation, inputIndex + 1, 487 skipPos, suggestions); 488 } 489 } else if (children != null) { 490 getWordsRec(children, codes, word, depth + 1, 491 false, snr * addedAttenuation, inputIndex + 1, 492 skipPos, suggestions); 493 } 494 } 495 } 496 } 497 } 498 } 499 500 public int setBigramAndGetFrequency(final String word0, final String word1, 501 final int frequency) { 502 return setBigramAndGetFrequency(word0, word1, frequency, null /* unused */); 503 } 504 505 public int setBigramAndGetFrequency(final String word0, final String word1, 506 final ForgettingCurveParams fcp) { 507 return setBigramAndGetFrequency(word0, word1, 0 /* unused */, fcp); 508 } 509 510 /** 511 * Adds bigrams to the in-memory trie structure that is being used to retrieve any word 512 * @param word0 the first word of this bigram 513 * @param word1 the second word of this bigram 514 * @param frequency frequency for this bigram 515 * @param fcp an instance of ForgettingCurveParams to use for decay policy 516 * @return returns the final bigram frequency 517 */ 518 private int setBigramAndGetFrequency(final String word0, final String word1, 519 final int frequency, final ForgettingCurveParams fcp) { 520 if (TextUtils.isEmpty(word0)) { 521 Log.e(TAG, "Invalid bigram previous word: " + word0); 522 return frequency; 523 } 524 // We don't want results to be different according to case of the looked up left hand side 525 // word. We do want however to return the correct case for the right hand side. 526 // So we want to squash the case of the left hand side, and preserve that of the right 527 // hand side word. 528 final String word0Lower = word0.toLowerCase(); 529 if (TextUtils.isEmpty(word0Lower) || TextUtils.isEmpty(word1)) { 530 Log.e(TAG, "Invalid bigram pair: " + word0 + ", " + word0Lower + ", " + word1); 531 return frequency; 532 } 533 final Node firstWord = searchWord(mRoots, word0Lower, 0, null); 534 final Node secondWord = searchWord(mRoots, word1, 0, null); 535 LinkedList<NextWord> bigrams = firstWord.mNGrams; 536 if (bigrams == null || bigrams.size() == 0) { 537 firstWord.mNGrams = CollectionUtils.newLinkedList(); 538 bigrams = firstWord.mNGrams; 539 } else { 540 for (NextWord nw : bigrams) { 541 if (nw.getWordNode() == secondWord) { 542 return nw.notifyTypedAgainAndGetFrequency(); 543 } 544 } 545 } 546 if (fcp != null) { 547 // history 548 firstWord.mNGrams.add(new NextHistoryWord(secondWord, fcp)); 549 } else { 550 firstWord.mNGrams.add(new NextStaticWord(secondWord, frequency)); 551 } 552 return frequency; 553 } 554 555 /** 556 * Searches for the word and add the word if it does not exist. 557 * @return Returns the terminal node of the word we are searching for. 558 */ 559 private Node searchWord(final NodeArray children, final String word, final int depth, 560 final Node parentNode) { 561 final int wordLength = word.length(); 562 final char c = word.charAt(depth); 563 // Does children have the current character? 564 final int childrenLength = children.mLength; 565 Node childNode = null; 566 for (int i = 0; i < childrenLength; i++) { 567 final Node node = children.mData[i]; 568 if (node.mCode == c) { 569 childNode = node; 570 break; 571 } 572 } 573 if (childNode == null) { 574 childNode = new Node(); 575 childNode.mCode = c; 576 childNode.mParent = parentNode; 577 children.add(childNode); 578 } 579 if (wordLength == depth + 1) { 580 // Terminate this word 581 childNode.mTerminal = true; 582 return childNode; 583 } 584 if (childNode.mChildren == null) { 585 childNode.mChildren = new NodeArray(); 586 } 587 return searchWord(childNode.mChildren, word, depth + 1, childNode); 588 } 589 590 private void runBigramReverseLookUp(final String previousWord, 591 final ArrayList<SuggestedWordInfo> suggestions) { 592 // Search for the lowercase version of the word only, because that's where bigrams 593 // store their sons. 594 final Node prevWord = searchNode(mRoots, previousWord.toLowerCase(), 0, 595 previousWord.length()); 596 if (prevWord != null && prevWord.mNGrams != null) { 597 reverseLookUp(prevWord.mNGrams, suggestions); 598 } 599 } 600 601 // Local to reverseLookUp, but do not allocate each time. 602 private final char[] mLookedUpString = new char[Constants.DICTIONARY_MAX_WORD_LENGTH]; 603 604 /** 605 * reverseLookUp retrieves the full word given a list of terminal nodes and adds those words 606 * to the suggestions list passed as an argument. 607 * @param terminalNodes list of terminal nodes we want to add 608 * @param suggestions the suggestion collection to add the word to 609 */ 610 private void reverseLookUp(final LinkedList<NextWord> terminalNodes, 611 final ArrayList<SuggestedWordInfo> suggestions) { 612 Node node; 613 int freq; 614 for (NextWord nextWord : terminalNodes) { 615 node = nextWord.getWordNode(); 616 freq = nextWord.getFrequency(); 617 int index = Constants.DICTIONARY_MAX_WORD_LENGTH; 618 do { 619 --index; 620 mLookedUpString[index] = node.mCode; 621 node = node.mParent; 622 } while (node != null && index > 0); 623 624 // If node is null, we have a word longer than MAX_WORD_LENGTH in the dictionary. 625 // It's a little unclear how this can happen, but just in case it does it's safer 626 // to ignore the word in this case. 627 if (freq >= 0 && node == null) { 628 suggestions.add(new SuggestedWordInfo(new String(mLookedUpString, index, 629 Constants.DICTIONARY_MAX_WORD_LENGTH - index), 630 freq, SuggestedWordInfo.KIND_CORRECTION, this /* sourceDict */, 631 SuggestedWordInfo.NOT_AN_INDEX /* indexOfTouchPointOfSecondWord */, 632 SuggestedWordInfo.NOT_A_CONFIDENCE /* autoCommitFirstWordConfidence */)); 633 } 634 } 635 } 636 637 /** 638 * Recursively search for the terminal node of the word. 639 * 640 * One iteration takes the full word to search for and the current index of the recursion. 641 * 642 * @param children the node of the trie to search under. 643 * @param word the word to search for. Only read [offset..length] so there may be trailing chars 644 * @param offset the index in {@code word} this recursion should operate on. 645 * @param length the length of the input word. 646 * @return Returns the terminal node of the word if the word exists 647 */ 648 private Node searchNode(final NodeArray children, final CharSequence word, final int offset, 649 final int length) { 650 final int count = children.mLength; 651 final char currentChar = word.charAt(offset); 652 for (int j = 0; j < count; j++) { 653 final Node node = children.mData[j]; 654 if (node.mCode == currentChar) { 655 if (offset == length - 1) { 656 if (node.mTerminal) { 657 return node; 658 } 659 } else { 660 if (node.mChildren != null) { 661 Node returnNode = searchNode(node.mChildren, word, offset + 1, length); 662 if (returnNode != null) return returnNode; 663 } 664 } 665 } 666 } 667 return null; 668 } 669 670 public void clearDictionary() { 671 mRoots = new NodeArray(); 672 } 673 674 private static char toLowerCase(final char c) { 675 char baseChar = c; 676 if (c < BASE_CHARS.length) { 677 baseChar = BASE_CHARS[c]; 678 } 679 if (baseChar >= 'A' && baseChar <= 'Z') { 680 return (char)(baseChar | 32); 681 } else if (baseChar > 127) { 682 return Character.toLowerCase(baseChar); 683 } 684 return baseChar; 685 } 686 687 /** 688 * Table mapping most combined Latin, Greek, and Cyrillic characters 689 * to their base characters. If c is in range, BASE_CHARS[c] == c 690 * if c is not a combined character, or the base character if it 691 * is combined. 692 * 693 * cf. native/jni/src/utils/char_utils.cpp 694 */ 695 private static final char BASE_CHARS[] = { 696 /* U+0000 */ 0x0000, 0x0001, 0x0002, 0x0003, 0x0004, 0x0005, 0x0006, 0x0007, 697 /* U+0008 */ 0x0008, 0x0009, 0x000A, 0x000B, 0x000C, 0x000D, 0x000E, 0x000F, 698 /* U+0010 */ 0x0010, 0x0011, 0x0012, 0x0013, 0x0014, 0x0015, 0x0016, 0x0017, 699 /* U+0018 */ 0x0018, 0x0019, 0x001A, 0x001B, 0x001C, 0x001D, 0x001E, 0x001F, 700 /* U+0020 */ 0x0020, 0x0021, 0x0022, 0x0023, 0x0024, 0x0025, 0x0026, 0x0027, 701 /* U+0028 */ 0x0028, 0x0029, 0x002A, 0x002B, 0x002C, 0x002D, 0x002E, 0x002F, 702 /* U+0030 */ 0x0030, 0x0031, 0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 703 /* U+0038 */ 0x0038, 0x0039, 0x003A, 0x003B, 0x003C, 0x003D, 0x003E, 0x003F, 704 /* U+0040 */ 0x0040, 0x0041, 0x0042, 0x0043, 0x0044, 0x0045, 0x0046, 0x0047, 705 /* U+0048 */ 0x0048, 0x0049, 0x004A, 0x004B, 0x004C, 0x004D, 0x004E, 0x004F, 706 /* U+0050 */ 0x0050, 0x0051, 0x0052, 0x0053, 0x0054, 0x0055, 0x0056, 0x0057, 707 /* U+0058 */ 0x0058, 0x0059, 0x005A, 0x005B, 0x005C, 0x005D, 0x005E, 0x005F, 708 /* U+0060 */ 0x0060, 0x0061, 0x0062, 0x0063, 0x0064, 0x0065, 0x0066, 0x0067, 709 /* U+0068 */ 0x0068, 0x0069, 0x006A, 0x006B, 0x006C, 0x006D, 0x006E, 0x006F, 710 /* U+0070 */ 0x0070, 0x0071, 0x0072, 0x0073, 0x0074, 0x0075, 0x0076, 0x0077, 711 /* U+0078 */ 0x0078, 0x0079, 0x007A, 0x007B, 0x007C, 0x007D, 0x007E, 0x007F, 712 /* U+0080 */ 0x0080, 0x0081, 0x0082, 0x0083, 0x0084, 0x0085, 0x0086, 0x0087, 713 /* U+0088 */ 0x0088, 0x0089, 0x008A, 0x008B, 0x008C, 0x008D, 0x008E, 0x008F, 714 /* U+0090 */ 0x0090, 0x0091, 0x0092, 0x0093, 0x0094, 0x0095, 0x0096, 0x0097, 715 /* U+0098 */ 0x0098, 0x0099, 0x009A, 0x009B, 0x009C, 0x009D, 0x009E, 0x009F, 716 /* U+00A0 */ 0x0020, 0x00A1, 0x00A2, 0x00A3, 0x00A4, 0x00A5, 0x00A6, 0x00A7, 717 /* U+00A8 */ 0x0020, 0x00A9, 0x0061, 0x00AB, 0x00AC, 0x00AD, 0x00AE, 0x0020, 718 /* U+00B0 */ 0x00B0, 0x00B1, 0x0032, 0x0033, 0x0020, 0x03BC, 0x00B6, 0x00B7, 719 /* U+00B8 */ 0x0020, 0x0031, 0x006F, 0x00BB, 0x0031, 0x0031, 0x0033, 0x00BF, 720 /* U+00C0 */ 0x0041, 0x0041, 0x0041, 0x0041, 0x0041, 0x0041, 0x00C6, 0x0043, 721 /* U+00C8 */ 0x0045, 0x0045, 0x0045, 0x0045, 0x0049, 0x0049, 0x0049, 0x0049, 722 /* U+00D0 */ 0x00D0, 0x004E, 0x004F, 0x004F, 0x004F, 0x004F, 0x004F, 0x00D7, 723 /* U+00D8 */ 0x004F, 0x0055, 0x0055, 0x0055, 0x0055, 0x0059, 0x00DE, 0x0073, 724 // U+00D8: Manually changed from 00D8 to 004F 725 // TODO: Check if it's really acceptable to consider a diacritical variant of O 726 // U+00DF: Manually changed from 00DF to 0073 727 /* U+00E0 */ 0x0061, 0x0061, 0x0061, 0x0061, 0x0061, 0x0061, 0x00E6, 0x0063, 728 /* U+00E8 */ 0x0065, 0x0065, 0x0065, 0x0065, 0x0069, 0x0069, 0x0069, 0x0069, 729 /* U+00F0 */ 0x00F0, 0x006E, 0x006F, 0x006F, 0x006F, 0x006F, 0x006F, 0x00F7, 730 /* U+00F8 */ 0x006F, 0x0075, 0x0075, 0x0075, 0x0075, 0x0079, 0x00FE, 0x0079, 731 // U+00F8: Manually changed from 00F8 to 006F 732 // TODO: Check if it's really acceptable to consider a diacritical variant of o 733 /* U+0100 */ 0x0041, 0x0061, 0x0041, 0x0061, 0x0041, 0x0061, 0x0043, 0x0063, 734 /* U+0108 */ 0x0043, 0x0063, 0x0043, 0x0063, 0x0043, 0x0063, 0x0044, 0x0064, 735 /* U+0110 */ 0x0110, 0x0111, 0x0045, 0x0065, 0x0045, 0x0065, 0x0045, 0x0065, 736 /* U+0118 */ 0x0045, 0x0065, 0x0045, 0x0065, 0x0047, 0x0067, 0x0047, 0x0067, 737 /* U+0120 */ 0x0047, 0x0067, 0x0047, 0x0067, 0x0048, 0x0068, 0x0126, 0x0127, 738 /* U+0128 */ 0x0049, 0x0069, 0x0049, 0x0069, 0x0049, 0x0069, 0x0049, 0x0069, 739 /* U+0130 */ 0x0049, 0x0131, 0x0049, 0x0069, 0x004A, 0x006A, 0x004B, 0x006B, 740 /* U+0138 */ 0x0138, 0x004C, 0x006C, 0x004C, 0x006C, 0x004C, 0x006C, 0x004C, 741 /* U+0140 */ 0x006C, 0x004C, 0x006C, 0x004E, 0x006E, 0x004E, 0x006E, 0x004E, 742 // U+0141: Manually changed from 0141 to 004C 743 // U+0142: Manually changed from 0142 to 006C 744 /* U+0148 */ 0x006E, 0x02BC, 0x014A, 0x014B, 0x004F, 0x006F, 0x004F, 0x006F, 745 /* U+0150 */ 0x004F, 0x006F, 0x0152, 0x0153, 0x0052, 0x0072, 0x0052, 0x0072, 746 /* U+0158 */ 0x0052, 0x0072, 0x0053, 0x0073, 0x0053, 0x0073, 0x0053, 0x0073, 747 /* U+0160 */ 0x0053, 0x0073, 0x0054, 0x0074, 0x0054, 0x0074, 0x0166, 0x0167, 748 /* U+0168 */ 0x0055, 0x0075, 0x0055, 0x0075, 0x0055, 0x0075, 0x0055, 0x0075, 749 /* U+0170 */ 0x0055, 0x0075, 0x0055, 0x0075, 0x0057, 0x0077, 0x0059, 0x0079, 750 /* U+0178 */ 0x0059, 0x005A, 0x007A, 0x005A, 0x007A, 0x005A, 0x007A, 0x0073, 751 /* U+0180 */ 0x0180, 0x0181, 0x0182, 0x0183, 0x0184, 0x0185, 0x0186, 0x0187, 752 /* U+0188 */ 0x0188, 0x0189, 0x018A, 0x018B, 0x018C, 0x018D, 0x018E, 0x018F, 753 /* U+0190 */ 0x0190, 0x0191, 0x0192, 0x0193, 0x0194, 0x0195, 0x0196, 0x0197, 754 /* U+0198 */ 0x0198, 0x0199, 0x019A, 0x019B, 0x019C, 0x019D, 0x019E, 0x019F, 755 /* U+01A0 */ 0x004F, 0x006F, 0x01A2, 0x01A3, 0x01A4, 0x01A5, 0x01A6, 0x01A7, 756 /* U+01A8 */ 0x01A8, 0x01A9, 0x01AA, 0x01AB, 0x01AC, 0x01AD, 0x01AE, 0x0055, 757 /* U+01B0 */ 0x0075, 0x01B1, 0x01B2, 0x01B3, 0x01B4, 0x01B5, 0x01B6, 0x01B7, 758 /* U+01B8 */ 0x01B8, 0x01B9, 0x01BA, 0x01BB, 0x01BC, 0x01BD, 0x01BE, 0x01BF, 759 /* U+01C0 */ 0x01C0, 0x01C1, 0x01C2, 0x01C3, 0x0044, 0x0044, 0x0064, 0x004C, 760 /* U+01C8 */ 0x004C, 0x006C, 0x004E, 0x004E, 0x006E, 0x0041, 0x0061, 0x0049, 761 /* U+01D0 */ 0x0069, 0x004F, 0x006F, 0x0055, 0x0075, 0x0055, 0x0075, 0x0055, 762 // U+01D5: Manually changed from 00DC to 0055 763 // U+01D6: Manually changed from 00FC to 0075 764 // U+01D7: Manually changed from 00DC to 0055 765 /* U+01D8 */ 0x0075, 0x0055, 0x0075, 0x0055, 0x0075, 0x01DD, 0x0041, 0x0061, 766 // U+01D8: Manually changed from 00FC to 0075 767 // U+01D9: Manually changed from 00DC to 0055 768 // U+01DA: Manually changed from 00FC to 0075 769 // U+01DB: Manually changed from 00DC to 0055 770 // U+01DC: Manually changed from 00FC to 0075 771 // U+01DE: Manually changed from 00C4 to 0041 772 // U+01DF: Manually changed from 00E4 to 0061 773 /* U+01E0 */ 0x0041, 0x0061, 0x00C6, 0x00E6, 0x01E4, 0x01E5, 0x0047, 0x0067, 774 // U+01E0: Manually changed from 0226 to 0041 775 // U+01E1: Manually changed from 0227 to 0061 776 /* U+01E8 */ 0x004B, 0x006B, 0x004F, 0x006F, 0x004F, 0x006F, 0x01B7, 0x0292, 777 // U+01EC: Manually changed from 01EA to 004F 778 // U+01ED: Manually changed from 01EB to 006F 779 /* U+01F0 */ 0x006A, 0x0044, 0x0044, 0x0064, 0x0047, 0x0067, 0x01F6, 0x01F7, 780 /* U+01F8 */ 0x004E, 0x006E, 0x0041, 0x0061, 0x00C6, 0x00E6, 0x004F, 0x006F, 781 // U+01FA: Manually changed from 00C5 to 0041 782 // U+01FB: Manually changed from 00E5 to 0061 783 // U+01FE: Manually changed from 00D8 to 004F 784 // TODO: Check if it's really acceptable to consider a diacritical variant of O 785 // U+01FF: Manually changed from 00F8 to 006F 786 // TODO: Check if it's really acceptable to consider a diacritical variant of o 787 /* U+0200 */ 0x0041, 0x0061, 0x0041, 0x0061, 0x0045, 0x0065, 0x0045, 0x0065, 788 /* U+0208 */ 0x0049, 0x0069, 0x0049, 0x0069, 0x004F, 0x006F, 0x004F, 0x006F, 789 /* U+0210 */ 0x0052, 0x0072, 0x0052, 0x0072, 0x0055, 0x0075, 0x0055, 0x0075, 790 /* U+0218 */ 0x0053, 0x0073, 0x0054, 0x0074, 0x021C, 0x021D, 0x0048, 0x0068, 791 /* U+0220 */ 0x0220, 0x0221, 0x0222, 0x0223, 0x0224, 0x0225, 0x0041, 0x0061, 792 /* U+0228 */ 0x0045, 0x0065, 0x004F, 0x006F, 0x004F, 0x006F, 0x004F, 0x006F, 793 // U+022A: Manually changed from 00D6 to 004F 794 // U+022B: Manually changed from 00F6 to 006F 795 // U+022C: Manually changed from 00D5 to 004F 796 // U+022D: Manually changed from 00F5 to 006F 797 /* U+0230 */ 0x004F, 0x006F, 0x0059, 0x0079, 0x0234, 0x0235, 0x0236, 0x0237, 798 // U+0230: Manually changed from 022E to 004F 799 // U+0231: Manually changed from 022F to 006F 800 /* U+0238 */ 0x0238, 0x0239, 0x023A, 0x023B, 0x023C, 0x023D, 0x023E, 0x023F, 801 /* U+0240 */ 0x0240, 0x0241, 0x0242, 0x0243, 0x0244, 0x0245, 0x0246, 0x0247, 802 /* U+0248 */ 0x0248, 0x0249, 0x024A, 0x024B, 0x024C, 0x024D, 0x024E, 0x024F, 803 /* U+0250 */ 0x0250, 0x0251, 0x0252, 0x0253, 0x0254, 0x0255, 0x0256, 0x0257, 804 /* U+0258 */ 0x0258, 0x0259, 0x025A, 0x025B, 0x025C, 0x025D, 0x025E, 0x025F, 805 /* U+0260 */ 0x0260, 0x0261, 0x0262, 0x0263, 0x0264, 0x0265, 0x0266, 0x0267, 806 /* U+0268 */ 0x0268, 0x0269, 0x026A, 0x026B, 0x026C, 0x026D, 0x026E, 0x026F, 807 /* U+0270 */ 0x0270, 0x0271, 0x0272, 0x0273, 0x0274, 0x0275, 0x0276, 0x0277, 808 /* U+0278 */ 0x0278, 0x0279, 0x027A, 0x027B, 0x027C, 0x027D, 0x027E, 0x027F, 809 /* U+0280 */ 0x0280, 0x0281, 0x0282, 0x0283, 0x0284, 0x0285, 0x0286, 0x0287, 810 /* U+0288 */ 0x0288, 0x0289, 0x028A, 0x028B, 0x028C, 0x028D, 0x028E, 0x028F, 811 /* U+0290 */ 0x0290, 0x0291, 0x0292, 0x0293, 0x0294, 0x0295, 0x0296, 0x0297, 812 /* U+0298 */ 0x0298, 0x0299, 0x029A, 0x029B, 0x029C, 0x029D, 0x029E, 0x029F, 813 /* U+02A0 */ 0x02A0, 0x02A1, 0x02A2, 0x02A3, 0x02A4, 0x02A5, 0x02A6, 0x02A7, 814 /* U+02A8 */ 0x02A8, 0x02A9, 0x02AA, 0x02AB, 0x02AC, 0x02AD, 0x02AE, 0x02AF, 815 /* U+02B0 */ 0x0068, 0x0266, 0x006A, 0x0072, 0x0279, 0x027B, 0x0281, 0x0077, 816 /* U+02B8 */ 0x0079, 0x02B9, 0x02BA, 0x02BB, 0x02BC, 0x02BD, 0x02BE, 0x02BF, 817 /* U+02C0 */ 0x02C0, 0x02C1, 0x02C2, 0x02C3, 0x02C4, 0x02C5, 0x02C6, 0x02C7, 818 /* U+02C8 */ 0x02C8, 0x02C9, 0x02CA, 0x02CB, 0x02CC, 0x02CD, 0x02CE, 0x02CF, 819 /* U+02D0 */ 0x02D0, 0x02D1, 0x02D2, 0x02D3, 0x02D4, 0x02D5, 0x02D6, 0x02D7, 820 /* U+02D8 */ 0x0020, 0x0020, 0x0020, 0x0020, 0x0020, 0x0020, 0x02DE, 0x02DF, 821 /* U+02E0 */ 0x0263, 0x006C, 0x0073, 0x0078, 0x0295, 0x02E5, 0x02E6, 0x02E7, 822 /* U+02E8 */ 0x02E8, 0x02E9, 0x02EA, 0x02EB, 0x02EC, 0x02ED, 0x02EE, 0x02EF, 823 /* U+02F0 */ 0x02F0, 0x02F1, 0x02F2, 0x02F3, 0x02F4, 0x02F5, 0x02F6, 0x02F7, 824 /* U+02F8 */ 0x02F8, 0x02F9, 0x02FA, 0x02FB, 0x02FC, 0x02FD, 0x02FE, 0x02FF, 825 /* U+0300 */ 0x0300, 0x0301, 0x0302, 0x0303, 0x0304, 0x0305, 0x0306, 0x0307, 826 /* U+0308 */ 0x0308, 0x0309, 0x030A, 0x030B, 0x030C, 0x030D, 0x030E, 0x030F, 827 /* U+0310 */ 0x0310, 0x0311, 0x0312, 0x0313, 0x0314, 0x0315, 0x0316, 0x0317, 828 /* U+0318 */ 0x0318, 0x0319, 0x031A, 0x031B, 0x031C, 0x031D, 0x031E, 0x031F, 829 /* U+0320 */ 0x0320, 0x0321, 0x0322, 0x0323, 0x0324, 0x0325, 0x0326, 0x0327, 830 /* U+0328 */ 0x0328, 0x0329, 0x032A, 0x032B, 0x032C, 0x032D, 0x032E, 0x032F, 831 /* U+0330 */ 0x0330, 0x0331, 0x0332, 0x0333, 0x0334, 0x0335, 0x0336, 0x0337, 832 /* U+0338 */ 0x0338, 0x0339, 0x033A, 0x033B, 0x033C, 0x033D, 0x033E, 0x033F, 833 /* U+0340 */ 0x0300, 0x0301, 0x0342, 0x0313, 0x0308, 0x0345, 0x0346, 0x0347, 834 /* U+0348 */ 0x0348, 0x0349, 0x034A, 0x034B, 0x034C, 0x034D, 0x034E, 0x034F, 835 /* U+0350 */ 0x0350, 0x0351, 0x0352, 0x0353, 0x0354, 0x0355, 0x0356, 0x0357, 836 /* U+0358 */ 0x0358, 0x0359, 0x035A, 0x035B, 0x035C, 0x035D, 0x035E, 0x035F, 837 /* U+0360 */ 0x0360, 0x0361, 0x0362, 0x0363, 0x0364, 0x0365, 0x0366, 0x0367, 838 /* U+0368 */ 0x0368, 0x0369, 0x036A, 0x036B, 0x036C, 0x036D, 0x036E, 0x036F, 839 /* U+0370 */ 0x0370, 0x0371, 0x0372, 0x0373, 0x02B9, 0x0375, 0x0376, 0x0377, 840 /* U+0378 */ 0x0378, 0x0379, 0x0020, 0x037B, 0x037C, 0x037D, 0x003B, 0x037F, 841 /* U+0380 */ 0x0380, 0x0381, 0x0382, 0x0383, 0x0020, 0x00A8, 0x0391, 0x00B7, 842 /* U+0388 */ 0x0395, 0x0397, 0x0399, 0x038B, 0x039F, 0x038D, 0x03A5, 0x03A9, 843 /* U+0390 */ 0x03CA, 0x0391, 0x0392, 0x0393, 0x0394, 0x0395, 0x0396, 0x0397, 844 /* U+0398 */ 0x0398, 0x0399, 0x039A, 0x039B, 0x039C, 0x039D, 0x039E, 0x039F, 845 /* U+03A0 */ 0x03A0, 0x03A1, 0x03A2, 0x03A3, 0x03A4, 0x03A5, 0x03A6, 0x03A7, 846 /* U+03A8 */ 0x03A8, 0x03A9, 0x0399, 0x03A5, 0x03B1, 0x03B5, 0x03B7, 0x03B9, 847 /* U+03B0 */ 0x03CB, 0x03B1, 0x03B2, 0x03B3, 0x03B4, 0x03B5, 0x03B6, 0x03B7, 848 /* U+03B8 */ 0x03B8, 0x03B9, 0x03BA, 0x03BB, 0x03BC, 0x03BD, 0x03BE, 0x03BF, 849 /* U+03C0 */ 0x03C0, 0x03C1, 0x03C2, 0x03C3, 0x03C4, 0x03C5, 0x03C6, 0x03C7, 850 /* U+03C8 */ 0x03C8, 0x03C9, 0x03B9, 0x03C5, 0x03BF, 0x03C5, 0x03C9, 0x03CF, 851 /* U+03D0 */ 0x03B2, 0x03B8, 0x03A5, 0x03D2, 0x03D2, 0x03C6, 0x03C0, 0x03D7, 852 /* U+03D8 */ 0x03D8, 0x03D9, 0x03DA, 0x03DB, 0x03DC, 0x03DD, 0x03DE, 0x03DF, 853 /* U+03E0 */ 0x03E0, 0x03E1, 0x03E2, 0x03E3, 0x03E4, 0x03E5, 0x03E6, 0x03E7, 854 /* U+03E8 */ 0x03E8, 0x03E9, 0x03EA, 0x03EB, 0x03EC, 0x03ED, 0x03EE, 0x03EF, 855 /* U+03F0 */ 0x03BA, 0x03C1, 0x03C2, 0x03F3, 0x0398, 0x03B5, 0x03F6, 0x03F7, 856 /* U+03F8 */ 0x03F8, 0x03A3, 0x03FA, 0x03FB, 0x03FC, 0x03FD, 0x03FE, 0x03FF, 857 /* U+0400 */ 0x0415, 0x0415, 0x0402, 0x0413, 0x0404, 0x0405, 0x0406, 0x0406, 858 /* U+0408 */ 0x0408, 0x0409, 0x040A, 0x040B, 0x041A, 0x0418, 0x0423, 0x040F, 859 /* U+0410 */ 0x0410, 0x0411, 0x0412, 0x0413, 0x0414, 0x0415, 0x0416, 0x0417, 860 /* U+0418 */ 0x0418, 0x0419, 0x041A, 0x041B, 0x041C, 0x041D, 0x041E, 0x041F, 861 // U+0419: Manually changed from 0418 to 0419 862 /* U+0420 */ 0x0420, 0x0421, 0x0422, 0x0423, 0x0424, 0x0425, 0x0426, 0x0427, 863 /* U+0428 */ 0x0428, 0x0429, 0x042C, 0x042B, 0x042C, 0x042D, 0x042E, 0x042F, 864 // U+042A: Manually changed from 042A to 042C 865 /* U+0430 */ 0x0430, 0x0431, 0x0432, 0x0433, 0x0434, 0x0435, 0x0436, 0x0437, 866 /* U+0438 */ 0x0438, 0x0439, 0x043A, 0x043B, 0x043C, 0x043D, 0x043E, 0x043F, 867 // U+0439: Manually changed from 0438 to 0439 868 /* U+0440 */ 0x0440, 0x0441, 0x0442, 0x0443, 0x0444, 0x0445, 0x0446, 0x0447, 869 /* U+0448 */ 0x0448, 0x0449, 0x044C, 0x044B, 0x044C, 0x044D, 0x044E, 0x044F, 870 // U+044A: Manually changed from 044A to 044C 871 /* U+0450 */ 0x0435, 0x0435, 0x0452, 0x0433, 0x0454, 0x0455, 0x0456, 0x0456, 872 /* U+0458 */ 0x0458, 0x0459, 0x045A, 0x045B, 0x043A, 0x0438, 0x0443, 0x045F, 873 /* U+0460 */ 0x0460, 0x0461, 0x0462, 0x0463, 0x0464, 0x0465, 0x0466, 0x0467, 874 /* U+0468 */ 0x0468, 0x0469, 0x046A, 0x046B, 0x046C, 0x046D, 0x046E, 0x046F, 875 /* U+0470 */ 0x0470, 0x0471, 0x0472, 0x0473, 0x0474, 0x0475, 0x0474, 0x0475, 876 /* U+0478 */ 0x0478, 0x0479, 0x047A, 0x047B, 0x047C, 0x047D, 0x047E, 0x047F, 877 /* U+0480 */ 0x0480, 0x0481, 0x0482, 0x0483, 0x0484, 0x0485, 0x0486, 0x0487, 878 /* U+0488 */ 0x0488, 0x0489, 0x048A, 0x048B, 0x048C, 0x048D, 0x048E, 0x048F, 879 /* U+0490 */ 0x0490, 0x0491, 0x0492, 0x0493, 0x0494, 0x0495, 0x0496, 0x0497, 880 /* U+0498 */ 0x0498, 0x0499, 0x049A, 0x049B, 0x049C, 0x049D, 0x049E, 0x049F, 881 /* U+04A0 */ 0x04A0, 0x04A1, 0x04A2, 0x04A3, 0x04A4, 0x04A5, 0x04A6, 0x04A7, 882 /* U+04A8 */ 0x04A8, 0x04A9, 0x04AA, 0x04AB, 0x04AC, 0x04AD, 0x04AE, 0x04AF, 883 /* U+04B0 */ 0x04B0, 0x04B1, 0x04B2, 0x04B3, 0x04B4, 0x04B5, 0x04B6, 0x04B7, 884 /* U+04B8 */ 0x04B8, 0x04B9, 0x04BA, 0x04BB, 0x04BC, 0x04BD, 0x04BE, 0x04BF, 885 /* U+04C0 */ 0x04C0, 0x0416, 0x0436, 0x04C3, 0x04C4, 0x04C5, 0x04C6, 0x04C7, 886 /* U+04C8 */ 0x04C8, 0x04C9, 0x04CA, 0x04CB, 0x04CC, 0x04CD, 0x04CE, 0x04CF, 887 /* U+04D0 */ 0x0410, 0x0430, 0x0410, 0x0430, 0x04D4, 0x04D5, 0x0415, 0x0435, 888 /* U+04D8 */ 0x04D8, 0x04D9, 0x04D8, 0x04D9, 0x0416, 0x0436, 0x0417, 0x0437, 889 /* U+04E0 */ 0x04E0, 0x04E1, 0x0418, 0x0438, 0x0418, 0x0438, 0x041E, 0x043E, 890 /* U+04E8 */ 0x04E8, 0x04E9, 0x04E8, 0x04E9, 0x042D, 0x044D, 0x0423, 0x0443, 891 /* U+04F0 */ 0x0423, 0x0443, 0x0423, 0x0443, 0x0427, 0x0447, 0x04F6, 0x04F7, 892 /* U+04F8 */ 0x042B, 0x044B, 0x04FA, 0x04FB, 0x04FC, 0x04FD, 0x04FE, 0x04FF, 893 }; 894 } 895
