2

想象有一组任意字符串。我们现在假设除了几个后续字符之外它们都是相等的（如果这个假设不成立，我可以返回错误）。我现在想派生一个正则表达式来识别字符串中不同的部分。

输入：
“你好 Alice，我是 Bob。”、“你好 John，我是 Bob。”、“你好 Josh，我是 Bob。”

输出：
“你好 (.+)，我是 Bob。”

输入：
“星期一”、“树”、“狗”

输出：
错误

也许找到最长的公共子串或Levenshtein 距离会有所帮助？我还不确定其中一个是否真的适用于我的问题或如何使用它们来解决它。

4

1 回答 1

0

您遇到了一个问题并决定使用正则表达式来解决它——现在您有两个问题。:-)

除了开玩笑，您可以将其分解为两个步骤：

  1. 识别字符串之间的差异。
  2. 查看所有差异并找出匹配它们的正则表达式。

对于 (1)，使用您的语言（如 Python）中的差异计算库difflib来查找两个字符串之间相同区域的列表是一个问题。如果所有字符串都有公共段，则将 string-1 与每个 string-[2..N] 进行比较以分析生成的相同块（您必须聪明地比较每个块的内容及其相对于其他相同块的位置块）。提取和记录相同块之间的文本。

对于您的示例，每次比较时都会得到两个相同的块："Hello "和", I'm Bob.". 相同块之间的文本将是这些字符串："Alice", "John", "Josh".

对于 (2)，最简单的解决方案是将您的发现组合成一个非常字面的正则表达式，其中包括：

Hello+ (Alice|John|Josh)+, I'm Bob.

或者，将在所有字符串中找到的相同相同块之间的任何段替换为.*. 考虑让它成为一个非贪婪的匹配 - .*?。

我不了解自动机理论，无法帮助您解决 DFA/NFA，但如果您需要更高的精度，这是一个可靠的方向。

于 2012-08-31T22:36:23.253 回答