CN107220333B - A Character Search Method Based on Sunday Algorithm - Google Patents

Abstract

The invention belongs to the field of computer software application, and discloses character searching methods based on a Sunday algorithm, which match a pattern string and a text pattern string by judging whether a combination of the last bit of the text window and the lower bit characters outside the text window appears in the pattern string, wherein if the matching is successful, a program is ended, if the matching is unsuccessful, the text window is moved, and the judgment is continued by using the method until the text window reaches the tail end of the text string or the matching is successful, the program is ended.

Description

A Character Search Method Based on Sunday Algorithm

technical field

The invention relates to character search, in particular to a character search method based on Sunday algorithm, which is used for character search in the field of computer networks.

Background technique

Strings are a common basic concept in computer science, and the search problem is also a basic problem in computer science. With the growing size of the Internet, there is more and more information. How to quickly find the information you want in the massive amount of information is the hotspot of network search research; in this, the string matching algorithm plays a very important role, a Efficient string matching algorithm can greatly improve the efficiency and quality of search. String matching has a wide range of applications in the network field. For example, spell checking, language translation, data compression, search engines, network intrusion detection, etc.

Existing common string matching algorithms include Brute force, KMP, Boyer Moore, Sunday, robin_karp, and bitap. Among them, the Sunday algorithm is a matching scheme with higher average efficiency.

Sunday algorithm is a string pattern matching algorithm proposed by Daniel M.Sunday in 1990. The core idea is: in the matching process, the pattern string is not required to be compared from left to right or from right to left. When it finds a mismatch, the algorithm can skip as many characters as possible to avoid The next step of matching is performed, thereby improving the matching efficiency.

The idea of the Sunday algorithm is very similar to the BM algorithm. When the match fails, the focus is on the next character of the last character in the text string that participates in the match. If the character does not appear in the matching string, skip it directly, that is, the moving step = the length of the matching string + 1; otherwise, the same as the BM algorithm, the moving step = the distance from the rightmost character in the matching string to the end + 1 .

When the pattern string of the Sunday algorithm is very long (in many practical applications, the pattern string will be very long), the probability of the next character outside the text window appearing in the pattern string will be very high, which will increase a lot of invalid matches, so the Sunday algorithm efficiency will be significantly reduced.

SUMMARY OF THE INVENTION

Based on the above technical problems, the present invention provides a character search method based on the Sunday algorithm, thereby solving the technical problem of generating many invalid matches in the character search.

The technical scheme of the present invention is as follows:

A character search method based on Sunday algorithm, including the following steps:

Step 1: use the information of two adjacent characters in the pattern string to construct an auxiliary array, and the pattern string is the character string to be matched;

Step 2: The text window is left aligned with the text string, the text string is the text to be searched, and the text window slides on the text string; the auxiliary array is used to determine the last two characters in the text window Whether it appears in the pattern string; if not, jump to step 4; if it does, align the characters appearing in the pattern string with the last two characters, and judge whether the characters in the corresponding positions of the pattern string and the text string are If it matches, the program ends if the match is successful; if it does not match, jump to step 3;

Step 3: Use the Sunday algorithm to perform the next match and jump. If the Sunday algorithm matches successfully, the program ends; if the Sunday algorithm fails to match, judge whether the length of the Sunday algorithm jump exceeds the length of the text window. If the length of the text window is exceeded, go to step 4; if the length of the text window is not exceeded, repeat step 3;

Step 4: Move the text window to the right by J characters, take the last character in the text window and the character adjacent to the last character outside the text window as the combined character, and use the auxiliary array to determine whether the combined character is in the pattern string. If it appears, jump to step 5; if it does not appear, judge whether the text window exceeds the text string, if it does, the match fails and the program ends; if it does not exceed, repeat the content of step 4; the length of the pattern string and The length of the text window is J characters;

Step 5: The characters appearing in the pattern string are aligned with the combined characters, and it is judged whether the pattern string matches the characters in the corresponding positions of the text string;

Further, the auxiliary array construction method in step 1 is as follows:

S201: Use the ASCII code value of the character in the pattern string and the set index value to calculate the hash value of two adjacent characters in the pattern string, using the following formula:

H[i]=A[i]×index+A[i+1]×(index+1) (1)

Among them, i represents the position number of the character in the pattern string; H[i] represents the hash value of two adjacent characters in the pattern string; A[i] represents the ASCII code value of the i-th character;

S202: the maximum hash value generated by the combination of all characters is used as the number of elements in the auxiliary array, and the size of the hash value generated by the combination of characters is the position sequence number of the element;

S203: Map the hash value calculated in S201 to the auxiliary array, and the specific method is as follows:

The element at the corresponding position of the hash value H[i] is 1. If the hash value H[i] generated by the combination of two or more adjacent characters in the pattern string is the same, then the hash value H[i] corresponds to The element at the position is set to a number greater than 1, and the elements at the remaining positions in the auxiliary array are all 0.

Further, the judging method using the auxiliary array is: calculating the hash value of two adjacent characters that need to be judged in the text string, and using the hash value to find the element on the corresponding position in the auxiliary array, if the element is 1, It means that two adjacent characters in the text string match the pattern string or appear in the pattern string; if the element is 0, it means that the two adjacent characters in the text string do not match the pattern string or do not appear in the pattern string; if If the element is a number greater than 1, it means that the hash value of the combination of characters is the same as that of the other combinations of characters, and the content of step 3 is performed.

To sum up, due to the adoption of the above-mentioned technical solutions, the beneficial effects of the present invention are:

Using the ASCII value and index value of the character to calculate the hash value is simple and easy; using the combination of characters to match can effectively reduce the probability of invalid matching, thereby improving the efficiency of the Sunday algorithm.

Once the pattern string is determined, the auxiliary array is obtained through preprocessing and then matched to improve the efficiency of use in practical applications; such as the detection of malicious code in network intrusion, the search of large texts in paper retrieval, and multi-feature scanning of viruses. The applied pattern string is generally very long, so the application of the present invention can greatly improve the efficiency.

Description of drawings

Fig. 1 is the flow chart of the present invention;

Fig. 2 is the experimental result figure of the present invention

Detailed ways

All features disclosed in this specification, except mutually exclusive features and/or steps, may be combined in any way.

The present invention will be described in detail below with reference to the accompanying drawings.

A character search method based on Sunday algorithm, including the following steps:

Step 1: use the information of two adjacent characters in the pattern string to construct an auxiliary array, and the pattern string is the character string to be matched;

The auxiliary array is constructed as follows:

S201: Use the ASCII code value of the character in the pattern string and the set index value to calculate the hash value of two adjacent characters in the pattern string, using the following formula:

H[i]=A[i]×index+A[i+1]×(index+1) (2)

Among them, i represents the position number of the character in the pattern string; H[i] represents the hash value of two adjacent characters in the pattern string; A[i] represents the ASCII code value of the i-th character;

S202: the maximum hash value generated by the combination of all characters is used as the number of elements in the auxiliary array, and the size of the hash value generated by the combination of characters is the position sequence number of the element;

S203: Map the hash value calculated in S201 to the auxiliary array, and the specific method is as follows:

The element at the corresponding position of the hash value H[i] is 1. If the hash value H[i] generated by the combination of two or more adjacent characters in the pattern string is the same, then the hash value H[i] corresponds to The element at the position is set to a number greater than 1, and the elements at the remaining positions in the auxiliary array are all 0.

Step 2: the text window is left aligned with the text string, the text string is the text to be searched, and the text window slides on the text string; the hash value of the last two characters in the text window is calculated, In the auxiliary array, if the element in the corresponding position of the calculated hash value is 0, it means that the last two characters do not appear in the pattern string, and jump to step 4; if the corresponding position of the calculated hash value is 0 If the element is 1, it means that the last two characters appear in the pattern string, then align the characters appearing in the pattern string with the last two characters, and judge whether the pattern string matches the characters in the corresponding position of the text string, If it matches, the matching program ends; if it does not match, jump to step 3; if the element at the corresponding position of the calculated hash value is a value greater than 1, it means that there is another combined character hash value and this The hash values are the same. To reduce the error rate, go to step 3.

Step 3: Use the Sunday algorithm to perform the next match and jump. If the Sunday algorithm matches successfully, the program ends; if the Sunday algorithm fails to match, judge whether the length of the Sunday algorithm jump exceeds the length of the text window. If the length of the text window is exceeded, go to step 4; if the length of the text window is not exceeded, repeat step 3;

Step 4: Move the text window to the right by J characters, take the last character in the text window and the character adjacent to the last character outside the text window as a combined character, calculate the hash value of the combined character, and use the auxiliary In the array, if the element at the corresponding position of the calculated hash value is 0, it means that the last two characters do not appear in the pattern string, and it is judged whether the text window exceeds the text string. If it exceeds, the matching fails and the program ends; if If it does not exceed, repeat the content of step 4; if the element in the corresponding position of the calculated hash value is 1, it means that the last two characters appear in the pattern string, and jump to step 5; if the calculated hash value is 1 If the element at the corresponding position of the value is a value greater than 1, it means that the hash value of another combined character is the same as the hash value. In order to reduce the error rate, go to step 3; the length of the pattern string is the same as that of the text window. The length is all J characters long;

Step 5: The characters appearing in the pattern string are aligned with the combined characters, and it is judged whether the pattern string matches the characters in the corresponding positions of the text string;

