Regular expression matching method, device and system based on multi-way tree

Abstract

An embodiment of the invention provides a regular expression matching method, device and system based on a multi-way tree. The method comprises the following steps: carrying out node fusion through asimplified tree of regular expression; then extracting a constant character of every node from the multi-way tree to generate a keyword dictionary, and carrying out word segmentation on a target textaccording to the keyword dictionary; and finally, matching a hit path from the multi-way tree according to a work segmentation result of the target text, and adding a regular expression correspondingto the hit path into a hit gather. By the multi-way tree, regular expressions which exist singly are clustered into various sub-trees in the multi-way tree, and thus, reduction of the total amount ofnodes and clustering of homologous expression are realized. When the hit path is matched, due to difference of root nodes of the different sub-trees, sub-trees to be matched can be rapidly positionedaccording to the root nodes, thus, a follow-up matching process only can be carried out in to-be-matched sub-trees, the regular expressions do not need to be matched one by one, the matching amount isreduced, and the matching efficiency is improved.

Description

technical field [0001] The present application relates to the technical field of natural language processing, in particular to a multi-tree-based regular expression matching method, device and system. Background technique [0002] In the field of natural language processing technology, regular expressions are used to describe and match a series of strings that match a certain syntax rule, and are often used for text retrieval, text matching or text replacement. Regular expressions are composed of constant characters (also known as ordinary characters) and operator characters (also known as special characters, metacharacters, pattern characters, etc.); where constant characters are used to match text in text retrieval, text matching or text replacement, Operators are used to define the operation rules when constant characters are used to match text. [0003] In the prior art, a large amount of text is sometimes involved in the process of text retrieval, text matching or text...

AI Technical Summary

Problems solved by technology

However, in practical applications, the number of regular expressions to be matched is very large, and can even reach as many as hundreds of thousands, while in the regular expression set, the number of regular expressions corresponding to a certain target text is usually only a few tens Therefore, the method of matching regular expressions one by one in the prior art has a huge amount of data matching in the matching process, and the matching efficiency is low, which cannot meet the actual application requirements.

Images