计算语言学讲义(02)词典

计算语言学讲义(02)词典

计算语言学第二讲词典刘群中国科学院计算技术研究所liuqun@ict.ac.cn中国科学院研究生院2002~2003学年第二学期课程讲义\n词典与词典编撰的研究•词典学lexicology–Theoryanddescriptionoflexicalinformation•计算词典学computationallexicology–formalmodellingoflexicalinformation•词典编撰学lexicography–Constructionofdictionaries(databases,handbooks)•计算词典编撰学computationallexicography–constructionandproductionofdictionariesusingelectronicpublishing中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n机读词典与人读词典•人读词典（HumanReadableDictionary）–格式不规范–数据完整性和一致性不好–非结构化•机读词典（MachineReadableDictionary）–格式规范–数据完整性和一致性较好–结构化中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n人读词典（demo）•金山词霸story中古英语storie<古法语estoire<拉丁语historian-ries(1)故事，小说；传闻；轶事Pleasereadusastory!请给我们读个故事！(2)谎话，假话(3)（书籍、电影、戏剧等的）情节(4)（报刊、杂志文章的）素材，题材中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n机读词典的分类•按信息类型分类–语法词典–语义词典（包括同义词典）–双语词典–……•按领域分类–通用词典–专业词典（术语词典）–专名词典–……中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n汉语语法信息词典•开发单位：北京大学计算语言学研究所•参考文献：–俞士汶等（1998）《现代汉语语法信息词典详解》，清华大学出版社、广西科学技术出版社1998年版。•规模：7万多词条–总库–词性库名词时间词处所词方位词数词量词区别词代词动词形容词状态词副词介词连词助词语气词前接成分后接成分成语简称略语习用语语素标点符号–词性分库动词代词中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n汉语语法信息词典·总库中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n汉语语法信息词典·动词库中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n汉语语法信息词典·谓宾动词分库中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n新华社词语数据库全库分为中文和外文两个大类，主要包括中文新闻库、经济信息库、证券库、人物库、组织机构库、专题资料库等中文数据库，还包括XinhuaNewsBulletin、Who’sWhoinChina等英文数据库。共有28个库100多个子库，数据量达80多亿汉字，并以日均150万汉字的速度增长。中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n新华社词语数据库·国际组织•“２０００年问题”联合委员会/jointyear2000council/International•“４·１９”运动/movementapril19/Colombia•“阿尔法６６”/"alpha66"/Cuba•“俄罗斯地区”社会联盟/regionsofrussiagroup/Russia•“法中－２０００年”协会/france-chinaassociationfortheyear2000/France•“繁荣”党/prosperity/Russia•“光明的日本”国会议员联盟/parliamentaryunionforabrightjapan/Japan•“基地”组织/alqaeda/SaudiArabia•《财富》杂志/fortune/USA•《朝日新闻》/asahishimbun/Japan•国际献血组织联合会/internationalfederationofblooddonororganizations/International•国际宪法学协会/internationalassociationofconstitutionallaw/International•国际香料集团/internationalspicegroup/International•经济和外贸部/ministryofeconomyandexternaltradeofsyria/Syria•经济和外贸部/ministryofeconomyandforeigntradeofegypt/Egypt中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n新华社词语数据库·人名中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n知网（Hownet）1•作者：董振东董强•网站：http://www.keenage.com•概念描述举例NO.=017144W_C=打G_C=VE_C=~网球，~牌，~秋千，~太极，球~得很棒W_E=playG_E=VE_E=DEF=exercise|锻练,sport|体育•其中DEF是核心，采用特定的“知识描述语言”中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n知网（Hownet）2打017144exercise|锻练,sport|体育男人059349human|人,family|家,male|男高兴029542aValue|属性值,circumstances|境况,happy|福,desired|良生日072280time|时间,day|日,@ComeToWorld|问世,$congratulate|祝贺写信089834write|写,ContentProduct=letter|信件北京003815place|地方,capital|国都,ProperName|专,(China|中国)爱好者000363human|人,*FondOf|喜欢,#WhileAway|消闲必须004932{modality|语气}串015204NounUnit|名量,&(grape|葡萄),&(key|钥匙)从良016251cease|停做,content=(prostitution|卖淫)subtract|削减,patient=price|价格,commercial|商,(range|幅度打对折017317=50%)儿童基part|部件,%institution|机构,politics|政,#young|幼,#fund|资024083金会金,(institution|机构=UN|联合国)中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n知网（Hownet）3•义原总数：1500多个•义原分类：共8类–基本义原•事件、实体、次要特征•属性、属性值、数量、数量值–语法义原：描述语法特征，如POS•语法–关系义原：描述意义关系，类似于格关系•动态角色•动态属性中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n知网（Hownet）4义原的上下位关系构成树结构-entity|实体├thing|万物…├physical|物质…├animate|生物…├AnimalHuman|动物…├human|人│└humanized|拟人└animal|兽├beast|走兽…中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n知网（Hownet）5知网中的关系中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n同义词词林1•梅家驹等，1983，上海辞书出版社•为克服写作和翻译时的词穷现象而编写•目前广泛应用于自然语言处理中•收词近7万（按义项统计）•按义项编排–12大类–94中类–1428小类–3925词群–词群内部的词是同义词–大类、中类、小类之间不一定是上下位关系（有些是领域）中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n同义词词林2Ag100101旅客Ag100101客人Ag100101旅人Ag100101客子大类：AAg100101客行子Ag100101游子Ag100101行人中类：gAg100101行者Ag100101行旅Ag100101行客小类：10Ag100101行子Ag100101征人词群：01Ag100101征夫Ag100101征客Ag100101羁客最小同义词集：01，02，03Ag100101羁旅Ag100101客Ag100102过路人Ag100102过客Ag100103游人Ag100103游客Ag100103游者Ag100103旅游者Ag100103观光者中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\nWordNet1•网址：–http://www.cogsci.princeton.edu/~wn/•开发单位：–普林斯顿大学心理语言学实验室–初衷是作为研究人类词汇记忆的心理语言学成果–在自然语言处理中得到广泛的应用•免费的在线词汇数据库•世界很多语种都开发了相应的版本–各种欧洲语言：EuroNet–汉语：CCD（ChineseConceptDictioanry）中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\nWordNet2•同义词集Synset–用一组同义词的集合Synset来表示一个概念–每一个概念有一段描述性的说明•关系–上下位关系（hyponymy，troponymy）–同义反义关系（synonymy，antonymy）–部分整体关系（entailment，meronymy）–……中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\nWordnet3•规模–名词：80,000words,60,000synsets–形容词：16,000synsets–动词：11,500synsets–还在不断发展之中中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\nWordNet4名词概念的组织：中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\nWordNet5形容词概念的组织：中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\nWordNet6中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\nWordNet7中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n词典检索算法1•词典检索算法的性能评价–时间复杂度–空间复杂度–检索方式•直接用词语检索•检索句子中某个位置开始的所有词•检索句子中某个位置开始的最长词•模糊检索•……–增量式索引中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n词典检索算法2•两个问题–索引结构–查找算法•一种索引结构可以对应不同的查找算法中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n词典顺序索引词索引表词典正文指针·······……···……··词典正文啊啊哈啊呀啊哟啊唷阿阿Q……酣睡•索引结构简单，占用空间小•不能实现增量式索引：每增加一个词需重新排序中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n词典顺序索引的查找算法•整词二分查找–时间复杂度O(logN)2–无法按前缀查找•改进的整词二分查找–时间复杂度O(logN)2–可以实现按前缀查找中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n词典散列索引词索引表词典正文指针·······……···……··词典正文啊啊哈啊呀啊哟啊唷阿阿Q……酣睡•索引结构简单，占用空间小（比顺序索引稍大）•可以实现增量式索引中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n词典散列索引的检索算法•利用散列（hash）函数直接定位•效率高：常数•不能按前缀查找•冲突的解决–使用冲突队列–使用再散列•散列函数（hash）的选择•算法改进：逐词散列，可以实现按前缀查找中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n词典分级索引•将词语分成若干部分，为每一部分分别建立索引•在分级索引中，每一级索引都可以采用各种不同的索引和查找算法•对于汉语而言，第一级索引一般使用词语的首字，所以又常称为首字索引•汉语的首字数量有限，可以使用直接定位法，效率最高，空间也不大中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n汉语词典按首字顺序索引首字表啊阿……大……鼾齄首字词数005089……794……002000第一项指针··……·……··词索引表词典正文指针·······……···……··词典正文啊啊哈啊呀啊哟啊唷阿阿Q……酣睡中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n首字二分检索2•时间复杂度：O(logN）2•空间复杂度：O(N)•可以按前缀查找•不能增量式索引：每次要重新排序中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n汉语词典TRIE树索引首字表啊阿……大……鼾齄首字词数005089……794……002000第一项指针··……·……··关键字^案把坝白……“大”字的声睡“鼾”字的子树大小02205……TRIE索引树00TRIE索引树子树指针·····……··^要^菜话鼠天0002205·······案0·中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\nAC算法1•问题–假设词典中有两个词：aba，abcd–考虑输入串：bababcdab–如何迅速找出输入串中词典词的所有出现？•简单解决办法–逐字查词典：效率太低•AC算法–将词典构造成一个自动机，一次扫描完成中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\nAC算法20abaaabcd1空边对应所有b不匹配的字符b2ca35d4中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\nAC算法3bababcdab0aaba1babcdb2bcaa35d4中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\nAC算法4bababcdab0aaba1babcdb2bcaa35d4中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\nAC算法5bababcdab0aaba1babcdb2bcaa35d4中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\nAC算法5bababcdab0aaba1abcdbb返回单词aba2bcaa35d4中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\nAC算法6bababcdab0aaba1babcdb2bcaa35d4中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\nAC算法7bababcdab0aaba1babcdb2bcaa35d4中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\nAC算法8bababcdab0aaba1babcdb返回单词abcd2bcaa35d4中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\nAC算法9bababcdab0aaba1babcdb2bcaa35d4中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n重复子串识别目标：识别出文本中所有出现两次以上的子串据香港《文汇报》报道，北京的台湾问题专家李家泉受访时指出，台北、高雄两市市长选举，尽管蓝、绿两政治势力进行了激烈的斗争，但“北蓝南绿”的政治格局未被打破，由此可以预见，未来一段时间内两岸关系的改善很难有突破。李家泉指出，此次北高两市选举在两个大背景下进行，一是民进党执政两年来政绩相当差，自身危机感非常强；二是距离2004年“大选”只有一年多时间，两派都格外重视此次交锋，对泛绿阵营来说是政权保卫战，而对泛蓝阵营来说则是夺权演习战。因此可以看到斗争形势相当严峻而激烈。中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n逐词递增算法1•首先记录所有二字串的出现位置和频度•删除只出现一次的二字串记录•对于出现两次以上的二字串，向后扩展一个字，记录所有三字串的出现位置和频度•删除只出现一次的三字串•重复上述过程，直到不再有重复串为止中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n逐词递增算法2•性能–最坏情况：前后两段文字完全相同–在最坏情况下，时间复杂度：O(n2)•算法改进–时间复杂度可以达到O(n)？•演示中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n基于重复子串的新词发现•对于《人民日报》2002年和2001年语料分别进行重复子串识别•用2002年的重复子串集合减去2001年的重复子串集合•2002年出现词数大于20的词语而2001年没有出现过的重复子串：1005个•Top10十六大精神1289中共十六大342学习贯彻十六大精神238核查人员223干部任用条例220建设中国特色社会主义194一边一国189贯彻十六大精神156胡锦涛当选为中共中央总书记155军品出口151中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学\n复习思考题•如果有一部人读的双语词典，你如何将它转换成机读词典？•如何利用语义词典进行词语相似度计算？•请实现逐字散列的词典检索算法。•汉语词典和英语词典在实现上有什么不同？•请查找文献，看看如何寻找一个好的散列函数。中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学