WO2017161749A1 - Method and device for information matching - Google Patents

Abstract

A method and a device for information matching, the method comprising: acquiring inputted information to be retrieved (S301); searching in a preset database, according to a preset rule, for data matching the information to be retrieved (S302); outputting the searched data which matches the information to be retrieved (S303); the data in the preset database being stored in a Trie tree, the Trie tree comprising fuzzy nodes in addition to ordinary nodes, the fuzzy node being used for crossing over respective sister ordinary nodes in the same level to directly reach sub nodes of the respective sister ordinary nodes in the same level when a fuzzy search is needed. The method improves the structure of the Trie tree by adding fuzzy nodes on the basis of ordinary nodes of the Trie tree so as to make it a more suitable data structure for a fuzzy match, in practice reducing the search and comparison times, thereby improving the speed of the fuzzy search.

Description

Information matching method and device

The present application claims priority to Chinese Patent Application No. 2016101615591, the entire disclosure of which is hereby incorporated by reference. .

Technical field

The present invention relates to computer technology, and in particular, to an information matching method and apparatus.

Background technique

At present, many web pages or APPs provide search functions. Users may input incorrect query words or input fuzzy query words. In this case, fuzzy matching technology is needed to provide users with the most accurate search results. In the prior art, fuzzy matching of search terms can be achieved by using a depth-first search algorithm on the structure of the Trie tree.

The Trie tree, also known as the prefix tree or dictionary tree, is a common method for matching lookups. It can be used to sort and save a large number of strings and so on, so it is often used by search engine systems for text word frequency statistics. Its advantage is: use the common prefix of the string to reduce the query time, minimize the unnecessary string comparison, the query efficiency is higher than the hash tree. Depth-first search is a commonly used enumeration search method. The rules are simple. Starting from the root node, each possible branch path can't go deeper, and each node can only access once.

In the process of implementing the present invention, the inventors have found that the existing retrieval method has too many times of searching and comparing, which results in a slow running speed, low efficiency, and poor user experience.

Summary of the invention

In order to overcome the problems in the prior art, the embodiments of the present invention provide an information matching method and apparatus, which improve efficiency in fuzzy retrieval.

According to a first aspect of the embodiments of the present invention, an information matching method is provided, the method comprising:

Obtain the input information to be retrieved;

Searching, in the preset database, data matching the information to be retrieved according to a preset rule;

Outputting the found data matching the information to be retrieved;

The data in the preset database is stored in a Trie tree manner, and the Trie The tree includes a fuzzy node in addition to the ordinary node, and the fuzzy node is used to directly reach the child nodes of the common nodes in the same level when crossing the common nodes in the same level when the fuzzy search needs to be performed;

The preset rules include:

The data matching the information to be retrieved is searched in the preset database according to the depth-first algorithm. When the next node needs to be selected, if the fuzzy search is performed at this time, only the fuzzy node in the next node is selected.

Optional:

The fuzzy node is divided into a first-level fuzzy node and a second-level fuzzy node, and each common node of the Trie tree has a first-order fuzzy node, and each first-order fuzzy node has a second-order fuzzy node. All common nodes in the child nodes of the parent node of the first-level fuzzy node are linked to the current level one fuzzy node, and all the ordinary nodes in the child child nodes of the grandparent node of the second-level fuzzy node are linked to the current two Under the fuzzy node, the first-level fuzzy node as the leaf node stores the data stored in all the common nodes of the same parent, and the secondary fuzzy node as the leaf node stores the data stored in all the common nodes of the same grandfather. .

Optionally, before obtaining the input information to be retrieved, the method further includes:

Obtaining data for generating the preset database;

And storing the data used to generate the preset database according to a Trie tree manner;

