Apparatus and method for compressing data signals and restoring the compressed data signals

A data compression and decompression system for compressing digital data and recovering the original data from the compressed data, said system including means for reading the digital data from a medium to provide a stream of data symbol signals, said data symbol signals being members of an alphabet of symbol signals comprising a predetermined number of symbol signals, said system including compression apparatus responsive to said stream of data symbol signals for providing a compressed stream of code signals corresponding thereto and applying said code signals to a medium, said system further including decompression apparatus responsive to said code signals for recovering the original data therefrom, said compression apparatus comprising:

• means for parsing said stream of data symbol signals into segments, each segment comprising a prefix and the next data symbol signal occurring in said stream after said prefix, said prefix comprising the longest match with a previous segment, said parsing means defining a first search tree having nodes and branches emanating from said nodes, each node having at most one incoming branch, the outgoing branches emanating from a node being representative of said symbol signals of said alphabet, respectively, said nodes having respective node labels associated therewith and respective addresses associated therewith, said first search tree having a unique root node without an incoming branch and leaf nodes without outgoing branches,
• said parsing means comprising means for tracing said stream of data symbol signals through said first search tree along a path from said root node to a leaf node, including means responsive to said stream of data symbol signals for determining the branches of said path in accordance with said symbol signals respectively,
• said parsing means comprising
• first storage means comprising a plurality of storage locations corresponding respectively to said addresses of said nodes of said tree, said storage locations being utilized for storing said node labels, a node label stored at a particular storage location identifying the node whose address corresponds to said particular storage location,
• address generator means for generating an address signal and for providing said address signal to said first storage means for accessing said storage locations thereof, said first storage means providing, in response thereto, the node label stored in the storage location accessed by said address signal, said address generator means being responsive to a node label provided by said first storage means and to a data symbol signal from said stream of data symbol signal for generating said address signal in accordance therewith,
• first detecting means for detecting when an accessed storage location of said first storage means does not contain a node label, said storage location not containing a node label defining a leaf node of said first search tree, and
• node counting means for inserting a node label into said accessed storage location of said first storage means detected by said first detecting means as not containing a node label;
• said address generator means comprising means for sequentially generating said address signals and for providing said address signals to said first storage means, the node label provided by said first storage means in response to an address signal providing the node label for generating the next address signal, said address generator means sequentially generating said address signals in accordance with the node labels sequentially provided by said first storage means respectively and in accordance with successive symbol signals of said stream of data symbol signals respectively, said address generator means sequentially generating said address signals until said first detecting means detects an accessed storage location of said first storage means without a node label;
• and
• means responsive to the address of said accessed storage location not containing a node label for generating a pointer signal in accordance therewith for each said segment, said pointer signal being representative of said previous segment matching said prefix and of said next occurring data symbol signal after said prefix,
• thereby providing pointer signals for segments of said stream of data symbol signals, respectively,
• said pointer signals comprising said compressed stream of code signals.