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