Add a first-level fuzzy node under the common node of each Trie tree, add a second-level fuzzy node under each first-level fuzzy node, and link all common nodes in the child nodes of the parent node of the first-level fuzzy node. Under the current level one fuzzy node, all the common nodes in the child sub-nodes of the grandfather node of the second-level fuzzy node are linked to the current second-level fuzzy node, and the first-level fuzzy node as the leaf node is stored with the same parent. The data stored by all the brothers' ordinary nodes, as the secondary fuzzy nodes of the leaf nodes, store the data stored by all the brothers' ordinary nodes of the grandfather to generate the preset database.

Optionally, determine whether it is a fuzzy search by:

If the information to be retrieved includes a fuzzy wildcard, when the search proceeds to the position of the fuzzy wildcard, it is determined that the fuzzy search is performed at this time.

Optionally, the data that is found by the output and matched with the information to be retrieved includes:

Outputs the data stored in the leaf nodes found.

According to a second aspect of the embodiments of the present invention, there is provided an information matching apparatus, the apparatus comprising:

An obtaining unit, configured to obtain input information to be retrieved;

a matching unit, configured to search for the information to be retrieved according to a preset rule in a preset database Matching data;

An output unit, configured to output the found data that matches the information to be retrieved;

The data in the preset database is stored in a Trie tree manner, and the Trie tree includes a fuzzy node in addition to the common node, and the fuzzy node is used to cross each of the same levels when the fuzzy search needs to be performed. The brothers are ordinary nodes and directly reach the child nodes of the common nodes of the brothers in the same level;

The preset rules include:

The data matching the information to be retrieved is searched in the preset database according to the depth-first algorithm. When the next node needs to be selected, if the fuzzy search is performed at this time, only the fuzzy node in the next node is selected.

Optional:

The fuzzy node is divided into a first-level fuzzy node and a second-level fuzzy node, and each common node of the Trie tree has a first-order fuzzy node, and each first-order fuzzy node has a second-order fuzzy node. All common nodes in the child nodes of the parent node of the first-level fuzzy node are linked to the current level one fuzzy node, and all the ordinary nodes in the child child nodes of the grandparent node of the second-level fuzzy node are linked to the current two Under the fuzzy node, the first-level fuzzy node as the leaf node stores the data stored in all the common nodes of the same parent, and the secondary fuzzy node as the leaf node stores the data stored in all the common nodes of the same grandfather. .

Optionally, the device further includes:

A default database generation unit for:

Obtaining data for generating the preset database; storing the data for generating the preset database according to a Trie tree manner; adding a first-level fuzzy node under each common node of the Trie tree, at each Adding a second-level fuzzy node under the first-level fuzzy node, linking all the common nodes in the child nodes of the parent node of the first-level fuzzy node to the current first-level fuzzy node, and sub-nodes of the grandparent node of the second-level fuzzy node All the common nodes in the child nodes are linked to the current secondary fuzzy nodes, and the first-level fuzzy nodes that are leaf nodes store the data stored by all the brothers of the same parent, and store them as the secondary fuzzy nodes of the leaf nodes. There is data stored by all the brothers' common nodes of the grandfather to generate the preset database.

Optionally, the matching unit determines whether the fuzzy search is performed by:

If the information to be retrieved includes a fuzzy wildcard, when the search proceeds to the position of the fuzzy wildcard, it is determined that the fuzzy search is performed at this time.

Optionally, the output unit is configured to:

Outputs the data stored in the leaf nodes found.

According to a third aspect of the present invention, a computer storage medium is further provided, wherein the computer storage medium can store a program, and when the program is executed, the information matching method provided by the first aspect of the embodiment of the present invention can be implemented. Some or all of the steps in each implementation.

The technical solutions provided by the embodiments of the present invention may include the following beneficial effects:

In the embodiment of the present invention, the structure of the Trie tree is improved, and the fuzzy node is added to the common node of the Trie tree to make it become a data structure more suitable for fuzzy matching, and the number of times of searching and comparing can be greatly reduced when used. This improves the speed of fuzzy lookups.

