Method and apparatus for compressing data

Claim 2

A data manipulation apparatus comprising: a) means for receiving a data element; b) storage means for sequentially storing previously received data elements at sequentially addressed fixed locations; said storage means including first sequence means for sequentially and repetitively addressing said locations; c) means for comparing said received data element to said stored data elements to determine whether said received data element matches at least one of said stored data elements and to determine a fixed address of said matching stored data elements; d) detector means including a second sequence means for determining whether said received data element extends a previously stored matching data element string and producing an indicator for each of said fixed locations which is determined to extend a previously stored matching data element, said detector means operating concurrently with said means for comparing; said second sequence means having a plurality of detector cells corresponding to said fixed locations for storing said indicators; and means for sequentially advancing said indicators in said detector cells; e) a plurality of storage cells each receiving an output of one of said detector cells and providing an output representation of said indicators before said sequentially advancing occurs, whereby said output representation is provided if an indicator does not occur after said sequential advancing; f) means for providing a pointer to at least one of said matching stored data elements in response to said output representation, said pointer including said fixed address of said matching stored data elements and a length of said matching stored data elements.

Claim 3

The data manipulation apparatus of claim 1 further comprising means for transmitting any data elements that does not match said stored data elements and for transmitting addresses of matching stored data elements that have been generated.

Claim 4

The data manipulation apparatus of claim 2 wherein the receiving means includes means for receiving said data element as data words in sequence.

Claim 5

The data manipulation apparatus of claim 3 wherein the storage means includes means for sequentially storing previously received data words at sequentially addressed fixed locations.

Claim 6

The data manipulation apparatus of claim 1 wherein said storage means includes a non-shifting content addressable memory.

Claim 7

The data manipulation apparatus of claim 4 wherein the comparing means includes means for sequentially comparing each of said received data words to said stored data words.

Claim 8

The data manipulation apparatus of claim 6 wherein the generating means includes means for generating a length of at least one of said matching stored data elements.

Claim 11

The method of claim 8 further comprising the step of transmitting any data element that does not match said stored data elements and transmitting addresses of matching stored data elements that have been generated.

Claim 12

The method of claim 9 wherein said step of receiving includes receiving data elements as data words in sequence.

Claim 13

The method of claim 10 wherein said step of storing includes sequentially storing previously received data words at sequentially addressable fixed addresses.

Claim 14

The method of claim 11 wherein said step of comparing includes sequentially comparing each of said received data words to said previously stored data words.

Claim 15

The method of claim 12 wherein said step of generating includes generating a length of at least one of said matching stored data elements.

Claim 16

A data processing system comprising: a host computer, said host computer including: a) processing means; b) memory means; c) input means; d) output means; and e) a data manipulation apparatus, said data manipulation apparatus including: i) means for receiving a data element; ii) storage means for sequentially storing previously received data elements at sequentially addressed fixed locations; iii) means for comparing said received data element to said stored data elements to determine whether said received data element matches at least one of said stored data elements and to determine a fixed address of said matching stored data elements; iv) detector means including a second sequence means for determining whether said received data element extends a previously stored matching data element string and producing an indicator for each of said fixed locations which is determined to extend a previously stored matching data element, said detector means of determining operating concurrently with said means for comparing; said second sequence means having a plurality of detector cells corresponding to said fixed locations for storing said indicators; and means for sequentially advancing said indicators in said detector cells; v) a plurality of storage cells each receiving an output of one of said detector cells and providing an output representation of said indicators before said sequentially advancing occurs, whereby said output representation is provided if an indicator does not occur after said sequential advancing; vi) means for providing a pointer to at least one of said matching stored data elements in response to said output representation, said pointer including said fixed address of said matching stored data elements and a length of said matching stored data elements.

Claim 17

A data processing system comprising: a host computer, said host computer including: a) processing means; b) memory means; c) input means; d) output means; and e) a data manipulation apparatus, said data manipulation apparatus including: i) means for receiving a data element; ii) storage means for sequentially storing previously received data elements at sequentially addressed fixed locations; iii) means for comparing said received data element to said stored data elements to determine whether said received data element matches at least one of said stored data elements and to determine a fixed address of said matching stored data elements; iv) detector means including a second sequence means for determining whether said received data element extends a previously stored matching data element string and producing an indicator for each of said fixed locations which is determined to extend a previously stored matching data element, said detector means of determining operating concurrently with said means for comparing; said second sequence means having a plurality of detector cells corresponding to said fixed locations for storing said indicators; and means for sequentially advancing said indicators in said detector cells; v) a plurality of storage cells each receiving an output of one of said detector cells and providing an output representation of said indicators before said sequentially advancing occurs, whereby said output representation is provided if an indicator does not occur after said sequential advancing; vi) means for providing a pointer to at least one of said matching stored data elements in response to said output representation, said pointer including said fixed address of said matching stored data elements and a length of said matching stored data elements.

Claim 18

The data processing system of claim 14 wherein said compression means manipulation apparatus further includes means for transmitting any data element that does not match said stored data elements and for transmitting addresses of matching stored data elements that have been generated.

Claim 19

The data processing system of claim 15 wherein said receiving means further includes means for receiving data elements as data words in sequence.

Claim 20

The data processing system of claim 16 wherein said storage means includes means for sequentially storing previously received data words at sequentially addressed fixed locations.

Claim 21

The data manipulation apparatus of claim 14 wherein said storage means includes a non-shifting content addressable memory.

Claim 22

The data processing system of claim 17 wherein said comparing means includes means for sequentially comparing each of said received data words to said stored data words.

Claim 23

The data processing system of claim 19 wherein said generating means includes means for generating a length of at least one of said matching stored data elements.