CN101488127B - Bit mark character string fuzzy retrieval method for grouping character and labellng with bit - Google Patents

Abstract

The invention discloses a character string retrieval fuzzy method for grouping characters and marking them with bits. The method includes: dividing all character elements into n groups, and using data W with n bits to record the characters constituting the character string S P meta information. If the character element P ₁ of S belongs to group j, set the jth bit of W to 1; if P2 belongs to group k, set the kth bit of W to 1..., W after all character elements are marked, It is called the "bit value" of S. By comparing W _a of S _a with W _b of S _b , it can be judged that S _b does not contain or may contain all the character elements of S _a ; for possible S _b , Then use the character comparison method to judge whether S _a is included. Based on the above methods, according to logic algebra, various methods of marking and comparing bit values can be derived. This method can increase the retrieval speed several times, but it needs to mark the string first, so it is suitable for string search with a relatively fixed retrieval range.

Description

A Fuzzy Retrieval Method of String Characters Grouped and Marked by Bits

technical field

The invention relates to a character string fuzzy search method, which quickly and effectively determines the possible range of a target character string, and then uses an existing character matching method to locate the target character string, and is suitable for the string search field where the search range is relatively fixed.

Background technique

The usual character string fuzzy search is carried out in a bit-by-bit comparison mode, such as judging whether the character string S="bdopfqew" contains character f, the computer compares the first character b and f of the main string S, and then uses the second character of S The first character d is compared with f, and so on, until the fifth character of S is the same as f, and the match is successful. This is the simplest case. If the length of the substring T is more than 2 characters, the simple pattern matching algorithm, that is, the BF algorithm, compares S ₁ with T ₁ , if they are different, compares S ₂ with T ₁ , and so on, until a certain character of S S _i is the same as T ₁ , then compare S _i+1 with T ₁₊₁ after them, if they are also the same, continue to compare, when a certain character S _i+n of S is different from T _1+n At the same time, return, and then make a new round of comparison with S _i+1 and T ₁ , repeat the above process until all the characters in T are compared, then the match is successful, otherwise the match fails. As the length of the retrieval keyword T increases, the complexity of character matching increases accordingly. The improved pattern matching algorithm, that is, the KMP algorithm, avoids backtracking for pinyin characters with small character sets, but it has little practical significance for Chinese character strings with large character sets and low frequency of single characters. In short, both the BF algorithm and the KMP algorithm compare the characters of the main string and the substring bit by bit.

In 2004, I proposed "Prime Number Substitution String Retrieval Technology". This method can improve the speed of string fuzzy retrieval by 2-3 times, but implementing this method for long strings requires more space to store the prime number product value. In order to improve the speed of character string fuzzy retrieval and reduce the demand for storage space, the present invention proposes to mark the composition information of character string with n bits (bit) of data, and the data after marking is called "bit" of the character string. value", compare the bit values of two strings, and combine the usual character-by-bit comparison method to realize the fuzzy retrieval of strings. Tests show that the speed is several times or even more than ten times faster than that of general character-by-digit fuzzy retrieval.

Contents of the invention

The invention is a character string retrieval technology, and the purpose is to improve the speed of character string fuzzy retrieval. One bit (bit) corresponds to several character elements, and n bits correspond to all character elements, that is, all character elements are divided into n groups, and n bits of a data are all 0, marked as W _F . Metainformation about the characters that make up the string. _If a character element P ₁ of several character _{strings S} belongs to the nth group, the nth bit of W is marked as 1 accordingly, and similarly, according to the The group marks W, and after completing all character meta-marks, W records the information of S, which is called the "bit value" of S, and this method is called 1 mark. According to the principle of logic algebra, it is also possible to use n bits of a data that are all 1, which is recorded as To mark the meta-information of the characters that make up the string. If a character element P of S belongs to the nth group, the data The nth bit of is marked as 0, which is called 0 marking. Through the "bit value" W _a of S _a , and the "bit value" W _b of S _b , By comparison, it can be judged that S _b "does not contain", "contains" or "may contain" all the character elements of S _b . For example, the bit implication operation is performed on W _a and W _b , if all bits have an implication relationship, then S _b contains or may contain "all characters" of S _a . If necessary, the usual character-by-bit comparison method is used to determine whether S _b contains "S _a ". Hereinafter referred to as the present invention method is " bit mark search ", " bit mark character string search "" bit mark character string search technology ".

Tests show that bit tag retrieval can significantly speed up fuzzy retrieval of strings. In addition to the advantage of speed, another feature of bit tag retrieval is that multiple keyword queries are as convenient as single keyword queries. The bit mark can be used for retrieval in the usual sense, that is, to judge whether the database string contains keywords, or as a "reverse search", to judge whether the keywords contain database strings, and can be used in voice input, pinyin input, and Chinese word segmentation, matching Basic sentence patterns or words.

As an extension of the basic method, if the number of digits n available for marking is more than twice the average length m of the string, a combination of several bits can be used to mark a group of characters to improve screening efficiency.

As a string algorithm, the bit-marked string retrieval technology needs to bit-mark the strings in the search range first, so it is suitable for the field of string search where the search range is relatively fixed.

1. Basic method

In the implementation of bit-marked character string retrieval, "bit" or "combination of bits" can be used to correspond to characters in common meaning, such as: a, b, A, B, ∑#, ∞, ま, :, 中, 国; according to needs, digits can also be used to correspond to radicals of Chinese characters, such as: 扌, 罒, and even strokes, such as 丿, , etc.; for pinyin characters, such as the English string "day and night", digits can be used to correspond to words , such as day, and, night, or use bit-corresponding letter combinations, such as ay, ai, which can represent the initials, finals or syllables of Chinese Pinyin in Chinese Pinyin input or voice input, and can represent phonetic symbols for other languages, such as θ, siη. For ease of description, the character unit corresponding to a bit or a combination of bits is referred to as a "character element", denoted as P.

The method for bit-marked character string retrieval is easy to implement in phonetic character string retrieval. Let a 32-bit data 0000, 0000, 0000, 0000, 0000, 0000, 0000, 0000 be recorded as W _F , with W _F from left to right (or from right to left) The 1st to 26th digits of the corresponding to 26 English letters, and the other 6 digits may not be considered, and may also correspond to punctuation marks. The word big contains b, g, and i, so the corresponding 3 bits such as 2, 7, and 9 are marked as "1", and the data becomes 0100, 0010, 1000, 0000, 0000, 0000, 0000, 0000, which is called big The bit value of is denoted as W _a , and this marking method is a "1" mark.

Similarly, bigger includes b, e, g, i, r, so the 5 bits 2, 5, 7, 9, and 18 of W _F are marked as "1", and the data becomes 0100, 1010, 1000, 0000, 0100 , 0000, 0000, 0000, called the bit value of bigger, denoted as W _b .

