CN113590895B - Character string retrieval method - Google Patents

Abstract

The present invention relates to the field of computer information processing, in particular to a character string retrieval method, comprising the following steps: step 1, acquiring feature pairs in a pattern string; step 2, obtaining an optimized order PNext array for matching a record pattern string with a target string; Step 3, obtain the TNext array and the FNext array that record the jump matching distance of the pattern string in the target string; Step 4, when the pattern string is matched from left to right in the target string, if the corresponding character is adapted, according to the prior obtained in step 2 The matching sequence is matched sequentially, and if the corresponding characters do not match, the jump is performed according to the record array obtained in advance in step 3. It solves the problem that once a mismatch occurs in the string retrieval process, a large jump distance cannot be obtained quickly, which leads to frequent backtracking during the retrieval process, and the retrieval efficiency is improved.

Description

A String Retrieval Method

technical field

The invention relates to the field of computer information processing, in particular to a character string retrieval method.

Background technique

String retrieval is a classic problem in the computer field. It has important applications in many scenarios such as information retrieval, virus detection, and gene sequence matching. Existing string retrieval mainly includes precise retrieval and fuzzy retrieval.

Since Boyer-Moore and Knuth-Morris-Pratt proposed the BM algorithm and the KMP algorithm respectively in 1977, the precise retrieval algorithm has been continuously tracked by many scholars. The KMP algorithm proposes a method to avoid target string backtracking based on the traditional simple algorithm. method, so that the efficiency of the algorithm has been improved to a certain extent; the BM algorithm uses back-to-front matching and obtains a larger jump distance according to bad characters and good suffixes, and improves the retrieval efficiency to sub-linear time complexity, that is, the actual The number of retrievals is less than the length of the target string; in 1980, Boyer Moore Horspool improved on the basis of the BM algorithm and proposed the BMH algorithm. BMH no longer focuses on mismatched characters like the BM algorithm. It focuses on bad characters. According to this The last position of the character in the pattern string to calculate the offset length, otherwise the length of the offset pattern string; in addition, there have been many variants of the Karp-Rabin and BM algorithms; in 1990, Daniel M.Sunday in the bad character On the basis of the idea, the Sunday algorithm is proposed, which raises the efficiency of string retrieval to a new level.

However, there is still a problem in the existing technology, that is, there are invalid matches in the matching process. Once a mismatch occurs, it is impossible to quickly obtain a sufficiently large jump distance, thereby increasing frequent backtracking in the retrieval process.

Contents of the invention

Based on the above problems, the present invention provides a string retrieval method, which solves the problem that in the string retrieval process, once a mismatch occurs, the jump distance cannot be quickly obtained, thereby increasing the frequent backtracking in the retrieval process.

In order to solve the above technical problems, the technical scheme adopted in the present invention is as follows:

A character string retrieval method, comprising the steps of:

Step 1, obtain the feature pair in the pattern string;

Step 2, obtaining the optimized sequence PNext array for matching the record pattern string and the target string;

Step 3, obtain the TNext array and the FNext array that record the jump matching distance of the pattern string in the target string;

Step 4. When the pattern string is matched from left to right in the target string, if the corresponding character is matched, it will be matched sequentially according to the matching sequence obtained in step 2. If the corresponding character does not match, it will be matched according to the record array obtained in step 3. Jump match.

Further, in the step 1, the feature pair is the most frequently occurring character pair in the pattern string, the number of feature pairs is not less than 2, the character on the left side of the feature pair is called a feature preorder, and the character on the right is called a feature postorder , the feature preorder and feature postorder are two different characters. Number all feature pairs in the pattern string from right to left, starting from 1, that is, the rightmost feature pair is the first feature pair, if there is more than one character pair with the most number of times, select the rightmost character pair among them as feature pairs. The method of obtaining is as follows:

First initialize a sufficiently large record array and initialize all values to 0, then use pointer i and pointer i+1 to traverse the pattern string from left to right, where i∈[0,PLen-2], PLen is the pattern The length of the string, when pointer i and pointer i+1 traverse to any character pair that satisfies the condition of PStr[i]≠PSr[i+1], add the unique corresponding array element value of these two characters in the record array to 1, where PStr is an array of pattern strings, if the value is greater than or equal to the number num of character pairs that appear most frequently at present, then update num to the value of the current array element, where the initial value of num is 0, and use feature pairs to record The pointers respectively record the characteristic preorder 'C _s ' and characteristic postorder 'C _e ' of the character pair, and update the pointer FirstFeaStr at the same time, where the FirstFeaStr pointer is used to record the position of the first characteristic postorder; when all pattern strings are traversed , if num is greater than 1, the character pair recorded by the record pointer is the feature pair of the pattern string, the number of num records is the total number of feature pairs, and the position recorded by the pointer FirstFeaStr is when the pattern string matches the target The matching starting point of the pattern string, and construct the general PNext, TNext and FNext arrays before the pattern string matches the target string; if num=1 after the traversal is completed, it indicates that there is no feature pair in the pattern string, and the matching starting point is set to the pattern string The rightmost character, and skip the general construction steps of TNext array and PNext array, and then construct special TNext array and PNext array.

Further, in the step 2, after the feature pair is successfully obtained, the matching order of the PNext array record includes the matching sequence of the first feature pair of the pattern string and the target string, the feature pairs and non-characteristic pairs except the first feature in the pattern string The matching order of the feature area and the target string. Construct a PNext array with the same length as the pattern string, use the postorder position of the first feature as the matching starting point, and assign the element in the PNext array at the same position as the matching starting point to the preorder index of the first feature pair, which will be matched with the first feature pair Assign the element at the same position in the preorder of a feature as the postorder index of the next feature pair, and so on; assign the element at the same position as the preorder of the last feature pair to the character index of the first non-characteristic area on the far right of the pattern string , and then assign values to the corresponding positions of the characters in the non-characteristic area from right to left in turn, and assign the corresponding element of each character position to the index of the next adjacent character in the non-characteristic area. And mark the last assigned element in the PNext array as the end sign.

Further, the matching order of the first feature pair of the pattern string and the target string is specifically as follows:

Obtaining the matching order of the first feature pair of the pattern string and the target string is the calculation and assignment process of the corresponding element of the first feature pair of the pattern string in the PNext array. After successfully obtaining the feature pair, the starting point where the pattern string recorded by the pointer FirstFeaStr matches the target string, when constructing the PNext array, use the pointer i to traverse the pattern string array from right to left, and use the pointer P to traverse the PNext array Assignment operation, the traversal starting point is the array index pointed to by the FirstFeaStr pointer. First, assign the array element corresponding to the FirstFeaStr pointer in the PNext array to FirstFeaStr-1, and assign the pointer i and P to the position of the first feature preorder at the same time, and assign the value to i to the array element Index[t], where Index The array is used to record the position of the preorder of the feature, where t is the sequence number of the feature pair, where the initial value of t is 1, and t is added by 1 for each feature pair processed, and the array element Sequence[i] and Sequence[i+1] Assign values of 1 and 2 respectively, where the Sequence array is used to mark the position of the character pair; then, use the pointer i and i+1 to continue traversing the PNext array, when the pointer i finds the character 'C _s ', and the pointer i +1 finds the characteristic postorder character 'C _e ', that is, when traversing to the second characteristic pair, assign the PNext array element pointed to by the pointer P to i+1, and finally assign the P pointer to i+1.

Further, the matching order of the feature pairs or non-feature regions and the target string except the first feature in the pattern string is the calculation and assignment process of the corresponding array elements in the PNext array.

