BinaryDictInputOutput.java revision 666a4338026866df1f18dd6b3f968c3788943e4c
1/* 2 * Copyright (C) 2011 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not 5 * use this file except in compliance with the License. You may obtain a copy of 6 * the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 12 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 13 * License for the specific language governing permissions and limitations under 14 * the License. 15 */ 16 17package com.android.inputmethod.latin.makedict; 18 19import com.android.inputmethod.latin.makedict.FusionDictionary.CharGroup; 20import com.android.inputmethod.latin.makedict.FusionDictionary.DictionaryOptions; 21import com.android.inputmethod.latin.makedict.FusionDictionary.Node; 22import com.android.inputmethod.latin.makedict.FusionDictionary.WeightedString; 23 24import java.io.ByteArrayOutputStream; 25import java.io.File; 26import java.io.FileInputStream; 27import java.io.FileNotFoundException; 28import java.io.IOException; 29import java.io.OutputStream; 30import java.nio.ByteBuffer; 31import java.nio.channels.FileChannel; 32import java.util.ArrayList; 33import java.util.Arrays; 34import java.util.HashMap; 35import java.util.Iterator; 36import java.util.Map; 37import java.util.Stack; 38import java.util.TreeMap; 39 40/** 41 * Reads and writes XML files for a FusionDictionary. 42 * 43 * All the methods in this class are static. 44 */ 45public class BinaryDictInputOutput { 46 47 final static boolean DBG = MakedictLog.DBG; 48 49 /* Node layout is as follows: 50 * | addressType xx : mask with MASK_GROUP_ADDRESS_TYPE 51 * 2 bits, 00 = no children : FLAG_GROUP_ADDRESS_TYPE_NOADDRESS 52 * f | 01 = 1 byte : FLAG_GROUP_ADDRESS_TYPE_ONEBYTE 53 * l | 10 = 2 bytes : FLAG_GROUP_ADDRESS_TYPE_TWOBYTES 54 * a | 11 = 3 bytes : FLAG_GROUP_ADDRESS_TYPE_THREEBYTES 55 * g | has several chars ? 1 bit, 1 = yes, 0 = no : FLAG_HAS_MULTIPLE_CHARS 56 * s | has a terminal ? 1 bit, 1 = yes, 0 = no : FLAG_IS_TERMINAL 57 * | has shortcut targets ? 1 bit, 1 = yes, 0 = no : FLAG_HAS_SHORTCUT_TARGETS 58 * | has bigrams ? 1 bit, 1 = yes, 0 = no : FLAG_HAS_BIGRAMS 59 * 60 * c | IF FLAG_HAS_MULTIPLE_CHARS 61 * h | char, char, char, char n * (1 or 3 bytes) : use CharGroupInfo for i/o helpers 62 * a | end 1 byte, = 0 63 * r | ELSE 64 * s | char 1 or 3 bytes 65 * | END 66 * 67 * f | 68 * r | IF FLAG_IS_TERMINAL 69 * e | frequency 1 byte 70 * q | 71 * 72 * c | IF 00 = FLAG_GROUP_ADDRESS_TYPE_NOADDRESS = addressType 73 * h | // nothing 74 * i | ELSIF 01 = FLAG_GROUP_ADDRESS_TYPE_ONEBYTE == addressType 75 * l | children address, 1 byte 76 * d | ELSIF 10 = FLAG_GROUP_ADDRESS_TYPE_TWOBYTES == addressType 77 * r | children address, 2 bytes 78 * e | ELSE // 11 = FLAG_GROUP_ADDRESS_TYPE_THREEBYTES = addressType 79 * n | children address, 3 bytes 80 * A | END 81 * d 82 * dress 83 * 84 * | IF FLAG_IS_TERMINAL && FLAG_HAS_SHORTCUT_TARGETS 85 * | shortcut string list 86 * | IF FLAG_IS_TERMINAL && FLAG_HAS_BIGRAMS 87 * | bigrams address list 88 * 89 * Char format is: 90 * 1 byte = bbbbbbbb match 91 * case 000xxxxx: xxxxx << 16 + next byte << 8 + next byte 92 * else: if 00011111 (= 0x1F) : this is the terminator. This is a relevant choice because 93 * unicode code points range from 0 to 0x10FFFF, so any 3-byte value starting with 94 * 00011111 would be outside unicode. 95 * else: iso-latin-1 code 96 * This allows for the whole unicode range to be encoded, including chars outside of 97 * the BMP. Also everything in the iso-latin-1 charset is only 1 byte, except control 98 * characters which should never happen anyway (and still work, but take 3 bytes). 99 * 100 * bigram address list is: 101 * <flags> = | hasNext = 1 bit, 1 = yes, 0 = no : FLAG_ATTRIBUTE_HAS_NEXT 102 * | addressSign = 1 bit, : FLAG_ATTRIBUTE_OFFSET_NEGATIVE 103 * | 1 = must take -address, 0 = must take +address 104 * | xx : mask with MASK_ATTRIBUTE_ADDRESS_TYPE 105 * | addressFormat = 2 bits, 00 = unused : FLAG_ATTRIBUTE_ADDRESS_TYPE_ONEBYTE 106 * | 01 = 1 byte : FLAG_ATTRIBUTE_ADDRESS_TYPE_ONEBYTE 107 * | 10 = 2 bytes : FLAG_ATTRIBUTE_ADDRESS_TYPE_TWOBYTES 108 * | 11 = 3 bytes : FLAG_ATTRIBUTE_ADDRESS_TYPE_THREEBYTES 109 * | 4 bits : frequency : mask with FLAG_ATTRIBUTE_FREQUENCY 110 * <address> | IF (01 == FLAG_ATTRIBUTE_ADDRESS_TYPE_ONEBYTE == addressFormat) 111 * | read 1 byte, add top 4 bits 112 * | ELSIF (10 == FLAG_ATTRIBUTE_ADDRESS_TYPE_TWOBYTES == addressFormat) 113 * | read 2 bytes, add top 4 bits 114 * | ELSE // 11 == FLAG_ATTRIBUTE_ADDRESS_TYPE_THREEBYTES == addressFormat 115 * | read 3 bytes, add top 4 bits 116 * | END 117 * | if (FLAG_ATTRIBUTE_OFFSET_NEGATIVE) then address = -address 118 * if (FLAG_ATTRIBUTE_HAS_NEXT) goto bigram_and_shortcut_address_list_is 119 * 120 * shortcut string list is: 121 * <byte size> = GROUP_SHORTCUT_LIST_SIZE_SIZE bytes, big-endian: size of the list, in bytes. 122 * <flags> = | hasNext = 1 bit, 1 = yes, 0 = no : FLAG_ATTRIBUTE_HAS_NEXT 123 * | reserved = 3 bits, must be 0 124 * | 4 bits : frequency : mask with FLAG_ATTRIBUTE_FREQUENCY 125 * <shortcut> = | string of characters at the char format described above, with the terminator 126 * | used to signal the end of the string. 127 * if (FLAG_ATTRIBUTE_HAS_NEXT goto flags 128 */ 129 130 private static final int VERSION_1_MAGIC_NUMBER = 0x78B1; 131 public static final int VERSION_2_MAGIC_NUMBER = 0x9BC13AFE; 132 private static final int MINIMUM_SUPPORTED_VERSION = 1; 133 private static final int MAXIMUM_SUPPORTED_VERSION = 2; 134 private static final int NOT_A_VERSION_NUMBER = -1; 135 private static final int FIRST_VERSION_WITH_HEADER_SIZE = 2; 136 137 // These options need to be the same numeric values as the one in the native reading code. 138 private static final int GERMAN_UMLAUT_PROCESSING_FLAG = 0x1; 139 private static final int FRENCH_LIGATURE_PROCESSING_FLAG = 0x4; 140 private static final int CONTAINS_BIGRAMS_FLAG = 0x8; 141 142 // TODO: Make this value adaptative to content data, store it in the header, and 143 // use it in the reading code. 144 private static final int MAX_WORD_LENGTH = 48; 145 146 private static final int MASK_GROUP_ADDRESS_TYPE = 0xC0; 147 private static final int FLAG_GROUP_ADDRESS_TYPE_NOADDRESS = 0x00; 148 private static final int FLAG_GROUP_ADDRESS_TYPE_ONEBYTE = 0x40; 149 private static final int FLAG_GROUP_ADDRESS_TYPE_TWOBYTES = 0x80; 150 private static final int FLAG_GROUP_ADDRESS_TYPE_THREEBYTES = 0xC0; 151 152 private static final int FLAG_HAS_MULTIPLE_CHARS = 0x20; 153 154 private static final int FLAG_IS_TERMINAL = 0x10; 155 private static final int FLAG_HAS_SHORTCUT_TARGETS = 0x08; 156 private static final int FLAG_HAS_BIGRAMS = 0x04; 157 158 private static final int FLAG_ATTRIBUTE_HAS_NEXT = 0x80; 159 private static final int FLAG_ATTRIBUTE_OFFSET_NEGATIVE = 0x40; 160 private static final int MASK_ATTRIBUTE_ADDRESS_TYPE = 0x30; 161 private static final int FLAG_ATTRIBUTE_ADDRESS_TYPE_ONEBYTE = 0x10; 162 private static final int FLAG_ATTRIBUTE_ADDRESS_TYPE_TWOBYTES = 0x20; 163 private static final int FLAG_ATTRIBUTE_ADDRESS_TYPE_THREEBYTES = 0x30; 164 private static final int FLAG_ATTRIBUTE_FREQUENCY = 0x0F; 165 166 private static final int GROUP_CHARACTERS_TERMINATOR = 0x1F; 167 168 private static final int GROUP_TERMINATOR_SIZE = 1; 169 private static final int GROUP_FLAGS_SIZE = 1; 170 private static final int GROUP_FREQUENCY_SIZE = 1; 171 private static final int GROUP_MAX_ADDRESS_SIZE = 3; 172 private static final int GROUP_ATTRIBUTE_FLAGS_SIZE = 1; 173 private static final int GROUP_ATTRIBUTE_MAX_ADDRESS_SIZE = 3; 174 private static final int GROUP_SHORTCUT_LIST_SIZE_SIZE = 2; 175 176 private static final int NO_CHILDREN_ADDRESS = Integer.MIN_VALUE; 177 private static final int INVALID_CHARACTER = -1; 178 179 private static final int MAX_CHARGROUPS_FOR_ONE_BYTE_CHARGROUP_COUNT = 0x7F; // 127 180 private static final int MAX_CHARGROUPS_IN_A_NODE = 0x7FFF; // 32767 181 182 private static final int MAX_TERMINAL_FREQUENCY = 255; 183 private static final int MAX_BIGRAM_FREQUENCY = 15; 184 185 // Arbitrary limit to how much passes we consider address size compression should 186 // terminate in. At the time of this writing, our largest dictionary completes 187 // compression in five passes. 188 // If the number of passes exceeds this number, makedict bails with an exception on 189 // suspicion that a bug might be causing an infinite loop. 190 private static final int MAX_PASSES = 24; 191 192 public interface FusionDictionaryBufferInterface { 193 public int readUnsignedByte(); 194 public int readUnsignedShort(); 195 public int readUnsignedInt24(); 196 public int readInt(); 197 public int position(); 198 public void position(int newPosition); 199 } 200 201 public static final class ByteBufferWrapper implements FusionDictionaryBufferInterface { 202 private ByteBuffer mBuffer; 203 204 public ByteBufferWrapper(final ByteBuffer buffer) { 205 mBuffer = buffer; 206 } 207 208 @Override 209 public int readUnsignedByte() { 210 return ((int)mBuffer.get()) & 0xFF; 211 } 212 213 @Override 214 public int readUnsignedShort() { 215 return ((int)mBuffer.getShort()) & 0xFFFF; 216 } 217 218 @Override 219 public int readUnsignedInt24() { 220 final int retval = readUnsignedByte(); 221 return (retval << 16) + readUnsignedShort(); 222 } 223 224 @Override 225 public int readInt() { 226 return mBuffer.getInt(); 227 } 228 229 @Override 230 public int position() { 231 return mBuffer.position(); 232 } 233 234 @Override 235 public void position(int newPos) { 236 mBuffer.position(newPos); 237 } 238 } 239 240 /** 241 * A class grouping utility function for our specific character encoding. 242 */ 243 private static class CharEncoding { 244 245 private static final int MINIMAL_ONE_BYTE_CHARACTER_VALUE = 0x20; 246 private static final int MAXIMAL_ONE_BYTE_CHARACTER_VALUE = 0xFF; 247 248 /** 249 * Helper method to find out whether this code fits on one byte 250 */ 251 private static boolean fitsOnOneByte(int character) { 252 return character >= MINIMAL_ONE_BYTE_CHARACTER_VALUE 253 && character <= MAXIMAL_ONE_BYTE_CHARACTER_VALUE; 254 } 255 256 /** 257 * Compute the size of a character given its character code. 258 * 259 * Char format is: 260 * 1 byte = bbbbbbbb match 261 * case 000xxxxx: xxxxx << 16 + next byte << 8 + next byte 262 * else: if 00011111 (= 0x1F) : this is the terminator. This is a relevant choice because 263 * unicode code points range from 0 to 0x10FFFF, so any 3-byte value starting with 264 * 00011111 would be outside unicode. 265 * else: iso-latin-1 code 266 * This allows for the whole unicode range to be encoded, including chars outside of 267 * the BMP. Also everything in the iso-latin-1 charset is only 1 byte, except control 268 * characters which should never happen anyway (and still work, but take 3 bytes). 269 * 270 * @param character the character code. 271 * @return the size in binary encoded-form, either 1 or 3 bytes. 272 */ 273 private static int getCharSize(int character) { 274 // See char encoding in FusionDictionary.java 275 if (fitsOnOneByte(character)) return 1; 276 if (INVALID_CHARACTER == character) return 1; 277 return 3; 278 } 279 280 /** 281 * Compute the byte size of a character array. 282 */ 283 private static int getCharArraySize(final int[] chars) { 284 int size = 0; 285 for (int character : chars) size += getCharSize(character); 286 return size; 287 } 288 289 /** 290 * Writes a char array to a byte buffer. 291 * 292 * @param codePoints the code point array to write. 293 * @param buffer the byte buffer to write to. 294 * @param index the index in buffer to write the character array to. 295 * @return the index after the last character. 296 */ 297 private static int writeCharArray(final int[] codePoints, final byte[] buffer, int index) { 298 for (int codePoint : codePoints) { 299 if (1 == getCharSize(codePoint)) { 300 buffer[index++] = (byte)codePoint; 301 } else { 302 buffer[index++] = (byte)(0xFF & (codePoint >> 16)); 303 buffer[index++] = (byte)(0xFF & (codePoint >> 8)); 304 buffer[index++] = (byte)(0xFF & codePoint); 305 } 306 } 307 return index; 308 } 309 310 /** 311 * Writes a string with our character format to a byte buffer. 312 * 313 * This will also write the terminator byte. 314 * 315 * @param buffer the byte buffer to write to. 316 * @param origin the offset to write from. 317 * @param word the string to write. 318 * @return the size written, in bytes. 319 */ 320 private static int writeString(final byte[] buffer, final int origin, 321 final String word) { 322 final int length = word.length(); 323 int index = origin; 324 for (int i = 0; i < length; i = word.offsetByCodePoints(i, 1)) { 325 final int codePoint = word.codePointAt(i); 326 if (1 == getCharSize(codePoint)) { 327 buffer[index++] = (byte)codePoint; 328 } else { 329 buffer[index++] = (byte)(0xFF & (codePoint >> 16)); 330 buffer[index++] = (byte)(0xFF & (codePoint >> 8)); 331 buffer[index++] = (byte)(0xFF & codePoint); 332 } 333 } 334 buffer[index++] = GROUP_CHARACTERS_TERMINATOR; 335 return index - origin; 336 } 337 338 /** 339 * Writes a string with our character format to a ByteArrayOutputStream. 340 * 341 * This will also write the terminator byte. 342 * 343 * @param buffer the ByteArrayOutputStream to write to. 344 * @param word the string to write. 345 */ 346 private static void writeString(ByteArrayOutputStream buffer, final String word) { 347 final int length = word.length(); 348 for (int i = 0; i < length; i = word.offsetByCodePoints(i, 1)) { 349 final int codePoint = word.codePointAt(i); 350 if (1 == getCharSize(codePoint)) { 351 buffer.write((byte) codePoint); 352 } else { 353 buffer.write((byte) (0xFF & (codePoint >> 16))); 354 buffer.write((byte) (0xFF & (codePoint >> 8))); 355 buffer.write((byte) (0xFF & codePoint)); 356 } 357 } 358 buffer.write(GROUP_CHARACTERS_TERMINATOR); 359 } 360 361 /** 362 * Reads a string from a buffer. This is the converse of the above method. 363 */ 364 private static String readString(final FusionDictionaryBufferInterface buffer) { 365 final StringBuilder s = new StringBuilder(); 366 int character = readChar(buffer); 367 while (character != INVALID_CHARACTER) { 368 s.appendCodePoint(character); 369 character = readChar(buffer); 370 } 371 return s.toString(); 372 } 373 374 /** 375 * Reads a character from the buffer. 376 * 377 * This follows the character format documented earlier in this source file. 378 * 379 * @param buffer the buffer, positioned over an encoded character. 380 * @return the character code. 381 */ 382 private static int readChar(final FusionDictionaryBufferInterface buffer) { 383 int character = buffer.readUnsignedByte(); 384 if (!fitsOnOneByte(character)) { 385 if (GROUP_CHARACTERS_TERMINATOR == character) return INVALID_CHARACTER; 386 character <<= 16; 387 character += buffer.readUnsignedShort(); 388 } 389 return character; 390 } 391 } 392 393 /** 394 * Compute the binary size of the character array in a group 395 * 396 * If only one character, this is the size of this character. If many, it's the sum of their 397 * sizes + 1 byte for the terminator. 398 * 399 * @param group the group 400 * @return the size of the char array, including the terminator if any 401 */ 402 private static int getGroupCharactersSize(CharGroup group) { 403 int size = CharEncoding.getCharArraySize(group.mChars); 404 if (group.hasSeveralChars()) size += GROUP_TERMINATOR_SIZE; 405 return size; 406 } 407 408 /** 409 * Compute the binary size of the group count 410 * @param count the group count 411 * @return the size of the group count, either 1 or 2 bytes. 412 */ 413 private static int getGroupCountSize(final int count) { 414 if (MAX_CHARGROUPS_FOR_ONE_BYTE_CHARGROUP_COUNT >= count) { 415 return 1; 416 } else if (MAX_CHARGROUPS_IN_A_NODE >= count) { 417 return 2; 418 } else { 419 throw new RuntimeException("Can't have more than " + MAX_CHARGROUPS_IN_A_NODE 420 + " groups in a node (found " + count +")"); 421 } 422 } 423 424 /** 425 * Compute the binary size of the group count for a node 426 * @param node the node 427 * @return the size of the group count, either 1 or 2 bytes. 428 */ 429 private static int getGroupCountSize(final Node node) { 430 return getGroupCountSize(node.mData.size()); 431 } 432 433 /** 434 * Compute the size of a shortcut in bytes. 435 */ 436 private static int getShortcutSize(final WeightedString shortcut) { 437 int size = GROUP_ATTRIBUTE_FLAGS_SIZE; 438 final String word = shortcut.mWord; 439 final int length = word.length(); 440 for (int i = 0; i < length; i = word.offsetByCodePoints(i, 1)) { 441 final int codePoint = word.codePointAt(i); 442 size += CharEncoding.getCharSize(codePoint); 443 } 444 size += GROUP_TERMINATOR_SIZE; 445 return size; 446 } 447 448 /** 449 * Compute the size of a shortcut list in bytes. 450 * 451 * This is known in advance and does not change according to position in the file 452 * like address lists do. 453 */ 454 private static int getShortcutListSize(final ArrayList<WeightedString> shortcutList) { 455 if (null == shortcutList) return 0; 456 int size = GROUP_SHORTCUT_LIST_SIZE_SIZE; 457 for (final WeightedString shortcut : shortcutList) { 458 size += getShortcutSize(shortcut); 459 } 460 return size; 461 } 462 463 /** 464 * Compute the maximum size of a CharGroup, assuming 3-byte addresses for everything. 465 * 466 * @param group the CharGroup to compute the size of. 467 * @return the maximum size of the group. 468 */ 469 private static int getCharGroupMaximumSize(CharGroup group) { 470 int size = getGroupCharactersSize(group) + GROUP_FLAGS_SIZE; 471 // If terminal, one byte for the frequency 472 if (group.isTerminal()) size += GROUP_FREQUENCY_SIZE; 473 size += GROUP_MAX_ADDRESS_SIZE; // For children address 474 size += getShortcutListSize(group.mShortcutTargets); 475 if (null != group.mBigrams) { 476 size += (GROUP_ATTRIBUTE_FLAGS_SIZE + GROUP_ATTRIBUTE_MAX_ADDRESS_SIZE) 477 * group.mBigrams.size(); 478 } 479 return size; 480 } 481 482 /** 483 * Compute the maximum size of a node, assuming 3-byte addresses for everything, and caches 484 * it in the 'actualSize' member of the node. 485 * 486 * @param node the node to compute the maximum size of. 487 */ 488 private static void setNodeMaximumSize(Node node) { 489 int size = getGroupCountSize(node); 490 for (CharGroup g : node.mData) { 491 final int groupSize = getCharGroupMaximumSize(g); 492 g.mCachedSize = groupSize; 493 size += groupSize; 494 } 495 node.mCachedSize = size; 496 } 497 498 /** 499 * Helper method to hide the actual value of the no children address. 500 */ 501 private static boolean hasChildrenAddress(int address) { 502 return NO_CHILDREN_ADDRESS != address; 503 } 504 505 /** 506 * Compute the size, in bytes, that an address will occupy. 507 * 508 * This can be used either for children addresses (which are always positive) or for 509 * attribute, which may be positive or negative but 510 * store their sign bit separately. 511 * 512 * @param address the address 513 * @return the byte size. 514 */ 515 private static int getByteSize(int address) { 516 assert(address < 0x1000000); 517 if (!hasChildrenAddress(address)) { 518 return 0; 519 } else if (Math.abs(address) < 0x100) { 520 return 1; 521 } else if (Math.abs(address) < 0x10000) { 522 return 2; 523 } else { 524 return 3; 525 } 526 } 527 // End utility methods. 528 529 // This method is responsible for finding a nice ordering of the nodes that favors run-time 530 // cache performance and dictionary size. 531 /* package for tests */ static ArrayList<Node> flattenTree(Node root) { 532 final int treeSize = FusionDictionary.countCharGroups(root); 533 MakedictLog.i("Counted nodes : " + treeSize); 534 final ArrayList<Node> flatTree = new ArrayList<Node>(treeSize); 535 return flattenTreeInner(flatTree, root); 536 } 537 538 private static ArrayList<Node> flattenTreeInner(ArrayList<Node> list, Node node) { 539 // Removing the node is necessary if the tails are merged, because we would then 540 // add the same node several times when we only want it once. A number of places in 541 // the code also depends on any node being only once in the list. 542 // Merging tails can only be done if there are no attributes. Searching for attributes 543 // in LatinIME code depends on a total breadth-first ordering, which merging tails 544 // breaks. If there are no attributes, it should be fine (and reduce the file size) 545 // to merge tails, and removing the node from the list would be necessary. However, 546 // we don't merge tails because breaking the breadth-first ordering would result in 547 // extreme overhead at bigram lookup time (it would make the search function O(n) instead 548 // of the current O(log(n)), where n=number of nodes in the dictionary which is pretty 549 // high). 550 // If no nodes are ever merged, we can't have the same node twice in the list, hence 551 // searching for duplicates in unnecessary. It is also very performance consuming, 552 // since `list' is an ArrayList so it's an O(n) operation that runs on all nodes, making 553 // this simple list.remove operation O(n*n) overall. On Android this overhead is very 554 // high. 555 // For future reference, the code to remove duplicate is a simple : list.remove(node); 556 list.add(node); 557 final ArrayList<CharGroup> branches = node.mData; 558 final int nodeSize = branches.size(); 559 for (CharGroup group : branches) { 560 if (null != group.mChildren) flattenTreeInner(list, group.mChildren); 561 } 562 return list; 563 } 564 565 /** 566 * Finds the absolute address of a word in the dictionary. 567 * 568 * @param dict the dictionary in which to search. 569 * @param word the word we are searching for. 570 * @return the word address. If it is not found, an exception is thrown. 571 */ 572 private static int findAddressOfWord(final FusionDictionary dict, final String word) { 573 return FusionDictionary.findWordInTree(dict.mRoot, word).mCachedAddress; 574 } 575 576 /** 577 * Computes the actual node size, based on the cached addresses of the children nodes. 578 * 579 * Each node stores its tentative address. During dictionary address computing, these 580 * are not final, but they can be used to compute the node size (the node size depends 581 * on the address of the children because the number of bytes necessary to store an 582 * address depends on its numeric value. The return value indicates whether the node 583 * contents (as in, any of the addresses stored in the cache fields) have changed with 584 * respect to their previous value. 585 * 586 * @param node the node to compute the size of. 587 * @param dict the dictionary in which the word/attributes are to be found. 588 * @return false if none of the cached addresses inside the node changed, true otherwise. 589 */ 590 private static boolean computeActualNodeSize(Node node, FusionDictionary dict) { 591 boolean changed = false; 592 int size = getGroupCountSize(node); 593 for (CharGroup group : node.mData) { 594 if (group.mCachedAddress != node.mCachedAddress + size) { 595 changed = true; 596 group.mCachedAddress = node.mCachedAddress + size; 597 } 598 int groupSize = GROUP_FLAGS_SIZE + getGroupCharactersSize(group); 599 if (group.isTerminal()) groupSize += GROUP_FREQUENCY_SIZE; 600 if (null != group.mChildren) { 601 final int offsetBasePoint= groupSize + node.mCachedAddress + size; 602 final int offset = group.mChildren.mCachedAddress - offsetBasePoint; 603 groupSize += getByteSize(offset); 604 } 605 groupSize += getShortcutListSize(group.mShortcutTargets); 606 if (null != group.mBigrams) { 607 for (WeightedString bigram : group.mBigrams) { 608 final int offsetBasePoint = groupSize + node.mCachedAddress + size 609 + GROUP_FLAGS_SIZE; 610 final int addressOfBigram = findAddressOfWord(dict, bigram.mWord); 611 final int offset = addressOfBigram - offsetBasePoint; 612 groupSize += getByteSize(offset) + GROUP_FLAGS_SIZE; 613 } 614 } 615 group.mCachedSize = groupSize; 616 size += groupSize; 617 } 618 if (node.mCachedSize != size) { 619 node.mCachedSize = size; 620 changed = true; 621 } 622 return changed; 623 } 624 625 /** 626 * Computes the byte size of a list of nodes and updates each node cached position. 627 * 628 * @param flatNodes the array of nodes. 629 * @return the byte size of the entire stack. 630 */ 631 private static int stackNodes(ArrayList<Node> flatNodes) { 632 int nodeOffset = 0; 633 for (Node n : flatNodes) { 634 n.mCachedAddress = nodeOffset; 635 int groupCountSize = getGroupCountSize(n); 636 int groupOffset = 0; 637 for (CharGroup g : n.mData) { 638 g.mCachedAddress = groupCountSize + nodeOffset + groupOffset; 639 groupOffset += g.mCachedSize; 640 } 641 if (groupOffset + groupCountSize != n.mCachedSize) { 642 throw new RuntimeException("Bug : Stored and computed node size differ"); 643 } 644 nodeOffset += n.mCachedSize; 645 } 646 return nodeOffset; 647 } 648 649 /** 650 * Compute the addresses and sizes of an ordered node array. 651 * 652 * This method takes a node array and will update its cached address and size values 653 * so that they can be written into a file. It determines the smallest size each of the 654 * nodes can be given the addresses of its children and attributes, and store that into 655 * each node. 656 * The order of the node is given by the order of the array. This method makes no effort 657 * to find a good order; it only mechanically computes the size this order results in. 658 * 659 * @param dict the dictionary 660 * @param flatNodes the ordered array of nodes 661 * @return the same array it was passed. The nodes have been updated for address and size. 662 */ 663 private static ArrayList<Node> computeAddresses(FusionDictionary dict, 664 ArrayList<Node> flatNodes) { 665 // First get the worst sizes and offsets 666 for (Node n : flatNodes) setNodeMaximumSize(n); 667 final int offset = stackNodes(flatNodes); 668 669 MakedictLog.i("Compressing the array addresses. Original size : " + offset); 670 MakedictLog.i("(Recursively seen size : " + offset + ")"); 671 672 int passes = 0; 673 boolean changesDone = false; 674 do { 675 changesDone = false; 676 for (Node n : flatNodes) { 677 final int oldNodeSize = n.mCachedSize; 678 final boolean changed = computeActualNodeSize(n, dict); 679 final int newNodeSize = n.mCachedSize; 680 if (oldNodeSize < newNodeSize) throw new RuntimeException("Increased size ?!"); 681 changesDone |= changed; 682 } 683 stackNodes(flatNodes); 684 ++passes; 685 if (passes > MAX_PASSES) throw new RuntimeException("Too many passes - probably a bug"); 686 } while (changesDone); 687 688 final Node lastNode = flatNodes.get(flatNodes.size() - 1); 689 MakedictLog.i("Compression complete in " + passes + " passes."); 690 MakedictLog.i("After address compression : " 691 + (lastNode.mCachedAddress + lastNode.mCachedSize)); 692 693 return flatNodes; 694 } 695 696 /** 697 * Sanity-checking method. 698 * 699 * This method checks an array of node for juxtaposition, that is, it will do 700 * nothing if each node's cached address is actually the previous node's address 701 * plus the previous node's size. 702 * If this is not the case, it will throw an exception. 703 * 704 * @param array the array node to check 705 */ 706 private static void checkFlatNodeArray(ArrayList<Node> array) { 707 int offset = 0; 708 int index = 0; 709 for (Node n : array) { 710 if (n.mCachedAddress != offset) { 711 throw new RuntimeException("Wrong address for node " + index 712 + " : expected " + offset + ", got " + n.mCachedAddress); 713 } 714 ++index; 715 offset += n.mCachedSize; 716 } 717 } 718 719 /** 720 * Helper method to write a variable-size address to a file. 721 * 722 * @param buffer the buffer to write to. 723 * @param index the index in the buffer to write the address to. 724 * @param address the address to write. 725 * @return the size in bytes the address actually took. 726 */ 727 private static int writeVariableAddress(final byte[] buffer, int index, final int address) { 728 switch (getByteSize(address)) { 729 case 1: 730 buffer[index++] = (byte)address; 731 return 1; 732 case 2: 733 buffer[index++] = (byte)(0xFF & (address >> 8)); 734 buffer[index++] = (byte)(0xFF & address); 735 return 2; 736 case 3: 737 buffer[index++] = (byte)(0xFF & (address >> 16)); 738 buffer[index++] = (byte)(0xFF & (address >> 8)); 739 buffer[index++] = (byte)(0xFF & address); 740 return 3; 741 case 0: 742 return 0; 743 default: 744 throw new RuntimeException("Address " + address + " has a strange size"); 745 } 746 } 747 748 private static byte makeCharGroupFlags(final CharGroup group, final int groupAddress, 749 final int childrenOffset) { 750 byte flags = 0; 751 if (group.mChars.length > 1) flags |= FLAG_HAS_MULTIPLE_CHARS; 752 if (group.mFrequency >= 0) { 753 flags |= FLAG_IS_TERMINAL; 754 } 755 if (null != group.mChildren) { 756 switch (getByteSize(childrenOffset)) { 757 case 1: 758 flags |= FLAG_GROUP_ADDRESS_TYPE_ONEBYTE; 759 break; 760 case 2: 761 flags |= FLAG_GROUP_ADDRESS_TYPE_TWOBYTES; 762 break; 763 case 3: 764 flags |= FLAG_GROUP_ADDRESS_TYPE_THREEBYTES; 765 break; 766 default: 767 throw new RuntimeException("Node with a strange address"); 768 } 769 } 770 if (null != group.mShortcutTargets) { 771 if (DBG && 0 == group.mShortcutTargets.size()) { 772 throw new RuntimeException("0-sized shortcut list must be null"); 773 } 774 flags |= FLAG_HAS_SHORTCUT_TARGETS; 775 } 776 if (null != group.mBigrams) { 777 if (DBG && 0 == group.mBigrams.size()) { 778 throw new RuntimeException("0-sized bigram list must be null"); 779 } 780 flags |= FLAG_HAS_BIGRAMS; 781 } 782 return flags; 783 } 784 785 /** 786 * Makes the flag value for a bigram. 787 * 788 * @param more whether there are more bigrams after this one. 789 * @param offset the offset of the bigram. 790 * @param bigramFrequency the frequency of the bigram, 0..255. 791 * @param unigramFrequency the unigram frequency of the same word, 0..255. 792 * @param word the second bigram, for debugging purposes 793 * @return the flags 794 */ 795 private static final int makeBigramFlags(final boolean more, final int offset, 796 int bigramFrequency, final int unigramFrequency, final String word) { 797 int bigramFlags = (more ? FLAG_ATTRIBUTE_HAS_NEXT : 0) 798 + (offset < 0 ? FLAG_ATTRIBUTE_OFFSET_NEGATIVE : 0); 799 switch (getByteSize(offset)) { 800 case 1: 801 bigramFlags |= FLAG_ATTRIBUTE_ADDRESS_TYPE_ONEBYTE; 802 break; 803 case 2: 804 bigramFlags |= FLAG_ATTRIBUTE_ADDRESS_TYPE_TWOBYTES; 805 break; 806 case 3: 807 bigramFlags |= FLAG_ATTRIBUTE_ADDRESS_TYPE_THREEBYTES; 808 break; 809 default: 810 throw new RuntimeException("Strange offset size"); 811 } 812 if (unigramFrequency > bigramFrequency) { 813 MakedictLog.e("Unigram freq is superior to bigram freq for \"" + word 814 + "\". Bigram freq is " + bigramFrequency + ", unigram freq for " 815 + word + " is " + unigramFrequency); 816 bigramFrequency = unigramFrequency; 817 } 818 // We compute the difference between 255 (which means probability = 1) and the 819 // unigram score. We split this into a number of discrete steps. 820 // Now, the steps are numbered 0~15; 0 represents an increase of 1 step while 15 821 // represents an increase of 16 steps: a value of 15 will be interpreted as the median 822 // value of the 16th step. In all justice, if the bigram frequency is low enough to be 823 // rounded below the first step (which means it is less than half a step higher than the 824 // unigram frequency) then the unigram frequency itself is the best approximation of the 825 // bigram freq that we could possibly supply, hence we should *not* include this bigram 826 // in the file at all. 827 // until this is done, we'll write 0 and slightly overestimate this case. 828 // In other words, 0 means "between 0.5 step and 1.5 step", 1 means "between 1.5 step 829 // and 2.5 steps", and 15 means "between 15.5 steps and 16.5 steps". So we want to 830 // divide our range [unigramFreq..MAX_TERMINAL_FREQUENCY] in 16.5 steps to get the 831 // step size. Then we compute the start of the first step (the one where value 0 starts) 832 // by adding half-a-step to the unigramFrequency. From there, we compute the integer 833 // number of steps to the bigramFrequency. One last thing: we want our steps to include 834 // their lower bound and exclude their higher bound so we need to have the first step 835 // start at exactly 1 unit higher than floor(unigramFreq + half a step). 836 // Note : to reconstruct the score, the dictionary reader will need to divide 837 // MAX_TERMINAL_FREQUENCY - unigramFreq by 16.5 likewise to get the value of the step, 838 // and add (discretizedFrequency + 0.5 + 0.5) times this value to get the best 839 // approximation. (0.5 to get the first step start, and 0.5 to get the middle of the 840 // step pointed by the discretized frequency. 841 final float stepSize = 842 (MAX_TERMINAL_FREQUENCY - unigramFrequency) / (1.5f + MAX_BIGRAM_FREQUENCY); 843 final float firstStepStart = 1 + unigramFrequency + (stepSize / 2.0f); 844 final int discretizedFrequency = (int)((bigramFrequency - firstStepStart) / stepSize); 845 // If the bigram freq is less than half-a-step higher than the unigram freq, we get -1 846 // here. The best approximation would be the unigram freq itself, so we should not 847 // include this bigram in the dictionary. For now, register as 0, and live with the 848 // small over-estimation that we get in this case. TODO: actually remove this bigram 849 // if discretizedFrequency < 0. 850 final int finalBigramFrequency = discretizedFrequency > 0 ? discretizedFrequency : 0; 851 bigramFlags += finalBigramFrequency & FLAG_ATTRIBUTE_FREQUENCY; 852 return bigramFlags; 853 } 854 855 /** 856 * Makes the 2-byte value for options flags. 857 */ 858 private static final int makeOptionsValue(final FusionDictionary dictionary) { 859 final DictionaryOptions options = dictionary.mOptions; 860 final boolean hasBigrams = dictionary.hasBigrams(); 861 return (options.mFrenchLigatureProcessing ? FRENCH_LIGATURE_PROCESSING_FLAG : 0) 862 + (options.mGermanUmlautProcessing ? GERMAN_UMLAUT_PROCESSING_FLAG : 0) 863 + (hasBigrams ? CONTAINS_BIGRAMS_FLAG : 0); 864 } 865 866 /** 867 * Makes the flag value for a shortcut. 868 * 869 * @param more whether there are more attributes after this one. 870 * @param frequency the frequency of the attribute, 0..15 871 * @return the flags 872 */ 873 private static final int makeShortcutFlags(final boolean more, final int frequency) { 874 return (more ? FLAG_ATTRIBUTE_HAS_NEXT : 0) + (frequency & FLAG_ATTRIBUTE_FREQUENCY); 875 } 876 877 /** 878 * Write a node to memory. The node is expected to have its final position cached. 879 * 880 * This can be an empty map, but the more is inside the faster the lookups will be. It can 881 * be carried on as long as nodes do not move. 882 * 883 * @param dict the dictionary the node is a part of (for relative offsets). 884 * @param buffer the memory buffer to write to. 885 * @param node the node to write. 886 * @return the address of the END of the node. 887 */ 888 private static int writePlacedNode(FusionDictionary dict, byte[] buffer, Node node) { 889 int index = node.mCachedAddress; 890 891 final int groupCount = node.mData.size(); 892 final int countSize = getGroupCountSize(node); 893 if (1 == countSize) { 894 buffer[index++] = (byte)groupCount; 895 } else if (2 == countSize) { 896 // We need to signal 2-byte size by setting the top bit of the MSB to 1, so 897 // we | 0x80 to do this. 898 buffer[index++] = (byte)((groupCount >> 8) | 0x80); 899 buffer[index++] = (byte)(groupCount & 0xFF); 900 } else { 901 throw new RuntimeException("Strange size from getGroupCountSize : " + countSize); 902 } 903 int groupAddress = index; 904 for (int i = 0; i < groupCount; ++i) { 905 CharGroup group = node.mData.get(i); 906 if (index != group.mCachedAddress) throw new RuntimeException("Bug: write index is not " 907 + "the same as the cached address of the group : " 908 + index + " <> " + group.mCachedAddress); 909 groupAddress += GROUP_FLAGS_SIZE + getGroupCharactersSize(group); 910 // Sanity checks. 911 if (DBG && group.mFrequency > MAX_TERMINAL_FREQUENCY) { 912 throw new RuntimeException("A node has a frequency > " + MAX_TERMINAL_FREQUENCY 913 + " : " + group.mFrequency); 914 } 915 if (group.mFrequency >= 0) groupAddress += GROUP_FREQUENCY_SIZE; 916 final int childrenOffset = null == group.mChildren 917 ? NO_CHILDREN_ADDRESS : group.mChildren.mCachedAddress - groupAddress; 918 byte flags = makeCharGroupFlags(group, groupAddress, childrenOffset); 919 buffer[index++] = flags; 920 index = CharEncoding.writeCharArray(group.mChars, buffer, index); 921 if (group.hasSeveralChars()) { 922 buffer[index++] = GROUP_CHARACTERS_TERMINATOR; 923 } 924 if (group.mFrequency >= 0) { 925 buffer[index++] = (byte) group.mFrequency; 926 } 927 final int shift = writeVariableAddress(buffer, index, childrenOffset); 928 index += shift; 929 groupAddress += shift; 930 931 // Write shortcuts 932 if (null != group.mShortcutTargets) { 933 final int indexOfShortcutByteSize = index; 934 index += GROUP_SHORTCUT_LIST_SIZE_SIZE; 935 groupAddress += GROUP_SHORTCUT_LIST_SIZE_SIZE; 936 final Iterator<WeightedString> shortcutIterator = group.mShortcutTargets.iterator(); 937 while (shortcutIterator.hasNext()) { 938 final WeightedString target = shortcutIterator.next(); 939 ++groupAddress; 940 int shortcutFlags = makeShortcutFlags(shortcutIterator.hasNext(), 941 target.mFrequency); 942 buffer[index++] = (byte)shortcutFlags; 943 final int shortcutShift = CharEncoding.writeString(buffer, index, target.mWord); 944 index += shortcutShift; 945 groupAddress += shortcutShift; 946 } 947 final int shortcutByteSize = index - indexOfShortcutByteSize; 948 if (shortcutByteSize > 0xFFFF) { 949 throw new RuntimeException("Shortcut list too large"); 950 } 951 buffer[indexOfShortcutByteSize] = (byte)(shortcutByteSize >> 8); 952 buffer[indexOfShortcutByteSize + 1] = (byte)(shortcutByteSize & 0xFF); 953 } 954 // Write bigrams 955 if (null != group.mBigrams) { 956 final Iterator<WeightedString> bigramIterator = group.mBigrams.iterator(); 957 while (bigramIterator.hasNext()) { 958 final WeightedString bigram = bigramIterator.next(); 959 final CharGroup target = 960 FusionDictionary.findWordInTree(dict.mRoot, bigram.mWord); 961 final int addressOfBigram = target.mCachedAddress; 962 final int unigramFrequencyForThisWord = target.mFrequency; 963 ++groupAddress; 964 final int offset = addressOfBigram - groupAddress; 965 int bigramFlags = makeBigramFlags(bigramIterator.hasNext(), offset, 966 bigram.mFrequency, unigramFrequencyForThisWord, bigram.mWord); 967 buffer[index++] = (byte)bigramFlags; 968 final int bigramShift = writeVariableAddress(buffer, index, Math.abs(offset)); 969 index += bigramShift; 970 groupAddress += bigramShift; 971 } 972 } 973 974 } 975 if (index != node.mCachedAddress + node.mCachedSize) throw new RuntimeException( 976 "Not the same size : written " 977 + (index - node.mCachedAddress) + " bytes out of a node that should have " 978 + node.mCachedSize + " bytes"); 979 return index; 980 } 981 982 /** 983 * Dumps a collection of useful statistics about a node array. 984 * 985 * This prints purely informative stuff, like the total estimated file size, the 986 * number of nodes, of character groups, the repartition of each address size, etc 987 * 988 * @param nodes the node array. 989 */ 990 private static void showStatistics(ArrayList<Node> nodes) { 991 int firstTerminalAddress = Integer.MAX_VALUE; 992 int lastTerminalAddress = Integer.MIN_VALUE; 993 int size = 0; 994 int charGroups = 0; 995 int maxGroups = 0; 996 int maxRuns = 0; 997 for (Node n : nodes) { 998 if (maxGroups < n.mData.size()) maxGroups = n.mData.size(); 999 for (CharGroup cg : n.mData) { 1000 ++charGroups; 1001 if (cg.mChars.length > maxRuns) maxRuns = cg.mChars.length; 1002 if (cg.mFrequency >= 0) { 1003 if (n.mCachedAddress < firstTerminalAddress) 1004 firstTerminalAddress = n.mCachedAddress; 1005 if (n.mCachedAddress > lastTerminalAddress) 1006 lastTerminalAddress = n.mCachedAddress; 1007 } 1008 } 1009 if (n.mCachedAddress + n.mCachedSize > size) size = n.mCachedAddress + n.mCachedSize; 1010 } 1011 final int[] groupCounts = new int[maxGroups + 1]; 1012 final int[] runCounts = new int[maxRuns + 1]; 1013 for (Node n : nodes) { 1014 ++groupCounts[n.mData.size()]; 1015 for (CharGroup cg : n.mData) { 1016 ++runCounts[cg.mChars.length]; 1017 } 1018 } 1019 1020 MakedictLog.i("Statistics:\n" 1021 + " total file size " + size + "\n" 1022 + " " + nodes.size() + " nodes\n" 1023 + " " + charGroups + " groups (" + ((float)charGroups / nodes.size()) 1024 + " groups per node)\n" 1025 + " first terminal at " + firstTerminalAddress + "\n" 1026 + " last terminal at " + lastTerminalAddress + "\n" 1027 + " Group stats : max = " + maxGroups); 1028 for (int i = 0; i < groupCounts.length; ++i) { 1029 MakedictLog.i(" " + i + " : " + groupCounts[i]); 1030 } 1031 MakedictLog.i(" Character run stats : max = " + maxRuns); 1032 for (int i = 0; i < runCounts.length; ++i) { 1033 MakedictLog.i(" " + i + " : " + runCounts[i]); 1034 } 1035 } 1036 1037 /** 1038 * Dumps a FusionDictionary to a file. 1039 * 1040 * This is the public entry point to write a dictionary to a file. 1041 * 1042 * @param destination the stream to write the binary data to. 1043 * @param dict the dictionary to write. 1044 * @param version the version of the format to write, currently either 1 or 2. 1045 */ 1046 public static void writeDictionaryBinary(final OutputStream destination, 1047 final FusionDictionary dict, final int version) 1048 throws IOException, UnsupportedFormatException { 1049 1050 // Addresses are limited to 3 bytes, but since addresses can be relative to each node, the 1051 // structure itself is not limited to 16MB. However, if it is over 16MB deciding the order 1052 // of the nodes becomes a quite complicated problem, because though the dictionary itself 1053 // does not have a size limit, each node must still be within 16MB of all its children and 1054 // parents. As long as this is ensured, the dictionary file may grow to any size. 1055 1056 if (version < MINIMUM_SUPPORTED_VERSION || version > MAXIMUM_SUPPORTED_VERSION) { 1057 throw new UnsupportedFormatException("Requested file format version " + version 1058 + ", but this implementation only supports versions " 1059 + MINIMUM_SUPPORTED_VERSION + " through " + MAXIMUM_SUPPORTED_VERSION); 1060 } 1061 1062 ByteArrayOutputStream headerBuffer = new ByteArrayOutputStream(256); 1063 1064 // The magic number in big-endian order. 1065 if (version >= FIRST_VERSION_WITH_HEADER_SIZE) { 1066 // Magic number for version 2+. 1067 headerBuffer.write((byte) (0xFF & (VERSION_2_MAGIC_NUMBER >> 24))); 1068 headerBuffer.write((byte) (0xFF & (VERSION_2_MAGIC_NUMBER >> 16))); 1069 headerBuffer.write((byte) (0xFF & (VERSION_2_MAGIC_NUMBER >> 8))); 1070 headerBuffer.write((byte) (0xFF & VERSION_2_MAGIC_NUMBER)); 1071 // Dictionary version. 1072 headerBuffer.write((byte) (0xFF & (version >> 8))); 1073 headerBuffer.write((byte) (0xFF & version)); 1074 } else { 1075 // Magic number for version 1. 1076 headerBuffer.write((byte) (0xFF & (VERSION_1_MAGIC_NUMBER >> 8))); 1077 headerBuffer.write((byte) (0xFF & VERSION_1_MAGIC_NUMBER)); 1078 // Dictionary version. 1079 headerBuffer.write((byte) (0xFF & version)); 1080 } 1081 // Options flags 1082 final int options = makeOptionsValue(dict); 1083 headerBuffer.write((byte) (0xFF & (options >> 8))); 1084 headerBuffer.write((byte) (0xFF & options)); 1085 if (version >= FIRST_VERSION_WITH_HEADER_SIZE) { 1086 final int headerSizeOffset = headerBuffer.size(); 1087 // Placeholder to be written later with header size. 1088 for (int i = 0; i < 4; ++i) { 1089 headerBuffer.write(0); 1090 } 1091 // Write out the options. 1092 for (final String key : dict.mOptions.mAttributes.keySet()) { 1093 final String value = dict.mOptions.mAttributes.get(key); 1094 CharEncoding.writeString(headerBuffer, key); 1095 CharEncoding.writeString(headerBuffer, value); 1096 } 1097 final int size = headerBuffer.size(); 1098 final byte[] bytes = headerBuffer.toByteArray(); 1099 // Write out the header size. 1100 bytes[headerSizeOffset] = (byte) (0xFF & (size >> 24)); 1101 bytes[headerSizeOffset + 1] = (byte) (0xFF & (size >> 16)); 1102 bytes[headerSizeOffset + 2] = (byte) (0xFF & (size >> 8)); 1103 bytes[headerSizeOffset + 3] = (byte) (0xFF & (size >> 0)); 1104 destination.write(bytes); 1105 } else { 1106 headerBuffer.writeTo(destination); 1107 } 1108 1109 headerBuffer.close(); 1110 1111 // Leave the choice of the optimal node order to the flattenTree function. 1112 MakedictLog.i("Flattening the tree..."); 1113 ArrayList<Node> flatNodes = flattenTree(dict.mRoot); 1114 1115 MakedictLog.i("Computing addresses..."); 1116 computeAddresses(dict, flatNodes); 1117 MakedictLog.i("Checking array..."); 1118 if (DBG) checkFlatNodeArray(flatNodes); 1119 1120 // Create a buffer that matches the final dictionary size. 1121 final Node lastNode = flatNodes.get(flatNodes.size() - 1); 1122 final int bufferSize =(lastNode.mCachedAddress + lastNode.mCachedSize); 1123 final byte[] buffer = new byte[bufferSize]; 1124 int index = 0; 1125 1126 MakedictLog.i("Writing file..."); 1127 int dataEndOffset = 0; 1128 for (Node n : flatNodes) { 1129 dataEndOffset = writePlacedNode(dict, buffer, n); 1130 } 1131 1132 if (DBG) showStatistics(flatNodes); 1133 1134 destination.write(buffer, 0, dataEndOffset); 1135 1136 destination.close(); 1137 MakedictLog.i("Done"); 1138 } 1139 1140 1141 // Input methods: Read a binary dictionary to memory. 1142 // readDictionaryBinary is the public entry point for them. 1143 1144 static final int[] characterBuffer = new int[MAX_WORD_LENGTH]; 1145 private static CharGroupInfo readCharGroup(final FusionDictionaryBufferInterface buffer, 1146 final int originalGroupAddress) { 1147 int addressPointer = originalGroupAddress; 1148 final int flags = buffer.readUnsignedByte(); 1149 ++addressPointer; 1150 final int characters[]; 1151 if (0 != (flags & FLAG_HAS_MULTIPLE_CHARS)) { 1152 int index = 0; 1153 int character = CharEncoding.readChar(buffer); 1154 addressPointer += CharEncoding.getCharSize(character); 1155 while (-1 != character) { 1156 characterBuffer[index++] = character; 1157 character = CharEncoding.readChar(buffer); 1158 addressPointer += CharEncoding.getCharSize(character); 1159 } 1160 characters = Arrays.copyOfRange(characterBuffer, 0, index); 1161 } else { 1162 final int character = CharEncoding.readChar(buffer); 1163 addressPointer += CharEncoding.getCharSize(character); 1164 characters = new int[] { character }; 1165 } 1166 final int frequency; 1167 if (0 != (FLAG_IS_TERMINAL & flags)) { 1168 ++addressPointer; 1169 frequency = buffer.readUnsignedByte(); 1170 } else { 1171 frequency = CharGroup.NOT_A_TERMINAL; 1172 } 1173 int childrenAddress = addressPointer; 1174 switch (flags & MASK_GROUP_ADDRESS_TYPE) { 1175 case FLAG_GROUP_ADDRESS_TYPE_ONEBYTE: 1176 childrenAddress += buffer.readUnsignedByte(); 1177 addressPointer += 1; 1178 break; 1179 case FLAG_GROUP_ADDRESS_TYPE_TWOBYTES: 1180 childrenAddress += buffer.readUnsignedShort(); 1181 addressPointer += 2; 1182 break; 1183 case FLAG_GROUP_ADDRESS_TYPE_THREEBYTES: 1184 childrenAddress += buffer.readUnsignedInt24(); 1185 addressPointer += 3; 1186 break; 1187 case FLAG_GROUP_ADDRESS_TYPE_NOADDRESS: 1188 default: 1189 childrenAddress = NO_CHILDREN_ADDRESS; 1190 break; 1191 } 1192 ArrayList<WeightedString> shortcutTargets = null; 1193 if (0 != (flags & FLAG_HAS_SHORTCUT_TARGETS)) { 1194 final int pointerBefore = buffer.position(); 1195 shortcutTargets = new ArrayList<WeightedString>(); 1196 buffer.readUnsignedShort(); // Skip the size 1197 while (true) { 1198 final int targetFlags = buffer.readUnsignedByte(); 1199 final String word = CharEncoding.readString(buffer); 1200 shortcutTargets.add(new WeightedString(word, 1201 targetFlags & FLAG_ATTRIBUTE_FREQUENCY)); 1202 if (0 == (targetFlags & FLAG_ATTRIBUTE_HAS_NEXT)) break; 1203 } 1204 addressPointer += buffer.position() - pointerBefore; 1205 } 1206 ArrayList<PendingAttribute> bigrams = null; 1207 if (0 != (flags & FLAG_HAS_BIGRAMS)) { 1208 bigrams = new ArrayList<PendingAttribute>(); 1209 while (true) { 1210 final int bigramFlags = buffer.readUnsignedByte(); 1211 ++addressPointer; 1212 final int sign = 0 == (bigramFlags & FLAG_ATTRIBUTE_OFFSET_NEGATIVE) ? 1 : -1; 1213 int bigramAddress = addressPointer; 1214 switch (bigramFlags & MASK_ATTRIBUTE_ADDRESS_TYPE) { 1215 case FLAG_ATTRIBUTE_ADDRESS_TYPE_ONEBYTE: 1216 bigramAddress += sign * buffer.readUnsignedByte(); 1217 addressPointer += 1; 1218 break; 1219 case FLAG_ATTRIBUTE_ADDRESS_TYPE_TWOBYTES: 1220 bigramAddress += sign * buffer.readUnsignedShort(); 1221 addressPointer += 2; 1222 break; 1223 case FLAG_ATTRIBUTE_ADDRESS_TYPE_THREEBYTES: 1224 final int offset = (buffer.readUnsignedByte() << 16) 1225 + buffer.readUnsignedShort(); 1226 bigramAddress += sign * offset; 1227 addressPointer += 3; 1228 break; 1229 default: 1230 throw new RuntimeException("Has bigrams with no address"); 1231 } 1232 bigrams.add(new PendingAttribute(bigramFlags & FLAG_ATTRIBUTE_FREQUENCY, 1233 bigramAddress)); 1234 if (0 == (bigramFlags & FLAG_ATTRIBUTE_HAS_NEXT)) break; 1235 } 1236 } 1237 return new CharGroupInfo(originalGroupAddress, addressPointer, flags, characters, frequency, 1238 childrenAddress, shortcutTargets, bigrams); 1239 } 1240 1241 /** 1242 * Reads and returns the char group count out of a buffer and forwards the pointer. 1243 */ 1244 private static int readCharGroupCount(final FusionDictionaryBufferInterface buffer) { 1245 final int msb = buffer.readUnsignedByte(); 1246 if (MAX_CHARGROUPS_FOR_ONE_BYTE_CHARGROUP_COUNT >= msb) { 1247 return msb; 1248 } else { 1249 return ((MAX_CHARGROUPS_FOR_ONE_BYTE_CHARGROUP_COUNT & msb) << 8) 1250 + buffer.readUnsignedByte(); 1251 } 1252 } 1253 1254 // The word cache here is a stopgap bandaid to help the catastrophic performance 1255 // of this method. Since it performs direct, unbuffered random access to the file and 1256 // may be called hundreds of thousands of times, the resulting performance is not 1257 // reasonable without some kind of cache. Thus: 1258 private static TreeMap<Integer, String> wordCache = new TreeMap<Integer, String>(); 1259 /** 1260 * Finds, as a string, the word at the address passed as an argument. 1261 * 1262 * @param buffer the buffer to read from. 1263 * @param headerSize the size of the header. 1264 * @param address the address to seek. 1265 * @return the word, as a string. 1266 */ 1267 private static String getWordAtAddress(final FusionDictionaryBufferInterface buffer, 1268 final int headerSize, final int address) { 1269 final String cachedString = wordCache.get(address); 1270 if (null != cachedString) return cachedString; 1271 final int originalPointer = buffer.position(); 1272 buffer.position(headerSize); 1273 final int count = readCharGroupCount(buffer); 1274 int groupOffset = getGroupCountSize(count); 1275 final StringBuilder builder = new StringBuilder(); 1276 String result = null; 1277 1278 CharGroupInfo last = null; 1279 for (int i = count - 1; i >= 0; --i) { 1280 CharGroupInfo info = readCharGroup(buffer, groupOffset); 1281 groupOffset = info.mEndAddress; 1282 if (info.mOriginalAddress == address) { 1283 builder.append(new String(info.mCharacters, 0, info.mCharacters.length)); 1284 result = builder.toString(); 1285 break; // and return 1286 } 1287 if (hasChildrenAddress(info.mChildrenAddress)) { 1288 if (info.mChildrenAddress > address) { 1289 if (null == last) continue; 1290 builder.append(new String(last.mCharacters, 0, last.mCharacters.length)); 1291 buffer.position(last.mChildrenAddress + headerSize); 1292 groupOffset = last.mChildrenAddress + 1; 1293 i = buffer.readUnsignedByte(); 1294 last = null; 1295 continue; 1296 } 1297 last = info; 1298 } 1299 if (0 == i && hasChildrenAddress(last.mChildrenAddress)) { 1300 builder.append(new String(last.mCharacters, 0, last.mCharacters.length)); 1301 buffer.position(last.mChildrenAddress + headerSize); 1302 groupOffset = last.mChildrenAddress + 1; 1303 i = buffer.readUnsignedByte(); 1304 last = null; 1305 continue; 1306 } 1307 } 1308 buffer.position(originalPointer); 1309 wordCache.put(address, result); 1310 return result; 1311 } 1312 1313 /** 1314 * Reads a single node from a buffer. 1315 * 1316 * This methods reads the file at the current position. A node is fully expected to start at 1317 * the current position. 1318 * This will recursively read other nodes into the structure, populating the reverse 1319 * maps on the fly and using them to keep track of already read nodes. 1320 * 1321 * @param buffer the buffer, correctly positioned at the start of a node. 1322 * @param headerSize the size, in bytes, of the file header. 1323 * @param reverseNodeMap a mapping from addresses to already read nodes. 1324 * @param reverseGroupMap a mapping from addresses to already read character groups. 1325 * @return the read node with all his children already read. 1326 */ 1327 private static Node readNode(final FusionDictionaryBufferInterface buffer, final int headerSize, 1328 final Map<Integer, Node> reverseNodeMap, final Map<Integer, CharGroup> reverseGroupMap) 1329 throws IOException { 1330 final int nodeOrigin = buffer.position() - headerSize; 1331 final int count = readCharGroupCount(buffer); 1332 final ArrayList<CharGroup> nodeContents = new ArrayList<CharGroup>(); 1333 int groupOffset = nodeOrigin + getGroupCountSize(count); 1334 for (int i = count; i > 0; --i) { 1335 CharGroupInfo info = readCharGroup(buffer, groupOffset); 1336 ArrayList<WeightedString> shortcutTargets = info.mShortcutTargets; 1337 ArrayList<WeightedString> bigrams = null; 1338 if (null != info.mBigrams) { 1339 bigrams = new ArrayList<WeightedString>(); 1340 for (PendingAttribute bigram : info.mBigrams) { 1341 final String word = getWordAtAddress( 1342 buffer, headerSize, bigram.mAddress); 1343 bigrams.add(new WeightedString(word, bigram.mFrequency)); 1344 } 1345 } 1346 if (hasChildrenAddress(info.mChildrenAddress)) { 1347 Node children = reverseNodeMap.get(info.mChildrenAddress); 1348 if (null == children) { 1349 final int currentPosition = buffer.position(); 1350 buffer.position(info.mChildrenAddress + headerSize); 1351 children = readNode( 1352 buffer, headerSize, reverseNodeMap, reverseGroupMap); 1353 buffer.position(currentPosition); 1354 } 1355 nodeContents.add( 1356 new CharGroup(info.mCharacters, shortcutTargets, 1357 bigrams, info.mFrequency, children)); 1358 } else { 1359 nodeContents.add( 1360 new CharGroup(info.mCharacters, shortcutTargets, 1361 bigrams, info.mFrequency)); 1362 } 1363 groupOffset = info.mEndAddress; 1364 } 1365 final Node node = new Node(nodeContents); 1366 node.mCachedAddress = nodeOrigin; 1367 reverseNodeMap.put(node.mCachedAddress, node); 1368 return node; 1369 } 1370 1371 // TODO: move these methods (readUnigramsAndBigramsBinary(|Inner)) and an inner class (Position) 1372 // out of this class. 1373 private static class Position { 1374 public static final int NOT_READ_GROUPCOUNT = -1; 1375 1376 public int mAddress; 1377 public int mNumOfCharGroup; 1378 public int mPosition; 1379 public int mLength; 1380 1381 public Position(int address, int length) { 1382 mAddress = address; 1383 mLength = length; 1384 mNumOfCharGroup = NOT_READ_GROUPCOUNT; 1385 } 1386 } 1387 1388 /** 1389 * Tours all node without recursive call. 1390 */ 1391 private static void readUnigramsAndBigramsBinaryInner( 1392 final FusionDictionaryBufferInterface buffer, final int headerSize, 1393 final Map<Integer, String> words, final Map<Integer, Integer> frequencies, 1394 final Map<Integer, ArrayList<PendingAttribute>> bigrams) { 1395 int[] pushedChars = new int[MAX_WORD_LENGTH + 1]; 1396 1397 Stack<Position> stack = new Stack<Position>(); 1398 int index = 0; 1399 1400 Position initPos = new Position(headerSize, 0); 1401 stack.push(initPos); 1402 1403 while (!stack.empty()) { 1404 Position p = stack.peek(); 1405 1406 if (DBG) { 1407 MakedictLog.d("read: address=" + p.mAddress + ", numOfCharGroup=" + 1408 p.mNumOfCharGroup + ", position=" + p.mPosition + ", length=" + p.mLength); 1409 } 1410 1411 if (buffer.position() != p.mAddress) buffer.position(p.mAddress); 1412 if (index != p.mLength) index = p.mLength; 1413 1414 if (p.mNumOfCharGroup == Position.NOT_READ_GROUPCOUNT) { 1415 p.mNumOfCharGroup = readCharGroupCount(buffer); 1416 p.mAddress += getGroupCountSize(p.mNumOfCharGroup); 1417 p.mPosition = 0; 1418 } 1419 1420 CharGroupInfo info = readCharGroup(buffer, p.mAddress - headerSize); 1421 for (int i = 0; i < info.mCharacters.length; ++i) { 1422 pushedChars[index++] = info.mCharacters[i]; 1423 } 1424 p.mPosition++; 1425 1426 if (info.mFrequency != FusionDictionary.CharGroup.NOT_A_TERMINAL) { // found word 1427 words.put(info.mOriginalAddress, new String(pushedChars, 0, index)); 1428 frequencies.put(info.mOriginalAddress, info.mFrequency); 1429 if (info.mBigrams != null) bigrams.put(info.mOriginalAddress, info.mBigrams); 1430 } 1431 1432 if (p.mPosition == p.mNumOfCharGroup) { 1433 stack.pop(); 1434 } else { 1435 // the node has more groups. 1436 p.mAddress = buffer.position(); 1437 } 1438 1439 if (hasChildrenAddress(info.mChildrenAddress)) { 1440 Position childrenPos = new Position(info.mChildrenAddress + headerSize, index); 1441 stack.push(childrenPos); 1442 } 1443 } 1444 } 1445 1446 /** 1447 * Reads unigrams and bigrams from the binary file. 1448 * Doesn't make the memory representation of the dictionary. 1449 * 1450 * @param buffer the buffer to read. 1451 * @param words the map to store the address as a key and the word as a value. 1452 * @param frequencies the map to store the address as a key and the frequency as a value. 1453 * @param bigrams the map to store the address as a key and the list of address as a value. 1454 * @throws IOException 1455 * @throws UnsupportedFormatException 1456 */ 1457 public static void readUnigramsAndBigramsBinary(final FusionDictionaryBufferInterface buffer, 1458 final Map<Integer, String> words, final Map<Integer, Integer> frequencies, 1459 final Map<Integer, ArrayList<PendingAttribute>> bigrams) throws IOException, 1460 UnsupportedFormatException { 1461 // Read header 1462 final int version = checkFormatVersion(buffer); 1463 final int optionsFlags = buffer.readUnsignedShort(); 1464 final HashMap<String, String> options = new HashMap<String, String>(); 1465 final int headerSize = readHeader(buffer, options, version); 1466 1467 readUnigramsAndBigramsBinaryInner(buffer, headerSize, words, frequencies, bigrams); 1468 } 1469 1470 /** 1471 * Helper function to get the binary format version from the header. 1472 * @throws IOException 1473 */ 1474 private static int getFormatVersion(final FusionDictionaryBufferInterface buffer) 1475 throws IOException { 1476 final int magic_v1 = buffer.readUnsignedShort(); 1477 if (VERSION_1_MAGIC_NUMBER == magic_v1) return buffer.readUnsignedByte(); 1478 final int magic_v2 = (magic_v1 << 16) + buffer.readUnsignedShort(); 1479 if (VERSION_2_MAGIC_NUMBER == magic_v2) return buffer.readUnsignedShort(); 1480 return NOT_A_VERSION_NUMBER; 1481 } 1482 1483 /** 1484 * Helper function to get and validate the binary format version. 1485 * @throws UnsupportedFormatException 1486 * @throws IOException 1487 */ 1488 private static int checkFormatVersion(final FusionDictionaryBufferInterface buffer) 1489 throws IOException, UnsupportedFormatException { 1490 final int version = getFormatVersion(buffer); 1491 if (version < MINIMUM_SUPPORTED_VERSION || version > MAXIMUM_SUPPORTED_VERSION) { 1492 throw new UnsupportedFormatException("This file has version " + version 1493 + ", but this implementation does not support versions above " 1494 + MAXIMUM_SUPPORTED_VERSION); 1495 } 1496 return version; 1497 } 1498 1499 /** 1500 * Reads a header from a buffer. 1501 * @throws IOException 1502 * @throws UnsupportedFormatException 1503 */ 1504 private static int readHeader(final FusionDictionaryBufferInterface buffer, 1505 final HashMap<String, String> options, final int version) 1506 throws IOException, UnsupportedFormatException { 1507 final int headerSize; 1508 if (version < FIRST_VERSION_WITH_HEADER_SIZE) { 1509 headerSize = buffer.position(); 1510 } else { 1511 headerSize = buffer.readInt(); 1512 populateOptions(buffer, headerSize, options); 1513 buffer.position(headerSize); 1514 } 1515 1516 if (headerSize < 0) { 1517 throw new UnsupportedFormatException("header size can't be negative."); 1518 } 1519 return headerSize; 1520 } 1521 1522 /** 1523 * Reads options from a buffer and populate a map with their contents. 1524 * 1525 * The buffer is read at the current position, so the caller must take care the pointer 1526 * is in the right place before calling this. 1527 */ 1528 public static void populateOptions(final FusionDictionaryBufferInterface buffer, 1529 final int headerSize, final HashMap<String, String> options) { 1530 while (buffer.position() < headerSize) { 1531 final String key = CharEncoding.readString(buffer); 1532 final String value = CharEncoding.readString(buffer); 1533 options.put(key, value); 1534 } 1535 } 1536 // TODO: remove this method. 1537 public static void populateOptions(final ByteBuffer buffer, final int headerSize, 1538 final HashMap<String, String> options) { 1539 populateOptions(new ByteBufferWrapper(buffer), headerSize, options); 1540 } 1541 1542 /** 1543 * Reads a buffer and returns the memory representation of the dictionary. 1544 * 1545 * This high-level method takes a buffer and reads its contents, populating a 1546 * FusionDictionary structure. The optional dict argument is an existing dictionary to 1547 * which words from the buffer should be added. If it is null, a new dictionary is created. 1548 * 1549 * @param buffer the buffer to read. 1550 * @param dict an optional dictionary to add words to, or null. 1551 * @return the created (or merged) dictionary. 1552 */ 1553 public static FusionDictionary readDictionaryBinary( 1554 final FusionDictionaryBufferInterface buffer, final FusionDictionary dict) 1555 throws IOException, UnsupportedFormatException { 1556 // clear cache 1557 wordCache.clear(); 1558 1559 // Read header 1560 final int version = checkFormatVersion(buffer); 1561 final int optionsFlags = buffer.readUnsignedShort(); 1562 1563 final HashMap<String, String> options = new HashMap<String, String>(); 1564 final int headerSize = readHeader(buffer, options, version); 1565 1566 Map<Integer, Node> reverseNodeMapping = new TreeMap<Integer, Node>(); 1567 Map<Integer, CharGroup> reverseGroupMapping = new TreeMap<Integer, CharGroup>(); 1568 final Node root = readNode( 1569 buffer, headerSize, reverseNodeMapping, reverseGroupMapping); 1570 1571 FusionDictionary newDict = new FusionDictionary(root, 1572 new FusionDictionary.DictionaryOptions(options, 1573 0 != (optionsFlags & GERMAN_UMLAUT_PROCESSING_FLAG), 1574 0 != (optionsFlags & FRENCH_LIGATURE_PROCESSING_FLAG))); 1575 if (null != dict) { 1576 for (final Word w : dict) { 1577 newDict.add(w.mWord, w.mFrequency, w.mShortcutTargets); 1578 } 1579 for (final Word w : dict) { 1580 // By construction a binary dictionary may not have bigrams pointing to 1581 // words that are not also registered as unigrams so we don't have to avoid 1582 // them explicitly here. 1583 for (final WeightedString bigram : w.mBigrams) { 1584 newDict.setBigram(w.mWord, bigram.mWord, bigram.mFrequency); 1585 } 1586 } 1587 } 1588 1589 return newDict; 1590 } 1591 1592 // TODO: remove this method. 1593 public static FusionDictionary readDictionaryBinary(final ByteBuffer buffer, 1594 final FusionDictionary dict) throws IOException, UnsupportedFormatException { 1595 return readDictionaryBinary(new ByteBufferWrapper(buffer), dict); 1596 } 1597 1598 /** 1599 * Basic test to find out whether the file is a binary dictionary or not. 1600 * 1601 * Concretely this only tests the magic number. 1602 * 1603 * @param filename The name of the file to test. 1604 * @return true if it's a binary dictionary, false otherwise 1605 */ 1606 public static boolean isBinaryDictionary(final String filename) { 1607 FileInputStream inStream = null; 1608 try { 1609 final File file = new File(filename); 1610 inStream = new FileInputStream(file); 1611 final ByteBuffer buffer = inStream.getChannel().map( 1612 FileChannel.MapMode.READ_ONLY, 0, file.length()); 1613 final int version = getFormatVersion(new ByteBufferWrapper(buffer)); 1614 return (version >= MINIMUM_SUPPORTED_VERSION && version <= MAXIMUM_SUPPORTED_VERSION); 1615 } catch (FileNotFoundException e) { 1616 return false; 1617 } catch (IOException e) { 1618 return false; 1619 } finally { 1620 if (inStream != null) { 1621 try { 1622 inStream.close(); 1623 } catch (IOException e) { 1624 // do nothing 1625 } 1626 } 1627 } 1628 } 1629 1630 /** 1631 * Calculate bigram frequency from compressed value 1632 * 1633 * @see #makeBigramFlags 1634 * 1635 * @param unigramFrequency 1636 * @param bigramFrequency compressed frequency 1637 * @return approximate bigram frequency 1638 */ 1639 public static int reconstructBigramFrequency(final int unigramFrequency, 1640 final int bigramFrequency) { 1641 final float stepSize = (MAX_TERMINAL_FREQUENCY - unigramFrequency) 1642 / (1.5f + MAX_BIGRAM_FREQUENCY); 1643 final float resultFreqFloat = (float)unigramFrequency 1644 + stepSize * (bigramFrequency + 1.0f); 1645 return (int)resultFreqFloat; 1646 } 1647} 1648