It can be seen that for all bits whose big is 1, bigger must also be 1; but for bits where bigger is 1, big may be 1 or 0, such as the 5th and 18th bits; for bits where bigger is 0, big must be It is 0, such as the 1st, 3rd, 4th, 6th, 8th, 10th and other 21 bits. Perform "bit implication" operation on W _a and W _b , the result is that all bits are "1": 1111, 1111, 1111, 1111, 1111, 1111, 1111, 1111, recorded as W _T , if it is an unsigned long An integer is 4294967295. It can be expressed as: W _a →W _b =W _T , and the character string bigger includes big.

If the bit value of biggest is denoted as W _c , there is also: W _a →W _c =W _T , and the character string biggest contains big.

If the bit value of BIG is recorded as W _A , and the bit value W _a of big is subjected to a "bit implication" operation, the same is: W _a → W _A = W _T , and the string BIG is equal to big. The case of letters is not considered here, and it only shows that the bit values of two identical strings are subjected to the "bit implication" operation, and all bits are 1.

If the bit value of digger is recorded as W _d , if the bit value W _a of big is used for "bit implication" operation, the result is 1011, 1111, 1111, 1111, 1111, 1111, 1111, 1111, which is not equal to W _T , That is: W _a → W _d ≠ W _T , the string digger does not contain big.

That is to say, by performing the "bit implication" operation on the bit value W of the two strings, if the result is not equal to W _T , then the string corresponding to the latter item "does not contain"("not more than" and "not equal to ", the same below) the character string corresponding to the preceding item.

The above scheme does not consider the case of letters, if you want to be case sensitive, you need 52 bits, which can also be achieved. But it's not always possible to have one bit per character element. For example, there are 21,000 Chinese characters in the GBK range, and one bit corresponds to one Chinese character. The data storing the bit value will take up a lot of space, and quite a lot of them are meaningless blanks, and it will be meaningless when reading data and bit comparison operations. In practice, one "bit" can be used to correspond to multiple Chinese characters as required. An easy solution is to divide the 21,000 Chinese characters and other symbols in the GBK range into 32 groups according to the encoding, use a long integer data to store the bit value of the string, and set the string "Great Desert Dust Straight Long River Falls" Yen", then:

Chinese character big desert solitary cigarette straight long river fall day round coding 46323 50350 47554 53708 54961 45988 47827 49892 51413 54450 Group 20 15 3 13 18 5 20 5 twenty two 19 Chinese character Frost cold long river fall day sky Career coding 52138 49380 45988 47827 49892 51413 52460 53700 Group 11 5 5 20 5 twenty two 13 5

The codes in the table are obtained by using the function code in excel, among which "big" and "river" are in 20 groups, and "long" and "fall" are in 5 groups, so only 8 corresponding positions are set to 1, then "desert lonely The bit value W _h of "Smoky Straight River Sets the Sun" is:

0010, 1000, 0000, 1010, 0111, 0100, 0000, 0000

Similarly, the "bit value" of W _i of "Long River Sunset" can be obtained as: 0000, 1000, 0000, 0000, 0001, 0100, 0000, 0000, using W _i and W _h as bit "bit implication" operation: W _i → W _h = W _T , there is an inclusion relationship between the two character strings.

"Frost" in "Frost Cold River" is the 11th group, and "cold" and "long" are both the 5th group, then the "bit value" W _j is: 0000, 1000, 0010, 0000, 0001, 0000, 0000 , 0000, W _j and W _h are used as the "bit implication" operation: W _j → W _h ≠ W _T , and there is no inclusion relationship between the two strings. That is to say, use one "bit" to correspond to multiple Chinese characters to obtain the bit value, and perform the "bit implication" operation on the bit values of the two strings. If the result is not equal to W _T , then the string corresponding to the latter item "is not Contains "all character elements" of the character string corresponding to the preceding item, so the "character string" must not be included. For pinyin characters, similarly, one bit can be used to correspond to multiple words, and it is judged that a character string "does not contain" or "may contain" the character elements of another character string.

However, if the "bit implication" operation is performed on the bit values of two character strings, if the result is equal to W _T , the character string corresponding to the later term only "may contain" the character string corresponding to the former term.

If the bit value of gibber is denoted as W _e , and the bit value W _a of big is used for the "bit implication" operation, it also has:

W _a →W _e ＝ W _T

But the string gibber does not contain big.

The "bit value" W _k of "Sunset Tianya" is: 0000, 1000, 0000, 1000, 0000, 0100, 0000, 0000, and W _h is used as a bit "bit implication" operation:

W _k →W _h ＝W _T

However, "the lonely smoke in the desert goes straight to the long river and the sun sets" does not include "the setting sun ends in the sky".

That is to say, there is a difference between bit-marked string retrieval and general string bit-by-bit comparison. Even if the bit values of the two strings have a bit implication, the two strings do not necessarily have an inclusion relationship. If a "bit" corresponds to "a character element", and there is a bit implication relationship between the bit values of the two character strings, then the character string corresponding to the latter item "contains" all the character elements of the character string corresponding to the former item. However, because the arrangement of characters is not considered, it is not sure whether there is a containment relationship between the two strings. If the mark is a "bit" corresponding to a "group of characters", and there are multiple characters in a group of characters, then the string corresponding to the latter item "may" contain all the characters of the string corresponding to the previous item , it is also "possible" not to contain all the characters of the string corresponding to the preceding item, and it is not certain whether the two strings have an inclusion relationship. However, according to the need, the character-by-character comparison method can be used to judge whether there is a containment relationship between the two character strings.

Bit-marked string retrieval, the bit value of the previous item and the next item of the bit operation can be the tag information of the character elements of a string, or the tag information of all the character elements of multiple strings, collectively referred to as "several The bit value of a string "S. "Several character strings" is the same concept of S, that is, S refers to one or more character strings.

Assuming that bit-marked string retrieval is performed on the database, the bit values of string records S ₁ , S ₂ , S ₃ , ... are W ₁ , W ₂ , W ₃ , ... respectively. The bit value of the retrieval keyword S _t is denoted as W _t , and the bit implication operation is performed with W _t and W _n , and the result is W _T , then the string S _n contains or may contain all the characters of S _t . A record set composed of qualified S _n is denoted as R _i . The time taken for retrieval is called T _i . Usually, it is necessary to use the bit-by-bit comparison of character strings in R _i to obtain the final result set R _z , and the retrieval time is called T _z .

Therefore, the total time spent by the bit-marked character string retrieval method is T _i +T _z . If T _i is expected to be low, for a 32-bit processor, the best data to store the bit value is 32 bits. For a string fuzzy retrieval, R _z is certain, and the way to reduce T _z is to minimize the initial result set R _i as much as possible. The fewer the number of bits n for storing bit values, the more characters one bit corresponds to, the worse the filtering effect, and the larger R _i will be; the longer the average length of the string, the larger R _i will be. There is another factor affecting the size of R _i : the longer the search keyword, the smaller R _i is.

