python - 重复文本检测/散列

Question

我在数据库中有几组字符串。每个集合将有不到 500 个成员，将有数万个集合，字符串是自然语言。我想检测每组中的重复字符串。新字符串将与现有集合进行比较，如果它们是唯一的，则添加到数据库中。

是否有哈希算法可以有效地找到(非常)相似的字符串？例如，字符串可能具有相同数量的单词，但编码可能略有不同(UTF-8 与 Latin-1)。

Answer 1

对于初学者，您可能应该进行某种规范化。您可能应该将所有文本转换为单一编码(例如:UTF-8)。您可能还想做 case-folding，其他 Unicode normalizations可能还会对每组进行排序(取决于您存储它们的方式)。

从你的问题中(对我来说)不清楚你是想找到完全匹配还是只是“相似”的字符串集。如果考虑到标准化后您只关心精确匹配，那么您就大功告成了。只需在字符串集的规范化形式上建立索引，您就可以通过对它们进行规范化来快速查找新集。

如果您想找到接近的匹配项，那么您可能需要进行某种相似性散列。关于 Locality Sensitive Hashing 的维基百科文章描述了许多技术。

许多这些技术背后的基本思想是在每个字符串 h[0] 到 h[n] 上计算一些非常有损的哈希值。要查找新的字符串集，您需要计算它的哈希值并逐一查找。至少获得一个匹配项的任何事物都是“相似的”，匹配项越多，它就越相似(您可以选择将事物切断的阈值)。