这篇讲义都是五笔打的
laekov 2018.04.12
Overview
作业要求
写一个拼音输入法, 一行一行地读拼音, 输出对应的汉语句子
84: 两小时就能写完
给出的数据
- GBK编码的拼音->汉字对应表
- 新浪新闻一年的文章
评分
- 基础2字模型
- 扩展3字模型
- 四字, 双词, 三词…
需要写什么东西
- 拼音 2 汉字的 map
- 快速查找某个字/词词频的 map
- 估值函数和 infer 的算法
训练数据处理
最常用的16位编码是utf-8, 但是 Python 默认是 ASCII 的
所以在程序第一行写上
# -*- coding:utf-8 -*-
Py 内部的 u'一个字符串' 可以用来表示 unicode 格式的字符串. 但是好像用不到.
创建 pinyin to 汉字的 map
读 GBK 文件的最简单的方法
with open('somefile.txt', 'r', encoding = 'gbk') as f:
for (lineno, content) in enumerate(f):
dealWithALine(content)
content 的格式
wo 窝 我 握 渥 (五笔党词穷了)
python 自带分割
py2ch_map = {}
def dealWithALine(c):
d = c.split()
py2ch_map[d[0]] = d
把 map 存进文件
python 带了一个叫 pickle 的库 (很原生, 也很原生地慢)
json 也可以
numpy 也有 dump 的功能
import pickle
with open('some.pickle', 'rb') as f:
data = pickle.load(f)
with open('some.pickle', 'wb') as f:
pickle.dump(data, f)
记得用 b 二进制模式
创建词频表
有 gbk 也有 utf-8, 直接用 utf-8
每行的格式大概长这样
{"html": "原标题：被困36天重见天日昨晚，第一名被困矿工通过救生吊带被成功救出。经过36天艰难救援，山东平邑“12·25”石膏矿坍塌事故中又有4名被困矿工获救。去年12月25日，山东省平邑县玉荣商贸有限公司石膏矿发生坍塌，当时共有29名作业人员被困井下。事故发生后，救援人员先后成功打通4个小口径保命孔，通过2号孔和7号孔发现4名被困矿工幸存者并与其取得联系，先后为他们输送充足的食物、保暖内衣、照明工具等物资。截至昨日，共有15名井下被困矿工获救，其他14名井下被困矿工，1人已确认遇难，13人仍然失联。新华社记者 郭绪雷 摄详见A14·中国", "time": "2016-01-30 03:20",
"title": "被困36天重见天日",
"url": "http://news.sina.com.cn/o/2016-01-30/doc-ifxnzanm3825052.shtml"}
是个 json, 其中 title 和 html 可以作为语料.
python 处理 json
import json
def dealWithALine(l):
data = json.loads(l)
dealAsMaterial(data['html'])
dealAsMaterial(data['title'])
分割语料
数字, 标点之类的东西要去掉
使用正则表达式. (参形式语言与自动机课)
import re
def dealAsMaterial(l):
pieces = re.split(r' |,|\.|\d', l) # 还有很多请自己补充
for i in pieces:
addToMap(i)
单双字扔进词频表
freq_map = {}
def addToMap(l):
global freq_map
for i in range(len(l)):
w = l[i]
if not w in freq_map:
freq_map[w] = 1
else:
freq_map[w] += 1
w = l[i : i + 2]
if not w in freq_map:
freq_map[w] = 1
else:
freq_map[w] += 1
Infer 算法
概率模型
设有一个串$\overline{ab}$
事件$A$表示$a$出现
事件$B$表示$b$出现
则有条件概率公式, 也有人叫马尔可夫概率链
$$P(B|A) = \frac{P(AB)}{P(A)}=\frac{freq_map[\overline{ab}]}{freq_map[a]}$$
这个概率表示了前一个字是$a$时后一个字是$b$的概率
设答案是$S=\overline{a_1a_2\dots a_n}$
假设估值函数为
$$Val(s) = \sum_{i=1}^{n-1}P(a_{i+1}|a_i)$$
找最好的答案就是要最大化上面这个式子
这里你需要实现一个求条件概率的代码
def getLinkValue(a, b):
rat1 = freq_dict[a + b] / freq_dict[a]
rat2 = freq_dict[b]
return smooth(rat1, rat2)
平滑化自己想办法实现就好
动态规划
动态规划是显然的做法
设$F_{i,j}$表示第$i$个字是$j$时$\overline{a_1a_2\dots a_i}$的最大价值
易得到状态转移方程
$$F_{i,j} = \max_{k\in D_{i-1}}{{F_{i-1}{k} + \frac{freq_map[\overline{kj}]}{freq_map[k]} }} $$
代码实现
f = [ {} ] * (n + 1)
f[0]['<start>'] = { 'val': 0 }
for i in range(1, n + 1):
for j in py[a[i]]:
f[i][j] = { 'val': 0, 'from': 0 }
for k in f[i - 1]:
if f[i - 1][k]['val'] + getLinkValue(k, j) > f[i][j]['val']:
f[i][j]['val'] = f[i - 1][k]['val'] + getLinkValue(k, j)
f[i][j]['from'] = k
记录from后就逆向查找即可获得答案
讨论内容
如何提高性能和提高精准度
优化上述DP的性能
对于每个$i$, 跑完一轮后只留值最高的$k$个
优化精准度
- 高端的估值函数
- 三词模型
- 引入新的学习数据