AlgorithmsByPython/CheckErrorWord.py at master · lanhaixuan/AlgorithmsByPython · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# 网传鹅厂面试题,英语单词拼写检查算法
# 比如输入hello, 却错误的输入了hellu, 找出出错的字母
# 感谢知乎知友@Lee Shellay

# 对词典中的每个词, 逐刺逐字母拓展Trie, 单词完结处结点用END符号标识
END='$'

defmake_trie(words):
trie= {}
forwordinwords:
t=trie
forcinword:
ifcnotint:
t[c] = {}
t=t[c]
t[END] = {}
returntrie

# 容错查找
# 实质上是对Trie的深度优先搜索,每一步加深时就消耗目标词的一个字母
# 当搜索到达某个结点时,分为不消耗容错数和消耗容错数的的情形,继续搜索知道目标词为空。
# 搜索过程中,用path记录搜索路径,该路径及为一个词典中存在的词,作为纠错的参考
# 最终结果即为诸多搜索停止位置的结点路径的并集
defcheck_fuzzy(trie, word, path='', tol=1): #tol为容错数
ifword=='':
return [path] ifENDintrieelse []
else:
p0= []
ifword[0] intrie:
p0=check_fuzzy(trie[word[0]], word[1:], path+word[0], tol)
p1= []
iftol>0:
forkintrie:
ifk!=word[0]:
p1.extend(check_fuzzy(trie[k], word[1:], path+k, tol-1))
returnp0+p1


# 测试代码
words= ['hello', 'hela', 'dome']
t=make_trie(words)
print(t)
print(check_fuzzy(t, 'hellu'))
print(check_fuzzy(t, 'healu', tol=2))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# 网传鹅厂面试题,英语单词拼写检查算法
# 比如输入hello, 却错误的输入了hellu, 找出出错的字母
# 感谢知乎知友@Lee Shellay

# 对词典中的每个词, 逐刺逐字母拓展Trie, 单词完结处结点用END符号标识
END='$'

defmake_trie(words):
trie= {}
forwordinwords:
t=trie
forcinword:
ifcnotint:
t[c] = {}
t=t[c]
t[END] = {}
returntrie

# 容错查找
# 实质上是对Trie的深度优先搜索,每一步加深时就消耗目标词的一个字母
# 当搜索到达某个结点时,分为不消耗容错数和消耗容错数的的情形,继续搜索知道目标词为空。
# 搜索过程中,用path记录搜索路径,该路径及为一个词典中存在的词,作为纠错的参考
# 最终结果即为诸多搜索停止位置的结点路径的并集
defcheck_fuzzy(trie, word, path='', tol=1): #tol为容错数
ifword=='':
return [path] ifENDintrieelse []
else:
p0= []
ifword[0] intrie:
p0=check_fuzzy(trie[word[0]], word[1:], path+word[0], tol)
p1= []
iftol>0:
forkintrie:
ifk!=word[0]:
p1.extend(check_fuzzy(trie[k], word[1:], path+k, tol-1))
returnp0+p1


# 测试代码
words= ['hello', 'hela', 'dome']
t=make_trie(words)
print(t)
print(check_fuzzy(t, 'hellu'))
print(check_fuzzy(t, 'healu', tol=2))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# 网传鹅厂面试题,英语单词拼写检查算法
# 比如输入hello, 却错误的输入了hellu, 找出出错的字母
# 感谢知乎知友@Lee Shellay

# 对词典中的每个词, 逐刺逐字母拓展Trie, 单词完结处结点用END符号标识
END='$'

defmake_trie(words):
trie= {}
forwordinwords:
t=trie
forcinword:
ifcnotint:
t[c] = {}
t=t[c]
t[END] = {}
returntrie

# 容错查找
# 实质上是对Trie的深度优先搜索,每一步加深时就消耗目标词的一个字母
# 当搜索到达某个结点时,分为不消耗容错数和消耗容错数的的情形,继续搜索知道目标词为空。
# 搜索过程中,用path记录搜索路径,该路径及为一个词典中存在的词,作为纠错的参考
# 最终结果即为诸多搜索停止位置的结点路径的并集
defcheck_fuzzy(trie, word, path='', tol=1): #tol为容错数
ifword=='':
return [path] ifENDintrieelse []
else:
p0= []
ifword[0] intrie:
p0=check_fuzzy(trie[word[0]], word[1:], path+word[0], tol)
p1= []
iftol>0:
forkintrie:
ifk!=word[0]:
p1.extend(check_fuzzy(trie[k], word[1:], path+k, tol-1))
returnp0+p1