Assuming that the number of digits used for the mark is n, the "1" of the character string value is m, and the "1" of the search key value is k, then the screening probability of bit comparison can be calculated by the following formula, and the smaller the value, the better good:

${\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; II</span>}}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}^{\mathrm{<span\; class="notranslate">\; k</span>}}}{{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}}^{\mathrm{<span\; class="notranslate">\; k</span>}}}<span\; class="notranslate">\; =</span>\frac{\frac{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}}{\frac{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}$

n is 32, and the screening probabilities for the values of m and k are calculated as follows:

m k=1 k=2 k=3 k=4 twenty four 0.75 0.556451613 0.408065 0.295495 twenty two 0.6875 0.465725806 0.310484 0.20342 20 0.625 0.383064516 0.229839 0.134733 18 0.5625 0.308467742 0.164516 0.085095 16 0.5 0.241935484 0.112903 0.050612 14 0.4375 0.183467742 0.073387 0.027836 12 0.375 0.133064516 0.044355 0.013765 10 0.3125 0.090725806 0.024194 0.00584 8 0.25 0.056451613 0.01129 0.001947

Among the three factors that affect the screening probability, the length of the keyword used by the user for retrieval determines the size of k, and the length of the record string determines the size of m, but the length of the record string and the length of the keyword used for retrieval are uncontrollable and controllable The factor is the number of digits n used for marking, and the number m and k of "1"s after a string of a certain length are also affected by n, so it is important to maintain a sufficient ratio between n and m.

A few suggestions:

1. The 32-bit CPU is marked with a long integer, which is most conducive to bit value comparison. If it is an unsigned integer, W is 32 bits. If it is a signed integer, only 31 bits are convenient for marking. If the average length of the string is greater than 16 characters and the number of records is large, in SQL Server 2000, 63 bits of the data type bigint can be used for marking, and the characters are divided into 63 groups accordingly. Of course, for a 32-bit processor, using bigint to store bit values, it will take more time to read and compare bits. In fact, any data type that is convenient for bit operations in any database can be used to mark strings, and it is naturally better to use unsigned data types. For a 64-bit CPU, of course, 64 bits should be used to mark the character string, so as to fully utilize the performance of the CPU and improve the discreteness of the "bit value".

2. If the cpu is 32 bits, and the length of the strings varies greatly, the records can be divided into two tables. The short string table is marked with 32 bits, and the long string table is marked with 64 bits. Union is used in the query The command combines the query results of two tables.

3. For the grouping of character elements, the frequency balance is the best, and the speed of marking bit values should also be taken into consideration. Carrying out modulo operation according to the internal code of Chinese characters, taking the remainder and grouping is easy to realize, but it is not optimal grouping, and the operation speed of modulo operation and division is slow. It can be considered to divide Chinese characters into 32 groups by taking a certain 5 bits of the internal code of Chinese characters, the speed will be faster and the effect may be better.

In addition to retrieval in the usual sense, the database string can be "reversely retrieved" by using the bit mark method, that is, the W _n value of the database string S _n is the previous item, and the W _t value of the search keyword S _t is the subsequent item Carry out the bit implication operation, and according to whether all the bits are "1" in the result, that is, W _n →W _t =W _T , it is possible to filter out those constituent characters in the database that may be included in the retrieval keyword S _t S _n .

Naturally, the calculation of the screening probability for reverse retrieval is reversed. Assuming that the database and keywords are all marked with "1 _" , the number of digits used for the mark is n, the number of "1"s in the value Wn of S _n after the bit mark is m, and the number of "1" after the search keyword mark is k. Then the probability that the retrieval keyword S _t contains or may contain all its characters can be calculated by the following formula:

${\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; II</span>}}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}^{\mathrm{<span\; class="notranslate">\; m</span>}}}{{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}}^{\mathrm{<span\; class="notranslate">\; m</span>}}}<span\; class="notranslate">\; =</span>\frac{\frac{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}}{\frac{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}$

2. Test analysis

Use the above method to test a database with Chinese characters as the main part and some English and numbers: the number of records is more than 267,000, the number of characters is more than 3,473,000, the average length of the string is 12.989, and the bit value is marked with a long integer. The programming language is VB. The system is Window xp, CPU Celeron 800Hz, memory 256M, Gigabyte 810 motherboard, hard disk 40G. The overall retrieval time is denoted as T. Apparently, for any bit tag retrieval, the bit values of all records must be read and compared with the bit values of keywords. The time used can be considered as a constant, called T ₀ , but it is not easy to measure directly. The qualified record set after bit value comparison is denoted as R ₁ , and T ₁ is not easy to measure directly when comparing and searching R ₁ bit by bit, but it is related to the size of R ₁ , and R ₁ can be obtained. Another factor that affects retrieval time is the size of the final result set R ₂ . According to T, R ₁ , R ₂ obtained from 120 tests, regression analysis obtained the following equation:

$\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; T</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0.268</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 0.000,008,625</span>}{\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 0.000,0270,2</span>}{\mathrm{<span\; class="notranslate">\; R</span>}}_{\text{<span class="notranslate"> 2</span>}}$

Adjusted coefficient of determination

Significance test of regression model F＝5265.814

Greater than F _0.01 (2,117)＝4.791

Significance test of constant t ₀ =86.610

Significance test of R ₁ t ₁ =74.263

Significance test of R ₂ t ₂ =25.489

are greater than t _0.01 (117)＝2.6185

It can be seen that the reliability of the regression equation is very high. The constant, that is, the time taken to read the bit values of all records and compare them with the bit values of keywords, that is, T ₀ , is 0.268 seconds. The average time for 120 string-by-bit comparisons at the same time is 2.1739 seconds. It can be seen that the time T ₀ used for bit value comparison is only one-eighth of the time used by the usual bit-by-bit comparison method. However, the overall time of bit-marked character string retrieval is also related to R ₁ and R _2. In this test, n=31, the average length of the character string is 12.989, and there is overlap after the mark. The average number m of "1" is about 11 to 12. Here, it is calculated by 12. If the distribution of characters in the above database string is normal, and the marked "1" is evenly distributed, R ₁ can be calculated according to the probability. The final result set R ₂ has nothing to do with the screening effect. Here, it is specified as 240. In an ideal state, the retrieval time when k is 1 to 12 after keyword tagging can be calculated according to the regression equation as follows:

k R ₁ R ₂ T 1 103354.8 240 1.16592 2 37896.77 240 0.601344 3 13067.85 240 0.387195 4 4200.381 240 0.310713

5 1244.557 240 0.285219 6 335.0732 240 0.277375 7 80.41756 240 0.275178 8 16.75366 240 0.274629 9 2.91368 240 0.27451 10 0.39732 240 0.274488 11 0.03784 240 0.274485 12 0.001892 240 0.274485

