java - W-shingling 实现 - 存储木瓦

Question

我需要实现w-shingling (Java 中)比较两个 html 文档的相似性。问题是如何收集和储存木瓦。我们假设 (a,rose,is,a,rose,is,a,rose) 是这些文档之一。我想我的算法(使用 LinkedList)不会是最快的:

1. 从文档 (a) 中获取下一个单词 - 如果没有其他单词，则在此停止。
2. 检查带状疱疹列表中的 (a) 情况
3. 如果出现这种情况，请转到第一步
4. 如果不是，请将其附加到列表中并转到第一步

正如我预测的那样，对于大型文档来说这可能会非常慢。你能给我一些提示让它更快吗...？

Answer 1

根据算法，您必须首先创建文档中出现的所有可能的 w-shinglings - w 长度的单词序列。您需要维护一个从文档读取的 w 长度的单词序列窗口(即读取 w + 1 个单词后，您可以丢弃缓冲区中的第一个单词)。

为了存储 w-shingling，您可以创建不可变类并实现 equals()和 hashCode()以提高比较性能。当您构建 shinglings 时，您可以将它们存储在 Set 中，以动态删除重复项。