Matrix implemented data compression apparatus and method

Data compression apparatus for compressing an input stream of data characters into an output stream of compressed codes, comprising

• a plurality of coincidence elements corresponding to a respective plurality of strings, a string being comprised of a prefix string of at least one of said data characters followed by an extension character, a prefix string having a prefix code associated therewith, said plurality of coincidence elements providing a respective plurality of coincidence outputs,
• a coincidence element having inputs responsive, respectively, to a representation of a predetermined prefix code and a representation of a predetermined character for energizing the coincidence output thereof upon coincidental energization of the inputs thereof,
• switch means having a plurality of switch inputs and a plurality of switch outputs, said plurality of coincidence outputs being coupled to said plurality of switch inputs, respectively, said switch means being controllably operative for coupling any one of said switch inputs to a selected one of said switch outputs so that said coincidence outputs are selectively coupled to said switch outputs,
• code assignment means for assigning a plurality of codes to said plurality of switch outputs, respectively, so that energization of a coincidence output coupled to a switch output provides a representation of the code assigned to the switch output,
• means for coupling the provided representations of codes assigned to the switch outputs to the prefix code inputs of the coincidence elements,
• means for coupling representations of data characters fetched from said input stream to the character inputs of the coincidence elements,
• means for sequentially fetching data characters from said input stream so as to sequentially energize switch outputs until a coincidence output is energized that is not coupled to a switch output,
• means for outputting the code assigned to the last energized switch output, thereby providing said stream of compressed codes, and
• means for selectively coupling the last energized coincidence output to the switch output corresponding to the next assignable code.

A data compression method for compressing an input stream of data characters into an output stream of compressed codes, comprising

• providing a plurality of coincidence elements corresponding to a respective plurality of strings, a string being comprised of a prefix string of at least one of said data characters followed by an extension character, a prefix string having a prefix code associated therewith, said plurality of coincidence elements providing a respective plurality of coincidence outputs,
• a coincidence element having inputs responsive, respectively, to a representation of a predetermined prefix code and a representation of a predetermined character for energizing tile coincidence output thereof upon coincidental energization of the inputs thereof,
• assigning a plurality of codes to selected coincidence elements, respectively, so that energization of a coincidence output of a selected coincidence element provides a representation of the code assigned thereto,
• coupling the provided representations of codes assigned to the coincidence elements to the prefix code inputs of the coincidence elements,
• coupling representations of data characters fetched from said input stream to the character inputs of the coincidence elements,
• sequentially fetching data characters from said input stream so as to sequentially energize coincidence outputs until a last coincidence output is energized of a coincidence element that does not have a code assigned thereto, and
• outputting the code assigned to the coincidence element having the coincidence output energized prior to said last coincidence output, thereby providing said stream of compressed codes,
• said assigning step including assigning a next assignable code to the coincidence element having said last coincidence output.

A data compression method for compressing an input stream of data characters into an output stream of compressed codes, comprising

• providing a plurality of coincidence elements corresponding to a respective plurality of strings, a string being comprised of a prefix string of at least one of said data characters followed by an extension character, a prefix string having a prefix code associated therewith, said plurality of coincidence elements providing a respective plurality of coincidence outputs,
• a coincidence element having inputs responsive, respectively, to a representation of a predetermined prefix code and a representation of a predetermined character for energizing the coincidence output thereof upon coincidental energization of the inputs thereof,
• providing a switch arrangement having a plurality of switch inputs and a plurality of switch outputs, said plurality of coincidence outputs being coupled to said plurality of switch inputs, respectively, said switch arrangement being controllably operative for coupling any one of said switch inputs to a selected one of said switch outputs so that said coincidence outputs are selectively coupled to said switch outputs,
• assigning a plurality of codes to said plurality of switch outputs, respectively, so that energization of a coincidence output coupled to a switch output provides a representation of the code assigned to the switch output,
• coupling the provided representations of codes assigned to the switch outputs to the prefix code inputs of the coincidence elements,
• coupling representations of data characters fetched from said input stream to the character inputs of the coincidence elements,
• sequentially fetching data characters from said input stream so as to sequentially energize switch outputs until a coincidence output is energized that is not coupled to a switch output,
• outputting the code assigned to the last energized switch output, thereby providing said stream of compressed codes, and
• selectively coupling the last energized coincidence output to the switch output corresponding to the next assignable code.