CN100354863C - Method and system for large scale keyboard matching - Google Patents

Abstract

The present invention provides methods and systems for large-scale keyword matching. According to the provided method and system, firstly, the given keyword set is normalized, and an optimal grouping and intra-group best matching method is solved on the normalized keyword set (or directly on the original keyword set). The process can use two mechanisms: one is to use the dynamic programming method to calculate an optimal grouping, and divide the given keyword set into several groups according to this result; then, for each group, obtain a The best matching method; one is to establish a directed graph with weights on the edges through training, and solve the shortest path of this graph to obtain the optimal grouping and best matching method within the group; then use the training results for all groups The scanning automaton is constructed sequentially to form a scanning automaton sequence, so that the input texts to be scanned pass through sequentially, and the final scanning result is obtained.

Description

Method and system for large-scale keyword matching

technical field

The invention relates to the technical field of text processing, in particular to a large-scale keyword matching method and system.

Background technique

The technology of multi-keyword matching is relatively mature, and it is widely used in various aspects of text processing and content filtering. The traditional multi-keyword matching algorithm regards the text to be scanned as a one-dimensional string, makes full use of the characteristics of the known keyword string, and jumps forward as much as possible during the scanning process to improve the matching performance. Multi-keyword matching algorithms can be divided into three forms according to different preprocessing methods for keywords: prefix mode (KMP, AC, Shift-AND, Shift-Or and other algorithms), suffix mode (Boyer-Moore, Wu-Manber and other algorithms), substring mode (BDM, BOM, SBDM, SBOM and other algorithms). The performance of the multi-keyword matching algorithm is mainly affected by the following three aspects: the number of keywords, the minimum length of keywords, and the character set. In addition, the matching speed is also related to the number of keywords appearing in the text to be scanned.

In order to continuously improve the performance of keyword matching, many new methods have emerged, but they are all improved on the preprocessing of the keyword itself, that is, to use the characteristics of the keyword string as much as possible to find a new data structure To store the features and the jump amount calculated by the features, improve the jump method, etc., such an improvement method has a limited improvement in the matching speed, which can usually be increased by about 20%-40%.

With the popularization of computer applications and network applications, the amount of data processing is increasing day by day. Especially in the network application environment, there is a large amount of real-time data processing requirements, such as: real-time filtering of spam, network content security and so on. In these applications, due to the continuous increase of user usage habits and data processing volume, the number of keywords will also continue to increase, and the scale often reaches tens of thousands. At this time, the speed of the traditional matching technology will obviously drop sharply, and it can no longer meet the application requirements, especially the real-time data processing requirements.

Contents of the invention

In order to meet the needs of large-scale fast keyword matching, the present invention provides a method for large-scale keyword matching, comprising the steps of: counting and sorting the keywords according to their length, and standardizing the keyword set; Dynamic programming method or shortest path method, carry out optimal grouping to keyword set and find best matching method; For each group of keywords in turn, use described best matching method to construct a scanning automaton, form the scanning automaton Sequence: use the formed scanning automaton sequence to scan and match the input text, and store the result in the specified memory structure or external file.

In order to achieve the above object, the present invention also provides a large-scale keyword matching system (Fig. 1), comprising: a device for normalizing a given keyword; a device for finding optimal grouping and best matching method, Two mechanisms are provided: one is the dynamic programming mechanism (Figure 2, 3), and the other is the shortest path mechanism (Figure 4, 5). This device stores the results in the form of configuration files; it is used to read the best results, And create a device for scanning automata for each group; a device for final scanning and storing the results in a specified memory structure or file.

More particularly, the invention relates to content-based text filtering and web content security.

In the large-scale keyword matching method, the core is how to solve an optimal grouping, the shortest path method is one of the methods, and the other is the dynamic programming method.

The invention solves the problem of fast matching of keywords in a large scale (usually more than 5000 keywords) in filtering, and is especially suitable for processing real-time network data. Experiments have proved that the speed of keyword matching can be doubled on average by using the system provided by the present invention.