After the calculation and assignment of the corresponding array elements of the first feature pair in the PNext array are completed, the pointer i points to the preorder of the feature of the second feature pair, and the pointer P points to the array position corresponding to the postorder of the second feature in the PNext array. At this time, completion The calculation and assignment of the PNext array elements corresponding to the feature pairs other than the first feature pair, the specific implementation method is as follows:

First, move the pointer i one bit to the left, then assign the array element pointed to by the P pointer in the PNext array to i+1, then point the P pointer to the array position corresponding to i+1, and then use the i pointer and i+1 The pointer continues to traverse to the left. When the pointer i finds the characteristic preorder character 'C _s ', and the pointer i+1 finds the characteristic postorder character 'C _e ', that is, when the next characteristic pair is obtained, the pointer P points to the PNext array The element is assigned the value i+1, and finally the P pointer is assigned the value i+1. At the same time, complete the same calculation and assignment of the Sequence array and the Index array in the matching order of the first feature pair of the acquired pattern string and the target string, and add the calculation and assignment of the record array Distance, that is, Distance[t-1] The assignment is Index[t-1] -Index[t], where the Distance array is used to record the distance between two adjacent features. So back and forth.

After pointer i completes the leftward traversal of the pattern string, the P pointer points to the PNext array position corresponding to the leftmost feature preorder. Traversing, and then completing the calculation and assignment of the PNext array elements corresponding to the non-characteristic area, the specific implementation method is as follows:

When the i pointer points to a non-characteristic area character, first assign the PNext array element pointed to by the P pointer to i, then assign the P pointer to i, and then continue to use the i pointer to traverse to the left to find the next non-characteristic character. So back and forth. When the calculation and assignment of the PNext array elements corresponding to all non-characteristic areas are completed, and the i pointer traverses to the left to the leftmost non-characteristic area character, assign the PNext array pointed to by the i pointer to -1, where -1 is the end of the match mark, which means that when the character matches successfully, all pattern string characters are successfully matched in the target string.

Further, by analyzing the matching process between the pattern string and the target string, it can be known that when the calculation pattern string moves to any position in the target string before the search operation is performed at the pattern string and the target string, when the first feature pair of the pattern string does not match the corresponding character of the target string The best jumping distance that can be provided, the best jumping distance recorded in the FNext array and the character string composed of the characters in the target string corresponding to the positions of the rightmost two or three characters of the pattern string. The optimal jumping distance is from the second rightmost character in the pattern string to the left, and the first character string is the same as the string in the target string corresponding to the position of the rightmost two or three characters of the pattern string. The distance between the rightmost character and the position of the rightmost character of the pattern string in the pattern string. Therefore, in said step 3, the method for obtaining the FNext array of the jump matching distance of the record pattern string in the target string is as follows:

Since there may be all character strings composed of two or three arbitrary characters in the character set of the target string in the target string, before the retrieval operation is performed at the pattern string and the target, all character strings consisting of two or three characters in the character set of the target string are calculated. The best jumping distance that can be provided by a string composed of any characters, and store the best jumping distance that these strings can provide in advance in the FNext array that is mapped one by one by a string and an array element.

First, obtain the character set of the target string, calculate the single or double Cartesian product of the character set of the target string and itself, obtain all the string sets composed of the character set one by one, and map them to an array element in the FNext array one by one, That is, each string uniquely corresponds to an element position in the FNext array. At the same time, calculate and assign the initial value to the array element at this position. Since the optimal jumping distance is from the second rightmost character in the pattern string to the left, the first and the rightmost two or three characters of the pattern string are located Corresponding to the same character string in the target string, the distance between the rightmost character of the string and the position of the rightmost character of the pattern string in the pattern string. When calculating the initial value, it is assumed that there are no strings consisting of two or three arbitrary characters in the character set of the target string in the pattern string. The specific method for calculating the optimal jump distance is as follows:

When constructing the FNext array with two characters, if the first character of the pattern string is the same as the second character of the two characters obtained, the array element mapped to the string is assigned as PLen-1, otherwise it is assigned as PLen, where PLen is Pattern string length.

When constructing an FNext array with three characters, if the first character and the second character in the pattern string are the same as the second and third characters in the three characters obtained respectively, assign the array element uniquely mapped to the string to PLen-2, if the first character of the pattern string is the same as the third character among the three acquired characters, assign the array element uniquely mapped to the string to PLen-1, otherwise assign it to PLen.

Then, the pattern string is traversed from left to right according to the characters with a length of 2 or 3, and the optimal jump distance is calculated for each character string traversed, and its value is between the rightmost character of the string and the rightmost character of the pattern string. The distance between the positions in the pattern string, reassign the array elements mapped from the string to the FNext array as the optimal jump distance.

After traversing from left to right and reassignment is completed, each element in the FNext array is the first feature pair in the pattern string that does not match the target string, and the rightmost two or three characters of the pattern string are in the target string The optimal jumping distance provided by any string at the corresponding position in the string.

Before constructing the FNext array, it is determined to use two or three characters for construction. When the character set is less than 20, use three characters to build the FNext array, when the character set is greater than 20, use two characters to build the FNext array; when the target string is longer, use three characters to build the FNext array, otherwise, use two characters Characters build an FNext array.

Further, by analyzing the matching process between the pattern string and the target string, it can be seen that when the pattern string moves to any position in the target string, according to the matching sequence guided by the PNext array, the feature pairs are matched first, and the characters in the non-feature area are matched after all the feature pairs are matched. The matching scheme is carried out from right to left in turn. When the pattern string does not match the first feature pair with the target string, and other characters do not match the target string, there must be at least one feature pair that has already matched the target string. match. According to the nature of the pattern string feature pair, when the characters of the pattern string except the first feature pair do not match the target string characters, and the pattern string is shifted right in the target string, if the successfully matched feature pair characters and The alignment of characters in the non-characteristic area of the pattern string will inevitably lead to a mismatch in the next round of matching between the pattern string and the target string.

Aiming at the appeal analysis, the present invention proposes a scheme to obtain the best jumping distance according to the adapted feature pair when the character of the pattern string except the first feature pair and the target string character do not match: when the pattern string removes the first feature pair character and There is a character mismatch in the target string. When the pattern string is shifted to the right in the target string, it must be satisfied that there is no character aligned with the non-characteristic area of the pattern string for the feature pair that has been successfully matched, or the leftmost character of the pattern string and the subsequent character of the feature When they are equal, the leftmost character of the pattern string can be moved to be aligned with the rightmost feature that has been successfully matched, and the smallest moving distance among all moving distances that meet the above conditions is called the optimal jumping distance. Since all pattern strings except the first feature pair characters or non-feature region characters are mismatched with the target string characters, the best jump distance that can be provided can be obtained before the pattern string matches the target string , therefore, the TNext array is used to store the best jumping distance that can be provided when all the characters in the pattern string except the first feature do not match. When any character mismatch occurs during the matching process between the pattern string and the target string, it can be directly Use the TNext array to get the best jumping distance.

In said step 3, when there is a feature pair, the method for obtaining the TNext array of the jump matching distance in the target string for the record pattern string is as follows:

First, obtain the best jump distance that can be provided when the feature pair is mismatched: sequentially assign values to the array elements in the TNext array that are at the same position as the second feature pair in the pattern string, and assign the feature that is being assigned in the pattern string to the right All the characters in are called known strings, the feature pairs in this string are called known feature pairs, and the first known feature pair is the reference feature pair. Build a TNext array using the Sequence, Index, and Distance arrays. When the known feature pair is completely aligned with the pattern string feature pair, the first feature preorder index is subtracted from the feature preorder index aligned with the reference feature pair to obtain the optimal jump distance when the feature pair being assigned is mismatched; If each feature pair in the pattern string is aligned with the reference feature pair one by one, but the condition that the known feature pair is completely aligned with the pattern string feature pair is not satisfied, obtain the longest jump distance that the pattern string can provide, and obtain the longest jump distance The method is: judge whether the character postorder and the leftmost character of the pattern string are equal, if they are equal, the longest jump distance is the index value of the first feature postorder, otherwise the longest jump distance is the index value of the first feature postorder Add 1 to the index value, and assign the longest jump distance to all subsequent array elements to be assigned in the TNext array.

