LZSS.java |
1 /** 2 * Distribution License: 3 * JSword is free software; you can redistribute it and/or modify it under 4 * the terms of the GNU Lesser General Public License, version 2.1 or later 5 * as published by the Free Software Foundation. This program is distributed 6 * in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even 7 * the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 8 * See the GNU Lesser General Public License for more details. 9 * 10 * The License is available on the internet at: 11 * http://www.gnu.org/copyleft/lgpl.html 12 * or by writing to: 13 * Free Software Foundation, Inc. 14 * 59 Temple Place - Suite 330 15 * Boston, MA 02111-1307, USA 16 * 17 * © CrossWire Bible Society, 2007 - 2016 18 * 19 */ 20 package org.crosswire.common.compress; 21 22 import java.io.ByteArrayOutputStream; 23 import java.io.IOException; 24 import java.io.InputStream; 25 import java.util.Arrays; 26 27 /** 28 * The LZSS compression is a port of code as implemented for STEP. The following 29 * information gives the history of this implementation. 30 * 31 * <p> 32 * Compression Info, 10-11-95<br> 33 * Jeff Wheeler 34 * </p> 35 * 36 * <h2><u>Source of Algorithm</u></h2> 37 * 38 * <p> 39 * The compression algorithms used here are based upon the algorithms developed 40 * and published by Haruhiko Okumura in a paper entitled 41 * "Data Compression Algorithms of LARC and LHarc." This paper discusses three 42 * compression algorithms, LSZZ, LZARI, and LZHUF. LZSS is described as the 43 * "first" of these, and is described as providing moderate compression with 44 * good speed. LZARI is described as an improved LZSS, a combination of the LZSS 45 * algorithm with adaptive arithmetic compression. It is described as being 46 * slower than LZSS but with better compression. LZHUF (the basis of the common 47 * LHA compression program) was included in the paper, however, a free usage 48 * license was not included. 49 * </p> 50 * 51 * <p> 52 * The following are copies of the statements included at the beginning of each 53 * source code listing that was supplied in the working paper. 54 * </p> 55 * 56 * <blockquote>LZSS, dated 4/6/89, marked as "Use, distribute and modify this 57 * program freely."</blockquote> 58 * 59 * <blockquote>LZARI, dated 4/7/89, marked as "Use, distribute and modify this 60 * program freely."</blockquote> 61 * 62 * <blockquote>LZHUF, dated 11/20/88, written by Haruyasu Yoshizaki, translated 63 * by Haruhiko Okumura on 4/7/89. Not expressly marked as redistributable or 64 * modifiable.</blockquote> 65 * 66 * <p> 67 * Since both LZSS and LZARI are marked as "use, distribute and modify freely" 68 * we have felt at liberty basing our compression algorithm on either of these. 69 * </p> 70 * 71 * <h2><u>Selection of Algorithm</u></h2> 72 * 73 * <p> 74 * Working samples of three possible compression algorithms are supplied in 75 * Okumura's paper. Which should be used? 76 * </p> 77 * 78 * <p> 79 * LZSS is the fastest at decompression, but does not generated as small a 80 * compressed file as the other methods. The other two methods provided, 81 * perhaps, a 15% improvement in compression. Or, put another way, on a 100K 82 * file, LZSS might compress it to 50K while the others might approach 40-45K. 83 * For STEP purposes, it was decided that decoding speed was of more importance 84 * than tighter compression. For these reasons, the first compression algorithm 85 * implemented is the LZSS algorithm. 86 * </p> 87 * 88 * <h2><u>About LZSS Encoding</u></h2> 89 * 90 * <p> 91 * (adapted from Haruhiko Okumura's paper) 92 * </p> 93 * 94 * <p> 95 * This scheme was proposed by Ziv and Lempel [1]. A slightly modified version 96 * is described by Storer and Szymanski [2]. An implementation using a binary 97 * tree has been proposed by Bell [3]. 98 * </p> 99 * 100 * The algorithm is quite simple. 101 * <ol> 102 * <li>Keep a ring buffer which initially contains all space characters.</li> 103 * <li>Read several letters from the file to the buffer.</li> 104 * <li>Search the buffer for the longest string that matches the letters just 105 * read, and send its length and position into the buffer.</li> 106 * </ol> 107 * 108 * <p> 109 * If the ring buffer is 4096 bytes, the position can be stored in 12 bits. If 110 * the length is represented in 4 bits, the <position, length> pair is two bytes 111 * long. If the longest match is no more than two characters, then just one 112 * character is sent without encoding. The process starts again with the next 113 * character. An extra bit is sent each time to tell the decoder whether the 114 * next item is a character of a <position, length> pair. 115 * </p> 116 * 117 * <p> 118 * [1] J. Ziv and A. Lempel, IEEE Transactions IT-23, 337-343 (1977).<br> 119 * [2] J. A. Storer and T. G. Szymanski, J. ACM, 29, 928-951 (1982).<br> 120 * [3] T.C. Gell, IEEE Transactions COM-34, 1176-1182 (1986). 121 * </p> 122 * 123 * Regarding this port to Java and not the original code, the following license 124 * applies: 125 * 126 * @see gnu.lgpl.License The GNU Lesser General Public License for details. 127 * @author DM Smith 128 */ 129 public class LZSS extends AbstractCompressor { 130 /** 131 * Create an LZSS that is capable of transforming the input. 132 * 133 * @param input 134 * to compress or uncompress. 135 */ 136 public LZSS(InputStream input) { 137 super(input); 138 ringBuffer = new byte[RING_SIZE + MAX_STORE_LENGTH - 1]; 139 dad = new short[RING_SIZE + 1]; 140 leftSon = new short[RING_SIZE + 1]; 141 rightSon = new short[RING_SIZE + 257]; 142 } 143 144 /* 145 * (non-Javadoc) 146 * 147 * @see org.crosswire.common.compress.Compressor#compress() 148 */ 149 public ByteArrayOutputStream compress() throws IOException { 150 out = new ByteArrayOutputStream(BUF_SIZE); 151 152 short i; // an iterator 153 short r; // node number in the binary tree 154 short s; // position in the ring buffer 155 short len; // length of initial string 156 short lastMatchLength; // length of last match 157 short codeBufPos; // position in the output buffer 158 byte[] codeBuff = new byte[17]; // the output buffer 159 byte mask; // bit mask for byte 0 of out input 160 byte c; // character read from string 161 162 // Start with a clean tree. 163 initTree(); 164 165 // codeBuff[0] works as eight flags. A "1" represents that the 166 // unit is an unencoded letter (1 byte), and a "0" represents 167 // that the next unit is a <position,length> pair (2 bytes). 168 // 169 // codeBuff[1..16] stores eight units of code. Since the best 170 // we can do is store eight <position,length> pairs, at most 16 171 // bytes are needed to store this. 172 // 173 // This is why the maximum size of the code buffer is 17 bytes. 174 codeBuff[0] = 0; 175 codeBufPos = 1; 176 177 // Mask iterates over the 8 bits in the code buffer. The first 178 // character ends up being stored in the low bit. 179 // 180 // bit 8 7 6 5 4 3 2 1 181 // | | 182 // | first sequence in code buffer 183 // | 184 // last sequence in code buffer 185 mask = 1; 186 187 s = 0; 188 r = RING_SIZE - MAX_STORE_LENGTH; 189 190 // Initialize the ring buffer with spaces... 191 192 // Note that the last MAX_STORE_LENGTH bytes of the ring buffer are not 193 // filled. 194 // This is because those MAX_STORE_LENGTH bytes will be filled in 195 // immediately 196 // with bytes from the input stream. 197 Arrays.fill(ringBuffer, 0, r, (byte) ' '); 198 199 // Read MAX_STORE_LENGTH bytes into the last MAX_STORE_LENGTH bytes of 200 // the ring buffer. 201 // 202 // This function loads the buffer with up to MAX_STORE_LENGTH characters 203 // and returns 204 // the actual amount loaded. 205 int readResult = input.read(ringBuffer, r, MAX_STORE_LENGTH); 206 207 // Make sure there is something to be compressed. 208 if (readResult <= 0) { 209 return out; 210 } 211 212 len = (short) readResult; 213 214 // Insert the MAX_STORE_LENGTH strings, each of which begins with one or 215 // more 216 // 'space' characters. Note the order in which these strings 217 // are inserted. This way, degenerate trees will be less likely 218 // to occur. 219 for (i = 1; i <= MAX_STORE_LENGTH; i++) { 220 insertNode((short) (r - i)); 221 } 222 223 // Finally, insert the whole string just read. The 224 // member variables matchLength and matchPosition are set. 225 insertNode(r); 226 227 // Now that we're preloaded, continue till done. 228 do { 229 230 // matchLength may be spuriously long near the end of text. 231 if (matchLength > len) { 232 matchLength = len; 233 } 234 235 // Is it cheaper to store this as a single character? If so, make it 236 // so. 237 if (matchLength < THRESHOLD) { 238 // Send one character. Remember that codeBuff[0] is the 239 // set of flags for the next eight items. 240 matchLength = 1; 241 codeBuff[0] |= mask; 242 codeBuff[codeBufPos++] = ringBuffer[r]; 243 } else { 244 // Otherwise, we do indeed have a string that can be stored 245 // compressed to save space. 246 247 // The next 16 bits need to contain the position (12 bits) 248 // and the length (4 bits). 249 codeBuff[codeBufPos++] = (byte) matchPosition; 250 codeBuff[codeBufPos++] = (byte) (((matchPosition >> 4) & 0xF0) | (matchLength - THRESHOLD)); 251 } 252 253 // Shift the mask one bit to the left so that it will be ready 254 // to store the new bit. 255 mask <<= 1; 256 257 // If the mask is now 0, then we know that we have a full set 258 // of flags and items in the code buffer. These need to be 259 // output. 260 if (mask == 0) { 261 // codeBuff is the buffer of characters to be output. 262 // codeBufPos is the number of characters it contains. 263 out.write(codeBuff, 0, codeBufPos); 264 265 // Reset for next buffer... 266 codeBuff[0] = 0; 267 codeBufPos = 1; 268 mask = 1; 269 } 270 271 lastMatchLength = matchLength; 272 273 // Delete old strings and read new bytes... 274 for (i = 0; i < lastMatchLength; i++) { 275 276 // Get next character... 277 readResult = input.read(); 278 if (readResult == -1) { 279 break; 280 } 281 c = (byte) readResult; 282 283 // Delete "old strings" 284 deleteNode(s); 285 286 // Put this character into the ring buffer. 287 // 288 // The original comment here says "If the position is near 289 // the end of the buffer, extend the buffer to make 290 // string comparison easier." 291 // 292 // That's a little misleading, because the "end" of the 293 // buffer is really what we consider to be the "beginning" 294 // of the buffer, that is, positions 0 through MAX_STORE_LENGTH. 295 // 296 // The idea is that the front end of the buffer is duplicated 297 // into the back end so that when you're looking at characters 298 // at the back end of the buffer, you can index ahead (beyond 299 // the normal end of the buffer) and see the characters 300 // that are at the front end of the buffer without having 301 // to adjust the index. 302 // 303 // That is... 304 // 305 // 1234xxxxxxxxxxxxxxxxxxxxxxxxxxxxx1234 306 // | | | 307 // position 0 end of buffer | 308 // | 309 // duplicate of front of buffer 310 ringBuffer[s] = c; 311 312 if (s < MAX_STORE_LENGTH - 1) { 313 ringBuffer[s + RING_SIZE] = c; 314 } 315 316 // Increment the position, and wrap around when we're at 317 // the end. Note that this relies on RING_SIZE being a power of 318 // 2. 319 s = (short) ((s + 1) & RING_WRAP); 320 r = (short) ((r + 1) & RING_WRAP); 321 322 // Register the string that is found in 323 // ringBuffer[r..r + MAX_STORE_LENGTH - 1]. 324 insertNode(r); 325 } 326 327 // If we didn't quit because we hit the lastMatchLength, 328 // then we must have quit because we ran out of characters 329 // to process. 330 while (i++ < lastMatchLength) { 331 deleteNode(s); 332 333 s = (short) ((s + 1) & RING_WRAP); 334 r = (short) ((r + 1) & RING_WRAP); 335 336 // Note that len hitting 0 is the key that causes the 337 // do...while() to terminate. This is the only place 338 // within the loop that len is modified. 339 // 340 // Its original value is MAX_STORE_LENGTH (or a number less than 341 // MAX_STORE_LENGTH for 342 // short strings). 343 if (--len != 0) { 344 insertNode(r); /* buffer may not be empty. */ 345 } 346 } 347 348 // End of do...while() loop. Continue processing until there 349 // are no more characters to be compressed. The variable 350 // "len" is used to signal this condition. 351 } while (len > 0); 352 353 // There could still be something in the output buffer. Send it now. 354 if (codeBufPos > 1) { 355 // codeBuff is the encoded string to send. 356 // codeBufPos is the number of characters. 357 out.write(codeBuff, 0, codeBufPos); 358 } 359 360 return out; 361 } 362 363 /* 364 * (non-Javadoc) 365 * 366 * @see org.crosswire.common.compress.Compressor#uncompress() 367 */ 368 public ByteArrayOutputStream uncompress() throws IOException { 369 return uncompress(BUF_SIZE); 370 } 371 372 /* 373 * (non-Javadoc) 374 * 375 * @see org.crosswire.common.compress.Compressor#uncompress(int) 376 */ 377 public ByteArrayOutputStream uncompress(int expectedSize) throws IOException { 378 out = new ByteArrayOutputStream(expectedSize); 379 380 byte[] c = new byte[MAX_STORE_LENGTH]; // an array of chars 381 byte flags; // 8 bits of flags 382 383 // Initialize the ring buffer with a common string. 384 // 385 // Note that the last MAX_STORE_LENGTH bytes of the ring buffer are not 386 // filled. 387 // r is a nodeNumber 388 int r = RING_SIZE - MAX_STORE_LENGTH; 389 Arrays.fill(ringBuffer, 0, r, (byte) ' '); 390 391 flags = 0; 392 int flagCount = 0; // which flag we're on 393 394 while (true) { 395 // If there are more bits of interest in this flag, then 396 // shift that next interesting bit into the 1's position. 397 // 398 // If this flag has been exhausted, the next byte must be a flag. 399 if (flagCount > 0) { 400 flags = (byte) (flags >> 1); 401 flagCount--; 402 } else { 403 // Next byte must be a flag. 404 int readResult = input.read(); 405 if (readResult == -1) { 406 break; 407 } 408 409 flags = (byte) (readResult & 0xFF); 410 411 // Set the flag counter. While at first it might appear 412 // that this should be an 8 since there are 8 bits in the 413 // flag, it should really be a 7 because the shift must 414 // be performed 7 times in order to see all 8 bits. 415 flagCount = 7; 416 } 417 418 // If the low order bit of the flag is now set, then we know 419 // that the next byte is a single, unencoded character. 420 if ((flags & 1) != 0) { 421 if (input.read(c, 0, 1) != 1) { 422 break; 423 } 424 425 out.write(c[0]); 426 427 // Add to buffer, and increment to next spot. Wrap at end. 428 ringBuffer[r] = c[0]; 429 r = (short) ((r + 1) & RING_WRAP); 430 } else { 431 // Otherwise, we know that the next two bytes are a 432 // <position,length> pair. The position is in 12 bits and 433 // the length is in 4 bits. 434 if (input.read(c, 0, 2) != 2) { 435 break; 436 } 437 438 // Convert these two characters into the position and 439 // length in the ringBuffer. Note that the length is always at 440 // least 441 // THRESHOLD, which is why we're able to get a length 442 // of 18 out of only 4 bits. 443 short pos = (short) ((c[0] & 0xFF) | ((c[1] & 0xF0) << 4)); 444 short len = (short) ((c[1] & 0x0F) + THRESHOLD); 445 446 // There are now "len" characters at position "pos" in 447 // the ring buffer that can be pulled out. Note that 448 // len is never more than MAX_STORE_LENGTH. 449 for (int k = 0; k < len; k++) { 450 c[k] = ringBuffer[(pos + k) & RING_WRAP]; 451 452 // Add to buffer, and increment to next spot. Wrap at end. 453 ringBuffer[r] = c[k]; 454 r = (r + 1) & RING_WRAP; 455 } 456 457 // Add the "len" characters to the output stream. 458 out.write(c, 0, len); 459 } 460 } 461 return out; 462 } 463 464 /** 465 * Initializes the tree nodes to "empty" states. 466 */ 467 private void initTree() { 468 // For i = 0 to RING_SIZE - 1, rightSon[i] and leftSon[i] will be the 469 // right 470 // and left children of node i. These nodes need not be 471 // initialized. However, for debugging purposes, it is nice to 472 // have them initialized. Since this is only used for compression 473 // (not decompression), I don't mind spending the time to do it. 474 // 475 // For the same range of i, dad[i] is the parent of node i. 476 // These are initialized to a known value that can represent 477 // a "not used" state. 478 // For i = 0 to 255, rightSon[RING_SIZE + i + 1] is the root of the tree 479 // for strings that begin with the character i. This is why 480 // the right child array is larger than the left child array. 481 // These are also initialized to a "not used" state. 482 // 483 // Note that there are 256 of these, one for each of the possible 484 // 256 characters. 485 Arrays.fill(dad, 0, dad.length, NOT_USED); 486 Arrays.fill(leftSon, 0, leftSon.length, NOT_USED); 487 Arrays.fill(rightSon, 0, rightSon.length, NOT_USED); 488 } 489 490 /** 491 * Inserts a string from the ring buffer into one of the trees. It loads the 492 * match position and length member variables for the longest match. 493 * 494 * <p> 495 * The string to be inserted is identified by the parameter pos, A full 496 * MAX_STORE_LENGTH bytes are inserted. So, ringBuffer[pos ... 497 * pos+MAX_STORE_LENGTH-1] are inserted. 498 * </p> 499 * 500 * <p> 501 * If the matched length is exactly MAX_STORE_LENGTH, then an old node is 502 * removed in favor of the new one (because the old one will be deleted 503 * sooner). 504 * </p> 505 * 506 * @param pos 507 * plays a dual role. It is used as both a position in the ring 508 * buffer and also as a tree node. ringBuffer[pos] defines a 509 * character that is used to identify a tree node. 510 */ 511 private void insertNode(short pos) { 512 assert pos >= 0 && pos < RING_SIZE; 513 514 int cmp = 1; 515 short key = pos; 516 517 // The last 256 entries in rightSon contain the root nodes for 518 // strings that begin with a letter. Get an index for the 519 // first letter in this string. 520 short p = (short) (RING_SIZE + 1 + (ringBuffer[key] & 0xFF)); 521 assert p > RING_SIZE; 522 523 // Set the left and right tree nodes for this position to "not used." 524 leftSon[pos] = NOT_USED; 525 rightSon[pos] = NOT_USED; 526 527 // Haven't matched anything yet. 528 matchLength = 0; 529 530 while (true) { 531 if (cmp >= 0) { 532 if (rightSon[p] != NOT_USED) { 533 p = rightSon[p]; 534 } else { 535 rightSon[p] = pos; 536 dad[pos] = p; 537 return; 538 } 539 } else { 540 if (leftSon[p] != NOT_USED) { 541 p = leftSon[p]; 542 } else { 543 leftSon[p] = pos; 544 dad[pos] = p; 545 return; 546 } 547 } 548 549 // Should we go to the right or the left to look for the 550 // next match? 551 short i = 0; 552 for (i = 1; i < MAX_STORE_LENGTH; i++) { 553 cmp = (ringBuffer[key + i] & 0xFF) - (ringBuffer[p + i] & 0xFF); 554 if (cmp != 0) { 555 break; 556 } 557 } 558 559 if (i > matchLength) { 560 matchPosition = p; 561 matchLength = i; 562 563 if (i >= MAX_STORE_LENGTH) { 564 break; 565 } 566 } 567 } 568 569 dad[pos] = dad[p]; 570 leftSon[pos] = leftSon[p]; 571 rightSon[pos] = rightSon[p]; 572 573 dad[leftSon[p]] = pos; 574 dad[rightSon[p]] = pos; 575 576 if (rightSon[dad[p]] == p) { 577 rightSon[dad[p]] = pos; 578 } else { 579 leftSon[dad[p]] = pos; 580 } 581 582 // Remove "p" 583 dad[p] = NOT_USED; 584 } 585 586 /** 587 * Remove a node from the tree. 588 * 589 * @param node 590 * the node to remove 591 */ 592 private void deleteNode(short node) { 593 assert node >= 0 && node < (RING_SIZE + 1); 594 595 short q; 596 597 if (dad[node] == NOT_USED) { 598 // not in tree, nothing to do 599 return; 600 } 601 602 if (rightSon[node] == NOT_USED) { 603 q = leftSon[node]; 604 } else if (leftSon[node] == NOT_USED) { 605 q = rightSon[node]; 606 } else { 607 q = leftSon[node]; 608 if (rightSon[q] != NOT_USED) { 609 do { 610 q = rightSon[q]; 611 } while (rightSon[q] != NOT_USED); 612 613 rightSon[dad[q]] = leftSon[q]; 614 dad[leftSon[q]] = dad[q]; 615 leftSon[q] = leftSon[node]; 616 dad[leftSon[node]] = q; 617 } 618 619 rightSon[q] = rightSon[node]; 620 dad[rightSon[node]] = q; 621 } 622 623 dad[q] = dad[node]; 624 625 if (rightSon[dad[node]] == node) { 626 rightSon[dad[node]] = q; 627 } else { 628 leftSon[dad[node]] = q; 629 } 630 631 dad[node] = NOT_USED; 632 } 633 634 /** 635 * This is the size of the ring buffer. It is set to 4K. It is important to 636 * note that a position within the ring buffer requires 12 bits. 637 */ 638 private static final short RING_SIZE = 4096; 639 640 /** 641 * This is used to determine the next position in the ring buffer, from 0 to 642 * RING_SIZE - 1. The idiom s = (s + 1) & RING_WRAP; will ensure this. This 643 * only works if RING_SIZE is a power of 2. Note this is slightly faster 644 * than the equivalent: s = (s + 1) % RING_SIZE; 645 */ 646 private static final short RING_WRAP = RING_SIZE - 1; 647 648 /** 649 * This is the maximum length of a character sequence that can be taken from 650 * the ring buffer. It is set to 18. Note that a length must be 3 before it 651 * is worthwhile to store a position/length pair, so the length can be 652 * encoded in only 4 bits. Or, put yet another way, it is not necessary to 653 * encode a length of 0-18, it is necessary to encode a length of 3-18, 654 * which requires 4 bits. 655 * <p> 656 * Note that the 12 bits used to store the position and the 4 bits used to 657 * store the length equal a total of 16 bits, or 2 bytes. 658 * </p> 659 */ 660 private static final int MAX_STORE_LENGTH = 18; 661 662 /** 663 * It takes 2 bytes to store an offset and a length. If a character sequence 664 * only requires 1 or 2 characters to store uncompressed, then it is better 665 * to store it uncompressed than as an offset into the ring buffer. 666 */ 667 private static final int THRESHOLD = 3; 668 669 /** 670 * Used to mark nodes as not used. 671 */ 672 private static final short NOT_USED = RING_SIZE; 673 674 /** 675 * A text buffer. It contains "nodes" of uncompressed text that can be 676 * indexed by position. That is, a substring of the ring buffer can be 677 * indexed by a position and a length. When decoding, the compressed text 678 * may contain a position in the ring buffer and a count of the number of 679 * bytes from the ring buffer that are to be moved into the uncompressed 680 * buffer. 681 * 682 * <p> 683 * This ring buffer is not maintained as part of the compressed text. 684 * Instead, it is reconstructed dynamically. That is, it starts out empty 685 * and gets built as the text is decompressed. 686 * </p> 687 * 688 * <p> 689 * The ring buffer contain RING_SIZE bytes, with an additional 690 * MAX_STORE_LENGTH - 1 bytes to facilitate string comparison. 691 * </p> 692 */ 693 private byte[] ringBuffer; 694 695 /** 696 * The position in the ring buffer. Used by insertNode. 697 */ 698 private short matchPosition; 699 700 /** 701 * The number of characters in the ring buffer at matchPosition that match a 702 * given string. Used by insertNode. 703 */ 704 private short matchLength; 705 706 /** 707 * leftSon, rightSon, and dad are the Japanese way of referring to a tree 708 * structure. The dad is the parent and it has a right and left son (child). 709 * 710 * <p> 711 * For i = 0 to RING_SIZE-1, rightSon[i] and leftSon[i] will be the right 712 * and left children of node i. 713 * </p> 714 * 715 * <p> 716 * For i = 0 to RING_SIZE-1, dad[i] is the parent of node i. 717 * </p> 718 * 719 * <p> 720 * For i = 0 to 255, rightSon[RING_SIZE + i + 1] is the root of the tree for 721 * strings that begin with the character i. Note that this requires one byte 722 * characters. 723 * </p> 724 * 725 * <p> 726 * These nodes store values of 0...(RING_SIZE-1). Memory requirements can be 727 * reduces by using 2-byte integers instead of full 4-byte integers (for 728 * 32-bit applications). Therefore, these are defined as "shorts." 729 * </p> 730 */ 731 private short[] dad; 732 private short[] leftSon; 733 private short[] rightSon; 734 735 /** 736 * The output stream containing the result. 737 */ 738 private ByteArrayOutputStream out; 739 } 740