Description of drawings

FIG. 1 is a schematic diagram of the large-scale keyword matching system of the present invention.

Fig. 2 is a schematic diagram of solving optimal grouping by the dynamic programming mechanism of the present invention.

Fig. 3 is a flow chart of the realization of the method for solving the optimal grouping by the dynamic programming mechanism of the present invention.

Fig. 4 is a schematic diagram of solving the optimal grouping by the shortest path mechanism of the present invention.

Fig. 5 is a flow chart of the implementation of the method for solving the optimal grouping based on the shortest path mechanism of the present invention.

Detailed ways

As shown in Figure 1, the system of the present invention includes:

Device (1): a device for standardizing keywords, which is used to count a large number of given keywords according to their length, and then sort them according to their length;

Device (2): The device for solving the optimal grouping and the best matching method. Its function is: two mechanisms can be used to solve the optimal grouping: one is to use the dynamic programming mechanism to obtain the optimal grouping, and then obtain the optimal grouping of each group through training. The best matching method; the other is to use the shortest path mechanism to directly obtain the grouping and the best matching method of each group; this device finally stores the results of the grouping and the best matching method in the file in the form of a configuration file;

Device (3): a device for setting up a scanning automaton, the effect is: read the configuration file, adopt the result after training, and set up a scanning automaton for each grouped keyword in turn;

The device (4) scanning device has the function of: using a group of scanning automata established in the device (3) to scan and match the input text, and store the result in a specified memory structure or an external file.

The detailed operation of each device will be described in detail respectively below.

1. Normalization device

The normalization device is to sort a given set of keywords according to length first, which can be from small to large or from large to small, and then count the number of keywords with the same length.

A set of keywords K={K ₁ , K ₂ , K ₃ , . . . , K _n } is defined, and the corresponding length L={l ₁ , l ₂ , l ₃ , . . . , l _n }. The normalization process first sorts K into: K'={K ₁ ', K ₂ ', K ₃ ', ..., K _n '}, so that the corresponding length L'={l ₁ ', l ₂ ', l ₃ ', ..., l _n '} satisfy: l ₁ '<=l ₂ '<=l ₃ '<=...<=l _n 'or l ₁ '>=l ₂ '>=l ₃ ' ＞＝...＞＝ l _n '. Then L' is counted, the number of the same length is calculated, and the statistical value sequence LNn: ₁ , n ₂ , n ₃ ,..., n _m is obtained. Among them, m is the maximum length of the keyword; n _i , 1<=i<=m represents the number of keywords whose length is i.

2. A device for solving optimal grouping and optimal matching methods

The purpose of this device is to solve an optimal grouping for the normalized keyword set, and use the most suitable matching method on each grouping, so as to make the matching speed of the whole set reach the fastest. In order to achieve this goal, the device can be realized through two mechanisms: one is the dynamic programming mechanism; the other is the shortest path mechanism. Described below respectively.

2.1 Dynamic programming mechanism

The dynamic programming mechanism is divided into four steps: defining the evaluation function step, grouping step, training step and storing configuration information step. In the step of defining the evaluation function, a function is given, which is related to the number and length of keywords, and is used in the grouping step; in the grouping step, the dynamic programming method is used to utilize the statistical information calculated in the normalization module, Solve an optimal grouping scheme for a given keyword set; in the training step, find the most suitable matching method for the keywords in each group; in the step of storing configuration information, combine the grouping position information and the most The best matching method information is recorded in a disk file for the final scanning robot to read and use.

(1), define the evaluation function steps (step1 in Figure 3)

According to the analysis of the traditional keyword matching algorithm, we believe that the keyword matching time is proportional to the number of keywords and inversely proportional to the minimum length of keywords under the condition of a certain character set, that is, the larger the number of keywords, The longer the matching time; the greater the minimum length of the keyword, the shorter the matching time. Furthermore, if F(K) is used to indicate the time when the text passes through the keyword set K, G(|K|) is used to indicate the influence relationship with the number of keyword set K, and L _min (K) is used to indicate the minimum The influence relationship of length, we can express their relationship as:

$f\left(K\right)=G\left(\right|K\left|\right)\&times;L_{\min }\left(K\right)=\frac{\sqrt{\left|K\right|}}{\min \left(K\right)}$ (Formula 1)

That is: the matching time is proportional to the root of the number of keywords, and inversely proportional to the minimum length (min(K)).

(2), grouping step (step2 among Fig. 3)

The grouping method steps are as follows:

Below we describe how to use dynamic programming to solve an optimal grouping.

The basic idea of dynamic programming is to decompose the problem to be solved into several sub-problems, first solve the sub-problems, and then obtain the solution of the original problem from the solutions of these sub-problems. It can usually be done in the following steps:

a. Find out the nature of the optimal solution and characterize its result characteristics;

b. Recursively define the optimal value;

c. Calculate the optimal value in a bottom-up manner;

d. According to the information obtained when calculating the optimal value, construct an optimal solution.

Our problem is: find a grouping of the set K that minimizes the value of F(K). See the expression of formula 1 for the nature of the optimal solution. In order to find the optimal solution, in essence, we are looking for a group that minimizes F(K).

Note that the grouping of an ordered set K is F[1:n], if the position of the first grouping separates the set at k, then there is F[1:n]=F[1:k]+F[k +1:n], and so on for F[k+1:n]. The recursive formula for grouping solution is:

$\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; :</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; min</span>}\left\{\begin{array}{c}\frac{\mathrm{<span\; class="notranslate">\; G</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; K</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; :</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; k</span>}\\ \frac{\mathrm{<span\; class="notranslate">\; G</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>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; K</span>}}\end{array}\right.<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; no</span>}$

Calculation process: start calculation from F[n:n], F[n-1:n], F[n-2:n], ..., until F[1:n]. In the calculation, the table is used to store the intermediate calculation result F[k:n], which is beneficial to the search of the subsequent calculation, which is also the core idea of the dynamic programming algorithm. At the same time, use the array position to store the position information at the value of F[k:n].

Backtracking process: When the value of F[1:n] is obtained, the calculation process ends, and then backtracking starts from the value of position to get the final solution. First take the value of position[1], which represents the grouping position for F[1:n], and then take position[position[1]], which represents the next position until position[n], so the obtained position sequence It is an optimal grouping position.

Use the dynamic programming method to group the sequence of length n, its time complexity is O(n ² ), and its space complexity is O(n).

(3), training steps (step3 in Figure 3)

After the grouping is completed, which suitable matching method to use for the keywords of each group is obtained by means of training in the present invention. In the previous technical background, we have explained the mature keyword matching technology, and we can choose several of them for training. In the system of the present invention, we have selected three methods of BOM, Wu-Manber and AC. The training text uses random data files generated according to different charset sizes.

For each group after grouping: use each of the matching methods A ₁ , A ₂ , .., A _p for training in turn, scan and match the training text, and record the time Ti required for the completion of the scan, 1<=i <=p. Finally calculate the minimum value T _j among {T ₁ , T ₂ , .., T _p }, then group this and use the jth matching method. Train all groups in turn, and record the best matching method for each group.

(4), the step of storing configuration information (step4 in Figure 3)

After the training is completed, the grouping results and training results are written into the configuration file of the system according to the specified format, so that the subsequent scanning automaton device can be read and used. In the system of the present invention, the configuration file is written in the form of an integer sequence, the first line represents the grouping result, and the second line represents the training result of the matching method. Integers are separated by the tab key.

For example:

3 14 40

1 3 2

The first line indicates that they are finally divided into 3 groups, the length <= 3 is a group, the length is 4-14 is a group, and the length is 15-40 is a group;

The second line indicates that the first group of keyword matches uses method 1, the second group uses method 3, and the third group uses method 2. The specific methods 1, 2, and 3 represent which methods are determined by the system itself.

See Figure 2 for a schematic diagram of using the dynamic programming mechanism. In the figure, the example of the above step 1 is not given. At the top is a group of keywords represented by length, and a dotted line is used to indicate the grouping of them using dynamic programming, which corresponds to the above grouping steps; below, for each keyword in the grouping, a training text is used , among the three candidate scan-matching automata, train to get the best automaton, which corresponds to the above-mentioned training steps; finally, store the grouping information and the best scanning automaton information used by each group in the external In the storage device, this corresponds to the above-mentioned step of storing configuration information. The corresponding implementation process is shown in Figure 3.

2.2 Shortest path mechanism

The shortest path mechanism is derived from the shortest path technique for solving a graph. For the problem of large-scale keyword matching, we make the following definitions:

Definition 1: In the normalized keyword set, keywords of the same length form a group, which is regarded as a point in the graph, and is recorded as: N _i , where i represents the length of the keyword at this point.

Definition 2: Directed edge representation from point Ni to Nj: All keywords with length i to j-1 are grouped together, denoted as: Bij.

Definition 3: The weight on Bij means: the time for a scanning automaton composed of keywords with length [i, j] to scan the training text once, denoted as: T _ij .

Definition 4: For a given set of keywords and a training text, if the minimum length of keywords is p and the maximum length is q, p<=q, then a directed graph corresponding to it is a set of points {N _p , N _p+1 ,..., N _q , N _q+1 } and the directed edge set {B _ij }, p<=i<=q, p<j<=q+1, composed of a directed picture.

According to the above definition, we have established a directed graph for a given keyword set, and then we can calculate the weight of each edge according to the given training text, and finally find the shortest path of the graph, that is, the optimal grouping. Solving a shortest path mechanism on a directed graph is divided into the following steps:

(1), the keyword set of normalization is expressed as the directed graph defined above; (step1 among Fig. 5)

(2) Calculate the weight of each edge. In the calculation process, use the set multiple matching methods to calculate each side, and finally take the minimum value (the shortest scanning time) as the weight of this side, and record the matching method used by this side; (step2 in Figure 5 )

(3), find the shortest path of the directed graph, obtain optimal grouping, and can obtain the best matching method corresponding to each group simultaneously; (step3 among Fig. 5)

(4) Store the final result in the configuration file of the system. The configuration file format is the same as

As described in the step of storing configuration information in 4.2.1. (step4 in Figure 5)

Figure 4 is a schematic diagram of solving the optimal grouping for a given keyword set. Assuming that the keyword length in the figure is 2-7, according to definition 1, the directed graph has 7 nodes labeled 2-8, according to definition 2, each node has a directed edge with a label greater than itself, according to definition 3, it can be Calculate the weight on each edge (not specifically marked in the figure), and then solve the shortest path for this graph. If the shortest path is 2-6-8, the grouping situation is: the length of 2-5 is a group, and the length of 6-7 is a group.

Using the shortest path mechanism, assuming that the number of key words is n, that is, the number of nodes in the directed graph is n, then the time complexity of simply calculating the shortest path of the directed graph is O(n ² ). If considering the training process with multiple matching methods in the process of calculating the weight of edges, assuming that there are m kinds of matching methods selected, the time complexity of the shortest path mechanism is O(n ² *m). This is acceptable as an initialization phase of the system.

3. Establish a scanning robot device

A device for reading configuration information and establishing a scanning automaton: According to the configuration information of the system, read the position of the group (length-separated position), and then form a group of keywords of the corresponding length, and according to the most The optimal scan-matching automaton is used to construct the automaton, and finally, an automaton sequence composed of multiple automata is constructed for the original keyword set.

To establish the configuration of the scanning automaton device reading system, first, group the original keyword set according to the grouping situation, and use the same data structure for each group to store the keywords in the group, the length of the keyword, the key Information such as the original index number of the word; and then according to the training situation, respectively establish scanning automata with different matching methods. The system stores the entry address of each scanning robot for direct use by subsequent scanning devices.

How to set up the scanning automaton does not belong to the scope of the present invention, and will not be described in detail here.

4. Scanning device

The scanning device reads text data input from the outside world, which may be files stored on the local disk, or various data transmitted over the network. The text data passes through each scanning automaton of the system in turn. When a keyword that matches successfully appears, the system will record their index number, occurrence location and other information, which can be counted in the corresponding machine structure of the memory for other external The application system can also store them directly in disk files.

5. Positive effect

With the above processing, we can increase the speed of large-scale keyword matching. Using the dynamic programming method to group keywords can ensure that this grouping is theoretically optimal under the matching speed evaluation function set by the system; for each group, because the number of keywords in the group is different, the minimum length is also are not the same, so the system uses the training method to find the best matching method. Using the shortest path mechanism, combining the search for optimal grouping and the best matching method, can ensure the fastest actual grouping speed in actual system operation. The time complexity of calculating the optimal grouping and finding the best matching process is slightly lower, but because they are all done in the initialization part of the system, it does not affect the final scan matching speed.

By using two different grouping mechanisms, we can guarantee to get a group with the fastest scanning speed under a given set of keywords and a given training text. By building a sequence of scanning automatons, we solve the problem of severe slowdown of large-scale keyword matching. The test proves: under the same conditions, using the method and system of the present invention, compared with traditional mature multi-keyword matching methods (AC, Wu-Manber, SBOM), the matching speed is 2 times that of the fastest single matching method, 4 times slower than the slowest single matching method.

Claims (6)

1. A method for large scale keyword matching, the method comprising the steps of:

counting and sequencing the number of the keywords according to the length, and standardizing a keyword set;

optimally grouping the keyword set and searching for an optimal matching method by using a dynamic programming method or a shortest path method;

sequentially constructing a scanning automaton for each group of keywords by using the optimal matching method to form a sequence of the scanning automaton;

and scanning and matching the input text by using the formed scanning automaton sequence, and storing the result in a specified memory structure or an external file.

2. The method for large scale keyword matching according to claim 1, wherein the dynamic programming method for optimally grouping the keyword sets and finding the best matching method comprises: defining an evaluation function, grouping, training and storing configuration information; wherein,

the step of defining the evaluation function specifically comprises: according to the analysis of the traditional keyword matching algorithm, the keyword matching time is in direct proportion to the number of keywords and in inverse proportion to the minimum length of the keywords under the condition that a character set is certain, if F (K) is used for representing the time of a text passing through a keyword set K, G (| K |) is used for representing the influence relation with the number of the keyword set K, and L is used for representing the influence relation with the number of the keyword set K_min(K) Representing the influence relationship with the minimum length of the keywords, their relationship is expressed as:

$F\left(K\right)=G\left(\right|K\left|\right)\&times;L_{\min }\left(K\right)=\frac{\sqrt{\left|K\right|}}{\min \left(K\right)}$ equation 1

Namely: the matching time is in direct proportion to the root of the number of the keywords and in inverse proportion to the minimum length min (K);

the grouping step specifically includes the steps of: solving an optimal grouping by using a dynamic programming method, solving sub-problems, and then obtaining a solution of an original problem from the solutions of the sub-problems, which can be generally performed according to the following steps: a. finding out the property of the optimal solution and depicting the result characteristics; b. a recursive defined optimum; c. calculating an optimal value in a bottom-up manner; d. constructing an optimal solution according to information obtained when the optimal value is calculated; finding a grouping of K sets that minimizes the value of F (K), finding a grouping that minimizes F (K) for an optimal solution, noting F [1: n ] for an ordered set K, if the position of the first grouping separates the sets at K, then F [1: n ] ═ F [1: K ] + F [ K +1: n ], and so on for F [ K +1: n ], the recursion for the grouping solution is:

$F[k:n]=\min \begin{array}{c}\left\{\begin{array}{c}\frac{G\left(p\right)}{K}+F[k+p:n],1\&le;p\&le;n-k\\ \frac{G(n-k+1)}{K}\end{array}\right.,1\&le;\end{array}k\&le;n$

and (3) calculating: starting calculation from Fn to n, Fn-1 to n, Fn-2 to n, until F1 to n, in the calculation, using table to store intermediate calculation result Fk to n, beneficial to searching later calculation, at the same time using array position to store position information of F k to n value;

a backtracking process: when the value of F [1: n ] is up, the calculation process is finished, and then backtracking is carried out from the value of position to obtain a final solution;

the training step specifically comprises: after grouping is completed, a matching method for the use of each grouped keyword is obtained by adopting a training method, three methods of BOM, Wu-Manber and AC are selected, a random data file generated according to different character set sizes is used for training a text, and for each grouped keyword: selecting and matching method A by using training in sequence₁，A₂，...，A_pIn each of the above methods, scanning and matching the training text, recording the time Ti required for scanning, 1 & lti & gt & lti & ltp & gt, and finally calculating { T [ ]₁，T₂，..，T_pMinimum value T in_jThen, for the group, using the jth matching method, training all the groups in turn, and recording the optimal matching method of each group;

the step of storing configuration information specifically comprises: after training, writing the grouping result and the training result into a configuration file of a system according to a specified format so as to facilitate the subsequent establishment of a scanning automatic machine for reading and use; and writing the configuration file in an integer sequence mode, wherein the first row represents a grouping result, the second row represents a training result of the matching method, and the integers are separated by tab keys.

3. A system for large scale keyword matching, comprising:

the normalized keyword device is used for counting the number of given keywords according to the length and then sorting the keywords according to the length;

apparatus for solving optimal grouping and optimal matching methods for solving optimal grouping using two mechanisms: firstly, obtaining an optimal grouping by adopting a dynamic programming mechanism, and then obtaining an optimal matching method of each group by a training method; the other method is to directly obtain the best matching method of the grouping and each group by using a shortest path mechanism; the device finally stores the grouping and the result of the best matching method in a file in the form of a configuration file;

a device for establishing the scanning automata, which is used for reading the configuration file and establishing the scanning automata for each grouped keyword in sequence by adopting the trained result;

and the scanning device is used for scanning and matching the input text by using a group of scanning automata established in the device for establishing the scanning automata and storing the result in a specified memory structure or an external file.

4. The large-scale keyword matching system of claim 3, wherein the normalized keyword means is configured to sort a given set of keywords by length, and count the number of keywords with the same length, and define a set of keywords K ═ { K ═ K [, where the keywords are sorted from small to large or from large to small, and then count the number of keywords with the same length₁，K₂，K₃，...，K_nL, corresponding length L ═ L₁，l₂，l₃，...，l_nThe normalization process first orders K into: k ═ K₁’，K₂’，K₃’，...，K_n', such that the corresponding length L' ═ L₁’，l₂’，l₃’，...，l_n' } satisfies: l₁’＜＝l₂’＜＝l₃’＜＝...＜＝l_n' or l₁’＞＝l₂’＞＝l₃’＞＝...＞＝l_n'then counting L', and calculating the number of the same length to obtain a statistical value sequence LN: n is₁，n₂，n₃，...，n_mWherein m is the maximum length of the keyword; n is_iAnd l < i < m represents the number of keywords having a length i.

5. The large-scale keyword matching system of claim 3, wherein the means for establishing a scanning automaton: reading the grouped positions according to the configuration information of the system, then combining the keywords with corresponding lengths into a group, and constructing an automatic machine according to the optimal scanning matching automatic machine in the group recorded in the configuration information, and finally constructing an automatic machine sequence consisting of a plurality of automatic machines for the original keyword set.

6. The large-scale keyword matching system according to claim 3, wherein the scanning device reads externally inputted text data, the data is files stored on a local disk or various data transmitted on a network, the text data sequentially passes through the scanning automata of the system, when the successfully matched keywords appear, the system records the index numbers and the appearance position information of the keywords, and then counts the information in the corresponding machine structure of the memory for use by an external application system or directly stores the information in the disk file.

Images