我有数千个字符串列表，每个列表大约有 10 个字符串。给定列表中的大多数字符串都非常相似，尽管有些字符串（很少）与其他字符串完全无关，并且有些字符串包含不相关的单词。它们可以被认为是规范字符串的嘈杂变体。我正在寻找一种算法或库，它将每个列表转换为这个规范的字符串。
这是一份这样的清单。
对于这个列表，任何匹配正则表达式的字符串^Star Wars:? Episode IV (- )?A New Hope$都是可以接受的。
我在 Coursera 上查看了 Andrew Ng 的机器学习课程，但我找不到类似的问题。
作为一个天真的解决方案，我建议首先选择列表中包含最常见标记的字符串。通过这种方式，您可以摆脱不相关的字符串。
在第二个短语中，我将进行多数投票。假设3个句子：
我会一一浏览令牌。我们从“星”开始。它获胜，因为所有字符串都以它开头。“战争”也将获胜。下一个是“：”。它也会赢。
在“希望”之前，所有代币都将获得多数投票。“希望”之后的下一个标记将是“|”或“（”或“-”。在多数投票中没有一个会获胜，所以我会在这里停下来！
另一种解决方案可能是使用Longest common subsequence。
正如我所说，我对此并没有太多考虑。因此，您的问题可能会有更多更好的解决方案:-)
首先计算所有字符串对之间的编辑距离。请参阅http://en.wikipedia.org/wiki/Edit_distance和http://web.stanford.edu/class/cs124/lec/med.pdf。然后根据某个距离阈值排除任何异常值字符串。
对于剩余的字符串，您可以使用距离矩阵来识别最中心的字符串。根据您使用的方法，您可能会得到一些数据的模棱两可的结果。没有一种方法能完美应对所有可能性。出于您的目的，您只需要一些启发式规则来解决歧义——即选择两个或更多候选人。
也许您不想从字符串列表中选择“最中心”，而是想生成一个正则表达式来捕获所有非异常字符串共有的模式。一种方法是合成一个与所有非异常字符串等距的字符串。您可以从矩阵中计算出所需的编辑距离，然后使用这些距离作为约束随机生成常规。然后，您将测试候选正则表达式并接受第一个符合约束条件的正则表达式，并接受非异常值列表中的所有字符串。（从最长的公共子字符串列表开始构建正则表达式，因为这些是非通配符。）