A method, device and system for regular expression matching based on multi-fork tree

Abstract

The embodiment of the present application provides a regular expression matching method, device and system based on a multi-fork tree, which generates a multi-fork tree by performing node fusion on a simplified tree of a regular expression; then, extracts each The constant character of the node, generate a keyword dictionary, and segment the target text according to the keyword dictionary; finally, according to the word segmentation result of the target text, match the hit path from the multi-fork tree, and add the regular expression corresponding to the hit path to the hit set. Among them, the multi-fork tree clusters the regular expressions that exist alone into each subtree in the multi-fork tree, which realizes the reduction of the total number of nodes and the clustering of homologous expressions. When matching the hit path, since the root node of each subtree is different, the subtree to be matched can be quickly located according to the root node, so that the subsequent matching process will only be performed in the subtree to be matched, and no regular expression is required The formula is matched one by one, which reduces the matching amount and improves the matching efficiency.

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