The above general description and the following detailed description are intended to be illustrative and not restrictive.

DRAWINGS

The accompanying drawings, which are incorporated in the specification of FIG

1 is a schematic diagram of a Trie tree in the prior art;

2 is a schematic diagram of a search sequence in a prior art search in a Trie tree;

FIG. 3 is a flowchart of an information matching method according to an exemplary embodiment of the present invention; FIG.

4 is a schematic diagram of a Trie tree with a fuzzy node, according to an exemplary embodiment of the present invention;

FIG. 5 is a schematic diagram showing a fuzzy node link according to an exemplary embodiment of the present invention; FIG.

6 is a schematic diagram of performing fuzzy search in the prior art;

FIG. 7 is a schematic diagram showing performing fuzzy search according to an exemplary embodiment of the present invention; FIG.

FIG. 8 is a flowchart of an information matching method according to an exemplary embodiment of the present invention; FIG.

FIG. 9 is a schematic diagram of an information matching apparatus according to an exemplary embodiment of the present invention; FIG.

FIG. 10 is a schematic diagram of an information matching apparatus according to an exemplary embodiment of the present invention.

detailed description

Exemplary embodiments will be described in detail herein, examples of which are illustrated in the accompanying drawings. The following description refers to the same or similar elements in the different figures unless otherwise indicated. The embodiments described in the following exemplary embodiments do not represent all embodiments consistent with the present invention. Instead, they are merely examples of devices and methods consistent with aspects of the invention as detailed in the appended claims.

First, a brief introduction to the Trie tree. Suppose the data stored in the Trie tree is "the brave The words "Adventure", "The Brave", "The Legend of the Brave", "The Legend of the Sanctuary", and "Myths and Legends" are shown in Figure 1. It is assumed that the keyword to be queried by the user at a certain moment is "The Legend of the Brave" ", the retrieval system will divide the "Brave Legend" into four single characters 'yong', '者', 'pass', 'say', and then start from the root node, retrieve the word 'yong', enter the node, from ' Starting from the byte point, search for the word 'holder', enter the node, and continue until you find all the words, hit the "Brave Legend", the search ends. The process can be seen in Figure 2, in Figure 2, next to the node The numbers represent the order in which the nodes are searched, the same below.

FIG. 3 is a flowchart of an information matching method according to an exemplary embodiment. The method can be used for terminal devices such as mobile phones, tablet computers, desktop computers, and the like, and can also be used for servers and the like.

Referring to FIG. 3, the method may include:

Step S301: Acquire the input information to be retrieved.

For example, when the user needs to retrieve a certain information, enter the information to be retrieved in the search box of the mobile phone, and then click the search button.

Step S302: Search for data matching the to-be-retrieved information according to a preset rule in a preset database.

The data in the preset database is stored in a Trie tree manner, and the Trie tree includes a fuzzy node in addition to the common node, and the fuzzy node is used to cross each of the same levels when the fuzzy search needs to be performed. The brothers are ordinary nodes and directly reach the child nodes of the common nodes of the brothers in the same level;

The preset rules include:

The data matching the information to be retrieved is searched in the preset database according to the depth-first algorithm. When the next node needs to be selected, if the fuzzy search is performed at this time, only the fuzzy node in the next node is selected.

The common nodes of the siblings of the same level may be children of the same parent, or children of the same grandfather.

Specifically, in this embodiment or some other embodiments of the invention:

The fuzzy node is divided into a first-level fuzzy node and a second-level fuzzy node, and each common node of the Trie tree has a first-order fuzzy node, and each first-order fuzzy node has a second-order fuzzy node. All common nodes in the child nodes of the parent node of the first-level fuzzy node are linked to the current level one fuzzy node, and all the ordinary nodes in the child child nodes of the grandparent node of the second-level fuzzy node are linked to the current Under the two-level fuzzy node, the first-level fuzzy node as the leaf node stores the data stored in all the common nodes of the same parent, and the secondary fuzzy node as the leaf node stores the information stored in all the common nodes of the same grandfather. data.