The working principle of the invention is as follows: an auxiliary array is constructed, the text window slides on the text string, and the sliding length is the length of the pattern string; the last character of the text window and the next character outside the text window are combined, and the auxiliary array is used to judge Whether the character combination appears in the pattern string to match the string.

Hereinafter, the present invention will be further described in detail with reference to specific embodiments.

specific embodiment

Specific Example 1

The following is the implementation program of the C language of the present invention:

Specific embodiment 2

The following is a graph of experimental results of the present invention, specifically an efficiency comparison graph with the Sunday algorithm.

Generate 10KB random pure English letters and numbers as text strings, select character strings with specific characteristics as pattern strings, use the original Sunday algorithm and the algorithm adopted by the present invention to search, compare their actual efficiency, and repeat the call 1000 times to find the total time (unit: milliseconds), the following statistical graphs are obtained.

In the figure, A represents the Sunday algorithm, and B represents the algorithm adopted by the present invention;

The pattern string used by cylinder 1 is: abcdef;

Cylinder 2 adopts the pattern string: abcdefghijklmnopqrstuvwxyz;

Cylinder 3 adopts the pattern string as:

abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ;

Cylinder 4 adopts the pattern string as:

abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567

The above are the embodiments of the present invention. The present invention is not limited to the above-mentioned embodiments, and anyone should know that structural changes made under the inspiration of the present invention, and all technical solutions that are the same or similar to those of the present invention, fall within the protection scope of the present invention.

Claims (3)

1, character search method based on Sunday algorithm, which is characterized in that the method comprises the following steps:

step 1: constructing an auxiliary array by using information of two adjacent characters in a pattern string, wherein the pattern string is a character string to be matched;

step 2: the method comprises the following steps that a text window is aligned with a text character string on the left, the text character string is a text to be searched, and the text window slides on the text character string; judging whether the last two characters in the text window appear in the pattern string by using the auxiliary array; if not, jumping to the step 4; if yes, aligning the characters appearing in the pattern string with the last two characters, judging whether the characters on the corresponding positions of the pattern string and the text character string are matched, and if yes, ending the matching success program; if not, jumping to the step 3;

step 3, adopting a Sunday algorithm to carry out matching and jumping for times, if the Sunday algorithm is successfully matched, ending the program, if the Sunday algorithm is unsuccessfully matched, judging whether the jumping length of the Sunday algorithm exceeds the length of a text window, if the jumping length of the Sunday algorithm exceeds the length of the text window, jumping to the step 4, and if the jumping length of the text window is not exceeded, repeating the step 3;

and 4, step 4: moving the text window to the right by J character length, taking the last character in the text window and the character outside the text window and adjacent to the last character as combined characters, and judging whether the combined characters appear in the pattern string by using an auxiliary array; if yes, jumping to the step 5; if not, judging whether the text window exceeds the text character string, if so, ending the matching failure program; if not, repeating the content of the step 4; the length of the mode string and the length of the text window are J characters;

and 5: aligning the characters appearing in the pattern string with the combined characters, and judging whether the characters on the corresponding positions of the pattern string and the text character string are matched or not; if the matching is successful, the matching procedure is ended; and if not, jumping to the step 3.

2. The character searching method based on Sunday algorithm, as claimed in claim 1, wherein the auxiliary array is constructed in the following manner in step 1:

s201: calculating the hash value of two adjacent characters in the pattern string by using the ASCII code value of the characters in the pattern string and the set index value, and adopting the following formula:

H[i]＝A[i]×index+A[i+1]×(index+1)

wherein i represents the position serial number of the character in the pattern string; h [ i ] represents the hash value of two adjacent characters in the pattern string; a [ i ] represents an ASCII code value of the ith character;

s202: the maximum hash value generated by combining all characters in pairs is used as the number of elements in the auxiliary array, and the size of the hash value generated by combining all the characters in pairs is the position serial number of the elements;

s203: mapping the hash value calculated in S201 to the auxiliary array in the following specific manner:

the elements at the positions corresponding to the hash values Hi are 1, if the hash values Hi generated by two or more groups of adjacent character combinations in the pattern string are the same, the elements at the positions corresponding to the hash values Hi are set to be numbers larger than 1, and the elements at the rest positions in the auxiliary array are 0.

3. The character searching method based on Sunday algorithm, as claimed in claim 2, wherein the method for determining by using the auxiliary array comprises calculating the hash value of two adjacent characters to be determined in the text string, searching the element at the corresponding position in the auxiliary array by using the hash value, if the element is 1, then representing that the two adjacent characters in the text string match the pattern string or appear in the pattern string, if the element is 0, then representing that the two adjacent characters in the text string do not match the pattern string or do not appear in the pattern string, and if the element is a number greater than 1, then representing that the hash value of the character combination is the same as that of the other character combinations, then proceeding with the content of step 3.

Images