Secondly, the best jumping distance that can be provided when obtaining the non-characteristic area character mismatch: using the pattern string as a known character string, using the method of obtaining the best jumping distance when the feature pair is mismatched, when obtaining the non-characteristic area character mismatch The optimal jumping distance that can be provided, and all the array elements in the TNext array that correspond to the characters in the non-characteristic area in the pattern string are assigned the distance.

Further, by analyzing the matching process between the pattern string and the target string, it can be seen that starting from the third character from right to left in the pattern string, when any character does not match the target string, the rightmost two characters of the pattern string and the target string have been successfully matched. And there is no other character pair identical to this character pair in the pattern string. Therefore, the construction process only needs to judge whether the leftmost character of the pattern string is equal to the rightmost character of the pattern string, and then calculate the third character from the bottom of the pattern string Initially, the optimal jumping distance when any character does not match the target string. Therefore, in the step 3, when there is no feature pair, the method of obtaining the special PNext and TNext arrays of the record pattern string jumping matching distance in the target string is as follows:

When there is no feature pair in the pattern string, the matching starting point is the rightmost character position of the pattern string, and from right to left from the matching starting point, a special PNext array is constructed sequentially, that is, when the pattern string moves to any position in the target string, the pattern string characters The characters in the target string are matched from the rightmost character of the pattern string to the left. When the two rightmost characters of the pattern string do not match, the optimal jump distance is obtained according to the special FNext array. The construction of the special FNext array is the same as the general construction method of the FNext array. Otherwise, obtain the best jumping distance according to the special TNext array, construct a TNext array with the same length as the pattern string, and each array element records the best jumping distance that can be provided when the characters in the corresponding pattern string do not match. Determine whether the leftmost character of the pattern string is equal to the rightmost character of the pattern string. If they are equal, assign all the values of the TNext array to PLen-1, otherwise, assign the value to PLen, that is, the jump distance of the target string in the pattern string is the pattern string length.

Further, in the step 4, after obtaining the PNext, TNext and FNext arrays, the pattern string is retrieved from left to right in the target string, and in the retrieval process, use the pattern string pointer Pi and the target string pointer Ti to point to the pattern string respectively The characters are matched against the characters of the target string. When the pattern string moves to a certain position of the target string, start from the matching starting point FirstFeaStr of the pattern string, and perform jump matching with the corresponding character of the target string from right to left.

When the pattern string pointer matches the character pointed to by the target string pointer, use the pattern string pointer to obtain the corresponding array element value PNext[Pi] in the PNext array, and calculate the next matching character position pointed to by the pattern string and the target string pointer respectively: First point Ti to Ti-Pi+PNext[Pi], then point Pi to PNext[Pi].

When the pattern string pointer does not match the character pointed to by the target string pointer, if the character pointed to by the pattern string pointer is the first feature pair, obtain the character string aligned with the last two or three characters of the pattern string in the target string, and then obtain FNext The array element value V uniquely mapped to the string in the array is the optimal jumping distance between the first feature pair of the current pattern string and the corresponding character in the target string, and the optimal jumping distance is used to calculate the pattern string and the target The position of the next matching character pointed to by the string pointer: first point Ti to Ti-Pi+FirstFeaStr+V, and then point Pi to FirstFeaStr; if the character pointed to by the pattern string pointer is not the first feature pair, use the pattern string pointer to obtain the corresponding character in the TNext array The array element value TNext[Pi] of TNext[Pi], this value is the best jumping distance between the characters in the current pattern string and the corresponding characters in the target string, and the next matching character pointed to by the pointer of the pattern string and the target string is calculated through the best jumping distance Position: first point Ti to Ti-Pi+FirstFeaStr+TNext[Pi], then point Pi to FirstFeaStr.

Compared with the prior art, the beneficial effect of the present invention is: when there is a mismatch in any character, jumping is carried out according to the best jumping distance of the next round of matching calculated in advance, avoiding the need to repeat the matching after the mismatch occurs in the prior art. Only by performing calculations can a certain jumping distance be obtained; the present invention calculates the jumping matching method according to the characteristics of the pattern string itself, and on this basis proposes two accelerated matching schemes that can obtain a larger jumping distance, so as to achieve the purpose of accelerated matching and solve the problem of During the string retrieval process, once a mismatch occurs, the jump distance cannot be quickly obtained, which increases the problem of frequent backtracking and time-consuming calculations during the retrieval process.

Description of drawings

Fig. 1 is the flowchart of implementation steps of the present embodiment;

Fig. 2 is a schematic diagram of pattern string division in this embodiment;

FIG. 3 is a schematic diagram of the principle of pattern string matching in this embodiment;

Fig. 4 is a schematic diagram of the matching between the pattern string and the target string in the present embodiment;

Fig. 5 is the schematic diagram of the record array of the present embodiment;

Fig. 6 is the schematic diagram that the pointer slides of the present embodiment constructs the PNext data module;

Fig. 7 is a schematic diagram of completion of feature pair traversal in this embodiment;

Fig. 8 is the schematic diagram of the complete PNext array of the present embodiment;

FIG. 9 is a schematic diagram of known character strings in this embodiment;

FIG. 10 is a schematic diagram of the failure of calculating the optimal jump distance in this embodiment;

Figure 11 is a schematic diagram of the successful calculation of the best jumping distance in this embodiment;

Fig. 12 is the construction of pattern string array under special circumstances of the present embodiment;

Fig. 13 is a schematic diagram of the result of searching in target strings of different magnitudes by selecting a pattern string with a length of 100 in this embodiment;

Fig. 14 is a schematic diagram of the result of searching in target strings of different magnitudes by selecting a pattern string with a length of 500 in this embodiment;

Fig. 15 is a schematic diagram of the result of searching in target strings of different magnitudes by selecting a pattern string with a length of 1000 in this embodiment;

Fig. 16 is a schematic diagram of the result of searching in target strings of different orders of magnitude by selecting a pattern string with a length of 3000 in this embodiment;

Fig. 17 is a schematic diagram of the result of searching in target strings of different orders of magnitude by selecting a pattern string with a length of 5000 in this embodiment;

Fig. 18 is a schematic diagram of the result of searching in target strings of different magnitudes by selecting a pattern string with a length of 10000 in this embodiment;

Fig. 19 is a schematic diagram of the result of verifying the retrieval efficiency of the algorithm of the present embodiment by the size of the character set;

Fig. 20 is a schematic diagram of the retrieval efficiency results of the algorithm in this embodiment where the number of character sets is greater than 15.

Detailed ways

The present invention will be further described below in conjunction with the accompanying drawings, and the embodiments of the present invention include but are not limited to the following examples.

Fig. 1 is a flow chart of the implementation steps of this embodiment, including:

Step 1, obtain the feature pair in the pattern string;

Step 2, obtaining the optimized sequence PNext array for matching the record pattern string and the target string;

Step 3, obtain the TNext array and the FNext array that record the jump matching distance of the pattern string in the target string;

Step 4. When the pattern string is matched from left to right in the target string, if the corresponding character is matched, it will be matched according to the matching sequence obtained in step 2. If the corresponding character does not match, jump according to the record array obtained in step 3 in advance match.

为特征对之外的区域，一个字符位的长度为1，