For example, as shown in FIG. 4 to FIG. 5, in FIG. 4, the F1 node is a first-order fuzzy node, and the F2 node is a second-order fuzzy node. In FIG. 5, all the ordinary nodes in the child nodes of the parent node of the F1 node are linked to the current F1 node and become the child nodes of F1, and all the ordinary nodes in the child child nodes of the grandparent node of the F2 node are linked. Go to the current F2 node and become a child of F2.

It should be noted in FIG. 4 and FIG. 5 that, in theory, a first-order fuzzy node should be added under each common node. However, in practice, after the first-order fuzzy node is added, the fuzzy node has no meaning, so in FIG. 4 And some common nodes in Figure 5 do not draw fuzzy nodes. Taking the 'punch' byte as an example, there is no child node under this node, so even if an F1 node is added to the node, there is no ordinary node that can be linked under the F1 node, so the F1 node has no meaning. Therefore, the first-order fuzzy nodes are not drawn under the 'punch' byte points in Figures 4 and 5. Similarly, some secondary fuzzy nodes are not drawn under the first-level fuzzy nodes.

Step S303, outputting the found data that matches the information to be retrieved.

As an example, the data that is found to match the information to be retrieved by the output may include:

Outputs the data stored in the leaf nodes found.

The data stored in the Trie tree is described below in conjunction with an example. The storage in the Trie tree can be a string, such as a phrase composed of natural language. Data is usually stored primarily at leaf nodes. For example, for the phrase "Brave Legend", there are four common nodes, each of which is used to index 'yong' 'pass' 'pass' 'say', and the actual data is the term "Brave Legend". Stored in the leaf node is the 'say' byte point. In addition, because the word "brave" can also be used as a single term, the ‘user’ byte can also store the word “勇勇”.

In addition, the data stored in the 'speak' byte point can include other related content, such as address, picture, profile, link, etc., in addition to the term "Brave Legend", so that the user retrieves the "Brave Legend". "You can further see other related content related to the search results."

In the present invention or some other embodiments of the present invention, it may be determined whether it is a fuzzy search by:

If the information to be retrieved includes a fuzzy wildcard, when the search proceeds to the position of the fuzzy wildcard, it is determined that the fuzzy search is performed at this time.

For example, the fuzzy wildcard can be "*", "%", and the like.

The fuzzy retrieval process using the depth-first algorithm is further described below with reference to specific examples:

Suppose the content to be retrieved is "** Legend", where ‘*’ stands for any word. If the fuzzy search is performed on the ordinary Trie tree, as shown in Figure 6, the process can be as follows:

1) Divide the "** legend" into four words, namely ‘*’, ‘*’, ‘pass’, ‘say’.

2) Starting from the root node, traversing all its child nodes, first entering the node 'yong'.

3) Since the second word is also ‘*’, starting from the ‘yong’ node, traversing all of its nodes, first entering the node ‘者’.

4) Starting from the ‘user’ byte point, search for the word 'pass' and enter the node.

5) Starting from the ‘transmission’ byte point, search for the word “say”, enter the node, and find the eligible entry “Brave Legend”, and record it.

6) Return to step 3) and continue the traversal of the child nodes of the 'yong' node, repeating 3) to 5). There is only one child node below the 'yong' node, so the traversal ends.

7) Go back to step 2) and continue the traversal of the child nodes of the root node, repeating 2) to 6). There are three child nodes below the root node, which are traversed one by one.

8) Statistics of all the recorded results ("Brave Legend", "Sanctuary Legend", "Myths and Legends"), the search ends.

However, if the Trie tree in which the fuzzy node is added in the present invention is used, as shown in FIG. 7, the process can be as follows:

a) Divide the “** Legend” into four words, namely ‘*’, ‘*’, ‘pass’, ‘say’.

