python - 有效的编辑距离

Question

我有一个很大的语料库，我试图在语料库中找到最相似的 n-gram。对于这种情况，我使用get_close matches.

问题是这个过程需要很多时间。一位朋友建议我将 n-gram 转换为 MD5，然后计算距离。我怀疑它会起作用。散列对散列是不变的吗？距离计算是否有效地在 MD5 上运行？

Post scriptum，在大型语料库中计算字符串（如n-gram）之间距离的最有效方法是什么？

标签： pythonnlpmd5corpusedit-distance

Answer 1

一个有前途的方法是度量嵌入。在这篇论文：Convolutional Embedding for Edit Distance研究人员指出，该算法可以将搜索速度提高几个数量级。在进行训练度量嵌入之后，您可以应用近似最近邻算法来找到距离最短的 k 个文本。

HTH。