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