Data compressor utilizing switched input coincidence elements arranged in virtual levels

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. An update extended string is recorded in the AND-gate corresponding to the next code to be assigned by coupling, through the prefix code matrix switch, the output of the AND-gate corresponding to the longest matching string to the prefix code input of the AND-gate corresponding to the next code to be assigned. The character decoder output representing the fetched character following the longest matching string is coupled, through the character matrix switch, to the character input of the AND-gate corresponding to the next code to be assigned. A virtual level is assigned to an AND-gate indicative of the number of characters of the string recorded by the AND-gate. The virtual level that is assigned to the AND-gate recording the update extended string is 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.