我正在尝试用 JAVA 编写一个程序，该程序将字典存储在 HashMap 中(每个单词在不同的键下)并将给定单词与字典中的单词进行比较，如果不是，则提出拼写建议在字典中找到 - 基本上是一个拼写检查程序。
我已经想出了比较算法(即 Needleman-Wunsch 然后 Levenshtein 距离)等，但是当它弄清楚字典 HashMap 中的哪些词来比较这个词时卡住了，例如“hellooo”。
我无法比较“ohello”[应该更正为“hello”到字典 b/c 中的每个单词，这会花费太长时间，而且我无法将它与字典中以 'o' b/c 开头的所有单词进行比较应该是“你好”。
有什么想法吗？
最佳答案
最常见的拼写错误是
- 删除一个字母(更小的词或分词)
- 交换相邻的字母
- 更改字母(QWERTY 相邻字母)
- 插入字母
一些报告说 70-90% 的错误属于上述类别(编辑距离 1)
查看下面的 url，它提供了针对单一错误或双重错误的解决方案(编辑距离 1 或 2)。您需要的几乎所有东西都在这里!
How to write a spelling corrector
仅供引用:您可以在上述文章的底部找到各种编程语言的实现。我在我的一些项目中使用过它，实际准确率非常好，有时超过作者声称的 95+%。
--基于OP的评论-- 如果您不想预先计算每个可能的更改然后在 map 上搜索，我建议您使用 patricia trie ( radix tree ) 而不是 HashMap。不幸的是，您将再次需要处理“首字母错误”(例如，删除第一个字母或将第一个字母替换为第二个字母，或者仅将其替换为相邻的 Qwerty)并且您很有可能会限制搜索。
您甚至可以将它与额外的索引映射或带有“反向”单词的 Trie 或省略前 N 个字符(例如前 2 个)的额外索引结合使用，这样您就可以捕获仅在前缀上发生的错误。
关于algorithm - 将单词与字典中的目标单词进行比较，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34323397/