# 测试代码
words= ['hello', 'hela', 'dome']
t=make_trie(words)
print(t)
print(check_fuzzy(t, 'hellu'))
print(check_fuzzy(t, 'healu', tol=2))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# 网传鹅厂面试题,英语单词拼写检查算法
# 比如输入hello, 却错误的输入了hellu, 找出出错的字母
# 感谢知乎知友@Lee Shellay

# 对词典中的每个词, 逐刺逐字母拓展Trie, 单词完结处结点用END符号标识
END='$'

defmake_trie(words):
trie= {}
forwordinwords:
t=trie
forcinword:
ifcnotint:
t[c] = {}
t=t[c]
t[END] = {}
returntrie

# 容错查找
# 实质上是对Trie的深度优先搜索,每一步加深时就消耗目标词的一个字母
# 当搜索到达某个结点时,分为不消耗容错数和消耗容错数的的情形,继续搜索知道目标词为空。
# 搜索过程中,用path记录搜索路径,该路径及为一个词典中存在的词,作为纠错的参考
# 最终结果即为诸多搜索停止位置的结点路径的并集
defcheck_fuzzy(trie, word, path='', tol=1): #tol为容错数
ifword=='':
return [path] ifENDintrieelse []
else:
p0= []
ifword[0] intrie:
p0=check_fuzzy(trie[word[0]], word[1:], path+word[0], tol)
p1= []
iftol>0:
forkintrie:
ifk!=word[0]:
p1.extend(check_fuzzy(trie[k], word[1:], path+k, tol-1))
returnp0+p1


# 测试代码
words= ['hello', 'hela', 'dome']
t=make_trie(words)
print(t)
print(check_fuzzy(t, 'hellu'))
print(check_fuzzy(t, 'healu', tol=2))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# 网传鹅厂面试题,英语单词拼写检查算法
# 比如输入hello, 却错误的输入了hellu, 找出出错的字母
# 感谢知乎知友@Lee Shellay

# 对词典中的每个词, 逐刺逐字母拓展Trie, 单词完结处结点用END符号标识
END='$'

defmake_trie(words):
trie= {}
forwordinwords:
t=trie
forcinword:
ifcnotint:
t[c] = {}
t=t[c]
t[END] = {}
returntrie

# 容错查找
# 实质上是对Trie的深度优先搜索,每一步加深时就消耗目标词的一个字母
# 当搜索到达某个结点时,分为不消耗容错数和消耗容错数的的情形,继续搜索知道目标词为空。
# 搜索过程中,用path记录搜索路径,该路径及为一个词典中存在的词,作为纠错的参考
# 最终结果即为诸多搜索停止位置的结点路径的并集
defcheck_fuzzy(trie, word, path='', tol=1): #tol为容错数
ifword=='':
return [path] ifENDintrieelse []
else:
p0= []
ifword[0] intrie:
p0=check_fuzzy(trie[word[0]], word[1:], path+word[0], tol)
p1= []
iftol>0:
forkintrie:
ifk!=word[0]:
p1.extend(check_fuzzy(trie[k], word[1:], path+k, tol-1))
returnp0+p1


# 测试代码
words= ['hello', 'hela', 'dome']
t=make_trie(words)
print(t)
print(check_fuzzy(t, 'hellu'))
print(check_fuzzy(t, 'healu', tol=2))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# 网传鹅厂面试题,英语单词拼写检查算法
# 比如输入hello, 却错误的输入了hellu, 找出出错的字母
# 感谢知乎知友@Lee Shellay

# 对词典中的每个词, 逐刺逐字母拓展Trie, 单词完结处结点用END符号标识
END='$'

defmake_trie(words):
trie= {}
forwordinwords:
t=trie
forcinword:
ifcnotint:
t[c] = {}
t=t[c]
t[END] = {}
returntrie

