updated at 2012.10.8：https://github.com/scturtle/zhseg

昨天的算法课老师以中文分词为例讲了DP,换了种简单的方式(求分词后频率和最大)实现了一下,效果不错,频率词典是从这里找的: http://download.csdn.net/source/347899  ,实测词典放到dict里后占了18MB内存

DP原理是令p[i]为s[i : n-1]的最优解,初始化为p[n]=0,转移公式为:

p[i]=max( freq(s[i : i+k-1] ) + p[i+k] )        1<=k<=n-i

代码如下:

update at 2011.5.12: 使用了defaultdict简化了代码

# coding: utf-8

import collections
d=collections.defaultdict(lambda:0)

def init(dictfile):
    f=open(dictfile,'r')
    while 1:
        line=f.readline()
        if not line: break
        word, freq = line.split('\t')
        d[word.decode('gbk')]=int(freq)
    f.close()

def fenci(s):
    l=len(s)
    p=[0 for i in range(l+1)]
    t=[1 for i in range(l)]
    for i in range(l-1,-1,-1):
        for k in range(1,l-i+1):
            if(d[s[i:i+k]]+p[i+k] > p[i]):
                p[i]=d[s[i:i+k]]+p[i+k] 
                t[i]=k
    print 'sum:',p[0]
    i=0
    while i<l:
        print s[i:i+t[i]].encode('utf8'), # 'gbk' for win
        i=i+t[i]


if __name__ == '__main__':
    init('dict.txt')
    s="科学研究需要大量的资金但社会资源有限需要政府调控所以需要政府的限制"
    s=s.decode('utf8')
    fenci(s)

显示结果为:

sum: 33505
科学 研究 需要 大量 的 资金 但 社会 资源 有限 需要 政府 调控 所以 需要 政府 的 限制

顺便贴一个以前写的求拼音首字母的小脚本:

# coding: utf-8

a=[ i.decode('utf8').encode('gbk') for i in 
     ['澳', '怖', '错', '堕', '贰', '咐', '过',
      '祸', '祸', '骏', '阔', '络', '穆', '诺',
      '沤', '瀑', '群', '弱', '所', '唾',
      '唾', '唾', '误', '褕', '孕', '座',] ]

def firstpy(s):
    s=s.encode('gbk')
    i=0
    while i<26 and a[i]<s:
        i+=1
    return '%c' % (97+i)

if __name__=='__main__':
    s='判断字符串首字母'.decode('utf8')
    for i in range(len(s)):
        print firstpy(s[i]),