6

可能重复：
如何从给定的字符串列表中自动生成正则表达式？

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

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

这些列表通常包含数千个字符串，并且字符串彼此非常相似。

我知道这个问题的简单答案，它只是生成一个形式为 ListA 中的字符串(Str1)|(Str2)|(Str3)的正则表达式。StrN但我正在寻找一种更有效的方法来做到这一点。

理想的解决方案是某种工具，它将获取两个列表并为此生成一个 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*：我并不特别担心生成 RegEx 所需的时间，现代机器上 10 分钟以下的任何内容都是可以接受的

4

1 回答 1

0

如果保证两个列表中都没有字符串，并且您不关心两个列表中的字符串，那么您只需要匹配 ListA 中的字符串；您可以完全忽略 ListB。

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

  • 如果您想有效地生成正则表达式，大多数语言的字符串工具都提供了一种将字符串列表与分隔符字符串（例如逗号）连接起来以生成单个字符串的方法。你真的没有比这更有效的了。
  • 如果您希望表达式有效地匹配事物，请确保在使用它之前“编译”它。（大多数正则表达式库都有此功能。）编译正则表达式意味着生成正则表达式库实际用于匹配操作的有限状态机。任何像样的正则表达式库都应该在优化 FSM 方面做得不错，例如尽可能将公共子字符串映射到相同的 FSM 状态。

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

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

于 2012-10-14T22:23:37.027 回答