我正在建立一个从多个网站提取的餐厅时间和地址信息数据库。由于同一餐厅的信息可能出现在多个网站中。所以在数据库中我会有一些几乎重复的副本。
由于餐厅的数量很大,比如 100000。然后对于每个新条目,我必须进行 100000^2 的比较,以检查是否已经存在任何名称几乎相似的餐厅信息。所以我问是否有比这更好的有效方法。谢谢你。
我正在建立一个从多个网站提取的餐厅时间和地址信息数据库。由于同一餐厅的信息可能出现在多个网站中。所以在数据库中我会有一些几乎重复的副本。
由于餐厅的数量很大,比如 100000。然后对于每个新条目,我必须进行 100000^2 的比较,以检查是否已经存在任何名称几乎相似的餐厅信息。所以我问是否有比这更好的有效方法。谢谢你。
基本上,您正在寻找记录链接工具。这些工具可以索引记录,然后为每条记录快速定位一小组潜在候选人,然后对这些进行更详细的比较。这避免了 O(n^2) 问题。它们还支持在比较之前清理您的数据,以及更复杂的比较器,如 Levenshtein 和 q-gram。
维基百科上的记录链接页面上曾经有一个工具列表,但它被删除了。如果您想查找它,它仍然存在于版本历史记录中。
我为此编写了自己的工具Duke,它使用 Lucene 进行索引,并内置了详细的比较器。我已经成功地使用它对 220,000 家酒店进行了重复数据删除。我可以在笔记本电脑上使用四个线程在几分钟内运行重复数据删除。
一种方法是构建相似性函数,以便您可以查找一小组现有餐厅来比较您的新餐厅。此查找将使用数据库中的索引并且应该很快。
如何定义相似函数是棘手的部分:) 通常您可以将每条记录转换为一系列标记,在数据库中查找每个标记以找到可能相似的记录。
请参阅这篇博文,我写这篇博文是为了描述我构建的一个系统,用于在抓取的数据中查找附近的重复项。这听起来与您想要做的非常相似,并且由于您的用例更小,我认为您的实现应该更简单。