我有一组大约 700 万个短语来匹配大约 3 亿个查询。
查询可以是子字符串或包含短语本身。基本上我想要衡量两个短语之间的“相似性”[不一定是编辑距离]
有人可以给出一些有效算法的指导来做到这一点。我更喜欢分布式算法，因为我将使用 python 通过流在 Hadoop 上执行此操作。
问问题
1695 次
2 回答
2
B ed树看起来很有趣
B ed -Tree：基于编辑距离的字符串相似性搜索的通用索引结构（演示文稿的 Pdf）
于 2011-02-21T13:23:01.303 回答
1
这至少不是很微不足道，因为一方面你有很多数据，另一方面甚至更多。
最简单的方法是 7 mio 上的 lucene 索引。短语并让 hadoop 作业查询索引。不太确定您是否需要一个 solr 服务器，或者 python 中的任何类似实现。
映射器应该写出短语 id 或 linenumber，无论您必须识别它。或者至少是短语本身，以及匹配分数。
在归约步骤中，您可以对短语键进行归约，并用分数写出所有相关的短语。（或任何您想要的）
对于相似性，您可以在此处进一步阅读：
Apache Lucene 的相似性
Apache Lucene 本身
于 2011-02-22T09:56:10.150 回答