动态规划和中文分词

原创
2017/01/17 09:40
阅读数 180
动态规划dynamical programming,简称dp。了解它请参考《数学之美》第12章和《算法导论》第2版第15章,这里就不重复了。

《算法导论》第15章的“装配线调度”问题是非常好的dp学习算法,用数学语言包装之后有点难懂,我用python写了个简化版,只需要看图15-2,再看下面的代码,就知道dp是怎么回事了。

-----------------------------------------------------
#!/usr/bin/env python
#!-*- coding:utf-8 -*-

#底盘进入装配线需要的时间
e1 = 2
e2 = 4

#底盘离开装配线需要的时间
s1 = 3
s2 = 2

#底盘在装配线上每个装配站的处理时间
a1 = [7, 9, 3, 4, 8, 4]
a2 = [8, 5, 6, 4, 5, 7]

#底盘在装配件之间移动时需要的时间。
t1 = [2, 3, 1, 3, 4]
t2 = [2, 1, 2, 2, 1]

#初始化f1和f2,也就是用进入装配线时间和第一个装配站用时之和
f1 = [e1 + a1[0]
f2 = [e2 + a2[0]

#这一块,就是用dp的方式,分别计算两条装配线的最短时间装配时间
i = 1
l1 = []
l2 = []
while i < 6:
    if (f1[i-1] + a1[i] < f2[i-1]+a1[i]+t2[i-1]):
        f1.append(f1[i-1] + a1[i])
        l1.append(1)
    else:
        f1.append(f2[i-1]+a1[i]+t2[i-1])
        l1.append(2)

    if (f2[i-1] + a2[i] < f1[i-1]+a2[i]+t1[i-1]):
        f2.append(f2[i-1] + a2[i])
        l2.append(2)
    else:
        f2.append(f1[i-1]+a2[i]+t1[i-1])
        l2.append(1)
    i += 1

#离开装配站
f1.append(f1[-1]+s1)
f2.append(f2[-1]+s2)

#f1和f2的最后一个元素分别是38和39,所以从第一条装配线出来的更快。l1和l2计算了底盘在两线之间的移动状态。

print f1
print f2
print l1
print l2
-----------------------------------------------------

关于中文分词:

注:代码和例子借鉴了 http://www.2cto.com/kf/201203/123935.html ,向原作者致谢。

《数学之美》第4章是中文分词问题。中文是句子,比如说,"其中最简单的就是最大匹配的中文分词",如果要让计算机理解这个句子,要先把它拆成若干个词组。根据统计模型,每个词组有不同的出现频率,这个频率是语料决定的,业内的做法是,找一个很大的文本资料,比如几十年里的人民日报,把里面的所有新闻拆成一个一个的词组,然后计算这些词组在所有新闻里的出现次数,由此生成一个巨大的词频表。

搜狗试验室做了一个词频表,在这里 http://www.sogou.com/labs/dl/w.html ,下载在这里 http://download.labs.sogou.com/dl/sogoulabdown/SogouW/SogouW.tar.gz 。这个词频表有157202个高频词。本文使用这个词频表。

如果要把一个句子拆成几个词组,应该尽量把它拆成高频词,越高越好。高频,就是高概率。

处理一个文本,如果要把它拆成概率最高的词组,最简单的方式是遍历所有组合,然后找概率最高的,这在算法上是指数复杂度,太慢,用dp算法处理最合适。

以"其中最简单的就是最大匹配的中文分词"为例,dp算法是这么做的:

1) 从最后一个字往第一个字处理。

2)最后一个字是“词”,查词频表,看它有没有出现,如果出现了,记下词频数,如果没出现,就认为它的词频数默认值是1。然后计算概率,它的概率就是“词频数/157202”,157202就是词频表里的词组总数。很显然,词频表没有这个字,于是它的概率就是1/157202,记作p[16] = 1/157202,p表示概率,16是这个字在句子里的坐标,这个句子一共17个字,坐标从0开始计算,所以它是第16位。

3) 倒数第二个字是“分”。这一次要处理的是两个字,也就是最后一个字和这一个字的组合,也就是“分词”,“分词”是全句的一部分,也就是子句。如何让“分词”这个子句的出现概率最高呢?先从“分”拆开,查它在词频表的词频,词频表没有,所以p[15]=1/157202,如果把“分“和”词”拆开计算概率,那么子句的整体概率就是p[15]*p[16]=(1/157202)*(1/157202)。如果从“词”拆,这么拆的话,“分词”就是一个整体了,查词频表,它的词频数是390214,所以它的概率是390214/157202,也就是说,子句的整体概率是390214/157202,这个概率比前面的高,于是更新一下p[15]=390214/157202。

4) 倒数第三个字是“文”。这一次,要处理三个字“文词汇”。按照跟上面相似的步骤,最佳的分割方式是“文 词汇”。

5) 倒数第四个字是“中”。这一次,要处理四个字“中文词汇”。按照跟上面相似的步骤,最佳的分割方式是“中文 词汇”。

....

以此类推,处理整个句子。

这里的关键是:如果让整个句子的分词结果是概率最高的,那么,每个子句的分词结果也必然是最高的,否则,总是可以找到一个更好的拆分子句方式,让整句的分词结果概率更高。dp的做法是,先从最短的子句开始,找概率最高的分词方式,然后逐步扩展到整句,于是整句的分词概率也就是最高的。

下面是代码:
------------------------------------------
#!/usr/bin/env python
#!-*- coding:utf-8 -*-

import collections

#d是字典,存储从词频表读取的词频数据。defaultdic的好处是,如果词频表没有某个词组,就返回1。
d = collections.defaultdict(lambda:1)