It can be seen that compared with the average time of 2.1739 seconds for the usual string retrieval method, bit-marked string retrieval has a great performance advantage. However, different hardware, as well as the data type used in marking, especially the size of n, the distribution of database characters, and the grouping of characters in marking, all affect the time spent on bit-marked string retrieval, so this regression equation is only a reference .

There are only 26 letters in English. If the string is very long and every record contains every letter, the bit mark search will lose its filtering effect. However, a test on an English database with 242,000 records and 7,493,000 characters shows that bit-marked string retrieval is usually also feasible for pinyin characters. The database string data type is varchar, the field length is 56, and the average string length is 30.846. 26 letters are marked with 26 bits of a long integer, regardless of case, spaces and other characters are ignored. Due to the unbalanced use frequency of English letters, there are only 3,213,052 "1"s after marking, and the average number of "1"s in each record is 13.2266. A record contains each letter.

120 character-by-character comparison searches were performed on the database, and the average time was 4.573 seconds. At the same time, bit mark searches were performed. According to 120 times of T, R1, R2, regression analysis obtained the following equation:

$\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; T</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0.265</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 0.000,019,36</span>}{\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 0.000,0362</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 3</span>}{\mathrm{<span\; class="notranslate">\; R</span>}}_{\text{<span class="notranslate"> 2</span>}}$

Adjusted coefficient of determination

Significance test of regression model F＝55405.88

Greater than F _0.01 (2, 117) = 4.791

Significance test of constant t ₀ =36.400

Significance test of R ₁ t ₁ =121.733

Significance test of R ₂ t ₂ =77.409

are greater than t _0.01 (117)＝2.6185

The following is the letter distribution statistics table of the database:

letter the number of records containing the letter percentage letter the number of records containing the letter percentage t 227167 0.935136 h 114263 0.470365 r 222338 0.915257 u 109376 0.450248 e 221713 0.912685 g 97339 0.400697 a 213249 0.877842 f 83452 0.343531 c 210116 0.864945 W 71228 0.293211 no 204225 0.840695 b 67065 0.276074 o 201082 0.827757 the y 60698 0.249864 i 195734 0.805742 v 59351 0.244319 the s 195639 0.805351 k 47379 0.195036 l 169753 0.698791 x 15150 0.062365 d 159202 0.655357 q 7258 0.029878 m 125449 0.516413 j 6351 0.026144 p 122168 0.502906 z 6307 0.025963

It can be seen from the above table that the three letters t, r, and e have the highest frequency in this database. Using tree as the retrieval keyword, 7 records containing tree were actually retrieved, and R ₁ was 188491, which took 3.655 seconds. The bit comparison retrieval took 4.465 seconds. For example, according to the frequency of the three letters t, r, and e in the above table, the calculation can be obtained:

R1＝242, 924*0.935136*0.915257*0.912685＝242, 924*0.781158＝189762

Then calculate the retrieval time according to the regression equation:

$\begin{array}{c}\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; T</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0.265</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 0.000,019,36</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 189762</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 0.000,0362,3</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 7</span>}\\ <span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 3.939</span>}\end{array}$

It can be seen that even for words such as tree, which are completely composed of high-frequency letters, bit tag retrieval still has performance advantages. In fact, most words in English have more than 4 letters. If there is a low-frequency letter among them, the screening effect of bit marks is very good, which is equivalent to the "short board effect". List thirty test data for reference:

3. Overlap probability of bit marks

The number of letters in pinyin text is small, so the frequency of repeated letters is high, such as bigger, biggest and other words have two g, but only the seventh "bit" is marked as 1. For Chinese character strings, the probability of the same Chinese character appearing repeatedly in a string is low, but for grouping Chinese characters, several Chinese characters in a string may belong to the same group, such as in the grouping above, "big" "he "The same in 20 groups, "long" and "drop" in the same 5 groups, overlapping in a "bit" after the mark. Even if the grouping achieves character frequency equalization, there is the problem of overlapping string tokens. Suppose the number of digits used for marking is n, and the number of character elements is m. where the probability of no overlap at all is:

$\mathrm{<span\; class="notranslate">\; P</span>}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}}^{\mathrm{<span\; class="notranslate">\; m</span>}}}{{\mathrm{<span\; class="notranslate">\; no</span>}}^{\mathrm{<span\; class="notranslate">\; m</span>}}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Center\; Dot;</span><span\; class="notranslate">\; \&CenterDot;</span><span\; class="notranslate">\; \&Center\; Dot;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; no</span>}}^{\mathrm{<span\; class="notranslate">\; m</span>}}}$

Obviously, when n is constant, every time m increases by 1, the new items in the numerator will decrease by 1, while the new items in the denominator will remain unchanged, and the probability of no overlap at all is getting lower and lower. Assuming that 32 bits are used for marking, and the string length m is 7, the probability of no overlap at all:

${\mathrm{<span\; class="notranslate">\; P</span>}}_{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 7</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 32</span>}}^{\mathrm{<span\; class="notranslate">\; 7</span>}}}{{\mathrm{<span\; class="notranslate">\; 32</span>}}^{\mathrm{<span\; class="notranslate">\; 7</span>}}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Center\; Dot;</span><span\; class="notranslate">\; \&Center\; Dot;</span><span\; class="notranslate">\; \&Center\; Dot;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 7</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; 32</span>}}^{\mathrm{<span\; class="notranslate">\; 7</span>}}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 31</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 30</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 29</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 28</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 27</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 26</span>}}{\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 32</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 16,963,914,240</span>}}{\mathrm{<span\; class="notranslate">\; 34,359,738,368</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0.4937</span>}$

The following table is marked with 32 bits, and when the string length m is 1 to 24, the probability of no overlap at all:

Overlap means the loss of information. A certain degree of overlap is inevitable and acceptable, but if the overlap ratio is too high, it will affect the performance of bit label retrieval, so the probability of overlap is also worthy of attention. Marked by n bits, the length of the string is m characters, and the probability calculation formula for overlapping k "1"s is:

$\mathrm{<span\; class="notranslate">\; P</span>}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}}^{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span>\mathrm{<span\; class="notranslate">\; A</span>}}{{\mathrm{<span\; class="notranslate">\; no</span>}}^{\mathrm{<span\; class="notranslate">\; m</span>}}}$

in $A=\underset{m_1+m_2+\&Center\; Dot;\&Center\; Dot;\&Center\; Dot;+m_k=m}{\mathrm{\&Sigma;}}\frac{m!}{m_1!m_2!\&Center\; Dot;\&Center\; Dot;\&Center\; Dot;m_k!}$

The summation here is to take all positive integer solutions satisfying m ₁ +m ₂ +...+m _k =m, and the number of groups is

Assuming that 32 bits are marked, the length of the string is 7 characters, and the overlap is 3 bits, that is, m ₁ +m ₂ +m ₃ =7, there are 15 groups, and the probability calculation is as follows:

