FusionDictionary.java revision bfbbee8c5757aef4a20879547c16af0a4d1bf4c7
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 17bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalardpackage com.android.inputmethod.latin; 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 Chalardimport java.util.List; 25bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 26bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard/** 27bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * A dictionary that can fusion heads and tails of words for more compression. 28bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 29bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalardpublic class FusionDictionary implements Iterable<Word> { 30bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 31bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 32bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * A node of the dictionary, containing several CharGroups. 33bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 34bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * A node is but an ordered array of CharGroups, which essentially contain all the 35bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * real information. 36bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This class also contains fields to cache size and address, to help with binary 37bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * generation. 38bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 39bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public static class Node { 40bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard ArrayList<CharGroup> mData; 41bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // To help with binary generation 42bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int mCachedSize; 43bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int mCachedAddress; 44bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public Node() { 45bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mData = new ArrayList<CharGroup>(); 46bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mCachedSize = Integer.MIN_VALUE; 47bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mCachedAddress = Integer.MIN_VALUE; 48bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 49bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public Node(ArrayList<CharGroup> data) { 50bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mData = data; 51bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mCachedSize = Integer.MIN_VALUE; 52bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mCachedAddress = Integer.MIN_VALUE; 53bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 54bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 55bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 56bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 57bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * A string with a frequency. 58bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 59bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This represents an "attribute", that is either a bigram or a shortcut. 60bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 61bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public static class WeightedString { 62bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final String mWord; 63bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final int mFrequency; 64bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public WeightedString(String word, int frequency) { 65bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mWord = word; 66bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mFrequency = frequency; 67bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 68bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 69bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 70bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 71bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * A group of characters, with a frequency, shortcuts, bigrams, and children. 72bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 73bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This is the central class of the in-memory representation. A CharGroup is what can 74bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * be seen as a traditional "trie node", except it can hold several characters at the 75bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * same time. A CharGroup essentially represents one or several characters in the middle 76bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * of the trie trie; as such, it can be a terminal, and it can have children. 77bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * In this in-memory representation, whether the CharGroup is a terminal or not is represented 78bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * in the frequency, where NOT_A_TERMINAL (= -1) means this is not a terminal and any other 79bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * value is the frequency of this terminal. A terminal may have non-null shortcuts and/or 80bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * bigrams, but a non-terminal may not. Moreover, children, if present, are null. 81bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 82bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public static class CharGroup { 83bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public static final int NOT_A_TERMINAL = -1; 84bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final int mChars[]; 85bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final ArrayList<WeightedString> mBigrams; 86bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final int mFrequency; // NOT_A_TERMINAL == mFrequency indicates this is not a terminal. 87bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Node mChildren; 88bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // The two following members to help with binary generation 89bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int mCachedSize; 90bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int mCachedAddress; 91bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 92bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public CharGroup(final int[] chars, 93bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final ArrayList<WeightedString> bigrams, final int frequency) { 94bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mChars = chars; 95bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mFrequency = frequency; 96bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mBigrams = bigrams; 97bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mChildren = null; 98bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 99bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 100bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public CharGroup(final int[] chars, 101bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final ArrayList<WeightedString> bigrams, final int frequency, final Node children) { 102bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mChars = chars; 103bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mFrequency = frequency; 104bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mBigrams = bigrams; 105bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mChildren = children; 106bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 107bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 108bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public void addChild(CharGroup n) { 109bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (null == mChildren) { 110bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mChildren = new Node(); 111bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 112bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mChildren.mData.add(n); 113bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 114bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 115bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public boolean isTerminal() { 116bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return NOT_A_TERMINAL != mFrequency; 117bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 118bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 119bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public boolean hasSeveralChars() { 120bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard assert(mChars.length > 0); 121bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return 1 < mChars.length; 122bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 123bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 124bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 125bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 126bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Options global to the dictionary. 127bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 128bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * There are no options at the moment, so this class is empty. 129bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 130bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public static class DictionaryOptions { 131bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 132bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 133bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 134bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public final DictionaryOptions mOptions; 135bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public final Node mRoot; 136bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 137bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public FusionDictionary() { 138bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mOptions = new DictionaryOptions(); 139bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mRoot = new Node(); 140bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 141bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 142bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public FusionDictionary(final Node root, final DictionaryOptions options) { 143bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mRoot = root; 144bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mOptions = options; 145bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 146bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 147bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 148bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Helper method to convert a String to an int array. 149bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 150bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard static private int[] getCodePoints(String word) { 151bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final int wordLength = word.length(); 152bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int[] array = new int[word.codePointCount(0, wordLength)]; 153bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard for (int i = 0; i < wordLength; ++i) { 154bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard array[i] = word.codePointAt(i); 155bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 156bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return array; 157bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 158bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 159bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 160bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Helper method to add a word as a string. 161bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 162bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This method adds a word to the dictionary with the given frequency. Optional 163bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * lists of bigrams and shortcuts can be passed here. For each word inside, 164bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * they will be added to the dictionary as necessary. 165bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 166bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param word the word to add. 167bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param frequency the frequency of the word, in the range [0..255]. 168bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param bigrams a list of bigrams, or null. 169bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 170bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public void add(String word, int frequency, ArrayList<WeightedString> bigrams) { 171bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (null != bigrams) { 172bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard for (WeightedString bigram : bigrams) { 173bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup t = findWordInTree(mRoot, bigram.mWord); 174bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (null == t) { 175bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard add(getCodePoints(bigram.mWord), 0, null); 176bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 177bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 178bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 179bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard add(getCodePoints(word), frequency, bigrams); 180bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 181bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 182bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 183bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Sanity check for a node. 184bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 185bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This method checks that all CharGroups in a node are ordered as expected. 186bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * If they are, nothing happens. If they aren't, an exception is thrown. 187bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 188bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard private void checkStack(Node node) { 189bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard ArrayList<CharGroup> stack = node.mData; 190bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int lastValue = -1; 191bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard for (int i = 0; i < stack.size(); ++i) { 192bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int currentValue = stack.get(i).mChars[0]; 193bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (currentValue <= lastValue) 194bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard throw new RuntimeException("Invalid stack"); 195bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard else 196bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard lastValue = currentValue; 197bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 198bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 199bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 200bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 201bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Add a word to this dictionary. 202bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 203bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * The bigrams, if any, have to be in the dictionary already. If they aren't, 204bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * an exception is thrown. 205bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 206bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param word the word, as an int array. 207bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param frequency the frequency of the word, in the range [0..255]. 208bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param bigrams an optional list of bigrams for this word (null if none). 209bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 210bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard private void add(int[] word, int frequency, ArrayList<WeightedString> bigrams) { 211bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard assert(frequency >= 0 && frequency <= 255); 212bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Node currentNode = mRoot; 213bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int charIndex = 0; 214bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 215bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard CharGroup currentGroup = null; 216bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int differentCharIndex = 0; // Set by the loop to the index of the char that differs 217bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int nodeIndex = findIndexOfChar(mRoot, word[charIndex]); 218bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard while (CHARACTER_NOT_FOUND != nodeIndex) { 219bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentGroup = currentNode.mData.get(nodeIndex); 220bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard differentCharIndex = compareArrays(currentGroup.mChars, word, charIndex) ; 221bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (ARRAYS_ARE_EQUAL != differentCharIndex 222bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard && differentCharIndex < currentGroup.mChars.length) break; 223bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (null == currentGroup.mChildren) break; 224bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard charIndex += currentGroup.mChars.length; 225bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (charIndex >= word.length) break; 226bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentNode = currentGroup.mChildren; 227bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard nodeIndex = findIndexOfChar(currentNode, word[charIndex]); 228bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 229bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 230bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (-1 == nodeIndex) { 231bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // No node at this point to accept the word. Create one. 232bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final int insertionIndex = findInsertionIndex(currentNode, word[charIndex]); 233bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup newGroup = new CharGroup( 234bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Arrays.copyOfRange(word, charIndex, word.length), bigrams, frequency); 235bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentNode.mData.add(insertionIndex, newGroup); 236bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard checkStack(currentNode); 237bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } else { 238bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // There is a word with a common prefix. 239bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (differentCharIndex == currentGroup.mChars.length) { 240bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (charIndex + differentCharIndex >= word.length) { 241bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // The new word is a prefix of an existing word, but the node on which it 242bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // should end already exists as is. 243bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (currentGroup.mFrequency > 0) { 244bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard throw new RuntimeException("Such a word already exists in the dictionary : " 245bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard + new String(word, 0, word.length)); 246bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } else { 247bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup newNode = new CharGroup(currentGroup.mChars, 248bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard bigrams, frequency, currentGroup.mChildren); 249bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentNode.mData.set(nodeIndex, newNode); 250bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard checkStack(currentNode); 251bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 252bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } else { 253bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // The new word matches the full old word and extends past it. 254bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // We only have to create a new node and add it to the end of this. 255bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup newNode = new CharGroup( 256bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Arrays.copyOfRange(word, charIndex + differentCharIndex, word.length), 257bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard bigrams, frequency); 258bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentGroup.mChildren = new Node(); 259bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentGroup.mChildren.mData.add(newNode); 260bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 261bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } else { 262bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (0 == differentCharIndex) { 263bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // Exact same word. Check the frequency is 0 or -1, and update. 264bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (0 != frequency) { 265bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (0 < currentGroup.mFrequency) { 266bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard throw new RuntimeException("This word already exists with frequency " 267bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard + currentGroup.mFrequency + " : " 268bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard + new String(word, 0, word.length)); 269bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 270bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup newGroup = new CharGroup(word, 271bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentGroup.mBigrams, frequency); 272bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentNode.mData.set(nodeIndex, newGroup); 273bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 274bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } else { 275bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // Partial prefix match only. We have to replace the current node with a node 276bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // containing the current prefix and create two new ones for the tails. 277bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Node newChildren = new Node(); 278bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup newOldWord = new CharGroup( 279bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Arrays.copyOfRange(currentGroup.mChars, differentCharIndex, 280bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentGroup.mChars.length), 281bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentGroup.mBigrams, currentGroup.mFrequency, currentGroup.mChildren); 282bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard newChildren.mData.add(newOldWord); 283bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 284bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup newParent; 285bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (charIndex + differentCharIndex >= word.length) { 286bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard newParent = new CharGroup( 287bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Arrays.copyOfRange(currentGroup.mChars, 0, differentCharIndex), 288bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard bigrams, frequency, newChildren); 289bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } else { 290bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard newParent = new CharGroup( 291bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Arrays.copyOfRange(currentGroup.mChars, 0, differentCharIndex), 292bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard null, -1, newChildren); 293bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup newWord = new CharGroup( 294bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Arrays.copyOfRange(word, charIndex + differentCharIndex, 295bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard word.length), bigrams, frequency); 296bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final int addIndex = word[charIndex + differentCharIndex] 297bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard > currentGroup.mChars[differentCharIndex] ? 1 : 0; 298bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard newChildren.mData.add(addIndex, newWord); 299bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 300bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentNode.mData.set(nodeIndex, newParent); 301bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 302bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard checkStack(currentNode); 303bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 304bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 305bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 306bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 307bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 308bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Custom comparison of two int arrays taken to contain character codes. 309bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 310bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This method compares the two arrays passed as an argument in a lexicographic way, 311bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * with an offset in the dst string. 312bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This method does NOT test for the first character. It is taken to be equal. 313bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * I repeat: this method starts the comparison at 1 <> dstOffset + 1. 314bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * The index where the strings differ is returned. ARRAYS_ARE_EQUAL = 0 is returned if the 315bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * strings are equal. This works BECAUSE we don't look at the first character. 316bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 317bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param src the left-hand side string of the comparison. 318bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param dst the right-hand side string of the comparison. 319bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param dstOffset the offset in the right-hand side string. 320bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @return the index at which the strings differ, or ARRAYS_ARE_EQUAL = 0 if they don't. 321bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 322bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard private static int ARRAYS_ARE_EQUAL = 0; 323bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard private static int compareArrays(final int[] src, final int[] dst, int dstOffset) { 324bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // We do NOT test the first char, because we come from a method that already 325bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // tested it. 326bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard for (int i = 1; i < src.length; ++i) { 327bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (dstOffset + i >= dst.length) return i; 328bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (src[i] != dst[dstOffset + i]) return i; 329bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 330bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (dst.length > src.length) return src.length; 331bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return ARRAYS_ARE_EQUAL; 332bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 333bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 334bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 335bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Helper class that compares and sorts two chargroups according to their 336bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * first element only. I repeat: ONLY the first element is considered, the rest 337bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * is ignored. 338bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This comparator imposes orderings that are inconsistent with equals. 339bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 340bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard static private class CharGroupComparator implements java.util.Comparator { 341bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public int compare(Object o1, Object o2) { 342bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup c1 = (CharGroup)o1; 343bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup c2 = (CharGroup)o2; 344bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (c1.mChars[0] == c2.mChars[0]) return 0; 345bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return c1.mChars[0] < c2.mChars[0] ? -1 : 1; 346bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 347bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public boolean equals(Object o) { 348bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return o instanceof CharGroupComparator; 349bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 350bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 351bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final static private CharGroupComparator CHARGROUP_COMPARATOR = new CharGroupComparator(); 352bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 353bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 354bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Finds the insertion index of a character within a node. 355bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 356bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard private static int findInsertionIndex(final Node node, int character) { 357bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final List data = node.mData; 358bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup reference = new CharGroup(new int[] { character }, null, 0); 359bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int result = Collections.binarySearch(data, reference, CHARGROUP_COMPARATOR); 360bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return result >= 0 ? result : -result - 1; 361bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 362bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 363bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 364bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Find the index of a char in a node, if it exists. 365bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 366bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param node the node to search in. 367bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param character the character to search for. 368bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @return the position of the character if it's there, or CHARACTER_NOT_FOUND = -1 else. 369bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 370bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard private static int CHARACTER_NOT_FOUND = -1; 371bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard private static int findIndexOfChar(final Node node, int character) { 372bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final int insertionIndex = findInsertionIndex(node, character); 373bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (node.mData.size() <= insertionIndex) return CHARACTER_NOT_FOUND; 374bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return character == node.mData.get(insertionIndex).mChars[0] ? insertionIndex 375bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard : CHARACTER_NOT_FOUND; 376bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 377bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 378bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 379bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Helper method to find a word in a given branch. 380bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 381bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public static CharGroup findWordInTree(Node node, final String s) { 382bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int index = 0; 383bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final StringBuilder checker = new StringBuilder(); 384bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 385bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard CharGroup currentGroup; 386bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard do { 387bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int indexOfGroup = findIndexOfChar(node, s.codePointAt(index)); 388bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (CHARACTER_NOT_FOUND == indexOfGroup) return null; 389bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentGroup = node.mData.get(indexOfGroup); 390bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard checker.append(new String(currentGroup.mChars, 0, currentGroup.mChars.length)); 391bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard index += currentGroup.mChars.length; 392bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (index < s.length()) { 393bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard node = currentGroup.mChildren; 394bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 395bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } while (null != node && index < s.length()); 396bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 397bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (!s.equals(checker.toString())) return null; 398bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return currentGroup; 399bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 400bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 401bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 402bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Recursively count the number of character groups in a given branch of the trie. 403bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 404bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param node the parent node. 405bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @return the number of char groups in all the branch under this node. 406bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 407bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public static int countCharGroups(final Node node) { 408bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final int nodeSize = node.mData.size(); 409bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int size = nodeSize; 410bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard for (int i = nodeSize - 1; i >= 0; --i) { 411bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard CharGroup group = node.mData.get(i); 412bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (null != group.mChildren) 413bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard size += countCharGroups(group.mChildren); 414bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 415bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return size; 416bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 417bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 418bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 419bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Recursively count the number of nodes in a given branch of the trie. 420bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 421bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @param node the node to count. 422bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * @result the number of nodes in this branch. 423bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 424bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public static int countNodes(final Node node) { 425bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard int size = 1; 426bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard for (int i = node.mData.size() - 1; i >= 0; --i) { 427bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard CharGroup group = node.mData.get(i); 428bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (null != group.mChildren) 429bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard size += countNodes(group.mChildren); 430bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 431bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return size; 432bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 433bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 434bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // Historically, the tails of the words were going to be merged to save space. 435bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // However, that would prevent the code to search for a specific address in log(n) 436bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // time so this was abandoned. 437bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // The code is still of interest as it does add some compression to any dictionary 438bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // that has no need for attributes. Implementations that does not read attributes should be 439bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // able to read a dictionary with merged tails. 440bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // Also, the following code does support frequencies, as in, it will only merges 441bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // tails that share the same frequency. Though it would result in the above loss of 442bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // performance while searching by address, it is still technically possible to merge 443bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // tails that contain attributes, but this code does not take that into account - it does 444bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // not compare attributes and will merge terminals with different attributes regardless. 445bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public void mergeTails() { 446bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard MakedictLog.i("Do not merge tails"); 447bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return; 448bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 449bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// MakedictLog.i("Merging nodes. Number of nodes : " + countNodes(root)); 450bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// MakedictLog.i("Number of groups : " + countCharGroups(root)); 451bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// 452bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// final HashMap<String, ArrayList<Node>> repository = 453bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// new HashMap<String, ArrayList<Node>>(); 454bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// mergeTailsInner(repository, root); 455bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// 456bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// MakedictLog.i("Number of different pseudohashes : " + repository.size()); 457bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// int size = 0; 458bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// for (ArrayList<Node> a : repository.values()) { 459bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// size += a.size(); 460bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 461bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// MakedictLog.i("Number of nodes after merge : " + (1 + size)); 462bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// MakedictLog.i("Recursively seen nodes : " + countNodes(root)); 463bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 464bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 465bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard // The following methods are used by the deactivated mergeTails() 466bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// private static boolean isEqual(Node a, Node b) { 467bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (null == a && null == b) return true; 468bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (null == a || null == b) return false; 469bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (a.data.size() != b.data.size()) return false; 470bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// final int size = a.data.size(); 471bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// for (int i = size - 1; i >= 0; --i) { 472bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// CharGroup aGroup = a.data.get(i); 473bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// CharGroup bGroup = b.data.get(i); 474bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (aGroup.frequency != bGroup.frequency) return false; 475bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (aGroup.alternates == null && bGroup.alternates != null) return false; 476bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (aGroup.alternates != null && !aGroup.equals(bGroup.alternates)) return false; 477bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (!Arrays.equals(aGroup.chars, bGroup.chars)) return false; 478bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (!isEqual(aGroup.children, bGroup.children)) return false; 479bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 480bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// return true; 481bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 482bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 483bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// static private HashMap<String, ArrayList<Node>> mergeTailsInner( 484bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// final HashMap<String, ArrayList<Node>> map, final Node node) { 485bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// final ArrayList<CharGroup> branches = node.data; 486bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// final int nodeSize = branches.size(); 487bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// for (int i = 0; i < nodeSize; ++i) { 488bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// CharGroup group = branches.get(i); 489bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (null != group.children) { 490bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// String pseudoHash = getPseudoHash(group.children); 491bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// ArrayList<Node> similarList = map.get(pseudoHash); 492bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (null == similarList) { 493bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// similarList = new ArrayList<Node>(); 494bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// map.put(pseudoHash, similarList); 495bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 496bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// boolean merged = false; 497bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// for (Node similar : similarList) { 498bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (isEqual(group.children, similar)) { 499bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// group.children = similar; 500bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// merged = true; 501bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// break; 502bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 503bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 504bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// if (!merged) { 505bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// similarList.add(group.children); 506bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 507bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// mergeTailsInner(map, group.children); 508bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 509bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 510bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// return map; 511bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 512bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 513bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// private static String getPseudoHash(final Node node) { 514bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// StringBuilder s = new StringBuilder(); 515bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// for (CharGroup g : node.data) { 516bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// s.append(g.frequency); 517bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// for (int ch : g.chars){ 518bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// s.append(Character.toChars(ch)); 519bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 520bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 521bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// return s.toString(); 522bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard// } 523bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 524bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 525bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Iterator to walk through a dictionary. 526bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 527bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This is purely for convenience. 528bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 529bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public static class DictionaryIterator implements Iterator<Word> { 530bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 531bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard private static class Position { 532bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public Iterator<CharGroup> pos; 533bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public int length; 534bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public Position(ArrayList<CharGroup> groups) { 535bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard pos = groups.iterator(); 536bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard length = 0; 537bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 538bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 539bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final StringBuilder mCurrentString; 540bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final LinkedList<Position> mPositions; 541bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 542bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public DictionaryIterator(ArrayList<CharGroup> root) { 543bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mCurrentString = new StringBuilder(); 544bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mPositions = new LinkedList<Position>(); 545bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final Position rootPos = new Position(root); 546bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mPositions.add(rootPos); 547bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 548bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 549bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard @Override 550bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public boolean hasNext() { 551bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard for (Position p : mPositions) { 552bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (p.pos.hasNext()) { 553bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return true; 554bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 555bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 556bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return false; 557bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 558bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 559bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard @Override 560bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public Word next() { 561bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard Position currentPos = mPositions.getLast(); 562bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mCurrentString.setLength(mCurrentString.length() - currentPos.length); 563bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 564bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard do { 565bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (currentPos.pos.hasNext()) { 566bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard final CharGroup currentGroup = currentPos.pos.next(); 567bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentPos.length = currentGroup.mChars.length; 568bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard for (int i : currentGroup.mChars) 569bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mCurrentString.append(Character.toChars(i)); 570bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (null != currentGroup.mChildren) { 571bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentPos = new Position(currentGroup.mChildren.mData); 572bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mPositions.addLast(currentPos); 573bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 574bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard if (currentGroup.mFrequency >= 0) 575bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return new Word(mCurrentString.toString(), currentGroup.mFrequency, 576bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentGroup.mBigrams); 577bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } else { 578bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mPositions.removeLast(); 579bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard currentPos = mPositions.getLast(); 580bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard mCurrentString.setLength(mCurrentString.length() - mPositions.getLast().length); 581bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 582bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } while(true); 583bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 584bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 585bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard @Override 586bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public void remove() { 587bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard throw new UnsupportedOperationException("Unsupported yet"); 588bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 589bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 590bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 591bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard 592bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard /** 593bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * Method to return an iterator. 594bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * 595bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * This method enables Java's enhanced for loop. With this you can have a FusionDictionary x 596bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard * and say : for (Word w : x) {} 597bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard */ 598bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard @Override 599bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard public Iterator<Word> iterator() { 600bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard return new DictionaryIterator(mRoot.mData); 601bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard } 602bfbbee8c5757aef4a20879547c16af0a4d1bf4c7Jean Chalard} 603