python - 纠正文本中错别字的最佳算法

Question

我有一个词库列表和一个有拼写错误(拼写错误)的文本，我想根据库列表更正单词拼写错误

例如

在单词列表中:

listOfWord = [...,"halo","saya","sedangkan","semangat","cemooh"..];

这是我的字符串:

string = "haaalllllllooo ssya sdngkan ceemoooh , smngat semoga menyenangkan"

我想将拼写错误更改为正确的，例如:

string = "halo saya sedangkan cemooh, semangat semoga menyenangkan"

检查列表中每个单词的最佳算法是什么，因为我在列表中有数百万个单词并且有很多可能性

Answer 1

这取决于您的数据存储方式，但您可能希望使用像 Aho–Corasick 这样的模式匹配算法。 .当然，这假设您的输入数据结构是 Trie。 Trie一个非常节省空间的存储容器，用于存放您可能也感兴趣的单词(同样，取决于您的环境。)