如何有效地找到一组术语和一组句子之间的所有模糊匹配？

Question

我有一个句子列表（例如“这是一个例句”）和一个术语表（例如“句子”，“例句”），需要找到所有与某个Levenshtein比率截止的句子匹配的术语。你知道吗

我怎样才能做得足够快？拆分句子，使用FTS查找出现在术语中的单词，并按比率过滤术语，这些方法都很有效，但速度相当慢。现在我正在使用sphinxsearch+python Levelshtein，有更好的工具吗？你知道吗

反向搜索：句子中的FTS匹配词会更快吗？你知道吗

Answer 1

如果速度是一个真正的问题，如果你的术语表不会经常更新，与你想要做的搜索数量相比，你可以研究类似于Levenshtein Automaton的东西。我不知道有哪个python库支持它，但是如果您真的需要它，您可以自己实现它。要找到所有可能的路径需要一些动态规划。你知道吗

如果您只需要完成它，只需在词汇表上循环，并针对字符串中的每个单词测试每个单词。这会在多项式时间内给你一个答案。如果您使用的是多核处理器，那么您可以通过执行in parallel来获得一些加速。你知道吗