logo标签列表

高效短语匹配算法

algorithmhadoopphrase
4

我有大约700万个短语需要与约3亿个查询进行匹配。

查询可以是子字符串或包含短语本身。基本上，我想要两个短语之间的“相似度”测量值[不一定是编辑距离]。

请问有人能提供高效算法的指针来完成这个任务吗？我更喜欢分布式算法，因为我将使用Python通过Hadoop进行流处理。

我不明白你想做什么。短语和查询之间的“匹配”需要什么要求？仅仅是短语必须是查询的子字符串吗？你希望从这个算法中得到什么样的输出？ - David Grayson
我已经更新了问题并添加了更多细节。 - Rohan Monga
2个回答
2
1

这至少不是很琐碎的，因为一方面你有非常多的数据，另一方面你还有更多的数据。

最简单的方法是在7百万短语上建立一个Lucene索引，让Hadoop作业查询该索引。不确定是否需要Solr服务器或任何类似Python实现。

Mapper应该写出短语ID或行号，无论您如何标识它。或者至少是短语本身，以及匹配分数。

在reduce步骤中，您可以选择按短语键进行减少，并写出所有相关短语和分数。（或者您想要的任何内容）
有关相似性，您可以在此处阅读更多信息：

Apache Lucene的相似性
Apache Lucene本身

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接