7! m ₁ m ₂ m ₃ m ₁ ! _m2 ! _m3 ! 7! /(m ₁ !*m ₂ !*m ₃ !) 5040 1 1 5 1 1 120 42 5040 1 2 4 1 2 twenty four 105 5040 1 3 3 1 6 6 140 5040 1 4 2 1 twenty four 2 105 5040 1 5 1 1 120 1 42 5040 2 1 4 2 1 twenty four 105 5040 2 2 3 2 2 6 210 5040 2 3 2 2 6 2 210 5040 2 4 1 2 twenty four 1 105 5040 3 1 3 6 1 6 140 5040 3 2 2 6 2 2 210 5040 3 3 1 6 6 1 140 5040 4 1 2 twenty four 1 2 105 5040 4 2 1 twenty four 2 1 105 5040 5 1 1 120 1 1 42 1806

$\mathrm{<span\; class="notranslate">\; P</span>}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; 32</span>}}^{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; \&CenterDot;</span>\mathrm{<span\; class="notranslate">\; A</span>}}{{\mathrm{<span\; class="notranslate">\; 32</span>}}^{\mathrm{<span\; class="notranslate">\; 7</span>}}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 4960</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 1806</span>}}{\mathrm{<span\; class="notranslate">\; 34,359,738,368</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0.000261</span>}$

It is marked with 32 bits, and the length of the string is 7 characters. The probability of k after marking is 1-7 is as follows:

k Number of permutations rank percentage cumulative percentage k* number of permutations 7 16963914240 0.493714884 0.493714884 1.18747E+11 6 13701623040 0.398769714 0.892484598 82209738240 5 3383116800 0.098461658 0.990946256 16915584000 4 302064000 0.008791219 0.999737475 1208256000 3 8957760 0.000260705 0.99999818 26873280 2 62496 1.81887E-06 0.999999999 124992 1 32 9.31323E-10 1 32 2.19108E+11

The weighted average number of "1" after marking is 6.376881392.

4. Logical algebra principles related to bit marks and 0 marks

A certain bit of the bit value W of the string S is "1", which means that the proposition "the string S has a certain character element or one of a certain group of character elements" is true. For two strings S _a and S _b , certain k bits of W _a are 1, which means that the proposition "string S _a has certain k characters or one of certain k groups of characters" is true; if All corresponding certain k bits of W _b are 1, which means that the proposition "string S _b has certain k characters or one of certain k groups of characters" is also true. Naturally, some mk bits of W _b may be 1, while some mk bits of W _a are 0. This relationship is expressed by the logic algebra formula: W _a → W _b = W _T , which is intuitive and easy to understand. But not all programming languages and database systems have "bit implication" operators, so the application needs to be transformed according to the principle of logical algebra.

Theorems of operation from logic algebra It can be seen that if a→b=1, then Similarly, for the bit value of n bits: if W _a →W _b ＝W _T , then

${\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; W</span>}}}_{\mathrm{<span\; class="notranslate">\; a</span>}}<span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; b</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; T</span>}}<span\; class="notranslate">\; .</span>$

Also get:

W _a |W _b =W _b

W _a &W _b =W _a

Theorems of Logical Operations $W_a\&Right\; Arrow;W_b\&DoubleLeftRightArrow;{\stackrel{\&OverBar;}{W}}_b\&Right\; Arrow;{\stackrel{\&OverBar;}{W}}_a$ It can be seen that

W _a →W _b ＝W _T , then

Therefore, a data W _T whose "bit" is 1 can be used to mark the bit value. If the string contains a certain character element, the corresponding bit is marked as 0. This method is called 0 mark. like:

bit value of big 1011110101111111111111111111111

bit value of bigger 10110101011111111011111111111111

obviously ${\stackrel{\&OverBar;}{W}}_b\&Right\; Arrow;{\stackrel{\&OverBar;}{W}}_a=W_T.$

Also get:

${\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; W</span>}}}_{\mathrm{<span\; class="notranslate">\; b</span>}}<span\; class="notranslate">\; |</span>{\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; W</span>}}}_{\mathrm{<span\; class="notranslate">\; a</span>}}<span\; class="notranslate">\; =</span>{\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; W</span>}}}_{\mathrm{<span\; class="notranslate">\; a</span>}}$

It is more intuitive to use a truth table:

W _a w _b W _a →W _b ＝W _T W _a &W _b =W _a W _a |W _b =W _b 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 1 1 1 1 1

What has been explained above is how to use the most common bit operators to compare bit values, and the principle of screening probability is the same. Of course, when 0 is marked, both m and k refer to the number of 0s. However, the number of bit operators provided by each programming language and database is different, and the specific operations of other bit operators can be deduced according to the principles of logical algebra. Using the principles of logical algebra and carrying out equivalent transformations, the formulas obtained should of course be simple and applicable, rather than becoming more and more complicated.

Another point is that if the programming language or database system provides the function of setting "bit" to 1 or 0, then the bit "flag" can be used directly. If the database system programming language does not provide a position of 1, the bit "or" (or) operation can be used to mark 1.

First group the character elements, if 32 bits are used to mark, then assign 2 ^32-n to the nth group. From the binary point of view, the nth bit of the value from left to right is 1, and the rest of the bits are 0, which is called "basic bit value". The bit value of the string can be obtained by performing an "or" (or) operation on the "basic bit values" of all the character elements of a string. Of course, it is also possible to assign 2 ^n-1 to the nth group of "basic bit values". From a binary point of view, the nth bit from right to left is 1, and the remaining bits are 0. In fact, in a specific database, record character strings and search keywords are marked, and characters and bits have a fixed correspondence, regardless of whether it is from right to left, from left to right, or in other order.

If it is to mark 0, first give the nth group of characters a "basic bit value" in which the nth bit is 0 and the rest of the bits are 1, and then the "basic bit value" of all the character elements of the specific string is assigned "And" (and) operation, you can get the bit value of the string

As for the calculation method of the marker overlap probability, the 0 marker and the 1 marker are interlinked.

5. Multi-bit mark and group mark

1. Multi-bit flag

On the basis of single "bit" (bit) flags, multi-"bit" (bit) flags are described below. If there are more digits n for storing bit values, but the length of the character string is small, the combination of j bits can be used to mark a group of character elements, and there are a total of The combination of ones, the corresponding sub-characters are group, if a character element P of S belongs to the rth group, mark the j bits in W that constitute the combination of the rth bit as 1. When j is 1, it is the above-mentioned single "bit" (bit) mark.

Let n be 32 and j be 2, then divide the characters into Group, that is, 496 groups, marked with "1", if the character element belongs to the first group, the two "bits" of W 1 and 2 are marked as "1"; if the character element belongs to the second group, then W The two "bits" 1 and 3 of W are marked as 1, and if the character element belongs to the third group, the two "bits" of W 1 and 4 are marked as 1, ....

