Character string retrieving circuit and character string retrieving method

Abstract

A character string retrieving circuit includes a delay circuit () for delaying a match/no match signal created in each clock period to indicate whether or not a character matched with a retrieval target exists in a dictionary by one clock period, creating circuits ((),(),() and()) for creating in advance signals of two kinds of a signal (ps]) to assume that a character matched with a retrieval target exists in a dictionary in the clock period and a signal (ps]) to assume that a character matched with a retrieval target does not exist in a dictionary in the clock period as signals to predict retrieved results in a certain clock period later and a selecting circuit ()() for selecting a signal with a correct assumption from the signals of 2 kinds in accordance with the match/no match signal delayed by the delay circuit (), wherein a signal selected by the selecting circuit ()() is used in the next clock period. Thus, in the character string retrieving circuit provided within a data compressing circuit using the LZ77 method, faster character string retrieval can be realized based on pipeline processing.