长度为d_k，d_k≥0。模式串中特征对的总数为num(num≥2)，F_i(i∈[1，num])。对特征对从右到左依次编号，即最右边的特征对为第一特征对。同时，模式串最左边的字符PStr[0]记做FirstChar。In this embodiment, before the pattern string (PStr, length is PLen) is retrieved in the target string (TStr, length is TLen), it is necessary to distinguish the characteristic area and the non-characteristic area of the character in the pattern string, thereby extracting the characteristic Yes, as shown in Figure 2, in the pattern string PStr, the feature area is composed of the feature pair F _i = "C _s C _e ", and the feature pair F _i consists of two ordered and adjacent characters 'C _s ' and 'C _e 'composition, respectively called feature preorder F _i[1] ='C _s ' and feature postorder F _i[2] ='C _e ', 'C _s '≠'C _e '; non-characteristic area

For the area outside the feature pair, the length of a character bit is 1,

The length is _dk , and _dk≥0 . The total number of feature pairs in the pattern string is num (num≥2), F _i (i∈[1, num]). The feature pairs are numbered sequentially from right to left, that is, the rightmost feature pair is the first feature pair. At the same time, the leftmost character PStr[0] of the pattern string is recorded as FirstChar.

From the above, we can see that the pattern string has the following properties:

Property 1: The feature pair is the most frequently occurring character pair in the pattern string;

Property 2: The pre-order of features and the post-order of features are strictly guaranteed;

Property 3: Mutual exclusion, that is, there are no feature pairs in the non-feature area.

In this embodiment, the function of the feature pair is to quickly locate the possible position of the pattern string in the target string during the retrieval process, and adopt the scheme of matching the feature pair first, and after all the feature pairs are matched, the characters in the non-characteristic area are matched sequentially from right to left to match. Analyzing the matching process between the pattern string and the target string, when there is a mismatch between the pattern string characters and the target string characters, it can be known from the pattern string property 3 that there are no feature pairs in the area other than the feature pairs in the pattern string. According to this property, it can be known that the pattern string is in In the process of right shifting in the target string, there may be a moving distance due to matching the successfully matched feature pair characters with the non-characteristic area characters of the moved pattern string. If the pattern string is moved by these distances, a mismatch will inevitably result.

According to the above analysis, when there is a mismatch between the pattern string characters and the target string characters, the matching position of the next round to avoid invalid matching can be analyzed according to the successfully matched pattern string characters, thereby accelerating the retrieval speed of the pattern string in the target string . Obviously, the more pattern string feature pairs are adapted to the target string characters, the more information to guide accelerated matching. Therefore, in order to obtain a longer jump distance, it is necessary to make the pattern string characters and target string characters fit as much as possible. A character string of length D can be selected as an alternative feature character, D∈[2, PLen/2]. Obviously, during the matching process, the shorter the characteristic string in the pattern string, the greater the probability of the characteristic character string appearing in the target string, and the greater the possibility of successful matching. In this embodiment, D=2 is used as the characteristic character string length , that is, the feature pair uses 2 characters to describe. Number all feature pairs in the pattern string from right to left, starting from 1, that is, the rightmost feature pair is the first feature pair, if there is more than one character pair with the most number of times, select the rightmost character pair among them as feature pairs.

In this embodiment, as shown in Figure 3, the matching principle is that when the pattern string moves to a certain position of the target string, starting from the feature postorder of the first feature pair, the pattern string characters are used to start matching with the target string characters, if If the matching is successful, continue to match the feature preorder of the feature pair. When the feature preorder is also matched successfully, jump to the feature postorder of the next feature pair to match, and so on. As shown in the upper row of Figure 3, when the pattern When all the feature pairs in the string are successfully matched, jump to the rightmost non-characteristic character of the pattern string, and match the characters in the non-characteristic area from right to left in turn, as shown in the bottom row of Figure 3, if the leftmost non-characteristic character matches successfully , it indicates that the pattern string is retrieved successfully in the target string.

区域进行匹配，由性质3可知，

区域不包含特征对，因此，F′_i与

对齐必然导致失配(失配字符为Try2中‘×’填充)；进行Try3尝试模式串右移4位，此时F₂与F′₁对齐、F₃与F′₂对齐，但是

区域存在与F′₃对齐的字符，因此移动至此同样为无效匹配；进行Try4尝试模式串右移11 位，此时F₄与F′₁对齐，并且模式串不存在与已知特征对对齐的非特征字符，因此当模式串右移11位时不会产生无效匹配。因此，尝试移动不同距离进行匹配时，为避免无效匹配，需要得到下次匹配的最佳跳跃距离。任意字符失配之后，根据性质3可得，将模式串右移后满足特定条件的距离称为可跳跃距离：模式串中非特征字符与目标串中已知特征对不存在对齐的字符时(如图4中Try4和Try5)。显然，将模式串从左往右移动过程中，第一个可跳跃距离即为最佳跳跃距离(如图4中Try4)。若跳跃距离小于最佳跳跃距离时会产生无效匹配，而大于最佳跳跃距离则可能遗漏本该检索成功的区域，如图4中Try5过程移动14位会出现漏检。当上述有一个特例，即当且仅当FirstChar与F′_i[2]对齐且F′_i[2]＝FirstChar这种特殊情况时，不能作为无效匹配的判定条件。In this embodiment, the principle of the optimal jumping distance is to match according to the matching principle. As shown in Figure 4, when F ₁ , F ₂ , F ₃ (F _i represents the i-th feature pair) in the pattern string PStr and the target string When TStr matches successfully, but any character in the next feature pair that matches the target string does not match, F′ ₁ , F′ ₂ , and F′ ₃ that have been successfully matched before are known feature pairs, where F′ _i represents Known feature pairs, F′ _i[1] and F′ _i[2] represent the known feature preorder and feature postorder respectively. When performing the next match, if you move an inappropriate distance, the matching will fail. The matching failure is because the known feature pair is matched with the non-characteristic area of the pattern string, or the known feature pair is misplaced with the feature pair in the pattern string. , the above match is called an invalid match. As shown in Figure 4, the matches performed by moving Try1, Try2 and Try3 are all invalid matches, Try4 is a valid match, and Try5 is an excessively moved match. Among them, the Try1 trial pattern string is shifted to the right by 1 bit, and F _i[1] and F' _i[2] appear to be matched, that is, the feature pair is misplaced, resulting in a mismatch (the mismatch character is filled with '×' in Try1); Carry out Try2 and try to shift the pattern string to the right by 2 bits, and there are F′ _i and

The area is matched, it can be seen from the property 3,

The region does not contain feature pairs, therefore, F′ _i and

Alignment will inevitably lead to a mismatch (the mismatch character is filled with '×' in Try2); the Try3 trial pattern string is shifted to the right by 4 bits, at this time F ₂ is aligned with F' ₁ , and F ₃ is aligned with F' ₂ , but

There is a character aligned with F′ ₃ in the area, so moving here is also an invalid match; perform Try4 to try to shift the pattern string to the right by 11 bits, at this time, F ₄ is aligned with F′ ₁ , and there is no pattern string aligned with a known feature pair Non-characteristic characters, so when the pattern string is shifted right by 11 bits, no invalid match will be generated. Therefore, when trying to move different distances for matching, in order to avoid invalid matching, it is necessary to obtain the best jumping distance for the next matching. After any character mismatch, according to property 3, the distance that satisfies certain conditions after shifting the pattern string to the right is called the jumpable distance: when there is no aligned character between the non-characteristic character in the pattern string and the known feature pair in the target string ( Try4 and Try5 in Figure 4). Obviously, in the process of moving the pattern string from left to right, the first jumpable distance is the optimal jumping distance (Try4 in Figure 4). If the jumping distance is less than the optimal jumping distance, an invalid match will be generated, and if it is greater than the optimal jumping distance, the region that should have been successfully retrieved may be missed. As shown in Figure 4, when the Try5 process moves 14 bits, there will be missed detection. When there is a special case above, that is, if and only when FirstChar is aligned with F'i _[2] and F'i _[2] =FirstChar, it cannot be used as a judgment condition for invalid matching.

