文档章节

动态规划和中文分词

brian_2017
 brian_2017
发布于 2017/01/17 09:40
字数 2696
阅读 13
收藏 0
动态规划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”,有兴趣的可以试用一下。

广告时间:请关注微信公众号“美食挖”,谢谢!

© 著作权归作者所有

brian_2017
粉丝 3
博文 61
码字总数 145216
作品 0
私信 提问
Go中文分词--Sego

词典用双数组trie(Double-Array Trie)实现, 分词器算法为基于词频的最短路径加动态规划。 支持普通和搜索引擎两种分词模式,支持用户词典、词性标注,可运行JSON RPC服务。 分词速度单线程...

匿名
2016/04/18
1K
0
python中文分词:结巴分词

中文分词是中文文本处理的一个基础性工作,结巴分词利用进行中文分词。其基本实现原理有三点: 基于Trie树结构实现高效的词图扫描,生成句子中汉字所有可能成词情况所构成的有向无环图(DAG...

技术mix呢
2017/11/10
0
0
python中文分词,使用结巴分词对python进行分词

在采集美女站时,需要对关键词进行分词,最终采用的是python的结巴分词方法. 中文分词是中文文本处理的一个基础性工作,结巴分词利用进行中文分词。其基本实现原理有三点: 基于Trie树结构实现...

yangjiyue0520
2017/11/04
50
0
Hanlp等七种优秀的开源中文分词库推荐

中文分词是中文文本处理的基础步骤,也是中文人机自然语言交互的基础模块。由于中文句子中没有词的界限,因此在进行中文自然语言处理时,通常需要先进行分词。 纵观整个开源领域,陆陆续续做...

左手的倒影
2018/10/12
259
1
【NLP】【二】jieba源码分析之分词

【一】词典加载 利用jieba进行分词时,jieba会自动加载词典,这里jieba使用python中的字典数据结构进行字典数据的存储,其中key为word,value为frequency即词频。 1. jieba中的词典如下: ji...

muqiusangyang
2018/11/02
188
0

没有更多内容

加载失败,请刷新页面

加载更多

golang-字符串-地址分析

demo package mainimport "fmt"func main() {str := "map.baidu.com"fmt.Println(&str, str)str = str[0:5]fmt.Println(&str, str)str = "abc"fmt.Println(&s......

李琼涛
今天
4
0
Spring Boot WebFlux 增删改查完整实战 demo

03:WebFlux Web CRUD 实践 前言 上一篇基于功能性端点去创建一个简单服务,实现了 Hello 。这一篇用 Spring Boot WebFlux 的注解控制层技术创建一个 CRUD WebFlux 应用,让开发更方便。这里...

泥瓦匠BYSocket
今天
6
0
从0开始学FreeRTOS-(列表与列表项)-3

FreeRTOS列表&列表项的源码解读 第一次看列表与列表项的时候,感觉很像是链表,虽然我自己的链表也不太会,但是就是感觉很像。 在FreeRTOS中,列表与列表项使用得非常多,是FreeRTOS的一个数...

杰杰1号
今天
4
0
Java反射

Java 反射 反射是框架设计的灵魂(使用的前提条件:必须先得到代表的字节码的 Class,Class 类 用于表示.class 文件(字节码)) 一、反射的概述 定义:JAVA 反射机制是在运行状态中,对于任...

zzz1122334
今天
5
0
聊聊nacos的LocalConfigInfoProcessor

序 本文主要研究一下nacos的LocalConfigInfoProcessor LocalConfigInfoProcessor nacos-1.1.3/client/src/main/java/com/alibaba/nacos/client/config/impl/LocalConfigInfoProcessor.java p......

go4it
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部