# 容错查找
# 实质上是对Trie的深度优先搜索,每一步加深时就消耗目标词的一个字母
# 当搜索到达某个结点时,分为不消耗容错数和消耗容错数的的情形,继续搜索知道目标词为空。
# 搜索过程中,用path记录搜索路径,该路径及为一个词典中存在的词,作为纠错的参考
# 最终结果即为诸多搜索停止位置的结点路径的并集
defcheck_fuzzy(trie, word, path='', tol=1): #tol为容错数
ifword=='':
return [path] ifENDintrieelse []
else:
p0= []
ifword[0] intrie:
p0=check_fuzzy(trie[word[0]], word[1:], path+word[0], tol)
p1= []
iftol>0:
forkintrie:
ifk!=word[0]:
p1.extend(check_fuzzy(trie[k], word[1:], path+k, tol-1))
returnp0+p1


# 测试代码
words= ['hello', 'hela', 'dome']
t=make_trie(words)
print(t)
print(check_fuzzy(t, 'hellu'))
print(check_fuzzy(t, 'healu', tol=2))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# 网传鹅厂面试题,英语单词拼写检查算法
# 比如输入hello, 却错误的输入了hellu, 找出出错的字母
# 感谢知乎知友@Lee Shellay

# 对词典中的每个词, 逐刺逐字母拓展Trie, 单词完结处结点用END符号标识
END='$'

defmake_trie(words):
trie= {}
forwordinwords:
t=trie
forcinword:
ifcnotint:
t[c] = {}
t=t[c]
t[END] = {}
returntrie

# 容错查找
# 实质上是对Trie的深度优先搜索,每一步加深时就消耗目标词的一个字母
# 当搜索到达某个结点时,分为不消耗容错数和消耗容错数的的情形,继续搜索知道目标词为空。
# 搜索过程中,用path记录搜索路径,该路径及为一个词典中存在的词,作为纠错的参考
# 最终结果即为诸多搜索停止位置的结点路径的并集
defcheck_fuzzy(trie, word, path='', tol=1): #tol为容错数
ifword=='':
return [path] ifENDintrieelse []
else:
p0= []
ifword[0] intrie:
p0=check_fuzzy(trie[word[0]], word[1:], path+word[0], tol)
p1= []
iftol>0:
forkintrie:
ifk!=word[0]:
p1.extend(check_fuzzy(trie[k], word[1:], path+k, tol-1))
returnp0+p1


# 测试代码
words= ['hello', 'hela', 'dome']
t=make_trie(words)
print(t)
print(check_fuzzy(t, 'hellu'))
print(check_fuzzy(t, 'healu', tol=2))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# 网传鹅厂面试题,英语单词拼写检查算法
# 比如输入hello, 却错误的输入了hellu, 找出出错的字母
# 感谢知乎知友@Lee Shellay

# 对词典中的每个词, 逐刺逐字母拓展Trie, 单词完结处结点用END符号标识
END='$'

defmake_trie(words):
trie= {}
forwordinwords:
t=trie
forcinword:
ifcnotint:
t[c] = {}
t=t[c]
t[END] = {}
returntrie

# 容错查找
# 实质上是对Trie的深度优先搜索,每一步加深时就消耗目标词的一个字母
# 当搜索到达某个结点时,分为不消耗容错数和消耗容错数的的情形,继续搜索知道目标词为空。
# 搜索过程中,用path记录搜索路径,该路径及为一个词典中存在的词,作为纠错的参考
# 最终结果即为诸多搜索停止位置的结点路径的并集
defcheck_fuzzy(trie, word, path='', tol=1): #tol为容错数
ifword=='':
return [path] ifENDintrieelse []
else:
p0= []
ifword[0] intrie:
p0=check_fuzzy(trie[word[0]], word[1:], path+word[0], tol)
p1= []
iftol>0:
forkintrie:
ifk!=word[0]:
p1.extend(check_fuzzy(trie[k], word[1:], path+k, tol-1))
returnp0+p1


# 测试代码
words= ['hello', 'hela', 'dome']
t=make_trie(words)
print(t)
print(check_fuzzy(t, 'hellu'))
print(check_fuzzy(t, 'healu', tol=2))