生成正则表达式以匹配列表A中的字符串，但不匹配列表B中的字符串

Question

生成正则表达式以匹配列表A中的字符串，但不匹配列表B中的字符串

javaregexstringalgorithmtext

6

我有两个字符串列表ListA和ListB。我需要生成一个正则表达式，可以匹配ListA中的所有字符串，并且不匹配ListB中的任何字符串。

字符串可以包含任意组合的字符、数字和标点符号。
如果一个字符串出现在ListA中，它保证不会出现在ListB中。
如果一个字符串不在这两个列表中，我不关心匹配的结果应该是什么。

这些列表通常包含数千个字符串，并且字符串之间相似度较高。

我知道这个问题的平凡答案，就是生成形如(Str1)|(Str2)|(Str3)的正则表达式，其中StrN是来自ListA的字符串。但我正在寻找一种更有效的方法来解决这个问题。

理想的解决方案是一种工具，可以接收两个列表并为此生成Java正则表达式。

更新1: 我所说的“高效”是指生成比普通解决方案更短的表达式。理想的算法将生成可能最短的表达式。以下是一些示例。

ListA = { C10 , C15, C195 }
ListB = { Bob, Billy }

理想的表达方式应该是

/^C1.+$/

另一个例子，注意ListB的第三个元素。

ListA = { C10 , C15, C195 }
ListB = { Bob, Billy, C25 }

理想的表达方式是

/^C[^2]{1}.+$/

最后一个例子

ListA = { A , D ,E , F , H } ListB = { B , C , G , I }

理想的表达式与平凡解相同，即

/^(A|D|E|F|H)$/

此外，我不是在寻找理想的解决方案，任何比平凡更好的东西都会有所帮助。我考虑生成平凡解决方案列表，然后尝试合并公共子字符串，同时观察我们不要偏离ListB领域。更新2：我并不特别担心生成正则表达式所需的时间，在现代计算机上，任何少于10分钟的时间都是可以接受的。

- Vlad

1

为什么需要正则表达式？如果您想要一个高效的匹配测试，请使用Trie。 - Bergi

1

你确定只用正则表达式就能完成这个任务吗？在我看来，它需要一个算法。此外，这需要更多的解释：“...一个正则表达式，将匹配ListA中的所有字符串，并且不会匹配ListB中的任何字符串...” - Tulains Córdova

1

我同意Bergi的观点——使用正则表达式似乎不是解决这个问题的正确工具。 - Ted Hopp

2

ListB 有何作用？如果表达式仅匹配来自 ListA 的字符串（这些字符串保证不在 B 中），为什么需要额外检查 ListB？ - Bergi

1

http://cstheory.stackexchange.com/questions/1854/is-finding-the-minimum-regular-expression-an-np-complete-problem - Andrew Cheong

显示剩余10条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Wyzard · Answer 1

如果可以保证两个列表中没有相同的字符串，而且你不关心既不在ListA也不在ListB的字符串，则只需匹配ListA中的字符串；可以完全忽略ListB。

你提到的“平凡答案”是一个完全合理的解决方案。当你说你想要一个“更有效”的方式时，你是指一种生成正则表达式本身更有效的方法呢，还是一种生成匹配字符串更有效的正则表达式的方法？

如果您想有效地生成regex，则大多数语言的字符串库都提供了一种将字符串列表与分隔符字符串（如逗号）连接以生成单个字符串的方法。您真的无法比这更有效率了。
如果您希望您的表达式能够高效地匹配，请确保在使用之前进行“编译”。（大多数regex库都有此功能）编译正则表达式意味着生成实际用于匹配操作的正则表达式库的有限状态机。任何体面的正则表达式库都应该能够优化FSM，例如在可能的情况下将常见的子字符串映射到相同的FSM状态。

或者，您可以完全放弃正则表达式，只需迭代ListA并将其每个字符串与候选字符串进行比较。在这种情况下，单个比较可能更快，因为查找精确的字符串匹配可以将字符串比较为4或8字节块，而正则表达式必须逐个字符查看。但是，如果您有很多字符串要进行比较，则会在内存中多次遍历候选字符串。相反，正则表达式可以遍历候选字符串一次以查找是否匹配。

尝试两种方法。看看哪个更快。