A divider divides an input data into a plurality of data blocks. A hash calculator calculates a hash value of each data block. A compression dictionary memory stores a compression dictionary that stores a previous input data and includes a shared dictionary shared by different data lengths. A hash table memory stores a hash table that stores an address representing a storage location of the data block corresponding to the hash value on the compression dictionary for each data block and includes a shared table shared by different data lengths. An address acquirer acquires the address corresponding to the data block based on the hash table. A matcher determines sameness between the previous data block indicated by the address and the new input data. An encoder generates a compressed data that includes matching information and a matched portion is converted to the address.