b) Starting from the root node, only enter its child node 'F1'.

c) Since the second word is also ‘*’, proceed from the ‘F1’ node to its child node 'F2’.

d) Starting from the 'F2' node, the word 'pass' is retrieved and multiple nodes are found, traversing these nodes.

e) Starting from the first ‘transmission’ byte, search for the word “say”, enter the node, and find the eligible entry “Brave Legend” and record it.

f) Repeat step e to complete the traversal.

g) Count all the matching results found ("Brave Legend", "Sanctuary Legend", "Myths and Legends"), and the search ends.

By comparing FIG. 6 and FIG. 7, the advantage of the retrieval speed of the present invention can be clearly seen, because the number of times of comparison needs to be greatly reduced, and when the fuzzy search is needed, the common nodes of the siblings in the same level are directly reached to reach the same level. The child nodes of the common nodes in each of the brothers.

In the real-time search, a large amount of data is stored on the server, and generally each node will have about 3,000 child nodes. The present invention avoids double traversal and optimizes speeds of approximately 3000 x 3000 times. This results in a significant increase in the speed of fuzzy matching, making the algorithm practically usable. When there is 800,000 data, the Trie tree fuzzy matching before optimization, the search takes about 5 to 6 minutes, and the optimized fuzzy matching algorithm can be ignored (less than 1 millisecond).

In addition, as shown in FIG. 8, before acquiring the input information to be retrieved, the method further includes:

Step S801, acquiring data for generating the preset database.

Step S802, storing the data used to generate the preset database according to a Trie tree manner.

Step S803, adding a first-level fuzzy node under the common node of each Trie tree, adding a second-level fuzzy node under each first-level fuzzy node, and all ordinary ones in the child nodes of the parent node of the first-level fuzzy node The nodes are all linked to the current first-level fuzzy node, and all the common nodes in the child sub-nodes of the grandfather node of the second-level fuzzy node are linked to the current second-level fuzzy node, and the first-level fuzzy node as the leaf node is stored. The data stored by all the siblings of the same parent, as the secondary fuzzy node of the leaf node, stores the data stored by all the common nodes of the grandfather to generate the preset database.

The embodiment of the invention improves the structure of the Trie tree, adds a fuzzy node to the common node of the Trie tree, and makes it become a data structure more suitable for fuzzy matching, which can greatly reduce the number of times of searching and comparing, thereby improving the number of times. Find speed.

The following is an embodiment of the apparatus of the present invention, which can be used to carry out the method embodiments of the present invention. For details not disclosed in the embodiment of the device of the present invention, please refer to the method embodiment of the present invention.

FIG. 9 is a schematic diagram of an information matching apparatus according to an exemplary embodiment. The device can be used for terminal devices such as mobile phones, tablet computers, desktop computers, and the like, and can also be used for servers and the like.

Referring to Figure 9, the apparatus can include:

The obtaining unit 901 is configured to obtain the input information to be retrieved.

For example, when the user needs to retrieve a certain information, enter the information to be retrieved in the search box of the mobile phone, and then click the search button.

The matching unit 902 is configured to search for data matching the to-be-retrieved information according to a preset rule in a preset database.

The data in the preset database is stored in a Trie tree manner, and the Trie tree includes a fuzzy node in addition to the common node, and the fuzzy node is used to cross each of the same levels when the fuzzy search needs to be performed. The brothers are ordinary nodes and directly reach the child nodes of the common nodes of the brothers in the same level;

The preset rules include:

The data matching the information to be retrieved is searched in the preset database according to the depth-first algorithm. When the next node needs to be selected, if the fuzzy search is performed at this time, only the fuzzy node in the next node is selected.

Specifically, in this embodiment or some other embodiments of the invention:

The fuzzy node is divided into a first-level fuzzy node and a second-level fuzzy node, and each common node of the Trie tree has a first-order fuzzy node, and each first-order fuzzy node has a second-order fuzzy node. Point, all common nodes in the child nodes of the parent node of the first-level fuzzy node are linked to the current level one fuzzy node, and all common nodes in the child child nodes of the grandparent node of the second-level fuzzy node are linked Under the current secondary fuzzy node, the first-level fuzzy node as the leaf node stores the data stored in all the common nodes of the same parent, and the secondary fuzzy node as the leaf node stores all the common nodes of the same grandfather. Stored data.

The output unit 903 is configured to output the found data that matches the information to be retrieved.

As an example, the output unit 903 can be specifically used to:

Outputs the data stored in the leaf nodes found.

In the present invention or some other embodiments of the present invention, the matching unit 902 can determine whether it is a fuzzy search by:

If the information to be retrieved includes a fuzzy wildcard, when the search proceeds to the position of the fuzzy wildcard, it is determined that the fuzzy search is performed at this time.

In addition, referring to FIG. 10, the apparatus may further include:

The preset database generating unit 904 is configured to:

Obtaining data for generating the preset database; storing the data for generating the preset database according to a Trie tree manner; adding a first-level fuzzy node under each common node of the Trie tree, at each Adding a second-level fuzzy node under the first-level fuzzy node, linking all the common nodes in the child nodes of the parent node of the first-level fuzzy node to the current first-level fuzzy node, and sub-nodes of the grandparent node of the second-level fuzzy node All the common nodes in the child nodes are linked to the current secondary fuzzy nodes, and the first-level fuzzy nodes that are leaf nodes store the data stored by all the brothers of the same parent, and store them as the secondary fuzzy nodes of the leaf nodes. There is data stored by all the brothers' common nodes of the grandfather to generate the preset database.

The embodiment of the invention improves the structure of the Trie tree, adds a fuzzy node to the common node of the Trie tree, and makes it become a data structure more suitable for fuzzy matching, which can greatly reduce the number of times of searching and comparing, thereby improving the number of times. Find speed.

With regard to the apparatus in the above embodiment, the specific manner in which each unit\module performs an operation has been described in detail in the embodiment relating to the method, and will not be explained in detail herein.

The embodiment of the present invention further provides a computer storage medium, wherein the computer storage medium can store a program, and when the program is executed, the implementation manners of an information matching method provided by the embodiments of FIG. 1 to FIG. 8 can be implemented. Part or all of the steps.

Those skilled in the art will readily appreciate the present invention after considering the specification and practicing the invention disclosed herein. Other embodiments of the invention. The present application is intended to cover any variations, uses, or adaptations of the present invention, which are in accordance with the general principles of the present invention and include common general knowledge or conventional technical means in the art that are not disclosed in the present invention. . The specification and examples are to be considered as illustrative only,

It is to be understood that the invention is not limited to the details of the details of The scope of the invention is limited only by the appended claims.

Claims (10)

