Patent ID: 8108387
Filing Date: 2012-01-31
Classification: G06F

Abstract:
1. A character string pattern matching, method recorded on a non-transient computer-readable medium for detecting presence of at least one of N, wherein N is a natural number equal to or greater than 2, patterns in specific text, comprising the steps of: (a) calculating a length of each of the N patterns, and storing a length of a shortest one thereof as a Length of a Shortest Pattern (LSP); (b) creating B, wherein B is a natural number equal to or greater than 2, number of SHIFT tables having all 1-byte characters, which are included in the text, as indices, and initializing values, corresponding to respective indices of each of the B number of SHIFT tables, to the LSP; (c) creating a HASH table having hash values of all character strings having a length of B, which are included in the text, as indices, and a PREFIX table having respective hash values of all character strings having a length of Bp, wherein Bp is a natural number equal to or greater than 2, which are included in the text, as indices; (d) selecting any, one from among the N patterns, calculating shift values of characters at relevant locations while shifting in steps of single spaces from a leftmost location of the character string in a rightward direction across a character string ranging from 0 to location (LSP−1) if a location of a leftmost character of the selected pattern is 0, and updating values of the B number of SHIFT tables; (e) for the pattern selected at the step (d), storing a value of the HASH table, having hash values for character strings, ranging from a right location of the selected pattern to location (LSP−B) to (LSP−1) of the selected pattern, as index values, as a pointer for the selected pattern; (f) for the pattern selected at the step (d), storing a value of the PREFIX table, having hash values for character strings, ranging from a left location of the selected pattern to location 0 to (Bp−1) of the selected pattern, as index values, as a pointer for the selected pattern; (g) repeating the steps (d) to (f) for all the N patterns; and (h) after the step (g), detecting presence of at least one of the N patterns in the text using the B number of SHIFT tables, the HASH table and the PREFIX table, wherein, when each of the B SHIFT tables is defined as the table SHIFT the step (d) comprises the steps of: (d-1) setting location k (d-2) extracting characters corresponding to the location k (d-3) calculating value (LSP−1−k (d-4) comparing the value (LSP−1−k (d-5) if the value k (d-6) repeating the steps (d-3) to (d-5) for all the B number of SHIFT tables; and (d-7) repeating the steps (d-2) to (d-6) while increasing the value k