在字典中找到最匹配的单词

Question

我正在创建一个程序来读取扫描的手写文档并将其转换为文本.公认的单词必须来自我创建的约300个单词的字典.例如,如果手写单词被识别为"heilo",但我的词典只包含"hello"和"world",则应将其转换为"hello".但是,如果它认为它是"星球",它就不应该与任何东西相匹配.我认为一种可能的方法是创建一个得分,即识别的单词与词典中每个单词的匹配程度.如果没有得到最低分,则找不到匹配项.

我正在用C#编写应用程序.是否有任何库/示例可以做这样的事情,或者我是否必须从头开始编码所有内容？

谢谢

Answer 1

标准库中没有任何东西可以计算单词之间的距离,但是在互联网上可以找到很多例子:查找"编辑距离"或"Levenshtein距离".我们的想法是根据第一个字符串的更改次数来衡量相似性,以使其成为第二个字符串."heil"和"hello"之间的距离为2,因为您需要将"i"替换为"l"(第一次编辑),然后附加"o"(第二次编辑).

在寻找实现或实现自己的实现时,避免使用2D数组进行简单的实现,因为它不具有内存效率.使用O(min(m,n))内存要求的修改而不是"天真" O(m*n).