After explaining the principle of this embodiment based on the above, a character string retrieval method includes the following steps:

Step 1. Obtain feature pairs in the characters of the pattern string.

Among them, the method of feature pair acquisition is as follows:

First, create a two-dimensional Chars record array with a size of SIZE×SIZE. SIZE is the size of the ASCII character set, and initialize all values to 0. Each element in the two-dimensional array is uniquely mapped to a character pair composed of any two characters. The mapping method is that the ASCII code of one character in any character pair corresponds to the abscissa of the Chars array, and the ASCII code of the other character corresponds to the ordinate of the Chars array. Use pointer i and pointer i+1 to traverse the pattern string from left to right, where i∈[0,PLen-2], when pointer i and pointer i+1 traverse to any satisfying PStr[i]≠PSr[i +1], add 1 to the array element value mapped by these two characters in the record array, if the value is greater than or equal to the number num of character pairs that appear most frequently at present, update num to the current array The value of the element, and use the feature pair record pointer to respectively record the characteristic preorder 'C _s ' and characteristic postorder 'C _e ' of the character pair, and assign the value i+1 to the pointer FirstFeaStr, and the pointer FirstFeaStr is used to record the first The post-order position of the feature is used as the starting point for matching the pattern string with the target. When all pattern strings are traversed, if num is greater than 1, the character pair recorded by the record pointer is the feature pair of the pattern string, the number of num records is the total number of feature pairs, and the position recorded by the pointer FirstFeaStr is the pattern The matching starting point when the string matches the target, and before the pattern string matches the target string, the general PNext, TNext and FNext arrays are constructed; if num=1 after the traversal is completed, it indicates that there is no feature pair in the pattern string, and this When the matching starting point is set to the rightmost character of the pattern string, the general construction steps of the TNext array and the PNext array are skipped, and then the special TNext array and the PNext array are constructed.

As shown in Figure 5, while obtaining the feature pair, it is easy to obtain the following three record arrays that can be used to quickly calculate the optimal jump distance: the Sequence array that identifies the positions of all feature preorders and feature postorders in the pattern string, such as Sequence[ 2]=1 and Sequence[3]=2 respectively represent the pre-order of the feature and the post-order of the feature, the non-characteristic area array value is 0, and the Index array of all the pre-order indexes of the features is recorded in turn, such as Index[1]=9, and the record The Distance array of the preceding distance between adjacent features, for example, Distance[1] stores the distance Δ ₁ =4 between F _1[1] and F _2[1] . In order to improve the efficiency of the algorithm, the Sequence array is initialized to 0 while acquiring the feature pairs.

Step 2. The pattern string and the target string are matched against the feature pair and the non-signature area, and the matching order is obtained by using the PNext array.

Among them, construct a PNext array that records the matching order of the pattern string and the target string, the specific method is:

First, build a PNext array with the same length as the pattern string. Since the PNext array records the positional relationship between the two characters matched successively, the pattern string is constructed by double-pointer synchronous traversal. Use the pointer P to point to the position corresponding to the character being processed in the PNext array, and use the pointer i to traverse the pattern string from right to left to find the feature pair. In order to improve the algorithm efficiency, when calculating the feature area of the PNext array, obtain the three record arrays in the above step 1 at the same time, as shown in Figure 6, take PStr="TTACTATTAGGATTAGCA" as an example, and "TA" is the feature in the pattern string right.

In this embodiment, the matching sequence of the PNext array records includes the matching sequence of the first feature pair of the pattern string and the target string, and the matching sequence of the feature pairs of the pattern string except the first feature or the matching sequence of the non-feature region and the target string.

Among them, the method for calculating the matching order of the first feature pair of the pattern string and the target string is as follows:

When the feature pair acquisition is completed, the index recorded by FirstFeaStr is the position of the feature sequence of the first feature pair, as shown in Figure 6 (P1), point the pointer i and the pointer P to the feature sequence of the first feature pair , namely FirstFeaStr-1, assign PNext[FirstFeaStr] to i. At the same time, assign i to Index[t] (t is the serial number of the feature pair, the initial value is 1), which is used to record the position of the feature preorder of the first feature pair, and add 1 to t after the assignment is completed; Sequence[i] and Sequence[i+1] are assigned values of 1 and 2 respectively, which are used to mark the position of the feature pair. Since the two adjacent feature pairs must satisfy that the post-order of the former feature will not coincide with the pre-order of the latter feature, in order to improve the calculation efficiency, after processing a feature pair, move the pointer i to the left by two bits. Then, as shown in Figure 6 (P2), use the pointers i and i+1 to continue to traverse the PNext array to the left, when the pointer i finds the characteristic preorder character 'T', and the pointer i+1 finds the characteristic postorder character 'A ', that is, when traversing to the second feature pair, assign the PNext array element pointed to by the pointer P to i+1, and finally, assign the P pointer to i+1.

In addition, the method of calculating the matching order of feature pairs or non-feature regions and the target string except the first feature in the pattern string is as follows:

First, move the pointer i one bit to the left, then assign the array element pointed to by the P pointer in the PNext array to i+1, then point the P pointer to the array position corresponding to i+1, and then use the i pointer and i+1 The pointer continues to traverse to the left. When the pointer i finds the characteristic preorder character 'T', and the pointer i+1 finds the characteristic postorder character 'A', that is, when the next characteristic pair is obtained, the PNext array element pointed to by the pointer P is assigned a value is i+1, and finally assign the P pointer to i+1. At the same time, complete the same calculation and assignment of the Sequence array and the Index array in the matching order of the first feature pair of the acquired pattern string and the target string, and add the calculation and assignment of the record array Distance, that is, Distance[t-1] The assignment is Index[t-1]-Index[t], where the Distance array is used to record the distance between two adjacent features. So back and forth.

As shown in Figure 7, after the pointer i traverses the pattern string to the left, the P pointer points to the PNext array position corresponding to the leftmost feature preorder. At this time, use the traverse pointer i to traverse the pattern string from right to left The elements of the non-feature area are traversed, and then the calculation and assignment of the PNext array elements corresponding to the non-feature area are completed. The specific implementation method is as follows:

As shown in Figure 8, when the i pointer points to a character in a non-characteristic area, first assign the PNext array element pointed to by the P pointer to i, and then assign the P pointer to i, and then continue to use the i pointer to traverse to the left to find For the next non-characteristic character, judge whether the character pointed to by the i pointer is a characteristic pair through the Sequence array. So back and forth. When the calculation and assignment of the PNext array elements corresponding to all non-characteristic areas are completed, and the i pointer traverses to the left to the leftmost non-characteristic area character, assign the PNext array pointed to by the i pointer to -1, where -1 is the end of the match mark, which means that when the character matches successfully, all pattern string characters are successfully matched in the target string.

Step 3, the method of obtaining the FNext array that records the jump matching distance of the pattern string in the target string is as follows:

In order to quickly construct the FNext array, the solution adopted in this embodiment is: after obtaining the character set of the target string, at first, calculate the single or double Cartesian product of the character set of the target string and itself, and obtain all character strings formed by the character set one by one Set, the best jumping distance recorded in the FNext array is mapped one by one to the strings in the set. Calculate the Cartesian product while calculating and assigning initial values to the array elements. The optimal jumping distance means that the pattern string starts from the second character on the right and goes to the left. The position corresponds to the distance between the rightmost character of the character string and the position of the rightmost character of the pattern string in the pattern string for the same character string in the target string. When calculating the initial value, it is assumed that there are no strings consisting of two or three arbitrary characters in the target string character set in the pattern string. The specific method is as follows:

When constructing the FNext array with two characters, if the first character of the pattern string is the same as the second character of the two characters obtained, the array element mapped to the string is assigned as PLen-1, otherwise it is assigned as PLen, where PLen is Pattern string length.

When constructing an FNext array with three characters, if the first character and the second character in the pattern string are the same as the second and third characters in the three characters obtained respectively, assign the array element uniquely mapped to the string to PLen-2, if the first character of the pattern string is the same as the third character among the three acquired characters, assign the array element uniquely mapped to the string to PLen-1, otherwise assign it to PLen.

Then, the pattern string is traversed from left to right according to the characters with a length of 2 or 3, and the optimal jump distance is calculated for each character string traversed, and its value is between the rightmost character of the string and the rightmost character of the pattern string. The distance between the positions in the pattern string, reassign the array elements mapped from the string to the FNext array as the optimal jump distance.

After traversing from left to right and reassignment is completed, each element in the FNext array is the first feature pair in the pattern string that does not match the target string, and the rightmost two or three characters of the pattern string are in the target string The optimal jumping distance provided by any string at the corresponding position in the string.

Before constructing the FNext array, it is determined to use two or three characters for construction. When the character set is less than 20, use three characters to build the FNext array, when the character set is greater than 20, use two characters to build the FNext array; when the target string is longer, use three characters to build the FNext array, otherwise, use two characters Characters build an FNext array.

Step 3. When the feature pair is obtained successfully, the method of obtaining the TNext array that records the jump matching distance of the pattern string in the target string is as follows:

Construct a TNext array of the same length as the pattern string, and perform calculation and assignment processing on the array elements corresponding to the feature pairs of the pattern string and the array elements of the non-characteristic area of the pattern string in the array. For F ₂ , the TNext array element corresponding to F ₂ indicates the optimal jump distance of the feature when the target string is mismatched. When F ₂ is mismatched, the known feature pair is only F′ ₁ , and the pattern string can only be Shift to align _F2 with _F'1 . When processing F _i (i∈[3,num]), the corresponding elements in the TNext array are calculated and assigned by the following methods:

As shown in Figure 9, during the retrieval process, if there is a mismatch in F _i (i∈[3,num]), all feature pairs before F _i are adapted, that is, the known feature pair is F′ _j (j∈[ 1,i-1]), and all the characters on the right of the mismatched feature pair in the pattern string are called known strings. Since the matching process between the known string and the pattern string is the same as the matching process between the target string and the pattern string, the optimal jumping distance is calculated using the matching between the pattern string and the known string.

F′ ₁ in the known character string is called a reference feature pair, use the F _i (i∈[2, num]) in the pattern string to align with the reference feature pair in turn, and judge the serial number of the F _i and the aligned pattern string feature pair, at this time T is equal to 2, the known string is the area covered by F′ _j (j∈[1,3]), the pattern string feature pair aligned with F′ ₁ for the first time is F _T , and the OSP pointer points to the preorder of the known feature , initialized to 1, and the SSP pointer obtains the position of the feature preorder of the pattern string feature pair aligned with the reference feature pair according to the Index array. First, according to the Distance array, obtain the distance between the OSP pointer and the preorder of the next known feature. Subtracting the distance from the SSP pointer is the position in the pattern string that is aligned with the preorder of the next known feature, and then use the SSP pointer to judge the Sequence array Whether the element value at this position is 1 is used to determine whether there is a misplaced character. For example, as shown by Shift① in Figure 10, the SSP pointer moves to the character position of the pattern string aligned with F′ _2[1] , that is, F _3[ in the pattern string _1] The position of the character. At this time, Sequence is equal to 1, indicating that the known feature pair in the known string is aligned with the corresponding position feature pair in the pattern string. OSP moves to the next feature preorder (Shift②), and continues to judge whether there is a misplaced character ; When the SSP pointer moves to point to the pattern string character (Shift ③) of the next known characteristic preorder alignment, the character aligned by F′ _3[1] is a non-characteristic character, that is, the position element in the corresponding Sequence array is not 1, so The match at this position is an invalid match. End this round of calculation, align the next feature pair of the pattern string with the reference feature pair, that is, add 1 to T, restore OSP to 1, and point to Index[T] with SSP, and continue the next round of calculation. So cycle.

When SSP subtracts the distance obtained by OSP according to Distance, if SSP<-1, it means that the SSP pointer points to a position beyond the pattern string by more than 2 character bits. Obviously, the next known feature pair of the known string cannot be matched with the pattern string Characters are aligned. Therefore, moving the pattern string to this point is the optimal jumping distance. If SSP=-1, it means that the FirstChar character of the pattern string is subsequently aligned with the known feature pair of the known character string. It is only necessary to judge F _i[2] and Whether FirstChar is equal, if equal, it is the best jumping distance, otherwise it is an invalid match. As shown in Figure 11, if there is no misplaced character in all known feature pairs and pattern strings in the known character string, it means that the position is a jumpable distance.

TStart indicates the serial number of the first feature pair aligned with the reference feature pair in the pattern string, the initial value is 2, T is used to record the serial number of the feature pair of the pattern string aligned with the reference feature pair during the calculation process, and t indicates the feature being processed at this time For the serial number. When the number of known feature pairs is K, if there is a misplaced character when a certain feature pair in the pattern string is aligned with the reference feature pair, then when the number of known feature pairs is greater than K, the pattern string feature pair is aligned with the reference feature pair Therefore, when calculating the optimal jumping distance, the feature pair that is first aligned with the reference feature pair in the pattern string should be the feature pair that was aligned with the reference feature pair when the last calculation was completed, not every time Count from _F2 . Therefore, the initial value of T is set to TStart, and every time the optimal jumping distance is calculated, TStart at the end of this calculation is passed to the next calculation.

Since there are all pattern string feature pairs that are aligned with the reference feature pairs, but do not meet the jumpable distance condition, the array of TNext array must be assigned, that is, the function must return an optimal jump distance, so when the reference feature pair and all pattern string feature pairs When aligning, if the jumpable distance condition is still not satisfied, it is only necessary to judge whether the sequence of the feature is equal to FirstChar, if they are equal, move FirstChar to the sequence of the first feature; otherwise, move FirstChar to the right of the sequence of the first feature character position.

If the alignment of F _num and the reference feature pair is also an invalid match, the pattern string will obtain a longest jump distance, which is determined by the pattern string attribute. Therefore, it is not necessary to use the calculation of the best jump distance when assigning a value to the next element of the TNext array, just All elements after the TNext array need to be assigned the longest jump distance. Based on the above method, the longest jumping distance is equal to the addition of the indices of F _num[1] and F _1[2] , where the size of the index of F _1[2] dominates. Therefore, when selecting a feature pair in step 1, if When there are more than one character pair with the most occurrences, the character pair on the right in the pattern string is selected as the feature pair.

When the feature pairs in the TNext array are assigned values to the corresponding area elements, it is necessary to assign values to the non-feature areas. At this time, all feature pairs are regarded as known feature pairs, and the same method is used to calculate the corresponding array element values of the feature pairs in the TNext array. The best jumping distance, only need to use the complete pattern string as a known string. In order to improve the efficiency of the algorithm, the assignment of non-characteristic areas in the PNext array and TNext array is implemented in the same program module.