Assuming that the 2nd and 5th bits of the bit value of the Chinese character "before" are 1, and the 23rd and 29th bits of the bit value of the "Jing" word are 1, then the word "foreground" has 2, 5, 23, and 29 Four bits are 1, set the 2nd, 23rd two bits of the bit value of " far " to be 1 again, the 5th, 29th two bits of " big " bit value are 1, then word " great " is also 2,5, The four bits 23 and 29 are 1, and if you use the bit value of "foreground" to search, "Yuanda" will appear in the result, and vice versa, that is, a character string containing "unrelated group characters" will appear in the search result, but due to Each group contains fewer Chinese characters than the single "bit" mark, so the screening effect can be improved. The purpose of using multiple markers is to improve the screening effect, and the calculation of the screening probability is the same as that of unit markers. The following calculates the screening probability when the length of the string is 4 characters, the length of the search keyword is 2 characters, and j is 1, 2, 3, or 4. The lower the value, the better:

j is 2, regardless of overlapping, then m after character string marking is 4*2=8 1s, and k after retrieval keyword marking is 2*2=4 1s.

j is 3, that is, the character element is divided into Groups, that is, 4960 groups, regardless of overlapping, m after character string marking is 4*3=12 1s, and k after retrieval keyword marking is 2*3=6 1s.

j is 4, that is, the character element is divided into Groups, that is, 35960 groups, regardless of overlapping, m after character string marking is 4*4=16 1s, and k after retrieval keyword marking is 2*4=8 1s.

${\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}^{\mathrm{<span\; class="notranslate">\; k</span>}}}{{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}}^{\mathrm{<span\; class="notranslate">\; k</span>}}}<span\; class="notranslate">\; =</span>\frac{\frac{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}}{\frac{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 3</span>}}{\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 31</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0.012097</span>}$

${\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; =</span>\frac{\frac{\mathrm{<span\; class="notranslate">\; 8</span>}<span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 8</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}}{\frac{\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}}<span\; class="notranslate">\; =</span>\frac{\frac{\mathrm{<span\; class="notranslate">\; 8</span>}<span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; !</span>}}{\frac{\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; 28</span>}<span\; class="notranslate">\; !</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 8</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 7</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 6</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; *</span>}{\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 31</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 30</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 29</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0.00194661</span>}$

${\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; =</span>\frac{\frac{\mathrm{<span\; class="notranslate">\; 12</span>}<span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; 6</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 12</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 6</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}}{\frac{\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; 6</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 6</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}}<span\; class="notranslate">\; =</span>\frac{\frac{\mathrm{<span\; class="notranslate">\; 12</span>}<span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; 6</span>}<span\; class="notranslate">\; !</span>}}{\frac{\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; 26</span>}<span\; class="notranslate">\; !</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 12</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 11</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 10</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 9</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 8</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 7</span>}<span\; class="notranslate">\; *</span>}{\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 31</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 30</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 29</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 28</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 27</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0.00101965</span>}$

