FusionDictionary.java revision b6ca354431367b625daf9fff5fbe4b1f5ef996ab
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 19b6ca354431367b625daf9fff5fbe4b1f5ef996abKen Wakasaimport com.android.inputmethod.annotations.UsedForTesting; 20eae7b293e4a854819aa0de663066cd0b6cdd52e7Yuichiro Hanadaimport com.android.inputmethod.latin.Constants; 21eae7b293e4a854819aa0de663066cd0b6cdd52e7Yuichiro Hanada 22bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalardimport java.util.ArrayList; 23bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalardimport java.util.Arrays; 24bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalardimport java.util.Collections; 2547cac57e4593f47e753410e4199e84e458d6de6fJean Chalardimport java.util.Date; 26c734c2aca1830643d169fd292e0c9d4d9306af5aJean Chalardimport java.util.HashMap; 27bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalardimport java.util.Iterator; 28bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalardimport java.util.LinkedList; 29bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 30bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard/** 31bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * A dictionary that can fusion heads and tails of words for more compression. 32bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 33b6ca354431367b625daf9fff5fbe4b1f5ef996abKen Wakasa@UsedForTesting 34a28a05e971cc242b338331a3b78276fa95188d19Tadashi G. Takaokapublic final class FusionDictionary implements Iterable<Word> { 3547db0be7cbdb8abafc18c1e49b71f6dac0d46994Jean Chalard private static final boolean DBG = MakedictLog.DBG; 3647db0be7cbdb8abafc18c1e49b71f6dac0d46994Jean Chalard 37bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 38bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * A node of the dictionary, containing several CharGroups. 39bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 40bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * A node is but an ordered array of CharGroups, which essentially contain all the 41bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * real information. 42bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This class also contains fields to cache size and address, to help with binary 43bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * generation. 44bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 45a28a05e971cc242b338331a3b78276fa95188d19Tadashi G. Takaoka public static final class Node { 46bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard ArrayList<CharGroup> mData; 47bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // To help with binary generation 48e55b644aefbefb4ac79308c9a59116e69a9c53a2Yuichiro Hanada int mCachedSize = Integer.MIN_VALUE; 49e55b644aefbefb4ac79308c9a59116e69a9c53a2Yuichiro Hanada int mCachedAddress = Integer.MIN_VALUE; 50e55b644aefbefb4ac79308c9a59116e69a9c53a2Yuichiro Hanada int mCachedParentAddress = 0; 51e55b644aefbefb4ac79308c9a59116e69a9c53a2Yuichiro Hanada 52bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public Node() { 53bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mData = new ArrayList<CharGroup>(); 54bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 55bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public Node(ArrayList<CharGroup> data) { 56bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mData = data; 57bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 58bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 59bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 60bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 61bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * A string with a frequency. 62bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 63bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This represents an "attribute", that is either a bigram or a shortcut. 64bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 65a28a05e971cc242b338331a3b78276fa95188d19Tadashi G. Takaoka public static final class WeightedString { 6654e84a00fc032ba566cbda41feafa71de77e1c43Jean Chalard public final String mWord; 6754e84a00fc032ba566cbda41feafa71de77e1c43Jean Chalard public int mFrequency; 68bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public WeightedString(String word, int frequency) { 69bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mWord = word; 70bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mFrequency = frequency; 71bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 729f0ea52a5db9710df6bef4672d8e193c48451df0Ken Wakasa 739f0ea52a5db9710df6bef4672d8e193c48451df0Ken Wakasa @Override 749f0ea52a5db9710df6bef4672d8e193c48451df0Ken Wakasa public int hashCode() { 759f0ea52a5db9710df6bef4672d8e193c48451df0Ken Wakasa return Arrays.hashCode(new Object[] { mWord, mFrequency }); 769f0ea52a5db9710df6bef4672d8e193c48451df0Ken Wakasa } 779f0ea52a5db9710df6bef4672d8e193c48451df0Ken Wakasa 789f0ea52a5db9710df6bef4672d8e193c48451df0Ken Wakasa @Override 799f0ea52a5db9710df6bef4672d8e193c48451df0Ken Wakasa public boolean equals(Object o) { 809f0ea52a5db9710df6bef4672d8e193c48451df0Ken Wakasa if (o == this) return true; 819f0ea52a5db9710df6bef4672d8e193c48451df0Ken Wakasa if (!(o instanceof WeightedString)) return false; 829f0ea52a5db9710df6bef4672d8e193c48451df0Ken Wakasa WeightedString w = (WeightedString)o; 839f0ea52a5db9710df6bef4672d8e193c48451df0Ken Wakasa return mWord.equals(w.mWord) && mFrequency == w.mFrequency; 849f0ea52a5db9710df6bef4672d8e193c48451df0Ken Wakasa } 85bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 86bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 87bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 88eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard * A group of characters, with a frequency, shortcut targets, bigrams, and children. 89bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 90bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This is the central class of the in-memory representation. A CharGroup is what can 91bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * be seen as a traditional "trie node", except it can hold several characters at the 92bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * same time. A CharGroup essentially represents one or several characters in the middle 93bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * of the trie trie; as such, it can be a terminal, and it can have children. 94bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * In this in-memory representation, whether the CharGroup is a terminal or not is represented 95bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * in the frequency, where NOT_A_TERMINAL (= -1) means this is not a terminal and any other 96bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * value is the frequency of this terminal. A terminal may have non-null shortcuts and/or 97bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * bigrams, but a non-terminal may not. Moreover, children, if present, are null. 98bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 99a28a05e971cc242b338331a3b78276fa95188d19Tadashi G. Takaoka public static final class CharGroup { 100bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public static final int NOT_A_TERMINAL = -1; 101bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final int mChars[]; 1027cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang ArrayList<WeightedString> mShortcutTargets; 1037cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang ArrayList<WeightedString> mBigrams; 1047cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang int mFrequency; // NOT_A_TERMINAL == mFrequency indicates this is not a terminal. 105bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Node mChildren; 10672b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard boolean mIsNotAWord; // Only a shortcut 10772b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard boolean mIsBlacklistEntry; 108bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // The two following members to help with binary generation 109bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int mCachedSize; 110bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int mCachedAddress; 111bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 112eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard public CharGroup(final int[] chars, final ArrayList<WeightedString> shortcutTargets, 11372b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard final ArrayList<WeightedString> bigrams, final int frequency, 11472b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard final boolean isNotAWord, final boolean isBlacklistEntry) { 115bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mChars = chars; 116bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mFrequency = frequency; 117eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard mShortcutTargets = shortcutTargets; 118bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mBigrams = bigrams; 119bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mChildren = null; 12072b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard mIsNotAWord = isNotAWord; 12172b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard mIsBlacklistEntry = isBlacklistEntry; 122bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 123bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 124eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard public CharGroup(final int[] chars, final ArrayList<WeightedString> shortcutTargets, 12572b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard final ArrayList<WeightedString> bigrams, final int frequency, 12672b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard final boolean isNotAWord, final boolean isBlacklistEntry, final Node children) { 127bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mChars = chars; 128bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mFrequency = frequency; 129eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard mShortcutTargets = shortcutTargets; 130bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mBigrams = bigrams; 131bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mChildren = children; 13272b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard mIsNotAWord = isNotAWord; 13372b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard mIsBlacklistEntry = isBlacklistEntry; 134bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 135bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 136bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public void addChild(CharGroup n) { 137bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (null == mChildren) { 138bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mChildren = new Node(); 139bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 140bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mChildren.mData.add(n); 141bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 142bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 143bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public boolean isTerminal() { 144bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return NOT_A_TERMINAL != mFrequency; 145bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 146bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 147b3c98901c5fc1460b54cdf27d74405f27c88e74bJean Chalard public int getFrequency() { 148b3c98901c5fc1460b54cdf27d74405f27c88e74bJean Chalard return mFrequency; 149b3c98901c5fc1460b54cdf27d74405f27c88e74bJean Chalard } 150b3c98901c5fc1460b54cdf27d74405f27c88e74bJean Chalard 151a23e3330798a3ade6d2f4f5a94b71746feb1b948Jean Chalard public boolean getIsNotAWord() { 152a23e3330798a3ade6d2f4f5a94b71746feb1b948Jean Chalard return mIsNotAWord; 153a23e3330798a3ade6d2f4f5a94b71746feb1b948Jean Chalard } 154a23e3330798a3ade6d2f4f5a94b71746feb1b948Jean Chalard 155a23e3330798a3ade6d2f4f5a94b71746feb1b948Jean Chalard public boolean getIsBlacklistEntry() { 156a23e3330798a3ade6d2f4f5a94b71746feb1b948Jean Chalard return mIsBlacklistEntry; 157a23e3330798a3ade6d2f4f5a94b71746feb1b948Jean Chalard } 158a23e3330798a3ade6d2f4f5a94b71746feb1b948Jean Chalard 159a23e3330798a3ade6d2f4f5a94b71746feb1b948Jean Chalard public ArrayList<WeightedString> getShortcutTargets() { 160a23e3330798a3ade6d2f4f5a94b71746feb1b948Jean Chalard // We don't want write permission to escape outside the package, so we return a copy 161a23e3330798a3ade6d2f4f5a94b71746feb1b948Jean Chalard if (null == mShortcutTargets) return null; 162f41389a74b02a01f7383b1a872db5fa65e81fa1eJean Chalard final ArrayList<WeightedString> copyOfShortcutTargets = 163f41389a74b02a01f7383b1a872db5fa65e81fa1eJean Chalard new ArrayList<WeightedString>(mShortcutTargets); 164a23e3330798a3ade6d2f4f5a94b71746feb1b948Jean Chalard return copyOfShortcutTargets; 165a23e3330798a3ade6d2f4f5a94b71746feb1b948Jean Chalard } 166a23e3330798a3ade6d2f4f5a94b71746feb1b948Jean Chalard 167a23e3330798a3ade6d2f4f5a94b71746feb1b948Jean Chalard public ArrayList<WeightedString> getBigrams() { 168a23e3330798a3ade6d2f4f5a94b71746feb1b948Jean Chalard // We don't want write permission to escape outside the package, so we return a copy 169a23e3330798a3ade6d2f4f5a94b71746feb1b948Jean Chalard if (null == mBigrams) return null; 170f41389a74b02a01f7383b1a872db5fa65e81fa1eJean Chalard final ArrayList<WeightedString> copyOfBigrams = new ArrayList<WeightedString>(mBigrams); 171a23e3330798a3ade6d2f4f5a94b71746feb1b948Jean Chalard return copyOfBigrams; 172a23e3330798a3ade6d2f4f5a94b71746feb1b948Jean Chalard } 173a23e3330798a3ade6d2f4f5a94b71746feb1b948Jean Chalard 174bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public boolean hasSeveralChars() { 175bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard assert(mChars.length > 0); 176bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return 1 < mChars.length; 177bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 1787cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang 1797cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang /** 1807cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * Adds a word to the bigram list. Updates the frequency if the word already 1817cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * exists. 1827cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang */ 1837cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang public void addBigram(final String word, final int frequency) { 1847cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (mBigrams == null) { 1857cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang mBigrams = new ArrayList<WeightedString>(); 1867cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 1877cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang WeightedString bigram = getBigram(word); 1887cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (bigram != null) { 1897cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang bigram.mFrequency = frequency; 1907cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } else { 1917cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang bigram = new WeightedString(word, frequency); 1927cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang mBigrams.add(bigram); 1937cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 1947cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 1957cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang 1967cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang /** 1977cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * Gets the shortcut target for the given word. Returns null if the word is not in the 1987cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * shortcut list. 1997cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang */ 2007cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang public WeightedString getShortcut(final String word) { 20147db0be7cbdb8abafc18c1e49b71f6dac0d46994Jean Chalard // TODO: Don't do a linear search 2027cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (mShortcutTargets != null) { 2037cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang final int size = mShortcutTargets.size(); 2047cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang for (int i = 0; i < size; ++i) { 2057cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang WeightedString shortcut = mShortcutTargets.get(i); 2067cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (shortcut.mWord.equals(word)) { 2077cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang return shortcut; 2087cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2097cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2107cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2117cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang return null; 2127cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2137cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang 2147cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang /** 2157cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * Gets the bigram for the given word. 2167cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * Returns null if the word is not in the bigrams list. 2177cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang */ 2187cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang public WeightedString getBigram(final String word) { 21947db0be7cbdb8abafc18c1e49b71f6dac0d46994Jean Chalard // TODO: Don't do a linear search 2207cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (mBigrams != null) { 2217cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang final int size = mBigrams.size(); 2227cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang for (int i = 0; i < size; ++i) { 2237cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang WeightedString bigram = mBigrams.get(i); 2247cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (bigram.mWord.equals(word)) { 2257cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang return bigram; 2267cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2277cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2287cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2297cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang return null; 2307cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2317cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang 2327cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang /** 2337cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * Updates the CharGroup with the given properties. Adds the shortcut and bigram lists to 2347cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * the existing ones if any. Note: unigram, bigram, and shortcut frequencies are only 2357cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * updated if they are higher than the existing ones. 2367cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang */ 23772b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard public void update(final int frequency, final ArrayList<WeightedString> shortcutTargets, 23872b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard final ArrayList<WeightedString> bigrams, 23972b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard final boolean isNotAWord, final boolean isBlacklistEntry) { 2407cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (frequency > mFrequency) { 2417cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang mFrequency = frequency; 2427cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2437cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (shortcutTargets != null) { 2447cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (mShortcutTargets == null) { 2457cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang mShortcutTargets = shortcutTargets; 2467cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } else { 2477cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang final int size = shortcutTargets.size(); 2487cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang for (int i = 0; i < size; ++i) { 2497cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang final WeightedString shortcut = shortcutTargets.get(i); 2507cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang final WeightedString existingShortcut = getShortcut(shortcut.mWord); 2517cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (existingShortcut == null) { 2527cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang mShortcutTargets.add(shortcut); 2537cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } else if (existingShortcut.mFrequency < shortcut.mFrequency) { 2547cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang existingShortcut.mFrequency = shortcut.mFrequency; 2557cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2567cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2577cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2587cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2597cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (bigrams != null) { 2607cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (mBigrams == null) { 2617cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang mBigrams = bigrams; 2627cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } else { 2637cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang final int size = bigrams.size(); 2647cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang for (int i = 0; i < size; ++i) { 2657cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang final WeightedString bigram = bigrams.get(i); 2667cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang final WeightedString existingBigram = getBigram(bigram.mWord); 2677cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (existingBigram == null) { 2687cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang mBigrams.add(bigram); 2697cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } else if (existingBigram.mFrequency < bigram.mFrequency) { 2707cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang existingBigram.mFrequency = bigram.mFrequency; 2717cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2727cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2737cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 2747cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 27572b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard mIsNotAWord = isNotAWord; 27672b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard mIsBlacklistEntry = isBlacklistEntry; 2777cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 278bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 279bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 280bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 281bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Options global to the dictionary. 282bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 283a28a05e971cc242b338331a3b78276fa95188d19Tadashi G. Takaoka public static final class DictionaryOptions { 284f420df28233c26e555d203185fb292e83b94b8c3Jean Chalard public final boolean mGermanUmlautProcessing; 285f420df28233c26e555d203185fb292e83b94b8c3Jean Chalard public final boolean mFrenchLigatureProcessing; 286f420df28233c26e555d203185fb292e83b94b8c3Jean Chalard public final HashMap<String, String> mAttributes; 287f420df28233c26e555d203185fb292e83b94b8c3Jean Chalard public DictionaryOptions(final HashMap<String, String> attributes, 288f420df28233c26e555d203185fb292e83b94b8c3Jean Chalard final boolean germanUmlautProcessing, final boolean frenchLigatureProcessing) { 289c734c2aca1830643d169fd292e0c9d4d9306af5aJean Chalard mAttributes = attributes; 290f420df28233c26e555d203185fb292e83b94b8c3Jean Chalard mGermanUmlautProcessing = germanUmlautProcessing; 291f420df28233c26e555d203185fb292e83b94b8c3Jean Chalard mFrenchLigatureProcessing = frenchLigatureProcessing; 292c734c2aca1830643d169fd292e0c9d4d9306af5aJean Chalard } 29347cac57e4593f47e753410e4199e84e458d6de6fJean Chalard @Override 29447cac57e4593f47e753410e4199e84e458d6de6fJean Chalard public String toString() { // Convenience method 29551a0ef8c59ea590b6e5e80a82fc75bf244084270Jean Chalard return toString(0, false); 29647cac57e4593f47e753410e4199e84e458d6de6fJean Chalard } 29751a0ef8c59ea590b6e5e80a82fc75bf244084270Jean Chalard public String toString(final int indentCount, final boolean plumbing) { 29847cac57e4593f47e753410e4199e84e458d6de6fJean Chalard final StringBuilder indent = new StringBuilder(); 29951a0ef8c59ea590b6e5e80a82fc75bf244084270Jean Chalard if (plumbing) { 30051a0ef8c59ea590b6e5e80a82fc75bf244084270Jean Chalard indent.append("H:"); 30151a0ef8c59ea590b6e5e80a82fc75bf244084270Jean Chalard } else { 30251a0ef8c59ea590b6e5e80a82fc75bf244084270Jean Chalard for (int i = 0; i < indentCount; ++i) { 30351a0ef8c59ea590b6e5e80a82fc75bf244084270Jean Chalard indent.append(" "); 30451a0ef8c59ea590b6e5e80a82fc75bf244084270Jean Chalard } 30547cac57e4593f47e753410e4199e84e458d6de6fJean Chalard } 30647cac57e4593f47e753410e4199e84e458d6de6fJean Chalard final StringBuilder s = new StringBuilder(); 30747cac57e4593f47e753410e4199e84e458d6de6fJean Chalard for (final String optionKey : mAttributes.keySet()) { 30847cac57e4593f47e753410e4199e84e458d6de6fJean Chalard s.append(indent); 30947cac57e4593f47e753410e4199e84e458d6de6fJean Chalard s.append(optionKey); 31047cac57e4593f47e753410e4199e84e458d6de6fJean Chalard s.append(" = "); 31151a0ef8c59ea590b6e5e80a82fc75bf244084270Jean Chalard if ("date".equals(optionKey) && !plumbing) { 31247cac57e4593f47e753410e4199e84e458d6de6fJean Chalard // Date needs a number of milliseconds, but the dictionary contains seconds 31347cac57e4593f47e753410e4199e84e458d6de6fJean Chalard s.append(new Date( 31447cac57e4593f47e753410e4199e84e458d6de6fJean Chalard 1000 * Long.parseLong(mAttributes.get(optionKey))).toString()); 31547cac57e4593f47e753410e4199e84e458d6de6fJean Chalard } else { 31647cac57e4593f47e753410e4199e84e458d6de6fJean Chalard s.append(mAttributes.get(optionKey)); 31747cac57e4593f47e753410e4199e84e458d6de6fJean Chalard } 31847cac57e4593f47e753410e4199e84e458d6de6fJean Chalard s.append("\n"); 31947cac57e4593f47e753410e4199e84e458d6de6fJean Chalard } 32047cac57e4593f47e753410e4199e84e458d6de6fJean Chalard if (mGermanUmlautProcessing) { 32147cac57e4593f47e753410e4199e84e458d6de6fJean Chalard s.append(indent); 32247cac57e4593f47e753410e4199e84e458d6de6fJean Chalard s.append("Needs German umlaut processing\n"); 32347cac57e4593f47e753410e4199e84e458d6de6fJean Chalard } 32447cac57e4593f47e753410e4199e84e458d6de6fJean Chalard if (mFrenchLigatureProcessing) { 32547cac57e4593f47e753410e4199e84e458d6de6fJean Chalard s.append(indent); 32647cac57e4593f47e753410e4199e84e458d6de6fJean Chalard s.append("Needs French ligature processing\n"); 32747cac57e4593f47e753410e4199e84e458d6de6fJean Chalard } 32847cac57e4593f47e753410e4199e84e458d6de6fJean Chalard return s.toString(); 32947cac57e4593f47e753410e4199e84e458d6de6fJean Chalard } 330bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 331bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 332bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public final DictionaryOptions mOptions; 333bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public final Node mRoot; 334bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 335bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public FusionDictionary(final Node root, final DictionaryOptions options) { 336bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mRoot = root; 337bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mOptions = options; 338bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 339bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 340c734c2aca1830643d169fd292e0c9d4d9306af5aJean Chalard public void addOptionAttribute(final String key, final String value) { 341c734c2aca1830643d169fd292e0c9d4d9306af5aJean Chalard mOptions.mAttributes.put(key, value); 342c734c2aca1830643d169fd292e0c9d4d9306af5aJean Chalard } 343c734c2aca1830643d169fd292e0c9d4d9306af5aJean Chalard 344bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 345bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Helper method to convert a String to an int array. 346bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 3473c6d9fe14840fd2c455ec65b6481ed78f99a5460Yuichiro Hanada static int[] getCodePoints(final String word) { 34847db0be7cbdb8abafc18c1e49b71f6dac0d46994Jean Chalard // TODO: this is a copy-paste of the contents of StringUtils.toCodePointArray, 34947db0be7cbdb8abafc18c1e49b71f6dac0d46994Jean Chalard // which is not visible from the makedict package. Factor this code. 35047db0be7cbdb8abafc18c1e49b71f6dac0d46994Jean Chalard final char[] characters = word.toCharArray(); 35147db0be7cbdb8abafc18c1e49b71f6dac0d46994Jean Chalard final int length = characters.length; 35247db0be7cbdb8abafc18c1e49b71f6dac0d46994Jean Chalard final int[] codePoints = new int[Character.codePointCount(characters, 0, length)]; 35347db0be7cbdb8abafc18c1e49b71f6dac0d46994Jean Chalard int codePoint = Character.codePointAt(characters, 0); 35447db0be7cbdb8abafc18c1e49b71f6dac0d46994Jean Chalard int dsti = 0; 35547db0be7cbdb8abafc18c1e49b71f6dac0d46994Jean Chalard for (int srci = Character.charCount(codePoint); 35647db0be7cbdb8abafc18c1e49b71f6dac0d46994Jean Chalard srci < length; srci += Character.charCount(codePoint), ++dsti) { 35747db0be7cbdb8abafc18c1e49b71f6dac0d46994Jean Chalard codePoints[dsti] = codePoint; 35847db0be7cbdb8abafc18c1e49b71f6dac0d46994Jean Chalard codePoint = Character.codePointAt(characters, srci); 359c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard } 36047db0be7cbdb8abafc18c1e49b71f6dac0d46994Jean Chalard codePoints[dsti] = codePoint; 36147db0be7cbdb8abafc18c1e49b71f6dac0d46994Jean Chalard return codePoints; 362c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard } 363c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard 364c599f2e9d6ab839f38183aa178684ff0e94178a3Jean Chalard /** 365bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Helper method to add a word as a string. 366bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 367bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This method adds a word to the dictionary with the given frequency. Optional 368bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * lists of bigrams and shortcuts can be passed here. For each word inside, 369bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * they will be added to the dictionary as necessary. 370bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 371bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param word the word to add. 372bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param frequency the frequency of the word, in the range [0..255]. 373eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard * @param shortcutTargets a list of shortcut targets for this word, or null. 37472b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard * @param isNotAWord true if this should not be considered a word (e.g. shortcut only) 375bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 376eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard public void add(final String word, final int frequency, 37772b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard final ArrayList<WeightedString> shortcutTargets, final boolean isNotAWord) { 37872b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard add(getCodePoints(word), frequency, shortcutTargets, isNotAWord, 37972b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard false /* isBlacklistEntry */); 38072b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard } 38172b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard 38272b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard /** 38372b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard * Helper method to add a blacklist entry as a string. 38472b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard * 38572b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard * @param word the word to add as a blacklist entry. 38672b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard * @param shortcutTargets a list of shortcut targets for this word, or null. 38772b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard * @param isNotAWord true if this is not a word for spellcheking purposes (shortcut only or so) 38872b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard */ 38972b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard public void addBlacklistEntry(final String word, 39072b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard final ArrayList<WeightedString> shortcutTargets, final boolean isNotAWord) { 39172b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard add(getCodePoints(word), 0, shortcutTargets, isNotAWord, true /* isBlacklistEntry */); 392bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 393bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 394bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 395bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Sanity check for a node. 396bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 397bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This method checks that all CharGroups in a node are ordered as expected. 398bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * If they are, nothing happens. If they aren't, an exception is thrown. 399bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 400bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard private void checkStack(Node node) { 401bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard ArrayList<CharGroup> stack = node.mData; 402bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int lastValue = -1; 403bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard for (int i = 0; i < stack.size(); ++i) { 404bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int currentValue = stack.get(i).mChars[0]; 405bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (currentValue <= lastValue) 406bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard throw new RuntimeException("Invalid stack"); 407bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard else 408bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard lastValue = currentValue; 409bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 410bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 411bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 412bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 4137cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * Helper method to add a new bigram to the dictionary. 4147cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * 4157cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * @param word1 the previous word of the context 4167cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * @param word2 the next word of the context 4177cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang * @param frequency the bigram frequency 4187cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang */ 4197cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang public void setBigram(final String word1, final String word2, final int frequency) { 4207cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang CharGroup charGroup = findWordInTree(mRoot, word1); 4217cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (charGroup != null) { 4227cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang final CharGroup charGroup2 = findWordInTree(mRoot, word2); 4237cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang if (charGroup2 == null) { 42472b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard add(getCodePoints(word2), 0, null, false /* isNotAWord */, 42572b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard false /* isBlacklistEntry */); 426ddb0bcc051c1e9f2706f3702f0bb3135e4352f7bJean Chalard // The chargroup for the first word may have moved by the above insertion, 427ddb0bcc051c1e9f2706f3702f0bb3135e4352f7bJean Chalard // if word1 and word2 share a common stem that happens not to have been 428ddb0bcc051c1e9f2706f3702f0bb3135e4352f7bJean Chalard // a cutting point until now. In this case, we need to refresh charGroup. 429ddb0bcc051c1e9f2706f3702f0bb3135e4352f7bJean Chalard charGroup = findWordInTree(mRoot, word1); 4307cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 4317cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang charGroup.addBigram(word2, frequency); 4327cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } else { 4337cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang throw new RuntimeException("First word of bigram not found"); 4347cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 4357cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang } 4367cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang 4377cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang /** 438bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Add a word to this dictionary. 439bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 44044c64f46a143623dd793facd889c8d6eab5e230cJean Chalard * The shortcuts, if any, have to be in the dictionary already. If they aren't, 441bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * an exception is thrown. 442bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 443bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param word the word, as an int array. 444bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param frequency the frequency of the word, in the range [0..255]. 445eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard * @param shortcutTargets an optional list of shortcut targets for this word (null if none). 44672b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard * @param isNotAWord true if this is not a word for spellcheking purposes (shortcut only or so) 44772b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard * @param isBlacklistEntry true if this is a blacklisted word, false otherwise 448bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 449eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard private void add(final int[] word, final int frequency, 45072b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard final ArrayList<WeightedString> shortcutTargets, 45172b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard final boolean isNotAWord, final boolean isBlacklistEntry) { 452bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard assert(frequency >= 0 && frequency <= 255); 453eae7b293e4a854819aa0de663066cd0b6cdd52e7Yuichiro Hanada if (word.length >= Constants.Dictionary.MAX_WORD_LENGTH) { 454eae7b293e4a854819aa0de663066cd0b6cdd52e7Yuichiro Hanada MakedictLog.w("Ignoring a word that is too long: word.length = " + word.length); 455eae7b293e4a854819aa0de663066cd0b6cdd52e7Yuichiro Hanada return; 456eae7b293e4a854819aa0de663066cd0b6cdd52e7Yuichiro Hanada } 457eae7b293e4a854819aa0de663066cd0b6cdd52e7Yuichiro Hanada 458bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Node currentNode = mRoot; 459bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int charIndex = 0; 460bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 461bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard CharGroup currentGroup = null; 462bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int differentCharIndex = 0; // Set by the loop to the index of the char that differs 463bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int nodeIndex = findIndexOfChar(mRoot, word[charIndex]); 464bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard while (CHARACTER_NOT_FOUND != nodeIndex) { 465bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentGroup = currentNode.mData.get(nodeIndex); 466cad25fc8a754d6f145bc846f17f270220b15c055Jean Chalard differentCharIndex = compareArrays(currentGroup.mChars, word, charIndex); 467bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (ARRAYS_ARE_EQUAL != differentCharIndex 468bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard && differentCharIndex < currentGroup.mChars.length) break; 469bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (null == currentGroup.mChildren) break; 470bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard charIndex += currentGroup.mChars.length; 471bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (charIndex >= word.length) break; 472bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentNode = currentGroup.mChildren; 473bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard nodeIndex = findIndexOfChar(currentNode, word[charIndex]); 474bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 475bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 476bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (-1 == nodeIndex) { 477bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // No node at this point to accept the word. Create one. 478bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final int insertionIndex = findInsertionIndex(currentNode, word[charIndex]); 479bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup newGroup = new CharGroup( 480eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard Arrays.copyOfRange(word, charIndex, word.length), 48172b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard shortcutTargets, null /* bigrams */, frequency, isNotAWord, isBlacklistEntry); 482bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentNode.mData.add(insertionIndex, newGroup); 48347db0be7cbdb8abafc18c1e49b71f6dac0d46994Jean Chalard if (DBG) checkStack(currentNode); 484bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } else { 485bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // There is a word with a common prefix. 486bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (differentCharIndex == currentGroup.mChars.length) { 487bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (charIndex + differentCharIndex >= word.length) { 488bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // The new word is a prefix of an existing word, but the node on which it 48945239029ceb876462e0d3f654c6b24ac9a9ed8afKen Wakasa // should end already exists as is. Since the old CharNode was not a terminal, 4907cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang // make it one by filling in its frequency and other attributes 49172b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard currentGroup.update(frequency, shortcutTargets, null, isNotAWord, 49272b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard isBlacklistEntry); 493bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } else { 494bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // The new word matches the full old word and extends past it. 495bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // We only have to create a new node and add it to the end of this. 496bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup newNode = new CharGroup( 497bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Arrays.copyOfRange(word, charIndex + differentCharIndex, word.length), 49872b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard shortcutTargets, null /* bigrams */, frequency, isNotAWord, 49972b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard isBlacklistEntry); 500bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentGroup.mChildren = new Node(); 501bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentGroup.mChildren.mData.add(newNode); 502bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 503bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } else { 504bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (0 == differentCharIndex) { 5057cfe20efbeb4a94b15291aee95d0559ae2449c45Tom Ouyang // Exact same word. Update the frequency if higher. This will also add the 50644c64f46a143623dd793facd889c8d6eab5e230cJean Chalard // new shortcuts to the existing shortcut list if it already exists. 50772b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard currentGroup.update(frequency, shortcutTargets, null, 50872b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard currentGroup.mIsNotAWord && isNotAWord, 50972b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard currentGroup.mIsBlacklistEntry || isBlacklistEntry); 510bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } else { 511bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // Partial prefix match only. We have to replace the current node with a node 512bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // containing the current prefix and create two new ones for the tails. 513bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Node newChildren = new Node(); 514bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup newOldWord = new CharGroup( 515bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Arrays.copyOfRange(currentGroup.mChars, differentCharIndex, 516eec2e51e2cbc9e69739187557846a439ed74325eJean Chalard currentGroup.mChars.length), currentGroup.mShortcutTargets, 51772b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard currentGroup.mBigrams, currentGroup.mFrequency, 51872b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard currentGroup.mIsNotAWord, currentGroup.mIsBlacklistEntry, 51972b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard currentGroup.mChildren); 520bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard newChildren.mData.add(newOldWord); 521bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 522bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup newParent; 523bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (charIndex + differentCharIndex >= word.length) { 524bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard newParent = new CharGroup( 525bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Arrays.copyOfRange(currentGroup.mChars, 0, differentCharIndex), 52672b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard shortcutTargets, null /* bigrams */, frequency, 52772b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard isNotAWord, isBlacklistEntry, newChildren); 528bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } else { 529bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard newParent = new CharGroup( 530bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Arrays.copyOfRange(currentGroup.mChars, 0, differentCharIndex), 53145239029ceb876462e0d3f654c6b24ac9a9ed8afKen Wakasa null /* shortcutTargets */, null /* bigrams */, -1, 53272b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard false /* isNotAWord */, false /* isBlacklistEntry */, newChildren); 53344c64f46a143623dd793facd889c8d6eab5e230cJean Chalard final CharGroup newWord = new CharGroup(Arrays.copyOfRange(word, 53444c64f46a143623dd793facd889c8d6eab5e230cJean Chalard charIndex + differentCharIndex, word.length), 53572b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard shortcutTargets, null /* bigrams */, frequency, 53672b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard isNotAWord, isBlacklistEntry); 537bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final int addIndex = word[charIndex + differentCharIndex] 538bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard > currentGroup.mChars[differentCharIndex] ? 1 : 0; 539bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard newChildren.mData.add(addIndex, newWord); 540bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 541bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentNode.mData.set(nodeIndex, newParent); 542bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 54347db0be7cbdb8abafc18c1e49b71f6dac0d46994Jean Chalard if (DBG) checkStack(currentNode); 544bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 545bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 546bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 547bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 54893ebf74bae44728e0d5f7e738ea28376187a876eTadashi G. Takaoka private static int ARRAYS_ARE_EQUAL = 0; 54993ebf74bae44728e0d5f7e738ea28376187a876eTadashi G. Takaoka 550bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 551bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Custom comparison of two int arrays taken to contain character codes. 552bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 553bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This method compares the two arrays passed as an argument in a lexicographic way, 554bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * with an offset in the dst string. 555bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This method does NOT test for the first character. It is taken to be equal. 556bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * I repeat: this method starts the comparison at 1 <> dstOffset + 1. 557bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * The index where the strings differ is returned. ARRAYS_ARE_EQUAL = 0 is returned if the 558bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * strings are equal. This works BECAUSE we don't look at the first character. 559bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 560bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param src the left-hand side string of the comparison. 561bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param dst the right-hand side string of the comparison. 562bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param dstOffset the offset in the right-hand side string. 563bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @return the index at which the strings differ, or ARRAYS_ARE_EQUAL = 0 if they don't. 564bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 565bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard private static int compareArrays(final int[] src, final int[] dst, int dstOffset) { 566bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // We do NOT test the first char, because we come from a method that already 567bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // tested it. 568bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard for (int i = 1; i < src.length; ++i) { 569bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (dstOffset + i >= dst.length) return i; 570bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (src[i] != dst[dstOffset + i]) return i; 571bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 572bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (dst.length > src.length) return src.length; 573bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return ARRAYS_ARE_EQUAL; 574bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 575bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 576bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 577bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Helper class that compares and sorts two chargroups according to their 578bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * first element only. I repeat: ONLY the first element is considered, the rest 579bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * is ignored. 580bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This comparator imposes orderings that are inconsistent with equals. 581bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 582a28a05e971cc242b338331a3b78276fa95188d19Tadashi G. Takaoka static private final class CharGroupComparator implements java.util.Comparator<CharGroup> { 58393ebf74bae44728e0d5f7e738ea28376187a876eTadashi G. Takaoka @Override 5842aa02b84a4fcfaf5554c278d2b25cf9414eecf8bKen Wakasa public int compare(CharGroup c1, CharGroup c2) { 585bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (c1.mChars[0] == c2.mChars[0]) return 0; 586bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return c1.mChars[0] < c2.mChars[0] ? -1 : 1; 587bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 588bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 589bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final static private CharGroupComparator CHARGROUP_COMPARATOR = new CharGroupComparator(); 590bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 591bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 592bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Finds the insertion index of a character within a node. 593bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 594bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard private static int findInsertionIndex(final Node node, int character) { 5952aa02b84a4fcfaf5554c278d2b25cf9414eecf8bKen Wakasa final ArrayList<CharGroup> data = node.mData; 59644c64f46a143623dd793facd889c8d6eab5e230cJean Chalard final CharGroup reference = new CharGroup(new int[] { character }, 59772b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard null /* shortcutTargets */, null /* bigrams */, 0, false /* isNotAWord */, 59872b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard false /* isBlacklistEntry */); 599bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int result = Collections.binarySearch(data, reference, CHARGROUP_COMPARATOR); 600bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return result >= 0 ? result : -result - 1; 601bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 602bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 60393ebf74bae44728e0d5f7e738ea28376187a876eTadashi G. Takaoka private static int CHARACTER_NOT_FOUND = -1; 60493ebf74bae44728e0d5f7e738ea28376187a876eTadashi G. Takaoka 605bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 606bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Find the index of a char in a node, if it exists. 607bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 608bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param node the node to search in. 609bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param character the character to search for. 610bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @return the position of the character if it's there, or CHARACTER_NOT_FOUND = -1 else. 611bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 612bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard private static int findIndexOfChar(final Node node, int character) { 613bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final int insertionIndex = findInsertionIndex(node, character); 614bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (node.mData.size() <= insertionIndex) return CHARACTER_NOT_FOUND; 615bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return character == node.mData.get(insertionIndex).mChars[0] ? insertionIndex 616bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard : CHARACTER_NOT_FOUND; 617bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 618bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 619bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 620bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Helper method to find a word in a given branch. 621bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 6222da886651874b2588f18f800417ba858ac93d88bJean Chalard @SuppressWarnings("unused") 623bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public static CharGroup findWordInTree(Node node, final String s) { 624bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int index = 0; 62512efad3d15147f255f6e01600c40e9fdb1224d84Jean Chalard final StringBuilder checker = DBG ? new StringBuilder() : null; 626bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 627bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard CharGroup currentGroup; 6286c721b5f68ee20e6d78ddd4f383fb8651827b726Jean Chalard final int codePointCountInS = s.codePointCount(0, s.length()); 629bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard do { 630bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int indexOfGroup = findIndexOfChar(node, s.codePointAt(index)); 631bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (CHARACTER_NOT_FOUND == indexOfGroup) return null; 632bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentGroup = node.mData.get(indexOfGroup); 63366f338983bb9cb04a0d94a4729330b1c8ff01c93Yuichiro Hanada 63466f338983bb9cb04a0d94a4729330b1c8ff01c93Yuichiro Hanada if (s.length() - index < currentGroup.mChars.length) return null; 63566f338983bb9cb04a0d94a4729330b1c8ff01c93Yuichiro Hanada int newIndex = index; 63666f338983bb9cb04a0d94a4729330b1c8ff01c93Yuichiro Hanada while (newIndex < s.length() && newIndex - index < currentGroup.mChars.length) { 63766f338983bb9cb04a0d94a4729330b1c8ff01c93Yuichiro Hanada if (currentGroup.mChars[newIndex - index] != s.codePointAt(newIndex)) return null; 63866f338983bb9cb04a0d94a4729330b1c8ff01c93Yuichiro Hanada newIndex++; 63966f338983bb9cb04a0d94a4729330b1c8ff01c93Yuichiro Hanada } 64066f338983bb9cb04a0d94a4729330b1c8ff01c93Yuichiro Hanada index = newIndex; 64166f338983bb9cb04a0d94a4729330b1c8ff01c93Yuichiro Hanada 64212efad3d15147f255f6e01600c40e9fdb1224d84Jean Chalard if (DBG) checker.append(new String(currentGroup.mChars, 0, currentGroup.mChars.length)); 6436c721b5f68ee20e6d78ddd4f383fb8651827b726Jean Chalard if (index < codePointCountInS) { 644bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard node = currentGroup.mChildren; 645bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 6466c721b5f68ee20e6d78ddd4f383fb8651827b726Jean Chalard } while (null != node && index < codePointCountInS); 647bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 6486c721b5f68ee20e6d78ddd4f383fb8651827b726Jean Chalard if (index < codePointCountInS) return null; 6490d35c159fefd7591c2ab9d5037c32d1804024197Yuichiro Hanada if (!currentGroup.isTerminal()) return null; 65012efad3d15147f255f6e01600c40e9fdb1224d84Jean Chalard if (DBG && !s.equals(checker.toString())) return null; 651bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return currentGroup; 652bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 653bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 654bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 655eddfbb68dcff55c85b3d5b82d406f543bd038825Jean Chalard * Helper method to find out whether a word is in the dict or not. 656eddfbb68dcff55c85b3d5b82d406f543bd038825Jean Chalard */ 657eddfbb68dcff55c85b3d5b82d406f543bd038825Jean Chalard public boolean hasWord(final String s) { 658eddfbb68dcff55c85b3d5b82d406f543bd038825Jean Chalard if (null == s || "".equals(s)) { 659eddfbb68dcff55c85b3d5b82d406f543bd038825Jean Chalard throw new RuntimeException("Can't search for a null or empty string"); 660eddfbb68dcff55c85b3d5b82d406f543bd038825Jean Chalard } 661eddfbb68dcff55c85b3d5b82d406f543bd038825Jean Chalard return null != findWordInTree(mRoot, s); 662eddfbb68dcff55c85b3d5b82d406f543bd038825Jean Chalard } 663eddfbb68dcff55c85b3d5b82d406f543bd038825Jean Chalard 664eddfbb68dcff55c85b3d5b82d406f543bd038825Jean Chalard /** 665bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Recursively count the number of character groups in a given branch of the trie. 666bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 667bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param node the parent node. 668bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @return the number of char groups in all the branch under this node. 669bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 670bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public static int countCharGroups(final Node node) { 671bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final int nodeSize = node.mData.size(); 672bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int size = nodeSize; 673bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard for (int i = nodeSize - 1; i >= 0; --i) { 674bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard CharGroup group = node.mData.get(i); 675bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (null != group.mChildren) 676bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard size += countCharGroups(group.mChildren); 677bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 678bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return size; 679bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 680bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 681bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 682bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Recursively count the number of nodes in a given branch of the trie. 683bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 684bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param node the node to count. 68520a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard * @return the number of nodes in this branch. 686bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 687bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public static int countNodes(final Node node) { 688bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int size = 1; 689bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard for (int i = node.mData.size() - 1; i >= 0; --i) { 690bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard CharGroup group = node.mData.get(i); 691bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (null != group.mChildren) 692bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard size += countNodes(group.mChildren); 693bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 694bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return size; 695bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 696bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 69720a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard // Recursively find out whether there are any bigrams. 69820a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard // This can be pretty expensive especially if there aren't any (we return as soon 69920a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard // as we find one, so it's much cheaper if there are bigrams) 70020a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard private static boolean hasBigramsInternal(final Node node) { 70120a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard if (null == node) return false; 70220a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard for (int i = node.mData.size() - 1; i >= 0; --i) { 70320a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard CharGroup group = node.mData.get(i); 70420a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard if (null != group.mBigrams) return true; 70520a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard if (hasBigramsInternal(group.mChildren)) return true; 70620a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard } 70720a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard return false; 70820a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard } 70920a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard 71020a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard /** 71120a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard * Finds out whether there are any bigrams in this dictionary. 71220a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard * 71320a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard * @return true if there is any bigram, false otherwise. 71420a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard */ 71520a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard // TODO: this is expensive especially for large dictionaries without any bigram. 71620a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard // The up side is, this is always accurate and correct and uses no memory. We should 71720a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard // find a more efficient way of doing this, without compromising too much on memory 71820a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard // and ease of use. 71920a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard public boolean hasBigrams() { 72020a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard return hasBigramsInternal(mRoot); 72120a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard } 72220a6dea1cabfd8822824f7dca828d898e5b91cbcJean Chalard 723bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // Historically, the tails of the words were going to be merged to save space. 724bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // However, that would prevent the code to search for a specific address in log(n) 725bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // time so this was abandoned. 726bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // The code is still of interest as it does add some compression to any dictionary 727bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // that has no need for attributes. Implementations that does not read attributes should be 728bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // able to read a dictionary with merged tails. 729bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // Also, the following code does support frequencies, as in, it will only merges 730bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // tails that share the same frequency. Though it would result in the above loss of 731bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // performance while searching by address, it is still technically possible to merge 732bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // tails that contain attributes, but this code does not take that into account - it does 733bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // not compare attributes and will merge terminals with different attributes regardless. 734bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public void mergeTails() { 735bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard MakedictLog.i("Do not merge tails"); 736bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return; 737bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 738bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// MakedictLog.i("Merging nodes. Number of nodes : " + countNodes(root)); 739bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// MakedictLog.i("Number of groups : " + countCharGroups(root)); 740bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// 741bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// final HashMap<String, ArrayList<Node>> repository = 742bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// new HashMap<String, ArrayList<Node>>(); 743bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// mergeTailsInner(repository, root); 744bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// 745bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// MakedictLog.i("Number of different pseudohashes : " + repository.size()); 746bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// int size = 0; 747bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// for (ArrayList<Node> a : repository.values()) { 748bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// size += a.size(); 749bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 750bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// MakedictLog.i("Number of nodes after merge : " + (1 + size)); 751bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// MakedictLog.i("Recursively seen nodes : " + countNodes(root)); 752bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 753bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 754bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // The following methods are used by the deactivated mergeTails() 755bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// private static boolean isEqual(Node a, Node b) { 756bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (null == a && null == b) return true; 757bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (null == a || null == b) return false; 758bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (a.data.size() != b.data.size()) return false; 759bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// final int size = a.data.size(); 760bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// for (int i = size - 1; i >= 0; --i) { 761bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// CharGroup aGroup = a.data.get(i); 762bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// CharGroup bGroup = b.data.get(i); 763bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (aGroup.frequency != bGroup.frequency) return false; 764bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (aGroup.alternates == null && bGroup.alternates != null) return false; 765bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (aGroup.alternates != null && !aGroup.equals(bGroup.alternates)) return false; 766bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (!Arrays.equals(aGroup.chars, bGroup.chars)) return false; 767bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (!isEqual(aGroup.children, bGroup.children)) return false; 768bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 769bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// return true; 770bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 771bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 772bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// static private HashMap<String, ArrayList<Node>> mergeTailsInner( 773bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// final HashMap<String, ArrayList<Node>> map, final Node node) { 774bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// final ArrayList<CharGroup> branches = node.data; 775bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// final int nodeSize = branches.size(); 776bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// for (int i = 0; i < nodeSize; ++i) { 777bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// CharGroup group = branches.get(i); 778bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (null != group.children) { 779bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// String pseudoHash = getPseudoHash(group.children); 780bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// ArrayList<Node> similarList = map.get(pseudoHash); 781bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (null == similarList) { 782bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// similarList = new ArrayList<Node>(); 783bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// map.put(pseudoHash, similarList); 784bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 785bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// boolean merged = false; 786bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// for (Node similar : similarList) { 787bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (isEqual(group.children, similar)) { 788bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// group.children = similar; 789bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// merged = true; 790bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// break; 791bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 792bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 793bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (!merged) { 794bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// similarList.add(group.children); 795bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 796bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// mergeTailsInner(map, group.children); 797bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 798bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 799bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// return map; 800bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 801bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 802bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// private static String getPseudoHash(final Node node) { 803bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// StringBuilder s = new StringBuilder(); 804bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// for (CharGroup g : node.data) { 805bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// s.append(g.frequency); 806f2789819bd005b5b0581e8439601b5501306327dKen Wakasa// for (int ch : g.chars) { 807bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// s.append(Character.toChars(ch)); 808bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 809bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 810bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// return s.toString(); 811bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 812bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 813bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 814bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Iterator to walk through a dictionary. 815bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 816bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This is purely for convenience. 817bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 818a28a05e971cc242b338331a3b78276fa95188d19Tadashi G. Takaoka public static final class DictionaryIterator implements Iterator<Word> { 819a28a05e971cc242b338331a3b78276fa95188d19Tadashi G. Takaoka private static final class Position { 820bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public Iterator<CharGroup> pos; 821bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public int length; 822bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public Position(ArrayList<CharGroup> groups) { 823bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard pos = groups.iterator(); 824bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard length = 0; 825bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 826bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 827bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final StringBuilder mCurrentString; 828bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final LinkedList<Position> mPositions; 829bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 830bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public DictionaryIterator(ArrayList<CharGroup> root) { 831bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mCurrentString = new StringBuilder(); 832bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mPositions = new LinkedList<Position>(); 833bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final Position rootPos = new Position(root); 834bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mPositions.add(rootPos); 835bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 836bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 837bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard @Override 838bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public boolean hasNext() { 839bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard for (Position p : mPositions) { 840bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (p.pos.hasNext()) { 841bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return true; 842bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 843bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 844bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return false; 845bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 846bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 847bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard @Override 848bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public Word next() { 849bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Position currentPos = mPositions.getLast(); 850bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mCurrentString.setLength(mCurrentString.length() - currentPos.length); 851bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 852bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard do { 853bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (currentPos.pos.hasNext()) { 854bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup currentGroup = currentPos.pos.next(); 855bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentPos.length = currentGroup.mChars.length; 856bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard for (int i : currentGroup.mChars) 857bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mCurrentString.append(Character.toChars(i)); 858bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (null != currentGroup.mChildren) { 859bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentPos = new Position(currentGroup.mChildren.mData); 860bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mPositions.addLast(currentPos); 861bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 862bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (currentGroup.mFrequency >= 0) 863bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return new Word(mCurrentString.toString(), currentGroup.mFrequency, 86472b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard currentGroup.mShortcutTargets, currentGroup.mBigrams, 86572b1c9394105b6fbc0d8c6ff00f3574ee37a9aaaJean Chalard currentGroup.mIsNotAWord, currentGroup.mIsBlacklistEntry); 866bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } else { 867bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mPositions.removeLast(); 868bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentPos = mPositions.getLast(); 869bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mCurrentString.setLength(mCurrentString.length() - mPositions.getLast().length); 870bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 871f2789819bd005b5b0581e8439601b5501306327dKen Wakasa } while (true); 872bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 873bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 874bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard @Override 875bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public void remove() { 876bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard throw new UnsupportedOperationException("Unsupported yet"); 877bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 878bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 879bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 880bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 881bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 882bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Method to return an iterator. 883bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 884bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This method enables Java's enhanced for loop. With this you can have a FusionDictionary x 885bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * and say : for (Word w : x) {} 886bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 887bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard @Override 888bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public Iterator<Word> iterator() { 889bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return new DictionaryIterator(mRoot.mData); 890bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 891bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard} 892