starter_code.ipynb 39.2 KB

搭建一个分词工具

Part 1 基于枚举方法来搭建中文分词工具

此项目需要的数据:

  1. 综合类中文词库.xlsx: 包含了中文词,当做词典来用(第二列:词频+词性)
  2. 以变量的方式提供了部分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 基于维特比算法来优化上述流程

此项目需要的数据:

  1. 综合类中文词库.xlsx: 包含了中文词,当做词典来用
  2. 以变量的方式提供了部分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
第一个方法: 时间复杂度= O(DN) O(D^N) , 空间复杂度= O(DN) O(D*N)

第二个方法: 时间复杂度= O(nD2) O(nD^2), 空间复杂度= O(D) O(D)

TODO:如果把上述的分词工具持续优化,有哪些可以考虑的方法? (至少列出3点)

    1. (例), 目前的概率是不完整的,可以考虑大量的语料库,然后从中计算出每一个词出现的概率,这样更加真实
    1. 概率太低的词可以不用记录,节约空间
    1. 隐马尔可夫不止基于前一个词,而是基于前几个词
    1. 对概率进行转换,保证相加为1