重复文本检测/哈希
我在数据库里有一组字符串。每组字符串的数量不会超过500个，而这样的组有好几万组，这些字符串都是自然语言。我想在每组里找出重复的字符串。新的字符串会和已有的组进行比较，如果是独一无二的，就会被添加到数据库里。
有没有什么哈希算法可以有效地找到（非常）相似的字符串呢？比如说，这些字符串可能单词数量是一样的，但编码可能会有一点不同（比如UTF-8和Latin-1）。
7 个回答
简单来说，就是猜测一个合适的哈希参数，让它符合你对“相似”的理解。
可能可以用所有字母的总和（A）和相邻字母之间差值的总和（B）来实现。对于每个新字符串，先用它的A和B值快速查找一小部分相似的字符串，然后再对这些字符串进行更仔细的比较。
这可能不是最完美的解决方案，但实际上，很多问题都是这样解决的。此外，目前在基因学领域也有很多工作在解决类似的问题（比如在庞大的数据库中寻找相似的基因序列），不过我觉得还没有一个通用的解决方案被广泛接受。
如果数据库里只有500个字符串，也许你可以直接一个一个地进行比较。首先，把这些字符串转换成一个标准的格式（比如UTF-16）。然后可以用莱文斯坦距离来比较两个字符串的相似度，这是一种很好的方法。
首先，你可能需要做一些规范化的工作。也就是说，你应该把所有的文本转换成一种统一的编码格式，比如说UTF-8。你还可能想要进行大小写转换、其他一些Unicode规范化，或者根据你存储数据的方式对每一组数据进行排序。
从你的问题来看，我不太清楚你是想找完全相同的匹配，还是想找一些“相似”的字符串集合。如果你只关心在规范化后是否有完全相同的匹配，那你基本上就完成了。只需要在规范化后的字符串集合上建立一个索引，这样你就可以快速查找新的集合，只需对它们进行规范化处理。
如果你想找到近似匹配，那么你可能需要做一些相似性哈希的工作。维基百科上关于局部敏感哈希的文章介绍了几种技术。
这些技术的基本思路是对每个字符串计算几个非常“模糊”的哈希值，记作h[0]到h[n]。要查找一个新的字符串集合，你需要计算它的哈希值，然后逐个查找。如果有至少一个匹配的哈希值，就认为它是“相似”的，匹配的越多，说明它们越相似（你可以选择一个阈值来决定相似的程度）。