我有一个单词列表,例如:
mmad
mmaaddd
bbad
bbaadddd
假设根据某些字典,mad 和 bad 被认为是有效词。是否有任何理想的算法或数据结构来查找这些拼写错误的匹配项?我认为 trie 会很有用,但我不确定如果有效的单词列表/字典包含数千个单词,它会如何发挥作用。
编辑:我应该提一下,我不担心从角色的角度来看这些词被消除,即我不希望“mmad”被纠正为“sad”或类似的东西。我认为这就是 Levenshtein 距离和 LD 距离更好的地方;这个问题是其中一个奇怪的子集。