FusionDictionary.java revision 7cfe20efbeb4a94b15291aee95d0559ae2449c45
1bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard/* 2bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Copyright (C) 2011 The Android Open Source Project 3bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 4bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Licensed under the Apache License, Version 2.0 (the "License"); you may not 5bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * use this file except in compliance with the License. You may obtain a copy of 6bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * the License at 7bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 8bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * http://www.apache.org/licenses/LICENSE-2.0 9bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 10bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Unless required by applicable law or agreed to in writing, software 11bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 12bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 13bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * License for the specific language governing permissions and limitations under 14bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * the License. 15bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 16bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 17cdc51fc6afc7fd374c5c9eeb0539cae5cf1de724Tom Ouyangpackage com.android.inputmethod.latin.makedict; 18bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 19bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalardimport java.util.ArrayList; 20bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalardimport java.util.Arrays; 21bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalardimport java.util.Collections; 22bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalardimport java.util.Iterator; 23bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalardimport java.util.LinkedList; 24bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 25bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard/** 26bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * A dictionary that can fusion heads and tails of words for more compression. 27bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 28bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalardpublic class FusionDictionary implements Iterable<Word> { 29bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 30bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 31bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * A node of the dictionary, containing several CharGroups. 32bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 33bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * A node is but an ordered array of CharGroups, which essentially contain all the 34bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * real information. 35bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This class also contains fields to cache size and address, to help with binary 36bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * generation. 37bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 38bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public static class Node { 39bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard ArrayList<CharGroup> mData; 40bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // To help with binary generation 41bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int mCachedSize; 42bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int mCachedAddress; 43bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public Node() { 44bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mData = new ArrayList<CharGroup>(); 45bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mCachedSize = Integer.MIN_VALUE; 46bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mCachedAddress = Integer.MIN_VALUE; 47bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 48bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public Node(ArrayList<CharGroup> data) { 49bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mData = data; 50bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mCachedSize = Integer.MIN_VALUE; 51bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mCachedAddress = Integer.MIN_VALUE; 52bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 53bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 54bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 55bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 56bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * A string with a frequency. 57bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 58bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This represents an "attribute", that is either a bigram or a shortcut. 59bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 60bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public static class WeightedString { 61bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final String mWord; 627cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang int mFrequency; 63bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public WeightedString(String word, int frequency) { 64bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mWord = word; 65bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mFrequency = frequency; 66bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 67bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 68bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 69bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 70eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard * A group of characters, with a frequency, shortcut targets, bigrams, and children. 71bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 72bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This is the central class of the in-memory representation. A CharGroup is what can 73bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * be seen as a traditional "trie node", except it can hold several characters at the 74bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * same time. A CharGroup essentially represents one or several characters in the middle 75bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * of the trie trie; as such, it can be a terminal, and it can have children. 76bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * In this in-memory representation, whether the CharGroup is a terminal or not is represented 77bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * in the frequency, where NOT_A_TERMINAL (= -1) means this is not a terminal and any other 78bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * value is the frequency of this terminal. A terminal may have non-null shortcuts and/or 79bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * bigrams, but a non-terminal may not. Moreover, children, if present, are null. 80bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 81bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public static class CharGroup { 82bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public static final int NOT_A_TERMINAL = -1; 83bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final int mChars[]; 847cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang ArrayList<WeightedString> mShortcutTargets; 857cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang ArrayList<WeightedString> mBigrams; 867cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang int mFrequency; // NOT_A_TERMINAL == mFrequency indicates this is not a terminal. 877cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang boolean mIsShortcutOnly; // Only valid if this is a terminal. 88bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Node mChildren; 89bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // The two following members to help with binary generation 90bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int mCachedSize; 91bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int mCachedAddress; 92bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 93eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard public CharGroup(final int[] chars, final ArrayList<WeightedString> shortcutTargets, 94903e58886e480d79b37c0f9347771042324e71a9Jean Chalard final ArrayList<WeightedString> bigrams, final int frequency, 95903e58886e480d79b37c0f9347771042324e71a9Jean Chalard final boolean isShortcutOnly) { 96bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mChars = chars; 97bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mFrequency = frequency; 98903e58886e480d79b37c0f9347771042324e71a9Jean Chalard mIsShortcutOnly = isShortcutOnly; 99903e58886e480d79b37c0f9347771042324e71a9Jean Chalard if (mIsShortcutOnly && NOT_A_TERMINAL == mFrequency) { 100903e58886e480d79b37c0f9347771042324e71a9Jean Chalard throw new RuntimeException("A node must be a terminal to be a shortcut only"); 101903e58886e480d79b37c0f9347771042324e71a9Jean Chalard } 102eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard mShortcutTargets = shortcutTargets; 103bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mBigrams = bigrams; 104bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mChildren = null; 105bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 106bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 107eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard public CharGroup(final int[] chars, final ArrayList<WeightedString> shortcutTargets, 108903e58886e480d79b37c0f9347771042324e71a9Jean Chalard final ArrayList<WeightedString> bigrams, final int frequency, final Node children, 109903e58886e480d79b37c0f9347771042324e71a9Jean Chalard final boolean isShortcutOnly) { 110bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mChars = chars; 111bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mFrequency = frequency; 112903e58886e480d79b37c0f9347771042324e71a9Jean Chalard mIsShortcutOnly = isShortcutOnly; 113903e58886e480d79b37c0f9347771042324e71a9Jean Chalard if (mIsShortcutOnly && NOT_A_TERMINAL == mFrequency) { 114903e58886e480d79b37c0f9347771042324e71a9Jean Chalard throw new RuntimeException("A node must be a terminal to be a shortcut only"); 115903e58886e480d79b37c0f9347771042324e71a9Jean Chalard } 116eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard mShortcutTargets = shortcutTargets; 117bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mBigrams = bigrams; 118bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mChildren = children; 119bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 120bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 121bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public void addChild(CharGroup n) { 122bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (null == mChildren) { 123bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mChildren = new Node(); 124bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 125bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mChildren.mData.add(n); 126bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 127bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 128bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public boolean isTerminal() { 129bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return NOT_A_TERMINAL != mFrequency; 130bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 131bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 132bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public boolean hasSeveralChars() { 133bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard assert(mChars.length > 0); 134bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return 1 < mChars.length; 135bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 1367cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang 1377cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang /** 1387cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * Adds a word to the bigram list. Updates the frequency if the word already 1397cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * exists. 1407cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang */ 1417cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang public void addBigram(final String word, final int frequency) { 1427cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (mBigrams == null) { 1437cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang mBigrams = new ArrayList<WeightedString>(); 1447cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 1457cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang WeightedString bigram = getBigram(word); 1467cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (bigram != null) { 1477cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang bigram.mFrequency = frequency; 1487cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } else { 1497cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang bigram = new WeightedString(word, frequency); 1507cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang mBigrams.add(bigram); 1517cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 1527cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 1537cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang 1547cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang /** 1557cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * Gets the shortcut target for the given word. Returns null if the word is not in the 1567cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * shortcut list. 1577cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang */ 1587cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang public WeightedString getShortcut(final String word) { 1597cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (mShortcutTargets != null) { 1607cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang final int size = mShortcutTargets.size(); 1617cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang for (int i = 0; i < size; ++i) { 1627cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang WeightedString shortcut = mShortcutTargets.get(i); 1637cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (shortcut.mWord.equals(word)) { 1647cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang return shortcut; 1657cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 1667cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 1677cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 1687cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang return null; 1697cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 1707cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang 1717cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang /** 1727cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * Gets the bigram for the given word. 1737cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * Returns null if the word is not in the bigrams list. 1747cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang */ 1757cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang public WeightedString getBigram(final String word) { 1767cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (mBigrams != null) { 1777cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang final int size = mBigrams.size(); 1787cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang for (int i = 0; i < size; ++i) { 1797cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang WeightedString bigram = mBigrams.get(i); 1807cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (bigram.mWord.equals(word)) { 1817cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang return bigram; 1827cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 1837cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 1847cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 1857cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang return null; 1867cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 1877cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang 1887cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang /** 1897cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * Updates the CharGroup with the given properties. Adds the shortcut and bigram lists to 1907cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * the existing ones if any. Note: unigram, bigram, and shortcut frequencies are only 1917cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * updated if they are higher than the existing ones. 1927cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang */ 1937cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang public void update(int frequency, ArrayList<WeightedString> shortcutTargets, 1947cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang ArrayList<WeightedString> bigrams, boolean isShortcutOnly) { 1957cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (frequency > mFrequency) { 1967cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang mFrequency = frequency; 1977cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 1987cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (shortcutTargets != null) { 1997cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (mShortcutTargets == null) { 2007cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang mShortcutTargets = shortcutTargets; 2017cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } else { 2027cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang final int size = shortcutTargets.size(); 2037cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang for (int i = 0; i < size; ++i) { 2047cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang final WeightedString shortcut = shortcutTargets.get(i); 2057cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang final WeightedString existingShortcut = getShortcut(shortcut.mWord); 2067cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (existingShortcut == null) { 2077cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang mShortcutTargets.add(shortcut); 2087cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } else if (existingShortcut.mFrequency < shortcut.mFrequency) { 2097cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang existingShortcut.mFrequency = shortcut.mFrequency; 2107cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2117cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2127cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2137cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2147cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (bigrams != null) { 2157cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (mBigrams == null) { 2167cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang mBigrams = bigrams; 2177cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } else { 2187cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang final int size = bigrams.size(); 2197cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang for (int i = 0; i < size; ++i) { 2207cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang final WeightedString bigram = bigrams.get(i); 2217cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang final WeightedString existingBigram = getBigram(bigram.mWord); 2227cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (existingBigram == null) { 2237cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang mBigrams.add(bigram); 2247cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } else if (existingBigram.mFrequency < bigram.mFrequency) { 2257cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang existingBigram.mFrequency = bigram.mFrequency; 2267cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2277cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2287cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2297cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2307cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang mIsShortcutOnly = isShortcutOnly; 2317cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 232bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 233bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 234bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 235bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Options global to the dictionary. 236bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 237bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * There are no options at the moment, so this class is empty. 238bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 239bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public static class DictionaryOptions { 240bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 241bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 242bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 243bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public final DictionaryOptions mOptions; 244bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public final Node mRoot; 245bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 246bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public FusionDictionary() { 247bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mOptions = new DictionaryOptions(); 248bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mRoot = new Node(); 249bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 250bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 251bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public FusionDictionary(final Node root, final DictionaryOptions options) { 252bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mRoot = root; 253bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mOptions = options; 254bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 255bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 256bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 257bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Helper method to convert a String to an int array. 258bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 259bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard static private int[] getCodePoints(String word) { 260bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final int wordLength = word.length(); 261bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int[] array = new int[word.codePointCount(0, wordLength)]; 2629242a2bcf8a6b07bb045a8356711bed1493c251eJean Chalard for (int i = 0; i < wordLength; i = word.offsetByCodePoints(i, 1)) { 263bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard array[i] = word.codePointAt(i); 264bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 265bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return array; 266bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 267bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 268bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 269c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard * Helper method to add all words in a list as 0-frequency entries 270c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard * 271c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard * These words are added when shortcuts targets or bigrams are not found in the dictionary 272c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard * yet. The same words may be added later with an actual frequency - this is handled by 273c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard * the private version of add(). 274c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard */ 275c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard private void addNeutralWords(final ArrayList<WeightedString> words) { 276c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard if (null != words) { 277c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard for (WeightedString word : words) { 278c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard final CharGroup t = findWordInTree(mRoot, word.mWord); 279c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard if (null == t) { 280c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard add(getCodePoints(word.mWord), 0, null, null, false /* isShortcutOnly */); 281c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard } 282c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard } 283c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard } 284c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard } 285c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard 286c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard /** 287bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Helper method to add a word as a string. 288bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 289bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This method adds a word to the dictionary with the given frequency. Optional 290bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * lists of bigrams and shortcuts can be passed here. For each word inside, 291bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * they will be added to the dictionary as necessary. 292bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 293bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param word the word to add. 294bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param frequency the frequency of the word, in the range [0..255]. 295eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard * @param shortcutTargets a list of shortcut targets for this word, or null. 296bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param bigrams a list of bigrams, or null. 297bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 298eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard public void add(final String word, final int frequency, 299eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard final ArrayList<WeightedString> shortcutTargets, 300eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard final ArrayList<WeightedString> bigrams) { 301eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard if (null != shortcutTargets) { 302c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard addNeutralWords(shortcutTargets); 303eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard } 304bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (null != bigrams) { 305c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard addNeutralWords(bigrams); 306bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 307c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard add(getCodePoints(word), frequency, shortcutTargets, bigrams, false /* isShortcutOnly */); 308bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 309bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 310bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 311bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Sanity check for a node. 312bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 313bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This method checks that all CharGroups in a node are ordered as expected. 314bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * If they are, nothing happens. If they aren't, an exception is thrown. 315bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 316bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard private void checkStack(Node node) { 317bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard ArrayList<CharGroup> stack = node.mData; 318bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int lastValue = -1; 319bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard for (int i = 0; i < stack.size(); ++i) { 320bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int currentValue = stack.get(i).mChars[0]; 321bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (currentValue <= lastValue) 322bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard throw new RuntimeException("Invalid stack"); 323bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard else 324bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard lastValue = currentValue; 325bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 326bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 327bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 328bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 329c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard * Helper method to add a shortcut that should not be a dictionary word. 330c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard * 331c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard * @param word the word to add. 332c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard * @param frequency the frequency of the word, in the range [0..255]. 333c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard * @param shortcutTargets a list of shortcut targets. May not be null. 334c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard */ 335c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard public void addShortcutOnly(final String word, final int frequency, 336c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard final ArrayList<WeightedString> shortcutTargets) { 337c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard if (null == shortcutTargets) { 338c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard throw new RuntimeException("Can't add a shortcut without targets"); 339c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard } 340c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard addNeutralWords(shortcutTargets); 341c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard add(getCodePoints(word), frequency, shortcutTargets, null, true /* isShortcutOnly */); 342c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard } 343c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard 344c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard /** 3457cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * Helper method to add a new bigram to the dictionary. 3467cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * 3477cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * @param word1 the previous word of the context 3487cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * @param word2 the next word of the context 3497cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * @param frequency the bigram frequency 3507cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang */ 3517cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang public void setBigram(final String word1, final String word2, final int frequency) { 3527cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang CharGroup charGroup = findWordInTree(mRoot, word1); 3537cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (charGroup != null) { 3547cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang final CharGroup charGroup2 = findWordInTree(mRoot, word2); 3557cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (charGroup2 == null) { 3567cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang // TODO: refactor with the identical code in addNeutralWords 3577cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang add(getCodePoints(word2), 0, null, null, false /* isShortcutOnly */); 3587cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 3597cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang charGroup.addBigram(word2, frequency); 3607cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } else { 3617cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang throw new RuntimeException("First word of bigram not found"); 3627cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 3637cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 3647cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang 3657cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang /** 366bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Add a word to this dictionary. 367bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 368eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard * The shortcuts and bigrams, if any, have to be in the dictionary already. If they aren't, 369bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * an exception is thrown. 370bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 371bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param word the word, as an int array. 372bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param frequency the frequency of the word, in the range [0..255]. 373eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard * @param shortcutTargets an optional list of shortcut targets for this word (null if none). 374bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param bigrams an optional list of bigrams for this word (null if none). 375c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard * @param isShortcutOnly whether this should be a shortcut only. 376bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 377eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard private void add(final int[] word, final int frequency, 378eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard final ArrayList<WeightedString> shortcutTargets, 379c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard final ArrayList<WeightedString> bigrams, 380c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard final boolean isShortcutOnly) { 381bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard assert(frequency >= 0 && frequency <= 255); 382bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Node currentNode = mRoot; 383bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int charIndex = 0; 384bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 385bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard CharGroup currentGroup = null; 386bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int differentCharIndex = 0; // Set by the loop to the index of the char that differs 387bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int nodeIndex = findIndexOfChar(mRoot, word[charIndex]); 388bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard while (CHARACTER_NOT_FOUND != nodeIndex) { 389bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentGroup = currentNode.mData.get(nodeIndex); 390cad25fc8a754d6f145bc846f17f270220b15c055Jean Chalard differentCharIndex = compareArrays(currentGroup.mChars, word, charIndex); 391bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (ARRAYS_ARE_EQUAL != differentCharIndex 392bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard && differentCharIndex < currentGroup.mChars.length) break; 393bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (null == currentGroup.mChildren) break; 394bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard charIndex += currentGroup.mChars.length; 395bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (charIndex >= word.length) break; 396bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentNode = currentGroup.mChildren; 397bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard nodeIndex = findIndexOfChar(currentNode, word[charIndex]); 398bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 399bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 400bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (-1 == nodeIndex) { 401bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // No node at this point to accept the word. Create one. 402bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final int insertionIndex = findInsertionIndex(currentNode, word[charIndex]); 403bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup newGroup = new CharGroup( 404eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard Arrays.copyOfRange(word, charIndex, word.length), 405c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard shortcutTargets, bigrams, frequency, isShortcutOnly); 406bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentNode.mData.add(insertionIndex, newGroup); 407bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard checkStack(currentNode); 408bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } else { 409bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // There is a word with a common prefix. 410bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (differentCharIndex == currentGroup.mChars.length) { 411bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (charIndex + differentCharIndex >= word.length) { 412bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // The new word is a prefix of an existing word, but the node on which it 4137cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang // should end already exists as is. Since the old CharNode was not a terminal, 4147cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang // make it one by filling in its frequency and other attributes 4157cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang currentGroup.update(frequency, shortcutTargets, bigrams, isShortcutOnly); 416bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } else { 417bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // The new word matches the full old word and extends past it. 418bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // We only have to create a new node and add it to the end of this. 419bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup newNode = new CharGroup( 420bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Arrays.copyOfRange(word, charIndex + differentCharIndex, word.length), 421c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard shortcutTargets, bigrams, frequency, isShortcutOnly); 422bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentGroup.mChildren = new Node(); 423bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentGroup.mChildren.mData.add(newNode); 424bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 425bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } else { 426bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (0 == differentCharIndex) { 4277cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang // Exact same word. Update the frequency if higher. This will also add the 4287cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang // new bigrams to the existing bigram list if it already exists. 4297cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang currentGroup.update(frequency, shortcutTargets, bigrams, isShortcutOnly); 430bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } else { 431bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // Partial prefix match only. We have to replace the current node with a node 432bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // containing the current prefix and create two new ones for the tails. 433bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Node newChildren = new Node(); 434bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup newOldWord = new CharGroup( 435bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Arrays.copyOfRange(currentGroup.mChars, differentCharIndex, 436eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard currentGroup.mChars.length), currentGroup.mShortcutTargets, 437903e58886e480d79b37c0f9347771042324e71a9Jean Chalard currentGroup.mBigrams, currentGroup.mFrequency, currentGroup.mChildren, 438903e58886e480d79b37c0f9347771042324e71a9Jean Chalard currentGroup.mIsShortcutOnly); 439bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard newChildren.mData.add(newOldWord); 440bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 441bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup newParent; 442bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (charIndex + differentCharIndex >= word.length) { 443bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard newParent = new CharGroup( 444bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Arrays.copyOfRange(currentGroup.mChars, 0, differentCharIndex), 445c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard shortcutTargets, bigrams, frequency, newChildren, isShortcutOnly); 446bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } else { 447c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard // isShortcutOnly makes no sense for non-terminal nodes. The following node 448c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard // is non-terminal (frequency 0 in FusionDictionary representation) so we 449c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard // pass false for isShortcutOnly 450bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard newParent = new CharGroup( 451bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Arrays.copyOfRange(currentGroup.mChars, 0, differentCharIndex), 452903e58886e480d79b37c0f9347771042324e71a9Jean Chalard null, null, -1, newChildren, false /* isShortcutOnly */); 453bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup newWord = new CharGroup( 454bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Arrays.copyOfRange(word, charIndex + differentCharIndex, 455903e58886e480d79b37c0f9347771042324e71a9Jean Chalard word.length), shortcutTargets, bigrams, frequency, 456c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard isShortcutOnly); 457bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final int addIndex = word[charIndex + differentCharIndex] 458bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard > currentGroup.mChars[differentCharIndex] ? 1 : 0; 459bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard newChildren.mData.add(addIndex, newWord); 460bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 461bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentNode.mData.set(nodeIndex, newParent); 462bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 463bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard checkStack(currentNode); 464bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 465bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 466bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 467bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 468bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 469bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Custom comparison of two int arrays taken to contain character codes. 470bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 471bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This method compares the two arrays passed as an argument in a lexicographic way, 472bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * with an offset in the dst string. 473bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This method does NOT test for the first character. It is taken to be equal. 474bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * I repeat: this method starts the comparison at 1 <> dstOffset + 1. 475bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * The index where the strings differ is returned. ARRAYS_ARE_EQUAL = 0 is returned if the 476bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * strings are equal. This works BECAUSE we don't look at the first character. 477bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 478bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param src the left-hand side string of the comparison. 479bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param dst the right-hand side string of the comparison. 480bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param dstOffset the offset in the right-hand side string. 481bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @return the index at which the strings differ, or ARRAYS_ARE_EQUAL = 0 if they don't. 482bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 483bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard private static int ARRAYS_ARE_EQUAL = 0; 484bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard private static int compareArrays(final int[] src, final int[] dst, int dstOffset) { 485bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // We do NOT test the first char, because we come from a method that already 486bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // tested it. 487bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard for (int i = 1; i < src.length; ++i) { 488bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (dstOffset + i >= dst.length) return i; 489bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (src[i] != dst[dstOffset + i]) return i; 490bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 491bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (dst.length > src.length) return src.length; 492bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return ARRAYS_ARE_EQUAL; 493bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 494bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 495bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 496bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Helper class that compares and sorts two chargroups according to their 497bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * first element only. I repeat: ONLY the first element is considered, the rest 498bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * is ignored. 499bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This comparator imposes orderings that are inconsistent with equals. 500bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 5012aa02b84a4fcfaf5554c278d2b25cf9414eecf8bKen Wakasa static private class CharGroupComparator implements java.util.Comparator<CharGroup> { 5022aa02b84a4fcfaf5554c278d2b25cf9414eecf8bKen Wakasa public int compare(CharGroup c1, CharGroup c2) { 503bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (c1.mChars[0] == c2.mChars[0]) return 0; 504bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return c1.mChars[0] < c2.mChars[0] ? -1 : 1; 505bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 506bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 507bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final static private CharGroupComparator CHARGROUP_COMPARATOR = new CharGroupComparator(); 508bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 509bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 510bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Finds the insertion index of a character within a node. 511bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 512bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard private static int findInsertionIndex(final Node node, int character) { 5132aa02b84a4fcfaf5554c278d2b25cf9414eecf8bKen Wakasa final ArrayList<CharGroup> data = node.mData; 514903e58886e480d79b37c0f9347771042324e71a9Jean Chalard final CharGroup reference = new CharGroup(new int[] { character }, null, null, 0, 515903e58886e480d79b37c0f9347771042324e71a9Jean Chalard false /* isShortcutOnly */); 516bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int result = Collections.binarySearch(data, reference, CHARGROUP_COMPARATOR); 517bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return result >= 0 ? result : -result - 1; 518bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 519bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 520bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 521bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Find the index of a char in a node, if it exists. 522bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 523bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param node the node to search in. 524bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param character the character to search for. 525bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @return the position of the character if it's there, or CHARACTER_NOT_FOUND = -1 else. 526bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 527bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard private static int CHARACTER_NOT_FOUND = -1; 528bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard private static int findIndexOfChar(final Node node, int character) { 529bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final int insertionIndex = findInsertionIndex(node, character); 530bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (node.mData.size() <= insertionIndex) return CHARACTER_NOT_FOUND; 531bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return character == node.mData.get(insertionIndex).mChars[0] ? insertionIndex 532bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard : CHARACTER_NOT_FOUND; 533bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 534bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 535bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 536bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Helper method to find a word in a given branch. 537bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 538bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public static CharGroup findWordInTree(Node node, final String s) { 539bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int index = 0; 540bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final StringBuilder checker = new StringBuilder(); 541bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 542bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard CharGroup currentGroup; 543bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard do { 544bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int indexOfGroup = findIndexOfChar(node, s.codePointAt(index)); 545bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (CHARACTER_NOT_FOUND == indexOfGroup) return null; 546bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentGroup = node.mData.get(indexOfGroup); 547bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard checker.append(new String(currentGroup.mChars, 0, currentGroup.mChars.length)); 548bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard index += currentGroup.mChars.length; 549bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (index < s.length()) { 550bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard node = currentGroup.mChildren; 551bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 552bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } while (null != node && index < s.length()); 553bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 554bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (!s.equals(checker.toString())) return null; 555bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return currentGroup; 556bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 557bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 558bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 559eddfbb68dcff55c85b3d5b82d406f543bd038825Jean Chalard * Helper method to find out whether a word is in the dict or not. 560eddfbb68dcff55c85b3d5b82d406f543bd038825Jean Chalard */ 561eddfbb68dcff55c85b3d5b82d406f543bd038825Jean Chalard public boolean hasWord(final String s) { 562eddfbb68dcff55c85b3d5b82d406f543bd038825Jean Chalard if (null == s || "".equals(s)) { 563eddfbb68dcff55c85b3d5b82d406f543bd038825Jean Chalard throw new RuntimeException("Can't search for a null or empty string"); 564eddfbb68dcff55c85b3d5b82d406f543bd038825Jean Chalard } 565eddfbb68dcff55c85b3d5b82d406f543bd038825Jean Chalard return null != findWordInTree(mRoot, s); 566eddfbb68dcff55c85b3d5b82d406f543bd038825Jean Chalard } 567eddfbb68dcff55c85b3d5b82d406f543bd038825Jean Chalard 568eddfbb68dcff55c85b3d5b82d406f543bd038825Jean Chalard /** 569bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Recursively count the number of character groups in a given branch of the trie. 570bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 571bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param node the parent node. 572bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @return the number of char groups in all the branch under this node. 573bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 574bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public static int countCharGroups(final Node node) { 575bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final int nodeSize = node.mData.size(); 576bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int size = nodeSize; 577bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard for (int i = nodeSize - 1; i >= 0; --i) { 578bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard CharGroup group = node.mData.get(i); 579bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (null != group.mChildren) 580bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard size += countCharGroups(group.mChildren); 581bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 582bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return size; 583bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 584bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 585bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 586bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Recursively count the number of nodes in a given branch of the trie. 587bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 588bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param node the node to count. 589bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @result the number of nodes in this branch. 590bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 591bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public static int countNodes(final Node node) { 592bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int size = 1; 593bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard for (int i = node.mData.size() - 1; i >= 0; --i) { 594bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard CharGroup group = node.mData.get(i); 595bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (null != group.mChildren) 596bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard size += countNodes(group.mChildren); 597bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 598bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return size; 599bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 600bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 601bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // Historically, the tails of the words were going to be merged to save space. 602bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // However, that would prevent the code to search for a specific address in log(n) 603bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // time so this was abandoned. 604bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // The code is still of interest as it does add some compression to any dictionary 605bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // that has no need for attributes. Implementations that does not read attributes should be 606bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // able to read a dictionary with merged tails. 607bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // Also, the following code does support frequencies, as in, it will only merges 608bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // tails that share the same frequency. Though it would result in the above loss of 609bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // performance while searching by address, it is still technically possible to merge 610bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // tails that contain attributes, but this code does not take that into account - it does 611bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // not compare attributes and will merge terminals with different attributes regardless. 612bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public void mergeTails() { 613bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard MakedictLog.i("Do not merge tails"); 614bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return; 615bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 616bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// MakedictLog.i("Merging nodes. Number of nodes : " + countNodes(root)); 617bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// MakedictLog.i("Number of groups : " + countCharGroups(root)); 618bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// 619bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// final HashMap<String, ArrayList<Node>> repository = 620bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// new HashMap<String, ArrayList<Node>>(); 621bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// mergeTailsInner(repository, root); 622bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// 623bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// MakedictLog.i("Number of different pseudohashes : " + repository.size()); 624bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// int size = 0; 625bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// for (ArrayList<Node> a : repository.values()) { 626bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// size += a.size(); 627bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 628bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// MakedictLog.i("Number of nodes after merge : " + (1 + size)); 629bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// MakedictLog.i("Recursively seen nodes : " + countNodes(root)); 630bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 631bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 632bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // The following methods are used by the deactivated mergeTails() 633bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// private static boolean isEqual(Node a, Node b) { 634bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (null == a && null == b) return true; 635bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (null == a || null == b) return false; 636bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (a.data.size() != b.data.size()) return false; 637bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// final int size = a.data.size(); 638bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// for (int i = size - 1; i >= 0; --i) { 639bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// CharGroup aGroup = a.data.get(i); 640bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// CharGroup bGroup = b.data.get(i); 641bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (aGroup.frequency != bGroup.frequency) return false; 642bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (aGroup.alternates == null && bGroup.alternates != null) return false; 643bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (aGroup.alternates != null && !aGroup.equals(bGroup.alternates)) return false; 644bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (!Arrays.equals(aGroup.chars, bGroup.chars)) return false; 645bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (!isEqual(aGroup.children, bGroup.children)) return false; 646bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 647bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// return true; 648bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 649bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 650bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// static private HashMap<String, ArrayList<Node>> mergeTailsInner( 651bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// final HashMap<String, ArrayList<Node>> map, final Node node) { 652bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// final ArrayList<CharGroup> branches = node.data; 653bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// final int nodeSize = branches.size(); 654bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// for (int i = 0; i < nodeSize; ++i) { 655bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// CharGroup group = branches.get(i); 656bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (null != group.children) { 657bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// String pseudoHash = getPseudoHash(group.children); 658bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// ArrayList<Node> similarList = map.get(pseudoHash); 659bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (null == similarList) { 660bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// similarList = new ArrayList<Node>(); 661bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// map.put(pseudoHash, similarList); 662bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 663bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// boolean merged = false; 664bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// for (Node similar : similarList) { 665bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (isEqual(group.children, similar)) { 666bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// group.children = similar; 667bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// merged = true; 668bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// break; 669bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 670bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 671bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (!merged) { 672bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// similarList.add(group.children); 673bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 674bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// mergeTailsInner(map, group.children); 675bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 676bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 677bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// return map; 678bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 679bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 680bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// private static String getPseudoHash(final Node node) { 681bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// StringBuilder s = new StringBuilder(); 682bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// for (CharGroup g : node.data) { 683bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// s.append(g.frequency); 684bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// for (int ch : g.chars){ 685bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// s.append(Character.toChars(ch)); 686bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 687bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 688bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// return s.toString(); 689bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 690bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 691bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 692bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Iterator to walk through a dictionary. 693bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 694bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This is purely for convenience. 695bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 696bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public static class DictionaryIterator implements Iterator<Word> { 697bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 698bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard private static class Position { 699bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public Iterator<CharGroup> pos; 700bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public int length; 701bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public Position(ArrayList<CharGroup> groups) { 702bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard pos = groups.iterator(); 703bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard length = 0; 704bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 705bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 706bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final StringBuilder mCurrentString; 707bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final LinkedList<Position> mPositions; 708bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 709bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public DictionaryIterator(ArrayList<CharGroup> root) { 710bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mCurrentString = new StringBuilder(); 711bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mPositions = new LinkedList<Position>(); 712bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final Position rootPos = new Position(root); 713bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mPositions.add(rootPos); 714bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 715bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 716bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard @Override 717bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public boolean hasNext() { 718bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard for (Position p : mPositions) { 719bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (p.pos.hasNext()) { 720bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return true; 721bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 722bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 723bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return false; 724bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 725bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 726bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard @Override 727bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public Word next() { 728bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Position currentPos = mPositions.getLast(); 729bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mCurrentString.setLength(mCurrentString.length() - currentPos.length); 730bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 731bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard do { 732bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (currentPos.pos.hasNext()) { 733bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup currentGroup = currentPos.pos.next(); 734bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentPos.length = currentGroup.mChars.length; 735bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard for (int i : currentGroup.mChars) 736bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mCurrentString.append(Character.toChars(i)); 737bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (null != currentGroup.mChildren) { 738bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentPos = new Position(currentGroup.mChildren.mData); 739bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mPositions.addLast(currentPos); 740bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 741bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (currentGroup.mFrequency >= 0) 742bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return new Word(mCurrentString.toString(), currentGroup.mFrequency, 7436145b7352398989be3f2bc9eb974013b0039a3a4Jean Chalard currentGroup.mShortcutTargets, currentGroup.mBigrams, 7446145b7352398989be3f2bc9eb974013b0039a3a4Jean Chalard currentGroup.mIsShortcutOnly); 745bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } else { 746bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mPositions.removeLast(); 747bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentPos = mPositions.getLast(); 748bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mCurrentString.setLength(mCurrentString.length() - mPositions.getLast().length); 749bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 750bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } while(true); 751bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 752bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 753bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard @Override 754bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public void remove() { 755bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard throw new UnsupportedOperationException("Unsupported yet"); 756bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 757bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 758bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 759bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 760bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 761bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Method to return an iterator. 762bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 763bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This method enables Java's enhanced for loop. With this you can have a FusionDictionary x 764bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * and say : for (Word w : x) {} 765bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 766bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard @Override 767bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public Iterator<Word> iterator() { 768bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return new DictionaryIterator(mRoot.mData); 769bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 770bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard} 771