#从词频表里读取词频数,SogouLabDic.dic需要下载,然后放到跟源代码相同的目录。
def init(filename = "SogouLabDic.dic"):
    total = 0
    for line in open(filename).readlines():
        word, freq = line.split('\t')[0:2]
        total += 1
        try:
            d[word.decode('gbk')] = int(freq)
        except:
            d[word] = int(freq)
    d['_t_'] = total

#分词函数
def solve(s):
    l = len(s)
    #p表示概率,初始值是0
    p = [0 for i in range(l+1)]
    #最后一位是为了方便计算,设置成1
    p[l] = 1
    #词频数太大了,不能使用除法,会有精度问题,把分子分母分开存储
    div = [1 for i in range(l+1)]
    #记录拆分位置
    t = [1 for i in range(l)]
    #dp算法做拆分
    for i in range(l-1,-1, -1):
        print "\ni = ", i
        for k in range(1, l-i+1):
            print " k = ", k
            if k > 1 and d[s[i:i+k] == 1:
                print " continue"
                continue
            #判断子句的概率大小,以计算拆分位置
            if d[s[i:i+k]*p[i+k]*div[i] > p[i]*d['_t_']*div[i+k]:
                p[i] = d[s[i:i+k]*p[i+k]
                div[i] = d['_t_'] * div[i+k]
                t[i] = k
    i = 0
    while i < l:
        print s[i:i+t[i].encode("utf8"),
        i = i+t[i]

init()
s="其中最简单的就是最大匹配的中文分词"
s=s.decode('utf8')
solve(s)
------------------------------------------
这句话的拆分结果是:“其中 最简单 的 就是 最大 匹配 的 中文 分词”,效果还不错哦!

再搞个更长一点的吧,这句话是网上对某个餐厅的一段评论:
“接着来到港汇。。皮和鹿都中了这家的现金券。。甜品阿拉果断要来蹭一下。。位于港汇的2楼,一堆服装店的里面。。位置真的有点难找啊。。绕了一大圈最后才找到的。。其实就在一个角落,从某个门进来就可以直接抵达了。。咳咳,我想说门口的胡宇崴我根本不认识。。店内的环境还可以吧,所谓的女仆啥的还有带着面具跳舞之类的我是完全没看到。。阿拉是晚上7点左右去的,是时间不对么???落座后服务员马上每人端上一杯水。。服务还是很周到的。。他家有wifi,密码会写在收银条上。。为了得知密码还得赶紧点单啊。。真是。。西西里海鲜意大利面,68米。。端上来时候就觉得有点坑爹了,菜单上的摆盘多精致啊,面都堆成一座小山的样子,虾什么也大多了。。面的口味一般,茄汁味不浓,吃起面来就觉得没啥味道。。里面有虾、青口贝、鱿鱼什么的,阿拉什么都没吃味道就不予评价了。。法式金砖,72米。。小块吐司上面顶着一个冰淇淋球,看着还是比较美貌的。。摆盘下方则是巧克力酱画的高音谱号和音符,对跳舞香水名字的点题吧。。吐司相对偏软了点,还可以烤的更脆。。比起坑爹的意面,甜品的口味还是能令人满意的。。甜品ok,主食不灵。。"

分词的结果是:
“接着 来到 港 汇 。 。 皮 和 鹿 都 中了 这家 的 现金 券 。 。 甜品 阿拉 果断 要来 蹭 一下 。 。 位于 港 汇 的 2 楼 , 一堆 服装店 的 里面 。 。 位置 真 的 有点 难找 啊 。 。 绕了 一大 圈 最后 才 找到 的 。 。 其实 就在 一个 角落 , 从 某个 门 进来 就可以 直接 抵达 了 。 。 咳咳 , 我想 说 门口 的 胡 宇 崴 我根本 不认识 。 。 店内 的 环境 还可以 吧 , 所谓 的 女仆 啥 的 还有 带着 面具 跳舞 之类 的 我是 完全 没 看到 。 。 阿拉 是 晚上 7 点 左右 去 的 , 是 时间 不对 么 ? ? ? 落座 后 服务员 马上 每人 端 上一 杯水 。 。 服务 还是 很 周到 的 。 。 他家 有 w i f i , 密码 会 写在 收银 条 上 。 。 为了 得知 密码 还得 赶紧 点 单 啊 。 。 真是 。 。 西西里 海鲜 意大利 面 , 6 8 米 。 。 端 上来 时候 就 觉得 有点 坑 爹 了 , 菜单 上 的 摆 盘 多 精致 啊 , 面 都 堆成 一座 小山 的 样子 , 虾 什么 也 大多 了 。 。 面 的 口味 一般 , 茄 汁 味 不 浓 , 吃 起 面 来 就 觉得 没啥 味道 。 。 里面 有 虾 、 青口 贝 、 鱿鱼 什么 的 , 阿拉 什么 都没 吃 味道 就不 予 评价 了 。 。 法式 金砖 , 7 2 米 。 。 小块 吐 司 上面 顶着 一个 冰淇淋 球 , 看着 还是 比较 美貌 的 。 。 摆 盘 下方 则是 巧克力 酱 画 的 高音 谱 号 和 音符 , 对 跳舞 香水 名字 的 点题 吧 。 。 吐 司 相对 偏 软了 点 , 还可以 烤 的 更 脆 。 。 比起 坑 爹 的 意 面 , 甜品 的 口味 还是 能 令人 满意 的 。 。 甜品 o k , 主食 不灵 。 。”

是不是觉得差强人意?这就是自然语言处理的困难之处,不通用,跟行业相关。选择合适的语料库很关键。

另外,python有一个开源的分词包,叫“jieba”,有兴趣的可以试用一下。

广告时间:请关注微信公众号“美食挖”,谢谢!
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部