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