diff options
Diffstat (limited to 'tests')
17 files changed, 3652 insertions, 4 deletions
diff --git a/tests/src/com/android/inputmethod/latin/BinaryDictionaryDecayingTests.java b/tests/src/com/android/inputmethod/latin/BinaryDictionaryDecayingTests.java index 918f09067..ae2205b36 100644 --- a/tests/src/com/android/inputmethod/latin/BinaryDictionaryDecayingTests.java +++ b/tests/src/com/android/inputmethod/latin/BinaryDictionaryDecayingTests.java @@ -20,6 +20,7 @@ import android.test.AndroidTestCase; import android.test.suitebuilder.annotation.LargeTest; import android.util.Pair; +import com.android.inputmethod.latin.makedict.BinaryDictIOUtils; import com.android.inputmethod.latin.makedict.CodePointUtils; import com.android.inputmethod.latin.makedict.DictDecoder; import com.android.inputmethod.latin.makedict.DictionaryHeader; @@ -151,7 +152,8 @@ public class BinaryDictionaryDecayingTests extends AndroidTestCase { binaryDictionary.flushWithGC(); binaryDictionary.close(); - final DictDecoder dictDecoder = FormatSpec.getDictDecoder(dictFile, 0, dictFile.length()); + final DictDecoder dictDecoder = + BinaryDictIOUtils.getDictDecoder(dictFile, 0, dictFile.length()); try { final FusionDictionary dict = dictDecoder.readDictionaryBinary(false /* deleteDictIfBroken */); diff --git a/tests/src/com/android/inputmethod/latin/makedict/AbstractDictDecoder.java b/tests/src/com/android/inputmethod/latin/makedict/AbstractDictDecoder.java new file mode 100644 index 000000000..bc856f113 --- /dev/null +++ b/tests/src/com/android/inputmethod/latin/makedict/AbstractDictDecoder.java @@ -0,0 +1,104 @@ +/* + * Copyright (C) 2013 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.inputmethod.latin.makedict; + +import com.android.inputmethod.annotations.UsedForTesting; + +import java.io.FileNotFoundException; +import java.io.IOException; +import java.util.ArrayList; +import java.util.TreeMap; + +/** + * A base class of the binary dictionary decoder. + */ +public abstract class AbstractDictDecoder implements DictDecoder { + private static final int SUCCESS = 0; + private static final int ERROR_CANNOT_READ = 1; + private static final int ERROR_WRONG_FORMAT = 2; + + @Override @UsedForTesting + public int getTerminalPosition(final String word) + throws IOException, UnsupportedFormatException { + if (!isDictBufferOpen()) { + openDictBuffer(); + } + return BinaryDictIOUtils.getTerminalPosition(this, word); + } + + @Override @UsedForTesting + public void readUnigramsAndBigramsBinary(final TreeMap<Integer, String> words, + final TreeMap<Integer, Integer> frequencies, + final TreeMap<Integer, ArrayList<PendingAttribute>> bigrams) + throws IOException, UnsupportedFormatException { + if (!isDictBufferOpen()) { + openDictBuffer(); + } + BinaryDictIOUtils.readUnigramsAndBigramsBinary(this, words, frequencies, bigrams); + } + + /** + * Check whether the header contains the expected information. This is a no-error method, + * that will return an error code and never throw a checked exception. + * @return an error code, either ERROR_* or SUCCESS. + */ + private int checkHeader() { + try { + readHeader(); + } catch (IOException e) { + return ERROR_CANNOT_READ; + } catch (UnsupportedFormatException e) { + return ERROR_WRONG_FORMAT; + } + return SUCCESS; + } + + @Override + public boolean hasValidRawBinaryDictionary() { + return checkHeader() == SUCCESS; + } + + // Placeholder implementations below. These are actually unused. + @Override + public void openDictBuffer() throws FileNotFoundException, IOException, + UnsupportedFormatException { + } + + @Override + public boolean isDictBufferOpen() { + return false; + } + + @Override + public PtNodeInfo readPtNode(final int ptNodePos) { + return null; + } + + @Override + public void setPosition(int newPos) { + } + + @Override + public int getPosition() { + return 0; + } + + @Override + public int readPtNodeCount() { + return 0; + } +} diff --git a/tests/src/com/android/inputmethod/latin/makedict/BinaryDictDecoderEncoderTests.java b/tests/src/com/android/inputmethod/latin/makedict/BinaryDictDecoderEncoderTests.java index 4bf61747c..f29fc21c1 100644 --- a/tests/src/com/android/inputmethod/latin/makedict/BinaryDictDecoderEncoderTests.java +++ b/tests/src/com/android/inputmethod/latin/makedict/BinaryDictDecoderEncoderTests.java @@ -251,7 +251,7 @@ public class BinaryDictDecoderEncoderTests extends AndroidTestCase { FusionDictionary dict = null; try { - final DictDecoder dictDecoder = FormatSpec.getDictDecoder(file, 0, file.length(), + final DictDecoder dictDecoder = BinaryDictIOUtils.getDictDecoder(file, 0, file.length(), bufferType); now = System.currentTimeMillis(); dict = dictDecoder.readDictionaryBinary(false /* deleteDictIfBroken */); @@ -414,7 +414,7 @@ public class BinaryDictDecoderEncoderTests extends AndroidTestCase { long now = -1, diff = -1; try { - final DictDecoder dictDecoder = FormatSpec.getDictDecoder(file, 0, file.length(), + final DictDecoder dictDecoder = BinaryDictIOUtils.getDictDecoder(file, 0, file.length(), bufferType); now = System.currentTimeMillis(); dictDecoder.readUnigramsAndBigramsBinary(resultWords, resultFreqs, resultBigrams); @@ -539,7 +539,7 @@ public class BinaryDictDecoderEncoderTests extends AndroidTestCase { addBigrams(dict, words, bigrams); timeWritingDictToFile(file, dict, formatOptions); - final DictDecoder dictDecoder = FormatSpec.getDictDecoder(file, 0, file.length(), + final DictDecoder dictDecoder = BinaryDictIOUtils.getDictDecoder(file, 0, file.length(), DictDecoder.USE_BYTEARRAY); try { dictDecoder.openDictBuffer(); diff --git a/tests/src/com/android/inputmethod/latin/makedict/BinaryDictDecoderUtils.java b/tests/src/com/android/inputmethod/latin/makedict/BinaryDictDecoderUtils.java new file mode 100644 index 000000000..6f8b07a34 --- /dev/null +++ b/tests/src/com/android/inputmethod/latin/makedict/BinaryDictDecoderUtils.java @@ -0,0 +1,364 @@ +/* + * Copyright (C) 2013 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.inputmethod.latin.makedict; + +import com.android.inputmethod.annotations.UsedForTesting; + +import java.io.File; +import java.io.IOException; +import java.io.OutputStream; +import java.nio.ByteBuffer; + +/** + * Decodes binary files for a FusionDictionary. + * + * All the methods in this class are static. + * + * TODO: Move this file to makedict/internal. + * TODO: Rename this class to DictDecoderUtils. + */ +public final class BinaryDictDecoderUtils { + + private static final boolean DBG = MakedictLog.DBG; + + private BinaryDictDecoderUtils() { + // This utility class is not publicly instantiable. + } + + @UsedForTesting + public interface DictBuffer { + public int readUnsignedByte(); + public int readUnsignedShort(); + public int readUnsignedInt24(); + public int readInt(); + public int position(); + public void position(int newPosition); + @UsedForTesting + public void put(final byte b); + public int limit(); + @UsedForTesting + public int capacity(); + } + + public static final class ByteBufferDictBuffer implements DictBuffer { + private ByteBuffer mBuffer; + + public ByteBufferDictBuffer(final ByteBuffer buffer) { + mBuffer = buffer; + } + + @Override + public int readUnsignedByte() { + return mBuffer.get() & 0xFF; + } + + @Override + public int readUnsignedShort() { + return mBuffer.getShort() & 0xFFFF; + } + + @Override + public int readUnsignedInt24() { + final int retval = readUnsignedByte(); + return (retval << 16) + readUnsignedShort(); + } + + @Override + public int readInt() { + return mBuffer.getInt(); + } + + @Override + public int position() { + return mBuffer.position(); + } + + @Override + public void position(int newPos) { + mBuffer.position(newPos); + } + + @Override + public void put(final byte b) { + mBuffer.put(b); + } + + @Override + public int limit() { + return mBuffer.limit(); + } + + @Override + public int capacity() { + return mBuffer.capacity(); + } + } + + /** + * A class grouping utility function for our specific character encoding. + */ + static final class CharEncoding { + private static final int MINIMAL_ONE_BYTE_CHARACTER_VALUE = 0x20; + private static final int MAXIMAL_ONE_BYTE_CHARACTER_VALUE = 0xFF; + + /** + * Helper method to find out whether this code fits on one byte + */ + private static boolean fitsOnOneByte(final int character) { + return character >= MINIMAL_ONE_BYTE_CHARACTER_VALUE + && character <= MAXIMAL_ONE_BYTE_CHARACTER_VALUE; + } + + /** + * Compute the size of a character given its character code. + * + * Char format is: + * 1 byte = bbbbbbbb match + * case 000xxxxx: xxxxx << 16 + next byte << 8 + next byte + * else: if 00011111 (= 0x1F) : this is the terminator. This is a relevant choice because + * unicode code points range from 0 to 0x10FFFF, so any 3-byte value starting with + * 00011111 would be outside unicode. + * else: iso-latin-1 code + * This allows for the whole unicode range to be encoded, including chars outside of + * the BMP. Also everything in the iso-latin-1 charset is only 1 byte, except control + * characters which should never happen anyway (and still work, but take 3 bytes). + * + * @param character the character code. + * @return the size in binary encoded-form, either 1 or 3 bytes. + */ + static int getCharSize(final int character) { + // See char encoding in FusionDictionary.java + if (fitsOnOneByte(character)) return 1; + if (FormatSpec.INVALID_CHARACTER == character) return 1; + return 3; + } + + /** + * Compute the byte size of a character array. + */ + static int getCharArraySize(final int[] chars) { + int size = 0; + for (int character : chars) size += getCharSize(character); + return size; + } + + /** + * Writes a char array to a byte buffer. + * + * @param codePoints the code point array to write. + * @param buffer the byte buffer to write to. + * @param index the index in buffer to write the character array to. + * @return the index after the last character. + */ + static int writeCharArray(final int[] codePoints, final byte[] buffer, int index) { + for (int codePoint : codePoints) { + if (1 == getCharSize(codePoint)) { + buffer[index++] = (byte)codePoint; + } else { + buffer[index++] = (byte)(0xFF & (codePoint >> 16)); + buffer[index++] = (byte)(0xFF & (codePoint >> 8)); + buffer[index++] = (byte)(0xFF & codePoint); + } + } + return index; + } + + /** + * Writes a string with our character format to a byte buffer. + * + * This will also write the terminator byte. + * + * @param buffer the byte buffer to write to. + * @param origin the offset to write from. + * @param word the string to write. + * @return the size written, in bytes. + */ + static int writeString(final byte[] buffer, final int origin, final String word) { + final int length = word.length(); + int index = origin; + for (int i = 0; i < length; i = word.offsetByCodePoints(i, 1)) { + final int codePoint = word.codePointAt(i); + if (1 == getCharSize(codePoint)) { + buffer[index++] = (byte)codePoint; + } else { + buffer[index++] = (byte)(0xFF & (codePoint >> 16)); + buffer[index++] = (byte)(0xFF & (codePoint >> 8)); + buffer[index++] = (byte)(0xFF & codePoint); + } + } + buffer[index++] = FormatSpec.PTNODE_CHARACTERS_TERMINATOR; + return index - origin; + } + + /** + * Writes a string with our character format to an OutputStream. + * + * This will also write the terminator byte. + * + * @param stream the OutputStream to write to. + * @param word the string to write. + * @return the size written, in bytes. + */ + static int writeString(final OutputStream stream, final String word) throws IOException { + final int length = word.length(); + int written = 0; + for (int i = 0; i < length; i = word.offsetByCodePoints(i, 1)) { + final int codePoint = word.codePointAt(i); + final int charSize = getCharSize(codePoint); + if (1 == charSize) { + stream.write((byte) codePoint); + } else { + stream.write((byte) (0xFF & (codePoint >> 16))); + stream.write((byte) (0xFF & (codePoint >> 8))); + stream.write((byte) (0xFF & codePoint)); + } + written += charSize; + } + stream.write(FormatSpec.PTNODE_CHARACTERS_TERMINATOR); + written += FormatSpec.PTNODE_TERMINATOR_SIZE; + return written; + } + + /** + * Reads a string from a DictBuffer. This is the converse of the above method. + */ + static String readString(final DictBuffer dictBuffer) { + final StringBuilder s = new StringBuilder(); + int character = readChar(dictBuffer); + while (character != FormatSpec.INVALID_CHARACTER) { + s.appendCodePoint(character); + character = readChar(dictBuffer); + } + return s.toString(); + } + + /** + * Reads a character from the buffer. + * + * This follows the character format documented earlier in this source file. + * + * @param dictBuffer the buffer, positioned over an encoded character. + * @return the character code. + */ + static int readChar(final DictBuffer dictBuffer) { + int character = dictBuffer.readUnsignedByte(); + if (!fitsOnOneByte(character)) { + if (FormatSpec.PTNODE_CHARACTERS_TERMINATOR == character) { + return FormatSpec.INVALID_CHARACTER; + } + character <<= 16; + character += dictBuffer.readUnsignedShort(); + } + return character; + } + } + + /** + * Reads and returns the PtNode count out of a buffer and forwards the pointer. + */ + /* package */ static int readPtNodeCount(final DictBuffer dictBuffer) { + final int msb = dictBuffer.readUnsignedByte(); + if (FormatSpec.MAX_PTNODES_FOR_ONE_BYTE_PTNODE_COUNT >= msb) { + return msb; + } else { + return ((FormatSpec.MAX_PTNODES_FOR_ONE_BYTE_PTNODE_COUNT & msb) << 8) + + dictBuffer.readUnsignedByte(); + } + } + + /** + * Finds, as a string, the word at the position passed as an argument. + * + * @param dictDecoder the dict decoder. + * @param headerSize the size of the header. + * @param pos the position to seek. + * @return the word with its frequency, as a weighted string. + */ + @UsedForTesting + /* package for tests */ static WeightedString getWordAtPosition(final DictDecoder dictDecoder, + final int headerSize, final int pos) { + final WeightedString result; + final int originalPos = dictDecoder.getPosition(); + dictDecoder.setPosition(pos); + result = getWordAtPositionWithoutParentAddress(dictDecoder, headerSize, pos); + dictDecoder.setPosition(originalPos); + return result; + } + + private static WeightedString getWordAtPositionWithoutParentAddress( + final DictDecoder dictDecoder, final int headerSize, final int pos) { + dictDecoder.setPosition(headerSize); + final int count = dictDecoder.readPtNodeCount(); + int groupPos = dictDecoder.getPosition(); + final StringBuilder builder = new StringBuilder(); + WeightedString result = null; + + PtNodeInfo last = null; + for (int i = count - 1; i >= 0; --i) { + PtNodeInfo info = dictDecoder.readPtNode(groupPos); + groupPos = info.mEndAddress; + if (info.mOriginalAddress == pos) { + builder.append(new String(info.mCharacters, 0, info.mCharacters.length)); + result = new WeightedString(builder.toString(), info.mProbabilityInfo); + break; // and return + } + if (BinaryDictIOUtils.hasChildrenAddress(info.mChildrenAddress)) { + if (info.mChildrenAddress > pos) { + if (null == last) continue; + builder.append(new String(last.mCharacters, 0, last.mCharacters.length)); + dictDecoder.setPosition(last.mChildrenAddress); + i = dictDecoder.readPtNodeCount(); + groupPos = last.mChildrenAddress + BinaryDictIOUtils.getPtNodeCountSize(i); + last = null; + continue; + } + last = info; + } + if (0 == i && BinaryDictIOUtils.hasChildrenAddress(last.mChildrenAddress)) { + builder.append(new String(last.mCharacters, 0, last.mCharacters.length)); + dictDecoder.setPosition(last.mChildrenAddress); + i = dictDecoder.readPtNodeCount(); + groupPos = last.mChildrenAddress + BinaryDictIOUtils.getPtNodeCountSize(i); + last = null; + continue; + } + } + return result; + } + + /** + * Helper method to pass a file name instead of a File object to isBinaryDictionary. + */ + public static boolean isBinaryDictionary(final String filename) { + final File file = new File(filename); + return isBinaryDictionary(file); + } + + /** + * Basic test to find out whether the file is a binary dictionary or not. + * + * @param file The file to test. + * @return true if it's a binary dictionary, false otherwise + */ + public static boolean isBinaryDictionary(final File file) { + final DictDecoder dictDecoder = BinaryDictIOUtils.getDictDecoder(file, 0, file.length()); + if (dictDecoder == null) { + return false; + } + return dictDecoder.hasValidRawBinaryDictionary(); + } +} diff --git a/tests/src/com/android/inputmethod/latin/makedict/BinaryDictEncoderUtils.java b/tests/src/com/android/inputmethod/latin/makedict/BinaryDictEncoderUtils.java new file mode 100644 index 000000000..39bd98bad --- /dev/null +++ b/tests/src/com/android/inputmethod/latin/makedict/BinaryDictEncoderUtils.java @@ -0,0 +1,881 @@ +/* + * Copyright (C) 2013 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.inputmethod.latin.makedict; + +import com.android.inputmethod.annotations.UsedForTesting; +import com.android.inputmethod.latin.makedict.BinaryDictDecoderUtils.CharEncoding; +import com.android.inputmethod.latin.makedict.BinaryDictDecoderUtils.DictBuffer; +import com.android.inputmethod.latin.makedict.FormatSpec.FormatOptions; +import com.android.inputmethod.latin.makedict.FusionDictionary.PtNode; +import com.android.inputmethod.latin.makedict.FusionDictionary.PtNodeArray; + +import java.io.ByteArrayOutputStream; +import java.io.IOException; +import java.io.OutputStream; +import java.util.ArrayList; + +/** + * Encodes binary files for a FusionDictionary. + * + * All the methods in this class are static. + * + * TODO: Rename this class to DictEncoderUtils. + */ +public class BinaryDictEncoderUtils { + + private static final boolean DBG = MakedictLog.DBG; + + private BinaryDictEncoderUtils() { + // This utility class is not publicly instantiable. + } + + // Arbitrary limit to how much passes we consider address size compression should + // terminate in. At the time of this writing, our largest dictionary completes + // compression in five passes. + // If the number of passes exceeds this number, makedict bails with an exception on + // suspicion that a bug might be causing an infinite loop. + private static final int MAX_PASSES = 24; + + /** + * Compute the binary size of the character array. + * + * If only one character, this is the size of this character. If many, it's the sum of their + * sizes + 1 byte for the terminator. + * + * @param characters the character array + * @return the size of the char array, including the terminator if any + */ + static int getPtNodeCharactersSize(final int[] characters) { + int size = CharEncoding.getCharArraySize(characters); + if (characters.length > 1) size += FormatSpec.PTNODE_TERMINATOR_SIZE; + return size; + } + + /** + * Compute the binary size of the character array in a PtNode + * + * If only one character, this is the size of this character. If many, it's the sum of their + * sizes + 1 byte for the terminator. + * + * @param ptNode the PtNode + * @return the size of the char array, including the terminator if any + */ + private static int getPtNodeCharactersSize(final PtNode ptNode) { + return getPtNodeCharactersSize(ptNode.mChars); + } + + /** + * Compute the binary size of the PtNode count for a node array. + * @param nodeArray the nodeArray + * @return the size of the PtNode count, either 1 or 2 bytes. + */ + private static int getPtNodeCountSize(final PtNodeArray nodeArray) { + return BinaryDictIOUtils.getPtNodeCountSize(nodeArray.mData.size()); + } + + /** + * Compute the size of a shortcut in bytes. + */ + private static int getShortcutSize(final WeightedString shortcut) { + int size = FormatSpec.PTNODE_ATTRIBUTE_FLAGS_SIZE; + final String word = shortcut.mWord; + final int length = word.length(); + for (int i = 0; i < length; i = word.offsetByCodePoints(i, 1)) { + final int codePoint = word.codePointAt(i); + size += CharEncoding.getCharSize(codePoint); + } + size += FormatSpec.PTNODE_TERMINATOR_SIZE; + return size; + } + + /** + * Compute the size of a shortcut list in bytes. + * + * This is known in advance and does not change according to position in the file + * like address lists do. + */ + static int getShortcutListSize(final ArrayList<WeightedString> shortcutList) { + if (null == shortcutList || shortcutList.isEmpty()) return 0; + int size = FormatSpec.PTNODE_SHORTCUT_LIST_SIZE_SIZE; + for (final WeightedString shortcut : shortcutList) { + size += getShortcutSize(shortcut); + } + return size; + } + + /** + * Compute the maximum size of a PtNode, assuming 3-byte addresses for everything. + * + * @param ptNode the PtNode to compute the size of. + * @return the maximum size of the PtNode. + */ + private static int getPtNodeMaximumSize(final PtNode ptNode) { + int size = getNodeHeaderSize(ptNode); + if (ptNode.isTerminal()) { + // If terminal, one byte for the frequency. + size += FormatSpec.PTNODE_FREQUENCY_SIZE; + } + size += FormatSpec.PTNODE_MAX_ADDRESS_SIZE; // For children address + size += getShortcutListSize(ptNode.mShortcutTargets); + if (null != ptNode.mBigrams) { + size += (FormatSpec.PTNODE_ATTRIBUTE_FLAGS_SIZE + + FormatSpec.PTNODE_ATTRIBUTE_MAX_ADDRESS_SIZE) + * ptNode.mBigrams.size(); + } + return size; + } + + /** + * Compute the maximum size of each PtNode of a PtNode array, assuming 3-byte addresses for + * everything, and caches it in the `mCachedSize' member of the nodes; deduce the size of + * the containing node array, and cache it it its 'mCachedSize' member. + * + * @param ptNodeArray the node array to compute the maximum size of. + */ + private static void calculatePtNodeArrayMaximumSize(final PtNodeArray ptNodeArray) { + int size = getPtNodeCountSize(ptNodeArray); + for (PtNode node : ptNodeArray.mData) { + final int nodeSize = getPtNodeMaximumSize(node); + node.mCachedSize = nodeSize; + size += nodeSize; + } + ptNodeArray.mCachedSize = size; + } + + /** + * Compute the size of the header (flag + [parent address] + characters size) of a PtNode. + * + * @param ptNode the PtNode of which to compute the size of the header + */ + private static int getNodeHeaderSize(final PtNode ptNode) { + return FormatSpec.PTNODE_FLAGS_SIZE + getPtNodeCharactersSize(ptNode); + } + + /** + * Compute the size, in bytes, that an address will occupy. + * + * This can be used either for children addresses (which are always positive) or for + * attribute, which may be positive or negative but + * store their sign bit separately. + * + * @param address the address + * @return the byte size. + */ + static int getByteSize(final int address) { + assert(address <= FormatSpec.UINT24_MAX); + if (!BinaryDictIOUtils.hasChildrenAddress(address)) { + return 0; + } else if (Math.abs(address) <= FormatSpec.UINT8_MAX) { + return 1; + } else if (Math.abs(address) <= FormatSpec.UINT16_MAX) { + return 2; + } else { + return 3; + } + } + + static int writeUIntToBuffer(final byte[] buffer, int position, final int value, + final int size) { + switch(size) { + case 4: + buffer[position++] = (byte) ((value >> 24) & 0xFF); + /* fall through */ + case 3: + buffer[position++] = (byte) ((value >> 16) & 0xFF); + /* fall through */ + case 2: + buffer[position++] = (byte) ((value >> 8) & 0xFF); + /* fall through */ + case 1: + buffer[position++] = (byte) (value & 0xFF); + break; + default: + /* nop */ + } + return position; + } + + static void writeUIntToStream(final OutputStream stream, final int value, final int size) + throws IOException { + switch(size) { + case 4: + stream.write((value >> 24) & 0xFF); + /* fall through */ + case 3: + stream.write((value >> 16) & 0xFF); + /* fall through */ + case 2: + stream.write((value >> 8) & 0xFF); + /* fall through */ + case 1: + stream.write(value & 0xFF); + break; + default: + /* nop */ + } + } + + @UsedForTesting + static void writeUIntToDictBuffer(final DictBuffer dictBuffer, final int value, + final int size) { + switch(size) { + case 4: + dictBuffer.put((byte) ((value >> 24) & 0xFF)); + /* fall through */ + case 3: + dictBuffer.put((byte) ((value >> 16) & 0xFF)); + /* fall through */ + case 2: + dictBuffer.put((byte) ((value >> 8) & 0xFF)); + /* fall through */ + case 1: + dictBuffer.put((byte) (value & 0xFF)); + break; + default: + /* nop */ + } + } + + // End utility methods + + // This method is responsible for finding a nice ordering of the nodes that favors run-time + // cache performance and dictionary size. + /* package for tests */ static ArrayList<PtNodeArray> flattenTree( + final PtNodeArray rootNodeArray) { + final int treeSize = FusionDictionary.countPtNodes(rootNodeArray); + MakedictLog.i("Counted nodes : " + treeSize); + final ArrayList<PtNodeArray> flatTree = new ArrayList<PtNodeArray>(treeSize); + return flattenTreeInner(flatTree, rootNodeArray); + } + + private static ArrayList<PtNodeArray> flattenTreeInner(final ArrayList<PtNodeArray> list, + final PtNodeArray ptNodeArray) { + // Removing the node is necessary if the tails are merged, because we would then + // add the same node several times when we only want it once. A number of places in + // the code also depends on any node being only once in the list. + // Merging tails can only be done if there are no attributes. Searching for attributes + // in LatinIME code depends on a total breadth-first ordering, which merging tails + // breaks. If there are no attributes, it should be fine (and reduce the file size) + // to merge tails, and removing the node from the list would be necessary. However, + // we don't merge tails because breaking the breadth-first ordering would result in + // extreme overhead at bigram lookup time (it would make the search function O(n) instead + // of the current O(log(n)), where n=number of nodes in the dictionary which is pretty + // high). + // If no nodes are ever merged, we can't have the same node twice in the list, hence + // searching for duplicates in unnecessary. It is also very performance consuming, + // since `list' is an ArrayList so it's an O(n) operation that runs on all nodes, making + // this simple list.remove operation O(n*n) overall. On Android this overhead is very + // high. + // For future reference, the code to remove duplicate is a simple : list.remove(node); + list.add(ptNodeArray); + final ArrayList<PtNode> branches = ptNodeArray.mData; + for (PtNode ptNode : branches) { + if (null != ptNode.mChildren) flattenTreeInner(list, ptNode.mChildren); + } + return list; + } + + /** + * Get the offset from a position inside a current node array to a target node array, during + * update. + * + * If the current node array is before the target node array, the target node array has not + * been updated yet, so we should return the offset from the old position of the current node + * array to the old position of the target node array. If on the other hand the target is + * before the current node array, it already has been updated, so we should return the offset + * from the new position in the current node array to the new position in the target node + * array. + * + * @param currentNodeArray node array containing the PtNode where the offset will be written + * @param offsetFromStartOfCurrentNodeArray offset, in bytes, from the start of currentNodeArray + * @param targetNodeArray the target node array to get the offset to + * @return the offset to the target node array + */ + private static int getOffsetToTargetNodeArrayDuringUpdate(final PtNodeArray currentNodeArray, + final int offsetFromStartOfCurrentNodeArray, final PtNodeArray targetNodeArray) { + final boolean isTargetBeforeCurrent = (targetNodeArray.mCachedAddressBeforeUpdate + < currentNodeArray.mCachedAddressBeforeUpdate); + if (isTargetBeforeCurrent) { + return targetNodeArray.mCachedAddressAfterUpdate + - (currentNodeArray.mCachedAddressAfterUpdate + + offsetFromStartOfCurrentNodeArray); + } else { + return targetNodeArray.mCachedAddressBeforeUpdate + - (currentNodeArray.mCachedAddressBeforeUpdate + + offsetFromStartOfCurrentNodeArray); + } + } + + /** + * Get the offset from a position inside a current node array to a target PtNode, during + * update. + * + * @param currentNodeArray node array containing the PtNode where the offset will be written + * @param offsetFromStartOfCurrentNodeArray offset, in bytes, from the start of currentNodeArray + * @param targetPtNode the target PtNode to get the offset to + * @return the offset to the target PtNode + */ + // TODO: is there any way to factorize this method with the one above? + private static int getOffsetToTargetPtNodeDuringUpdate(final PtNodeArray currentNodeArray, + final int offsetFromStartOfCurrentNodeArray, final PtNode targetPtNode) { + final int oldOffsetBasePoint = currentNodeArray.mCachedAddressBeforeUpdate + + offsetFromStartOfCurrentNodeArray; + final boolean isTargetBeforeCurrent = (targetPtNode.mCachedAddressBeforeUpdate + < oldOffsetBasePoint); + // If the target is before the current node array, then its address has already been + // updated. We can use the AfterUpdate member, and compare it to our own member after + // update. Otherwise, the AfterUpdate member is not updated yet, so we need to use the + // BeforeUpdate member, and of course we have to compare this to our own address before + // update. + if (isTargetBeforeCurrent) { + final int newOffsetBasePoint = currentNodeArray.mCachedAddressAfterUpdate + + offsetFromStartOfCurrentNodeArray; + return targetPtNode.mCachedAddressAfterUpdate - newOffsetBasePoint; + } else { + return targetPtNode.mCachedAddressBeforeUpdate - oldOffsetBasePoint; + } + } + + /** + * Computes the actual node array size, based on the cached addresses of the children nodes. + * + * Each node array stores its tentative address. During dictionary address computing, these + * are not final, but they can be used to compute the node array size (the node array size + * depends on the address of the children because the number of bytes necessary to store an + * address depends on its numeric value. The return value indicates whether the node array + * contents (as in, any of the addresses stored in the cache fields) have changed with + * respect to their previous value. + * + * @param ptNodeArray the node array to compute the size of. + * @param dict the dictionary in which the word/attributes are to be found. + * @return false if none of the cached addresses inside the node array changed, true otherwise. + */ + private static boolean computeActualPtNodeArraySize(final PtNodeArray ptNodeArray, + final FusionDictionary dict) { + boolean changed = false; + int size = getPtNodeCountSize(ptNodeArray); + for (PtNode ptNode : ptNodeArray.mData) { + ptNode.mCachedAddressAfterUpdate = ptNodeArray.mCachedAddressAfterUpdate + size; + if (ptNode.mCachedAddressAfterUpdate != ptNode.mCachedAddressBeforeUpdate) { + changed = true; + } + int nodeSize = getNodeHeaderSize(ptNode); + if (ptNode.isTerminal()) { + nodeSize += FormatSpec.PTNODE_FREQUENCY_SIZE; + } + if (null != ptNode.mChildren) { + nodeSize += getByteSize(getOffsetToTargetNodeArrayDuringUpdate(ptNodeArray, + nodeSize + size, ptNode.mChildren)); + } + nodeSize += getShortcutListSize(ptNode.mShortcutTargets); + if (null != ptNode.mBigrams) { + for (WeightedString bigram : ptNode.mBigrams) { + final int offset = getOffsetToTargetPtNodeDuringUpdate(ptNodeArray, + nodeSize + size + FormatSpec.PTNODE_ATTRIBUTE_FLAGS_SIZE, + FusionDictionary.findWordInTree(dict.mRootNodeArray, bigram.mWord)); + nodeSize += getByteSize(offset) + FormatSpec.PTNODE_ATTRIBUTE_FLAGS_SIZE; + } + } + ptNode.mCachedSize = nodeSize; + size += nodeSize; + } + if (ptNodeArray.mCachedSize != size) { + ptNodeArray.mCachedSize = size; + changed = true; + } + return changed; + } + + /** + * Initializes the cached addresses of node arrays and their containing nodes from their size. + * + * @param flatNodes the list of node arrays. + * @return the byte size of the entire stack. + */ + private static int initializePtNodeArraysCachedAddresses( + final ArrayList<PtNodeArray> flatNodes) { + int nodeArrayOffset = 0; + for (final PtNodeArray nodeArray : flatNodes) { + nodeArray.mCachedAddressBeforeUpdate = nodeArrayOffset; + int nodeCountSize = getPtNodeCountSize(nodeArray); + int nodeffset = 0; + for (final PtNode ptNode : nodeArray.mData) { + ptNode.mCachedAddressBeforeUpdate = ptNode.mCachedAddressAfterUpdate = + nodeCountSize + nodeArrayOffset + nodeffset; + nodeffset += ptNode.mCachedSize; + } + nodeArrayOffset += nodeArray.mCachedSize; + } + return nodeArrayOffset; + } + + /** + * Updates the cached addresses of node arrays after recomputing their new positions. + * + * @param flatNodes the list of node arrays. + */ + private static void updatePtNodeArraysCachedAddresses(final ArrayList<PtNodeArray> flatNodes) { + for (final PtNodeArray nodeArray : flatNodes) { + nodeArray.mCachedAddressBeforeUpdate = nodeArray.mCachedAddressAfterUpdate; + for (final PtNode ptNode : nodeArray.mData) { + ptNode.mCachedAddressBeforeUpdate = ptNode.mCachedAddressAfterUpdate; + } + } + } + + /** + * Compute the addresses and sizes of an ordered list of PtNode arrays. + * + * This method takes a list of PtNode arrays and will update their cached address and size + * values so that they can be written into a file. It determines the smallest size each of the + * PtNode arrays can be given the addresses of its children and attributes, and store that into + * each PtNode. + * The order of the PtNode is given by the order of the array. This method makes no effort + * to find a good order; it only mechanically computes the size this order results in. + * + * @param dict the dictionary + * @param flatNodes the ordered list of PtNode arrays + * @return the same array it was passed. The nodes have been updated for address and size. + */ + /* package */ static ArrayList<PtNodeArray> computeAddresses(final FusionDictionary dict, + final ArrayList<PtNodeArray> flatNodes) { + // First get the worst possible sizes and offsets + for (final PtNodeArray n : flatNodes) { + calculatePtNodeArrayMaximumSize(n); + } + final int offset = initializePtNodeArraysCachedAddresses(flatNodes); + + MakedictLog.i("Compressing the array addresses. Original size : " + offset); + MakedictLog.i("(Recursively seen size : " + offset + ")"); + + int passes = 0; + boolean changesDone = false; + do { + changesDone = false; + int ptNodeArrayStartOffset = 0; + for (final PtNodeArray ptNodeArray : flatNodes) { + ptNodeArray.mCachedAddressAfterUpdate = ptNodeArrayStartOffset; + final int oldNodeArraySize = ptNodeArray.mCachedSize; + final boolean changed = computeActualPtNodeArraySize(ptNodeArray, dict); + final int newNodeArraySize = ptNodeArray.mCachedSize; + if (oldNodeArraySize < newNodeArraySize) { + throw new RuntimeException("Increased size ?!"); + } + ptNodeArrayStartOffset += newNodeArraySize; + changesDone |= changed; + } + updatePtNodeArraysCachedAddresses(flatNodes); + ++passes; + if (passes > MAX_PASSES) throw new RuntimeException("Too many passes - probably a bug"); + } while (changesDone); + + final PtNodeArray lastPtNodeArray = flatNodes.get(flatNodes.size() - 1); + MakedictLog.i("Compression complete in " + passes + " passes."); + MakedictLog.i("After address compression : " + + (lastPtNodeArray.mCachedAddressAfterUpdate + lastPtNodeArray.mCachedSize)); + + return flatNodes; + } + + /** + * Sanity-checking method. + * + * This method checks a list of PtNode arrays for juxtaposition, that is, it will do + * nothing if each node array's cached address is actually the previous node array's address + * plus the previous node's size. + * If this is not the case, it will throw an exception. + * + * @param arrays the list of node arrays to check + */ + /* package */ static void checkFlatPtNodeArrayList(final ArrayList<PtNodeArray> arrays) { + int offset = 0; + int index = 0; + for (final PtNodeArray ptNodeArray : arrays) { + // BeforeUpdate and AfterUpdate addresses are the same here, so it does not matter + // which we use. + if (ptNodeArray.mCachedAddressAfterUpdate != offset) { + throw new RuntimeException("Wrong address for node " + index + + " : expected " + offset + ", got " + + ptNodeArray.mCachedAddressAfterUpdate); + } + ++index; + offset += ptNodeArray.mCachedSize; + } + } + + /** + * Helper method to write a children position to a file. + * + * @param buffer the buffer to write to. + * @param index the index in the buffer to write the address to. + * @param position the position to write. + * @return the size in bytes the address actually took. + */ + /* package */ static int writeChildrenPosition(final byte[] buffer, int index, + final int position) { + switch (getByteSize(position)) { + case 1: + buffer[index++] = (byte)position; + return 1; + case 2: + buffer[index++] = (byte)(0xFF & (position >> 8)); + buffer[index++] = (byte)(0xFF & position); + return 2; + case 3: + buffer[index++] = (byte)(0xFF & (position >> 16)); + buffer[index++] = (byte)(0xFF & (position >> 8)); + buffer[index++] = (byte)(0xFF & position); + return 3; + case 0: + return 0; + default: + throw new RuntimeException("Position " + position + " has a strange size"); + } + } + + /** + * Helper method to write a signed children position to a file. + * + * @param buffer the buffer to write to. + * @param index the index in the buffer to write the address to. + * @param position the position to write. + * @return the size in bytes the address actually took. + */ + /* package */ static int writeSignedChildrenPosition(final byte[] buffer, int index, + final int position) { + if (!BinaryDictIOUtils.hasChildrenAddress(position)) { + buffer[index] = buffer[index + 1] = buffer[index + 2] = 0; + } else { + final int absPosition = Math.abs(position); + buffer[index++] = + (byte)((position < 0 ? FormatSpec.MSB8 : 0) | (0xFF & (absPosition >> 16))); + buffer[index++] = (byte)(0xFF & (absPosition >> 8)); + buffer[index++] = (byte)(0xFF & absPosition); + } + return 3; + } + + /** + * Makes the flag value for a PtNode. + * + * @param hasMultipleChars whether the PtNode has multiple chars. + * @param isTerminal whether the PtNode is terminal. + * @param childrenAddressSize the size of a children address. + * @param hasShortcuts whether the PtNode has shortcuts. + * @param hasBigrams whether the PtNode has bigrams. + * @param isNotAWord whether the PtNode is not a word. + * @param isBlackListEntry whether the PtNode is a blacklist entry. + * @return the flags + */ + static int makePtNodeFlags(final boolean hasMultipleChars, final boolean isTerminal, + final int childrenAddressSize, final boolean hasShortcuts, final boolean hasBigrams, + final boolean isNotAWord, final boolean isBlackListEntry) { + byte flags = 0; + if (hasMultipleChars) flags |= FormatSpec.FLAG_HAS_MULTIPLE_CHARS; + if (isTerminal) flags |= FormatSpec.FLAG_IS_TERMINAL; + switch (childrenAddressSize) { + case 1: + flags |= FormatSpec.FLAG_CHILDREN_ADDRESS_TYPE_ONEBYTE; + break; + case 2: + flags |= FormatSpec.FLAG_CHILDREN_ADDRESS_TYPE_TWOBYTES; + break; + case 3: + flags |= FormatSpec.FLAG_CHILDREN_ADDRESS_TYPE_THREEBYTES; + break; + case 0: + flags |= FormatSpec.FLAG_CHILDREN_ADDRESS_TYPE_NOADDRESS; + break; + default: + throw new RuntimeException("Node with a strange address"); + } + if (hasShortcuts) flags |= FormatSpec.FLAG_HAS_SHORTCUT_TARGETS; + if (hasBigrams) flags |= FormatSpec.FLAG_HAS_BIGRAMS; + if (isNotAWord) flags |= FormatSpec.FLAG_IS_NOT_A_WORD; + if (isBlackListEntry) flags |= FormatSpec.FLAG_IS_BLACKLISTED; + return flags; + } + + /* package */ static byte makePtNodeFlags(final PtNode node, final int childrenOffset) { + return (byte) makePtNodeFlags(node.mChars.length > 1, node.isTerminal(), + getByteSize(childrenOffset), + node.mShortcutTargets != null && !node.mShortcutTargets.isEmpty(), + node.mBigrams != null && !node.mBigrams.isEmpty(), + node.mIsNotAWord, node.mIsBlacklistEntry); + } + + /** + * Makes the flag value for a bigram. + * + * @param more whether there are more bigrams after this one. + * @param offset the offset of the bigram. + * @param bigramFrequency the frequency of the bigram, 0..255. + * @param unigramFrequency the unigram frequency of the same word, 0..255. + * @param word the second bigram, for debugging purposes + * @return the flags + */ + /* package */ static final int makeBigramFlags(final boolean more, final int offset, + int bigramFrequency, final int unigramFrequency, final String word) { + int bigramFlags = (more ? FormatSpec.FLAG_BIGRAM_SHORTCUT_ATTR_HAS_NEXT : 0) + + (offset < 0 ? FormatSpec.FLAG_BIGRAM_ATTR_OFFSET_NEGATIVE : 0); + switch (getByteSize(offset)) { + case 1: + bigramFlags |= FormatSpec.FLAG_BIGRAM_ATTR_ADDRESS_TYPE_ONEBYTE; + break; + case 2: + bigramFlags |= FormatSpec.FLAG_BIGRAM_ATTR_ADDRESS_TYPE_TWOBYTES; + break; + case 3: + bigramFlags |= FormatSpec.FLAG_BIGRAM_ATTR_ADDRESS_TYPE_THREEBYTES; + break; + default: + throw new RuntimeException("Strange offset size"); + } + if (unigramFrequency > bigramFrequency) { + MakedictLog.e("Unigram freq is superior to bigram freq for \"" + word + + "\". Bigram freq is " + bigramFrequency + ", unigram freq for " + + word + " is " + unigramFrequency); + bigramFrequency = unigramFrequency; + } + bigramFlags += getBigramFrequencyDiff(unigramFrequency, bigramFrequency) + & FormatSpec.FLAG_BIGRAM_SHORTCUT_ATTR_FREQUENCY; + return bigramFlags; + } + + public static int getBigramFrequencyDiff(final int unigramFrequency, + final int bigramFrequency) { + // We compute the difference between 255 (which means probability = 1) and the + // unigram score. We split this into a number of discrete steps. + // Now, the steps are numbered 0~15; 0 represents an increase of 1 step while 15 + // represents an increase of 16 steps: a value of 15 will be interpreted as the median + // value of the 16th step. In all justice, if the bigram frequency is low enough to be + // rounded below the first step (which means it is less than half a step higher than the + // unigram frequency) then the unigram frequency itself is the best approximation of the + // bigram freq that we could possibly supply, hence we should *not* include this bigram + // in the file at all. + // until this is done, we'll write 0 and slightly overestimate this case. + // In other words, 0 means "between 0.5 step and 1.5 step", 1 means "between 1.5 step + // and 2.5 steps", and 15 means "between 15.5 steps and 16.5 steps". So we want to + // divide our range [unigramFreq..MAX_TERMINAL_FREQUENCY] in 16.5 steps to get the + // step size. Then we compute the start of the first step (the one where value 0 starts) + // by adding half-a-step to the unigramFrequency. From there, we compute the integer + // number of steps to the bigramFrequency. One last thing: we want our steps to include + // their lower bound and exclude their higher bound so we need to have the first step + // start at exactly 1 unit higher than floor(unigramFreq + half a step). + // Note : to reconstruct the score, the dictionary reader will need to divide + // MAX_TERMINAL_FREQUENCY - unigramFreq by 16.5 likewise to get the value of the step, + // and add (discretizedFrequency + 0.5 + 0.5) times this value to get the best + // approximation. (0.5 to get the first step start, and 0.5 to get the middle of the + // step pointed by the discretized frequency. + final float stepSize = + (FormatSpec.MAX_TERMINAL_FREQUENCY - unigramFrequency) + / (1.5f + FormatSpec.MAX_BIGRAM_FREQUENCY); + final float firstStepStart = 1 + unigramFrequency + (stepSize / 2.0f); + final int discretizedFrequency = (int)((bigramFrequency - firstStepStart) / stepSize); + // If the bigram freq is less than half-a-step higher than the unigram freq, we get -1 + // here. The best approximation would be the unigram freq itself, so we should not + // include this bigram in the dictionary. For now, register as 0, and live with the + // small over-estimation that we get in this case. TODO: actually remove this bigram + // if discretizedFrequency < 0. + return discretizedFrequency > 0 ? discretizedFrequency : 0; + } + + /** + * Makes the flag value for a shortcut. + * + * @param more whether there are more attributes after this one. + * @param frequency the frequency of the attribute, 0..15 + * @return the flags + */ + static final int makeShortcutFlags(final boolean more, final int frequency) { + return (more ? FormatSpec.FLAG_BIGRAM_SHORTCUT_ATTR_HAS_NEXT : 0) + + (frequency & FormatSpec.FLAG_BIGRAM_SHORTCUT_ATTR_FREQUENCY); + } + + /* package */ static final int getChildrenPosition(final PtNode ptNode) { + int positionOfChildrenPosField = ptNode.mCachedAddressAfterUpdate + + getNodeHeaderSize(ptNode); + if (ptNode.isTerminal()) { + // A terminal node has the frequency. + // If positionOfChildrenPosField is incorrect, we may crash when jumping to the children + // position. + positionOfChildrenPosField += FormatSpec.PTNODE_FREQUENCY_SIZE; + } + return null == ptNode.mChildren ? FormatSpec.NO_CHILDREN_ADDRESS + : ptNode.mChildren.mCachedAddressAfterUpdate - positionOfChildrenPosField; + } + + /** + * Write a PtNodeArray. The PtNodeArray is expected to have its final position cached. + * + * @param dict the dictionary the node array is a part of (for relative offsets). + * @param dictEncoder the dictionary encoder. + * @param ptNodeArray the node array to write. + */ + @SuppressWarnings("unused") + /* package */ static void writePlacedPtNodeArray(final FusionDictionary dict, + final DictEncoder dictEncoder, final PtNodeArray ptNodeArray) { + // TODO: Make the code in common with BinaryDictIOUtils#writePtNode + dictEncoder.setPosition(ptNodeArray.mCachedAddressAfterUpdate); + + final int ptNodeCount = ptNodeArray.mData.size(); + dictEncoder.writePtNodeCount(ptNodeCount); + final int parentPosition = + (ptNodeArray.mCachedParentAddress == FormatSpec.NO_PARENT_ADDRESS) + ? FormatSpec.NO_PARENT_ADDRESS + : ptNodeArray.mCachedParentAddress + ptNodeArray.mCachedAddressAfterUpdate; + for (int i = 0; i < ptNodeCount; ++i) { + final PtNode ptNode = ptNodeArray.mData.get(i); + if (dictEncoder.getPosition() != ptNode.mCachedAddressAfterUpdate) { + throw new RuntimeException("Bug: write index is not the same as the cached address " + + "of the node : " + dictEncoder.getPosition() + " <> " + + ptNode.mCachedAddressAfterUpdate); + } + // Sanity checks. + if (DBG && ptNode.getProbability() > FormatSpec.MAX_TERMINAL_FREQUENCY) { + throw new RuntimeException("A node has a frequency > " + + FormatSpec.MAX_TERMINAL_FREQUENCY + + " : " + ptNode.mProbabilityInfo.toString()); + } + dictEncoder.writePtNode(ptNode, dict); + } + if (dictEncoder.getPosition() != ptNodeArray.mCachedAddressAfterUpdate + + ptNodeArray.mCachedSize) { + throw new RuntimeException("Not the same size : written " + + (dictEncoder.getPosition() - ptNodeArray.mCachedAddressAfterUpdate) + + " bytes from a node that should have " + ptNodeArray.mCachedSize + " bytes"); + } + } + + /** + * Dumps a collection of useful statistics about a list of PtNode arrays. + * + * This prints purely informative stuff, like the total estimated file size, the + * number of PtNode arrays, of PtNodes, the repartition of each address size, etc + * + * @param ptNodeArrays the list of PtNode arrays. + */ + /* package */ static void showStatistics(ArrayList<PtNodeArray> ptNodeArrays) { + int firstTerminalAddress = Integer.MAX_VALUE; + int lastTerminalAddress = Integer.MIN_VALUE; + int size = 0; + int ptNodes = 0; + int maxNodes = 0; + int maxRuns = 0; + for (final PtNodeArray ptNodeArray : ptNodeArrays) { + if (maxNodes < ptNodeArray.mData.size()) maxNodes = ptNodeArray.mData.size(); + for (final PtNode ptNode : ptNodeArray.mData) { + ++ptNodes; + if (ptNode.mChars.length > maxRuns) maxRuns = ptNode.mChars.length; + if (ptNode.isTerminal()) { + if (ptNodeArray.mCachedAddressAfterUpdate < firstTerminalAddress) + firstTerminalAddress = ptNodeArray.mCachedAddressAfterUpdate; + if (ptNodeArray.mCachedAddressAfterUpdate > lastTerminalAddress) + lastTerminalAddress = ptNodeArray.mCachedAddressAfterUpdate; + } + } + if (ptNodeArray.mCachedAddressAfterUpdate + ptNodeArray.mCachedSize > size) { + size = ptNodeArray.mCachedAddressAfterUpdate + ptNodeArray.mCachedSize; + } + } + final int[] ptNodeCounts = new int[maxNodes + 1]; + final int[] runCounts = new int[maxRuns + 1]; + for (final PtNodeArray ptNodeArray : ptNodeArrays) { + ++ptNodeCounts[ptNodeArray.mData.size()]; + for (final PtNode ptNode : ptNodeArray.mData) { + ++runCounts[ptNode.mChars.length]; + } + } + + MakedictLog.i("Statistics:\n" + + " total file size " + size + "\n" + + " " + ptNodeArrays.size() + " node arrays\n" + + " " + ptNodes + " PtNodes (" + ((float)ptNodes / ptNodeArrays.size()) + + " PtNodes per node)\n" + + " first terminal at " + firstTerminalAddress + "\n" + + " last terminal at " + lastTerminalAddress + "\n" + + " PtNode stats : max = " + maxNodes); + for (int i = 0; i < ptNodeCounts.length; ++i) { + MakedictLog.i(" " + i + " : " + ptNodeCounts[i]); + } + MakedictLog.i(" Character run stats : max = " + maxRuns); + for (int i = 0; i < runCounts.length; ++i) { + MakedictLog.i(" " + i + " : " + runCounts[i]); + } + } + + /** + * Writes a file header to an output stream. + * + * @param destination the stream to write the file header to. + * @param dict the dictionary to write. + * @param formatOptions file format options. + * @return the size of the header. + */ + /* package */ static int writeDictionaryHeader(final OutputStream destination, + final FusionDictionary dict, final FormatOptions formatOptions) + throws IOException, UnsupportedFormatException { + final int version = formatOptions.mVersion; + if (version < FormatSpec.MINIMUM_SUPPORTED_VERSION + || version > FormatSpec.MAXIMUM_SUPPORTED_VERSION) { + throw new UnsupportedFormatException("Requested file format version " + version + + ", but this implementation only supports versions " + + FormatSpec.MINIMUM_SUPPORTED_VERSION + " through " + + FormatSpec.MAXIMUM_SUPPORTED_VERSION); + } + + ByteArrayOutputStream headerBuffer = new ByteArrayOutputStream(256); + + // The magic number in big-endian order. + // Magic number for all versions. + headerBuffer.write((byte) (0xFF & (FormatSpec.MAGIC_NUMBER >> 24))); + headerBuffer.write((byte) (0xFF & (FormatSpec.MAGIC_NUMBER >> 16))); + headerBuffer.write((byte) (0xFF & (FormatSpec.MAGIC_NUMBER >> 8))); + headerBuffer.write((byte) (0xFF & FormatSpec.MAGIC_NUMBER)); + // Dictionary version. + headerBuffer.write((byte) (0xFF & (version >> 8))); + headerBuffer.write((byte) (0xFF & version)); + + // Options flags + // TODO: Remove this field. + final int options = 0; + headerBuffer.write((byte) (0xFF & (options >> 8))); + headerBuffer.write((byte) (0xFF & options)); + final int headerSizeOffset = headerBuffer.size(); + // Placeholder to be written later with header size. + for (int i = 0; i < 4; ++i) { + headerBuffer.write(0); + } + // Write out the options. + for (final String key : dict.mOptions.mAttributes.keySet()) { + final String value = dict.mOptions.mAttributes.get(key); + CharEncoding.writeString(headerBuffer, key); + CharEncoding.writeString(headerBuffer, value); + } + final int size = headerBuffer.size(); + final byte[] bytes = headerBuffer.toByteArray(); + // Write out the header size. + bytes[headerSizeOffset] = (byte) (0xFF & (size >> 24)); + bytes[headerSizeOffset + 1] = (byte) (0xFF & (size >> 16)); + bytes[headerSizeOffset + 2] = (byte) (0xFF & (size >> 8)); + bytes[headerSizeOffset + 3] = (byte) (0xFF & (size >> 0)); + destination.write(bytes); + + headerBuffer.close(); + return size; + } +} diff --git a/tests/src/com/android/inputmethod/latin/makedict/BinaryDictIOUtils.java b/tests/src/com/android/inputmethod/latin/makedict/BinaryDictIOUtils.java new file mode 100644 index 000000000..42a50be66 --- /dev/null +++ b/tests/src/com/android/inputmethod/latin/makedict/BinaryDictIOUtils.java @@ -0,0 +1,306 @@ +/* + * Copyright (C) 2012 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.inputmethod.latin.makedict; + +import com.android.inputmethod.annotations.UsedForTesting; +import com.android.inputmethod.latin.Constants; +import com.android.inputmethod.latin.makedict.DictDecoder.DictionaryBufferFactory; + +import java.io.File; +import java.io.IOException; +import java.io.OutputStream; +import java.util.ArrayList; +import java.util.Map; +import java.util.Stack; + +public final class BinaryDictIOUtils { + private static final boolean DBG = false; + + private BinaryDictIOUtils() { + // This utility class is not publicly instantiable. + } + + /** + * Returns new dictionary decoder. + * + * @param dictFile the dictionary file. + * @param bufferType The type of buffer, as one of USE_* in DictDecoder. + * @return new dictionary decoder if the dictionary file exists, otherwise null. + */ + public static DictDecoder getDictDecoder(final File dictFile, final long offset, + final long length, final int bufferType) { + if (dictFile.isDirectory()) { + return new Ver4DictDecoder(dictFile, bufferType); + } else if (dictFile.isFile()) { + return new Ver2DictDecoder(dictFile, offset, length, bufferType); + } + return null; + } + + public static DictDecoder getDictDecoder(final File dictFile, final long offset, + final long length, final DictionaryBufferFactory factory) { + if (dictFile.isDirectory()) { + return new Ver4DictDecoder(dictFile, factory); + } else if (dictFile.isFile()) { + return new Ver2DictDecoder(dictFile, offset, length, factory); + } + return null; + } + + public static DictDecoder getDictDecoder(final File dictFile, final long offset, + final long length) { + return getDictDecoder(dictFile, offset, length, DictDecoder.USE_READONLY_BYTEBUFFER); + } + + private static final class Position { + public static final int NOT_READ_PTNODE_COUNT = -1; + + public int mAddress; + public int mNumOfPtNode; + public int mPosition; + public int mLength; + + public Position(int address, int length) { + mAddress = address; + mLength = length; + mNumOfPtNode = NOT_READ_PTNODE_COUNT; + } + } + + /** + * Retrieves all node arrays without recursive call. + */ + private static void readUnigramsAndBigramsBinaryInner(final DictDecoder dictDecoder, + final int bodyOffset, final Map<Integer, String> words, + final Map<Integer, Integer> frequencies, + final Map<Integer, ArrayList<PendingAttribute>> bigrams) { + int[] pushedChars = new int[FormatSpec.MAX_WORD_LENGTH + 1]; + + Stack<Position> stack = new Stack<Position>(); + int index = 0; + + Position initPos = new Position(bodyOffset, 0); + stack.push(initPos); + + while (!stack.empty()) { + Position p = stack.peek(); + + if (DBG) { + MakedictLog.d("read: address=" + p.mAddress + ", numOfPtNode=" + + p.mNumOfPtNode + ", position=" + p.mPosition + ", length=" + p.mLength); + } + + if (dictDecoder.getPosition() != p.mAddress) dictDecoder.setPosition(p.mAddress); + if (index != p.mLength) index = p.mLength; + + if (p.mNumOfPtNode == Position.NOT_READ_PTNODE_COUNT) { + p.mNumOfPtNode = dictDecoder.readPtNodeCount(); + p.mAddress = dictDecoder.getPosition(); + p.mPosition = 0; + } + if (p.mNumOfPtNode == 0) { + stack.pop(); + continue; + } + final PtNodeInfo ptNodeInfo = dictDecoder.readPtNode(p.mAddress); + for (int i = 0; i < ptNodeInfo.mCharacters.length; ++i) { + pushedChars[index++] = ptNodeInfo.mCharacters[i]; + } + p.mPosition++; + if (ptNodeInfo.isTerminal()) {// found word + words.put(ptNodeInfo.mOriginalAddress, new String(pushedChars, 0, index)); + frequencies.put( + ptNodeInfo.mOriginalAddress, ptNodeInfo.mProbabilityInfo.mProbability); + if (ptNodeInfo.mBigrams != null) { + bigrams.put(ptNodeInfo.mOriginalAddress, ptNodeInfo.mBigrams); + } + } + + if (p.mPosition == p.mNumOfPtNode) { + stack.pop(); + } else { + // The PtNode array has more PtNodes. + p.mAddress = dictDecoder.getPosition(); + } + + if (hasChildrenAddress(ptNodeInfo.mChildrenAddress)) { + final Position childrenPos = new Position(ptNodeInfo.mChildrenAddress, index); + stack.push(childrenPos); + } + } + } + + /** + * Reads unigrams and bigrams from the binary file. + * Doesn't store a full memory representation of the dictionary. + * + * @param dictDecoder the dict decoder. + * @param words the map to store the address as a key and the word as a value. + * @param frequencies the map to store the address as a key and the frequency as a value. + * @param bigrams the map to store the address as a key and the list of address as a value. + * @throws IOException if the file can't be read. + * @throws UnsupportedFormatException if the format of the file is not recognized. + */ + /* package */ static void readUnigramsAndBigramsBinary(final DictDecoder dictDecoder, + final Map<Integer, String> words, final Map<Integer, Integer> frequencies, + final Map<Integer, ArrayList<PendingAttribute>> bigrams) throws IOException, + UnsupportedFormatException { + // Read header + final DictionaryHeader header = dictDecoder.readHeader(); + readUnigramsAndBigramsBinaryInner(dictDecoder, header.mBodyOffset, words, + frequencies, bigrams); + } + + /** + * Gets the address of the last PtNode of the exact matching word in the dictionary. + * If no match is found, returns NOT_VALID_WORD. + * + * @param dictDecoder the dict decoder. + * @param word the word we search for. + * @return the address of the terminal node. + * @throws IOException if the file can't be read. + * @throws UnsupportedFormatException if the format of the file is not recognized. + */ + @UsedForTesting + /* package */ static int getTerminalPosition(final DictDecoder dictDecoder, + final String word) throws IOException, UnsupportedFormatException { + if (word == null) return FormatSpec.NOT_VALID_WORD; + dictDecoder.setPosition(0); + dictDecoder.readHeader(); + int wordPos = 0; + final int wordLen = word.codePointCount(0, word.length()); + for (int depth = 0; depth < Constants.DICTIONARY_MAX_WORD_LENGTH; ++depth) { + if (wordPos >= wordLen) return FormatSpec.NOT_VALID_WORD; + + do { + final int ptNodeCount = dictDecoder.readPtNodeCount(); + boolean foundNextPtNode = false; + for (int i = 0; i < ptNodeCount; ++i) { + final int ptNodePos = dictDecoder.getPosition(); + final PtNodeInfo currentInfo = dictDecoder.readPtNode(ptNodePos); + boolean same = true; + for (int p = 0, j = word.offsetByCodePoints(0, wordPos); + p < currentInfo.mCharacters.length; + ++p, j = word.offsetByCodePoints(j, 1)) { + if (wordPos + p >= wordLen + || word.codePointAt(j) != currentInfo.mCharacters[p]) { + same = false; + break; + } + } + + if (same) { + // found the PtNode matches the word. + if (wordPos + currentInfo.mCharacters.length == wordLen) { + if (!currentInfo.isTerminal()) { + return FormatSpec.NOT_VALID_WORD; + } else { + return ptNodePos; + } + } + wordPos += currentInfo.mCharacters.length; + if (currentInfo.mChildrenAddress == FormatSpec.NO_CHILDREN_ADDRESS) { + return FormatSpec.NOT_VALID_WORD; + } + foundNextPtNode = true; + dictDecoder.setPosition(currentInfo.mChildrenAddress); + break; + } + } + if (foundNextPtNode) break; + return FormatSpec.NOT_VALID_WORD; + } while(true); + } + return FormatSpec.NOT_VALID_WORD; + } + + /** + * Writes a PtNodeCount to the stream. + * + * @param destination the stream to write. + * @param ptNodeCount the count. + * @return the size written in bytes. + */ + @UsedForTesting + static int writePtNodeCount(final OutputStream destination, final int ptNodeCount) + throws IOException { + final int countSize = BinaryDictIOUtils.getPtNodeCountSize(ptNodeCount); + // the count must fit on one byte or two bytes. + // Please see comments in FormatSpec. + if (countSize != 1 && countSize != 2) { + throw new RuntimeException("Strange size from getPtNodeCountSize : " + countSize); + } + final int encodedPtNodeCount = (countSize == 2) ? + (ptNodeCount | FormatSpec.LARGE_PTNODE_ARRAY_SIZE_FIELD_SIZE_FLAG) : ptNodeCount; + BinaryDictEncoderUtils.writeUIntToStream(destination, encodedPtNodeCount, countSize); + return countSize; + } + + /** + * Helper method to hide the actual value of the no children address. + */ + public static boolean hasChildrenAddress(final int address) { + return FormatSpec.NO_CHILDREN_ADDRESS != address; + } + + /** + * Compute the binary size of the node count + * @param count the node count + * @return the size of the node count, either 1 or 2 bytes. + */ + public static int getPtNodeCountSize(final int count) { + if (FormatSpec.MAX_PTNODES_FOR_ONE_BYTE_PTNODE_COUNT >= count) { + return 1; + } else if (FormatSpec.MAX_PTNODES_IN_A_PT_NODE_ARRAY >= count) { + return 2; + } else { + throw new RuntimeException("Can't have more than " + + FormatSpec.MAX_PTNODES_IN_A_PT_NODE_ARRAY + " PtNode in a PtNodeArray (found " + + count + ")"); + } + } + + static int getChildrenAddressSize(final int optionFlags) { + switch (optionFlags & FormatSpec.MASK_CHILDREN_ADDRESS_TYPE) { + case FormatSpec.FLAG_CHILDREN_ADDRESS_TYPE_ONEBYTE: + return 1; + case FormatSpec.FLAG_CHILDREN_ADDRESS_TYPE_TWOBYTES: + return 2; + case FormatSpec.FLAG_CHILDREN_ADDRESS_TYPE_THREEBYTES: + return 3; + case FormatSpec.FLAG_CHILDREN_ADDRESS_TYPE_NOADDRESS: + default: + return 0; + } + } + + /** + * Calculate bigram frequency from compressed value + * + * @param unigramFrequency + * @param bigramFrequency compressed frequency + * @return approximate bigram frequency + */ + @UsedForTesting + public static int reconstructBigramFrequency(final int unigramFrequency, + final int bigramFrequency) { + final float stepSize = (FormatSpec.MAX_TERMINAL_FREQUENCY - unigramFrequency) + / (1.5f + FormatSpec.MAX_BIGRAM_FREQUENCY); + final float resultFreqFloat = unigramFrequency + stepSize * (bigramFrequency + 1.0f); + return (int)resultFreqFloat; + } +} diff --git a/tests/src/com/android/inputmethod/latin/makedict/DictDecoder.java b/tests/src/com/android/inputmethod/latin/makedict/DictDecoder.java new file mode 100644 index 000000000..a3b28a702 --- /dev/null +++ b/tests/src/com/android/inputmethod/latin/makedict/DictDecoder.java @@ -0,0 +1,222 @@ +/* + * Copyright (C) 2013 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.inputmethod.latin.makedict; + +import com.android.inputmethod.annotations.UsedForTesting; +import com.android.inputmethod.latin.makedict.BinaryDictDecoderUtils.DictBuffer; +import com.android.inputmethod.latin.utils.ByteArrayDictBuffer; + +import java.io.File; +import java.io.FileInputStream; +import java.io.FileNotFoundException; +import java.io.IOException; +import java.io.RandomAccessFile; +import java.nio.ByteBuffer; +import java.nio.channels.FileChannel; +import java.util.ArrayList; +import java.util.TreeMap; + +/** + * An interface of binary dictionary decoders. + */ +// TODO: Straighten out responsibility for the buffer's file pointer. +public interface DictDecoder { + + /** + * Reads and returns the file header. + */ + public DictionaryHeader readHeader() throws IOException, UnsupportedFormatException; + + /** + * Reads PtNode from ptNodePos. + * @param ptNodePos the position of PtNode. + * @return PtNodeInfo. + */ + public PtNodeInfo readPtNode(final int ptNodePos); + + /** + * Reads a buffer and returns the memory representation of the dictionary. + * + * This high-level method takes a buffer and reads its contents, populating a + * FusionDictionary structure. + * + * @param deleteDictIfBroken a flag indicating whether this method should remove the broken + * dictionary or not. + * @return the created dictionary. + */ + @UsedForTesting + public FusionDictionary readDictionaryBinary(final boolean deleteDictIfBroken) + throws FileNotFoundException, IOException, UnsupportedFormatException; + + /** + * Gets the address of the last PtNode of the exact matching word in the dictionary. + * If no match is found, returns NOT_VALID_WORD. + * + * @param word the word we search for. + * @return the address of the terminal node. + * @throws IOException if the file can't be read. + * @throws UnsupportedFormatException if the format of the file is not recognized. + */ + @UsedForTesting + public int getTerminalPosition(final String word) + throws IOException, UnsupportedFormatException; + + /** + * Reads unigrams and bigrams from the binary file. + * Doesn't store a full memory representation of the dictionary. + * + * @param words the map to store the address as a key and the word as a value. + * @param frequencies the map to store the address as a key and the frequency as a value. + * @param bigrams the map to store the address as a key and the list of address as a value. + * @throws IOException if the file can't be read. + * @throws UnsupportedFormatException if the format of the file is not recognized. + */ + @UsedForTesting + public void readUnigramsAndBigramsBinary(final TreeMap<Integer, String> words, + final TreeMap<Integer, Integer> frequencies, + final TreeMap<Integer, ArrayList<PendingAttribute>> bigrams) + throws IOException, UnsupportedFormatException; + + /** + * Sets the position of the buffer to the given value. + * + * @param newPos the new position + */ + public void setPosition(final int newPos); + + /** + * Gets the position of the buffer. + * + * @return the position + */ + public int getPosition(); + + /** + * Reads and returns the PtNode count out of a buffer and forwards the pointer. + */ + public int readPtNodeCount(); + + /** + * Opens the dictionary file and makes DictBuffer. + */ + @UsedForTesting + public void openDictBuffer() throws FileNotFoundException, IOException, + UnsupportedFormatException; + @UsedForTesting + public boolean isDictBufferOpen(); + + // Constants for DictionaryBufferFactory. + public static final int USE_READONLY_BYTEBUFFER = 0x01000000; + public static final int USE_BYTEARRAY = 0x02000000; + public static final int USE_WRITABLE_BYTEBUFFER = 0x03000000; + public static final int MASK_DICTBUFFER = 0x0F000000; + + public interface DictionaryBufferFactory { + public DictBuffer getDictionaryBuffer(final File file) + throws FileNotFoundException, IOException; + } + + /** + * Creates DictionaryBuffer using a ByteBuffer + * + * This class uses less memory than DictionaryBufferFromByteArrayFactory, + * but doesn't perform as fast. + * When operating on a big dictionary, this class is preferred. + */ + public static final class DictionaryBufferFromReadOnlyByteBufferFactory + implements DictionaryBufferFactory { + @Override + public DictBuffer getDictionaryBuffer(final File file) + throws FileNotFoundException, IOException { + FileInputStream inStream = null; + ByteBuffer buffer = null; + try { + inStream = new FileInputStream(file); + buffer = inStream.getChannel().map(FileChannel.MapMode.READ_ONLY, + 0, file.length()); + } finally { + if (inStream != null) { + inStream.close(); + } + } + if (buffer != null) { + return new BinaryDictDecoderUtils.ByteBufferDictBuffer(buffer); + } + return null; + } + } + + /** + * Creates DictionaryBuffer using a byte array + * + * This class performs faster than other classes, but consumes more memory. + * When operating on a small dictionary, this class is preferred. + */ + public static final class DictionaryBufferFromByteArrayFactory + implements DictionaryBufferFactory { + @Override + public DictBuffer getDictionaryBuffer(final File file) + throws FileNotFoundException, IOException { + FileInputStream inStream = null; + try { + inStream = new FileInputStream(file); + final byte[] array = new byte[(int) file.length()]; + inStream.read(array); + return new ByteArrayDictBuffer(array); + } finally { + if (inStream != null) { + inStream.close(); + } + } + } + } + + /** + * Creates DictionaryBuffer using a writable ByteBuffer and a RandomAccessFile. + * + * This class doesn't perform as fast as other classes, + * but this class is the only option available for destructive operations (insert or delete) + * on a dictionary. + */ + @UsedForTesting + public static final class DictionaryBufferFromWritableByteBufferFactory + implements DictionaryBufferFactory { + @Override + public DictBuffer getDictionaryBuffer(final File file) + throws FileNotFoundException, IOException { + RandomAccessFile raFile = null; + ByteBuffer buffer = null; + try { + raFile = new RandomAccessFile(file, "rw"); + buffer = raFile.getChannel().map(FileChannel.MapMode.READ_WRITE, 0, file.length()); + } finally { + if (raFile != null) { + raFile.close(); + } + } + if (buffer != null) { + return new BinaryDictDecoderUtils.ByteBufferDictBuffer(buffer); + } + return null; + } + } + + /** + * @return whether this decoder has a valid binary dictionary that it can decode. + */ + public boolean hasValidRawBinaryDictionary(); +} diff --git a/tests/src/com/android/inputmethod/latin/makedict/DictEncoder.java b/tests/src/com/android/inputmethod/latin/makedict/DictEncoder.java new file mode 100644 index 000000000..678c5ca6b --- /dev/null +++ b/tests/src/com/android/inputmethod/latin/makedict/DictEncoder.java @@ -0,0 +1,38 @@ +/* + * Copyright (C) 2013 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.inputmethod.latin.makedict; + +import com.android.inputmethod.annotations.UsedForTesting; +import com.android.inputmethod.latin.makedict.FormatSpec.FormatOptions; +import com.android.inputmethod.latin.makedict.FusionDictionary.PtNode; + +import java.io.IOException; + +/** + * An interface of binary dictionary encoder. + */ +public interface DictEncoder { + @UsedForTesting + public void writeDictionary(final FusionDictionary dict, final FormatOptions formatOptions) + throws IOException, UnsupportedFormatException; + + public void setPosition(final int position); + public int getPosition(); + public void writePtNodeCount(final int ptNodeCount); + public void writeForwardLinkAddress(final int forwardLinkAddress); + public void writePtNode(final PtNode ptNode, final FusionDictionary dict); +} diff --git a/tests/src/com/android/inputmethod/latin/makedict/FusionDictionary.java b/tests/src/com/android/inputmethod/latin/makedict/FusionDictionary.java new file mode 100644 index 000000000..f60b3af4f --- /dev/null +++ b/tests/src/com/android/inputmethod/latin/makedict/FusionDictionary.java @@ -0,0 +1,717 @@ +/* + * Copyright (C) 2011 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.inputmethod.latin.makedict; + +import com.android.inputmethod.annotations.UsedForTesting; +import com.android.inputmethod.latin.Constants; +import com.android.inputmethod.latin.makedict.FormatSpec.DictionaryOptions; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.Iterator; +import java.util.LinkedList; + +/** + * A dictionary that can fusion heads and tails of words for more compression. + */ +@UsedForTesting +public final class FusionDictionary implements Iterable<WordProperty> { + private static final boolean DBG = MakedictLog.DBG; + + private static int CHARACTER_NOT_FOUND_INDEX = -1; + + /** + * A node array of the dictionary, containing several PtNodes. + * + * A PtNodeArray is but an ordered array of PtNodes, which essentially contain all the + * real information. + * This class also contains fields to cache size and address, to help with binary + * generation. + */ + public static final class PtNodeArray { + ArrayList<PtNode> mData; + // To help with binary generation + int mCachedSize = Integer.MIN_VALUE; + // mCachedAddressBefore/AfterUpdate are helpers for binary dictionary generation. They + // always hold the same value except between dictionary address compression, during which + // the update process needs to know about both values at the same time. Updating will + // update the AfterUpdate value, and the code will move them to BeforeUpdate before + // the next update pass. + int mCachedAddressBeforeUpdate = Integer.MIN_VALUE; + int mCachedAddressAfterUpdate = Integer.MIN_VALUE; + int mCachedParentAddress = 0; + + public PtNodeArray() { + mData = new ArrayList<PtNode>(); + } + public PtNodeArray(ArrayList<PtNode> data) { + Collections.sort(data, PTNODE_COMPARATOR); + mData = data; + } + } + + /** + * PtNode is a group of characters, with probability information, shortcut targets, bigrams, + * and children (Pt means Patricia Trie). + * + * This is the central class of the in-memory representation. A PtNode is what can + * be seen as a traditional "trie node", except it can hold several characters at the + * same time. A PtNode essentially represents one or several characters in the middle + * of the trie tree; as such, it can be a terminal, and it can have children. + * In this in-memory representation, whether the PtNode is a terminal or not is represented + * by mProbabilityInfo. The PtNode is a terminal when the mProbabilityInfo is not null and the + * PtNode is not a terminal when the mProbabilityInfo is null. A terminal may have non-null + * shortcuts and/or bigrams, but a non-terminal may not. Moreover, children, if present, + * are non-null. + */ + public static final class PtNode { + private static final int NOT_A_TERMINAL = -1; + final int mChars[]; + ArrayList<WeightedString> mShortcutTargets; + ArrayList<WeightedString> mBigrams; + // null == mProbabilityInfo indicates this is not a terminal. + ProbabilityInfo mProbabilityInfo; + int mTerminalId; // NOT_A_TERMINAL == mTerminalId indicates this is not a terminal. + PtNodeArray mChildren; + boolean mIsNotAWord; // Only a shortcut + boolean mIsBlacklistEntry; + // mCachedSize and mCachedAddressBefore/AfterUpdate are helpers for binary dictionary + // generation. Before and After always hold the same value except during dictionary + // address compression, where the update process needs to know about both values at the + // same time. Updating will update the AfterUpdate value, and the code will move them + // to BeforeUpdate before the next update pass. + // The update process does not need two versions of mCachedSize. + int mCachedSize; // The size, in bytes, of this PtNode. + int mCachedAddressBeforeUpdate; // The address of this PtNode (before update) + int mCachedAddressAfterUpdate; // The address of this PtNode (after update) + + public PtNode(final int[] chars, final ArrayList<WeightedString> shortcutTargets, + final ArrayList<WeightedString> bigrams, final ProbabilityInfo probabilityInfo, + final boolean isNotAWord, final boolean isBlacklistEntry) { + mChars = chars; + mProbabilityInfo = probabilityInfo; + mTerminalId = probabilityInfo == null ? NOT_A_TERMINAL : probabilityInfo.mProbability; + mShortcutTargets = shortcutTargets; + mBigrams = bigrams; + mChildren = null; + mIsNotAWord = isNotAWord; + mIsBlacklistEntry = isBlacklistEntry; + } + + public PtNode(final int[] chars, final ArrayList<WeightedString> shortcutTargets, + final ArrayList<WeightedString> bigrams, final ProbabilityInfo probabilityInfo, + final boolean isNotAWord, final boolean isBlacklistEntry, + final PtNodeArray children) { + mChars = chars; + mProbabilityInfo = probabilityInfo; + mShortcutTargets = shortcutTargets; + mBigrams = bigrams; + mChildren = children; + mIsNotAWord = isNotAWord; + mIsBlacklistEntry = isBlacklistEntry; + } + + public void addChild(PtNode n) { + if (null == mChildren) { + mChildren = new PtNodeArray(); + } + mChildren.mData.add(n); + } + + public int getTerminalId() { + return mTerminalId; + } + + public boolean isTerminal() { + return mProbabilityInfo != null; + } + + public int getProbability() { + if (isTerminal()) { + return mProbabilityInfo.mProbability; + } else { + return NOT_A_TERMINAL; + } + } + + public boolean getIsNotAWord() { + return mIsNotAWord; + } + + public boolean getIsBlacklistEntry() { + return mIsBlacklistEntry; + } + + public ArrayList<WeightedString> getShortcutTargets() { + // We don't want write permission to escape outside the package, so we return a copy + if (null == mShortcutTargets) return null; + final ArrayList<WeightedString> copyOfShortcutTargets = + new ArrayList<WeightedString>(mShortcutTargets); + return copyOfShortcutTargets; + } + + public ArrayList<WeightedString> getBigrams() { + // We don't want write permission to escape outside the package, so we return a copy + if (null == mBigrams) return null; + final ArrayList<WeightedString> copyOfBigrams = new ArrayList<WeightedString>(mBigrams); + return copyOfBigrams; + } + + public boolean hasSeveralChars() { + assert(mChars.length > 0); + return 1 < mChars.length; + } + + /** + * Adds a word to the bigram list. Updates the probability information if the word already + * exists. + */ + public void addBigram(final String word, final ProbabilityInfo probabilityInfo) { + if (mBigrams == null) { + mBigrams = new ArrayList<WeightedString>(); + } + WeightedString bigram = getBigram(word); + if (bigram != null) { + bigram.mProbabilityInfo = probabilityInfo; + } else { + bigram = new WeightedString(word, probabilityInfo); + mBigrams.add(bigram); + } + } + + /** + * Gets the shortcut target for the given word. Returns null if the word is not in the + * shortcut list. + */ + public WeightedString getShortcut(final String word) { + // TODO: Don't do a linear search + if (mShortcutTargets != null) { + final int size = mShortcutTargets.size(); + for (int i = 0; i < size; ++i) { + WeightedString shortcut = mShortcutTargets.get(i); + if (shortcut.mWord.equals(word)) { + return shortcut; + } + } + } + return null; + } + + /** + * Gets the bigram for the given word. + * Returns null if the word is not in the bigrams list. + */ + public WeightedString getBigram(final String word) { + // TODO: Don't do a linear search + if (mBigrams != null) { + final int size = mBigrams.size(); + for (int i = 0; i < size; ++i) { + WeightedString bigram = mBigrams.get(i); + if (bigram.mWord.equals(word)) { + return bigram; + } + } + } + return null; + } + + /** + * Updates the PtNode with the given properties. Adds the shortcut and bigram lists to + * the existing ones if any. Note: unigram, bigram, and shortcut frequencies are only + * updated if they are higher than the existing ones. + */ + private void update(final ProbabilityInfo probabilityInfo, + final ArrayList<WeightedString> shortcutTargets, + final ArrayList<WeightedString> bigrams, + final boolean isNotAWord, final boolean isBlacklistEntry) { + mProbabilityInfo = ProbabilityInfo.max(mProbabilityInfo, probabilityInfo); + if (shortcutTargets != null) { + if (mShortcutTargets == null) { + mShortcutTargets = shortcutTargets; + } else { + final int size = shortcutTargets.size(); + for (int i = 0; i < size; ++i) { + final WeightedString shortcut = shortcutTargets.get(i); + final WeightedString existingShortcut = getShortcut(shortcut.mWord); + if (existingShortcut == null) { + mShortcutTargets.add(shortcut); + } else { + existingShortcut.mProbabilityInfo = ProbabilityInfo.max( + existingShortcut.mProbabilityInfo, shortcut.mProbabilityInfo); + } + } + } + } + if (bigrams != null) { + if (mBigrams == null) { + mBigrams = bigrams; + } else { + final int size = bigrams.size(); + for (int i = 0; i < size; ++i) { + final WeightedString bigram = bigrams.get(i); + final WeightedString existingBigram = getBigram(bigram.mWord); + if (existingBigram == null) { + mBigrams.add(bigram); + } else { + existingBigram.mProbabilityInfo = ProbabilityInfo.max( + existingBigram.mProbabilityInfo, bigram.mProbabilityInfo); + } + } + } + } + mIsNotAWord = isNotAWord; + mIsBlacklistEntry = isBlacklistEntry; + } + } + + public final DictionaryOptions mOptions; + public final PtNodeArray mRootNodeArray; + + public FusionDictionary(final PtNodeArray rootNodeArray, final DictionaryOptions options) { + mRootNodeArray = rootNodeArray; + mOptions = options; + } + + public void addOptionAttribute(final String key, final String value) { + mOptions.mAttributes.put(key, value); + } + + /** + * Helper method to convert a String to an int array. + */ + static int[] getCodePoints(final String word) { + // TODO: this is a copy-paste of the old contents of StringUtils.toCodePointArray, + // which is not visible from the makedict package. Factor this code. + final int length = word.length(); + if (length <= 0) return new int[] {}; + final char[] characters = word.toCharArray(); + final int[] codePoints = new int[Character.codePointCount(characters, 0, length)]; + int codePoint = Character.codePointAt(characters, 0); + int dsti = 0; + for (int srci = Character.charCount(codePoint); + srci < length; srci += Character.charCount(codePoint), ++dsti) { + codePoints[dsti] = codePoint; + codePoint = Character.codePointAt(characters, srci); + } + codePoints[dsti] = codePoint; + return codePoints; + } + + /** + * Helper method to add a word as a string. + * + * This method adds a word to the dictionary with the given frequency. Optional + * lists of bigrams and shortcuts can be passed here. For each word inside, + * they will be added to the dictionary as necessary. + * + * @param word the word to add. + * @param probabilityInfo probability information of the word. + * @param shortcutTargets a list of shortcut targets for this word, or null. + * @param isNotAWord true if this should not be considered a word (e.g. shortcut only) + */ + public void add(final String word, final ProbabilityInfo probabilityInfo, + final ArrayList<WeightedString> shortcutTargets, final boolean isNotAWord) { + add(getCodePoints(word), probabilityInfo, shortcutTargets, isNotAWord, + false /* isBlacklistEntry */); + } + + /** + * Helper method to add a blacklist entry as a string. + * + * @param word the word to add as a blacklist entry. + * @param shortcutTargets a list of shortcut targets for this word, or null. + * @param isNotAWord true if this is not a word for spellcheking purposes (shortcut only or so) + */ + public void addBlacklistEntry(final String word, + final ArrayList<WeightedString> shortcutTargets, final boolean isNotAWord) { + add(getCodePoints(word), new ProbabilityInfo(0), shortcutTargets, isNotAWord, + true /* isBlacklistEntry */); + } + + /** + * Sanity check for a PtNode array. + * + * This method checks that all PtNodes in a node array are ordered as expected. + * If they are, nothing happens. If they aren't, an exception is thrown. + */ + private void checkStack(PtNodeArray ptNodeArray) { + ArrayList<PtNode> stack = ptNodeArray.mData; + int lastValue = -1; + for (int i = 0; i < stack.size(); ++i) { + int currentValue = stack.get(i).mChars[0]; + if (currentValue <= lastValue) + throw new RuntimeException("Invalid stack"); + else + lastValue = currentValue; + } + } + + /** + * Helper method to add a new bigram to the dictionary. + * + * @param word0 the previous word of the context + * @param word1 the next word of the context + * @param probabilityInfo the bigram probability info + */ + public void setBigram(final String word0, final String word1, + final ProbabilityInfo probabilityInfo) { + PtNode ptNode0 = findWordInTree(mRootNodeArray, word0); + if (ptNode0 != null) { + final PtNode ptNode1 = findWordInTree(mRootNodeArray, word1); + if (ptNode1 == null) { + add(getCodePoints(word1), new ProbabilityInfo(0), null, false /* isNotAWord */, + false /* isBlacklistEntry */); + // The PtNode for the first word may have moved by the above insertion, + // if word1 and word2 share a common stem that happens not to have been + // a cutting point until now. In this case, we need to refresh ptNode. + ptNode0 = findWordInTree(mRootNodeArray, word0); + } + ptNode0.addBigram(word1, probabilityInfo); + } else { + throw new RuntimeException("First word of bigram not found " + word0); + } + } + + /** + * Add a word to this dictionary. + * + * The shortcuts, if any, have to be in the dictionary already. If they aren't, + * an exception is thrown. + * + * @param word the word, as an int array. + * @param probabilityInfo the probability information of the word. + * @param shortcutTargets an optional list of shortcut targets for this word (null if none). + * @param isNotAWord true if this is not a word for spellcheking purposes (shortcut only or so) + * @param isBlacklistEntry true if this is a blacklisted word, false otherwise + */ + private void add(final int[] word, final ProbabilityInfo probabilityInfo, + final ArrayList<WeightedString> shortcutTargets, + final boolean isNotAWord, final boolean isBlacklistEntry) { + assert(probabilityInfo.mProbability <= FormatSpec.MAX_TERMINAL_FREQUENCY); + if (word.length >= Constants.DICTIONARY_MAX_WORD_LENGTH) { + MakedictLog.w("Ignoring a word that is too long: word.length = " + word.length); + return; + } + + PtNodeArray currentNodeArray = mRootNodeArray; + int charIndex = 0; + + PtNode currentPtNode = null; + int differentCharIndex = 0; // Set by the loop to the index of the char that differs + int nodeIndex = findIndexOfChar(mRootNodeArray, word[charIndex]); + while (CHARACTER_NOT_FOUND_INDEX != nodeIndex) { + currentPtNode = currentNodeArray.mData.get(nodeIndex); + differentCharIndex = compareCharArrays(currentPtNode.mChars, word, charIndex); + if (ARRAYS_ARE_EQUAL != differentCharIndex + && differentCharIndex < currentPtNode.mChars.length) break; + if (null == currentPtNode.mChildren) break; + charIndex += currentPtNode.mChars.length; + if (charIndex >= word.length) break; + currentNodeArray = currentPtNode.mChildren; + nodeIndex = findIndexOfChar(currentNodeArray, word[charIndex]); + } + + if (CHARACTER_NOT_FOUND_INDEX == nodeIndex) { + // No node at this point to accept the word. Create one. + final int insertionIndex = findInsertionIndex(currentNodeArray, word[charIndex]); + final PtNode newPtNode = new PtNode(Arrays.copyOfRange(word, charIndex, word.length), + shortcutTargets, null /* bigrams */, probabilityInfo, isNotAWord, + isBlacklistEntry); + currentNodeArray.mData.add(insertionIndex, newPtNode); + if (DBG) checkStack(currentNodeArray); + } else { + // There is a word with a common prefix. + if (differentCharIndex == currentPtNode.mChars.length) { + if (charIndex + differentCharIndex >= word.length) { + // The new word is a prefix of an existing word, but the node on which it + // should end already exists as is. Since the old PtNode was not a terminal, + // make it one by filling in its frequency and other attributes + currentPtNode.update(probabilityInfo, shortcutTargets, null, isNotAWord, + isBlacklistEntry); + } else { + // The new word matches the full old word and extends past it. + // We only have to create a new node and add it to the end of this. + final PtNode newNode = new PtNode( + Arrays.copyOfRange(word, charIndex + differentCharIndex, word.length), + shortcutTargets, null /* bigrams */, probabilityInfo, + isNotAWord, isBlacklistEntry); + currentPtNode.mChildren = new PtNodeArray(); + currentPtNode.mChildren.mData.add(newNode); + } + } else { + if (0 == differentCharIndex) { + // Exact same word. Update the frequency if higher. This will also add the + // new shortcuts to the existing shortcut list if it already exists. + currentPtNode.update(probabilityInfo, shortcutTargets, null, + currentPtNode.mIsNotAWord && isNotAWord, + currentPtNode.mIsBlacklistEntry || isBlacklistEntry); + } else { + // Partial prefix match only. We have to replace the current node with a node + // containing the current prefix and create two new ones for the tails. + PtNodeArray newChildren = new PtNodeArray(); + final PtNode newOldWord = new PtNode( + Arrays.copyOfRange(currentPtNode.mChars, differentCharIndex, + currentPtNode.mChars.length), currentPtNode.mShortcutTargets, + currentPtNode.mBigrams, currentPtNode.mProbabilityInfo, + currentPtNode.mIsNotAWord, currentPtNode.mIsBlacklistEntry, + currentPtNode.mChildren); + newChildren.mData.add(newOldWord); + + final PtNode newParent; + if (charIndex + differentCharIndex >= word.length) { + newParent = new PtNode( + Arrays.copyOfRange(currentPtNode.mChars, 0, differentCharIndex), + shortcutTargets, null /* bigrams */, probabilityInfo, + isNotAWord, isBlacklistEntry, newChildren); + } else { + newParent = new PtNode( + Arrays.copyOfRange(currentPtNode.mChars, 0, differentCharIndex), + null /* shortcutTargets */, null /* bigrams */, + null /* probabilityInfo */, false /* isNotAWord */, + false /* isBlacklistEntry */, newChildren); + final PtNode newWord = new PtNode(Arrays.copyOfRange(word, + charIndex + differentCharIndex, word.length), + shortcutTargets, null /* bigrams */, probabilityInfo, + isNotAWord, isBlacklistEntry); + final int addIndex = word[charIndex + differentCharIndex] + > currentPtNode.mChars[differentCharIndex] ? 1 : 0; + newChildren.mData.add(addIndex, newWord); + } + currentNodeArray.mData.set(nodeIndex, newParent); + } + if (DBG) checkStack(currentNodeArray); + } + } + } + + private static int ARRAYS_ARE_EQUAL = 0; + + /** + * Custom comparison of two int arrays taken to contain character codes. + * + * This method compares the two arrays passed as an argument in a lexicographic way, + * with an offset in the dst string. + * This method does NOT test for the first character. It is taken to be equal. + * I repeat: this method starts the comparison at 1 <> dstOffset + 1. + * The index where the strings differ is returned. ARRAYS_ARE_EQUAL = 0 is returned if the + * strings are equal. This works BECAUSE we don't look at the first character. + * + * @param src the left-hand side string of the comparison. + * @param dst the right-hand side string of the comparison. + * @param dstOffset the offset in the right-hand side string. + * @return the index at which the strings differ, or ARRAYS_ARE_EQUAL = 0 if they don't. + */ + private static int compareCharArrays(final int[] src, final int[] dst, int dstOffset) { + // We do NOT test the first char, because we come from a method that already + // tested it. + for (int i = 1; i < src.length; ++i) { + if (dstOffset + i >= dst.length) return i; + if (src[i] != dst[dstOffset + i]) return i; + } + if (dst.length > src.length) return src.length; + return ARRAYS_ARE_EQUAL; + } + + /** + * Helper class that compares and sorts two PtNodes according to their + * first element only. I repeat: ONLY the first element is considered, the rest + * is ignored. + * This comparator imposes orderings that are inconsistent with equals. + */ + static private final class PtNodeComparator implements java.util.Comparator<PtNode> { + @Override + public int compare(PtNode p1, PtNode p2) { + if (p1.mChars[0] == p2.mChars[0]) return 0; + return p1.mChars[0] < p2.mChars[0] ? -1 : 1; + } + } + final static private PtNodeComparator PTNODE_COMPARATOR = new PtNodeComparator(); + + /** + * Finds the insertion index of a character within a node array. + */ + private static int findInsertionIndex(final PtNodeArray nodeArray, int character) { + final ArrayList<PtNode> data = nodeArray.mData; + final PtNode reference = new PtNode(new int[] { character }, + null /* shortcutTargets */, null /* bigrams */, null /* probabilityInfo */, + false /* isNotAWord */, false /* isBlacklistEntry */); + int result = Collections.binarySearch(data, reference, PTNODE_COMPARATOR); + return result >= 0 ? result : -result - 1; + } + + /** + * Find the index of a char in a node array, if it exists. + * + * @param nodeArray the node array to search in. + * @param character the character to search for. + * @return the position of the character if it's there, or CHARACTER_NOT_FOUND_INDEX = -1 else. + */ + private static int findIndexOfChar(final PtNodeArray nodeArray, int character) { + final int insertionIndex = findInsertionIndex(nodeArray, character); + if (nodeArray.mData.size() <= insertionIndex) return CHARACTER_NOT_FOUND_INDEX; + return character == nodeArray.mData.get(insertionIndex).mChars[0] ? insertionIndex + : CHARACTER_NOT_FOUND_INDEX; + } + + /** + * Helper method to find a word in a given branch. + */ + @SuppressWarnings("unused") + public static PtNode findWordInTree(PtNodeArray nodeArray, final String string) { + int index = 0; + final StringBuilder checker = DBG ? new StringBuilder() : null; + final int[] codePoints = getCodePoints(string); + + PtNode currentPtNode; + do { + int indexOfGroup = findIndexOfChar(nodeArray, codePoints[index]); + if (CHARACTER_NOT_FOUND_INDEX == indexOfGroup) return null; + currentPtNode = nodeArray.mData.get(indexOfGroup); + + if (codePoints.length - index < currentPtNode.mChars.length) return null; + int newIndex = index; + while (newIndex < codePoints.length && newIndex - index < currentPtNode.mChars.length) { + if (currentPtNode.mChars[newIndex - index] != codePoints[newIndex]) return null; + newIndex++; + } + index = newIndex; + + if (DBG) { + checker.append(new String(currentPtNode.mChars, 0, currentPtNode.mChars.length)); + } + if (index < codePoints.length) { + nodeArray = currentPtNode.mChildren; + } + } while (null != nodeArray && index < codePoints.length); + + if (index < codePoints.length) return null; + if (!currentPtNode.isTerminal()) return null; + if (DBG && !string.equals(checker.toString())) return null; + return currentPtNode; + } + + /** + * Helper method to find out whether a word is in the dict or not. + */ + public boolean hasWord(final String s) { + if (null == s || "".equals(s)) { + throw new RuntimeException("Can't search for a null or empty string"); + } + return null != findWordInTree(mRootNodeArray, s); + } + + /** + * Recursively count the number of PtNodes in a given branch of the trie. + * + * @param nodeArray the parent node. + * @return the number of PtNodes in all the branch under this node. + */ + public static int countPtNodes(final PtNodeArray nodeArray) { + final int nodeSize = nodeArray.mData.size(); + int size = nodeSize; + for (int i = nodeSize - 1; i >= 0; --i) { + PtNode ptNode = nodeArray.mData.get(i); + if (null != ptNode.mChildren) + size += countPtNodes(ptNode.mChildren); + } + return size; + } + + /** + * Iterator to walk through a dictionary. + * + * This is purely for convenience. + */ + public static final class DictionaryIterator implements Iterator<WordProperty> { + private static final class Position { + public Iterator<PtNode> pos; + public int length; + public Position(ArrayList<PtNode> ptNodes) { + pos = ptNodes.iterator(); + length = 0; + } + } + final StringBuilder mCurrentString; + final LinkedList<Position> mPositions; + + public DictionaryIterator(ArrayList<PtNode> ptRoot) { + mCurrentString = new StringBuilder(); + mPositions = new LinkedList<Position>(); + final Position rootPos = new Position(ptRoot); + mPositions.add(rootPos); + } + + @Override + public boolean hasNext() { + for (Position p : mPositions) { + if (p.pos.hasNext()) { + return true; + } + } + return false; + } + + @Override + public WordProperty next() { + Position currentPos = mPositions.getLast(); + mCurrentString.setLength(currentPos.length); + + do { + if (currentPos.pos.hasNext()) { + final PtNode currentPtNode = currentPos.pos.next(); + currentPos.length = mCurrentString.length(); + for (int i : currentPtNode.mChars) { + mCurrentString.append(Character.toChars(i)); + } + if (null != currentPtNode.mChildren) { + currentPos = new Position(currentPtNode.mChildren.mData); + currentPos.length = mCurrentString.length(); + mPositions.addLast(currentPos); + } + if (currentPtNode.isTerminal()) { + return new WordProperty(mCurrentString.toString(), + currentPtNode.mProbabilityInfo, + currentPtNode.mShortcutTargets, currentPtNode.mBigrams, + currentPtNode.mIsNotAWord, currentPtNode.mIsBlacklistEntry); + } + } else { + mPositions.removeLast(); + currentPos = mPositions.getLast(); + mCurrentString.setLength(mPositions.getLast().length); + } + } while (true); + } + + @Override + public void remove() { + throw new UnsupportedOperationException("Unsupported yet"); + } + + } + + /** + * Method to return an iterator. + * + * This method enables Java's enhanced for loop. With this you can have a FusionDictionary x + * and say : for (Word w : x) {} + */ + @Override + public Iterator<WordProperty> iterator() { + return new DictionaryIterator(mRootNodeArray.mData); + } +} diff --git a/tests/src/com/android/inputmethod/latin/makedict/MakedictLog.java b/tests/src/com/android/inputmethod/latin/makedict/MakedictLog.java new file mode 100644 index 000000000..7eccff2b4 --- /dev/null +++ b/tests/src/com/android/inputmethod/latin/makedict/MakedictLog.java @@ -0,0 +1,44 @@ +/* + * Copyright (C) 2012 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); you may not + * use this file except in compliance with the License. You may obtain a copy of + * the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the + * License for the specific language governing permissions and limitations under + * the License. + */ + +package com.android.inputmethod.latin.makedict; + +/** + * Wrapper to redirect log events to the right output medium. + */ +public class MakedictLog { + public static final boolean DBG = true; + + private static void print(String message) { + System.out.println(message); + } + + public static void d(String message) { + print(message); + } + + public static void i(String message) { + print(message); + } + + public static void w(String message) { + print(message); + } + + public static void e(String message) { + print(message); + } +} diff --git a/tests/src/com/android/inputmethod/latin/makedict/PendingAttribute.java b/tests/src/com/android/inputmethod/latin/makedict/PendingAttribute.java new file mode 100644 index 000000000..70e24cc98 --- /dev/null +++ b/tests/src/com/android/inputmethod/latin/makedict/PendingAttribute.java @@ -0,0 +1,32 @@ +/* + * Copyright (C) 2011 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.inputmethod.latin.makedict; + +/** + * A not-yet-resolved attribute. + * + * An attribute is either a bigram or a shortcut. + * All instances of this class are always immutable. + */ +public final class PendingAttribute { + public final int mFrequency; + public final int mAddress; + public PendingAttribute(final int frequency, final int address) { + mFrequency = frequency; + mAddress = address; + } +} diff --git a/tests/src/com/android/inputmethod/latin/makedict/PtNodeInfo.java b/tests/src/com/android/inputmethod/latin/makedict/PtNodeInfo.java new file mode 100644 index 000000000..862e8c101 --- /dev/null +++ b/tests/src/com/android/inputmethod/latin/makedict/PtNodeInfo.java @@ -0,0 +1,51 @@ +/* + * Copyright (C) 2011 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.inputmethod.latin.makedict; + +import java.util.ArrayList; + +/** + * Raw PtNode info straight out of a file. This will contain numbers for addresses. + */ +public final class PtNodeInfo { + public final int mOriginalAddress; + public final int mEndAddress; + public final int mFlags; + public final int[] mCharacters; + public final ProbabilityInfo mProbabilityInfo; + public final int mChildrenAddress; + public final ArrayList<WeightedString> mShortcutTargets; + public final ArrayList<PendingAttribute> mBigrams; + + public PtNodeInfo(final int originalAddress, final int endAddress, final int flags, + final int[] characters, final ProbabilityInfo probabilityInfo, + final int childrenAddress, final ArrayList<WeightedString> shortcutTargets, + final ArrayList<PendingAttribute> bigrams) { + mOriginalAddress = originalAddress; + mEndAddress = endAddress; + mFlags = flags; + mCharacters = characters; + mProbabilityInfo = probabilityInfo; + mChildrenAddress = childrenAddress; + mShortcutTargets = shortcutTargets; + mBigrams = bigrams; + } + + public boolean isTerminal() { + return mProbabilityInfo != null; + } +} diff --git a/tests/src/com/android/inputmethod/latin/makedict/Ver2DictDecoder.java b/tests/src/com/android/inputmethod/latin/makedict/Ver2DictDecoder.java new file mode 100644 index 000000000..7091c119e --- /dev/null +++ b/tests/src/com/android/inputmethod/latin/makedict/Ver2DictDecoder.java @@ -0,0 +1,324 @@ +/* + * Copyright (C) 2013 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.inputmethod.latin.makedict; + +import com.android.inputmethod.annotations.UsedForTesting; +import com.android.inputmethod.latin.BinaryDictionary; +import com.android.inputmethod.latin.makedict.BinaryDictDecoderUtils.CharEncoding; +import com.android.inputmethod.latin.makedict.BinaryDictDecoderUtils.DictBuffer; +import com.android.inputmethod.latin.utils.CollectionUtils; + +import java.io.File; +import java.io.FileNotFoundException; +import java.io.IOException; +import java.util.ArrayList; +import java.util.Arrays; + +/** + * An implementation of DictDecoder for version 2 binary dictionary. + */ +// TODO: Separate logics that are used only for testing. +@UsedForTesting +public class Ver2DictDecoder extends AbstractDictDecoder { + private static final String TAG = Ver2DictDecoder.class.getSimpleName(); + + /** + * A utility class for reading a PtNode. + */ + protected static class PtNodeReader { + private static ProbabilityInfo readProbabilityInfo(final DictBuffer dictBuffer) { + // Ver2 dicts don't contain historical information. + return new ProbabilityInfo(dictBuffer.readUnsignedByte()); + } + + protected static int readPtNodeOptionFlags(final DictBuffer dictBuffer) { + return dictBuffer.readUnsignedByte(); + } + + protected static int readChildrenAddress(final DictBuffer dictBuffer, + final int ptNodeFlags) { + switch (ptNodeFlags & FormatSpec.MASK_CHILDREN_ADDRESS_TYPE) { + case FormatSpec.FLAG_CHILDREN_ADDRESS_TYPE_ONEBYTE: + return dictBuffer.readUnsignedByte(); + case FormatSpec.FLAG_CHILDREN_ADDRESS_TYPE_TWOBYTES: + return dictBuffer.readUnsignedShort(); + case FormatSpec.FLAG_CHILDREN_ADDRESS_TYPE_THREEBYTES: + return dictBuffer.readUnsignedInt24(); + case FormatSpec.FLAG_CHILDREN_ADDRESS_TYPE_NOADDRESS: + default: + return FormatSpec.NO_CHILDREN_ADDRESS; + } + } + + // Reads shortcuts and returns the read length. + protected static int readShortcut(final DictBuffer dictBuffer, + final ArrayList<WeightedString> shortcutTargets) { + final int pointerBefore = dictBuffer.position(); + dictBuffer.readUnsignedShort(); // skip the size + while (true) { + final int targetFlags = dictBuffer.readUnsignedByte(); + final String word = CharEncoding.readString(dictBuffer); + shortcutTargets.add(new WeightedString(word, + targetFlags & FormatSpec.FLAG_BIGRAM_SHORTCUT_ATTR_FREQUENCY)); + if (0 == (targetFlags & FormatSpec.FLAG_BIGRAM_SHORTCUT_ATTR_HAS_NEXT)) break; + } + return dictBuffer.position() - pointerBefore; + } + + protected static int readBigramAddresses(final DictBuffer dictBuffer, + final ArrayList<PendingAttribute> bigrams, final int baseAddress) { + int readLength = 0; + int bigramCount = 0; + while (bigramCount++ < FormatSpec.MAX_BIGRAMS_IN_A_PTNODE) { + final int bigramFlags = dictBuffer.readUnsignedByte(); + ++readLength; + final int sign = 0 == (bigramFlags & FormatSpec.FLAG_BIGRAM_ATTR_OFFSET_NEGATIVE) + ? 1 : -1; + int bigramAddress = baseAddress + readLength; + switch (bigramFlags & FormatSpec.MASK_BIGRAM_ATTR_ADDRESS_TYPE) { + case FormatSpec.FLAG_BIGRAM_ATTR_ADDRESS_TYPE_ONEBYTE: + bigramAddress += sign * dictBuffer.readUnsignedByte(); + readLength += 1; + break; + case FormatSpec.FLAG_BIGRAM_ATTR_ADDRESS_TYPE_TWOBYTES: + bigramAddress += sign * dictBuffer.readUnsignedShort(); + readLength += 2; + break; + case FormatSpec.FLAG_BIGRAM_ATTR_ADDRESS_TYPE_THREEBYTES: + bigramAddress += sign * dictBuffer.readUnsignedInt24(); + readLength += 3; + break; + default: + throw new RuntimeException("Has bigrams with no address"); + } + bigrams.add(new PendingAttribute( + bigramFlags & FormatSpec.FLAG_BIGRAM_SHORTCUT_ATTR_FREQUENCY, + bigramAddress)); + if (0 == (bigramFlags & FormatSpec.FLAG_BIGRAM_SHORTCUT_ATTR_HAS_NEXT)) break; + } + return readLength; + } + } + + protected final File mDictionaryBinaryFile; + protected final long mOffset; + protected final long mLength; + // TODO: Remove mBufferFactory and mDictBuffer from this class members because they are now + // used only for testing. + private final DictionaryBufferFactory mBufferFactory; + protected DictBuffer mDictBuffer; + + @UsedForTesting + /* package */ Ver2DictDecoder(final File file, final long offset, final long length, + final int factoryFlag) { + mDictionaryBinaryFile = file; + mOffset = offset; + mLength = length; + mDictBuffer = null; + if ((factoryFlag & MASK_DICTBUFFER) == USE_READONLY_BYTEBUFFER) { + mBufferFactory = new DictionaryBufferFromReadOnlyByteBufferFactory(); + } else if ((factoryFlag & MASK_DICTBUFFER) == USE_BYTEARRAY) { + mBufferFactory = new DictionaryBufferFromByteArrayFactory(); + } else if ((factoryFlag & MASK_DICTBUFFER) == USE_WRITABLE_BYTEBUFFER) { + mBufferFactory = new DictionaryBufferFromWritableByteBufferFactory(); + } else { + mBufferFactory = new DictionaryBufferFromReadOnlyByteBufferFactory(); + } + } + + /* package */ Ver2DictDecoder(final File file, final long offset, final long length, + final DictionaryBufferFactory factory) { + mDictionaryBinaryFile = file; + mOffset = offset; + mLength = length; + mBufferFactory = factory; + } + + @Override + public void openDictBuffer() throws FileNotFoundException, IOException { + mDictBuffer = mBufferFactory.getDictionaryBuffer(mDictionaryBinaryFile); + } + + @Override + public boolean isDictBufferOpen() { + return mDictBuffer != null; + } + + /* package */ DictBuffer getDictBuffer() { + return mDictBuffer; + } + + @UsedForTesting + /* package */ DictBuffer openAndGetDictBuffer() throws FileNotFoundException, IOException { + openDictBuffer(); + return getDictBuffer(); + } + + @Override + public DictionaryHeader readHeader() throws IOException, UnsupportedFormatException { + // dictType is not being used in dicttool. Passing an empty string. + final BinaryDictionary binaryDictionary = new BinaryDictionary( + mDictionaryBinaryFile.getAbsolutePath(), mOffset, mLength, + true /* useFullEditDistance */, null /* locale */, "" /* dictType */, + false /* isUpdatable */); + final DictionaryHeader header = binaryDictionary.getHeader(); + binaryDictionary.close(); + if (header == null) { + throw new IOException("Cannot read the dictionary header."); + } + if (header.mFormatOptions.mVersion != FormatSpec.VERSION2) { + throw new UnsupportedFormatException("File header has a wrong version : " + + header.mFormatOptions.mVersion); + } + if (!isDictBufferOpen()) { + openDictBuffer(); + } + // Advance buffer reading position to the head of dictionary body. + setPosition(header.mBodyOffset); + return header; + } + + // TODO: Make this buffer multi thread safe. + private final int[] mCharacterBuffer = new int[FormatSpec.MAX_WORD_LENGTH]; + @Override + public PtNodeInfo readPtNode(final int ptNodePos) { + int addressPointer = ptNodePos; + final int flags = PtNodeReader.readPtNodeOptionFlags(mDictBuffer); + addressPointer += FormatSpec.PTNODE_FLAGS_SIZE; + final int characters[]; + if (0 != (flags & FormatSpec.FLAG_HAS_MULTIPLE_CHARS)) { + int index = 0; + int character = CharEncoding.readChar(mDictBuffer); + addressPointer += CharEncoding.getCharSize(character); + while (FormatSpec.INVALID_CHARACTER != character) { + // FusionDictionary is making sure that the length of the word is smaller than + // MAX_WORD_LENGTH. + // So we'll never write past the end of mCharacterBuffer. + mCharacterBuffer[index++] = character; + character = CharEncoding.readChar(mDictBuffer); + addressPointer += CharEncoding.getCharSize(character); + } + characters = Arrays.copyOfRange(mCharacterBuffer, 0, index); + } else { + final int character = CharEncoding.readChar(mDictBuffer); + addressPointer += CharEncoding.getCharSize(character); + characters = new int[] { character }; + } + final ProbabilityInfo probabilityInfo; + if (0 != (FormatSpec.FLAG_IS_TERMINAL & flags)) { + probabilityInfo = PtNodeReader.readProbabilityInfo(mDictBuffer); + addressPointer += FormatSpec.PTNODE_FREQUENCY_SIZE; + } else { + probabilityInfo = null; + } + int childrenAddress = PtNodeReader.readChildrenAddress(mDictBuffer, flags); + if (childrenAddress != FormatSpec.NO_CHILDREN_ADDRESS) { + childrenAddress += addressPointer; + } + addressPointer += BinaryDictIOUtils.getChildrenAddressSize(flags); + final ArrayList<WeightedString> shortcutTargets; + if (0 != (flags & FormatSpec.FLAG_HAS_SHORTCUT_TARGETS)) { + // readShortcut will add shortcuts to shortcutTargets. + shortcutTargets = new ArrayList<WeightedString>(); + addressPointer += PtNodeReader.readShortcut(mDictBuffer, shortcutTargets); + } else { + shortcutTargets = null; + } + + final ArrayList<PendingAttribute> bigrams; + if (0 != (flags & FormatSpec.FLAG_HAS_BIGRAMS)) { + bigrams = new ArrayList<PendingAttribute>(); + addressPointer += PtNodeReader.readBigramAddresses(mDictBuffer, bigrams, + addressPointer); + if (bigrams.size() >= FormatSpec.MAX_BIGRAMS_IN_A_PTNODE) { + throw new RuntimeException("Too many bigrams in a PtNode (" + bigrams.size() + + " but max is " + FormatSpec.MAX_BIGRAMS_IN_A_PTNODE + ")"); + } + } else { + bigrams = null; + } + return new PtNodeInfo(ptNodePos, addressPointer, flags, characters, probabilityInfo, + childrenAddress, shortcutTargets, bigrams); + } + + @Override + public FusionDictionary readDictionaryBinary(final boolean deleteDictIfBroken) + throws FileNotFoundException, IOException, UnsupportedFormatException { + // dictType is not being used in dicttool. Passing an empty string. + final BinaryDictionary binaryDictionary = new BinaryDictionary( + mDictionaryBinaryFile.getAbsolutePath(), 0 /* offset */, + mDictionaryBinaryFile.length() /* length */, true /* useFullEditDistance */, + null /* locale */, "" /* dictType */, false /* isUpdatable */); + final DictionaryHeader header = readHeader(); + final FusionDictionary fusionDict = + new FusionDictionary(new FusionDictionary.PtNodeArray(), header.mDictionaryOptions); + int token = 0; + final ArrayList<WordProperty> wordProperties = CollectionUtils.newArrayList(); + do { + final BinaryDictionary.GetNextWordPropertyResult result = + binaryDictionary.getNextWordProperty(token); + final WordProperty wordProperty = result.mWordProperty; + if (wordProperty == null) { + binaryDictionary.close(); + if (deleteDictIfBroken) { + mDictionaryBinaryFile.delete(); + } + return null; + } + wordProperties.add(wordProperty); + token = result.mNextToken; + } while (token != 0); + + // Insert unigrams into the fusion dictionary. + for (final WordProperty wordProperty : wordProperties) { + if (wordProperty.mIsBlacklistEntry) { + fusionDict.addBlacklistEntry(wordProperty.mWord, wordProperty.mShortcutTargets, + wordProperty.mIsNotAWord); + } else { + fusionDict.add(wordProperty.mWord, wordProperty.mProbabilityInfo, + wordProperty.mShortcutTargets, wordProperty.mIsNotAWord); + } + } + // Insert bigrams into the fusion dictionary. + for (final WordProperty wordProperty : wordProperties) { + if (wordProperty.mBigrams == null) { + continue; + } + final String word0 = wordProperty.mWord; + for (final WeightedString bigram : wordProperty.mBigrams) { + fusionDict.setBigram(word0, bigram.mWord, bigram.mProbabilityInfo); + } + } + binaryDictionary.close(); + return fusionDict; + } + + @Override + public void setPosition(int newPos) { + mDictBuffer.position(newPos); + } + + @Override + public int getPosition() { + return mDictBuffer.position(); + } + + @Override + public int readPtNodeCount() { + return BinaryDictDecoderUtils.readPtNodeCount(mDictBuffer); + } +} diff --git a/tests/src/com/android/inputmethod/latin/makedict/Ver2DictEncoder.java b/tests/src/com/android/inputmethod/latin/makedict/Ver2DictEncoder.java new file mode 100644 index 000000000..a286190cb --- /dev/null +++ b/tests/src/com/android/inputmethod/latin/makedict/Ver2DictEncoder.java @@ -0,0 +1,240 @@ +/* + * Copyright (C) 2013 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.inputmethod.latin.makedict; + +import com.android.inputmethod.annotations.UsedForTesting; +import com.android.inputmethod.latin.makedict.BinaryDictDecoderUtils.CharEncoding; +import com.android.inputmethod.latin.makedict.FormatSpec.FormatOptions; +import com.android.inputmethod.latin.makedict.FusionDictionary.PtNode; +import com.android.inputmethod.latin.makedict.FusionDictionary.PtNodeArray; + +import java.io.File; +import java.io.FileNotFoundException; +import java.io.FileOutputStream; +import java.io.IOException; +import java.io.OutputStream; +import java.util.ArrayList; +import java.util.Iterator; + +/** + * An implementation of DictEncoder for version 2 binary dictionary. + */ +@UsedForTesting +public class Ver2DictEncoder implements DictEncoder { + + private final File mDictFile; + private OutputStream mOutStream; + private byte[] mBuffer; + private int mPosition; + + @UsedForTesting + public Ver2DictEncoder(final File dictFile) { + mDictFile = dictFile; + mOutStream = null; + mBuffer = null; + } + + // This constructor is used only by BinaryDictOffdeviceUtilsTests. + // If you want to use this in the production code, you should consider keeping consistency of + // the interface of Ver3DictDecoder by using factory. + @UsedForTesting + public Ver2DictEncoder(final OutputStream outStream) { + mDictFile = null; + mOutStream = outStream; + } + + private void openStream() throws FileNotFoundException { + mOutStream = new FileOutputStream(mDictFile); + } + + private void close() throws IOException { + if (mOutStream != null) { + mOutStream.close(); + mOutStream = null; + } + } + + @Override + public void writeDictionary(final FusionDictionary dict, final FormatOptions formatOptions) + throws IOException, UnsupportedFormatException { + if (formatOptions.mVersion > FormatSpec.VERSION2) { + throw new UnsupportedFormatException( + "The given format options has wrong version number : " + + formatOptions.mVersion); + } + + if (mOutStream == null) { + openStream(); + } + BinaryDictEncoderUtils.writeDictionaryHeader(mOutStream, dict, formatOptions); + + // Addresses are limited to 3 bytes, but since addresses can be relative to each node + // array, the structure itself is not limited to 16MB. However, if it is over 16MB deciding + // the order of the PtNode arrays becomes a quite complicated problem, because though the + // dictionary itself does not have a size limit, each node array must still be within 16MB + // of all its children and parents. As long as this is ensured, the dictionary file may + // grow to any size. + + // Leave the choice of the optimal node order to the flattenTree function. + MakedictLog.i("Flattening the tree..."); + ArrayList<PtNodeArray> flatNodes = BinaryDictEncoderUtils.flattenTree(dict.mRootNodeArray); + + MakedictLog.i("Computing addresses..."); + BinaryDictEncoderUtils.computeAddresses(dict, flatNodes); + MakedictLog.i("Checking PtNode array..."); + if (MakedictLog.DBG) BinaryDictEncoderUtils.checkFlatPtNodeArrayList(flatNodes); + + // Create a buffer that matches the final dictionary size. + final PtNodeArray lastNodeArray = flatNodes.get(flatNodes.size() - 1); + final int bufferSize = lastNodeArray.mCachedAddressAfterUpdate + lastNodeArray.mCachedSize; + mBuffer = new byte[bufferSize]; + + MakedictLog.i("Writing file..."); + + for (PtNodeArray nodeArray : flatNodes) { + BinaryDictEncoderUtils.writePlacedPtNodeArray(dict, this, nodeArray); + } + if (MakedictLog.DBG) BinaryDictEncoderUtils.showStatistics(flatNodes); + mOutStream.write(mBuffer, 0, mPosition); + + MakedictLog.i("Done"); + close(); + } + + @Override + public void setPosition(final int position) { + if (mBuffer == null || position < 0 || position >= mBuffer.length) return; + mPosition = position; + } + + @Override + public int getPosition() { + return mPosition; + } + + @Override + public void writePtNodeCount(final int ptNodeCount) { + final int countSize = BinaryDictIOUtils.getPtNodeCountSize(ptNodeCount); + if (countSize != 1 && countSize != 2) { + throw new RuntimeException("Strange size from getGroupCountSize : " + countSize); + } + final int encodedPtNodeCount = (countSize == 2) ? + (ptNodeCount | FormatSpec.LARGE_PTNODE_ARRAY_SIZE_FIELD_SIZE_FLAG) : ptNodeCount; + mPosition = BinaryDictEncoderUtils.writeUIntToBuffer(mBuffer, mPosition, encodedPtNodeCount, + countSize); + } + + private void writePtNodeFlags(final PtNode ptNode) { + final int childrenPos = BinaryDictEncoderUtils.getChildrenPosition(ptNode); + mPosition = BinaryDictEncoderUtils.writeUIntToBuffer(mBuffer, mPosition, + BinaryDictEncoderUtils.makePtNodeFlags(ptNode, childrenPos), + FormatSpec.PTNODE_FLAGS_SIZE); + } + + private void writeCharacters(final int[] codePoints, final boolean hasSeveralChars) { + mPosition = CharEncoding.writeCharArray(codePoints, mBuffer, mPosition); + if (hasSeveralChars) { + mBuffer[mPosition++] = FormatSpec.PTNODE_CHARACTERS_TERMINATOR; + } + } + + private void writeFrequency(final int frequency) { + if (frequency >= 0) { + mPosition = BinaryDictEncoderUtils.writeUIntToBuffer(mBuffer, mPosition, frequency, + FormatSpec.PTNODE_FREQUENCY_SIZE); + } + } + + private void writeChildrenPosition(final PtNode ptNode) { + final int childrenPos = BinaryDictEncoderUtils.getChildrenPosition(ptNode); + mPosition += BinaryDictEncoderUtils.writeChildrenPosition(mBuffer, mPosition, + childrenPos); + } + + /** + * Write a shortcut attributes list to mBuffer. + * + * @param shortcuts the shortcut attributes list. + */ + private void writeShortcuts(final ArrayList<WeightedString> shortcuts) { + if (null == shortcuts || shortcuts.isEmpty()) return; + + final int indexOfShortcutByteSize = mPosition; + mPosition += FormatSpec.PTNODE_SHORTCUT_LIST_SIZE_SIZE; + final Iterator<WeightedString> shortcutIterator = shortcuts.iterator(); + while (shortcutIterator.hasNext()) { + final WeightedString target = shortcutIterator.next(); + final int shortcutFlags = BinaryDictEncoderUtils.makeShortcutFlags( + shortcutIterator.hasNext(), + target.getProbability()); + mPosition = BinaryDictEncoderUtils.writeUIntToBuffer(mBuffer, mPosition, shortcutFlags, + FormatSpec.PTNODE_ATTRIBUTE_FLAGS_SIZE); + final int shortcutShift = CharEncoding.writeString(mBuffer, mPosition, target.mWord); + mPosition += shortcutShift; + } + final int shortcutByteSize = mPosition - indexOfShortcutByteSize; + if (shortcutByteSize > FormatSpec.MAX_SHORTCUT_LIST_SIZE_IN_A_PTNODE) { + throw new RuntimeException("Shortcut list too large"); + } + BinaryDictEncoderUtils.writeUIntToBuffer(mBuffer, indexOfShortcutByteSize, shortcutByteSize, + FormatSpec.PTNODE_SHORTCUT_LIST_SIZE_SIZE); + } + + /** + * Write a bigram attributes list to mBuffer. + * + * @param bigrams the bigram attributes list. + * @param dict the dictionary the node array is a part of (for relative offsets). + */ + private void writeBigrams(final ArrayList<WeightedString> bigrams, + final FusionDictionary dict) { + if (bigrams == null) return; + + final Iterator<WeightedString> bigramIterator = bigrams.iterator(); + while (bigramIterator.hasNext()) { + final WeightedString bigram = bigramIterator.next(); + final PtNode target = + FusionDictionary.findWordInTree(dict.mRootNodeArray, bigram.mWord); + final int addressOfBigram = target.mCachedAddressAfterUpdate; + final int unigramFrequencyForThisWord = target.getProbability(); + final int offset = addressOfBigram + - (mPosition + FormatSpec.PTNODE_ATTRIBUTE_FLAGS_SIZE); + final int bigramFlags = BinaryDictEncoderUtils.makeBigramFlags(bigramIterator.hasNext(), + offset, bigram.getProbability(), unigramFrequencyForThisWord, bigram.mWord); + mPosition = BinaryDictEncoderUtils.writeUIntToBuffer(mBuffer, mPosition, bigramFlags, + FormatSpec.PTNODE_ATTRIBUTE_FLAGS_SIZE); + mPosition += BinaryDictEncoderUtils.writeChildrenPosition(mBuffer, mPosition, + Math.abs(offset)); + } + } + + @Override + public void writeForwardLinkAddress(final int forwardLinkAddress) { + mPosition = BinaryDictEncoderUtils.writeUIntToBuffer(mBuffer, mPosition, forwardLinkAddress, + FormatSpec.FORWARD_LINK_ADDRESS_SIZE); + } + + @Override + public void writePtNode(final PtNode ptNode, final FusionDictionary dict) { + writePtNodeFlags(ptNode); + writeCharacters(ptNode.mChars, ptNode.hasSeveralChars()); + writeFrequency(ptNode.getProbability()); + writeChildrenPosition(ptNode); + writeShortcuts(ptNode.mShortcutTargets); + writeBigrams(ptNode.mBigrams, dict); + } +} diff --git a/tests/src/com/android/inputmethod/latin/makedict/Ver4DictDecoder.java b/tests/src/com/android/inputmethod/latin/makedict/Ver4DictDecoder.java new file mode 100644 index 000000000..f3fad7e99 --- /dev/null +++ b/tests/src/com/android/inputmethod/latin/makedict/Ver4DictDecoder.java @@ -0,0 +1,115 @@ +/* + * Copyright (C) 2013 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.inputmethod.latin.makedict; + +import com.android.inputmethod.annotations.UsedForTesting; +import com.android.inputmethod.latin.BinaryDictionary; +import com.android.inputmethod.latin.utils.CollectionUtils; +import com.android.inputmethod.latin.utils.FileUtils; + +import java.io.File; +import java.io.FileNotFoundException; +import java.io.IOException; +import java.util.ArrayList; + +/** + * An implementation of binary dictionary decoder for version 4 binary dictionary. + */ +@UsedForTesting +public class Ver4DictDecoder extends AbstractDictDecoder { + private static final String TAG = Ver4DictDecoder.class.getSimpleName(); + + final File mDictDirectory; + + @UsedForTesting + /* package */ Ver4DictDecoder(final File dictDirectory, final int factoryFlag) { + this(dictDirectory, null /* factory */); + } + + @UsedForTesting + /* package */ Ver4DictDecoder(final File dictDirectory, final DictionaryBufferFactory factory) { + mDictDirectory = dictDirectory; + + } + + @Override + public DictionaryHeader readHeader() throws IOException, UnsupportedFormatException { + // dictType is not being used in dicttool. Passing an empty string. + final BinaryDictionary binaryDictionary= new BinaryDictionary( + mDictDirectory.getAbsolutePath(), 0 /* offset */, 0 /* length */, + true /* useFullEditDistance */, null /* locale */, + "" /* dictType */, true /* isUpdatable */); + final DictionaryHeader header = binaryDictionary.getHeader(); + binaryDictionary.close(); + if (header == null) { + throw new IOException("Cannot read the dictionary header."); + } + return header; + } + + @Override + public FusionDictionary readDictionaryBinary(final boolean deleteDictIfBroken) + throws FileNotFoundException, IOException, UnsupportedFormatException { + // dictType is not being used in dicttool. Passing an empty string. + final BinaryDictionary binaryDictionary = new BinaryDictionary( + mDictDirectory.getAbsolutePath(), 0 /* offset */, 0 /* length */, + true /* useFullEditDistance */, null /* locale */, + "" /* dictType */, true /* isUpdatable */); + final DictionaryHeader header = readHeader(); + final FusionDictionary fusionDict = + new FusionDictionary(new FusionDictionary.PtNodeArray(), header.mDictionaryOptions); + int token = 0; + final ArrayList<WordProperty> wordProperties = CollectionUtils.newArrayList(); + do { + final BinaryDictionary.GetNextWordPropertyResult result = + binaryDictionary.getNextWordProperty(token); + final WordProperty wordProperty = result.mWordProperty; + if (wordProperty == null) { + binaryDictionary.close(); + if (deleteDictIfBroken) { + FileUtils.deleteRecursively(mDictDirectory); + } + return null; + } + wordProperties.add(wordProperty); + token = result.mNextToken; + } while (token != 0); + + // Insert unigrams into the fusion dictionary. + for (final WordProperty wordProperty : wordProperties) { + if (wordProperty.mIsBlacklistEntry) { + fusionDict.addBlacklistEntry(wordProperty.mWord, wordProperty.mShortcutTargets, + wordProperty.mIsNotAWord); + } else { + fusionDict.add(wordProperty.mWord, wordProperty.mProbabilityInfo, + wordProperty.mShortcutTargets, wordProperty.mIsNotAWord); + } + } + // Insert bigrams into the fusion dictionary. + for (final WordProperty wordProperty : wordProperties) { + if (wordProperty.mBigrams == null) { + continue; + } + final String word0 = wordProperty.mWord; + for (final WeightedString bigram : wordProperty.mBigrams) { + fusionDict.setBigram(word0, bigram.mWord, bigram.mProbabilityInfo); + } + } + binaryDictionary.close(); + return fusionDict; + } +} diff --git a/tests/src/com/android/inputmethod/latin/makedict/Ver4DictEncoder.java b/tests/src/com/android/inputmethod/latin/makedict/Ver4DictEncoder.java new file mode 100644 index 000000000..dab9a4315 --- /dev/null +++ b/tests/src/com/android/inputmethod/latin/makedict/Ver4DictEncoder.java @@ -0,0 +1,127 @@ +/* + * Copyright (C) 2013 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.inputmethod.latin.makedict; + +import com.android.inputmethod.annotations.UsedForTesting; +import com.android.inputmethod.latin.BinaryDictionary; +import com.android.inputmethod.latin.Dictionary; +import com.android.inputmethod.latin.makedict.FormatSpec.FormatOptions; +import com.android.inputmethod.latin.makedict.FusionDictionary.PtNode; +import com.android.inputmethod.latin.utils.BinaryDictionaryUtils; +import com.android.inputmethod.latin.utils.LocaleUtils; + +import java.io.File; +import java.io.IOException; + +/** + * An implementation of DictEncoder for version 4 binary dictionary. + */ +@UsedForTesting +public class Ver4DictEncoder implements DictEncoder { + private final File mDictPlacedDir; + + @UsedForTesting + public Ver4DictEncoder(final File dictPlacedDir) { + mDictPlacedDir = dictPlacedDir; + } + + // TODO: This builds a FusionDictionary first and iterates it to add words to the binary + // dictionary. However, it is possible to just add words directly to the binary dictionary + // instead. + // In the long run, when we stop supporting version 2, FusionDictionary will become deprecated + // and we can remove it. Then we'll be able to just call BinaryDictionary directly. + @Override + public void writeDictionary(FusionDictionary dict, FormatOptions formatOptions) + throws IOException, UnsupportedFormatException { + if (formatOptions.mVersion != FormatSpec.VERSION4) { + throw new UnsupportedFormatException("File header has a wrong version number : " + + formatOptions.mVersion); + } + if (!mDictPlacedDir.isDirectory()) { + throw new UnsupportedFormatException("Given path is not a directory."); + } + if (!BinaryDictionaryUtils.createEmptyDictFile(mDictPlacedDir.getAbsolutePath(), + FormatSpec.VERSION4, LocaleUtils.constructLocaleFromString( + dict.mOptions.mAttributes.get(DictionaryHeader.DICTIONARY_LOCALE_KEY)), + dict.mOptions.mAttributes)) { + throw new IOException("Cannot create dictionary file : " + + mDictPlacedDir.getAbsolutePath()); + } + final BinaryDictionary binaryDict = new BinaryDictionary(mDictPlacedDir.getAbsolutePath(), + 0l, mDictPlacedDir.length(), true /* useFullEditDistance */, + LocaleUtils.constructLocaleFromString(dict.mOptions.mAttributes.get( + DictionaryHeader.DICTIONARY_LOCALE_KEY)), + Dictionary.TYPE_USER /* Dictionary type. Does not matter for us */, + true /* isUpdatable */); + if (!binaryDict.isValidDictionary()) { + // Somehow createEmptyDictFile returned true, but the file was not created correctly + throw new IOException("Cannot create dictionary file"); + } + for (final WordProperty wordProperty : dict) { + // TODO: switch to addMultipleDictionaryEntries when they support shortcuts + if (null == wordProperty.mShortcutTargets || wordProperty.mShortcutTargets.isEmpty()) { + binaryDict.addUnigramWord(wordProperty.mWord, wordProperty.getProbability(), + null /* shortcutTarget */, 0 /* shortcutProbability */, + wordProperty.mIsNotAWord, wordProperty.mIsBlacklistEntry, + 0 /* timestamp */); + } else { + for (final WeightedString shortcutTarget : wordProperty.mShortcutTargets) { + binaryDict.addUnigramWord(wordProperty.mWord, wordProperty.getProbability(), + shortcutTarget.mWord, shortcutTarget.getProbability(), + wordProperty.mIsNotAWord, wordProperty.mIsBlacklistEntry, + 0 /* timestamp */); + } + } + if (binaryDict.needsToRunGC(true /* mindsBlockByGC */)) { + binaryDict.flushWithGC(); + } + } + for (final WordProperty word0Property : dict) { + if (null == word0Property.mBigrams) continue; + for (final WeightedString word1 : word0Property.mBigrams) { + binaryDict.addBigramWords(word0Property.mWord, word1.mWord, word1.getProbability(), + 0 /* timestamp */); + if (binaryDict.needsToRunGC(true /* mindsBlockByGC */)) { + binaryDict.flushWithGC(); + } + } + } + binaryDict.flushWithGC(); + binaryDict.close(); + } + + @Override + public void setPosition(int position) { + } + + @Override + public int getPosition() { + return 0; + } + + @Override + public void writePtNodeCount(int ptNodeCount) { + } + + @Override + public void writeForwardLinkAddress(int forwardLinkAddress) { + } + + @Override + public void writePtNode(PtNode ptNode, FusionDictionary dict) { + } +} diff --git a/tests/src/com/android/inputmethod/latin/utils/ByteArrayDictBuffer.java b/tests/src/com/android/inputmethod/latin/utils/ByteArrayDictBuffer.java new file mode 100644 index 000000000..2028298f2 --- /dev/null +++ b/tests/src/com/android/inputmethod/latin/utils/ByteArrayDictBuffer.java @@ -0,0 +1,81 @@ +/* + * Copyright (C) 2013 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.inputmethod.latin.utils; + +import com.android.inputmethod.latin.makedict.BinaryDictDecoderUtils.DictBuffer; + +/** + * This class provides an implementation for the FusionDictionary buffer interface that is backed + * by a simpled byte array. It allows to create a binary dictionary in memory. + */ +public final class ByteArrayDictBuffer implements DictBuffer { + private byte[] mBuffer; + private int mPosition; + + public ByteArrayDictBuffer(final byte[] buffer) { + mBuffer = buffer; + mPosition = 0; + } + + @Override + public int readUnsignedByte() { + return mBuffer[mPosition++] & 0xFF; + } + + @Override + public int readUnsignedShort() { + final int retval = readUnsignedByte(); + return (retval << 8) + readUnsignedByte(); + } + + @Override + public int readUnsignedInt24() { + final int retval = readUnsignedShort(); + return (retval << 8) + readUnsignedByte(); + } + + @Override + public int readInt() { + final int retval = readUnsignedShort(); + return (retval << 16) + readUnsignedShort(); + } + + @Override + public int position() { + return mPosition; + } + + @Override + public void position(int position) { + mPosition = position; + } + + @Override + public void put(final byte b) { + mBuffer[mPosition++] = b; + } + + @Override + public int limit() { + return mBuffer.length - 1; + } + + @Override + public int capacity() { + return mBuffer.length; + } +} |