String collating system for searching for character string of arbitrary length within a given distance from reference string

Claim 1

A character string collating system comprising: an input device receiving a reference character string in a parallel form and serially receiving a character string to be collated, in order and character by character, said input device generating a coincidence signal for each constituent character of said reference character string when a serially received character of said character string to be collated is coincident to a corresponding constituent character of said reference character string; and a character string comparator composed of cells arranged in the form of a matrix having M columns and N rows (where M and N are integers), the cells in each column being coupled to said input device so as to receive the coincidence signal for a corresponding constituent character of said reference character string; each cell f i ,j (i=1 to M-1 and j=1 to N-1) being coupled to a rightward adjacent cell f i ,j+1 through a first transfer means which operates to transfer data stored in the cell f i ,j to said cell f i ,j+1 when the same character as the (j)th character of said reference character string is applied to said input device as one character to be collated, each cell f i ,j being also coupled to a downward adjacent cell f i+1 ,j through a second transfer means which operates to transfer data stored in the cell f i ,j to said cell f i+1 ,j each time one character to be collated is applied to said input device; each cell f i ,j being further coupled to a lower rightward adjacent cell f i+1 ,j+1 through a third transfer means which operates to transfer data stored in the cell f i ,j to said cell f i+1 ,j+1 if a character different from the j(th) character of the reference character string is applied to said input device as one character to be collated each time one character to be collated is applied to said input device; each cell f i ,j being also coupled to the same lower rightward adjacent cell f i+1 ,j+1 through an automatic setting means which operates to set the cells downstream of a set cell in a lower rightward coupling direction after each character to be collated is applied to said input device; whereby, the cells in the Mth column output the result of collation.

Claim 4

A method of determining the distance of a character string to be collated with respect to a reference character string in a character string collating system including an input device and a character string comparator composed of cells arranged in the form of a matrix having M columns and N rows (where M and N are integers), the method comprising the steps of: storing the reference character string, in parallel form, in the input device; serially receiving the character string to be collated into the input device; the input device generating a coincidence signal when a particular character of the character string to be collated is the same as a corresponding character of the reference character string and supplying the coincidence signal to a column of cells associated with the corresponding character of the reference character string; each cell transferring data stored therein to a rightward adjacent cell upon receipt of a coincidence signal; each cell transferring data stored therein to a downward adjacent cell each time the input device receives a character of the character string to be collated; each cell transferring data stored therein to a lower rightward adjacent cell when the coincidence signal is not present and the input device receives a character of the character string to be collated; and each cell, when in a set state, transferring data stored therein to cells in a lower rightward coupling direction when the input device receives a character of the character string to be collated; wherein the cells of the Mth column provide an indication of the distance between the reference character string and the characters of the character string to be collated received by the input device.

Claim 5

A method of determining the distance of a character string to be collated with respect to a reference character string in a character string collating system including an input device and a character string comparator composed of cells arranged in the form of a matrix having M columns and N rows (where M and N are integers), the method comprising the steps of: storing the reference character string, in parallel form, in the input device; serially receiving the character string to be collated into the input device; the input device generating a coincidence signal when a particular character of the character string to be collated is the same as a corresponding character of the reference character string and supplying the coincidence signal to a column of cells associated with the corresponding character of the reference character string; each cell transferring data stored therein to a rightward adjacent cell upon receipt of a coincidence signal; each cell transferring data stored therein to a downward adjacent cell each time the input device receives a character of the character string to be collated; each cell transferring data stored therein to a lower rightward adjacent cell when the coincidence signal is not present and the input device receives a character of the character string to be collated; and each cell, when in a set state, transferring data stored therein to cells in a lower rightward coupling direction when the input device receives a character of the character string to be collated; wherein the cells of the Mth column provide an indication of the distance between the reference character string and the characters of the character string to be collated received by the input device.