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