Step 3, when obtaining the feature pair fails, the method of obtaining the special PNext and TNext arrays that record the jump matching distance of the pattern string in the target string is as follows:

When there is no feature pair in the pattern string, on the basis of the existing retrieval process, construct special PNext array and TNext array to obtain high retrieval efficiency. As shown in Figure 12, taking PStr="ABCDEFGH" as an example, PLen=8 and there is no feature pair, first construct a set of PNext arrays that are retrieved sequentially from right to left, and the matching starting point FirstFNext is set to PLen–1. When the first two matched characters (G and H) do not match, the optimal jump distance is obtained according to the FNext array; when other characters do not match, since there is no character pair consisting of the rightmost two characters in the pattern string at this time, therefore , just judge whether FirstChar is equal to PStr[PLen–1], if they are equal, assign all values of TNext array to PLen-1, otherwise assign to PLen.

Step 4. If both the feature pair and the non-feature area are successfully matched, the pattern string is successfully retrieved in the target string, and the position of the next matching character is obtained. The retrieval process is as follows:

After obtaining the PNext, TNext and FNext arrays, search the pattern string from left to right in the target string. During the retrieval process, use the pattern string pointer Pi and the target string pointer Ti to point to the characters of the pattern string and the characters of the target string respectively to match . When the pattern string moves to a certain position of the target string, start from the matching starting point FirstFeaStr of the pattern string, and perform jump matching with the corresponding character of the target string from right to left.

When the pattern string pointer matches the character pointed to by the target string pointer, use the pattern string pointer to obtain the corresponding array element value PNext[Pi] in the PNext array, and calculate the next matching character position pointed to by the pattern string and the target string pointer respectively: First point Ti to Ti-Pi+PNext[Pi], then point Pi to PNext[Pi].

When the pattern string pointer does not match the character pointed to by the target string pointer, if the character pointed to by the pattern string pointer is the first feature pair, obtain the character string aligned with the last two or three characters of the pattern string in the target string, and then obtain FNext The array element value V uniquely mapped to the string in the array is the optimal jumping distance between the first feature pair of the current pattern string and the corresponding character in the target string, and the optimal jumping distance is used to calculate the pattern string and the target The position of the next matching character pointed to by the string pointer: first point Ti to Ti-Pi+FirstFeaStr+V, and then point Pi to FirstFeaStr; if the character pointed to by the pattern string pointer is not the first feature pair, use the pattern string pointer to obtain the corresponding character in the TNext array The array element value TNext[Pi] of TNext[Pi], this value is the best jumping distance between the characters in the current pattern string and the corresponding characters in the target string, and the next matching character pointed to by the pointer of the pattern string and the target string is calculated through the best jumping distance Position: first point Ti to Ti-Pi+FirstFeaStr+TNext[Pi], then point Pi to FirstFeaStr.

When the pointer Pi traverses to the last character (PNext[Pi]=-1), jump out of the loop. Since the search sequence is jump matching, when the pattern string matches any two characters of the target string, no matter whether it fails or succeeds, the target string pointer needs to be restored to the target string position aligned with the FirstChar of the current pattern string before pointing to the next matching position. Then get the next matching position according to the auxiliary array.

In order to further verify the stability and effectiveness of this example, strings of different magnitudes (tumor genome, virus genome, and genetic disease genome) were obtained through the public genome database https://www.ncbi.nlm.nih.gov/, and selected Pattern strings with lengths of 100, 500, 1000, 3000, 5000 and 10000 are retrieved respectively in target strings of different orders of magnitude, using the algorithms ZK(2) and ZK(3) of this embodiment and the Sunday, BMH, KMP, BF and BM algorithms are compared, among which ZK(2) and ZK(3) are algorithms for constructing FNext arrays using two and three characters respectively.

The whole process of the experiment is operated in the memory, the CPU is Intel-i5-8400-2.80GHz, the memory is 24G, and the microsecond-level timing function "QueryPerformanceFrequency" is used to count the retrieval time. Among them, the genome database has removed gene tags.

As shown in Figure 13-Figure 18, Experiment 1 shows that as the magnitude of the target string increases, the retrieval time (ms) of the ZK(2) and ZK(3) algorithms for pattern strings of different lengths is much shorter than other algorithms, and the algorithm stability good. The larger the magnitude of the target string, the more obvious the advantages of the ZK(3) algorithm. As shown in Figure 17-Figure 18, when the order of magnitude of the target string is low, the ZK(2) algorithm is obviously better than ZK(3) and other algorithms, because the ZK(3) algorithm is relatively time-consuming when constructing the auxiliary array. longer. In practical applications, when the target string is long, it is recommended to choose the ZK(3) algorithm, otherwise, choose the ZK(2) algorithm.

In order to verify the effect of character set size on the retrieval efficiency of existing algorithms and the ZK algorithm, experiment 2 was carried out, as shown in Figure 19-20, the method of randomly generating target strings and pattern strings with a specified character set size, TLen=5× 10^8, PLen＝2 × 10^3, the ordinate is the retrieval time, in milliseconds, and the abscissa is the size of the character set. In Figure 19, ZK(2), ZK(3) and existing algorithms are tested, and the KMP and BF algorithms that have a greater impact on data analysis are excluded, and the character set 5-60 is analyzed; in Figure 20, with the character set As the set increases, when the character set is less than 20, the retrieval efficiency of the ZK(3) algorithm is much higher than other algorithms. When the character set is greater than 20, the auxiliary array construction takes a long time.

Since the ZK algorithm uses jump matching for matching, and the optimal jump distance when the TNext array and the FNext array correspond to any character mismatch can be calculated according to the pattern string attributes, the ZK algorithm uses the calculation of the optimal jump distance in advance and The scheme saved in the corresponding array, in actual retrieval, regardless of the mismatch or adaptation of the character being matched, the next matching position or the best jumping distance can be obtained in the corresponding auxiliary array according to the index of the character currently being matched. The advantage of this embodiment is that there is no need to perform too many calculations in the retrieval process, and only need to perform a data fetch operation on the corresponding auxiliary array, which greatly optimizes the time consumption of the program retrieval process.

The above is the embodiment of the present invention. The above examples and the specific parameters in the examples are only for clearly expressing the inventor's invention verification process, and are not used to limit the scope of patent protection of the present invention. The scope of patent protection of the present invention is still subject to its claims. The equivalent structural changes made in the specification and drawings of the present invention should be included in the protection scope of the present invention in the same way.

Claims (3)

