algorithm - 句子索引

Question

我有几万个短文档，每个文档包含 10 到 20 个英语句子(以及一些其他非句子内容，如 HTML 格式或其他“垃圾”)。这些文件是从其他较长的文件中切出的——换句话说，较短的文件“A1”可能是原始文件“A”的第 10 到 20 句，而另一个较短的文件“A2”可能是同一文件原始文件的第 11 到 25 句“A”，并且一些原始源文档可能是其他原始源文档的摘要或副本，因此原始源文档“B”也可能包含原始源文档“A”的第 10 到 20 句，尽管不一定在相同的位置。而同一组句子可能已经从“B”中提取到另一个短文档“B3”中。

对于每个句子，或者至少每个超过一定长度的句子(比如，> 3 个词长)，我想生成一个包含该句子出现的每个短文档的列表。我想扫描现有的更短的文档并生成该索引，并在我将更长的原始源文档分解为更短的文档时更新该索引。

我在想我需要的是一些代码来为一个句子制作一个有效的哈希码，而这个句子为两个不同的句子生成相同哈希码的可能性非常低。 Java String.hashCode() 中使用的哈希算法是一个不错的选择吗？ MD5 或其他加密散列似乎对于此目的而言过于昂贵和矫枉过正。

Answer 1

我最近评估了散列算法，要求在几百万个输入中几乎不存在散列冲突的可能性，并且散列必须非常快。 CityHash毫无疑问是赢家。

如果您对计算哈希冲突的概率感兴趣，该主题有时称为生日问题。它背后的数学原理在这里:

https://sites.google.com/site/craigandera/craigs-stuff/odds-ends/the-birthday-problem-calculator