从有噪声的字符串列表中提取规范字符串

Question

我有数千个字符串列表，每个列表大约有10个字符串。给定列表中的大多数字符串非常相似，尽管有些字符串(很少)与其他字符串完全无关，有些字符串包含不相关的单词。它们可以被认为是标准字符串的噪声变体。我正在寻找一个算法或库，它将把每个列表转换成这个规范字符串。

这是一份这样的清单。

• 星球大战:第四集新希望StarWars.com
• 星球大战第四集“新希望”(1977)
• 星球大战:第四集-新希望-烂番茄
• 看星球大战:第四集-网上新希望免费
• “星球大战”(1977) -最伟大的电影
• 记录 4海报承诺死在舷外马达上- SciFiNow

对于这个列表，任何匹配正则表达式^Star Wars:? Episode IV (- )?A New Hope$的字符串都是可以接受的。

我看过安德鲁·吴( Andrew )的课程“课程机器学习”，但我找不到类似的问题。

Answer 1

作为一种天真的解决方案，我建议首先选择包含列表中最频繁的标记的字符串。这样你就可以摆脱不相关的字符串了。

在第二个短语中，我会投过半数票。假设这三句话：

• 星球大战:第四集新希望StarWars.com
• 星球大战第四集“新希望”(1977)
• 星球大战:第四集-新希望-烂番茄

我会一个一个地检查这些代币。我们从“明星”开始。当所有的字符串都从它开始时，它就赢了。“战争”也会赢。下一个是":“。它也会赢。

所有的代币都将以多数票投票，直到“希望”为止。在“希望”之后的下一个标记将是“AC.26”或"(“或"-”)。没有人会在多数票中获胜，所以我就到此为止！

另一个解决方案可能是使用最长公共子序列。

就像我说的，我对这件事没有太多的考虑。因此，您的问题可能有更好的解决方案:-)

Answer 2

首先计算所有字符串对之间的编辑距离。见http://en.wikipedia.org/wiki/Edit_距离和http://web.stanford.edu/class/cs124/lec/med.pdf。然后根据某种距离阈值排除任何异常值字符串。

对于剩余的字符串，您可以使用距离矩阵来识别最中心的字符串。根据您使用的方法，您可能会得到一些数据的模糊结果。没有一种方法适合所有的可能性。就您的目的而言，您所需要的只是一些启发式规则来解决歧义--即挑选两个或多个候选人。

也许您不想从字符串列表中选择“最中心的”，而是希望生成一个正则表达式来捕获所有非异常字符串所共有的模式。其中一种方法是合成一个与所有非离群值字符串等距的字符串。您可以计算出从矩阵所需的编辑距离，然后使用这些距离作为约束随机生成规则。然后，您将测试候选正则表达式，并接受符合约束的第一个正则表达式，并接受非异常列表中的所有字符串。(开始从最长的公共子字符串列表构建正则表达式，因为它们是非通配符字符。)