1. a character string retrieval method, it is characterized in that, obtains the optimization order that given pattern string matches with target string, and the distance that pattern string jumps and matches in target string in matching process, thereby reaches the purpose of fast retrieval, its Specific steps are as follows: Step 1, obtain the feature pair in the pattern string; Step 2, obtaining the optimized sequence PNext array for matching the record pattern string and the target string; Step 3, obtain the TNext array and the FNext array that record the jump matching distance of the pattern string in the target string; Step 4. When the pattern string is matched from left to right in the target string, if the corresponding character is matched, it will be matched according to the matching sequence obtained in step 2. If the corresponding character does not match, jump according to the record array obtained in step 3 in advance match; The feature pair is the character pair that appears most often in the pattern string. The number of feature pairs is not less than 2. The character on the left of the feature pair is called the feature preorder, and the character on the right is called the feature postorder. The feature preorder and the feature postorder They are two mutually different characters, and all the feature pairs in the pattern string are numbered from right to left, starting from 1, that is, the rightmost feature pair is the first feature pair, if there is more than one character pair with the most number of times , select the rightmost character pair among them as the feature pair; In the step 2, after successfully obtaining the feature pair, obtain the PNext array of the matching order of the record pattern string character and the target string character, the specific method is as follows: After the feature pair is obtained, the pattern string is divided into feature pairs and non-feature areas, and a PNext array with the same length as the pattern string is constructed, and the postorder position of the first feature is used as the matching starting point, and the element in the PNext array at the same position as the matching starting point is assigned a value As the preorder index of the first feature pair, the element at the same position as the first feature pair is assigned as the feature postorder index of the next feature pair, and so on; assign the element with the same preorder position as the last feature pair The element assignment is the index of the first non-characteristic area character on the far right of the pattern string, and then the corresponding position of the non-characteristic area character is assigned from right to left, and the corresponding element of each character position is assigned the next adjacent non-characteristic area character index, and mark the last assigned element in the PNext array as the end sign; In said step 3, after successfully obtaining the feature pair, the specific acquisition method of the record array recording the jump distance when the pattern string and the target string characters do not match are as follows: When any character does not match, the best jump distance is obtained according to the corresponding record array. The record array includes the FNext array that records the best jump distance when the first feature pair of the pattern string does not match the character of the target string, and the pattern string except the first feature pair The TNext array that records the best jumping distance when the character of the character does not match the character of the target string; The FNext array stores the best jumping distance that can be provided by all strings composed of two or three consecutive characters in the target string character set, and each string uniquely maps to one FNext array element; First, obtain the character set of the target string, calculate the single or double Cartesian product of the character set of the target string and itself, obtain all the string sets composed of the character set one by one, and map them to an array element in the FNext array one by one, That is, each string uniquely corresponds to an element position in the FNext array, and at the same time assign an initial value to the position, the specific method is as follows: When constructing the FNext array with two characters, if the first character of the pattern string is the same as the second character of the two characters obtained, the array element mapped to the string is assigned as PLen-1, otherwise it is assigned as PLen, where PLen is pattern string length; When constructing an FNext array with three characters, if the first character and the second character in the pattern string are the same as the second and third characters in the three characters obtained respectively, assign the array element uniquely mapped to the string to PLen-2, if the first character of the pattern string is the same as the third character among the three acquired characters, assign the array element uniquely mapped to the string to PLen-1, otherwise assign it to PLen; Then, the pattern string is traversed from left to right according to the characters with a length of 2 or 3, and the optimal jump distance is calculated for each character string traversed, and its value is between the rightmost character of the string and the rightmost character of the pattern string. The distance between the positions in the pattern string, reassign the array element mapped to the string and the FNext array as the optimal jump distance; After traversing from left to right and reassignment is completed, each element in the FNext array is the first feature pair in the pattern string that does not match the target string, and the rightmost two or three characters of the pattern string are in the target string The optimal jumping distance that any string at the corresponding position in the string can provide; The specific construction method of TNext array is: Construct a TNext array with the same length as the pattern string, and each array element in the TNext array records the best jumping distance that can be provided when the characters in the corresponding pattern string do not match, including when the feature pairs in the pattern string do not match and the characters in the non-characteristic area do not match The best distance that can be jumped when First, obtain the best jumping distance that can be provided when the feature pair is mismatched: sequentially assign values to the array elements in the TNext array that are at the same position as the second feature pair in the pattern string, and assign the feature that is being assigned in the pattern string to the right All the characters in are called known strings, and the feature pairs in this string are called known feature pairs. The first known feature pair is the reference feature pair, and the use pattern string starts from the second feature pair with the reference feature pair in turn. Alignment, using the Sequence array that identifies the positions of all feature preorders and feature postorders in the pattern string, the Index array that records the preorder indexes of all features in turn, and the Distance array that records the distance between adjacent feature preorders to construct a TNext array. When the feature is known When the pair is completely aligned with the feature pair of the pattern string, the first feature preorder index is subtracted from the feature preorder index aligned with the reference feature pair to obtain the optimal jump distance when the feature pair being assigned is mismatched; if the pattern string is Each feature pair is aligned with the reference feature pair one by one, but the condition that the known feature pair is completely aligned with the pattern string feature pair is not satisfied, and the longest jump distance that the pattern string can provide is obtained. The longest jump distance acquisition method is: judge Whether the character postorder is equal to the leftmost character of the pattern string, if they are equal, the longest jump distance is the index value of the first feature postorder, otherwise the longest jump distance is the index value of the first feature postorder plus 1 , and assign all subsequent array elements to be assigned in the TNext array to the longest jump distance; Secondly, obtain the best jumping distance that can be provided when the characters in the non-characteristic area are mismatched: use the pattern string as a known character string, use the method of obtaining the best jumping distance when the feature pair is mismatched, and obtain the best jumping distance when the characters in the non-characteristic area are mismatched The best jumping distance that can be provided, and all the array elements in the TNext array corresponding to the non-characteristic area characters in the pattern string are assigned the distance; Wherein, the Sequence array, the Index array and the Distance array can be obtained in the process of obtaining the PNext record array in step 2. 2. A kind of character string retrieval method according to claim 1, it is characterized in that, in described step 3, after obtaining feature to fail, carry out special construction to PNext array and TNext array, concrete construction steps are as follows: When there is no feature pair in the pattern string, the matching starting point is the rightmost character position of the pattern string, and from right to left from the matching starting point, a special PNext array is constructed sequentially; when the two rightmost characters of the pattern string do not match, according to the special FNext The array obtains the optimal jumping distance, and the construction of the special FNext array is the same as the FNext array construction method described in claim 1, otherwise the optimal jumping distance is obtained according to the special TNext array, and the construction method of the special TNext array is as follows: Construct a TNext array with the same length as the pattern string, and each array element records the best jumping distance that can be provided when the characters in the corresponding pattern string do not match, and judge whether the leftmost character of the pattern string is equal to the rightmost character of the pattern string, if If they are equal, assign all the values of the TNext array to PLen-1, otherwise, assign PLen, that is, the target string’s jumping distance in the pattern string is the length of the pattern string. 3. a kind of string retrieval method according to claim 1, is characterized in that, in described step 4, after obtaining PNext, TNext and FNext array, pattern string is retrieved from left to right in target string, retrieves During the process, use the pattern string pointer Pi and the target string pointer Ti to point to the characters of the pattern string and the characters of the target string respectively to match. When the pattern string moves to a certain position of the target string, start from the pattern string matching starting point FirstFeaStr, from right to Jump match the characters corresponding to the left and target strings; When the pattern string pointer matches the character pointed to by the target string pointer, use the pattern string pointer to obtain the corresponding array element value PNext[Pi] in the PNext array, and calculate the next matching character position pointed to by the pattern string and the target string pointer respectively: First point Ti to Ti-Pi+PNext[Pi], then point Pi to PNext[Pi]; When the pattern string pointer does not match the character pointed to by the target string pointer, if the character pointed to by the pattern string pointer is the first feature pair, obtain the character string aligned with the last two or three characters of the pattern string in the target string, and then obtain FNext The array element value V uniquely mapped to the string in the array is the optimal jumping distance between the first feature pair of the current pattern string and the corresponding character in the target string, and the optimal jumping distance is used to calculate the pattern string and the target The position of the next matching character pointed to by the string pointer: first point Ti to Ti-Pi+FirstFeaStr+V, and then point Pi to FirstFeaStr; if the character pointed to by the pattern string pointer is not the first feature pair, use the pattern string pointer to obtain the corresponding character in the TNext array The array element value TNext[Pi] of TNext[Pi], this value is the best jumping distance between the characters in the current pattern string and the corresponding characters in the target string, and the next matching character pointed to by the pointer of the pattern string and the target string is calculated through the best jumping distance Position: first point Ti to Ti-Pi+FirstFeaStr+TNext[Pi], then point Pi to FirstFeaStr.

Images