python 英语单词拼写检查算法
- # 网传鹅厂面试题,英语单词拼写检查算法
- # 比如输入hello, 却错误的输入了hellu, 找出出错的字母
- # 感谢知乎知友@Lee Shellay
- # 对词典中的每个词, 逐刺逐字母拓展Trie, 单词完结处结点用END符号标识
- END = '$'
-
- def make_trie(words):
- trie = {}
- for word in words:
- t = trie
- for c in word:
- if c not in t:
- t[c] = {}
- t = t[c]
- t[END] = {}
- return trie
-
- # 容错查找
- # 实质上是对Trie的深度优先搜索,每一步加深时就消耗目标词的一个字母
- # 当搜索到达某个结点时,分为不消耗容错数和消耗容错数的的情形,继续搜索知道目标词为空。
- # 搜索过程中,用path记录搜索路径,该路径及为一个词典中存在的词,作为纠错的参考
- # 最终结果即为诸多搜索停止位置的结点路径的并集
- def check_fuzzy(trie, word, path='', tol=1): #tol为容错数
- if word == '':
- return [path] if END in trie else []
- else:
- p0 = []
- if word[0] in trie:
- p0 = check_fuzzy(trie[word[0]], word[1:], path+word[0], tol)
- p1 = []
- if tol > 0:
- for k in trie:
- if k != word[0]:
- p1.extend(check_fuzzy(trie[k], word[1:], path+k, tol-1))
- return p0 + p1
-
-
- # 测试代码
- words = ['hello', 'hela', 'dome']
- t = make_trie(words)
- print(t)
- print(check_fuzzy(t, 'hellu'))
- print(check_fuzzy(t, 'healu', tol=2))
解压密码: detechn或detechn.com
免责声明
本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。
本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。
本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。