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