starter_code.ipynb
39.2 KB
搭建一个分词工具
Part 1 基于枚举方法来搭建中文分词工具
此项目需要的数据:
- 综合类中文词库.xlsx: 包含了中文词,当做词典来用(第二列:词频+词性)
- 以变量的方式提供了部分unigram概率 word_prob
举个例子: 给定词典=[我们 学习 人工 智能 人工智能 未来 是], 另外我们给定unigram概率:p(我们)=0.25, p(学习)=0.15, p(人工)=0.05, p(智能)=0.1, p(人工智能)=0.2, p(未来)=0.1, p(是)=0.15
Step 1: 对于给定字符串:”我们学习人工智能,人工智能是未来“, 找出所有可能的分割方式
- [我们,学习,人工智能,人工智能,是,未来]
- [我们,学习,人工,智能,人工智能,是,未来]
- [我们,学习,人工,智能,人工,智能,是,未来]
- [我们,学习,人工智能,人工,智能,是,未来] .......
Step 2: 我们也可以计算出每一个切分之后句子的概率
- p(我们,学习,人工智能,人工智能,是,未来)= -log p(我们)-log p(学习)-log p(人工智能)-log p(人工智能)-log p(是)-log p(未来)
- p(我们,学习,人工,智能,人工智能,是,未来)=-log p(我们)-log p(学习)-log p(人工)-log p(智能)-log p(人工智能)-log p(是)-log p(未来)
- p(我们,学习,人工,智能,人工,智能,是,未来)=-log p(我们)-log p(学习)-log p(人工)-log p(智能)-log p(人工)-log p(智能)-log p(是)-log p(未来)
- p(我们,学习,人工智能,人工,智能,是,未来)=-log p(我们)-log p(学习)-log p(人工智能)-log p(人工)-log p(智能)-log(是)-log p(未来) .....
Step 3: 返回第二步中概率最大的结果
In [1]:
import pandas as pd import numpy as np
In [2]:
import xlrd data=xlrd.open_workbook('综合类中文词库.xlsx')#excle文件位置 sheet=data.sheets()[0] #读取第一bai个表du col=sheet.col_values(0) #读取第一列 col
Out [2]:
['酢', '做做事', '做做饭', '做做', '做作', '做主', '做针线', '做张做智', '做张做致', '做张做势', '做贼心虚', '做月子', '做一天和尚撞一天钟', '做一日和尚撞一天钟', '做秀', '做小伏低', '做戏', '做文章', '做为', '做头', '做通', '做私商勾当', '做寿', '做手脚', '做事', '做市商', '做生意', '做生日', '做神做鬼', '做人做世', '做人', '做起', '做派', '做梦', '做媒', '做礼拜', '做客', '做假账', '做家教', '做活儿', '做活', '做好做恶', '做好做歹', '做好', '做鬼做神', '做鬼', '做官者', '做官当老爷', '做官', '做功', '做工精细', '做工', '做刚做柔', '做饭', '做法', '做东道', '做东', '做到', '做大做强', '做出', '做成', '做操', '做菜', '做不了', '做伴', '做爱', '做', '座座', '座子', '座钟', '座右铭', '座椅', '座像', '座向', '座席', '座无虚席', '座位图', '座位数', '座位号', '座位费', '座位表', '座位', '座套', '座谈会', '座谈', '座上客', '座上宾', '座山峰', '座山雕', '座圈', '座区', '座骑', '座票', '座盘', '座落在', '座落', '座楼', '座架', '座驾', '座机', '座环', '座号', '座豪华', '座垫', '座次', '座充', '座车', '座厕', '座舱', '座标', '座便器', '座便', '座', '唑', '祚庆', '祚', '胙', '怍', '阼', '坐坐', '坐姿', '坐庄', '坐支', '坐镇', '坐诊', '坐在', '坐运筹策', '坐月子', '坐浴', '坐于涂炭', '坐拥书城', '坐拥百城', '坐椅', '坐以待旦', '坐以待毙', '坐药', '坐言起行', '坐薪悬胆', '坐薪尝胆', '坐像', '坐享其功', '坐享其成', '坐下', '坐席', '坐无虚席', '坐卧针毡', '坐卧不宁', '坐卧不离', '坐卧不安', '坐位表', '坐位', '坐堂', '坐探', '坐台', '坐树无言', '坐树不言', '坐守', '坐收渔利', '坐收', '坐视成败', '坐视不救', '坐视不管', '坐视', '坐式', '坐食山空', '坐失事机', '坐失良机', '坐失机宜', '坐失', '坐上琴心', '坐商', '坐山观虎斗', '坐山雕', '坐骑', '坐盆', '坐喷气式', '坐南朝北', '坐落', '坐立不安', '坐力', '坐冷板凳', '坐牢', '坐困愁城', '坐客', '坐具', '坐井观天', '坐禁闭', '坐江山', '坐监', '坐怀不乱', '坐化', '坐果', '坐观成败', '坐骨神经', '坐骨', '坐功', '坐而论道', '坐而待旦', '坐而待弊', '坐而待毙', '坐墩', '坐蔸', '坐定', '坐垫', '坐地自划', '坐地分脏', '坐地分赃', '坐地', '坐凳', '坐等', '坐待', '坐大', '坐次', '坐床', '坐船', '坐筹帷幄', '坐吃山空', '坐吃山崩', '坐车', '坐禅', '坐厕', '坐舱', '坐不重席', '坐不窥堂', '坐不改姓', '坐不垂堂', '坐不安席', '坐标轴', '坐标系', '坐标', '坐便器', '坐便', '坐北朝南', '坐班制', '坐班', '坐', '作作有芒', '作作', '作祖', '作子', '作主', '作忠', '作证', '作者投稿', '作者群', '作者', '作哲', '作战室', '作战区', '作战科', '作战服', '作战处', '作战部', '作战', '作贼心虚', '作育人材', '作用力', '作用点', '作用', '作勇', '作翊', '作役', '作义', '作揖', '作业组', '作业证', '作业者', '作业员', '作业线', '作业题', '作业区', '作业面', '作业率', '作业流程', '作业量', '作业机', '作业费', '作业队', '作业点', '作业车', '作业本', '作业', '作言造语', '作训服', '作训', '作秀', '作兴', '作协', '作孝', '作小服低', '作响', '作宪', '作息时间', '作息', '作物', '作务衣', '作武', '作文指导', '作文网', '作文题', '作文课', '作文辅导', '作文簿', '作文本', '作文', '作伪者', '作伪', '作为', '作威作福', '作威', '作图', '作田', '作态', '作祟', '作手脚', '作适', '作势', '作士', '作生', '作舍道旁', '作舍道边', '作善降祥', '作善', '作如是观', '作人', '作曲者', '作曲系', '作曲家', '作曲法', '作曲编曲', '作曲', '作乔', '作品展示', '作品展览', '作品展', '作品阅读', '作品选', '作品欣赏', '作品赏析', '作品目录', '作品列表', '作品简介', '作品集', '作品', '作陪', '作派', '作呕', '作弄', '作孽', '作鸟兽散', '作难', '作牧', '作民', '作美', '作梅', '作洛', '作乱', '作料', '作乐', '作浪兴风', '作朗', '作客思想', '作客', '作金石声', '作娇', '作践', '作贱', '作件', '作茧自缚', '作奸犯科', '作嫁衣裳', '作价', '作假者', '作假', '作家作品', '作家资料', '作家在线', '作家杂志', '作家协会', '作家网', '作家群', '作家风景', '作家档案', '作家出版社', '作家', '作画', '作好作歹', '作好', '作翰', '作鬼', '作怪', '作谷', '作古正经', '作古', '作工', '作梗', '作福作威', '作孚', '作夫', '作风建设', '作风', '作废', '作坊式', '作坊', '作范', '作法自弊', '作法自毙', '作法', '作伐', '作恶者', '作恶多端', '作恶', '作厄', '作对', '作东', '作登乡', '作到', '作代会', '作大', '作答', '作词家', '作词', '作辍无常', '作出', '作成', '作宾', '作别', '作壁上观', '作弊器', '作弊', '作保', '作伴儿', '作伴', '作罢', '作案者', '作案人', '作案', '作', '佐佐木元', '佐佐木', '佐佐', '佐助', '佐竹', '佐州', '佐治亚州', '佐治亚大学', '佐治亚', '佐治', '佐织', '佐之才', '佐证', '佐钊', '佐佑', '佐饔得尝', '佐雍得尝', '佐雍得', '佐弋', '佐伊', '佐野', '佐享', '佐相', '佐维奇', '佐托夫', '佐藤嘉恭', '佐藤', '佐特', '佐塔', '佐书', '佐使', '佐山', '佐人', '佐钦', '佐派', '佐纳', '佐幕', '佐谋', '佐默', '佐命', '佐米曲坦', '佐美', '佐洛埃格塞格', '佐洛', '佐罗', '佐卢', '佐林', '佐料', '佐理', '佐拉', '佐克', '佐卡', '佐酒', '佐剂', '佐欢', '佐贺县', '佐贺', '佐哈尔', '佐国', '佐攻者', '佐格', '佐夫斯基', '佐夫', '佐法尔', '佐尔坦', '佐尔格', '佐尔', '佐恩', '佐渡岛', '佐斗', '佐登', '佐村镇', '佐川', '佐车', '佐餐', '佐伯', '佐埃', '佐', '左左右右', '左宗棠', '左枝右梧', '左支右吾', '左支右调', '左支右绌', '左证', '左镇乡', '左镇', '左云县', '左云', '左右翼', '左右眼', '左右为难', '左右腿', '左右图史', '左右手', '左右脑', '左右两难', '左右开弓', '左右江', '左右逢源', '左右逢原', '左右方', '左右侧', '左右采获', '左右岸', '左右', '左拥右抱', '左萦右拂', '左营', '左翼文化运动', '左翼', '左宜右有', '左宜右宜', '左眼', '左延安', '左旋肉碱', '左旋炔诺孕酮', '左旋咪唑涂布剂', '左旋', '左舷', '左贤王', '左贤', '左下角', '左下方', '左下', '左膝', '左溪', '左文襄公', '左文', '左腿', '左徒', '左图右书', '左图右史', '左图', '左铁镛', '左天觉', '左提右挈', '左藤', '左思右想', '左思', '左司马', '左书右息', '左首', '左手指', '左手腕', '左手画方', '左手', '左上角', '左上方', '左上臂', '左上', '左嗓子', '左炔诺孕酮', '左券', '左权县', '左权墓', '左权', '左丘明', '左晴雯', '左倾机会主义', '左倾', '左强', '左前卫', '左铅右椠', '左迁', '左旗', '左撇子', '左膀右臂', '左膀', '左派', '左木', '左民党', '左面', '左绵', '左满舵', '左轮手枪', '左轮', '左路', '左岭镇', '左麟右李', '左邻右舍', '左邻右里', '左列', '左联五烈士', '左联', '左连璧', '左拉', '左近', '左金丸', '左脚', '左江日报', '左江', '左键', '左家庄', '左家塘', '左家', '左焕琮', '左焕琛', '左后卫', '左行', '左海', '左归丸', '左顾右盼', '左顾右眄', '左贡县', '左贡', '左公柳', '左各庄镇', '左辅右弼', '左锋', '左方', '左耳', '左躲右闪', '左端', '左道旁门', '左传', '左丞相', '左侧', '左不过', '左边前卫', '左边锋', '左边', '左臂右膀', '左臂', '左岸', '左安门', '左安龙', '左安安', '左', '阝', '昨夜', '昨晚', '昨天', '昨日', '昨儿个', '昨儿', '昨', '嘬嘬', '嘬', '撙撙', '撙节', '撙', '鳟鱼', '鳟', '樽俎折冲', '樽俎', '樽前月下', '樽', '遵嘱', '遵照', '遵章守纪', '遵章率', '遵义县', '遵义钛厂', '遵义市政府', '遵义市委', '遵义市', '遵义会议', '遵义供电局', '遵义', '遵业', '遵尧', '遵养时晦', '遵养晦时', '遵养待时', '遵厌兆祥', '遵循', '遵学', '遵序', '遵信', '遵帅', '遵守宪法', '遵守', '遵时养晦', '遵生', '遵钦', '遵命', '遵理', '遵礼', '遵敬', '遵纪守法户', '遵纪守法', '遵纪爱民', '遵纪', '遵化县', '遵化市', '遵化', '遵鸿', '遵行', '遵海', '遵复', '遵奉', '遵法', '遵而勿失', '遵而不失', '遵典', '遵德', '遵道秉义', '遵道', '遵从', '遵', '尊俎折冲', '尊主泽民', '尊主', '尊重', '尊者', '尊长', '尊章', '尊造', '尊远', '尊仪', '尊严感', '尊严', '尊萱', '尊姓大名', '尊姓', '尊幸', '尊贤使能', '尊贤', '尊无二上', '尊翁', '尊为', '尊威', '尊特拉', '尊堂', '尊肃', '尊寿', '尊师重教', '尊师重道', '尊师贵道', '尊师', '尊盛', '尊胜陀罗尼经幢', '尊胜', '尊神', '尊尚', '尊容', '尊荣', '尊亲', '尊年尚齿', '尊明', '尊礼', '尊老敬老', '尊老爱幼', '尊老', '尊君', '尊爵', '尊敬', '尊介', '尊驾', '尊纪', '尊华', '尊厚', '尊号', '尊行', '尊贵', '尊古卑今', '尊公', '尊庚', '尊刚', '尊府', '尊甫', '尊夫人', '尊奉', '尊范', '尊慈', '尊宠', '尊崇', '尊驰', '尊称', '尊卑', '尊宝', '尊安', '尊', '醉枣', '醉玉颓山', '醉鱼草', '醉意', '醉眼', '醉醺醺', '醉心', '醉乡', '醉舞狂歌', '醉舞', '醉翁之意不在酒', '醉翁亭记', '醉翁亭', '醉吐相茵', '醉态', '醉死梦生', '醉生梦死', '醉山颓倒', '醉人', '醉拳', '醉梦花', '醉马草', '醉酒者', '醉酒饱德', '醉酒', '醉鸡', '醉话', '醉汉', '醉鬼', '醉白池', '醉', '蕞', '罪状', '罪证', '罪责难逃', '罪责', '罪有攸归', '罪有应得', '罪应万死', '罪业深重', '罪业', '罪人不孥', '罪人', '罪愆', '罪孽深重', '罪孽', '罪逆深重', '罪名', '罪魁祸首', '罪魁', '罪加一等', '罪行', '罪过形式', '罪过', '罪该万死', '罪犯', '罪恶滔天', '罪恶贯盈', '罪恶感', '罪恶都市', '罪恶的黑手', '罪恶', '罪当万死', '罪大恶极', '罪错', '罪不胜诛', '罪不容诛', '罪不容赦', '罪不可逭', '罪案率', '罪案', '罪', '最最', '最重', '最终幻想', '最终', '最长', '最早', '最远点', '最远', '最游记', '最优化', '最新作品', '最新咨讯', '最新专辑', '最新政策', '最新招聘', '最新战况', '最新在线', '最新音乐', '最新讯息', '最新型', '最新消息', '最新下载', '最新文章', '最新图片', '最新商情', '最新软件', '最新期刊', '最新漏洞', '最新楼盘', '最新景点', '最新技术', '最新活动', '最新公告', '最新更新', '最新法规', '最新发行', '最新电影', '最新大片', '最新产品', '最新报价', '最新报道', '最新版', '最新', '最小化', '最小公倍数', '最小', '最先', '最为', '最深', '最少', '最全面', '最全', '最轻量级', '最强音', '最强', '最前沿', '最起码', '最末', '最美', '最快', '最近新书', '最近似值', '最近', '最简式', '最简论坛', '最简分数', '最佳期', '最佳奖', '最佳化', '最佳', '最惠国待遇', '最惠国', '最惠', '最後', '最后战士', '最后一秒', '最后通牒', '最后通谍', '最后的晚餐', '最后的审判', '最后的爱', '最后', '最好', '最高值', '最高者', '最高院', '最高人民检察院政治部', '最高人民检察院', '最高人民法院审判委员会', '最高人民法院党组', '最高人民法院', '最高检察院', '最高检', '最高价', '最高级', '最高峰', '最高分', '最高法院', '最高额', '最高点', '最高处', '最高潮', '最高层', '最高', '最底层', '最低值', '最低限', '最低价', '最低谷', '最低点', '最低', '最大值', '最大者', '最大化', '最大公约数', '最大', ...]
In [3]:
# TODO: 第一步: 从综合类中文词库.xlsx 中读取所有中文词。 # hint: 思考一下用什么数据结构来存储这个词典会比较好? 要考虑我们每次查询一个单词的效率。 max_len_word = 0 dic_words = {} # 保存词典库中读取的单词 for word in col: dic_words[word] = 0.00001 len_word = len(word) if len_word > max_len_word: max_len_word = len_word # 以下是每一个单词出现的概率。为了问题的简化,我们只列出了一小部分单词的概率。 在这里没有出现的的单词但是出现在词典里的,统一把概率设置成为0.00001 # 比如 p("学院")=p("概率")=...0.00001 word_prob = {"北京":0.03,"的":0.08,"天":0.005,"气":0.005,"天气":0.06,"真":0.04,"好":0.05,"真好":0.04,"啊":0.01,"真好啊":0.02, "今":0.01,"今天":0.07,"课程":0.06,"内容":0.06,"有":0.05,"很":0.03,"很有":0.04,"意思":0.06,"有意思":0.005,"课":0.01, "程":0.005,"经常":0.08,"意见":0.08,"意":0.01,"见":0.005,"有意见":0.02,"分歧":0.04,"分":0.02, "歧":0.005} for key, values in word_prob.items(): dic_words[key] = values print (sum(word_prob.values()))
Out [3]:
1.0000000000000002
In [4]:
def segment(input_str): segments = [] # 存储所有分词的结果。如果次字符串不可能被完全切分,则返回空列表(list) len_input_str = len(input_str) if len_input_str == 0: # 空字符串 return [segments] else: result = [] for idx in range(1, len_input_str + 1): if input_str[:idx] in dic_words: for remain_segment in segment(input_str[idx:]): result.append([input_str[:idx]] + remain_segment) return result
In [5]:
## TODO 请编写word_segment_naive函数来实现对输入字符串的分词 def word_segment_naive(input_str): """ 1. 对于输入字符串做分词,并返回所有可行的分词之后的结果。 2. 针对于每一个返回结果,计算句子的概率 3. 返回概率最高的最作为最后结果 input_str: 输入字符串 输入格式:“今天天气好” best_segment: 最好的分词结果 输出格式:["今天","天气","好"] """ # TODO: 第一步: 计算所有可能的分词结果,要保证每个分完的词存在于词典里,这个结果有可能会非常多。 segments = segment(input_str) # 存储所有分词的结果。如果次字符串不可能被完全切分,则返回空列表(list) # 格式为:segments = [["今天",“天气”,“好”],["今天",“天“,”气”,“好”],["今“,”天",“天气”,“好”],...] # TODO: 第二步:循环所有的分词结果,并计算出概率最高的分词结果,并返回 best_score = np.inf for seg in segments: score = 0 for word in seg: score -= np.log(dic_words[word]) if score < best_score: best_score = score best_segment = seg return best_segment
In [6]:
# 测试 print (word_segment_naive("北京的天气真好啊")) print (word_segment_naive("今天的课程内容很有意思")) print (word_segment_naive("经常有意见分歧"))
Out [6]:
['北京', '的', '天气', '真好啊'] ['今天', '的', '课程', '内容', '很有', '意思'] ['经常', '有意见', '分歧']
Part 2 基于维特比算法来优化上述流程
此项目需要的数据:
- 综合类中文词库.xlsx: 包含了中文词,当做词典来用
- 以变量的方式提供了部分unigram概率word_prob
举个例子: 给定词典=[我们 学习 人工 智能 人工智能 未来 是], 另外我们给定unigram概率:p(我们)=0.25, p(学习)=0.15, p(人工)=0.05, p(智能)=0.1, p(人工智能)=0.2, p(未来)=0.1, p(是)=0.15
Step 1: 根据词典,输入的句子和 word_prob来创建带权重的有向图(Directed Graph) 参考:课程内容
有向图的每一条边是一个单词的概率(只要存在于词典里的都可以作为一个合法的单词),这些概率已经给出(存放在word_prob)。 注意:思考用什么方式来存储这种有向图比较合适? 不一定只有一种方式来存储这种结构。
Step 2: 编写维特比算法(viterebi)算法来找出其中最好的PATH, 也就是最好的句子切分
具体算法参考课程中讲过的内容
Step 3: 返回结果
跟PART 1的要求一致
In [7]:
## TODO 请编写word_segment_viterbi函数来实现对输入字符串的分词 def word_segment_viterbi(input_str): """ 1. 基于输入字符串,词典,以及给定的unigram概率来创建DAG(有向图)。 2. 编写维特比算法来寻找最优的PATH 3. 返回分词结果 input_str: 输入字符串 输入格式:“今天天气好” best_segment: 最好的分词结果 输出格式:["今天","天气","好"] """ # TODO: 第一步:根据词典,输入的句子,以及给定的unigram概率来创建带权重的有向图(Directed Graph) 参考:课程内容 # 有向图的每一条边是一个单词的概率(只要存在于词典里的都可以作为一个合法的单词),这些概率在 word_prob,如果不在word_prob里的单词但在 # 词典里存在的,统一用概率值0.00001。 # 注意:思考用什么方式来存储这种有向图比较合适? 不一定有只有一种方式来存储这种结构。 graph = {} N = len(input_str) for idx in range(N,-1,-1): temp = [] for k in range(idx): if input_str[k:idx] in dic_words: temp.append(k) graph[idx] = temp # TODO: 第二步: 利用维特比算法来找出最好的PATH, 这个PATH是P(sentence)最大或者 -log P(sentence)最小的PATH。 # hint: 思考为什么不用相乘: p(w1)p(w2)...而是使用negative log sum: -log(w1)-log(w2)-... # 防止下溢出 res = [0]*(N+1) last_index = [0]*(N+1) for i in range(1,N+1): temp = np.inf for j in graph[i]: if input_str[j:i] in dic_words: if temp > res[j] - np.log(dic_words[input_str[j:i]]): temp = res[j] - np.log(dic_words[input_str[j:i]]) last_index[i] = j res[i] = temp path = list(set(last_index)) # TODO: 第三步: 根据最好的PATH, 返回最好的切分 len_path = len(path) best_segment = [input_str[path[x]:path[x+1]] for x in range(len_path-1)] best_segment.append(input_str[path[len_path-1]:]) return best_segment
In [8]:
# 测试 print(word_segment_viterbi("北京的天气真好啊")) print(word_segment_viterbi("今天的课程内容很有意思")) print(word_segment_viterbi("经常有意见分歧"))
Out [8]:
['北京', '的', '天气', '真好啊'] ['今天', '的', '课程', '内容', '很有', '意思'] ['经常', '有', '意见', '分歧']
TODO: 第一种方法和第二种方法的时间复杂度和空间复杂度分别是多少?
网格宽度为D,长度为N
第一个方法:
时间复杂度= , 空间复杂度=
第二个方法: 时间复杂度= , 空间复杂度=
TODO:如果把上述的分词工具持续优化,有哪些可以考虑的方法? (至少列出3点)
- (例), 目前的概率是不完整的,可以考虑大量的语料库,然后从中计算出每一个词出现的概率,这样更加真实
- 概率太低的词可以不用记录,节约空间
- 隐马尔可夫不止基于前一个词,而是基于前几个词
- 对概率进行转换,保证相加为1