计算两个列表之间编辑距离的最有效方法？

Question

我有两个文件，一个是CSV，另一个是文本文件。它们都包含Unicode单词。我的任务是比较这两个文件中的单词以纠正拼写错误。（CSV文件包含拼写错误的单词，文本文件包含正确的单词）CSV文件包含大约1000个单词，文本文件包含5000个单词。 我为这个任务实现了以下代码，因为我是python新手，所以效率非常低。有什么建议可以提高效率

import pandas as pd
import nltk
 
df = pd.read_csv('C:/mis_spel.csv',encoding='utf8')
list_check_words = df['words'].tolist()

df2 = pd.read_csv('C:/words.txt',encoding='utf8',delimiter='\t')
list_words = df2['word'].tolist()
 
for word in list_check_words:
    for dix in list_words:
        ed = nltk.edit_distance(word, dix)
        if (ed<2):
            print(word, dix, ed)

Answer 1

对于您的用例来说，这可能是一种过度的杀伤力，但无论如何，我还是把它放在这里。顺便说一句，现在拼写自动更正的行业标准涉及到从单词嵌入的角度来看待这个问题。在过去，使用了基于n-gram的概率方法，但现在不再使用了

您想做的事情可能如下所示：

1. 训练模型生成字符级单词嵌入
2. 将整个字典投影到向量空间，并建立索引以进行高效搜索
3. 对于每个拼错的单词，将其与其最近的邻居配对

我在下面添加了对两篇不同文章的引用，这两篇文章更详细地解释了这一点。不过有一个建议，请尝试从gensim中探索ANNOY索引，这对于近似近邻搜索来说是非常快的。从个人经验来讲

• 第1条：Embedding for spelling correction
• 第2条：Spelling Correction Using Deep Learning: How Bi-Directional LSTM with Attention Flow works in Spelling Correction