2

我有一个简单的正则表达式列表：

ABC.+DE.+FHIJ.+
.+XY.+Z.+AB
.+KLM.+NO.+J.+
QRST.+UV

它们都有 .+ 的交替模式，并且某些文本（我将称之为“单词”）重复了若干次。模式可能以 .+ 开头或结尾，也可能不以 .+ 结尾。这些正则表达式都是互斥的。添加另一个正则表达式时，我想删除任何其他匹配的正则表达式，并添加一个正则表达式，将添加的正则表达式与其所有匹配项结合起来。例如，添加：

.+J.+

会匹配，

ABC.+DE.+FHIJ.+
.+KLM.+NO.+J.+

因此，这些将被删除并替换为添加的正则表达式，从而导致：

.+J.+ 
.+XY.+Z.+AB
QRST.+UV

我需要以某种数据结构或（最好）以有效的方式将这些模式存储在数据库中。我首先尝试了一个字典树，只是意识到在正则表达式以 .* 开头的情况下，它必须在整个树中搜索下一个单词，即 O(2^n) 的顺序。不幸的是，（除非我弄错了）似乎 SQLite（我正在使用）和我使用过的任何其他关系数据库都不支持“正则表达式”作为数据类型。我的问题是，有没有一种有效的方法来存储和检索这种简单的正则表达式？如果没有固定方法，是否存在一些相对有效的数据结构（例如，在最坏的摊销多项式时间）？

4

1 回答 1

0

您能否解释一下您使用这些正则表达式的目的，因为这样可以更容易地提供更好的答案？特别是当我看到您拆分正则表达式的方式时，我想知道Trie或有向无环词图是否更合适。

从他们那里您可能会发现您的答案很简单，就像提供更好的规范化或找到专门为您的问题领域制作的替代无 SQL 数据库一样简单。

于 2012-08-01T02:26:31.803 回答