Multiple names: PART 3, ARC PART 3
FILE INFORMATION
FILENAME(S):
• PART 3<br>• ARC PART 3
FILE TYPE(S): DEL, SEQ
FILE SIZE: 19.7K
FIRST SEEN: 2025-11-30 18:12:26
APPEARS ON: 2 disk(s)
FILE HASH
d3d77a30b8e0ef2503c2ad5ffe0d34611c4f508f9c0f50b90b0bfbe04820e9cf
FOUND ON DISKS (2 DISKS)
| DISK TITLE | FILENAME | FILE TYPE | COLLECTION | TRACK | SECTOR | ACTIONS |
|---|---|---|---|---|---|---|
| SEA CHEST | PART 3 | DEL | Sailor, Ganheden | 33 | 4 | DOWNLOAD FILE |
| SEA CHEST | ARC PART 3 | SEQ | Sailor, Ganheden | 11 | 11 | DOWNLOAD FILE |
FILE CONTENT & ANALYSIS
00000000: 00 30 30 2C 38 30 0D 53 54 4F 52 45 44 20 49 4E |.00,80.STORED IN| 00000010: 20 D2 C1 CD 20 4D 41 59 20 4C 4F 4F 4B 20 53 4F | ... MAY LOOK SO| 00000020: 4D 45 54 48 49 4E 47 20 4C 49 4B 45 20 54 48 45 |METHING LIKE THE| 00000030: 20 46 4F 4C 4C 4F 57 49 4E 47 20 49 46 20 56 49 | FOLLOWING IF VI| 00000040: 45 57 45 44 20 57 49 54 48 20 54 48 45 20 4D 41 |EWED WITH THE MA| 00000050: 43 48 49 4E 45 0D 4C 41 4E 47 55 41 47 45 20 4D |CHINE.LANGUAGE M| 00000060: 4F 4E 49 54 4F 52 3A 0D 0D 20 20 20 20 20 20 20 |ONITOR:.. | 00000070: 20 20 20 20 20 20 20 20 2E 3A 32 30 30 30 20 30 | .:2000 0| 00000080: 30 20 30 30 20 30 30 20 30 30 20 30 30 20 30 30 |0 00 00 00 00 00| 00000090: 20 30 30 20 30 30 20 0D 20 20 20 20 20 20 20 20 | 00 00 . | 000000A0: 20 20 20 20 20 20 20 2E 3A 32 30 30 38 20 30 30 | .:2008 00| 000000B0: 20 30 30 20 46 46 20 46 46 20 46 46 20 46 46 20 | 00 FF FF FF FF | 000000C0: 46 46 20 30 30 0D 20 20 20 20 20 20 20 20 20 20 |FF 00. | 000000D0: 20 20 20 20 20 2E 3A 32 30 31 30 20 30 30 20 30 | .:2010 00 0| 000000E0: 30 20 30 30 20 30 30 20 30 30 20 30 30 20 30 30 |0 00 00 00 00 00| 000000F0: 20 30 30 20 0D 20 20 20 20 20 20 20 20 20 20 20 | 00 . | 00000100: 20 20 20 20 2E 3A 32 30 31 38 20 41 30 20 30 42 | .:2018 A0 0B| 00000110: 20 46 46 20 46 46 20 46 46 20 46 46 20 46 46 20 | FF FF FF FF FF | 00000120: 46 46 20 20 20 0D 20 20 20 20 20 20 20 20 20 20 |FF . | 00000130: 20 20 20 20 20 20 20 41 4E 44 20 53 4F 20 4F 4E | AND SO ON| 00000140: 2E 2E 2E 2E 0D 0D 20 20 20 20 20 20 20 20 20 20 |...... | 00000150: 20 20 20 20 20 D4 48 49 53 20 43 4F 55 4C 44 20 | .HIS COULD | 00000160: 42 45 20 53 54 4F 52 45 44 20 4F 4E 20 44 49 53 |BE STORED ON DIS| 00000170: 4B 20 41 53 20 54 48 45 20 53 45 51 55 45 4E 43 |K AS THE SEQUENC| 00000180: 45 3A 0D 0D 20 20 20 20 20 20 20 20 20 20 20 20 |E:.. | 00000190: 20 20 20 46 45 20 30 30 20 30 41 20 46 45 20 46 | FE 00 0A FE F| 000001A0: 46 20 30 35 20 46 45 20 30 30 20 30 39 20 41 30 |F 05 FE 00 09 A0| 000001B0: 20 30 42 20 46 45 20 46 46 20 30 36 0D 0D 20 20 | 0B FE FF 06.. | 000001C0: 20 20 D4 48 45 20 46 49 52 53 54 20 42 59 54 45 | .HE FIRST BYTE| 000001D0: 20 28 24 46 45 29 20 49 53 20 41 20 43 4F 4E 54 | ($FE) IS A CONT| 000001E0: 52 4F 4C 20 43 48 41 52 41 43 54 45 52 2E 20 D7 |ROL CHARACTER. .| 000001F0: 48 45 4E 20 54 48 45 20 55 4E 53 51 55 45 45 5A |HEN THE UNSQUEEZ| 00000200: 45 20 52 4F 55 54 49 4E 45 0D 45 4E 43 4F 55 4E |E ROUTINE.ENCOUN| 00000210: 54 45 52 53 20 41 20 4F 4E 45 20 4F 46 20 54 48 |TERS A ONE OF TH| 00000220: 45 53 45 20 49 54 20 47 45 54 53 20 54 48 45 20 |ESE IT GETS THE | 00000230: 4E 45 58 54 20 54 57 4F 20 43 48 41 52 41 43 54 |NEXT TWO CHARACT| 00000240: 45 52 53 20 41 4E 44 20 49 4E 54 45 52 50 52 45 |ERS AND INTERPRE| 00000250: 54 53 20 54 48 45 4D 20 41 53 0D 41 20 43 48 41 |TS THEM AS.A CHA| 00000260: 52 41 43 54 45 52 20 49 44 45 4E 54 49 46 49 45 |RACTER IDENTIFIE| 00000270: 52 20 41 4E 44 20 41 20 43 4F 55 4E 54 2E 20 D4 |R AND A COUNT. .| 00000280: 48 55 53 20 54 48 45 20 46 49 52 53 54 20 33 20 |HUS THE FIRST 3 | 00000290: 42 59 54 45 20 53 45 51 55 45 4E 43 45 20 49 53 |BYTE SEQUENCE IS| 000002A0: 0D 49 4E 54 45 52 50 52 45 54 45 44 20 41 53 20 |.INTERPRETED AS | 000002B0: 31 30 20 5A 45 52 4F 53 2C 20 54 48 45 20 4E 45 |10 ZEROS, THE NE| 000002C0: 58 54 20 33 20 42 59 54 45 20 53 45 51 55 45 4E |XT 3 BYTE SEQUEN| 000002D0: 43 45 20 41 53 20 35 20 46 46 27 53 20 41 4E 44 |CE AS 5 FF'S AND| 000002E0: 20 53 4F 20 20 4F 4E 2E 20 D7 48 45 4E 20 41 0D | SO ON. .HEN A.| 000002F0: 43 48 41 52 41 43 54 45 52 20 49 53 20 4E 4F 54 |CHARACTER IS NOT| 00000300: 20 52 45 50 45 41 54 45 44 2C 20 49 54 20 49 53 | REPEATED, IT IS| 00000310: 20 53 49 4D 50 4C 59 20 43 4F 44 45 44 20 44 49 | SIMPLY CODED DI| 00000320: 52 45 43 54 4C 59 20 54 4F 20 54 48 45 20 4F 55 |RECTLY TO THE OU| 00000330: 54 50 55 54 20 46 49 4C 45 2E 20 28 54 48 45 0D |TPUT FILE. (THE.| 00000340: 24 41 30 20 41 54 20 24 32 30 31 38 20 41 42 4F |$A0 AT $2018 ABO| 00000350: 56 45 29 20 C1 4E 44 20 53 4F 20 54 48 45 20 41 |VE) .ND SO THE A| 00000360: 42 4F 56 45 20 49 53 20 53 51 55 45 45 5A 45 44 |BOVE IS SQUEEZED| 00000370: 20 46 52 4F 4D 20 33 32 20 42 59 54 45 53 20 44 | FROM 32 BYTES D| 00000380: 4F 57 4E 20 54 4F 20 31 34 2E 0D 0D 20 20 20 20 |OWN TO 14... | 00000390: C4 41 54 41 42 41 53 45 20 50 52 4F 47 52 41 4D |.ATABASE PROGRAM| 000003A0: 53 20 4F 46 54 45 4E 20 53 41 43 52 49 46 49 43 |S OFTEN SACRIFIC| 000003B0: 45 20 44 49 53 4B 20 53 50 41 43 45 20 49 4E 20 |E DISK SPACE IN | 000003C0: 4F 52 44 45 52 20 54 4F 20 47 41 49 4E 20 53 50 |ORDER TO GAIN SP| 000003D0: 45 45 44 2E 0D D2 45 4C 41 54 49 56 45 20 46 49 |EED...ELATIVE FI| 000003E0: 4C 45 53 2C 20 46 4F 52 20 49 4E 53 54 41 4E 43 |LES, FOR INSTANC| 000003F0: 45 2C 20 53 54 4F 52 45 20 54 48 45 49 52 20 44 |E, STORE THEIR D| 00000400: 41 54 41 20 41 54 20 54 48 45 20 42 45 47 49 4E |ATA AT THE BEGIN| 00000410: 4E 49 4E 47 20 4F 46 20 45 41 43 48 20 52 45 43 |NING OF EACH REC| 00000420: 4F 52 44 2C 0D 41 4E 44 20 50 41 44 20 54 48 45 |ORD,.AND PAD THE| 00000430: 20 52 45 43 4F 52 44 20 57 49 54 48 20 5A 45 52 | RECORD WITH ZER| 00000440: 4F 53 2E 20 D3 49 4E 43 45 20 45 56 45 52 59 20 |OS. .INCE EVERY | 00000450: 52 45 43 4F 52 44 20 49 53 20 54 48 45 20 53 41 |RECORD IS THE SA| 00000460: 4D 45 20 4C 45 4E 47 54 48 2C 20 54 48 45 20 C4 |ME LENGTH, THE .| 00000470: CF D3 0D 43 41 4E 20 45 41 53 49 4C 59 20 43 41 |...CAN EASILY CA| 00000480: 4C 43 55 4C 41 54 45 20 57 48 45 52 45 20 45 41 |LCULATE WHERE EA| 00000490: 43 48 20 52 45 43 4F 52 44 20 53 54 41 52 54 53 |CH RECORD STARTS| 000004A0: 20 41 4E 44 20 54 48 55 53 20 52 41 4E 44 4F 4D | AND THUS RANDOM| 000004B0: 4C 59 20 53 4B 49 50 20 54 4F 20 41 4E 59 0D 52 |LY SKIP TO ANY.R| 000004C0: 45 43 4F 52 44 20 49 4E 20 54 48 45 20 46 49 4C |ECORD IN THE FIL| 000004D0: 45 2E 20 D4 C8 C5 20 CD C1 CE C1 C7 C5 D2 2C 20 |E. ... ......., | 000004E0: 41 4E 44 20 4F 54 48 45 52 20 44 41 54 41 42 41 |AND OTHER DATABA| 000004F0: 53 45 20 50 52 4F 47 52 41 4D 53 20 50 41 44 20 |SE PROGRAMS PAD | 00000500: 54 48 45 49 52 20 52 45 43 4F 52 44 53 0D 57 49 |THEIR RECORDS.WI| 00000510: 54 48 20 53 50 41 43 45 53 2E 20 C9 4E 20 45 49 |TH SPACES. .N EI| 00000520: 54 48 45 52 20 43 41 53 45 20 54 48 45 52 45 20 |THER CASE THERE | 00000530: 49 53 20 41 20 47 52 45 41 54 20 44 45 41 4C 20 |IS A GREAT DEAL | 00000540: 4F 46 20 53 50 41 43 45 20 54 4F 20 42 45 20 47 |OF SPACE TO BE G| 00000550: 41 49 4E 45 44 20 57 48 45 4E 0D 50 41 43 4B 49 |AINED WHEN.PACKI| 00000560: 4E 47 20 54 48 49 53 20 54 59 50 45 20 4F 46 20 |NG THIS TYPE OF | 00000570: 46 49 4C 45 2E 20 D7 45 20 48 41 56 45 20 53 45 |FILE. .E HAVE SE| 00000580: 45 4E 20 53 4F 4D 45 20 C4 C2 C1 D3 C5 20 C9 C9 |EN SOME ..... ..| 00000590: C9 20 46 49 4C 45 53 20 49 4E 20 45 58 43 45 53 |. FILES IN EXCES| 000005A0: 53 20 4F 46 20 31 0D 4D 45 47 41 42 59 54 45 20 |S OF 1.MEGABYTE | 000005B0: 27 43 52 55 4E 43 48 27 20 44 4F 57 4E 20 54 4F |'CRUNCH' DOWN TO| 000005C0: 20 4F 4E 4C 59 20 35 30 2C 30 30 30 20 43 48 41 | ONLY 50,000 CHA| 000005D0: 52 41 43 54 45 52 53 20 4F 52 20 53 4F 2E 20 CD |RACTERS OR SO. .| 000005E0: 4F 53 54 20 4F 46 20 54 48 49 53 20 49 53 20 44 |OST OF THIS IS D| 000005F0: 55 45 20 54 4F 0D 50 41 43 4B 49 4E 47 2E 0D 0D |UE TO.PACKING...| 00000600: 20 20 20 20 D4 48 45 52 45 20 49 53 20 4F 4E 45 | .HERE IS ONE| 00000610: 20 53 4C 49 47 48 54 20 50 52 4F 42 4C 45 4D 20 | SLIGHT PROBLEM | 00000620: 57 49 54 48 20 54 48 49 53 20 4D 45 54 48 4F 44 |WITH THIS METHOD| 00000630: 2E 20 D3 55 50 50 4F 53 45 20 59 4F 55 20 41 52 |. .UPPOSE YOU AR| 00000640: 45 20 55 53 49 4E 47 20 41 0D 5A 45 52 4F 2D 42 |E USING A.ZERO-B| 00000650: 59 54 45 20 41 53 20 54 48 45 20 43 4F 4E 54 52 |YTE AS THE CONTR| 00000660: 4F 4C 20 43 48 41 52 41 43 54 45 52 2E 20 C9 46 |OL CHARACTER. .F| 00000670: 20 41 20 53 45 51 55 45 4E 43 45 20 4F 46 20 4F | A SEQUENCE OF O| 00000680: 4E 4C 59 20 4F 4E 45 20 5A 45 52 4F 20 49 53 0D |NLY ONE ZERO IS.| 00000690: 45 4E 43 4F 55 4E 54 45 52 45 44 2C 20 59 4F 55 |ENCOUNTERED, YOU| 000006A0: 20 43 41 4E 4E 4F 54 20 43 4F 44 45 20 49 54 20 | CANNOT CODE IT | 000006B0: 54 4F 20 54 48 45 20 4F 55 54 50 55 54 20 46 49 |TO THE OUTPUT FI| 000006C0: 4C 45 20 53 49 4E 43 45 20 49 54 20 57 49 4C 4C |LE SINCE IT WILL| 000006D0: 20 42 45 20 49 4E 54 45 52 50 52 45 54 45 44 0D | BE INTERPRETED.| 000006E0: 41 53 20 41 20 43 4F 4E 54 52 4F 4C 20 43 48 41 |AS A CONTROL CHA| 000006F0: 52 41 43 54 45 52 2E 20 D9 4F 55 20 4D 55 53 54 |RACTER. .OU MUST| 00000700: 20 53 45 4E 44 20 41 20 54 48 52 45 45 20 42 59 | SEND A THREE BY| 00000710: 54 45 20 43 4F 4E 54 52 4F 4C 20 53 45 51 55 45 |TE CONTROL SEQUE| 00000720: 4E 43 45 20 54 4F 20 43 4F 44 45 20 54 48 45 0D |NCE TO CODE THE.| 00000730: 53 49 4E 47 4C 45 20 5A 45 52 4F 2E 20 C1 4E 20 |SINGLE ZERO. .N | 00000740: 45 58 41 4D 50 4C 45 20 4F 46 20 54 48 49 53 20 |EXAMPLE OF THIS | 00000750: 57 4F 55 4C 44 20 42 45 20 41 53 20 46 4F 4C 4C |WOULD BE AS FOLL| 00000760: 4F 57 53 3A 0D 0D 20 20 20 20 20 20 20 20 20 20 |OWS:.. | 00000770: 20 20 20 20 20 2E 3A 30 38 30 31 20 30 36 20 30 | .:0801 06 0| 00000780: 38 20 30 31 20 30 30 20 38 46 20 30 30 20 30 43 |8 01 00 8F 00 0C| 00000790: 20 30 38 20 0D 20 20 20 20 20 20 20 20 20 20 20 | 08 . | 000007A0: 20 20 20 20 2E 3A 30 38 30 39 20 30 32 20 30 30 | .:0809 02 00| 000007B0: 20 38 46 20 30 30 20 31 32 20 30 38 20 30 33 20 | 8F 00 12 08 03 | 000007C0: 30 30 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 |00. | 000007D0: 20 20 2E 3A 30 38 31 31 20 38 46 20 30 30 20 30 | .:0811 8F 00 0| 000007E0: 30 20 30 30 20 30 30 20 30 30 20 30 30 20 30 30 |0 00 00 00 00 00| 000007F0: 20 20 20 20 20 20 41 4E 44 20 53 4F 20 4F 4E 2E | AND SO ON.| 00000800: 2E 2E 2E 0D 0D 20 20 20 20 20 20 20 20 20 20 20 |..... | 00000810: 20 20 20 20 D4 48 49 53 20 57 4F 55 4C 44 20 42 | .HIS WOULD B| 00000820: 45 20 53 54 4F 52 45 44 20 4F 4E 20 44 49 53 4B |E STORED ON DISK| 00000830: 20 41 53 20 54 48 45 20 53 45 51 55 45 4E 43 45 | AS THE SEQUENCE| 00000840: 3A 0D 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 |:.. | 00000850: 20 20 30 36 20 30 38 20 30 31 20 30 30 20 30 30 | 06 08 01 00 00| 00000860: 20 30 31 20 38 46 20 30 30 20 30 30 20 30 31 20 | 01 8F 00 00 01 | 00000870: 30 43 20 30 38 20 30 32 20 30 30 20 30 30 20 30 |0C 08 02 00 00 0| 00000880: 31 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 20 |1. | 00000890: 20 38 46 20 30 30 20 30 30 20 30 31 20 31 32 20 | 8F 00 00 01 12 | 000008A0: 30 38 20 30 33 20 30 30 20 30 30 20 30 31 20 38 |08 03 00 00 01 8| 000008B0: 46 20 30 30 20 30 30 20 30 37 20 2E 2E 2E 2E 2E |F 00 00 07 .....| 000008C0: 0D 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 20 |.. | 000008D0: 20 D7 45 20 57 45 4E 54 20 46 52 4F 4D 20 32 34 | .E WENT FROM 24| 000008E0: 20 42 59 54 45 53 20 54 4F 20 33 30 21 20 CE 4F | BYTES TO 30! .O| 000008F0: 54 20 4D 55 43 48 20 4F 46 20 41 20 53 41 56 49 |T MUCH OF A SAVI| 00000900: 4E 47 53 2E 0D 0D 20 20 20 20 C9 54 20 49 53 20 |NGS... .T IS | 00000910: 42 45 43 41 55 53 45 20 4F 46 20 54 48 49 53 20 |BECAUSE OF THIS | 00000920: 50 52 4F 42 4C 45 4D 20 57 49 54 48 20 50 41 43 |PROBLEM WITH PAC| 00000930: 4B 49 4E 47 20 54 48 41 54 20 53 51 55 45 45 5A |KING THAT SQUEEZ| 00000940: 45 44 20 46 49 4C 45 53 20 41 52 45 0D 4F 43 43 |ED FILES ARE.OCC| 00000950: 41 53 49 4F 4E 41 4C 4C 59 20 53 48 4F 52 54 45 |ASIONALLY SHORTE| 00000960: 52 20 54 48 41 4E 20 54 48 45 49 52 20 53 51 55 |R THAN THEIR SQU| 00000970: 41 53 48 45 44 20 45 51 55 49 56 41 4C 45 4E 54 |ASHED EQUIVALENT| 00000980: 2E 0D 0D 20 20 20 20 C8 55 46 46 4D 41 4E 20 43 |... .UFFMAN C| 00000990: 4F 44 49 4E 47 20 49 53 20 53 4F 4D 45 57 48 41 |ODING IS SOMEWHA| 000009A0: 54 20 4D 4F 52 45 20 43 4F 4D 50 4C 45 58 2E 20 |T MORE COMPLEX. | 000009B0: C9 54 20 49 53 20 50 52 4F 42 41 42 4C 59 20 54 |.T IS PROBABLY T| 000009C0: 48 45 20 4D 4F 53 54 20 45 4C 45 47 41 4E 54 20 |HE MOST ELEGANT | 000009D0: 4F 46 0D 41 4C 4C 20 54 48 45 20 43 4F 4D 50 52 |OF.ALL THE COMPR| 000009E0: 45 53 53 49 4F 4E 20 4D 45 54 48 4F 44 53 20 55 |ESSION METHODS U| 000009F0: 53 45 44 20 41 4E 44 20 43 45 52 54 41 49 4E 4C |SED AND CERTAINL| 00000A00: 59 20 54 48 45 20 4D 4F 53 54 20 43 4F 4D 4D 4F |Y THE MOST COMMO| 00000A10: 4E 2E 20 C9 54 20 54 41 4B 45 53 0D 41 44 56 41 |N. .T TAKES.ADVA| 00000A20: 4E 54 41 47 45 20 4F 46 20 54 48 45 20 46 41 43 |NTAGE OF THE FAC| 00000A30: 54 20 54 48 41 54 20 53 4F 4D 45 20 43 48 41 52 |T THAT SOME CHAR| 00000A40: 41 43 54 45 52 53 20 41 52 45 20 55 53 45 44 20 |ACTERS ARE USED | 00000A50: 4D 4F 52 45 20 4F 46 54 45 4E 20 54 48 41 4E 20 |MORE OFTEN THAN | 00000A60: 4F 54 48 45 52 53 20 49 4E 0D 4D 4F 53 54 20 46 |OTHERS IN.MOST F| 00000A70: 49 4C 45 53 2E 20 D4 45 58 54 20 46 49 4C 45 53 |ILES. .EXT FILES| 00000A80: 20 43 4F 4E 54 41 49 4E 20 4D 41 4E 59 20 53 50 | CONTAIN MANY SP| 00000A90: 41 43 45 53 2C 20 41 4E 44 20 4C 45 54 54 45 52 |ACES, AND LETTER| 00000AA0: 53 20 4C 49 4B 45 20 41 2C 45 20 4F 52 20 43 20 |S LIKE A,E OR C | 00000AB0: 41 52 45 20 4D 55 43 48 0D 4D 4F 52 45 20 43 4F |ARE MUCH.MORE CO| 00000AC0: 4D 4D 4F 4E 20 54 48 41 4E 20 58 2C 20 5A 2C 20 |MMON THAN X, Z, | 00000AD0: 4F 52 20 51 2E 20 C7 52 41 50 48 49 43 53 20 46 |OR Q. .RAPHICS F| 00000AE0: 49 4C 45 53 20 43 4F 4E 54 41 49 4E 20 4D 41 4E |ILES CONTAIN MAN| 00000AF0: 59 20 5A 45 52 4F 53 20 4F 52 20 24 46 46 27 53 |Y ZEROS OR $FF'S| 00000B00: 20 41 4E 44 0D 4D 41 43 48 49 4E 45 20 4C 41 4E | AND.MACHINE LAN| 00000B10: 47 55 41 47 45 20 50 52 4F 47 52 41 4D 53 20 54 |GUAGE PROGRAMS T| 00000B20: 45 4E 44 20 54 4F 20 43 4F 4E 54 41 49 4E 20 4D |END TO CONTAIN M| 00000B30: 4F 52 45 20 CC C4 C1 27 53 20 41 4E 44 20 D3 D4 |ORE ...'S AND ..| 00000B40: C1 27 53 20 54 48 41 4E 20 C5 CF D2 27 53 20 4F |.'S THAN ...'S O| 00000B50: 52 0D D2 CF D2 27 53 2E 0D 0D 20 20 20 20 D3 55 |R....'S... .U| 00000B60: 50 50 4F 53 45 20 4E 4F 57 20 54 48 41 54 20 41 |PPOSE NOW THAT A| 00000B70: 20 46 49 4C 45 20 43 4F 4E 54 41 49 4E 53 20 4F | FILE CONTAINS O| 00000B80: 4E 4C 59 20 54 48 45 20 43 48 41 52 41 43 54 45 |NLY THE CHARACTE| 00000B90: 52 53 20 41 20 54 48 52 4F 55 47 48 20 5A 2E 20 |RS A THROUGH Z. | 00000BA0: D3 49 4E 43 45 0D 54 48 45 52 45 20 41 52 45 20 |.INCE.THERE ARE | 00000BB0: 4F 4E 4C 59 20 32 36 20 43 48 41 52 41 43 54 45 |ONLY 26 CHARACTE| 00000BC0: 52 53 20 55 53 45 44 2C 20 41 20 46 49 56 45 20 |RS USED, A FIVE | 00000BD0: 42 49 54 20 42 49 4E 41 52 59 20 4E 55 4D 42 45 |BIT BINARY NUMBE| 00000BE0: 52 2C 20 57 48 49 43 48 20 43 41 4E 20 54 41 4B |R, WHICH CAN TAK| 00000BF0: 45 20 4F 4E 0D 33 32 20 50 4F 53 53 49 42 4C 45 |E ON.32 POSSIBLE| 00000C00: 20 56 41 4C 55 45 53 2C 20 57 4F 55 4C 44 20 42 | VALUES, WOULD B| 00000C10: 45 20 4D 4F 52 45 20 54 48 41 4E 20 41 44 45 51 |E MORE THAN ADEQ| 00000C20: 55 41 54 45 20 54 4F 20 52 45 50 52 45 53 45 4E |UATE TO REPRESEN| 00000C30: 54 20 45 41 43 48 20 43 48 41 52 41 43 54 45 52 |T EACH CHARACTER| 00000C40: 2E 20 D7 45 0D 43 4F 55 4C 44 20 41 53 53 49 47 |. .E.COULD ASSIG| 00000C50: 4E 20 41 20 46 49 56 45 20 42 49 54 20 4E 55 4D |N A FIVE BIT NUM| 00000C60: 42 45 52 20 54 4F 20 45 41 43 48 20 4F 46 20 54 |BER TO EACH OF T| 00000C70: 48 45 20 43 48 41 52 41 43 54 45 52 53 20 41 20 |HE CHARACTERS A | 00000C80: 54 4F 20 5A 20 41 4E 44 20 47 41 49 4E 20 33 20 |TO Z AND GAIN 3 | 00000C90: 42 49 54 53 0D 50 45 52 20 43 48 41 52 41 43 54 |BITS.PER CHARACT| 00000CA0: 45 52 20 4F 52 20 33 37 2E 35 25 0D 0D 20 20 20 |ER OR 37.5%.. | 00000CB0: 20 C8 55 46 46 4D 41 4E 20 43 4F 44 49 4E 47 20 | .UFFMAN CODING | 00000CC0: 54 41 4B 45 53 20 54 48 49 53 20 4F 4E 45 20 53 |TAKES THIS ONE S| 00000CD0: 54 45 50 20 46 55 52 54 48 45 52 2E 0D 0D 20 20 |TEP FURTHER... | 00000CE0: 20 20 D3 55 50 50 4F 53 45 20 41 4C 53 4F 20 54 | .UPPOSE ALSO T| 00000CF0: 48 41 54 20 53 4F 4D 45 20 4F 46 20 54 48 45 20 |HAT SOME OF THE | 00000D00: 43 48 41 52 41 43 54 45 52 53 20 4F 43 43 55 52 |CHARACTERS OCCUR| 00000D10: 20 4D 55 43 48 20 4D 4F 52 45 20 4F 46 54 45 4E | MUCH MORE OFTEN| 00000D20: 20 49 4E 20 54 48 45 20 46 49 4C 45 0D 54 48 41 | IN THE FILE.THA| 00000D30: 4E 20 44 4F 20 4F 54 48 45 52 53 2E 20 D7 45 20 |N DO OTHERS. .E | 00000D40: 43 4F 55 4C 44 20 47 41 49 4E 20 45 56 45 4E 20 |COULD GAIN EVEN | 00000D50: 4D 4F 52 45 20 53 50 41 43 45 20 49 46 20 54 48 |MORE SPACE IF TH| 00000D60: 45 20 46 52 45 51 55 45 4E 54 4C 59 20 4F 43 43 |E FREQUENTLY OCC| 00000D70: 55 52 52 49 4E 47 0D 43 48 41 52 41 43 54 45 52 |URRING.CHARACTER| 00000D80: 53 20 57 45 52 45 20 41 53 53 49 47 4E 45 44 20 |S WERE ASSIGNED | 00000D90: 43 4F 44 45 53 20 4C 45 53 53 20 54 48 41 4E 20 |CODES LESS THAN | 00000DA0: 46 49 56 45 20 42 49 54 53 20 4C 4F 4E 47 2C 20 |FIVE BITS LONG, | 00000DB0: 41 4E 44 20 54 48 45 20 4C 45 53 53 20 46 52 45 |AND THE LESS FRE| 00000DC0: 51 55 45 4E 54 4C 59 0D 4F 43 43 55 52 52 49 4E |QUENTLY.OCCURRIN| 00000DD0: 47 20 20 43 48 41 52 41 43 54 45 52 53 20 57 45 |G CHARACTERS WE| 00000DE0: 52 45 20 20 41 53 53 49 47 4E 45 44 20 20 43 4F |RE ASSIGNED CO| 00000DF0: 44 45 53 20 20 54 48 41 54 20 57 45 52 45 20 46 |DES THAT WERE F| 00000E00: 49 56 45 20 4F 52 20 4D 4F 52 45 20 42 49 54 53 |IVE OR MORE BITS| 00000E10: 20 4C 4F 4E 47 2E 0D D4 48 45 20 C8 55 46 46 4D | LONG...HE .UFFM| 00000E20: 41 4E 20 41 4C 47 4F 52 49 54 48 4D 20 44 4F 45 |AN ALGORITHM DOE| 00000E30: 53 20 4A 55 53 54 20 54 48 41 54 2E 0D 0D 20 20 |S JUST THAT... | 00000E40: 20 20 D4 48 45 20 20 20 C8 55 46 46 4D 41 4E 20 | .HE .UFFMAN | 00000E50: 20 41 4C 47 4F 52 49 54 48 4D 20 43 4F 4E 56 45 | ALGORITHM CONVE| 00000E60: 52 54 53 20 46 49 58 45 44 20 4C 45 4E 47 54 48 |RTS FIXED LENGTH| 00000E70: 20 43 4F 44 45 53 20 28 38 20 42 49 54 20 43 48 | CODES (8 BIT CH| 00000E80: 41 52 41 43 54 45 52 53 29 20 49 4E 54 4F 0D 43 |ARACTERS) INTO.C| 00000E90: 4F 44 45 53 20 57 48 4F 53 45 20 4C 45 4E 47 54 |ODES WHOSE LENGT| 00000EA0: 48 20 49 4E 20 42 49 54 53 20 49 53 20 49 4E 56 |H IN BITS IS INV| 00000EB0: 45 52 53 45 4C 59 20 50 52 4F 50 4F 52 54 49 4F |ERSELY PROPORTIO| 00000EC0: 4E 41 4C 20 54 4F 20 54 48 45 49 52 20 50 52 4F |NAL TO THEIR PRO| 00000ED0: 42 41 42 49 4C 49 54 59 20 20 4F 46 0D 4F 43 43 |BABILITY OF.OCC| 00000EE0: 55 52 52 45 4E 43 45 20 49 4E 20 54 48 45 20 44 |URRENCE IN THE D| 00000EF0: 41 54 41 20 46 49 4C 45 2E 20 20 20 C6 4F 52 20 |ATA FILE. .OR | 00000F00: 45 58 41 4D 50 4C 45 2C 20 53 55 50 50 4F 53 45 |EXAMPLE, SUPPOSE| 00000F10: 20 59 4F 55 52 20 44 41 54 41 20 46 49 4C 45 20 | YOUR DATA FILE | 00000F20: 4C 4F 4F 4B 45 44 0D 53 4F 4D 45 54 48 49 4E 47 |LOOKED.SOMETHING| 00000F30: 20 4C 49 4B 45 20 54 48 49 53 3A 0D 0D 20 20 20 | LIKE THIS:.. | 00000F40: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00000F50: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 41 | A| 00000F60: 42 52 41 43 41 44 41 42 52 41 0D 0D 20 20 20 20 |BRACADABRA.. | 00000F70: 20 20 20 20 20 20 20 20 20 20 20 D4 48 45 20 43 | .HE C| 00000F80: 48 41 52 41 43 54 45 52 20 46 52 45 51 55 45 4E |HARACTER FREQUEN| 00000F90: 43 59 20 44 49 53 54 52 49 42 55 54 49 4F 4E 20 |CY DISTRIBUTION | 00000FA0: 49 53 20 41 53 20 46 4F 4C 4C 4F 57 53 3A 0D 0D |IS AS FOLLOWS:..| 00000FB0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00000FC0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00000FD0: 20 20 20 20 20 20 20 20 20 20 20 20 54 4F 54 41 | TOTA| 00000FE0: 4C 20 42 49 54 53 20 20 54 4F 54 41 4C 20 42 49 |L BITS TOTAL BI| 00000FF0: 54 53 0D 20 20 20 20 20 20 20 20 20 20 43 48 41 |TS. CHA| 00001000: 52 41 43 54 45 52 20 46 52 45 51 55 45 4E 43 59 |RACTER FREQUENCY| 00001010: 20 20 48 55 46 46 4D 41 4E 20 43 4F 44 45 20 55 | HUFFMAN CODE U| 00001020: 4E 53 51 55 45 45 5A 45 44 20 20 20 53 51 55 45 |NSQUEEZED SQUE| 00001030: 45 5A 45 44 0D 20 20 20 20 20 20 20 20 20 20 2D |EZED. -| 00001040: 2D 2D 2D 2D 2D 2D 2D 2D 20 2D 2D 2D 2D 2D 2D 2D |-------- -------| 00001050: 2D 2D 20 20 2D 2D 2D 2D 2D 2D 2D 2D 2D 2D 2D 2D |-- ------------| 00001060: 20 2D 2D 2D 2D 2D 2D 2D 2D 2D 2D 20 20 2D 2D 2D | ---------- ---| 00001070: 2D 2D 2D 2D 2D 2D 2D 2D 0D 20 20 20 20 20 20 20 |--------. | 00001080: 20 20 20 20 20 20 41 20 20 20 20 20 20 20 20 35 | A 5| 00001090: 20 20 20 20 20 20 20 20 20 20 30 20 20 20 20 20 | 0 | 000010A0: 20 20 20 20 20 38 20 2A 20 35 20 3D 20 34 30 20 | 8 * 5 = 40 | 000010B0: 20 31 20 2A 20 35 20 3D 20 35 0D 20 20 20 20 20 | 1 * 5 = 5. | 000010C0: 20 20 20 20 20 20 20 20 42 20 20 20 20 20 20 20 | B | 000010D0: 20 32 20 20 20 20 20 20 20 20 20 20 31 30 20 20 | 2 10 | 000010E0: 20 20 20 20 20 20 20 38 20 2A 20 32 20 3D 20 31 | 8 * 2 = 1| 000010F0: 36 20 20 32 20 2A 20 32 20 3D 20 34 0D 20 20 20 |6 2 * 2 = 4. | 00001100: 20 20 20 20 20 20 20 20 20 20 52 20 20 20 20 20 | R | 00001110: 20 20 20 32 20 20 20 20 20 20 20 20 20 20 31 31 | 2 11| 00001120: 31 20 20 20 20 20 20 20 20 38 20 2A 20 32 20 3D |1 8 * 2 =| 00001130: 20 31 36 20 20 33 20 2A 20 32 20 3D 20 36 0D 20 | 16 3 * 2 = 6. | 00001140: 20 20 20 20 20 20 20 20 20 20 20 20 43 20 20 20 | C | 00001150: 20 20 20 20 20 31 20 20 20 20 20 20 20 20 20 20 | 1 | 00001160: 31 31 30 30 20 20 20 20 20 20 20 38 20 2A 20 31 |1100 8 * 1| 00001170: 20 3D 20 20 38 20 20 34 20 2A 20 31 20 3D 20 34 | = 8 4 * 1 = 4| 00001180: 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 44 20 |. D | 00001190: 20 20 20 20 20 20 20 31 20 20 20 20 20 20 20 20 | 1 | 000011A0: 20 20 31 31 30 31 20 20 20 20 20 20 20 38 20 2A | 1101 8 *| 000011B0: 20 31 20 3D 20 20 38 20 20 34 20 2A 20 31 20 3D | 1 = 8 4 * 1 =| 000011C0: 20 34 0D 20 20 20 20 20 20 20 20 20 20 41 4C 4C | 4. ALL| 000011D0: 20 4F 54 48 45 52 53 20 20 30 20 20 20 20 20 20 | OTHERS 0 | 000011E0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2D | -| 000011F0: 2D 2D 2D 2D 2D 2D 2D 2D 2D 20 20 2D 2D 2D 2D 2D |--------- -----| 00001200: 2D 2D 2D 2D 2D 0D 20 20 20 20 20 20 20 20 20 20 |-----. | 00001210: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00001220: 20 20 20 20 54 4F 54 41 4C 53 3A 20 20 20 20 20 | TOTALS: | 00001230: 20 20 20 20 20 20 20 20 20 20 38 38 20 20 20 20 | 88 | 00001240: 20 20 20 20 20 32 33 0D 0D 20 20 20 20 20 20 20 | 23.. | 00001250: 20 20 20 20 20 20 20 20 D7 45 20 43 4F 55 4C 44 | .E COULD| 00001260: 20 52 45 50 52 45 53 45 4E 54 20 54 48 49 53 20 | REPRESENT THIS | 00001270: 49 4E 46 4F 52 4D 41 54 49 4F 4E 20 41 53 20 41 |INFORMATION AS A| 00001280: 20 42 49 4E 41 52 59 20 54 52 45 45 3A 0D 0D 20 | BINARY TREE:.. | 00001290: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 000012A0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 000012B0: 20 20 20 20 20 20 20 20 20 20 43 0D 20 20 20 20 | C. | 000012C0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 000012D0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 000012E0: 20 20 20 20 20 20 2F 0D 20 20 20 20 20 20 20 20 | /. | 000012F0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00001300: 20 20 20 20 20 20 20 20 41 20 20 20 20 42 20 20 | A B | 00001310: 20 2F 2D 2D 2D 2D 20 44 0D 20 20 20 20 20 20 20 | /---- D. | 00001320: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00001330: 20 20 20 20 20 20 20 20 2F 20 20 20 20 2F 20 20 | / / | 00001340: 20 2F 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 | /. | 00001350: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 52 4F | RO| 00001360: 4F 54 20 20 2D 2D 2D 20 2D 2D 2D 20 2D 2D 2D 20 |OT --- --- --- | 00001370: 52 0D 0D 20 20 20 20 D4 4F 20 47 45 54 20 54 48 |R.. .O GET TH| 00001380: 45 20 C8 55 46 46 4D 41 4E 20 43 4F 44 45 20 57 |E .UFFMAN CODE W| 00001390: 45 20 43 4F 44 45 20 41 20 30 20 42 49 54 20 45 |E CODE A 0 BIT E| 000013A0: 41 43 48 20 54 49 4D 45 20 57 45 20 54 52 41 56 |ACH TIME WE TRAV| 000013B0: 45 52 53 45 20 41 20 42 52 41 4E 43 48 20 54 4F |ERSE A BRANCH TO| 000013C0: 0D 54 48 45 20 4C 45 46 54 2C 20 41 4E 44 20 41 |.THE LEFT, AND A| 000013D0: 20 31 20 42 49 54 20 45 41 43 48 20 54 49 4D 45 | 1 BIT EACH TIME| 000013E0: 20 57 45 20 54 52 41 56 45 52 53 45 20 41 20 42 | WE TRAVERSE A B| 000013F0: 52 41 4E 43 48 20 54 4F 20 54 48 45 20 52 49 47 |RANCH TO THE RIG| 00001400: 48 54 2E 20 D4 48 55 53 20 54 48 45 0D 43 4F 44 |HT. .HUS THE.COD| 00001410: 45 53 20 41 52 45 20 47 45 4E 45 52 41 54 45 44 |ES ARE GENERATED| 00001420: 20 41 53 20 49 4E 20 54 48 45 20 54 41 42 4C 45 | AS IN THE TABLE| 00001430: 20 41 42 4F 56 45 20 41 4E 44 20 45 56 45 52 59 | ABOVE AND EVERY| 00001440: 20 43 48 41 52 41 43 54 45 52 20 47 45 54 53 20 | CHARACTER GETS | 00001450: 41 20 55 4E 49 51 55 45 0D 43 4F 44 45 2E 20 D4 |A UNIQUE.CODE. .| 00001460: 48 45 20 44 45 43 4F 4D 50 52 45 53 53 4F 52 20 |HE DECOMPRESSOR | 00001470: 53 49 4D 50 4C 59 20 53 54 41 52 54 53 20 41 54 |SIMPLY STARTS AT| 00001480: 20 54 48 45 20 52 4F 4F 54 2C 20 52 45 41 44 53 | THE ROOT, READS| 00001490: 20 54 48 45 20 53 51 55 45 45 5A 45 44 20 46 49 | THE SQUEEZED FI| 000014A0: 4C 45 20 4F 4E 45 0D 42 49 54 20 41 54 20 41 20 |LE ONE.BIT AT A | 000014B0: 54 49 4D 45 2C 20 41 4E 44 20 4D 4F 56 45 53 20 |TIME, AND MOVES | 000014C0: 54 48 52 4F 55 47 48 20 54 48 45 20 54 52 45 45 |THROUGH THE TREE| 000014D0: 20 55 4E 54 49 4C 20 49 54 20 52 45 41 43 48 45 | UNTIL IT REACHE| 000014E0: 53 20 41 20 54 45 52 4D 49 4E 41 4C 20 4E 4F 44 |S A TERMINAL NOD| 000014F0: 45 20 41 4E 44 0D 54 48 45 4E 20 53 45 4E 44 53 |E AND.THEN SENDS| 00001500: 20 54 48 45 20 43 48 41 52 41 43 54 45 52 20 49 | THE CHARACTER I| 00001510: 4E 20 54 48 41 54 20 50 4F 53 49 54 49 4F 4E 20 |N THAT POSITION | 00001520: 54 4F 20 54 48 45 20 4F 55 54 50 55 54 20 46 49 |TO THE OUTPUT FI| 00001530: 4C 45 2E 0D 0D 20 20 20 20 D4 48 45 20 4D 4F 53 |LE... .HE MOS| 00001540: 54 20 46 52 45 51 55 45 4E 54 4C 59 20 4F 43 43 |T FREQUENTLY OCC| 00001550: 55 52 52 49 4E 47 20 43 48 41 52 41 43 54 45 52 |URRING CHARACTER| 00001560: 53 20 41 52 45 20 4B 45 50 54 20 43 4C 4F 53 45 |S ARE KEPT CLOSE| 00001570: 53 54 20 54 4F 20 54 48 45 20 52 4F 4F 54 20 41 |ST TO THE ROOT A| 00001580: 4E 44 0D 54 48 55 53 20 48 41 56 45 20 53 48 4F |ND.THUS HAVE SHO| 00001590: 52 54 45 52 20 43 4F 44 45 53 2E 20 D4 48 4F 53 |RTER CODES. .HOS| 000015A0: 45 20 57 49 54 48 20 4C 4F 57 45 52 20 46 52 45 |E WITH LOWER FRE| 000015B0: 51 55 45 4E 43 49 45 53 20 4F 46 20 4F 43 43 55 |QUENCIES OF OCCU| 000015C0: 52 52 45 4E 43 45 20 41 52 45 20 4B 45 50 54 0D |RRENCE ARE KEPT.| 000015D0: 46 55 52 54 48 45 52 20 41 57 41 59 20 41 4E 44 |FURTHER AWAY AND| 000015E0: 20 47 45 54 20 4C 4F 4E 47 45 52 20 43 4F 44 45 | GET LONGER CODE| 000015F0: 53 2E 20 D4 48 45 20 52 45 53 55 4C 54 20 49 53 |S. .HE RESULT IS| 00001600: 20 4F 46 54 45 4E 20 41 20 46 49 4C 45 20 54 48 | OFTEN A FILE TH| 00001610: 41 54 20 49 53 0D 53 49 47 4E 49 46 49 43 41 4E |AT IS.SIGNIFICAN| 00001620: 54 4C 59 20 53 48 4F 52 54 45 52 20 54 48 41 4E |TLY SHORTER THAN| 00001630: 20 54 48 45 20 4F 52 49 47 49 4E 41 4C 2E 0D 0D | THE ORIGINAL...| 00001640: 20 20 20 20 D7 48 45 4E 20 41 4C 4C 20 42 59 54 | .HEN ALL BYT| 00001650: 45 53 20 4F 43 43 55 52 20 57 49 54 48 20 41 42 |ES OCCUR WITH AB| 00001660: 4F 55 54 20 54 48 45 20 53 41 4D 45 20 46 52 45 |OUT THE SAME FRE| 00001670: 51 55 45 4E 43 59 2C 20 41 53 20 49 4E 20 4D 41 |QUENCY, AS IN MA| 00001680: 43 48 49 4E 45 20 4C 41 4E 47 55 41 47 45 0D 50 |CHINE LANGUAGE.P| 00001690: 52 4F 47 52 41 4D 20 46 49 4C 45 53 2C 20 54 48 |ROGRAM FILES, TH| 000016A0: 45 4E 20 41 4C 4C 20 54 48 45 20 43 4F 44 45 53 |EN ALL THE CODES| 000016B0: 20 41 52 45 20 41 42 4F 55 54 20 54 48 45 20 53 | ARE ABOUT THE S| 000016C0: 41 4D 45 20 4C 45 4E 47 54 48 20 41 4E 44 20 4E |AME LENGTH AND N| 000016D0: 4F 54 20 4D 55 43 48 20 49 53 0D 47 41 49 4E 45 |OT MUCH IS.GAINE| 000016E0: 44 2E 20 C9 4E 20 46 41 43 54 2C 20 53 49 4E 43 |D. .N FACT, SINC| 000016F0: 45 20 54 48 45 20 44 45 2D 43 4F 44 49 4E 47 20 |E THE DE-CODING | 00001700: 49 4E 46 4F 52 4D 41 54 49 4F 4E 20 28 54 48 45 |INFORMATION (THE| 00001710: 20 54 52 45 45 29 20 4D 55 53 54 20 42 45 20 49 | TREE) MUST BE I| 00001720: 4E 43 4C 55 44 45 44 20 49 4E 0D 54 48 45 20 4F |NCLUDED IN.THE O| 00001730: 55 54 50 55 54 20 46 49 4C 45 2C 20 54 48 45 20 |UTPUT FILE, THE | 00001740: 52 45 53 55 4C 54 20 43 41 4E 20 4F 46 54 45 4E |RESULT CAN OFTEN| 00001750: 20 42 45 20 4C 4F 4E 47 45 52 2C 20 50 41 52 54 | BE LONGER, PART| 00001760: 49 43 55 4C 41 52 4C 59 20 4F 4E 20 53 48 4F 52 |ICULARLY ON SHOR| 00001770: 54 20 46 49 4C 45 53 2E 0D 0D 20 20 20 20 C6 4F |T FILES... .O| 00001780: 52 20 54 48 4F 53 45 20 4F 46 20 59 4F 55 20 54 |R THOSE OF YOU T| 00001790: 48 41 54 20 41 52 45 20 49 4E 54 45 52 45 53 54 |HAT ARE INTEREST| 000017A0: 45 44 20 49 4E 20 53 54 41 54 49 53 54 49 43 53 |ED IN STATISTICS| 000017B0: 2C 20 57 45 20 48 41 56 45 20 49 4E 43 4C 55 44 |, WE HAVE INCLUD| 000017C0: 45 44 20 41 20 53 4D 41 4C 4C 0D 55 54 49 4C 49 |ED A SMALL.UTILI| 000017D0: 54 59 20 50 52 4F 47 52 41 4D 20 57 49 54 48 20 |TY PROGRAM WITH | 000017E0: C1 D2 C3 20 54 48 41 54 20 41 4E 41 4C 59 5A 45 |... THAT ANALYZE| 000017F0: 53 20 54 48 45 20 46 52 45 51 55 45 4E 43 59 20 |S THE FREQUENCY | 00001800: 44 49 53 54 52 49 42 55 54 49 4F 4E 20 4F 46 20 |DISTRIBUTION OF | 00001810: 54 48 45 20 42 59 54 45 53 0D 49 4E 20 41 20 46 |THE BYTES.IN A F| 00001820: 49 4C 45 20 41 4E 44 20 47 52 41 50 48 49 43 41 |ILE AND GRAPHICA| 00001830: 4C 4C 59 20 44 49 53 50 4C 41 59 53 20 54 48 45 |LLY DISPLAYS THE| 00001840: 20 52 45 53 55 4C 54 53 2E 20 CF 4E 20 54 48 45 | RESULTS. .N THE| 00001850: 20 54 4F 50 20 50 4F 52 54 49 4F 4E 20 4F 46 20 | TOP PORTION OF | 00001860: 54 48 45 20 53 43 52 45 45 4E 0D 59 4F 55 20 57 |THE SCREEN.YOU W| 00001870: 49 4C 4C 20 53 45 45 20 54 48 45 20 46 52 45 51 |ILL SEE THE FREQ| 00001880: 55 45 4E 43 59 20 44 49 53 54 52 49 42 55 54 49 |UENCY DISTRIBUTI| 00001890: 4F 4E 20 4F 46 20 54 48 45 20 42 59 54 45 53 20 |ON OF THE BYTES | 000018A0: 49 4E 20 54 48 45 20 46 49 4C 45 2E 20 CF 4E 20 |IN THE FILE. .N | 000018B0: 54 48 45 20 42 4F 54 54 4F 4D 0D 50 4F 52 54 49 |THE BOTTOM.PORTI| 000018C0: 4F 4E 20 49 53 20 41 20 42 41 52 20 47 52 41 50 |ON IS A BAR GRAP| 000018D0: 48 20 52 45 50 52 45 53 45 4E 54 49 4E 47 20 54 |H REPRESENTING T| 000018E0: 48 45 20 4C 45 4E 47 54 48 53 20 4F 46 20 54 48 |HE LENGTHS OF TH| 000018F0: 45 20 C8 55 46 46 4D 41 4E 20 43 4F 44 45 53 20 |E .UFFMAN CODES | 00001900: 47 45 4E 45 52 41 54 45 44 0D 42 59 20 54 48 45 |GENERATED.BY THE| 00001910: 20 53 51 55 45 45 5A 45 20 41 4C 47 4F 52 49 54 | SQUEEZE ALGORIT| 00001920: 48 4D 2E 20 C1 20 48 55 46 46 4D 41 4E 20 43 4F |HM. . HUFFMAN CO| 00001930: 44 45 20 43 41 4E 20 42 45 20 41 4E 59 57 48 45 |DE CAN BE ANYWHE| 00001940: 52 45 20 46 52 4F 4D 20 30 20 54 4F 20 32 34 20 |RE FROM 0 TO 24 | 00001950: 42 49 54 53 20 49 4E 0D 4C 45 4E 47 54 48 2E 20 |BITS IN.LENGTH. | 00001960: C5 41 43 48 20 42 49 54 20 49 4E 20 54 48 45 20 |.ACH BIT IN THE | 00001970: C8 55 46 46 4D 41 4E 20 43 4F 44 45 20 49 53 20 |.UFFMAN CODE IS | 00001980: 52 45 50 52 45 53 45 4E 54 45 44 20 42 59 20 54 |REPRESENTED BY T| 00001990: 57 4F 20 50 49 58 45 4C 53 20 4F 4E 20 54 48 45 |WO PIXELS ON THE| 000019A0: 0D 47 52 41 50 48 49 43 53 20 53 43 52 45 45 4E |.GRAPHICS SCREEN| 000019B0: 2E 20 D4 4F 20 52 55 4E 20 54 48 45 20 55 54 49 |. .O RUN THE UTI| 000019C0: 4C 49 54 59 20 59 4F 55 20 4D 55 53 54 20 48 41 |LITY YOU MUST HA| 000019D0: 56 45 20 C1 D2 C3 20 49 4E 20 4D 45 4D 4F 52 59 |VE ... IN MEMORY| 000019E0: 20 41 4E 44 20 54 59 50 45 3A 0D 0D 20 20 20 20 | AND TYPE:.. | 000019F0: 20 20 20 20 20 20 20 20 20 20 20 41 3A 41 4E 41 | A:ANA| 00001A00: 4C 59 5A 45 20 5B 44 3A 5D 46 49 4C 45 4E 41 4D |LYZE [D:]FILENAM| 00001A10: 45 0D 0D 20 20 20 20 D4 48 45 20 50 52 4F 47 52 |E.. .HE PROGR| 00001A20: 41 4D 20 57 49 4C 4C 20 54 48 45 4E 20 52 45 41 |AM WILL THEN REA| 00001A30: 44 20 54 48 52 4F 55 47 48 20 27 44 3A 46 49 4C |D THROUGH 'D:FIL| 00001A40: 45 4E 41 4D 45 27 20 41 4E 44 20 44 49 53 50 4C |ENAME' AND DISPL| 00001A50: 41 59 20 41 20 46 52 45 51 55 45 4E 43 59 0D 44 |AY A FREQUENCY.D| 00001A60: 49 53 54 52 49 42 55 54 49 4F 4E 20 46 4F 52 20 |ISTRIBUTION FOR | 00001A70: 54 48 45 20 46 49 4C 45 2E 0D 0D 20 20 20 20 C2 |THE FILE... .| 00001A80: 55 54 20 48 4F 57 20 44 4F 20 57 45 20 43 4F 4D |UT HOW DO WE COM| 00001A90: 45 20 55 50 20 57 49 54 48 20 54 48 45 20 42 45 |E UP WITH THE BE| 00001AA0: 53 54 20 54 52 45 45 20 54 4F 20 55 53 45 20 54 |ST TREE TO USE T| 00001AB0: 4F 20 47 45 4E 45 52 41 54 45 20 54 48 45 20 C8 |O GENERATE THE .| 00001AC0: 55 46 46 4D 41 4E 0D 43 4F 44 45 53 3F 20 C9 46 |UFFMAN.CODES? .F| 00001AD0: 20 59 4F 55 20 53 49 54 20 44 4F 57 4E 20 41 4E | YOU SIT DOWN AN| 00001AE0: 44 20 54 48 49 4E 4B 20 41 42 4F 55 54 20 49 54 |D THINK ABOUT IT| 00001AF0: 20 59 4F 55 20 57 49 4C 4C 20 52 45 41 4C 49 5A | YOU WILL REALIZ| 00001B00: 45 20 54 48 41 54 20 45 56 45 4E 20 49 46 20 4F |E THAT EVEN IF O| 00001B10: 4E 4C 59 20 41 0D 44 4F 5A 45 4E 20 4F 52 20 53 |NLY A.DOZEN OR S| 00001B20: 4F 20 42 59 54 45 53 20 41 52 45 20 55 53 45 44 |O BYTES ARE USED| 00001B30: 2C 20 54 48 45 20 4E 55 4D 42 45 52 20 4F 46 20 |, THE NUMBER OF | 00001B40: 50 4F 53 53 49 42 4C 45 20 54 52 45 45 53 20 49 |POSSIBLE TREES I| 00001B50: 53 20 51 55 49 54 45 20 4C 41 52 47 45 2E 0D 0D |S QUITE LARGE...| 00001B60: 20 20 20 20 C8 55 46 46 4D 41 4E 20 53 51 55 45 | .UFFMAN SQUE| 00001B70: 45 5A 49 4E 47 20 47 45 54 53 20 49 54 20 4E 41 |EZING GETS IT NA| 00001B80: 4D 45 20 46 52 4F 4D 20 54 48 45 20 4D 41 4E 20 |ME FROM THE MAN | 00001B90: 54 48 41 54 20 43 41 4D 45 20 55 50 20 57 49 54 |THAT CAME UP WIT| 00001BA0: 48 20 41 20 53 4F 4C 55 54 49 4F 4E 20 54 4F 0D |H A SOLUTION TO.| 00001BB0: 54 48 49 53 20 50 52 4F 42 4C 45 4D 2E 20 D7 45 |THIS PROBLEM. .E| 00001BC0: 20 41 43 54 55 41 4C 4C 59 20 54 52 49 45 44 20 | ACTUALLY TRIED | 00001BD0: 54 4F 20 46 49 47 55 52 45 20 49 54 20 4F 55 54 |TO FIGURE IT OUT| 00001BE0: 20 46 4F 52 20 4F 55 52 53 45 4C 56 45 53 20 41 | FOR OURSELVES A| 00001BF0: 4E 44 20 45 4E 44 45 44 20 55 50 0D 55 54 54 45 |ND ENDED UP.UTTE| 00001C00: 52 4C 59 20 43 4F 4E 46 55 53 45 44 20 55 4E 54 |RLY CONFUSED UNT| 00001C10: 49 4C 20 57 45 20 43 41 4D 45 20 41 43 52 4F 53 |IL WE CAME ACROS| 00001C20: 53 20 C8 55 46 46 4D 41 4E 27 53 20 41 52 54 49 |S .UFFMAN'S ARTI| 00001C30: 43 4C 45 28 32 29 2E 20 C8 55 46 46 4D 41 4E 20 |CLE(2). .UFFMAN | 00001C40: 4D 41 4B 45 53 20 49 54 0D 4C 4F 4F 4B 20 53 49 |MAKES IT.LOOK SI| 00001C50: 4D 50 4C 45 2E 0D 0D 20 20 20 20 20 20 20 20 20 |MPLE... | 00001C60: 20 20 20 20 20 20 CC 45 54 53 20 47 4F 20 42 41 | .ETS GO BA| 00001C70: 43 4B 20 54 4F 20 4F 55 52 20 50 52 45 56 49 4F |CK TO OUR PREVIO| 00001C80: 55 53 20 45 58 41 4D 50 4C 45 20 4F 46 20 22 41 |US EXAMPLE OF "A| 00001C90: 42 52 41 43 41 44 41 42 52 41 22 2E 0D 0D 20 20 |BRACADABRA"... | 00001CA0: 20 20 20 20 20 20 20 20 20 20 20 20 20 D7 45 20 | .E | 00001CB0: 53 54 41 52 54 20 4F 55 54 20 57 49 54 48 20 54 |START OUT WITH T| 00001CC0: 48 45 20 46 4F 4C 4C 4F 57 49 4E 47 20 46 52 45 |HE FOLLOWING FRE| 00001CD0: 51 55 45 4E 43 59 20 44 49 53 54 52 49 42 55 54 |QUENCY DISTRIBUT| 00001CE0: 49 4F 4E 3A 0D 0D 20 20 20 20 20 20 20 20 20 20 |ION:.. | 00001CF0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00001D00: 20 20 43 48 41 52 41 43 54 45 52 20 20 20 20 20 | CHARACTER | 00001D10: 20 46 52 45 51 55 45 4E 43 59 0D 20 20 20 20 20 | FREQUENCY. | 00001D20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00001D30: 20 20 20 20 20 20 20 2D 2D 2D 2D 2D 2D 2D 2D 2D | ---------| 00001D40: 20 20 20 20 20 20 2D 2D 2D 2D 2D 2D 2D 2D 2D 0D | ---------.| 00001D50: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00001D60: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00001D70: 41 20 20 20 20 20 20 20 20 20 20 20 20 20 20 35 |A 5| 00001D80: 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 |. | 00001D90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00001DA0: 20 42 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | B | 00001DB0: 32 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 20 |2. | 00001DC0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00001DD0: 20 20 52 20 20 20 20 20 20 20 20 20 20 20 20 20 | R | 00001DE0: 20 32 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 | 2. | 00001DF0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00001E00: 20 20 20 43 20 20 20 20 20 20 20 20 20 20 20 20 | C | 00001E10: 20 20 31 0D 20 20 20 20 20 20 20 20 20 20 20 20 | 1. | 00001E20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00001E30: 20 20 20 20 44 20 20 20 20 20 20 20 20 20 20 20 | D | 00001E40: 20 20 20 31 0D 0D 20 20 20 20 D7 45 20 53 54 41 | 1.. .E STA| 00001E50: 52 54 20 42 59 20 50 49 43 4B 49 4E 47 20 4F 46 |RT BY PICKING OF| 00001E60: 46 20 54 48 45 20 54 57 4F 20 4C 4F 57 45 53 54 |F THE TWO LOWEST| 00001E70: 20 46 52 45 51 55 45 4E 43 49 45 53 20 41 4E 44 | FREQUENCIES AND| 00001E80: 20 46 4F 52 4D 49 4E 47 20 41 20 50 41 52 54 49 | FORMING A PARTI| 00001E90: 41 4C 0D 54 52 45 45 20 57 49 54 48 20 54 48 45 |AL.TREE WITH THE| 00001EA0: 4D 2E 20 C9 4E 20 54 48 49 53 20 43 41 53 45 20 |M. .N THIS CASE | 00001EB0: 22 43 22 20 41 4E 44 20 22 44 22 2E 20 D4 48 49 |"C" AND "D". .HI| 00001EC0: 53 20 47 49 56 45 53 20 55 53 20 41 20 4E 45 57 |S GIVES US A NEW| 00001ED0: 20 54 41 42 4C 45 3A 0D 0D 5F 0D 20 20 20 20 20 | TABLE:.._. | 00001EE0: 20 20 20 20 20 32 2E 20 C8 55 46 46 4D 41 4E 2C | 2. .UFFMAN,| 00001EF0: 20 C4 2E C1 2E 2C 20 22 C1 20 CD C5 D4 C8 CF C4 | ...., ". ......| 00001F00: 20 C6 CF D2 20 D4 C8 C5 20 C3 CF CE D3 D4 D2 D5 | ... ... .......| 00001F10: C3 D4 C9 CF CE 20 CF C6 20 CD C9 CE C9 CD D5 CD |..... .. .......| 00001F20: 20 D2 C5 C4 D5 CE C4 C1 CE C3 D9 0D C3 CF C4 C5 | ...............| 00001F30: D3 22 2C 20 D0 52 4F 43 2E 20 C9 D2 C5 2C 20 34 |.", .ROC. ..., 4| 00001F40: 30 28 39 29 2C 20 31 30 39 38 2D 31 31 30 31 28 |0(9), 1098-1101(| 00001F50: 31 39 35 32 29 0D 0D 20 20 20 20 20 20 20 20 20 |1952).. | 00001F60: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00001F70: 20 20 20 43 48 41 52 41 43 54 45 52 20 20 20 20 | CHARACTER | 00001F80: 20 20 46 52 45 51 55 45 4E 43 59 0D 20 20 20 20 | FREQUENCY. | 00001F90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00001FA0: 20 20 20 20 20 20 20 20 2D 2D 2D 2D 2D 2D 2D 2D | --------| 00001FB0: 2D 20 20 20 20 20 20 2D 2D 2D 2D 2D 2D 2D 2D 2D |- ---------| 00001FC0: 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 |. | 00001FD0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00001FE0: 20 41 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | A | 00001FF0: 35 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 20 |5. | 00002000: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00002010: 20 20 42 20 20 20 20 20 20 20 20 20 20 20 20 20 | B | 00002020: 20 32 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 | 2. | 00002030: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00002040: 20 20 20 52 20 20 20 20 20 20 20 20 20 20 20 20 | R | 00002050: 20 20 32 0D 20 20 20 20 20 20 20 20 20 20 20 20 | 2. | 00002060: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00002070: 20 20 20 43 2C 44 20 20 20 20 20 20 20 20 20 20 | C,D | 00002080: 20 20 20 32 0D 0D 20 20 20 20 20 20 20 20 20 20 | 2.. | 00002090: 20 20 20 20 20 C1 4E 44 20 57 45 20 48 41 56 45 | .ND WE HAVE| 000020A0: 20 41 20 50 41 52 54 49 41 4C 20 54 52 45 45 3A | A PARTIAL TREE:| 000020B0: 0D 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 20 |.. | 000020C0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 000020D0: 20 20 20 44 0D 20 20 20 20 20 20 20 20 20 20 20 | D. | 000020E0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 000020F0: 20 20 20 20 20 2F 0D 20 20 20 20 20 20 20 20 20 | /. | 00002100: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00002110: 20 20 20 20 52 4F 4F 54 20 2D 20 43 0D 0D 20 20 | ROOT - C.. | 00002120: 20 20 CE 4F 57 20 57 45 20 52 45 50 45 41 54 20 | .OW WE REPEAT | 00002130: 54 48 45 20 50 52 4F 43 45 44 55 52 45 2E 20 D4 |THE PROCEDURE. .| 00002140: 48 49 53 20 54 49 4D 45 2C 20 48 4F 57 45 56 45 |HIS TIME, HOWEVE| 00002150: 52 2C 20 57 45 20 48 41 56 45 20 4D 4F 52 45 20 |R, WE HAVE MORE | 00002160: 54 48 41 4E 20 4F 4E 45 0D 43 48 4F 49 43 45 2E |THAN ONE.CHOICE.| 00002170: 20 D7 45 20 43 4F 55 4C 44 20 43 48 4F 4F 53 45 | .E COULD CHOOSE| 00002180: 20 22 42 22 20 41 4E 44 20 22 52 22 2C 20 4F 52 | "B" AND "R", OR| 00002190: 20 22 42 22 20 41 4E 44 20 22 43 2C 44 22 20 4F | "B" AND "C,D" O| 000021A0: 52 20 22 52 22 20 41 4E 44 20 22 43 2C 44 22 2E |R "R" AND "C,D".| 000021B0: 20 C1 53 20 46 41 52 0D 41 53 20 54 48 45 20 52 | .S FAR.AS THE R| 000021C0: 45 53 55 4C 54 49 4E 47 20 46 49 4C 45 20 49 53 |ESULTING FILE IS| 000021D0: 20 43 4F 4E 43 45 52 4E 45 44 2C 20 49 54 20 4D | CONCERNED, IT M| 000021E0: 41 4B 45 53 20 4E 4F 20 44 49 46 46 45 52 45 4E |AKES NO DIFFEREN| 000021F0: 43 45 20 57 48 49 43 48 20 4F 4E 45 20 57 45 20 |CE WHICH ONE WE | 00002200: 43 48 4F 4F 53 45 2E 0D D4 48 45 20 53 51 55 45 |CHOOSE...HE SQUE| 00002210: 45 5A 45 44 20 46 49 4C 45 53 20 4C 45 4E 47 54 |EZED FILES LENGT| 00002220: 48 20 57 49 4C 4C 20 42 45 20 54 48 45 20 53 41 |H WILL BE THE SA| 00002230: 4D 45 21 20 CC 45 54 53 20 44 4F 20 49 54 20 54 |ME! .ETS DO IT T| 00002240: 57 4F 20 44 49 46 46 45 52 45 4E 54 20 57 41 59 |WO DIFFERENT WAY| 00002250: 53 20 4A 55 53 54 0D 54 4F 20 53 45 45 20 57 48 |S JUST.TO SEE WH| 00002260: 41 54 20 48 41 50 50 45 4E 53 2E 0D 0D 20 20 20 |AT HAPPENS... | 00002270: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 43 48 | CH| 00002280: 41 52 41 43 54 45 52 20 20 46 52 45 51 55 45 4E |ARACTER FREQUEN| 00002290: 43 59 20 20 20 20 20 20 43 48 41 52 41 43 54 45 |CY CHARACTE| 000022A0: 52 20 20 46 52 45 51 55 45 4E 43 59 0D 20 20 20 |R FREQUENCY. | 000022B0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2D 2D | --| 000022C0: 2D 2D 2D 2D 2D 2D 2D 20 20 2D 2D 2D 2D 2D 2D 2D |------- -------| 000022D0: 2D 2D 20 20 20 20 20 20 2D 2D 2D 2D 2D 2D 2D 2D |-- --------| 000022E0: 2D 20 20 2D 2D 2D 2D 2D 2D 2D 2D 2D 0D 20 20 20 |- ---------. | 000022F0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00002300: 20 20 41 20 20 20 20 20 20 20 20 20 20 35 20 20 | A 5 | 00002310: 20 20 20 20 20 20 20 20 20 20 20 20 41 20 20 20 | A | 00002320: 20 20 20 20 20 20 20 35 0D 20 20 20 20 20 20 20 | 5. | 00002330: 20 20 20 20 20 20 20 20 20 20 20 20 20 42 2C 52 | B,R| 00002340: 20 20 20 20 20 20 20 20 20 34 20 20 20 20 20 20 | 4 | 00002350: 20 20 20 20 20 20 43 2C 44 2C 52 20 20 20 20 20 | C,D,R | 00002360: 20 20 20 34 0D 20 20 20 20 20 20 20 20 20 20 20 | 4. | 00002370: 20 20 20 20 20 20 20 20 20 43 2C 44 20 20 20 20 | C,D | 00002380: 20 20 20 20 20 32 20 20 20 20 20 20 20 20 20 20 | 2 | 00002390: 20 20 20 20 42 20 20 20 20 20 20 20 20 20 20 32 | B 2| 000023A0: 0D 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 20 |.. | 000023B0: 20 D7 48 49 43 48 20 47 49 56 45 53 3A 0D 0D 20 | .HICH GIVES:.. | 000023C0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 000023D0: 20 20 20 20 20 20 20 20 42 20 20 20 20 20 20 20 | B | 000023E0: 20 20 20 20 43 20 20 20 20 20 20 20 20 20 20 20 | C | 000023F0: 20 20 20 20 20 20 20 52 20 20 44 0D 20 20 20 20 | R D. | 00002400: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00002410: 20 20 20 20 2F 20 20 20 20 20 20 20 20 20 20 20 | / | 00002420: 2F 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 |/ | 00002430: 20 20 20 2F 20 20 2F 0D 20 20 20 20 20 20 20 20 | / /. | 00002440: 20 20 20 20 20 20 20 20 20 20 20 20 52 4F 4F 54 | ROOT| 00002450: 20 2D 20 52 20 20 20 20 52 4F 4F 54 20 2D 20 44 | - R ROOT - D| 00002460: 20 20 20 20 20 20 20 20 20 20 52 4F 4F 54 20 2D | ROOT -| 00002470: 20 2D 20 43 0D 0D 0D 0D 0D 20 20 20 20 20 20 20 | - C..... | 00002480: 20 20 20 20 20 20 20 20 C1 4E 44 20 41 47 41 49 | .ND AGAI| 00002490: 4E 3A 0D 0D 20 20 20 20 20 20 20 20 20 20 20 20 |N:.. | 000024A0: 20 20 20 20 20 43 48 41 52 41 43 54 45 52 20 20 | CHARACTER | 000024B0: 46 52 45 51 55 45 4E 43 59 20 20 20 20 20 20 43 |FREQUENCY C| 000024C0: 48 41 52 41 43 54 45 52 20 20 46 52 45 51 55 45 |HARACTER FREQUE| 000024D0: 4E 43 59 0D 20 20 20 20 20 20 20 20 20 20 20 20 |NCY. | 000024E0: 20 20 20 20 20 2D 2D 2D 2D 2D 2D 2D 2D 2D 20 20 | --------- | 000024F0: 2D 2D 2D 2D 2D 2D 2D 2D 2D 20 20 20 20 20 20 2D |--------- -| 00002500: 2D 2D 2D 2D 2D 2D 2D 2D 20 20 2D 2D 2D 2D 2D 2D |-------- ------| 00002510: 2D 2D 2D 0D 20 20 20 20 20 20 20 20 20 20 20 20 |---. | 00002520: 20 20 20 20 20 20 43 2C 44 2C 42 2C 52 20 20 20 | C,D,B,R | 00002530: 20 20 20 20 36 20 20 20 20 20 20 20 20 20 20 20 | 6 | 00002540: 43 2C 44 2C 42 2C 52 20 20 20 20 20 20 20 36 0D |C,D,B,R 6.| 00002550: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00002560: 20 20 20 20 20 41 20 20 20 20 20 20 20 20 20 20 | A | 00002570: 35 20 20 20 20 20 20 20 20 20 20 20 20 20 20 41 |5 A| 00002580: 20 20 20 20 20 20 20 20 20 20 35 0D 0D 20 20 20 | 5.. | 00002590: 20 20 20 20 20 20 20 20 20 20 20 20 D7 48 49 43 | .HIC| 000025A0: 48 20 47 49 56 45 53 3A 0D 0D 20 20 20 20 20 20 |H GIVES:.. | 000025B0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 000025C0: 20 20 20 20 44 0D 20 20 20 20 20 20 20 20 20 20 | D. | 000025D0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2F | /| 000025E0: 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 |. | 000025F0: 20 20 20 20 20 20 20 20 20 2F 2D 2D 43 0D 20 20 | /--C. | 00002600: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00002610: 20 20 20 20 20 2F 0D 20 20 20 20 20 20 20 20 20 | /. | 00002620: 20 20 20 20 20 20 20 20 20 20 20 20 20 2F 20 20 | / | 00002630: 20 42 20 20 20 20 20 20 4F 52 3A 20 20 20 20 20 | B OR: | 00002640: 20 20 20 20 20 20 20 42 20 20 52 20 20 44 0D 20 | B R D. | 00002650: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00002660: 20 20 20 20 2F 20 20 20 2F 20 20 20 20 20 20 20 | / / | 00002670: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2F 20 | / | 00002680: 20 2F 20 20 2F 0D 20 20 20 20 20 20 20 20 20 20 | / /. | 00002690: 20 20 20 20 20 20 20 52 4F 4F 54 20 2D 2D 20 2D | ROOT -- -| 000026A0: 20 52 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | R | 000026B0: 52 4F 4F 54 20 2D 20 2D 20 2D 20 2D 20 43 0D 0D |ROOT - - - - C..| 000026C0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 C1 | .| 000026D0: 4E 44 20 46 49 4E 41 4C 4C 59 20 57 45 20 43 4F |ND FINALLY WE CO| 000026E0: 4D 42 49 4E 45 20 54 48 45 53 45 20 54 4F 20 47 |MBINE THESE TO G| 000026F0: 45 54 3A 0D 0D 20 20 20 20 20 20 20 20 20 20 20 |ET:.. | 00002700: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00002710: 20 44 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 | D. | 00002720: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2F 0D | /.| 00002730: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00002740: 20 20 20 20 20 20 20 20 20 20 2F 2D 2D 43 0D 20 | /--C. | 00002750: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00002760: 20 20 20 20 20 20 20 20 2F 0D 20 20 20 20 20 20 | /. | 00002770: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 41 20 | A | 00002780: 20 20 2F 20 20 20 42 20 20 20 20 20 20 4F 52 3A | / B OR:| 00002790: 20 20 20 20 20 20 20 20 20 20 20 41 20 20 42 20 | A B | 000027A0: 20 52 20 20 44 0D 20 20 20 20 20 20 20 20 20 20 | R D. | 000027B0: 20 20 20 20 20 20 20 20 20 2F 20 20 20 2F 20 20 | / / | 000027C0: 20 2F 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | / | 000027D0: 20 20 20 20 20 20 2F 20 20 2F 20 20 2F 20 20 2F | / / / /| 000027E0: 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 |. | 000027F0: 52 4F 4F 54 20 2D 20 2D 20 2D 20 2D 20 2D 52 20 |ROOT - - - - -R | 00002800: 20 20 20 20 20 20 20 20 20 20 20 20 20 52 4F 4F | ROO| 00002810: 54 20 2D 20 2D 20 2D 20 2D 20 2D 20 43 0D 0D 20 |T - - - - - C.. | 00002820: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 D7 45 | .E| 00002830: 20 45 4E 44 20 55 50 20 57 49 54 48 20 54 48 45 | END UP WITH THE| 00002840: 20 46 4F 4C 4C 4F 57 49 4E 47 20 54 41 42 4C 45 | FOLLOWING TABLE| 00002850: 53 3A 0D 0D 20 20 20 20 20 20 20 20 20 20 20 20 |S:.. | 00002860: 20 20 20 20 20 20 43 48 41 52 41 43 54 45 52 20 | CHARACTER | 00002870: 20 46 52 45 51 55 45 4E 43 59 20 20 20 20 20 20 | FREQUENCY | 00002880: 20 20 43 4F 44 45 31 20 20 20 20 20 43 4F 44 45 | CODE1 CODE| 00002890: 32 20 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 |2 . | 000028A0: 20 20 20 20 20 2D 2D 2D 2D 2D 2D 2D 2D 2D 20 20 | --------- | 000028B0: 2D 2D 2D 2D 2D 2D 2D 2D 2D 20 20 20 20 20 20 20 |--------- | 000028C0: 20 2D 2D 2D 2D 2D 20 20 20 20 20 2D 2D 2D 2D 2D | ----- -----| 000028D0: 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 |. | 000028E0: 20 20 20 20 20 20 20 41 20 20 20 20 20 20 20 20 | A | 000028F0: 20 20 35 20 20 20 20 20 20 20 20 20 20 20 20 20 | 5 | 00002900: 30 20 20 20 20 20 20 20 20 20 30 20 0D 20 20 20 |0 0 . | 00002910: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00002920: 20 20 20 42 20 20 20 20 20 20 20 20 20 20 32 20 | B 2 | 00002930: 20 20 20 20 20 20 20 20 20 20 20 20 31 31 30 20 | 110 | 00002940: 20 20 20 20 20 20 31 30 0D 20 20 20 20 20 20 20 | 10. | 00002950: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 52 | R| 00002960: 20 20 20 20 20 20 20 20 20 20 32 20 20 20 20 20 | 2 | 00002970: 20 20 20 20 20 20 20 20 31 31 31 20 20 20 20 20 | 111 | 00002980: 20 20 31 31 30 20 0D 20 20 20 20 20 20 20 20 20 | 110 . | 00002990: 20 20 20 20 20 20 20 20 20 20 20 20 20 43 20 20 | C | 000029A0: 20 20 20 20 20 20 20 20 31 20 20 20 20 20 20 20 | 1 | 000029B0: 20 20 20 20 20 20 31 30 31 20 20 20 20 20 20 20 | 101 | 000029C0: 31 31 31 31 0D 20 20 20 20 20 20 20 20 20 20 20 |1111. | 000029D0: 20 20 20 20 20 20 20 20 20 20 20 44 20 20 20 20 | D | 000029E0: 20 20 20 20 20 20 31 20 20 20 20 20 20 20 20 20 | 1 | 000029F0: 20 20 20 20 31 30 30 20 20 20 20 20 20 20 31 31 | 100 11| 00002A00: 31 30 0D 0D 20 20 20 20 C9 46 20 59 4F 55 20 4D |10.. .F YOU M| 00002A10: 55 4C 54 49 50 4C 59 20 54 48 45 20 43 4F 44 45 |ULTIPLY THE CODE| 00002A20: 20 4C 45 4E 47 54 48 20 54 49 4D 45 53 20 54 48 | LENGTH TIMES TH| 00002A30: 45 20 46 52 45 51 55 45 4E 43 59 20 46 4F 52 20 |E FREQUENCY FOR | 00002A40: 45 41 43 48 20 43 48 41 52 41 43 54 45 52 20 41 |EACH CHARACTER A| 00002A50: 4E 44 0D 53 55 4D 20 54 48 45 20 52 45 53 55 4C |ND.SUM THE RESUL| 00002A60: 54 53 2C 20 59 4F 55 20 57 49 4C 4C 20 47 45 54 |TS, YOU WILL GET| 00002A70: 20 54 48 45 20 46 49 4C 45 53 20 53 51 55 45 45 | THE FILES SQUEE| 00002A80: 5A 45 44 20 4C 45 4E 47 54 48 20 49 4E 20 42 49 |ZED LENGTH IN BI| 00002A90: 54 53 2E 20 D9 4F 55 20 57 49 4C 4C 20 46 49 4E |TS. .OU WILL FIN| 00002AA0: 44 0D 54 48 41 54 20 49 54 20 49 53 20 54 48 45 |D.THAT IT IS THE| 00002AB0: 20 53 41 4D 45 20 49 4E 20 42 4F 54 48 20 20 43 | SAME IN BOTH C| 00002AC0: 41 53 45 53 2E 20 C1 D2 C3 20 57 49 4C 4C 2C 20 |ASES. ... WILL, | 00002AD0: 48 4F 57 45 56 45 52 2C 20 41 4C 57 41 59 53 20 |HOWEVER, ALWAYS | 00002AE0: 43 48 4F 4F 53 45 20 54 48 45 20 4F 50 54 49 4F |CHOOSE THE OPTIO| 00002AF0: 4E 0D 57 48 49 43 48 20 52 45 53 55 4C 54 53 20 |N.WHICH RESULTS | 00002B00: 49 4E 20 54 48 45 20 53 48 4F 52 54 45 53 54 20 |IN THE SHORTEST | 00002B10: 43 4F 44 45 20 4C 45 4E 47 54 48 53 2E 20 C1 D2 |CODE LENGTHS. ..| 00002B20: C3 20 4F 4E 4C 59 20 41 4C 4C 4F 57 53 20 41 20 |. ONLY ALLOWS A | 00002B30: 4D 41 58 49 4D 55 4D 20 43 4F 44 45 0D 4C 45 4E |MAXIMUM CODE.LEN| 00002B40: 47 54 48 20 4F 46 20 32 34 20 42 49 54 53 2E 20 |GTH OF 24 BITS. | 00002B50: CE 4F 54 45 20 41 4C 53 4F 20 54 48 41 54 20 54 |.OTE ALSO THAT T| 00002B60: 48 45 52 45 20 41 52 45 20 41 20 54 4F 54 41 4C |HERE ARE A TOTAL| 00002B70: 20 4F 46 20 4F 4E 4C 59 20 31 33 20 42 49 54 53 | OF ONLY 13 BITS| 00002B80: 20 4F 4E 20 54 48 45 20 4C 45 46 54 2C 0D 42 55 | ON THE LEFT,.BU| 00002B90: 54 20 31 34 20 4F 4E 20 54 48 45 20 52 49 47 48 |T 14 ON THE RIGH| 00002BA0: 54 2E 20 D4 48 49 53 20 41 4C 53 4F 20 4D 41 4B |T. .HIS ALSO MAK| 00002BB0: 45 53 20 54 48 45 20 4C 45 4E 47 54 48 20 4F 46 |ES THE LENGTH OF| 00002BC0: 20 54 48 45 20 45 4E 43 4F 44 49 4E 47 20 54 41 | THE ENCODING TA| 00002BD0: 42 4C 45 20 41 20 42 49 54 0D 53 48 4F 52 54 45 |BLE A BIT.SHORTE| 00002BE0: 52 2E 20 CE 4F 20 50 55 4E 20 49 4E 54 45 4E 44 |R. .O PUN INTEND| 00002BF0: 45 44 2E 0D 0D 20 20 20 20 D3 49 4E 43 45 20 57 |ED... .INCE W| 00002C00: 45 20 41 52 45 20 42 55 49 4C 44 49 4E 47 20 54 |E ARE BUILDING T| 00002C10: 48 45 20 43 4F 44 45 53 20 54 57 4F 20 47 52 4F |HE CODES TWO GRO| 00002C20: 55 50 53 20 41 54 20 41 20 54 49 4D 45 2C 20 54 |UPS AT A TIME, T| 00002C30: 48 45 20 54 49 4D 45 20 54 48 41 54 20 49 54 20 |HE TIME THAT IT | 00002C40: 54 41 4B 45 53 0D 54 4F 20 47 45 4E 45 52 41 54 |TAKES.TO GENERAT| 00002C50: 45 20 54 48 45 20 43 4F 44 45 53 20 49 53 20 44 |E THE CODES IS D| 00002C60: 49 52 45 43 54 4C 59 20 50 52 4F 50 4F 52 54 49 |IRECTLY PROPORTI| 00002C70: 4F 4E 41 4C 20 54 4F 20 54 48 45 20 4E 55 4D 42 |ONAL TO THE NUMB| 00002C80: 45 52 20 4F 46 20 45 4E 54 52 49 45 53 20 49 4E |ER OF ENTRIES IN| 00002C90: 20 54 48 45 0D 54 41 42 4C 45 2E 20 C1 46 54 45 | THE.TABLE. .FTE| 00002CA0: 52 20 C1 D2 C3 20 46 49 4E 49 53 48 45 53 20 49 |R ... FINISHES I| 00002CB0: 54 53 20 41 4E 41 4C 59 5A 45 20 50 41 53 53 2C |TS ANALYZE PASS,| 00002CC0: 20 59 4F 55 20 57 49 4C 4C 20 4E 4F 54 49 43 45 | YOU WILL NOTICE| 00002CD0: 20 41 20 44 45 4C 41 59 20 4F 46 20 41 20 53 45 | A DELAY OF A SE| 00002CE0: 43 4F 4E 44 0D 4F 52 20 54 57 4F 20 42 45 46 4F |COND.OR TWO BEFO| 00002CF0: 52 45 20 C1 D2 C3 20 41 43 54 55 41 4C 4C 59 20 |RE ... ACTUALLY | 00002D00: 53 54 41 52 54 53 20 53 51 55 45 45 5A 49 4E 47 |STARTS SQUEEZING| 00002D10: 20 41 20 46 49 4C 45 2E 20 C6 4F 52 20 54 45 58 | A FILE. .OR TEX| 00002D20: 54 20 46 49 4C 45 53 2C 20 54 48 45 20 44 45 4C |T FILES, THE DEL| 00002D30: 41 59 20 49 53 0D 53 48 4F 52 54 20 42 45 43 41 |AY IS.SHORT BECA| 00002D40: 55 53 45 20 54 48 45 20 54 41 42 4C 45 20 49 53 |USE THE TABLE IS| 00002D50: 4E 27 54 20 56 45 52 59 20 4C 4F 4E 47 2E 20 C6 |N'T VERY LONG. .| 00002D60: 4F 52 20 50 52 4F 47 52 41 4D 53 2C 20 48 4F 57 |OR PROGRAMS, HOW| 00002D70: 45 56 45 52 2C 20 54 48 45 20 44 45 4C 41 59 20 |EVER, THE DELAY | 00002D80: 49 53 0D 51 55 49 54 45 20 4E 4F 54 49 43 45 41 |IS.QUITE NOTICEA| 00002D90: 42 4C 45 20 42 45 43 41 55 53 45 20 41 4C 4C 20 |BLE BECAUSE ALL | 00002DA0: 32 35 36 20 50 4F 53 53 49 42 4C 45 20 42 59 54 |256 POSSIBLE BYT| 00002DB0: 45 20 56 41 4C 55 45 53 20 41 52 45 20 55 53 55 |E VALUES ARE USU| 00002DC0: 41 4C 4C 59 20 55 53 45 44 2E 0D 0D 20 20 20 20 |ALLY USED... | 00002DD0: D4 52 45 45 53 20 41 52 45 20 41 4E 20 45 58 43 |.REES ARE AN EXC| 00002DE0: 45 4C 4C 45 4E 54 20 54 4F 4F 4C 20 54 4F 20 55 |ELLENT TOOL TO U| 00002DF0: 4E 44 45 52 53 54 41 4E 44 49 4E 47 20 54 48 45 |NDERSTANDING THE| 00002E00: 20 54 48 45 4F 52 59 20 42 45 48 49 4E 44 20 C8 | THEORY BEHIND .| 00002E10: 55 46 46 4D 41 4E 0D 53 51 55 45 45 5A 49 4E 47 |UFFMAN.SQUEEZING| 00002E20: 2E 20 CF 44 44 4C 59 20 45 4E 4F 55 47 48 2C 20 |. .DDLY ENOUGH, | 00002E30: C1 D2 C3 20 44 4F 45 53 4E 27 54 20 55 53 45 20 |... DOESN'T USE | 00002E40: 54 48 49 53 20 43 4F 4E 43 45 50 54 20 54 4F 20 |THIS CONCEPT TO | 00002E50: 41 4E 59 20 41 44 56 41 4E 54 41 47 45 20 41 54 |ANY ADVANTAGE AT| 00002E60: 20 41 4C 4C 2E 0D 0D 20 20 20 20 CC 45 4D 50 45 | ALL... .EMPE| 00002E70: 4C 2D DA 45 56 2D D7 45 4C 43 48 28 33 29 2C 20 |L-.EV-.ELCH(3), | 00002E80: 4F 52 20 CC DA D7 20 43 4F 4D 50 52 45 53 53 49 |OR ... COMPRESSI| 00002E90: 4F 4E 20 49 53 20 55 53 45 44 20 54 4F 20 27 43 |ON IS USED TO 'C| 00002EA0: 52 55 4E 43 48 27 20 46 49 4C 45 53 2E 20 C9 54 |RUNCH' FILES. .T| 00002EB0: 20 49 53 0D 52 45 41 4C 4C 59 20 51 55 49 54 45 | IS.REALLY QUITE| 00002EC0: 20 41 4D 41 5A 49 4E 47 20 53 49 4E 43 45 20 49 | AMAZING SINCE I| 00002ED0: 54 20 41 4C 4D 4F 53 54 20 41 4C 57 41 59 53 20 |T ALMOST ALWAYS | 00002EE0: 49 53 20 43 48 4F 53 45 4E 20 41 53 20 54 48 45 |IS CHOSEN AS THE| 00002EF0: 20 4D 4F 53 54 20 45 46 46 49 43 49 45 4E 54 0D | MOST EFFICIENT.| 00002F00: 43 4F 4D 50 52 45 53 53 4F 52 20 41 4E 44 20 43 |COMPRESSOR AND C| 00002F10: 41 4E 20 42 45 20 50 45 52 46 4F 52 4D 45 44 20 |AN BE PERFORMED | 00002F20: 27 4F 4E 20 54 48 45 20 46 4C 59 27 20 57 49 54 |'ON THE FLY' WIT| 00002F30: 48 4F 55 54 20 46 49 52 53 54 20 48 41 56 49 4E |HOUT FIRST HAVIN| 00002F40: 47 20 54 4F 20 41 4E 41 4C 59 5A 45 20 41 0D 46 |G TO ANALYZE A.F| 00002F50: 49 4C 45 53 20 43 4F 4E 54 45 4E 54 53 2E 20 C9 |ILES CONTENTS. .| 00002F60: 54 20 54 41 4B 45 53 20 41 44 56 41 4E 54 41 47 |T TAKES ADVANTAG| 00002F70: 45 20 4F 46 20 54 48 45 20 46 41 43 54 20 54 48 |E OF THE FACT TH| 00002F80: 41 54 20 43 45 52 54 41 49 4E 20 53 45 51 55 45 |AT CERTAIN SEQUE| 00002F90: 4E 43 45 53 20 4F 46 20 42 59 54 45 53 0D 4F 43 |NCES OF BYTES.OC| 00002FA0: 43 55 52 20 4D 4F 52 45 20 4F 46 54 45 4E 20 54 |CUR MORE OFTEN T| 00002FB0: 48 41 4E 20 4F 54 48 45 52 53 20 49 4E 20 54 59 |HAN OTHERS IN TY| 00002FC0: 50 49 43 41 4C 20 44 41 54 41 20 46 49 4C 45 53 |PICAL DATA FILES| 00002FD0: 2E 0D 0D 20 20 20 20 C6 4F 52 20 45 58 41 4D 50 |... .OR EXAMP| 00002FE0: 4C 45 2C 20 49 4E 20 41 4E 20 41 53 43 49 49 20 |LE, IN AN ASCII | 00002FF0: 4C 49 53 54 49 4E 47 20 4F 46 20 41 20 C2 C1 D3 |LISTING OF A ...| 00003000: C9 C3 20 50 52 4F 47 52 41 4D 2C 20 54 48 45 20 |.. PROGRAM, THE | 00003010: C2 C1 D3 C9 C3 20 4B 45 59 57 4F 52 44 53 2C 0D |..... KEYWORDS,.| 00003020: C9 CE D0 D5 D4 2C 20 C7 CF D4 CF 2C 20 C7 CF D3 |....., ...., ...| 00003030: D5 C2 20 41 4E 44 20 4F 54 48 45 52 53 20 4F 43 |.. AND OTHERS OC| 00003040: 43 55 52 20 57 49 54 48 20 41 42 55 4E 44 41 4E |CUR WITH ABUNDAN| 00003050: 43 45 2E 20 C9 4E 20 54 48 49 53 20 44 4F 43 55 |CE. .N THIS DOCU| 00003060: 4D 45 4E 54 2C 20 57 4F 52 44 53 20 4C 49 4B 45 |MENT, WORDS LIKE| 00003070: 0D 22 C1 D2 C3 22 2C 20 22 43 4F 4D 50 52 45 53 |."...", "COMPRES| 00003080: 53 22 2C 20 22 53 51 55 45 45 5A 45 22 2C 20 4F |S", "SQUEEZE", O| 00003090: 52 20 43 48 41 52 41 43 54 45 52 53 20 53 45 51 |R CHARACTERS SEQ| 000030A0: 55 45 4E 43 45 53 20 4C 49 4B 45 20 22 2E 20 22 |UENCES LIKE ". "| 000030B0: 20 4F 52 20 22 2C 20 22 20 4F 43 43 55 52 0D 51 | OR ", " OCCUR.Q| 000030C0: 55 49 54 45 20 4F 46 54 45 4E 2E 20 C9 46 20 57 |UITE OFTEN. .F W| 000030D0: 45 20 43 4F 55 4C 44 20 52 45 50 4C 41 43 45 20 |E COULD REPLACE | 000030E0: 54 48 45 53 45 20 43 48 41 52 41 43 54 45 52 20 |THESE CHARACTER | 000030F0: 53 45 51 55 45 4E 43 45 53 20 57 49 54 48 20 53 |SEQUENCES WITH S| 00003100: 48 4F 52 54 45 52 20 43 4F 44 45 53 2C 0D 57 45 |HORTER CODES,.WE| 00003110: 20 57 4F 55 4C 44 20 45 4E 44 20 55 50 20 57 49 | WOULD END UP WI| 00003120: 54 48 20 41 20 53 48 4F 52 54 45 52 20 4F 55 54 |TH A SHORTER OUT| 00003130: 50 55 54 20 46 49 4C 45 2E 20 D7 48 45 4E 20 59 |PUT FILE. .HEN Y| 00003140: 4F 55 20 45 4E 54 45 52 20 41 20 4C 49 4E 45 20 |OU ENTER A LINE | 00003150: 4F 46 20 C2 C1 D3 C9 C3 20 43 4F 44 45 2C 0D 54 |OF ..... CODE,.T| 00003160: 48 45 20 C2 C1 D3 C9 C3 20 49 4E 54 45 52 50 52 |HE ..... INTERPR| 00003170: 45 54 45 52 20 44 4F 45 53 20 4A 55 53 54 20 54 |ETER DOES JUST T| 00003180: 48 41 54 20 42 59 20 4C 4F 4F 4B 49 4E 47 20 54 |HAT BY LOOKING T| 00003190: 4F 20 53 45 45 20 49 46 20 41 4E 59 20 4F 46 20 |O SEE IF ANY OF | 000031A0: 4B 45 59 57 4F 52 44 53 20 49 4E 20 54 48 45 0D |KEYWORDS IN THE.| 000031B0: 4C 49 4E 45 20 4F 43 43 55 52 20 49 4E 20 49 54 |LINE OCCUR IN IT| 000031C0: 53 20 4B 45 59 57 4F 52 44 20 54 41 42 4C 45 2E |S KEYWORD TABLE.| 000031D0: 20 C1 D2 C3 20 44 4F 45 53 20 53 4F 4D 45 54 48 | ... DOES SOMETH| 000031E0: 49 4E 47 20 53 49 4D 49 4C 41 52 2C 20 42 55 54 |ING SIMILAR, BUT| 000031F0: 20 50 52 45 50 41 52 45 53 20 54 48 45 0D 4B 45 | PREPARES THE.KE| 00003200: 59 57 4F 52 44 20 54 41 42 4C 45 20 46 52 4F 4D |YWORD TABLE FROM| 00003210: 20 53 43 52 41 54 43 48 20 46 4F 52 20 45 41 43 | SCRATCH FOR EAC| 00003220: 48 20 46 49 4C 45 20 49 54 20 43 52 55 4E 43 48 |H FILE IT CRUNCH| 00003230: 45 53 2E 0D 0D 20 20 20 20 D4 48 45 20 CC DA D7 |ES... .HE ...| 00003240: 20 41 4C 47 4F 52 49 54 48 4D 20 52 45 41 44 53 | ALGORITHM READS| 00003250: 20 54 48 45 20 49 4E 50 55 54 20 46 49 4C 45 20 | THE INPUT FILE | 00003260: 53 45 51 55 45 4E 54 49 41 4C 4C 59 20 41 4E 44 |SEQUENTIALLY AND| 00003270: 20 52 45 4D 45 4D 42 45 52 53 20 53 45 51 55 45 | REMEMBERS SEQUE| 00003280: 4E 43 45 53 0D 4F 46 20 43 48 41 52 41 43 54 45 |NCES.OF CHARACTE| 00003290: 52 53 20 54 48 41 54 20 48 41 56 45 20 4F 43 43 |RS THAT HAVE OCC| 000032A0: 55 52 52 45 44 20 50 52 45 56 49 4F 55 53 4C 59 |URRED PREVIOUSLY| 000032B0: 20 49 4E 20 54 48 45 20 46 49 4C 45 20 41 4E 44 | IN THE FILE AND| 000032C0: 20 52 45 50 4C 41 43 45 53 20 53 55 42 53 45 51 | REPLACES SUBSEQ| 000032D0: 55 45 4E 54 0D 4F 43 43 55 52 52 45 4E 43 45 53 |UENT.OCCURRENCES| 000032E0: 20 57 49 54 48 20 53 48 4F 52 54 45 52 20 43 4F | WITH SHORTER CO| 000032F0: 44 45 53 2E 20 C9 54 20 50 52 45 50 41 52 45 53 |DES. .T PREPARES| 00003300: 20 41 20 27 53 54 52 49 4E 47 20 54 41 42 4C 45 | A 'STRING TABLE| 00003310: 27 20 41 53 20 49 54 20 47 4F 45 53 20 54 48 52 |' AS IT GOES THR| 00003320: 4F 55 47 48 0D 54 48 45 20 46 49 4C 45 20 57 48 |OUGH.THE FILE WH| 00003330: 49 43 48 20 49 53 20 55 53 45 44 20 54 4F 20 47 |ICH IS USED TO G| 00003340: 45 4E 45 52 41 54 45 20 54 48 45 20 43 4F 44 45 |ENERATE THE CODE| 00003350: 53 2E 20 C1 47 41 49 4E 2C 20 57 45 20 43 4F 55 |S. .GAIN, WE COU| 00003360: 4C 44 20 54 48 49 4E 4B 20 4F 46 20 54 48 45 0D |LD THINK OF THE.| 00003370: 53 54 52 49 4E 47 20 54 41 42 4C 45 20 41 53 20 |STRING TABLE AS | 00003380: 41 20 54 52 45 45 2C 20 42 55 54 20 54 48 49 53 |A TREE, BUT THIS| 00003390: 20 54 49 4D 45 20 49 54 20 49 53 20 41 20 4D 55 | TIME IT IS A MU| 000033A0: 43 48 20 4D 4F 52 45 20 43 4F 4D 50 4C 49 43 41 |CH MORE COMPLICA| 000033B0: 54 45 44 20 54 52 45 45 20 53 49 4E 43 45 0D 45 |TED TREE SINCE.E| 000033C0: 41 43 48 20 4E 4F 44 45 20 43 41 4E 20 48 41 56 |ACH NODE CAN HAV| 000033D0: 45 20 41 53 20 4D 41 4E 59 20 41 53 20 32 35 36 |E AS MANY AS 256| 000033E0: 20 42 52 41 4E 43 48 45 53 21 0D 0D 20 20 20 20 | BRANCHES!.. | 000033F0: CC 45 54 53 20 54 41 4B 45 20 41 20 53 49 4D 50 |.ETS TAKE A SIMP| 00003400: 4C 49 46 49 45 44 20 45 58 41 4D 50 4C 45 2E 0D |LIFIED EXAMPLE..| 00003410: 0D 20 20 20 20 D3 55 50 50 4F 53 45 20 54 48 41 |. .UPPOSE THA| 00003420: 54 20 54 48 45 20 41 4C 50 48 41 42 45 54 20 43 |T THE ALPHABET C| 00003430: 4F 4E 53 49 53 54 45 44 20 4F 4E 4C 59 20 4F 46 |ONSISTED ONLY OF| 00003440: 20 54 48 45 20 4C 45 54 54 45 52 53 20 41 2C 42 | THE LETTERS A,B| 00003450: 2C 20 41 4E 44 20 43 20 41 4E 44 20 4F 55 52 0D |, AND C AND OUR.| 00003460: 46 49 4C 45 20 49 53 20 22 41 42 41 42 41 42 41 |FILE IS "ABABABA| 00003470: 43 41 42 41 42 41 41 22 2E 0D 0D 20 20 20 20 D7 |CABABAA"... .| 00003480: 45 20 53 54 41 52 54 20 42 59 20 41 53 53 49 47 |E START BY ASSIG| 00003490: 4E 49 4E 47 20 41 20 43 4F 44 45 20 54 4F 20 45 |NING A CODE TO E| 000034A0: 41 43 48 20 4C 45 54 54 45 52 20 49 4E 20 4F 55 |ACH LETTER IN OU| 000034B0: 52 20 41 4C 50 48 41 42 45 54 2E 20 D4 48 55 53 |R ALPHABET. .HUS| 000034C0: 20 41 3D 31 20 42 3D 32 0D 41 4E 44 20 43 3D 33 | A=1 B=2.AND C=3| 000034D0: 2E 0D 0D 20 20 20 20 D4 48 45 20 46 49 52 53 54 |... .HE FIRST| 000034E0: 20 43 48 41 52 41 43 54 45 52 20 57 45 20 45 4E | CHARACTER WE EN| 000034F0: 43 4F 55 4E 54 45 52 20 49 53 20 41 4E 20 22 41 |COUNTER IS AN "A| 00003500: 22 2E 20 C9 54 20 49 53 20 49 4E 20 54 48 45 20 |". .T IS IN THE | 00003510: 53 54 52 49 4E 47 20 54 41 42 4C 45 2C 20 53 4F |STRING TABLE, SO| 00003520: 20 57 45 0D 53 41 56 45 20 54 48 45 20 22 41 22 | WE.SAVE THE "A"| 00003530: 20 41 53 20 41 20 50 52 45 46 49 58 20 53 54 52 | AS A PREFIX STR| 00003540: 49 4E 47 20 41 4E 44 20 47 45 54 20 41 4E 4F 54 |ING AND GET ANOT| 00003550: 48 45 52 20 43 48 41 52 41 43 54 45 52 20 57 48 |HER CHARACTER WH| 00003560: 49 43 48 20 57 45 20 43 41 4C 4C 20 54 48 45 0D |ICH WE CALL THE.| 00003570: 45 58 54 45 4E 53 49 4F 4E 2E 20 D4 48 45 20 4E |EXTENSION. .HE N| 00003580: 45 58 54 20 43 48 41 52 41 43 54 45 52 20 49 53 |EXT CHARACTER IS| 00003590: 20 41 20 22 42 22 2C 20 53 4F 20 57 45 20 4E 4F | A "B", SO WE NO| 000035A0: 57 20 48 41 56 45 20 54 48 45 20 53 45 51 55 45 |W HAVE THE SEQUE| 000035B0: 4E 43 45 20 22 41 42 22 2C 20 57 48 49 43 48 0D |NCE "AB", WHICH.| 000035C0: 49 53 20 4E 4F 54 20 49 4E 20 54 48 45 20 53 54 |IS NOT IN THE ST| 000035D0: 52 49 4E 47 20 54 41 42 4C 45 2E 20 D7 48 45 4E |RING TABLE. .HEN| 000035E0: 45 56 45 52 20 54 48 45 20 43 55 52 52 45 4E 54 |EVER THE CURRENT| 000035F0: 20 50 52 45 46 49 58 2B 45 58 54 45 4E 53 49 4F | PREFIX+EXTENSIO| 00003600: 4E 20 53 54 52 49 4E 47 20 57 45 20 48 41 56 45 |N STRING WE HAVE| 00003610: 0D 49 4E 20 4D 45 4D 4F 52 59 20 49 53 20 4E 4F |.IN MEMORY IS NO| 00003620: 54 20 49 4E 20 54 48 45 20 53 54 52 49 4E 47 20 |T IN THE STRING | 00003630: 54 41 42 4C 45 2C 20 57 45 20 44 4F 20 54 48 52 |TABLE, WE DO THR| 00003640: 45 45 20 54 48 49 4E 47 53 2E 20 D7 45 20 53 45 |EE THINGS. .E SE| 00003650: 4E 44 20 54 48 45 20 43 4F 44 45 20 46 4F 52 0D |ND THE CODE FOR.| 00003660: 54 48 45 20 50 52 45 46 49 58 20 54 4F 20 20 54 |THE PREFIX TO T| 00003670: 48 45 20 4F 55 54 50 55 54 20 46 49 4C 45 2C 20 |HE OUTPUT FILE, | 00003680: 41 44 44 20 54 48 45 20 50 52 45 46 49 58 2B 45 |ADD THE PREFIX+E| 00003690: 58 54 45 4E 53 49 4F 4E 20 53 54 52 49 4E 47 20 |XTENSION STRING | 000036A0: 54 4F 20 4F 55 52 20 53 54 52 49 4E 47 0D 54 41 |TO OUR STRING.TA| 000036B0: 42 4C 45 2C 20 41 4E 44 20 4D 41 4B 45 20 54 48 |BLE, AND MAKE TH| 000036C0: 45 20 45 58 54 45 4E 53 49 4F 4E 20 54 48 45 20 |E EXTENSION THE | 000036D0: 4E 45 57 20 50 52 45 46 49 58 2E 20 D4 48 55 53 |NEW PREFIX. .HUS| 000036E0: 20 57 45 20 43 4F 44 45 20 4F 55 54 20 41 20 22 | WE CODE OUT A "| 000036F0: 31 22 20 41 4E 44 20 53 45 54 20 54 48 45 0D 50 |1" AND SET THE.P| 00003700: 52 45 46 49 58 20 45 51 55 41 4C 20 54 4F 20 22 |REFIX EQUAL TO "| 00003710: 32 22 2C 20 54 48 45 20 43 4F 44 45 20 46 4F 52 |2", THE CODE FOR| 00003720: 20 22 42 22 20 41 4E 44 20 41 44 44 20 22 41 42 | "B" AND ADD "AB| 00003730: 22 20 54 4F 20 54 48 45 20 53 54 52 49 4E 47 20 |" TO THE STRING | 00003740: 54 41 42 4C 45 20 41 53 20 43 4F 44 45 0D 34 2E |TABLE AS CODE.4.| 00003750: 0D 0D 0D 0D 5F 0D 20 20 20 20 20 20 20 20 20 20 |...._. | 00003760: 33 2E 20 D7 45 4C 43 48 2C 20 D4 45 52 52 59 20 |3. .ELCH, .ERRY | 00003770: C1 2E 2C 20 22 C1 20 D4 C5 C3 C8 CE C9 D1 D5 C5 |.., ". .........| 00003780: 20 C6 CF D2 20 C8 C9 C7 C8 20 D0 C5 D2 C6 CF D2 | ... .... ......| 00003790: CD C1 CE C3 C5 20 C4 C1 D4 C1 0D 20 20 20 20 20 |..... ..... | 000037A0: 20 20 20 20 20 C3 CF CD D0 D2 C5 D3 D3 C9 CF CE | ...........| 000037B0: 22 2C 20 C9 C5 C5 C5 20 C3 CF CD D0 D5 D4 C5 D2 |", .... ........| 000037C0: 2C 20 CA 55 4E 45 20 31 39 38 34 2E 0D 0D 20 20 |, .UNE 1984... | 000037D0: 20 20 D7 45 20 4E 4F 57 20 48 41 56 45 20 22 42 | .E NOW HAVE "B| 000037E0: 22 20 41 53 20 54 48 45 20 50 52 45 46 49 58 2C |" AS THE PREFIX,| 000037F0: 20 41 4E 44 20 52 45 41 44 20 49 4E 20 54 48 45 | AND READ IN THE| 00003800: 20 4E 45 58 54 20 43 48 41 52 41 43 54 45 52 20 | NEXT CHARACTER | 00003810: 46 52 4F 4D 20 54 48 45 20 49 4E 50 55 54 0D 46 |FROM THE INPUT.F| 00003820: 49 4C 45 20 41 53 20 4F 55 52 20 4E 45 57 20 45 |ILE AS OUR NEW E| 00003830: 58 54 45 4E 53 49 4F 4E 2E 20 D4 48 45 20 4E 45 |XTENSION. .HE NE| 00003840: 58 54 20 43 48 41 52 41 43 54 45 52 20 49 53 20 |XT CHARACTER IS | 00003850: 41 4E 20 22 41 22 2E 20 22 42 41 22 20 49 53 20 |AN "A". "BA" IS | 00003860: 4E 4F 54 20 49 4E 20 54 48 45 0D 53 54 52 49 4E |NOT IN THE.STRIN| 00003870: 47 20 54 41 42 4C 45 2C 20 53 4F 20 57 45 20 43 |G TABLE, SO WE C| 00003880: 4F 44 45 20 4F 55 54 20 20 54 48 45 20 22 42 22 |ODE OUT THE "B"| 00003890: 2C 20 41 44 44 20 22 42 41 22 3D 35 20 54 4F 20 |, ADD "BA"=5 TO | 000038A0: 54 48 45 20 53 54 52 49 4E 47 20 54 41 42 4C 45 |THE STRING TABLE| 000038B0: 2C 20 41 4E 44 20 4D 41 4B 45 0D 22 41 22 20 54 |, AND MAKE."A" T| 000038C0: 48 45 20 4E 45 57 20 50 52 45 46 49 58 2E 0D 0D |HE NEW PREFIX...| 000038D0: 20 20 20 20 CE 4F 57 20 49 53 20 57 48 45 4E 20 | .OW IS WHEN | 000038E0: 49 54 20 53 54 41 52 54 53 20 54 4F 20 47 45 54 |IT STARTS TO GET| 000038F0: 20 49 4E 54 45 52 45 53 54 49 4E 47 2E 20 D7 45 | INTERESTING. .E| 00003900: 20 4E 4F 57 20 48 41 56 45 20 22 41 22 20 41 53 | NOW HAVE "A" AS| 00003910: 20 20 54 48 45 20 50 52 45 46 49 58 20 41 4E 44 | THE PREFIX AND| 00003920: 0D 52 45 41 44 20 49 4E 20 22 42 22 20 41 53 20 |.READ IN "B" AS | 00003930: 54 48 45 20 4E 45 58 54 20 45 58 54 45 4E 53 49 |THE NEXT EXTENSI| 00003940: 4F 4E 2E 20 D4 48 49 53 20 54 49 4D 45 20 22 41 |ON. .HIS TIME "A| 00003950: 42 22 20 49 53 20 49 4E 20 54 48 45 20 53 54 52 |B" IS IN THE STR| 00003960: 49 4E 47 20 54 41 42 4C 45 2C 20 53 4F 20 57 45 |ING TABLE, SO WE| 00003970: 0D 4D 41 4B 45 20 54 48 45 20 43 4F 44 45 20 46 |.MAKE THE CODE F| 00003980: 4F 52 20 22 41 42 22 20 54 48 45 20 4E 45 57 20 |OR "AB" THE NEW | 00003990: 50 52 45 46 49 58 20 41 4E 44 20 47 45 54 20 41 |PREFIX AND GET A| 000039A0: 4E 4F 54 48 45 52 20 45 58 54 45 4E 53 49 4F 4E |NOTHER EXTENSION| 000039B0: 2E 20 D4 48 45 20 4E 45 58 54 0D 43 48 41 52 41 |. .HE NEXT.CHARA| 000039C0: 43 54 45 52 20 49 53 20 41 4E 20 22 41 22 2C 20 |CTER IS AN "A", | 000039D0: 22 41 42 41 22 20 49 53 20 4E 4F 54 20 49 4E 20 |"ABA" IS NOT IN | 000039E0: 54 48 45 20 53 54 52 49 4E 47 20 54 41 42 4C 45 |THE STRING TABLE| 000039F0: 20 53 4F 20 57 45 20 53 45 4E 44 20 54 48 45 20 | SO WE SEND THE | 00003A00: 50 52 45 46 49 58 20 43 4F 44 45 0D 22 41 42 22 |PREFIX CODE."AB"| 00003A10: 3D 34 20 54 4F 20 54 48 45 20 4F 55 54 50 55 54 |=4 TO THE OUTPUT| 00003A20: 20 46 49 4C 45 20 41 4E 44 20 41 44 44 20 22 41 | FILE AND ADD "A| 00003A30: 42 41 22 3D 36 20 54 4F 20 4F 55 52 20 53 54 52 |BA"=6 TO OUR STR| 00003A40: 49 4E 47 20 54 41 42 4C 45 2E 20 CE 45 58 54 20 |ING TABLE. .EXT | 00003A50: 54 49 4D 45 20 57 45 0D 45 4E 43 4F 55 4E 54 45 |TIME WE.ENCOUNTE| 00003A60: 52 20 54 48 45 20 53 45 51 55 45 4E 43 45 20 22 |R THE SEQUENCE "| 00003A70: 41 42 41 22 2C 20 57 45 27 4C 4C 20 4F 4E 4C 59 |ABA", WE'LL ONLY| 00003A80: 20 48 41 56 45 20 54 4F 20 53 45 4E 44 20 4F 4E | HAVE TO SEND ON| 00003A90: 45 20 43 4F 44 45 20 49 4E 20 54 48 45 20 50 4C |E CODE IN THE PL| 00003AA0: 41 43 45 20 4F 46 0D 54 48 52 45 45 20 43 48 41 |ACE OF.THREE CHA| 00003AB0: 52 41 43 54 45 52 53 21 0D 0D 20 20 20 20 D4 48 |RACTERS!.. .H| 00003AC0: 45 20 50 52 45 46 49 58 20 49 53 20 4E 4F 57 20 |E PREFIX IS NOW | 00003AD0: 22 41 22 2E 20 D7 45 20 47 45 54 20 54 48 45 20 |"A". .E GET THE | 00003AE0: 4E 45 58 54 20 43 48 41 52 41 43 54 45 52 20 22 |NEXT CHARACTER "| 00003AF0: 42 22 2E 20 22 41 42 22 20 49 53 20 49 4E 20 54 |B". "AB" IS IN T| 00003B00: 48 45 20 53 54 52 49 4E 47 0D 54 41 42 4C 45 2C |HE STRING.TABLE,| 00003B10: 20 53 4F 20 57 45 20 4D 41 4B 45 20 22 41 42 22 | SO WE MAKE "AB"| 00003B20: 3D 34 20 54 48 45 20 50 52 45 46 49 58 20 41 4E |=4 THE PREFIX AN| 00003B30: 44 20 47 45 54 20 41 4E 4F 54 48 45 52 20 43 48 |D GET ANOTHER CH| 00003B40: 41 52 41 43 54 45 52 2E 20 D4 48 49 53 20 54 49 |ARACTER. .HIS TI| 00003B50: 4D 45 20 49 54 53 20 41 4E 0D 22 41 22 2E 20 22 |ME ITS AN."A". "| 00003B60: 41 42 41 22 20 49 53 20 41 4C 53 4F 20 49 4E 20 |ABA" IS ALSO IN | 00003B70: 54 48 45 20 53 54 52 49 4E 47 20 54 41 42 4C 45 |THE STRING TABLE| 00003B80: 2C 20 53 4F 20 57 45 20 57 45 20 4D 41 4B 45 20 |, SO WE WE MAKE | 00003B90: 22 41 42 41 22 3D 36 20 4F 55 52 20 50 52 45 46 |"ABA"=6 OUR PREF| 00003BA0: 49 58 20 41 4E 44 20 47 45 54 0D 41 4E 4F 54 48 |IX AND GET.ANOTH| 00003BB0: 45 52 20 45 58 54 45 4E 53 49 4F 4E 2E 20 D4 48 |ER EXTENSION. .H| 00003BC0: 49 53 20 54 49 4D 45 20 49 54 53 20 41 20 22 43 |IS TIME ITS A "C| 00003BD0: 22 2C 20 53 4F 20 57 45 20 43 4F 44 45 20 4F 55 |", SO WE CODE OU| 00003BE0: 54 20 54 48 45 20 50 52 45 46 49 58 20 36 20 41 |T THE PREFIX 6 A| 00003BF0: 4E 44 20 4D 41 4B 45 20 22 43 22 0D 54 48 45 20 |ND MAKE "C".THE | 00003C00: 4E 45 57 20 50 52 45 46 49 58 2E 0D 0D 20 20 20 |NEW PREFIX... | 00003C10: 20 20 20 20 20 20 20 20 20 20 20 20 C1 54 20 54 | .T T| 00003C20: 48 49 53 20 50 4F 49 4E 54 20 4F 55 52 20 53 54 |HIS POINT OUR ST| 00003C30: 52 49 4E 47 20 54 41 42 4C 45 20 4C 4F 4F 4B 53 |RING TABLE LOOKS| 00003C40: 20 4C 49 4B 45 20 54 48 49 53 3A 0D 0D 20 20 20 | LIKE THIS:.. | 00003C50: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00003C60: 20 20 20 20 53 54 52 49 4E 47 20 20 20 43 4F 44 | STRING COD| 00003C70: 45 20 20 20 20 20 50 52 45 46 49 58 2B 45 58 54 |E PREFIX+EXT| 00003C80: 45 4E 53 49 4F 4E 0D 20 20 20 20 20 20 20 20 20 |ENSION. | 00003C90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2D 2D | --| 00003CA0: 2D 2D 2D 2D 20 20 20 2D 2D 2D 2D 20 20 20 20 20 |---- ---- | 00003CB0: 2D 2D 2D 2D 2D 2D 2D 2D 2D 2D 2D 2D 2D 2D 2D 2D |----------------| 00003CC0: 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 |. | 00003CD0: 20 20 20 20 20 20 20 20 20 20 41 20 20 20 20 20 | A | 00003CE0: 20 20 31 0D 20 20 20 20 20 20 20 20 20 20 20 20 | 1. | 00003CF0: 20 20 20 20 20 20 20 20 20 20 20 20 20 42 20 20 | B | 00003D00: 20 20 20 20 20 32 0D 20 20 20 20 20 20 20 20 20 | 2. | 00003D10: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00003D20: 43 20 20 20 20 20 20 20 33 0D 20 20 20 20 20 20 |C 3. | 00003D30: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00003D40: 20 20 20 41 42 20 20 20 20 20 20 34 20 20 20 20 | AB 4 | 00003D50: 20 20 20 31 2B 32 0D 20 20 20 20 20 20 20 20 20 | 1+2. | 00003D60: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00003D70: 42 41 20 20 20 20 20 20 35 20 20 20 20 20 20 20 |BA 5 | 00003D80: 32 2B 31 0D 20 20 20 20 20 20 20 20 20 20 20 20 |2+1. | 00003D90: 20 20 20 20 20 20 20 20 20 20 20 20 20 41 42 41 | ABA| 00003DA0: 20 20 20 20 20 36 20 20 20 20 20 20 20 34 2B 31 | 6 4+1| 00003DB0: 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 |. | 00003DC0: 20 20 20 20 20 20 20 20 20 20 41 42 41 43 20 20 | ABAC | 00003DD0: 20 20 37 20 20 20 20 20 20 20 36 2B 31 0D 0D 20 | 7 6+1.. | 00003DE0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 CF | .| 00003DF0: 52 20 49 46 20 59 4F 55 20 50 52 45 46 45 52 20 |R IF YOU PREFER | 00003E00: 54 52 45 45 53 3A 0D 0D 20 20 20 20 20 20 20 20 |TREES:.. | 00003E10: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 41 | A| 00003E20: 3D 31 20 2D 20 42 3D 34 20 2D 20 41 3D 36 20 2D |=1 - B=4 - A=6 -| 00003E30: 20 43 3D 37 0D 20 20 20 20 20 20 20 20 20 20 20 | C=7. | 00003E40: 20 20 20 20 20 20 20 20 20 20 2F 0D 20 20 20 20 | /. | 00003E50: 20 20 20 20 20 20 20 20 20 20 20 20 52 4F 4F 54 | ROOT| 00003E60: 20 2D 20 42 3D 32 20 2D 20 41 3D 35 0D 20 20 20 | - B=2 - A=5. | 00003E70: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00003E80: 20 20 5C 0D 20 20 20 20 20 20 20 20 20 20 20 20 | \. | 00003E90: 20 20 20 20 20 20 20 20 20 20 20 43 3D 33 0D 0D | C=3..| 00003EA0: 20 20 20 20 D4 48 49 53 20 47 4F 45 53 20 4F 4E | .HIS GOES ON| 00003EB0: 20 55 4E 54 49 4C 20 54 48 45 20 53 54 52 49 4E | UNTIL THE STRIN| 00003EC0: 47 20 54 41 42 4C 45 20 49 53 20 46 55 4C 4C 2E |G TABLE IS FULL.| 00003ED0: 20 C9 46 20 54 48 45 52 45 20 49 53 20 45 4E 4F | .F THERE IS ENO| 00003EE0: 55 47 48 20 52 45 50 45 54 49 54 49 4F 4E 0D 49 |UGH REPETITION.I| 00003EF0: 4E 20 54 48 45 20 49 4E 50 55 54 20 46 49 4C 45 |N THE INPUT FILE| 00003F00: 2C 20 4C 4F 4E 47 20 53 45 51 55 45 4E 43 45 53 |, LONG SEQUENCES| 00003F10: 20 4F 46 20 43 48 41 52 41 43 54 45 52 53 20 43 | OF CHARACTERS C| 00003F20: 41 4E 20 42 45 20 52 45 50 4C 41 43 45 44 20 42 |AN BE REPLACED B| 00003F30: 59 20 53 48 4F 52 54 20 39 2D 31 32 0D 42 49 54 |Y SHORT 9-12.BIT| 00003F40: 20 43 4F 44 45 53 20 41 4E 44 20 53 49 47 4E 49 | CODES AND SIGNI| 00003F50: 46 49 43 41 4E 54 20 53 41 56 49 4E 47 53 20 43 |FICANT SAVINGS C| 00003F60: 41 4E 20 42 45 20 41 43 48 49 45 56 45 44 2E 0D |AN BE ACHIEVED..| 00003F70: 0D 20 20 20 20 C1 D2 C3 20 53 54 41 52 54 53 20 |. ... STARTS | 00003F80: 4F 55 54 20 42 59 20 49 4E 49 54 49 41 4C 49 5A |OUT BY INITIALIZ| 00003F90: 49 4E 47 20 49 54 53 20 53 54 52 49 4E 47 20 54 |ING ITS STRING T| 00003FA0: 41 42 4C 45 20 54 4F 20 32 35 36 20 45 4E 54 52 |ABLE TO 256 ENTR| 00003FB0: 49 45 53 3B 20 54 48 45 20 42 59 54 45 0D 56 41 |IES; THE BYTE.VA| 00003FC0: 4C 55 45 53 20 30 20 54 4F 20 32 35 35 2E 20 D3 |LUES 0 TO 255. .| 00003FD0: 49 4E 43 45 20 54 48 45 20 46 49 52 53 54 20 32 |INCE THE FIRST 2| 00003FE0: 35 36 20 43 4F 44 45 53 20 47 45 4E 45 52 41 54 |56 CODES GENERAT| 00003FF0: 45 44 20 57 49 4C 4C 20 54 41 4B 45 20 4F 4E 20 |ED WILL TAKE ON | 00004000: 56 41 4C 55 45 53 20 42 45 54 57 45 45 4E 0D 32 |VALUES BETWEEN.2| 00004010: 35 36 20 41 4E 44 20 35 31 31 2C 20 57 45 20 4F |56 AND 511, WE O| 00004020: 4E 4C 59 20 4E 45 45 44 20 4E 49 4E 45 20 42 49 |NLY NEED NINE BI| 00004030: 54 53 20 46 4F 52 20 54 48 45 20 46 49 52 53 54 |TS FOR THE FIRST| 00004040: 20 32 35 36 20 43 4F 44 45 53 2E 20 D4 48 45 20 | 256 CODES. .HE | 00004050: 4E 45 58 54 20 35 31 32 20 43 4F 44 45 53 0D 57 |NEXT 512 CODES.W| 00004060: 49 4C 4C 20 42 45 20 42 45 54 57 45 45 4E 20 35 |ILL BE BETWEEN 5| 00004070: 31 32 20 41 4E 44 20 31 30 32 33 2C 20 53 4F 20 |12 AND 1023, SO | 00004080: 57 45 20 4F 4E 4C 59 20 4E 45 45 44 20 31 30 20 |WE ONLY NEED 10 | 00004090: 42 49 54 53 20 46 4F 52 20 54 48 45 20 4E 45 58 |BITS FOR THE NEX| 000040A0: 54 20 35 31 32 20 43 4F 44 45 53 2E 0D D4 48 45 |T 512 CODES...HE| 000040B0: 20 53 49 5A 45 20 4F 46 20 54 48 45 20 43 4F 44 | SIZE OF THE COD| 000040C0: 45 20 4B 45 45 50 53 20 47 52 4F 57 49 4E 47 20 |E KEEPS GROWING | 000040D0: 4C 49 4B 45 20 54 48 49 53 20 55 4E 54 49 4C 20 |LIKE THIS UNTIL | 000040E0: 49 54 20 52 45 41 43 48 45 53 20 31 32 20 42 49 |IT REACHES 12 BI| 000040F0: 54 53 20 41 4E 44 20 54 48 45 0D 53 54 52 49 4E |TS AND THE.STRIN| 00004100: 47 20 54 41 42 4C 45 20 49 53 20 46 55 4C 4C 2E |G TABLE IS FULL.| 00004110: 20 D4 48 49 53 20 53 49 47 4E 49 46 49 43 41 4E | .HIS SIGNIFICAN| 00004120: 54 4C 59 20 49 4D 50 52 4F 56 45 53 20 54 48 45 |TLY IMPROVES THE| 00004130: 20 43 4F 4D 50 52 45 53 53 49 4F 4E 20 52 41 54 | COMPRESSION RAT| 00004140: 49 4F 20 57 48 45 4E 0D 43 52 55 4E 43 48 49 4E |IO WHEN.CRUNCHIN| 00004150: 47 20 53 4D 41 4C 4C 20 46 49 4C 45 53 2E 0D 0D |G SMALL FILES...| 00004160: 20 20 20 20 CF 4E 43 45 20 54 48 45 20 53 54 52 | .NCE THE STR| 00004170: 49 4E 47 20 54 41 42 4C 45 20 49 53 20 46 55 4C |ING TABLE IS FUL| 00004180: 4C 2C 20 49 46 20 41 20 43 48 41 52 41 43 54 45 |L, IF A CHARACTE| 00004190: 52 20 49 53 20 45 4E 43 4F 55 4E 54 45 52 45 44 |R IS ENCOUNTERED| 000041A0: 20 46 4F 52 20 54 48 45 20 46 49 52 53 54 0D 54 | FOR THE FIRST.T| 000041B0: 49 4D 45 2C 20 49 54 20 57 49 4C 4C 20 48 41 56 |IME, IT WILL HAV| 000041C0: 45 20 54 4F 20 42 45 20 53 45 4E 54 20 54 4F 20 |E TO BE SENT TO | 000041D0: 54 48 45 20 4F 55 54 50 55 54 20 46 49 4C 45 20 |THE OUTPUT FILE | 000041E0: 41 53 20 41 20 31 32 20 42 49 54 20 43 4F 44 45 |AS A 12 BIT CODE| 000041F0: 3B 20 41 20 35 30 25 20 4C 4F 53 53 21 0D D7 45 |; A 50% LOSS!..E| 00004200: 20 48 41 56 45 20 46 4F 55 4E 44 20 54 48 41 54 | HAVE FOUND THAT| 00004210: 20 54 48 45 20 53 54 52 49 4E 47 20 54 41 42 4C | THE STRING TABL| 00004220: 45 20 55 53 55 41 4C 4C 59 20 46 49 4C 4C 53 20 |E USUALLY FILLS | 00004230: 55 50 20 41 54 20 41 42 4F 55 54 20 36 30 2D 37 |UP AT ABOUT 60-7| 00004240: 30 20 C3 C2 CD 20 44 49 53 4B 0D 42 4C 4F 43 4B |0 ... DISK.BLOCK| 00004250: 53 20 46 4F 52 20 54 45 58 54 2C 20 41 4E 44 20 |S FOR TEXT, AND | 00004260: 41 54 20 41 42 4F 55 54 20 34 30 20 46 4F 52 20 |AT ABOUT 40 FOR | 00004270: 4D 41 43 48 49 4E 45 20 4C 41 4E 47 55 41 47 45 |MACHINE LANGUAGE| 00004280: 2E 20 D9 4F 55 20 4D 41 59 20 4E 4F 54 49 43 45 |. .OU MAY NOTICE| 00004290: 20 54 48 41 54 20 CD CC 0D 50 52 4F 47 52 41 4D | THAT ...PROGRAM| 000042A0: 53 20 4F 46 20 34 30 20 42 4C 4F 43 4B 53 20 4F |S OF 40 BLOCKS O| 000042B0: 52 20 4C 45 53 53 20 55 53 55 41 4C 4C 59 20 43 |R LESS USUALLY C| 000042C0: 52 55 4E 43 48 2C 20 57 48 45 52 45 20 41 53 20 |RUNCH, WHERE AS | 000042D0: 4C 4F 4E 47 45 52 20 CD CC 20 50 52 4F 47 52 41 |LONGER .. PROGRA| 000042E0: 4D 53 20 54 45 4E 44 0D 54 4F 20 42 45 20 53 51 |MS TEND.TO BE SQ| 000042F0: 55 41 53 48 45 44 2E 20 C9 46 20 59 4F 55 20 41 |UASHED. .F YOU A| 00004300: 52 45 20 43 52 55 4E 43 48 49 4E 47 20 54 45 58 |RE CRUNCHING TEX| 00004310: 54 20 46 49 4C 45 53 2C 20 54 48 45 20 43 4F 4D |T FILES, THE COM| 00004320: 50 52 45 53 53 49 4F 4E 20 52 41 54 49 4F 20 49 |PRESSION RATIO I| 00004330: 53 0D 55 53 55 41 4C 4C 59 20 41 42 4F 55 54 20 |S.USUALLY ABOUT | 00004340: 32 2E 30 30 2E 20 CF 4E 43 45 20 54 48 45 20 53 |2.00. .NCE THE S| 00004350: 54 52 49 4E 47 20 54 41 42 4C 45 20 48 41 53 20 |TRING TABLE HAS | 00004360: 42 45 43 4F 4D 45 20 46 55 4C 4C 2C 20 54 48 45 |BECOME FULL, THE| 00004370: 20 43 4F 4D 50 52 45 53 53 49 4F 4E 20 52 41 54 | COMPRESSION RAT| 00004380: 49 4F 0D 57 49 4C 4C 20 53 54 41 52 54 20 54 4F |IO.WILL START TO| 00004390: 20 44 49 4D 49 4E 49 53 48 20 42 45 43 41 55 53 | DIMINISH BECAUS| 000043A0: 45 20 4F 46 20 54 48 49 53 2E 0D 0D 20 20 20 20 |E OF THIS... | 000043B0: C1 D2 C3 20 52 45 53 45 52 56 45 53 20 54 57 4F |... RESERVES TWO| 000043C0: 20 43 4F 44 45 53 20 57 48 45 4E 20 49 54 20 43 | CODES WHEN IT C| 000043D0: 52 55 4E 43 48 45 53 20 41 20 46 49 4C 45 2E 20 |RUNCHES A FILE. | 000043E0: C3 4F 44 45 20 32 35 36 20 49 53 20 52 45 53 45 |.ODE 256 IS RESE| 000043F0: 52 56 45 44 20 54 4F 0D 49 4E 44 49 43 41 54 45 |RVED TO.INDICATE| 00004400: 20 54 48 45 20 45 4E 44 20 4F 46 20 46 49 4C 45 | THE END OF FILE| 00004410: 2E 20 D4 48 49 53 20 49 53 20 4E 45 43 45 53 53 |. .HIS IS NECESS| 00004420: 41 52 59 20 53 49 4E 43 45 20 C1 D2 C3 20 44 4F |ARY SINCE ... DO| 00004430: 45 53 4E 27 54 20 4B 4E 4F 57 20 41 20 46 49 4C |ESN'T KNOW A FIL| 00004440: 45 53 0D 4C 45 4E 47 54 48 20 55 4E 54 49 4C 20 |ES.LENGTH UNTIL | 00004450: 41 46 54 45 52 20 49 54 20 48 41 53 20 42 45 45 |AFTER IT HAS BEE| 00004460: 4E 20 41 52 43 48 49 56 45 44 20 55 53 49 4E 47 |N ARCHIVED USING| 00004470: 20 54 48 45 20 53 49 4E 47 4C 45 20 50 41 53 53 | THE SINGLE PASS| 00004480: 20 43 52 55 4E 43 48 20 4F 50 54 49 4F 4E 2E 0D | CRUNCH OPTION..| 00004490: C3 4F 44 45 20 32 35 37 20 49 53 20 52 45 53 45 |.ODE 257 IS RESE| 000044A0: 52 56 45 44 20 46 4F 52 20 46 55 54 55 52 45 20 |RVED FOR FUTURE | 000044B0: 56 45 52 53 49 4F 4E 53 20 4F 46 20 C1 D2 C3 2C |VERSIONS OF ...,| 000044C0: 20 57 48 49 43 48 20 57 49 4C 4C 20 55 53 45 20 | WHICH WILL USE | 000044D0: 49 54 20 41 53 20 41 20 53 49 47 4E 41 4C 0D 54 |IT AS A SIGNAL.T| 000044E0: 4F 20 54 45 4C 4C 20 54 48 45 20 44 45 43 4F 4D |O TELL THE DECOM| 000044F0: 50 52 45 53 53 4F 52 20 54 4F 20 52 45 53 45 54 |PRESSOR TO RESET| 00004500: 20 54 48 45 20 53 54 52 49 4E 47 20 54 41 42 4C | THE STRING TABL| 00004510: 45 20 4F 4E 43 45 20 54 48 45 20 43 4F 4D 50 52 |E ONCE THE COMPR| 00004520: 45 53 53 49 4F 4E 20 52 41 54 49 4F 0D 53 54 41 |ESSION RATIO.STA| 00004530: 52 54 53 20 54 4F 20 46 41 4C 4C 20 4F 46 46 20 |RTS TO FALL OFF | 00004540: 4F 4E 20 4C 41 52 47 45 20 46 49 4C 45 53 2E 0D |ON LARGE FILES..| 00004550: 0D 20 20 20 C1 4E 4F 54 48 45 52 20 41 4D 41 5A |. .NOTHER AMAZ| 00004560: 49 4E 47 20 54 48 49 4E 47 20 41 42 4F 55 54 20 |ING THING ABOUT | 00004570: 43 52 55 4E 43 48 49 4E 47 20 49 53 20 54 48 45 |CRUNCHING IS THE| 00004580: 20 46 41 43 54 20 54 48 41 54 20 49 54 20 49 53 | FACT THAT IT IS| 00004590: 20 4E 4F 54 20 56 45 52 59 0D 45 46 46 49 43 49 | NOT VERY.EFFICI| 000045A0: 45 4E 54 21 20 CE 4F 20 41 54 54 45 4D 50 54 20 |ENT! .O ATTEMPT | 000045B0: 49 53 20 4D 41 44 45 20 54 4F 20 46 49 4E 44 20 |IS MADE TO FIND | 000045C0: 54 48 45 20 4D 4F 53 54 20 4F 46 54 45 4E 20 4F |THE MOST OFTEN O| 000045D0: 43 43 55 52 49 4E 47 20 43 48 41 52 41 43 54 45 |CCURING CHARACTE| 000045E0: 52 0D 53 45 51 55 45 4E 43 45 53 20 49 4E 20 54 |R.SEQUENCES IN T| 000045F0: 48 45 20 46 49 4C 45 2E 20 D4 48 45 20 CC DA D7 |HE FILE. .HE ...| 00004600: 20 41 50 50 52 4F 41 43 48 20 53 49 4D 50 4C 59 | APPROACH SIMPLY| 00004610: 20 54 41 4B 45 53 20 54 48 49 4E 47 53 20 41 53 | TAKES THINGS AS| 00004620: 20 54 48 45 59 20 43 4F 4D 45 2E 20 C1 20 4C 4F | THEY COME. . LO| 00004630: 4E 47 0D 41 4E 44 20 56 45 52 59 20 49 4E 46 52 |NG.AND VERY INFR| 00004640: 45 51 55 45 4E 54 4C 59 20 4F 43 43 55 52 49 4E |EQUENTLY OCCURIN| 00004650: 47 20 43 48 41 52 41 43 54 45 52 20 53 45 51 55 |G CHARACTER SEQU| 00004660: 45 4E 43 45 20 43 4F 55 4C 44 20 42 45 20 54 41 |ENCE COULD BE TA| 00004670: 4B 49 4E 47 20 55 50 20 56 41 4C 55 41 42 4C 45 |KING UP VALUABLE| 00004680: 0D 53 50 41 43 45 20 49 4E 20 54 48 45 20 53 54 |.SPACE IN THE ST| 00004690: 52 49 4E 47 20 54 41 42 4C 45 2C 20 57 48 45 4E |RING TABLE, WHEN| 000046A0: 20 4F 54 48 45 52 20 46 52 45 51 55 45 4E 54 4C | OTHER FREQUENTL| 000046B0: 59 20 4F 43 43 55 52 52 49 4E 47 20 53 45 51 55 |Y OCCURRING SEQU| 000046C0: 45 4E 43 45 53 20 48 41 56 45 20 54 4F 20 42 45 |ENCES HAVE TO BE| 000046D0: 0D 43 4F 44 45 44 20 41 53 20 49 4E 44 49 56 49 |.CODED AS INDIVI| 000046E0: 44 55 41 4C 20 43 4F 44 45 53 20 4F 4E 43 45 20 |DUAL CODES ONCE | 000046F0: 54 48 45 20 54 41 42 4C 45 20 49 53 20 46 55 4C |THE TABLE IS FUL| 00004700: 4C 2E 20 D7 48 45 4E 20 41 20 46 49 4C 45 20 49 |L. .HEN A FILE I| 00004710: 53 20 56 45 52 59 20 4C 4F 4E 47 2C 20 54 48 45 |S VERY LONG, THE| 00004720: 0D 53 54 52 49 4E 47 20 54 41 42 4C 45 20 4D 41 |.STRING TABLE MA| 00004730: 59 20 48 41 56 45 20 47 49 56 45 4E 20 41 20 47 |Y HAVE GIVEN A G| 00004740: 4F 4F 44 20 43 4F 4D 50 52 45 53 53 49 4F 4E 20 |OOD COMPRESSION | 00004750: 52 41 54 49 4F 20 4E 45 41 52 20 54 48 45 20 42 |RATIO NEAR THE B| 00004760: 45 47 49 4E 4E 49 4E 47 20 4F 46 20 54 48 45 0D |EGINNING OF THE.| 00004770: 46 49 4C 45 20 42 55 54 20 54 48 45 20 53 54 52 |FILE BUT THE STR| 00004780: 49 4E 47 20 54 41 42 4C 45 20 4D 41 59 20 4E 4F |ING TABLE MAY NO| 00004790: 20 4C 4F 4E 47 45 52 20 52 45 46 4C 45 43 54 20 | LONGER REFLECT | 000047A0: 54 48 45 20 46 49 4C 45 53 20 43 48 41 52 41 43 |THE FILES CHARAC| 000047B0: 54 45 52 49 53 54 49 43 53 20 4E 45 41 52 0D 54 |TERISTICS NEAR.T| 000047C0: 48 45 20 45 4E 44 20 4F 46 20 54 48 45 20 46 49 |HE END OF THE FI| 000047D0: 4C 45 2E 0D 0D 20 20 20 20 C4 45 53 50 49 54 45 |LE... .ESPITE| 000047E0: 20 54 48 45 20 46 41 43 54 20 54 48 41 54 20 43 | THE FACT THAT C| 000047F0: 52 55 4E 43 48 49 4E 47 20 47 49 56 45 53 20 51 |RUNCHING GIVES Q| 00004800: 55 49 54 45 20 47 4F 4F 44 20 43 4F 4D 50 52 45 |UITE GOOD COMPRE| 00004810: 53 53 49 4F 4E 20 52 41 54 49 4F 53 2C 20 54 48 |SSION RATIOS, TH| 00004820: 45 52 45 0D 49 53 20 4C 4F 54 53 20 4F 46 20 52 |ERE.IS LOTS OF R| 00004830: 4F 4F 4D 20 46 4F 52 20 49 4D 50 52 4F 56 45 4D |OOM FOR IMPROVEM| 00004840: 45 4E 54 2E 20 D7 45 20 43 4F 55 4C 44 20 42 45 |ENT. .E COULD BE| 00004850: 20 4D 4F 52 45 20 53 45 4C 45 43 54 49 56 45 20 | MORE SELECTIVE | 00004860: 41 42 4F 55 54 20 54 48 45 20 53 54 52 49 4E 47 |ABOUT THE STRING| 00004870: 53 20 57 45 0D 41 4C 4C 4F 57 20 49 4E 20 54 48 |S WE.ALLOW IN TH| 00004880: 45 20 54 41 42 4C 45 2C 20 57 45 20 43 4F 55 4C |E TABLE, WE COUL| 00004890: 44 20 50 55 52 47 45 20 54 48 45 20 54 41 42 4C |D PURGE THE TABL| 000048A0: 45 20 50 45 52 49 4F 44 49 43 41 4C 4C 59 20 46 |E PERIODICALLY F| 000048B0: 4F 52 20 49 4E 46 52 45 51 55 45 4E 54 4C 59 20 |OR INFREQUENTLY | 000048C0: 55 53 45 44 0D 43 4F 44 45 53 2C 20 4F 52 20 57 |USED.CODES, OR W| 000048D0: 45 20 43 4F 55 4C 44 20 53 49 4D 50 4C 59 20 55 |E COULD SIMPLY U| 000048E0: 53 45 20 41 20 4C 41 52 47 45 52 20 53 54 52 49 |SE A LARGER STRI| 000048F0: 4E 47 20 54 41 42 4C 45 2E 0D 0D 20 20 20 20 C1 |NG TABLE... .| 00004900: 52 43 48 49 56 45 20 C6 49 4C 45 20 C6 4F 52 4D |RCHIVE .ILE .ORM| 00004910: 41 54 0D 0D 20 20 20 20 C5 41 43 48 20 41 52 43 |AT.. .ACH ARC| 00004920: 48 49 56 45 20 45 4E 54 52 59 20 43 4F 4E 53 49 |HIVE ENTRY CONSI| 00004930: 53 54 53 20 4F 46 20 41 20 53 48 4F 52 54 20 48 |STS OF A SHORT H| 00004940: 45 41 44 45 52 20 46 4F 4C 4C 4F 57 45 44 20 42 |EADER FOLLOWED B| 00004950: 59 20 54 48 45 20 43 4F 4D 50 52 45 53 53 45 44 |Y THE COMPRESSED| 00004960: 0D 46 49 4C 45 2E 20 C9 46 20 54 48 45 20 46 49 |.FILE. .F THE FI| 00004970: 4C 45 20 49 53 20 53 51 55 45 45 5A 45 44 20 4F |LE IS SQUEEZED O| 00004980: 52 20 53 51 55 41 53 48 45 44 2C 20 54 48 45 20 |R SQUASHED, THE | 00004990: C8 55 46 46 4D 41 4E 20 45 4E 43 4F 44 49 4E 47 |.UFFMAN ENCODING| 000049A0: 20 54 41 42 4C 45 20 41 50 50 45 41 52 53 0D 49 | TABLE APPEARS.I| 000049B0: 4D 4D 45 44 49 41 54 45 4C 59 20 46 4F 4C 4C 4F |MMEDIATELY FOLLO| 000049C0: 57 49 4E 47 20 54 48 45 20 48 45 41 44 45 52 20 |WING THE HEADER | 000049D0: 41 4E 44 20 42 45 46 4F 52 45 20 54 48 45 20 46 |AND BEFORE THE F| 000049E0: 49 4C 45 20 44 41 54 41 2E 20 D4 48 45 20 41 52 |ILE DATA. .HE AR| 000049F0: 43 48 49 56 45 20 48 45 41 44 45 52 0D 43 4F 4E |CHIVE HEADER.CON| 00004A00: 53 49 53 54 53 20 4F 46 20 54 48 45 20 46 4F 4C |SISTS OF THE FOL| 00004A10: 4C 4F 57 49 4E 47 20 42 59 54 45 53 3A 0D 0D 20 |LOWING BYTES:.. | 00004A20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00004A30: 20 4F 46 46 53 45 54 20 20 4C 45 4E 47 54 48 20 | OFFSET LENGTH | 00004A40: 20 20 20 20 44 45 53 43 52 49 50 54 49 4F 4E 0D | DESCRIPTION.| 00004A50: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00004A60: 20 20 2D 2D 2D 2D 2D 2D 20 20 2D 2D 2D 2D 2D 2D | ------ ------| 00004A70: 20 20 20 20 20 2D 2D 2D 2D 2D 2D 2D 2D 2D 2D 2D | -----------| 00004A80: 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 |. | 00004A90: 20 20 20 20 20 30 20 20 20 20 20 20 20 31 20 20 | 0 1 | 00004AA0: 20 20 20 20 20 20 56 45 52 53 49 4F 4E 20 20 31 | VERSION 1| 00004AB0: 20 46 4F 52 20 C1 D2 C3 20 31 2E 58 58 0D 20 20 | FOR ... 1.XX. | 00004AC0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00004AD0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00004AE0: 20 20 20 20 20 20 20 20 20 20 20 20 32 20 46 4F | 2 FO| 00004AF0: 52 20 C1 D2 C3 20 32 2E 58 58 0D 20 20 20 20 20 |R ... 2.XX. | 00004B00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 31 | 1| 00004B10: 20 20 20 20 20 20 20 31 20 20 20 20 20 20 20 20 | 1 | 00004B20: 53 54 4F 52 41 47 45 2E 20 30 3D 53 54 4F 52 45 |STORAGE. 0=STORE| 00004B30: 20 20 31 3D 50 41 43 4B 0D 20 20 20 20 20 20 20 | 1=PACK. | 00004B40: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00004B50: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00004B60: 20 20 20 20 20 20 20 32 3D 53 51 55 45 45 5A 20 | 2=SQUEEZ | 00004B70: 33 3D 43 52 55 4E 43 48 0D 20 20 20 20 20 20 20 |3=CRUNCH. | 00004B80: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00004B90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00004BA0: 20 20 20 20 20 20 20 34 3D 53 51 55 41 53 48 20 | 4=SQUASH | 00004BB0: 35 3D 31 20 50 41 53 53 20 43 52 55 4E 43 48 0D |5=1 PASS CRUNCH.| 00004BC0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00004BD0: 20 20 20 20 32 20 20 20 20 20 20 20 32 20 20 20 | 2 2 | 00004BE0: 20 20 20 20 20 43 48 45 43 4B 53 55 4D 20 4C 4F | CHECKSUM LO| 00004BF0: 2C 48 49 0D 20 20 20 20 20 20 20 20 20 20 20 20 |,HI. | 00004C00: 20 20 20 20 20 20 20 20 34 20 20 20 20 20 20 20 | 4 | 00004C10: 33 20 20 20 20 20 20 20 20 4F 52 49 47 49 4E 41 |3 ORIGINA| 00004C20: 4C 20 4C 45 4E 47 54 48 2D 28 42 59 54 45 53 29 |L LENGTH-(BYTES)| 00004C30: 20 4C 4F 2C 4D 49 44 2C 48 49 0D 20 20 20 20 20 | LO,MID,HI. | 00004C40: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 37 | 7| 00004C50: 20 20 20 20 20 20 20 32 20 20 20 20 20 20 20 20 | 2 | 00004C60: 53 51 55 45 45 5A 45 44 20 4C 45 4E 47 54 48 2D |SQUEEZED LENGTH-| 00004C70: 28 42 4C 4F 43 4B 53 29 20 4C 4F 2C 48 49 0D 20 |(BLOCKS) LO,HI. | 00004C80: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00004C90: 20 20 20 39 20 20 20 20 20 20 20 31 20 20 20 20 | 9 1 | 00004CA0: 20 20 20 20 46 49 4C 45 20 54 59 50 45 2C 20 53 | FILE TYPE, S| 00004CB0: 2C 50 2C 55 2C 20 4F 52 20 52 0D 20 20 20 20 20 |,P,U, OR R. | 00004CC0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 31 30 | 10| 00004CD0: 20 20 20 20 20 20 20 31 20 20 20 20 20 20 20 20 | 1 | 00004CE0: 4C 45 4E 47 54 48 20 4F 46 20 46 49 4C 45 4E 41 |LENGTH OF FILENA| 00004CF0: 4D 45 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 |ME. | 00004D00: 20 20 20 20 20 20 31 31 20 20 20 20 20 20 20 4E | 11 N| 00004D10: 20 20 20 20 20 20 20 20 46 49 4C 45 4E 41 4D 45 | FILENAME| 00004D20: 0D 0D 20 20 20 20 20 20 20 20 D4 48 45 20 46 4F |.. .HE FO| 00004D30: 4C 4C 4F 57 49 4E 47 20 41 44 44 49 54 49 4F 4E |LLOWING ADDITION| 00004D40: 41 4C 20 42 59 54 45 53 20 4F 43 43 55 52 20 49 |AL BYTES OCCUR I| 00004D50: 46 20 56 45 52 53 49 4F 4E 20 49 53 20 32 20 4F |F VERSION IS 2 O| 00004D60: 52 20 48 49 47 48 45 52 2E 0D 0D 20 20 20 20 20 |R HIGHER... | 00004D70: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 31 31 | 11| 00004D80: 2B 4E 20 20 20 20 20 31 20 20 20 20 20 20 20 20 |+N 1 | 00004D90: 52 45 43 4F 52 44 20 4C 45 4E 47 54 48 20 49 46 |RECORD LENGTH IF| 00004DA0: 20 52 45 4C 41 54 49 56 45 20 46 49 4C 45 2E 0D | RELATIVE FILE..| 00004DB0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00004DC0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00004DD0: 20 20 20 20 20 20 20 20 20 20 20 20 28 32 35 34 | (254| 00004DE0: 20 4F 54 48 45 52 57 49 53 45 29 0D 20 20 20 20 | OTHERWISE). | 00004DF0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 31 | 1| 00004E00: 31 2B 4E 2B 31 20 20 20 32 20 20 20 20 20 20 20 |1+N+1 2 | 00004E10: 20 44 41 54 45 20 49 4E 20 CD D3 2D C4 CF D3 20 | DATE IN ..-... | 00004E20: 46 4F 52 4D 41 54 2E 0D 0D 20 20 20 20 20 20 20 |FORMAT... | 00004E30: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00004E40: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00004E50: 20 20 20 42 49 54 53 3A 20 30 2D 34 20 3D 20 44 | BITS: 0-4 = D| 00004E60: 41 59 0D 20 20 20 20 20 20 20 20 20 20 20 20 20 |AY. | 00004E70: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00004E80: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00004E90: 20 20 20 35 2D 38 20 3D 20 4D 4F 4E 54 48 0D 20 | 5-8 = MONTH. | 00004EA0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00004EB0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 | | 00004EC0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 39 | 9| 00004ED0: 2D 31 35 3D 20 59 45 41 52 2D 31 39 38 30 00 0D |-15= YEAR-1980..|
.00,80.STORED IN RAM MAY LOOK SOMETHING
LIKE THE FOLLOWING IF VIEWED WITH THE MA
CHINE.LANGUAGE MONITOR:..
.:2000 00 00 00 00 00 00 00 00 .
.:2008 00 00 FF FF FF FF FF 00.
.:2010 00 00 00 00 00 00 00
00 . .:2018 A0 0B FF FF F
F FF FF FF . AND SO ON
...... THIS COULD BE STORE
D ON DISK AS THE SEQUENCE:..
FE 00 0A FE FF 05 FE 00 09 A0 0B FE F
F 06.. THE FIRST BYTE ($FE) IS A CONT
ROL CHARACTER. WHEN THE UNSQUEEZE ROUTIN
E.ENCOUNTERS A ONE OF THESE IT GETS THE
NEXT TWO CHARACTERS AND INTERPRETS THEM
AS.A CHARACTER IDENTIFIER AND A COUNT. T
HUS THE FIRST 3 BYTE SEQUENCE IS.INTERPR
ETED AS 10 ZEROS, THE NEXT 3 BYTE SEQUEN
CE AS 5 FF'S AND SO ON. WHEN A.CHARACTE
R IS NOT REPEATED, IT IS SIMPLY CODED DI
RECTLY TO THE OUTPUT FILE. (THE.$A0 AT $
2018 ABOVE) AND SO THE ABOVE IS SQUEEZED
FROM 32 BYTES DOWN TO 14... DATABASE
PROGRAMS OFTEN SACRIFICE DISK SPACE IN
ORDER TO GAIN SPEED..RELATIVE FILES, FOR
INSTANCE, STORE THEIR DATA AT THE BEGIN
NING OF EACH RECORD,.AND PAD THE RECORD
WITH ZEROS. SINCE EVERY RECORD IS THE SA
ME LENGTH, THE DOS.CAN EASILY CALCULATE
WHERE EACH RECORD STARTS AND THUS RANDOM
LY SKIP TO ANY.RECORD IN THE FILE. THE M
ANAGER, AND OTHER DATABASE PROGRAMS PAD
THEIR RECORDS.WITH SPACES. IN EITHER CAS
E THERE IS A GREAT DEAL OF SPACE TO BE G
AINED WHEN.PACKING THIS TYPE OF FILE. WE
HAVE SEEN SOME DBASE III FILES IN EXCES
S OF 1.MEGABYTE 'CRUNCH' DOWN TO ONLY 50
,000 CHARACTERS OR SO. MOST OF THIS IS D
UE TO.PACKING... THERE IS ONE SLIGHT
PROBLEM WITH THIS METHOD. SUPPOSE YOU AR
E USING A.ZERO-BYTE AS THE CONTROL CHARA
CTER. IF A SEQUENCE OF ONLY ONE ZERO IS.
ENCOUNTERED, YOU CANNOT CODE IT TO THE O
UTPUT FILE SINCE IT WILL BE INTERPRETED.
AS A CONTROL CHARACTER. YOU MUST SEND A
THREE BYTE CONTROL SEQUENCE TO CODE THE.
SINGLE ZERO. AN EXAMPLE OF THIS WOULD BE
AS FOLLOWS:.. .:0801 06 0
8 01 00 8F 00 0C 08 . .:08
09 02 00 8F 00 12 08 03 00.
.:0811 8F 00 00 00 00 00 00 00 AN
D SO ON...... THIS WOULD B
E STORED ON DISK AS THE SEQUENCE:..
06 08 01 00 00 01 8F 00 00 01
0C 08 02 00 00 01. 8F 00 0
0 01 12 08 03 00 00 01 8F 00 00 07 .....
.. WE WENT FROM 24 BYTES T
O 30! NOT MUCH OF A SAVINGS... IT IS
BECAUSE OF THIS PROBLEM WITH PACKING THA
T SQUEEZED FILES ARE.OCCASIONALLY SHORTE
R THAN THEIR SQUASHED EQUIVALENT... H
UFFMAN CODING IS SOMEWHAT MORE COMPLEX.
IT IS PROBABLY THE MOST ELEGANT OF.ALL T
HE COMPRESSION METHODS USED AND CERTAINL
Y THE MOST COMMON. IT TAKES.ADVANTAGE OF
THE FACT THAT SOME CHARACTERS ARE USED
MORE OFTEN THAN OTHERS IN.MOST FILES. TE
XT FILES CONTAIN MANY SPACES, AND LETTER
S LIKE A,E OR C ARE MUCH.MORE COMMON THA
N X, Z, OR Q. GRAPHICS FILES CONTAIN MAN
Y ZEROS OR $FF'S AND.MACHINE LANGUAGE PR
OGRAMS TEND TO CONTAIN MORE LDA'S AND ST
A'S THAN EOR'S OR.ROR'S... SUPPOSE NO
W THAT A FILE CONTAINS ONLY THE CHARACTE
RS A THROUGH Z. SINCE.THERE ARE ONLY 26
CHARACTERS USED, A FIVE BIT BINARY NUMBE
R, WHICH CAN TAKE ON.32 POSSIBLE VALUES,
WOULD BE MORE THAN ADEQUATE TO REPRESEN
T EACH CHARACTER. WE.COULD ASSIGN A FIVE
BIT NUMBER TO EACH OF THE CHARACTERS A
TO Z AND GAIN 3 BITS.PER CHARACTER OR 37
.5%.. HUFFMAN CODING TAKES THIS ONE S
TEP FURTHER... SUPPOSE ALSO THAT SOME
OF THE CHARACTERS OCCUR MUCH MORE OFTEN
IN THE FILE.THAN DO OTHERS. WE COULD GA
IN EVEN MORE SPACE IF THE FREQUENTLY OCC
URRING.CHARACTERS WERE ASSIGNED CODES LE
SS THAN FIVE BITS LONG, AND THE LESS FRE
QUENTLY.OCCURRING CHARACTERS WERE ASSI
GNED CODES THAT WERE FIVE OR MORE BITS
LONG..THE HUFFMAN ALGORITHM DOES JUST T
HAT... THE HUFFMAN ALGORITHM CONVE
RTS FIXED LENGTH CODES (8 BIT CHARACTERS
) INTO.CODES WHOSE LENGTH IN BITS IS INV
ERSELY PROPORTIONAL TO THEIR PROBABILITY
OF.OCCURRENCE IN THE DATA FILE. FOR
EXAMPLE, SUPPOSE YOUR DATA FILE LOOKED.S
OMETHING LIKE THIS:..
ABRACADABRA..
THE CHARACTER FREQUENCY DISTRIBUTION
IS AS FOLLOWS:..
TOTAL BITS TOTAL BI
TS. CHARACTER FREQUENCY HUFFMA
N CODE UNSQUEEZED SQUEEZED. -
-------- --------- ------------ -------
--- -----------. A 5
0 8 * 5 = 40 1 * 5 =
5. B 2 10
8 * 2 = 16 2 * 2 = 4.
R 2 111 8 * 2 =
16 3 * 2 = 6. C 1
1100 8 * 1 = 8 4 * 1 = 4
. D 1 1101
8 * 1 = 8 4 * 1 = 4. ALL
OTHERS 0 ---------
- ----------.
TOTALS: 88 23.
. WE COULD REPRESENT THIS
INFORMATION AS A BINARY TREE:..
C.
/.
A B
/---- D.
/ / /. RO
OT --- --- --- R.. TO GET THE HUFFMA
N CODE WE CODE A 0 BIT EACH TIME WE TRAV
ERSE A BRANCH TO.THE LEFT, AND A 1 BIT E
ACH TIME WE TRAVERSE A BRANCH TO THE RIG
HT. THUS THE.CODES ARE GENERATED AS IN T
HE TABLE ABOVE AND EVERY CHARACTER GETS
A UNIQUE.CODE. THE DECOMPRESSOR SIMPLY S
TARTS AT THE ROOT, READS THE SQUEEZED FI
LE ONE.BIT AT A TIME, AND MOVES THROUGH
THE TREE UNTIL IT REACHES A TERMINAL NOD
E AND.THEN SENDS THE CHARACTER IN THAT P
OSITION TO THE OUTPUT FILE... THE MOS
T FREQUENTLY OCCURRING CHARACTERS ARE KE
PT CLOSEST TO THE ROOT AND.THUS HAVE SHO
RTER CODES. THOSE WITH LOWER FREQUENCIES
OF OCCURRENCE ARE KEPT.FURTHER AWAY AND
GET LONGER CODES. THE RESULT IS OFTEN A
FILE THAT IS.SIGNIFICANTLY SHORTER THAN
THE ORIGINAL... WHEN ALL BYTES OCCUR
WITH ABOUT THE SAME FREQUENCY, AS IN MA
CHINE LANGUAGE.PROGRAM FILES, THEN ALL T
HE CODES ARE ABOUT THE SAME LENGTH AND N
OT MUCH IS.GAINED. IN FACT, SINCE THE DE
-CODING INFORMATION (THE TREE) MUST BE I
NCLUDED IN.THE OUTPUT FILE, THE RESULT C
AN OFTEN BE LONGER, PARTICULARLY ON SHOR
T FILES... FOR THOSE OF YOU THAT ARE
INTERESTED IN STATISTICS, WE HAVE INCLUD
ED A SMALL.UTILITY PROGRAM WITH ARC THAT
ANALYZES THE FREQUENCY DISTRIBUTION OF
THE BYTES.IN A FILE AND GRAPHICALLY DISP
LAYS THE RESULTS. ON THE TOP PORTION OF
THE SCREEN.YOU WILL SEE THE FREQUENCY DI
STRIBUTION OF THE BYTES IN THE FILE. ON
THE BOTTOM.PORTION IS A BAR GRAPH REPRES
ENTING THE LENGTHS OF THE HUFFMAN CODES
GENERATED.BY THE SQUEEZE ALGORITHM. A HU
FFMAN CODE CAN BE ANYWHERE FROM 0 TO 24
BITS IN.LENGTH. EACH BIT IN THE HUFFMAN
CODE IS REPRESENTED BY TWO PIXELS ON THE
.GRAPHICS SCREEN. TO RUN THE UTILITY YOU
MUST HAVE ARC IN MEMORY AND TYPE:..
A:ANALYZE [D:]FILENAME.. T
HE PROGRAM WILL THEN READ THROUGH 'D:FIL
ENAME' AND DISPLAY A FREQUENCY.DISTRIBUT
ION FOR THE FILE... BUT HOW DO WE COM
E UP WITH THE BEST TREE TO USE TO GENERA
TE THE HUFFMAN.CODES? IF YOU SIT DOWN AN
D THINK ABOUT IT YOU WILL REALIZE THAT E
VEN IF ONLY A.DOZEN OR SO BYTES ARE USED
, THE NUMBER OF POSSIBLE TREES IS QUITE
LARGE... HUFFMAN SQUEEZING GETS IT NA
ME FROM THE MAN THAT CAME UP WITH A SOLU
TION TO.THIS PROBLEM. WE ACTUALLY TRIED
TO FIGURE IT OUT FOR OURSELVES AND ENDED
UP.UTTERLY CONFUSED UNTIL WE CAME ACROS
S HUFFMAN'S ARTICLE(2). HUFFMAN MAKES IT
.LOOK SIMPLE... LETS GO BA
CK TO OUR PREVIOUS EXAMPLE OF "ABRACADAB
RA"... WE START OUT WITH T
HE FOLLOWING FREQUENCY DISTRIBUTION:..
CHARACTER
FREQUENCY. -
-------- ---------.
A 5.
B
2. R
2.
C 1.
D 1.. WE STA
RT BY PICKING OFF THE TWO LOWEST FREQUEN
CIES AND FORMING A PARTIAL.TREE WITH THE
M. IN THIS CASE "C" AND "D". THIS GIVES
US A NEW TABLE:.._. 2. HUFFMAN,
D.A., "A METHOD FOR THE CONSTRUCTION OF
MINIMUM REDUNDANCY.CODES", PROC. IRE, 4
0(9), 1098-1101(1952)..
CHARACTER FREQUENCY.
--------- -
--------.
A 5.
B 2.
R 2.
C,D
2.. AND WE HAVE A PARTI
AL TREE:..
D. /.
ROOT - C..
NOW WE REPEAT THE PROCEDURE. THIS TIME
, HOWEVER, WE HAVE MORE THAN ONE.CHOICE.
WE COULD CHOOSE "B" AND "R", OR "B" AND
"C,D" OR "R" AND "C,D". AS FAR.AS THE R
ESULTING FILE IS CONCERNED, IT MAKES NO
DIFFERENCE WHICH ONE WE CHOOSE..THE SQUE
EZED FILES LENGTH WILL BE THE SAME! LETS
DO IT TWO DIFFERENT WAYS JUST.TO SEE WH
AT HAPPENS... CHARACTER
FREQUENCY CHARACTER FREQUENCY.
--------- ---------
--------- ---------.
A 5 A 5
. B,R 4
C,D,R 4.
C,D 2 B 2
.. WHICH GIVES:..
B C
R D. /
/ / /.
ROOT - R ROOT - D
ROOT - - C..... AND AGAI
N:.. CHARACTER FREQUENC
Y CHARACTER FREQUENCY.
--------- --------- ---------
---------. C,D,B,R
6 C,D,B,R 6.
A 5 A
5.. WHICH GIVES:
.. D.
/.
/--C. /.
/ B OR: B
R D. / /
/ / /. R
OOT -- - R ROOT - - - - C..
AND FINALLY WE COMBINE TH
ESE TO GET:..
D. /.
/--C.
/. A / B
OR: A B R D.
/ / / /
/ / /. ROOT - - - - -R
ROOT - - - - - C..
WE END UP WITH THE FOLLOWING TABLE
S:.. CHARACTER FREQUEN
CY CODE1 CODE2 .
--------- --------- -----
-----. A
5 0 0 .
B 2 110
10. R
2 111 110 .
C 1 10
1 1111. D
1 100 1110..
IF YOU MULTIPLY THE CODE LENGTH TIMES TH
E FREQUENCY FOR EACH CHARACTER AND.SUM T
HE RESULTS, YOU WILL GET THE FILES SQUEE
ZED LENGTH IN BITS. YOU WILL FIND.THAT I
T IS THE SAME IN BOTH CASES. ARC WILL,
HOWEVER, ALWAYS CHOOSE THE OPTION.WHICH
RESULTS IN THE SHORTEST CODE LENGTHS. AR
C ONLY ALLOWS A MAXIMUM CODE.LENGTH OF 2
4 BITS. NOTE ALSO THAT THERE ARE A TOTAL
OF ONLY 13 BITS ON THE LEFT,.BUT 14 ON
THE RIGHT. THIS ALSO MAKES THE LENGTH OF
THE ENCODING TABLE A BIT.SHORTER. NO PU
N INTENDED... SINCE WE ARE BUILDING T
HE CODES TWO GROUPS AT A TIME, THE TIME
THAT IT TAKES.TO GENERATE THE CODES IS D
IRECTLY PROPORTIONAL TO THE NUMBER OF EN
TRIES IN THE.TABLE. AFTER ARC FINISHES I
TS ANALYZE PASS, YOU WILL NOTICE A DELAY
OF A SECOND.OR TWO BEFORE ARC ACTUALLY
STARTS SQUEEZING A FILE. FOR TEXT FILES,
THE DELAY IS.SHORT BECAUSE THE TABLE IS
N'T VERY LONG. FOR PROGRAMS, HOWEVER, TH
E DELAY IS.QUITE NOTICEABLE BECAUSE ALL
256 POSSIBLE BYTE VALUES ARE USUALLY USE
D... TREES ARE AN EXCELLENT TOOL TO U
NDERSTANDING THE THEORY BEHIND HUFFMAN.S
QUEEZING. ODDLY ENOUGH, ARC DOESN'T USE
THIS CONCEPT TO ANY ADVANTAGE AT ALL...
LEMPEL-ZEV-WELCH(3), OR LZW COMPRESSI
ON IS USED TO 'CRUNCH' FILES. IT IS.REAL
LY QUITE AMAZING SINCE IT ALMOST ALWAYS
IS CHOSEN AS THE MOST EFFICIENT.COMPRESS
OR AND CAN BE PERFORMED 'ON THE FLY' WIT
HOUT FIRST HAVING TO ANALYZE A.FILES CON
TENTS. IT TAKES ADVANTAGE OF THE FACT TH
AT CERTAIN SEQUENCES OF BYTES.OCCUR MORE
OFTEN THAN OTHERS IN TYPICAL DATA FILES
... FOR EXAMPLE, IN AN ASCII LISTING
OF A BASIC PROGRAM, THE BASIC KEYWORDS,.
INPUT, GOTO, GOSUB AND OTHERS OCCUR WITH
ABUNDANCE. IN THIS DOCUMENT, WORDS LIKE
."ARC", "COMPRESS", "SQUEEZE", OR CHARAC
TERS SEQUENCES LIKE ". " OR ", " OCCUR.Q
UITE OFTEN. IF WE COULD REPLACE THESE CH
ARACTER SEQUENCES WITH SHORTER CODES,.WE
WOULD END UP WITH A SHORTER OUTPUT FILE
. WHEN YOU ENTER A LINE OF BASIC CODE,.T
HE BASIC INTERPRETER DOES JUST THAT BY L
OOKING TO SEE IF ANY OF KEYWORDS IN THE.
LINE OCCUR IN ITS KEYWORD TABLE. ARC DOE
S SOMETHING SIMILAR, BUT PREPARES THE.KE
YWORD TABLE FROM SCRATCH FOR EACH FILE I
T CRUNCHES... THE LZW ALGORITHM READS
THE INPUT FILE SEQUENTIALLY AND REMEMBE
RS SEQUENCES.OF CHARACTERS THAT HAVE OCC
URRED PREVIOUSLY IN THE FILE AND REPLACE
S SUBSEQUENT.OCCURRENCES WITH SHORTER CO
DES. IT PREPARES A 'STRING TABLE' AS IT
GOES THROUGH.THE FILE WHICH IS USED TO G
ENERATE THE CODES. AGAIN, WE COULD THINK
OF THE.STRING TABLE AS A TREE, BUT THIS
TIME IT IS A MUCH MORE COMPLICATED TREE
SINCE.EACH NODE CAN HAVE AS MANY AS 256
BRANCHES!.. LETS TAKE A SIMPLIFIED E
XAMPLE... SUPPOSE THAT THE ALPHABET C
ONSISTED ONLY OF THE LETTERS A,B, AND C
AND OUR.FILE IS "ABABABACABABAA"... W
E START BY ASSIGNING A CODE TO EACH LETT
ER IN OUR ALPHABET. THUS A=1 B=2.AND C=3
... THE FIRST CHARACTER WE ENCOUNTER
IS AN "A". IT IS IN THE STRING TABLE, SO
WE.SAVE THE "A" AS A PREFIX STRING AND
GET ANOTHER CHARACTER WHICH WE CALL THE.
EXTENSION. THE NEXT CHARACTER IS A "B",
SO WE NOW HAVE THE SEQUENCE "AB", WHICH.
IS NOT IN THE STRING TABLE. WHENEVER THE
CURRENT PREFIX+EXTENSION STRING WE HAVE
.IN MEMORY IS NOT IN THE STRING TABLE, W
E DO THREE THINGS. WE SEND THE CODE FOR.
THE PREFIX TO THE OUTPUT FILE, ADD THE
PREFIX+EXTENSION STRING TO OUR STRING.TA
BLE, AND MAKE THE EXTENSION THE NEW PREF
IX. THUS WE CODE OUT A "1" AND SET THE.P
REFIX EQUAL TO "2", THE CODE FOR "B" AND
ADD "AB" TO THE STRING TABLE AS CODE.4.
...._. 3. WELCH, TERRY A., "A T
ECHNIQUE FOR HIGH PERFORMANCE DATA.
COMPRESSION", IEEE COMPUTER, JUNE 1
984... WE NOW HAVE "B" AS THE PREFIX,
AND READ IN THE NEXT CHARACTER FROM THE
INPUT.FILE AS OUR NEW EXTENSION. THE NE
XT CHARACTER IS AN "A". "BA" IS NOT IN T
HE.STRING TABLE, SO WE CODE OUT THE "B"
, ADD "BA"=5 TO THE STRING TABLE, AND MA
KE."A" THE NEW PREFIX... NOW IS WHEN
IT STARTS TO GET INTERESTING. WE NOW HAV
E "A" AS THE PREFIX AND.READ IN "B" AS
THE NEXT EXTENSION. THIS TIME "AB" IS IN
THE STRING TABLE, SO WE.MAKE THE CODE F
OR "AB" THE NEW PREFIX AND GET ANOTHER E
XTENSION. THE NEXT.CHARACTER IS AN "A",
"ABA" IS NOT IN THE STRING TABLE SO WE S
END THE PREFIX CODE."AB"=4 TO THE OUTPUT
FILE AND ADD "ABA"=6 TO OUR STRING TABL
E. NEXT TIME WE.ENCOUNTER THE SEQUENCE "
ABA", WE'LL ONLY HAVE TO SEND ONE CODE I
N THE PLACE OF.THREE CHARACTERS!.. TH
E PREFIX IS NOW "A". WE GET THE NEXT CHA
RACTER "B". "AB" IS IN THE STRING.TABLE,
SO WE MAKE "AB"=4 THE PREFIX AND GET AN
OTHER CHARACTER. THIS TIME ITS AN."A". "
ABA" IS ALSO IN THE STRING TABLE, SO WE
WE MAKE "ABA"=6 OUR PREFIX AND GET.ANOTH
ER EXTENSION. THIS TIME ITS A "C", SO WE
CODE OUT THE PREFIX 6 AND MAKE "C".THE
NEW PREFIX... AT THIS POIN
T OUR STRING TABLE LOOKS LIKE THIS:..
STRING CODE PR
EFIX+EXTENSION. --
---- ---- ----------------.
A 1.
B 2.
C 3.
AB 4 1+2.
BA 5 2+1.
ABA 6 4+1.
ABAC 7 6+1..
OR IF YOU PREFER TREES:..
A=1 - B=4 - A=6 -
C=7. /.
ROOT - B=2 - A=5.
\. C=3.. THIS
GOES ON UNTIL THE STRING TABLE IS FULL.
IF THERE IS ENOUGH REPETITION.IN THE IN
PUT FILE, LONG SEQUENCES OF CHARACTERS C
AN BE REPLACED BY SHORT 9-12.BIT CODES A
ND SIGNIFICANT SAVINGS CAN BE ACHIEVED..
. ARC STARTS OUT BY INITIALIZING ITS
STRING TABLE TO 256 ENTRIES; THE BYTE.VA
LUES 0 TO 255. SINCE THE FIRST 256 CODES
GENERATED WILL TAKE ON VALUES BETWEEN.2
56 AND 511, WE ONLY NEED NINE BITS FOR T
HE FIRST 256 CODES. THE NEXT 512 CODES.W
ILL BE BETWEEN 512 AND 1023, SO WE ONLY
NEED 10 BITS FOR THE NEXT 512 CODES..THE
SIZE OF THE CODE KEEPS GROWING LIKE THI
S UNTIL IT REACHES 12 BITS AND THE.STRIN
G TABLE IS FULL. THIS SIGNIFICANTLY IMPR
OVES THE COMPRESSION RATIO WHEN.CRUNCHIN
G SMALL FILES... ONCE THE STRING TABL
E IS FULL, IF A CHARACTER IS ENCOUNTERED
FOR THE FIRST.TIME, IT WILL HAVE TO BE
SENT TO THE OUTPUT FILE AS A 12 BIT CODE
; A 50% LOSS!.WE HAVE FOUND THAT THE STR
ING TABLE USUALLY FILLS UP AT ABOUT 60-7
0 CBM DISK.BLOCKS FOR TEXT, AND AT ABOUT
40 FOR MACHINE LANGUAGE. YOU MAY NOTICE
THAT ML.PROGRAMS OF 40 BLOCKS OR LESS U
SUALLY CRUNCH, WHERE AS LONGER ML PROGRA
MS TEND.TO BE SQUASHED. IF YOU ARE CRUNC
HING TEXT FILES, THE COMPRESSION RATIO I
S.USUALLY ABOUT 2.00. ONCE THE STRING TA
BLE HAS BECOME FULL, THE COMPRESSION RAT
IO.WILL START TO DIMINISH BECAUSE OF THI
S... ARC RESERVES TWO CODES WHEN IT C
RUNCHES A FILE. CODE 256 IS RESERVED TO.
INDICATE THE END OF FILE. THIS IS NECESS
ARY SINCE ARC DOESN'T KNOW A FILES.LENGT
H UNTIL AFTER IT HAS BEEN ARCHIVED USING
THE SINGLE PASS CRUNCH OPTION..CODE 257
IS RESERVED FOR FUTURE VERSIONS OF ARC,
WHICH WILL USE IT AS A SIGNAL.TO TELL T
HE DECOMPRESSOR TO RESET THE STRING TABL
E ONCE THE COMPRESSION RATIO.STARTS TO F
ALL OFF ON LARGE FILES... ANOTHER AMAZ
ING THING ABOUT CRUNCHING IS THE FACT TH
AT IT IS NOT VERY.EFFICIENT! NO ATTEMPT
IS MADE TO FIND THE MOST OFTEN OCCURING
CHARACTER.SEQUENCES IN THE FILE. THE LZW
APPROACH SIMPLY TAKES THINGS AS THEY CO
ME. A LONG.AND VERY INFREQUENTLY OCCURIN
G CHARACTER SEQUENCE COULD BE TAKING UP
VALUABLE.SPACE IN THE STRING TABLE, WHEN
OTHER FREQUENTLY OCCURRING SEQUENCES HA
VE TO BE.CODED AS INDIVIDUAL CODES ONCE
THE TABLE IS FULL. WHEN A FILE IS VERY L
ONG, THE.STRING TABLE MAY HAVE GIVEN A G
OOD COMPRESSION RATIO NEAR THE BEGINNING
OF THE.FILE BUT THE STRING TABLE MAY NO
LONGER REFLECT THE FILES CHARACTERISTIC
S NEAR.THE END OF THE FILE... DESPITE
THE FACT THAT CRUNCHING GIVES QUITE GOO
D COMPRESSION RATIOS, THERE.IS LOTS OF R
OOM FOR IMPROVEMENT. WE COULD BE MORE SE
LECTIVE ABOUT THE STRINGS WE.ALLOW IN TH
E TABLE, WE COULD PURGE THE TABLE PERIOD
ICALLY FOR INFREQUENTLY USED.CODES, OR W
E COULD SIMPLY USE A LARGER STRING TABLE
... ARCHIVE FILE FORMAT.. EACH ARC
HIVE ENTRY CONSISTS OF A SHORT HEADER FO
LLOWED BY THE COMPRESSED.FILE. IF THE FI
LE IS SQUEEZED OR SQUASHED, THE HUFFMAN
ENCODING TABLE APPEARS.IMMEDIATELY FOLLO
WING THE HEADER AND BEFORE THE FILE DATA
. THE ARCHIVE HEADER.CONSISTS OF THE FOL
LOWING BYTES:.. OFFSET
LENGTH DESCRIPTION.
------ ------ -----------.
0 1 VERSION 1
FOR ARC 1.XX.
2 FOR ARC 2.XX.
1 1 STORAGE.
0=STORE 1=PACK.
2=SQUEEZ 3=CRUNCH
.
4=SQUASH 5=1 PASS CRUNCH.
2 2 CHECKSUM LO
,HI. 4 3
ORIGINAL LENGTH-(BYTES) LO,MID,HI.
7 2 SQUEEZED
LENGTH-(BLOCKS) LO,HI.
9 1 FILE TYPE, S,P,U, OR
R. 10 1
LENGTH OF FILENAME. 11
N FILENAME.. THE FO
LLOWING ADDITIONAL BYTES OCCUR IF VERSIO
N IS 2 OR HIGHER... 11
+N 1 RECORD LENGTH IF RELATIV
E FILE..
(254 OTHERWISE).
11+N+1 2 DATE IN MS-DOS
FORMAT...
BITS: 0-4 = DAY.
5-8 =
MONTH.
9-15= YEAR-1980..
> CLICK IMAGE PREVIEW FOR FULL MODAL