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