基于歧义的“‘Scoring”正则表达式

Question

我有许多由用户提供的正则表达式，并从中选择一个与输入字符串匹配的表达式。现在，在多个表达式匹配的情况下，我想选择最具体的表达式，也就是最不明确的表达式。

更具体地说：--我正在用与几个人一起编写一个IRC机器人，确切地说是用编写的。命令可以由regex注册，其中一些命令是重叠的。可以为每个命令提供某种优先级，但是这将引入另一个失败点。我更愿意在命令注册时根据所提供的正则表达式的模糊性自动生成一种“记分”。我还没有在Google上找到合适的算法。

一种天真的方法，目前可能适用于我的需要，可能是正则表达式中字符与通配符的比例，但是如果您知道这里的任何具体算法，我会感兴趣的。

Answer 1

如果使用可以转换为DFA的grep样式正则表达式，那么对于任何正则表达式，都可以计算出随机字符串匹配它的概率。

我认为这是一个合理的选择，对于你想要的分数--一个随机字符串匹配的概率越低，正则表达式就越具体。对于额外的点，“随机字符串”的概念可以建模人们实际键入的字符串类型。

这不容易，但是可行的。这一过程将是这样的：

1. 为正则表达式生成一个minmal (automaton)。通常使用汤普森的构造(construction)创建NFA，使用powerset构造(construction)转换为DFA，然后应用Hopcroft的算法或类似的(minimization)创建最小的DFA。
2. 将单个接受状态添加到DFA以处理“string的结束”。将“string结束”的转换从以前的每个接受状态添加到新的单个接受状态。
3. 现在，您需要计算随机字符串进入每个状态的概率。对于开始状态，这个概率是1。对于其他状态，您可以建立一个方程来计算输入的概率。它是进入每个前一状态的概率之和，乘以下一次从状态到目标状态的转移的概率(常数)。您可以根据每个字母实际出现在键入命令中的频率来衡量转换概率。您可能会假设字符串在每个状态结束的概率不变(要么转换到接受状态，要么不转换)。
4. 在步骤(3)中，你不能直接计算概率，但是你可以为N个未知数建立N个线性方程组，其中未知数是除起始状态之外的所有状态的进入概率。用高斯消去法(elimination)或其他标准方法求解线性方程组，计算每种状态由随机串进入的概率。

步骤(4)将指定随机字符串进入接受状态的概率，即随机字符串匹配正则表达式的概率。这个概率越低，正则表达式就越具体。