按相似性分组字符串

有很多方法可以比较字符串的相似性。

Here is a site with various similarity metrics 你可以用。

Here is a Wikipedia article with various similarity metrics

你可以使用 Levenshtein Here's

假设您不担心每个单词的拼写错误或其他错误,您可以执行以下操作:

建立一个反向索引,它基本上是一个由word键控的散列,指向一个指向包含该单词的字符串的指针列表(如何处理重复出现的情况取决于您自己)。要确定与给定查询字符串相似的字符串,请查找索引中的每个查询词,并对结果列表中的每个源字符串计算源字符串在每个列表中出现的次数。计数最高的字符串是相似性的最佳候选字符串,因为它们包含最多的共同单词。

然后您可以计算两个字符串之间的编辑距离,或者您想要的任何其他度量。这样就避免了将每个字符串与其他字符串进行比较的O(n^2)复杂性。

它可能太过杀伤力,可能也不完全符合你想要达到的目标,但你可以使用“Ferret”来帮助(Lucene的Ruby版本-全文索引/搜索API)整理标点和格式-如果句子中的常用“停止词”(the,and,is…)不同,这些也可以被过滤掉。

这样,你们的查寻,就有权柄。这权柄就有相似的意思。

http://www.davebalmain.com/ http://www.amazon.co.uk/Ferret-David-Balmain/dp/0596519400/ref=sr_1_2?ie=UTF8&s=books&qid=1264751909&sr=8-2