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