Efficient Regular Expression Matching Based on Positional Inverted Index

doi:10.1109/TKDE.2020.2992295

Return

Efficient Regular Expression Matching Based on Positional Inverted Index

2022-03-01

PRE

DOI：10.1109/TKDE.2020.2992295

Original

Original request for help

Save

Abstract

En 中文

We study the efficient regular expression (regex) matching problem. Existing algorithms are the scanning-based algorithms which typically use an equivalent automaton compiled from the regex query to verify a document. Although some works propose various strategies to quickly jump to candidate locations in a document where a query result may appear, they still need to utilize the scanning-based method to verify these candidate locations. These methods become inefficient when there are still many candidate locations needed to be verified. In this article, we propose a novel approach to efficiently compute all matching positions for a regex query purely based on a positional q-gram inverted index. We propose a gram-driven NFA to represent the language of a regex and show all regex matching locations can be obtained by finding positions on q-grams of GNFA that satisfy certain positional constraints. Then we propose several GNFA-based query plans to answer the query using the positional inverted index. In order to improve the query efficiency, we design the algorithm to build a tree-based query plan by carefully choosing a checking order for positional constraints. Experimental results on real-world datasets show that our method outperforms state-of-the-art methods by up to an order of magnitude in query efficiency.

Keywords:

Regular expression matching

positional inverted index

query plan

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.