Multiple sub-string searching

Patent metadata

Field	Value
Publication number	US-10546002-B2
Application number	US-201514842866-A
Country	US
Kind code	B2
Filing date	Sep 2, 2015
Priority date	Jul 6, 2015
Publication date	Jan 28, 2020
Grant date	Jan 28, 2020

Abstract

A method for searching for multiple sub-strings of an original text is provided. A search query is received, wherein the search query includes a plurality of sub-strings. A hash array is allocated. The hash array has a size based, at least in part, on the plurality of sub-strings and an original text. The hash array is populated with a plurality of hash values, wherein the plurality of hash values are generated using a rolling hash function, and wherein each of the plurality of hash values corresponds to a portion of the original text. A plurality of sub-string values are computed based on the plurality of sub-strings. Each of the plurality of sub-strings are determined to occur in the original text based, at least in part, on searching the hash array for the plurality of sub-string values.

First claim

What is claimed is:

1. A method comprising:
receiving, by one or more processors, a search query of an original text, wherein:
the search query comprises a plurality of sub-strings including a first sub-string of a first length and a second sub-string of a second length; and
the first length is different than the second length;

determining, by one or more processors, a number of different sub-string lengths present within the plurality of sub-strings;
allocating, by one or more processors, a hash array having a number of entries, wherein the number of entries is based on (i) the determined number of different sub-string lengths and (ii) a character length of the original text;
populating, by one or more processors, the hash array with a plurality of hash values, wherein:
the plurality of hash values are generated using: (i) a first rolling hash equal to the first length, and a second rolling hash equal to the second length; and
each of the plurality of hash values corresponds to a portion of the original text;

computing, by one or more processors, a plurality of sub-string values based, at least in part, on the plurality of sub-strings; and
determining, by one or more processors, whether each of the plurality of sub-strings occurs in the original text based on searching the hash array for the plurality of sub-string values.

2. The method of claim 1 , further comprising:
determining, by one or more processors, that a first hash value of the hash array matches a first sub-string value of the plurality of sub-string values and, in response, determining, by one or more processors, whether a first portion of the original text corresponding to the first hash value is equal to a first sub-string corresponding to the first sub-string value.

3. The method of claim 2 , further comprising:
determining, by one or more processors, that the first portion of the original text is equal to the first sub-string based, at least in part, on a character-by-character comparison of the first portion of the original text and the first sub-string.

4. The method of claim 1 , wherein searching the hash array for plurality of sub-string values comprises:
initializing, by one or more processors, a TRT array, wherein the TRT array comprises a plurality of action codes;
flagging, by one or more processors, one or more action codes based on the plurality of sub-string values; and
comparing, by one or more processors, the TRT array and the hash array.

5. The method of claim 1 , wherein populating the hash array comprises:
calculating, by one or more processors, a first hash sequence based, at least in part, on portions of the original text having lengths equal to the first length;
calculating, by one or more processors, a second hash sequence based, at least in part, on portions of the original text having lengths equal to the second length; and
compiling, by one or more processors, the hash array by interleaving the hash values of the first hash sequence and the second hash sequence.

6. The method of claim 1 , wherein searching the hash array for plurality of sub-string values comprises:
initializing, by one or more processors, a vector, wherein the vector comprises the plurality of sub-string values; and
comparing, by one or more processors, the vector and the hash array.

7. The method of claim 1 , wherein the plurality of sub-strings further comprises a third sub-string of the first length.

Assignees

• IBM

Inventors

• Cheung Chi-Wai
• Mak Ying-Chau R

Classifications

• G06F16/90344

  by using string matching techniques · CPC title

• G06F16/334 Primary

  Query execution (filtering based on additional data G06F16/335) · CPC title

• G06F16/325 Primary

  Hash tables · CPC title