${\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 4</span>}}<span\; class="notranslate">\; =</span>\frac{\frac{\mathrm{<span\; class="notranslate">\; 16</span>}<span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; 8</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 16</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 8</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}}{\frac{\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; 8</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 8</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}}<span\; class="notranslate">\; =</span>\frac{\frac{\mathrm{<span\; class="notranslate">\; 16</span>}<span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; 8</span>}<span\; class="notranslate">\; !</span>}}{\frac{\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; twenty\; four</span>}<span\; class="notranslate">\; !</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 16</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 15</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 14</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 13</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 12</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 11</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 10</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 9</span>}}{\mathrm{<span\; class="notranslate">\; 32</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 31</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 30</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 29</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 28</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 27</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 26</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 25</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0.00122358</span>}$

Multi-digit tags are especially meaningful if the search keyword length is 1 or 2 characters. But when the storage bit value n is constant, the value of j is not as big as possible. As the above calculation shows, when n is 32 and m is 4, j is the best effect when it is 3. If it continues to increase, the screening effect cannot be improved, and the mark When the overlap ratio increases, the labeling operation is more complicated. n must be sufficiently large if multi-bit tokenizing long strings.

2. Group marking:

For example, divide the 32 bits of an unsigned long integer into two groups of 17 and 15, and mark them separately. The length of the string m is 4. Regardless of the problem of overlapping marks, there are four 1s after the mark, and the length of the keyword is set to 2. If there are two 1s after that, the screening probability is:

$\mathrm{<span\; class="notranslate">\; P</span>}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 17</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; 17</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}<span\; class="notranslate">\; \&times;</span>\frac{\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 15</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}{\mathrm{<span\; class="notranslate">\; 15</span>}<span\; class="notranslate">\; !</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; !</span>}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 3</span>}}{\mathrm{<span\; class="notranslate">\; 17</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 16</span>}}<span\; class="notranslate">\; \&times;</span>\frac{\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 3</span>}}{\mathrm{<span\; class="notranslate">\; 15</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 14</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 12</span>}}{\mathrm{<span\; class="notranslate">\; 272</span>}}<span\; class="notranslate">\; \&times;</span>\frac{\mathrm{<span\; class="notranslate">\; 12</span>}}{\mathrm{<span\; class="notranslate">\; 210</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0.002521</span>}$

Obviously, the screening effect can also be improved. Certainly, to carry out this kind of optimization, the bit n of the mark must be several times m as well. This optimization method can be adapted when used for long strings, that is, two different character grouping methods are used, and two data are respectively marked to obtain two groups of W and W'. When searching, first obtain the W _t of the keyword with one of the marking methods, compare it with the W _n value of the database, and filter out R ₁ . In _R1 , the _W't of the keyword is obtained by the marking method of the second group, compared with the _W'n value of the database to obtain _R2 , and then in _R2 , the final result set R is obtained by the usual bit-by-bit comparison method _z . Compared with the previous optimization method, it also increases the storage space of the bit value. This optimization method does not need to read all W' _n for comparison with W' _t .

Both 0 mark and 1 mark can carry out multi-bit mark and group mark, group mark can also be combined with multi-bit mark, and different groups can also be 0 mark and 1 mark respectively. Of course, it is better to apply. 0 mark, multi-bit mark and group mark can all be used for inverse retrieval.

The bit-marked character string retrieval speed is faster than the prime number substitution character retrieval speed, but when there are many types of character elements, it is not easy to implement with one bit corresponding to a character element; if multi-bit tags are used, the search results do not contain "target group characters". meta" and strings containing only "unrelated group characters meta" are mixed in. Substituting a character element with a prime number can avoid such a mixed phenomenon in the retrieval results. In the application, you can first use the bit-marked character string retrieval for primary screening, and then use the prime number substitution character retrieval for secondary retrieval. If necessary, Then use the usual string bit by bit comparison method to get the final result.

6. Application of bit-marked string retrieval technology in speech input and Chinese pinyin input:

There are many homophones and homophones in Chinese, so it is necessary to filter suitable words by pinyin in Chinese phonetic input and pinyin input, and the bit mark method "reverse search" can be used for this aspect.

Regardless of the tone, Chinese has more than 400 syllables, and it is not convenient to correspond to a syllable with one bit, and 64 bits of 8 bytes can be used to correspond to the initial consonant and the final vowel of the Chinese phonetic alphabet. There is a database of Chinese word collocation and basic sentence patterns, including the basic sentence pattern "he graduated", the pinyin is "tabiyele", and the post-mark value W ₁ is:

1000, 0101, 0000, 0000, 0000, 0001, 1011, 0000, 0000, 0000, 0000, 0000, 0000, 0000, 0000, 0000

If the phonetic conversion or pinyin input "tazaojiubiyele", the post-mark value W _t is:

1000, 0101, 0001, 0010, 0000, 0001, 1011, 0000, 1000, 0000, 1000, 0000, 0000, 0000, 0000, 0000

W ₁ →W _t =W _T

Then "he graduated" is the basic sentence pattern that "tazaojiubiyele" can refer to. After processing, "he zaojiu graduated" can be obtained, where "graduated" is a predicate and a verb, and the words with the pinyin of "zaojiu" in the thesaurus are "Early" and "bringing up" "jujube wine", if other aspects such as grammar, semantics, and word frequency can play a supporting role, it can be further converted into "he has graduated a long time ago". Due to the diversity of phonetic and rhyme coordination, sentence patterns such as "tebayile" in pinyin will also appear in the preliminary results obtained by place value comparison. On the basis of the bit-marked character string, a prime number substitution method in which a prime number corresponds to a syllable can be used for secondary screening to obtain a closer result.

If there is a collocation "building" between "lou" and the quantifier "dong" in the word collocation and basic sentence patterns, and there is also a collocation "high building" between "lou" and the adjective "high" that often modifies it, you can press their initials The vowels are marked. If voice conversion or pinyin input "zhedongxiezilouhengao" is also marked according to the consonant and final consonant, all word collocations in the database and the bit value W _n of the basic sentence pattern are compared with it, and collocations such as "buildings" and "high buildings" can be screened out. For reference, after processing, "zhe building xiezi building hen height" can be obtained, where xiezi or xiezilou can get "writing" or "office building" from the lexicon. If other aspects such as grammar, semantics, and word frequency can play an auxiliary role, you can Convert "zhedongxiezilouhengao" to "this office building is very tall". Other Chinese collocations and corresponding place values can be obtained similarly. Administrative divisions such as "provinces" and "provinces and counties"; numbers such as "Qiba" and "Wanqian"; quantifiers "jinliang" and "yuanjiao"; and even the combination of surnames "Zhang Li" and "Zhang Liu". If you input "hubeishengxianningshi", you can get "Xianning City, Hubei Province" according to the above method. If you input "zhanglonglihu", you can get "Zhang longlihu". If you enter "qiwansanqian", you can get "seven thousand three thousand". Similarly, on the basis of the bit-marked character string, a prime number substitution method in which a prime number corresponds to a syllable can be used for secondary screening to obtain a closer result.

In addition, because the frequency of use of Chinese initials and finals is unbalanced, when the unit is marked, 64 "bits" of 8-byte data correspond to the initials and finals of Chinese Pinyin. When searching for some syllables such as li, due to Both 1 and i are high-frequency initials and finals, and the screening effect may not be good. Double-digit marks can be considered, that is, n is 32, j is 2, that is, 496 groups, corresponding to 400 syllables in Chinese, and the database Calculate and make it as balanced as possible. Of course, if 400 syllables are marked with double digits, there will definitely be "non-purpose" sentence patterns and collocations in the preliminary results. On the basis of the search and screening of digit markers, a prime number substitution method of one prime number corresponding to one syllable can be used for secondary Filter to get closer results.

This technology can also be used in Chinese word segmentation, and the words, reference collocations and sentence patterns in the thesaurus are marked with pinyin, and keywords (actually sentences) are also marked with pinyin, and the bit implication operation is performed to obtain R _i , can effectively narrow down the search scope; of course, words, reference collocations and sentence patterns in the thesaurus can also be grouped and marked with bit values according to internal codes, and keywords can also be marked with the same grouped bit values to perform bit implication operations. It is also possible to effectively narrow down the scope of search, and then complete the decomposition of keywords (that is, sentences) with the aid of other methods.

In English, there are many phenomena of continuous reading and phonetic rheology, which are not as clear as Chinese syllables. Bit-marked string retrieval technology can also be used to filter reference words and phrases. Suppose the database has a phrase in the morning, according to the vowel, consonant i, n, m, n, i, n are marked to obtain the bit value. After the voice input is converted, the corresponding to the It is relatively fuzzy and can be eliminated, and other relatively loud i, n, m, n, i, n are marked to obtain the bit value, and compared with the bit value of the database reference vocabulary and phrase, the phrase in the morning can be obtained, and other pronunciations contain i, n, m, Phrases or words of n, i, η. On this basis, the method of substituting syllables with prime numbers further narrows the scope, and then according to the context, with the assistance of grammar, semantics, and word frequency, choose in the morning.

The method of bit-marked character string retrieval and related probability calculation formulas and logical algebra principles are described above, and the emphasis is placed on the screening of character string records in the database. From a programming point of view, the data structure of the database is diverse, and various data structures are not only used in the database. However, as a string algorithm, bit-marked string retrieval technology can be used for string search in various data structures, such as string fuzzy search in large arrays. As for the fuzzy search of character strings in small arrays, it may not be necessary, because the marking of character strings also requires time and space.

Detailed ways

The present invention has obtained good realization in the fuzzy retrieval of Chinese character string database and English character string database, below is to the Chinese character string database in SQL SERVER2000, with the vb6.0 code that " 1 " is marked, other programming language, database The fuzzy retrieval of bit-marked strings can refer to the implementation.

1. Create a database

Suppose the database shuku has a table biao, which has a field shuming, the data type is nvarchar, and the length is 40. Another field wei is created, the data type is "long integer", that is, 4 bytes, with 32 bits, one of which is a sign bit, and the remaining 31 bits can be used for marking.

2 There is no command to directly set the "bit" to "1" or "0" in vb6.0, so use the "or" operation of the bit to "mark" the database string

dim shuzu(30)As Long

'Define an array of long integers with 31 elements.

shuzu(0)=1

For x＝1 To 30

shuzu(x)=2*shuzu(x-1)

Next

'Assign values to the 31 elements of the long integer array, from 1, 2, 4, 8, 16 to 1073741824. From the binary point of view, one bit is 1, while the rest are 0, which is the "basic bit value".

Dim biaostr As String

'Store the currently processed string

Dim weizhi As Long

'Store the bit value of the string

Dim weizhilin As Long

'Store the basic bit value of a character

Dim x As Integer

biaors. MoveFirst

'Move to the first record of the database recordset biaors

do

weizhilin=0

weizhi=0

With biases

biaostr=.Fields("shuming")

End With

'Read the string of a record and assign it to the string variable biaostr

For x＝1 To Len(biaostr)

index＝Abs(Asc W(Mid(biaostr, x, 1))Mod 31)

'Take a character from the string variable biaostr, and use the internal code of the character to operate modulo 31, then take the absolute value, and assign it to index, that is, to group the character elements.

weizhilin=shuzu(index)

'Assign the array shuzu (index) value to weizhilin, which is one of 1, 2, 4, 8, 16 to 1073741824.

weizhi＝weizhi Or weizhilin

'The "or" operation of "basic bit value" weizhilin value and weizhi of a character.

Next

'The end of the loop, get the "bit value" of the current string

With biases

.Fields("wei")＝weizhi

End With

biaors.Update

'Store the "bit value" weizhi into the field wei of the current record

biaors.MoveNext

'Process the next record

Loop While Not biaors.EOF

3. Use the "and" operation of bits to perform fuzzy retrieval of database strings

Dim shuzu(30)As Long

shuzu(0)=1.

For x＝1 To 30

shuzu(x)=2*shuzu(x-1)

Next

'Define a 31-element long integer array, assigned values from 1, 2, 4, 8, 16 to 1073741824, which is consistent with the array of "mark".

Dim weizhi As Long

'Store the bit value of a string

Dim weizhilin As Long

'Store the bit value of a character

Dim textstr As String

'store search string

Dim x As Integer

weizhilin=0

weizhi=0

textstr=Text1.Text

'Text1.Text is the search keyword in the text box

For x＝1 To Len(biaostr)

index=Abs(Asc W(Mid(textstr,x,1))Mod 31)

weizhilin=shuzu(index)

weizhi＝weizhi Or weizhilin

Next

'Mark the search keywords to get the "bit value" weizhi, the method is consistent with the database string "marking" method.

strQuery = "select*from(SELECT*FROM biao WHERE(wei&"&weizhi&")="&weizhi&")DERIVEDTBL WHERE(shuming like′%″&textstr&″%′)″

'There is no bit implication operator in SQL SERVER 2000. Here, the "bit value" weizhi of the search keyword and the "bit value" weizhi of each record in the database are used for "and" (and) operation, and the "and" (and) operation is selected The result is equal to the record of the "bit value" weizhi of the keyword (you can also use (wei|"&weizhi&")=wei) to get the preliminary result set R _i , and then perform a secondary search with the usual string fuzzy search method to get the final result R _z . This is the query statement of SQL SERVER 2000, other databases may be slightly different.

Adodc 1.RecordSource＝strQuery

Adodc 1. Refresh

'Execute the search

DataList 1.ListField="shuming"

DataList l.ReFill

'Display the current search results in the list box.

Claims (6)

1. A character string fuzzy search method, characterized in that: Use the data W with n bits (bits) that are all 0 to mark the character meta-information that constitutes the string, and take j bits as a combination, then there are The combination of ones, correspondingly divides all characters into Group, with a combination of bits corresponding to a group of character elements, marked; if a character element P ₁ of the string S belongs to the rth group, then the j bits of W that constitute the combination of the rth bit are marked as 1, Similarly, W is marked according to the group to which other character elements P ₂ , P ₃ , P ₄ ... of S belong, and after all character elements are marked, W has the character meta information of S recorded, which is called 1 of the string S tag bit value; Use data with n bits all 1 To mark the meta-information of the characters that make up the character string, taking the j bits as a combination, there are a total of The combination of ones, correspondingly divides all characters into Group, with a combination of bits corresponding to a group of character elements, marked; if a character element P ₁ of the string S belongs to the rth group, then the The j bits that constitute the combination of the rth bit are marked as 0, similarly, according to the group pairs to which other character elements P ₂ , P ₃ , P ₄ ... of S belong markup, after completing all character meta-tags The character meta information of S is recorded, which is called the 0 mark bit value of the string S; Note that the 1 flag value of the string S _a is W _a , and the 0 flag value of S _a is Record the value of the 1 mark bit of the string S _b as W _b , record the value of the 0 mark bit of S _b Use the following method for string comparison: 1. compare with W _a and W _b , if all W _a is the position of 1, the corresponding bit of W _b is also 1, then S _b includes or may include all character elements of S _a ; II. to and compare if all bit of 1, The corresponding bit is also 1, then S _b contains or may contain all the characters of S _a ; III. With W _a and To compare, if All the corresponding bits with W _a are not 1 at the same time, then S _b contains or may contain all the characters of S _a ; IV. to Compare with W _b if All the corresponding bits of W _b are not 0 at the same time, then S _b contains or may contain all the characters of S _a . 2. The method according to claim 1, characterized in that: for W _a , with W _b , The comparison is realized with bit operators: write W _T as the bit value with all bits being 1, then method I can use W _a → W _b = W _T , W _a | W _b = W _b , W _a & W _b = W _a to fulfill. 3. The method according to claim 1, characterized in that: for W _a , with W _b , Comparing, if not meeting the judging criteria, then S _b does not contain all character elements of S _a ; if meeting the judging criteria, when each group of character elements is marked with a single bit and there is only one character element in each group of character elements , then S _b contains all the characters of S _a , and it is not sure whether S _b contains S _a ; if it meets the judgment standard, when each group of characters is marked with a single bit and there are multiple characters in each group of characters , or when multiple bits are used to mark each group of character elements, then S _b may contain all the character elements of S _a , and it is not sure whether S _b contains S _a ; according to needs, use the character-by-character comparison method to judge Does S _b contain S _a . 4. according to the described method of claim 1, it is characterized in that: character element comprises Chinese character radical, stroke; Letter, initial consonant, simple or compound vowel of Chinese phonetic alphabet, syllable; Letter, syllable, word of other languages; The phonetic symbol of other language; Or they combination. 5. according to the described method of claim 1, it is characterized in that: character string S comprises one or more character strings, when comprising a character string, its bit value W and Mark the character meta-information of a string, when multiple strings are included, its bit value W and Tokenize all character meta information for multiple strings. 6. according to the described method of claim 1, it is characterized in that: search key word S _t has 1 flag value W _t and 0 flag value And the string S _n has 1 flag value W _n and 0 flag value By W _t , with W _n , Comparing: It is possible to screen out all the S _n characters that contain or may contain the search keyword S _t . If necessary, use the character-by-character comparison method to determine whether S _n contains S _t or not, and also filter out the search keyword S _t S _n that contains or may contain all its character elements, if necessary, can use the character-by-bit comparison method to judge whether S _t contains S _n .