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