Dav*_*lle 4 .net algorithm spell-checking
是否有一个现有的.NET算法能够从预定义的单词列表中检测拼写错误？
例如,假设单词"Stuff"在我的列表中,有人输入"Stuf","sutff"或"stff"或"stiff".我希望能够告诉那个人"Stuff"这个词可能是正确的词.
我不是在谈论任何语法或任何超过一个字母缺失,替代或混合的东西.
我的目标是防止在不同类型的列表中输入相同的单词.不是大写和小写不会对我造成问题,因为一切都是小写的.
这是一个经过充分研究的问题,并且有许多好的算法可以做到这一点.他们中的大多数通过构建某种数据结构来工作,以便能够有效地找到具有相似编辑距离的单词的方式来保存所有合法单词.非正式地,两个字符串之间的编辑距离是将一个字符串转换为另一个字符串所需的更改次数.例如,给定单词"拼写错误"和"拼写错误",编辑距离为1(只是在单词中插入另一个's'),而"cat"和"dog"之间的编辑距离为3(替换每个字母) .
拼写错误的单词可能距离预期的单词只有很小的编辑距离,因此如果您可以以任何方式存储单词,对于任何字符串,查询与字符串相距较小编辑距离的单词,可以提供用户可能意指的可能单词的候选列表.
用于保存该数据的一种常见数据结构是trie,26路树结构,其中每个节点存储字的前缀,并且每个边对应于将一些字母附加到当前前缀.如果您有这样的结构,您可以使用简单的递归树搜索找到与特定单词(可能是某个编辑距离之外)"接近"的单词.在每个点上,跟踪您希望远离目标单词的编辑距离的距离以及到目前为止已处理的拼写错误单词的数量.在每个点上,您可以跟随对应于单词中字母的trie中的边缘,或者可以使用一个编辑距离通过跟随trie中的不同边缘插入新字母.
另一个经常用于此的数据结构是BK树,它以一种方式存储字符串,您可以有效地查询距离某些源字符串一定编辑距离的所有字.这将更直接地解决您的问题,尽管与尝试相比,如何构建BK树的在线资源更少.
一旦找到了某个编辑距离内的单词,您可能希望在将它们呈现给用户之前以某种方式对它们进行排名.这需要您了解人们在实践中倾向于做出什么样的拼写错误.常见错别字包括
要构建一个好的拼写检查器,理想情况下你会遇到与每种类型的错误相关的某种概率.这样,当您列出可能的更正列表时,您可以将它们从最可能到最不可能的排名.
希望这可以帮助!
| 归档时间： |
|
| 查看次数： |
902 次 |
| 最近记录： |