An information matching method, characterized in that the method comprises: Obtain the input information to be retrieved; Searching, in the preset database, data matching the information to be retrieved according to a preset rule; Outputting the found data matching the information to be retrieved; The data in the preset database is stored in a Trie tree manner, and the Trie tree includes a fuzzy node in addition to the common node, and the fuzzy node is used to cross each of the same levels when the fuzzy search needs to be performed. The brothers are ordinary nodes and directly reach the child nodes of the common nodes of the brothers in the same level; The preset rules include: The data matching the information to be retrieved is searched in the preset database according to the depth-first algorithm. When the next node needs to be selected, if the fuzzy search is performed at this time, only the fuzzy node in the next node is selected. The method of claim 1 wherein: The fuzzy node is divided into a first-level fuzzy node and a second-level fuzzy node, and each common node of the Trie tree has a first-order fuzzy node, and each first-order fuzzy node has a second-order fuzzy node. All common nodes in the child nodes of the parent node of the first-level fuzzy node are linked to the current level one fuzzy node, and all the ordinary nodes in the child child nodes of the grandparent node of the second-level fuzzy node are linked to the current two Under the fuzzy node, the first-level fuzzy node as the leaf node stores the data stored in all the common nodes of the same parent, and the secondary fuzzy node as the leaf node stores the data stored in all the common nodes of the same grandfather. . The method of claim 2, wherein before the obtaining the information to be retrieved, the method further comprises: Obtaining data for generating the preset database; And storing the data used to generate the preset database according to a Trie tree manner; Add a first-level fuzzy node under the common node of each Trie tree, add a second-level fuzzy node under each first-level fuzzy node, and link all common nodes in the child nodes of the parent node of the first-level fuzzy node. Under the current level one fuzzy node, all the common nodes in the child sub-nodes of the grandfather node of the second-level fuzzy node are linked to the current second-level fuzzy node, and the first-level fuzzy node as the leaf node is stored with the same parent. The data stored by all the brothers' ordinary nodes, as the secondary fuzzy nodes of the leaf nodes, store the data stored by all the brothers' ordinary nodes of the grandfather to generate the preset database. The method according to claim 1, wherein whether the fuzzy search is performed is determined by: If the information to be retrieved includes a fuzzy wildcard, when the search proceeds to the position of the fuzzy wildcard, it is determined that the fuzzy search is performed at this time. The method according to claim 1, wherein the outputting the found data matching the information to be retrieved comprises: Outputs the data stored in the leaf nodes found. An information matching device, characterized in that the device comprises: An obtaining unit, configured to obtain input information to be retrieved; a matching unit, configured to search, in a preset database, data that matches the information to be retrieved according to a preset rule; An output unit, configured to output the found data that matches the information to be retrieved; The data in the preset database is stored in a Trie tree manner, and the Trie tree includes a fuzzy node in addition to the common node, and the fuzzy node is used to cross each of the same levels when the fuzzy search needs to be performed. The brothers are ordinary nodes and directly reach the child nodes of the common nodes of the brothers in the same level; The preset rules include: The data matching the information to be retrieved is searched in the preset database according to the depth-first algorithm. When the next node needs to be selected, if the fuzzy search is performed at this time, only the fuzzy node in the next node is selected. The device of claim 6 wherein: The fuzzy node is divided into a first-level fuzzy node and a second-level fuzzy node, and each common node of the Trie tree has a first-order fuzzy node, and each first-order fuzzy node has a second-order fuzzy node. All common nodes in the child nodes of the parent node of the first-level fuzzy node are linked to the current level one fuzzy node, and all the ordinary nodes in the child child nodes of the grandparent node of the second-level fuzzy node are linked to the current two Under the fuzzy node, the first-level fuzzy node as the leaf node stores the data stored in all the common nodes of the same parent, and the secondary fuzzy node as the leaf node stores the data stored in all the common nodes of the same grandfather. . The device according to claim 7, wherein the device further comprises: A default database generation unit for: Obtaining data for generating the preset database; storing the data for generating the preset database according to a Trie tree manner; adding a first-order fuzzy section under a common node of each Trie tree Point, add a secondary fuzzy node under each primary fuzzy node, link all common nodes in the child nodes of the parent node of the primary fuzzy node to the current first-level fuzzy node, and the secondary fuzzy node All common nodes in the child nodes of the grandparent node are linked to the current secondary fuzzy node, and the first-level fuzzy nodes that are leaf nodes store the data stored by all the common nodes of the same parent as the leaf nodes. The secondary fuzzy node stores data stored by all the sibling common nodes of the grandfather to generate the preset database. The apparatus according to claim 6, wherein the matching unit determines whether it is a fuzzy search by: If the information to be retrieved includes a fuzzy wildcard, when the search proceeds to the position of the fuzzy wildcard, it is determined that the fuzzy search is performed at this time. The apparatus of claim 6 wherein said output unit is for: Outputs the data stored in the leaf nodes found.

Images