网站开发如何,私人网站制作,在上海注册公司有什么好处,昌图网站最大匹配算法是自然语言处理中的中文匹配算法中最基础的算法#xff0c;分为正向和逆向#xff0c;原理都是一样的。
正向最大匹配算法#xff0c;故名思意#xff0c;从左向右扫描寻找词的最大匹配。
首先我们可以规定一个词的最大长度#xff0c;每次扫描的时候寻找当前…最大匹配算法是自然语言处理中的中文匹配算法中最基础的算法分为正向和逆向原理都是一样的。
正向最大匹配算法故名思意从左向右扫描寻找词的最大匹配。
首先我们可以规定一个词的最大长度每次扫描的时候寻找当前开始的这个长度的词来和字典中的词匹配如果没有找到就缩短长度继续寻找直到找到或者成为单字。
实例
S1计算语言学课程是三个课时 ,设定最大词长MaxLen 5 ,S2
字典中含有三个词[计算语言学]、[课程]、[课时]
1S2S1不为空从S1左边取出候选子串W计算语言学
2查词表“计算语言学”在词表中将W加入到S2中S2“计算语言学/ ” 并将W从S1中去掉此时S1课程是三个课时
3S1不为空于是从S1左边取出候选子串W课程是三个
4查词表W不在词表中将W最右边一个字去掉得到W课程是三
5查词表W不在词表中将W最右边一个字去掉得到W课程是
6查词表W不在词表中将W最右边一个字去掉得到W课程
7查词表W在词表中将W加入到S2中S2“计算语言学/ 课程/ ”并 将W从S1中去掉此时S1是三个课时
8S1不为空于是从S1左边取出候选子串W是三个课时
9查词表W不在词表中将W最右边一个字去掉得到W是三个课
10查词表W不在词表中将W最右边一个字去掉得到W是三个
11查词表W不在词表中将W最右边一个字去掉得到W是三
12查词表W不在词表中将W最右边一个字去掉得到W“是”这时 W是单字将W加入到S2中S2“计算语言学/ 课程/ 是/ ”并将 W从S1中去掉此时S1三个课时
13S1不为空从S1左边取出候选子串W三个课时
14查词表W不在词表中将W最右边一个字去掉得到W三个课
15查词表W不在词表中将W最右边一个字去掉得到W三个
16查词表W不在词表中将W最右边一个字去掉得到W“三”这时 W是单字将W加入到S2中S2“计算语言学/ 课程/ 是/ 三/ ”并 将W从S1中去掉此时S1个课时
17S1不为空从S1左边取出候选子串W个课时
18查词表W不在词表中将W最右边一个字去掉得到W个课
19查词表W不在词表中将W最右边一个字去掉得到W“个” 这时W是单字将W加入到S2中S2“计算语言学/ 课程/ 是/ 三/ 个/ 并将W从S1中去掉此时S1课时
20S1不为空从S1左边取出候选子串W课时
21查词表W在词表中将W加入到S2中S2“计算语言学/ 课程/ 是/ 三/ 个/ 课时/ 并将W从S1中去掉此时S1。
22S1为空输出S2作为分词结果分词过程结束。
中文分词算法的Python实现
脚本接受两个参数一个是输入文件的路径另一个是词典的路径。
它的运行方法如下
python max-match.py
#!/usr/bin/env python
import cPickle as pickle
import sys
window_size5
def max_match_segment(line, dic):
# write your code here
chars line.decode(utf8)
words []
idx 0
while idx len(chars):
matched False
for i in xrange(window_size, 0, -1):
candchars[idx:idxi].encode(utf8)
if cand in dic:
words.append(cand)
matched True
break
if not matched:
i 1
words.append(chars[idx].encode(utf8))
idx i
return words
if __name____main__:
try:
fpiopen(sys.argv[1], r)
except:
print sys.stderr, failed to open file
sys.exit(1)
try:
dic pickle.load(open(sys.argv[2], r))
except:
print sys.stderr, failed to load dict %s % sys.argv[2]
sys.exit(1)
try:
fpo open(out.txt,w)
except:
print sys.stderr, failed to load out.txt
sys.exit(1)
for line in fpi:
fpo.write(\t.join( max_match_segment(line.strip(), dic) ))
当然这只是最基础的还可以有很多高级的优化比如说改成Trie树版本的控制最大词长度的等等。
