US 6,788,226 B1 · Data compressor with string code reassignment utilizing switched input coincidence elements

Abstract

A matrix of AND-gates correspond to respective codes to be assigned to strings. The outputs of the AND-gates are selectively coupled to prefix code inputs of the AND-gates through a prefix code matrix switch. A plurality of characters from the input stream are fetched into an input character buffer and applied through respective character decoders and selectively through a character matrix switch to character inputs of the AND-gates. An AND-gate-corresponding to a code assigned to a string that is the longest match to the plurality of fetched characters is thereby enabled. Update extended strings are recorded in the AND-gates, an extended string comprising a longest matching string extended by the data character following the longest matching string. A virtual level is assigned to an AND-gate indicative of the number of characters of the string recorded thereby, the virtual level being one greater than the level that had been assigned to the AND-gate corresponding to the longest match. The virtual level is also indicative of the stage of the input character buffer holding the character following the longest match. An AND-gate is reassigned to an extended string to be recorded when further codes are unavailable for assignment and the output of the AND-gate is not coupled to the prefix code input of another AND-gate.

Claims34

Dependent claims

Apparatus for reassigning string codes in a data compressor that compresses 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 codes to be assigned to 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,
each coincidence element providing a coincidence output and having a prefix code input and a character input for enabling the coincidence element to energize the coincidence output thereof upon coincidental energization of the inputs thereof so that energization of a coincidence output of a coincidence element provides a representation of the code corresponding thereto,
first coupling means for selectively coupling the representations of codes corresponding to the coincidence elements to the prefix code inputs of the coincidence elements,
second coupling means for selectively coupling representations of data characters fetched from said input stream to the character inputs of the coincidence elements,
means for recording extended strings in said coincidence elements, an extended string comprising a longest matching string extended by the data character following said longest matching string, and
means for reassigning a coincidence element to an extended string to be recorded when further codes are unavailable for assignment.

3 more elements

A method for reassigning string codes in a data compressor that compresses 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 codes to be assigned to 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,
each coincidence element providing a coincidence output and having a prefix code input and a character input for enabling the coincidence element to energize the coincidence output thereof upon coincidental energization of the inputs thereof so that energization of a coincidence output of a coincidence element provides a representation of the code corresponding thereto,
selectively coupling through first coupling means, the representations of codes corresponding to the coincidence elements to the prefix code inputs of the coincidence elements,
selectively coupling through second coupling means, representations of data characters fetched from said input stream to the character inputs of the coincidence elements,
recording extended strings in said coincidence elements, an extended string comprising a longest matching string extended by the data character following said longest matching string, and
reassigning a coincidence element to an extended string to be recorded when further codes are unavailable for assignment.

3 more elements

Dependencies are inferred from the claim text.

Data compressor with string code reassignment utilizing switched input coincidence elements

Life of this patent

Data compressor with string code reassignment utilizing switched input coincidence elements

Life of this patent

Abstract

Claims34