1、词典1谢谢观赏2019-8-28词典与词典编撰的研究n词典学lexicologynTheory and description of lexical informationn计算词典学computational lexicologynformal modelling of lexical informationn词典编撰学lexicographynConstruction of dictionaries(databases,handbooks)n计算词典编撰学computational lexicographynconstruction and production of dictionari
2、es using electronic publishing2谢谢观赏2019-8-28机读词典与人读词典n人读词典（Human Readable Dictionary）n格式不规范n数据完整性和一致性不好n非结构化n机读词典（Machine Readable Dictionary）n格式规范n数据完整性和一致性较好n结构化3谢谢观赏2019-8-28机读词典的分类n按信息类型分类n语法词典n语义词典（包括同义词典）n双语词典nn按领域分类n通用词典n专业词典（术语词典）n专名词典n4谢谢观赏2019-8-28人读词典（demo）n金山词霸story中古英语storie 古法语estoire
3、拉丁语historian-ries(1)故事，小说；传闻；轶事Please read us a story!请给我们读个故事！(2)谎话，假话(3)（书籍、电影、戏剧等的）情节(4)（报刊、杂志文章的）素材，题材5谢谢观赏2019-8-28汉语语法信息词典n开发单位：北京大学计算语言学研究所n参考文献：n俞士汶等（1998）现代汉语语法信息词典详解，清华大学出版社、广西科学技术出版社1998年版。n规模：7万多词条n总库n词性库名词时间词处所词方位词数词量词区别词代词动词形容词状态词副词介词连词助词语气词前接成分后接成分成语简称略语习用语语素标点符号n词性分库动词代词6谢谢观赏2019-8-2
4、8新华社词语数据库n全库分为中文和外文两个大类，主要包括中文新闻库、经济信息库、证券库、人物库、组织机构库、专题资料库等中文数据库，还包括Xinhua News Bulletin、Whos Who in China等英文数据库。共有28个库100多个子库，数据量达80多亿汉字，并以日均150万汉字的速度增长。7谢谢观赏2019-8-28新华社词语数据库国际组织n“年问题”联合委员会/joint year 2000 council/Internationaln“”运动/movement april 19/Colombian“阿尔法”/alpha 66/Cuban“俄罗斯地区”社会联盟/regio
5、ns of russia group/Russian“法中年”协会/france-china association for the year 2000/Francen“繁荣”党/prosperity/Russian“光明的日本”国会议员联盟/parliamentary union for a bright japan/Japann“基地”组织/al qaeda/Saudi Arabian财富杂志/fortune/USAn朝日新闻/asahi shimbun/Japann国际献血组织联合会/international federation of blood donor organization
6、s/Internationaln国际宪法学协会/international association of constitutional law/Internationaln国际香料集团/international spice group/Internationaln经济和外贸部/ministry of economy and external trade of syria/Syrian经济和外贸部/ministry of economy and foreign trade of egypt/Egypt8谢谢观赏2019-8-28知网（Hownet）1n作者：董振东董强n网站：http:/n概念
7、描述举例NO.=017144W_C=打G_C=VE_C=网球，牌，秋千，太极，球得很棒W_E=playG_E=VE_E=DEF=exercise|锻练,sport|体育n其中DEF是核心，采用特定的“知识描述语言”9谢谢观赏2019-8-28知网（Hownet）2n打 017144 exercise|锻练,sport|体育n男人 059349 human|人,family|家,male|男n高兴 029542 aValue|属性值,circumstances|境况,happy|福,desired|良n生日 072280 time|时间,day|日,ComeToWorld|问世,$congrat
8、ulate|祝贺n写信 089834 write|写,ContentProduct=letter|信件n北京 003815 place|地方,capital|国都,ProperName|专,(China|中国)n爱好者 000363 human|人,*FondOf|喜欢,#WhileAway|消闲n必须 004932 modality|语气n串 015204 NounUnit|名量,&(grape|葡萄),&(key|钥匙)n从良 016251 cease|停做,content=(prostitution|卖淫)n打对折 017317 subtract|削减,patient=price|价格,
9、commercial|商,(range|幅度=50%)n儿童基金会 024083 part|部件,%institution|机构,politics|政,#young|幼,#fund|资金,(institution|机构=UN|联合国)10谢谢观赏2019-8-28知网（Hownet）3n义原总数：1500多个n义原分类：共8类n基本义原n事件、实体、次要特征n属性、属性值、数量、数量值n语法义原：描述语法特征，如POSn语法n关系义原：描述意义关系，类似于格关系n动态角色n动态属性11谢谢观赏2019-8-28知网（Hownet）4n义原的上下位关系构成树结构-entity|实体 thing|
10、万物 physical|物质 animate|生物 AnimalHuman|动物 human|人 humanized|拟人 animal|兽 beast|走兽 12谢谢观赏2019-8-28知网（Hownet）513谢谢观赏2019-8-28同义词词林1n梅家驹等，1983，上海辞书出版社n为克服写作和翻译时的词穷现象而编写n目前广泛应用于自然语言处理中n收词近7万（按义项统计）n按义项编排n12大类n94中类n1428小类n3925词群n词群内部的词是同义词n大类、中类、小类之间不一定是上下位关系（有些是领域）14谢谢观赏2019-8-28同义词词林2Ag100101旅客Ag100101客人
11、Ag100101旅人Ag100101客子Ag100101客行子Ag100101游子Ag100101行人Ag100101行者Ag100101行旅Ag100101行客Ag100101行子Ag100101征人Ag100101征夫Ag100101征客Ag100101羁客Ag100101羁旅Ag100101客Ag100102过路人Ag100102过客Ag100103游人Ag100103游客Ag100103游者Ag100103旅游者Ag100103观光者大类：A中类：g小类：10词群：01最小同义词集：01，02，0315谢谢观赏2019-8-28WordNet 1n网址：n开发单位：n普林斯顿大学心理语
12、言学实验室n初衷是作为研究人类词汇记忆的心理语言学成果n在自然语言处理中得到广泛的应用n免费的在线词汇数据库n世界很多语种都开发了相应的版本n各种欧洲语言：EuroNetn汉语：CCD（Chinese Concept Dictioanry）16谢谢观赏2019-8-28WordNet 2n同义词集Synsetn用一组同义词的集合Synset来表示一个概念n每一个概念有一段描述性的说明n关系n上下位关系（hyponymy，troponymy）n同义反义关系（synonymy，antonymy）n部分整体关系（entailment，meronymy）n17谢谢观赏2019-8-28Wordnet
13、3n规模n名词：80,000 words,60,000 synsetsn形容词：16,000 synsetsn动词：11,500 synsetsn还在不断发展之中18谢谢观赏2019-8-28WordNet 4名词概念的组织19谢谢观赏2019-8-28WordNet 5形容词概念的组织20谢谢观赏2019-8-28词典检索算法1n词典检索算法的性能评价n时间复杂度n空间复杂度n检索方式n直接用词语检索n检索句子中某个位置开始的所有词n检索句子中某个位置开始的最长词n模糊检索nn增量式索引21谢谢观赏2019-8-28词典检索算法2n两个问题n索引结构n查找算法n一种索引结构可以对应不同的查找
14、算法22谢谢观赏2019-8-28词典顺序索引23谢谢观赏2019-8-28词典顺序索引的查找算法n整词二分查找n时间复杂度O(log2N)n无法按前缀查找n改进的整词二分查找n时间复杂度O(log2N)n可以实现按前缀查找24谢谢观赏2019-8-28词典散列索引25谢谢观赏2019-8-28词典散列索引的检索算法n利用散列（hash）函数直接定位n效率高：常数n不能按前缀查找n冲突的解决n使用冲突队列n使用再散列n散列函数（hash）的选择n算法改进：逐词散列，可以实现按前缀查找26谢谢观赏2019-8-28词典分级索引n将词语分成若干部分，为每一部分分别建立索引n在分级索引中，每一级索引
15、都可以采用各种不同的索引和查找算法n对于汉语而言，第一级索引一般使用词语的首字，所以又常称为首字索引n汉语的首字数量有限，可以使用直接定位法，效率最高，空间也不大27谢谢观赏2019-8-28汉语词典按首字顺序索引28谢谢观赏2019-8-28首字二分检索2n时间复杂度：O(log2N）n空间复杂度：O(N)n可以按前缀查找n不能增量式索引：每次要重新排序29谢谢观赏2019-8-28汉语词典TRIE树索引30谢谢观赏2019-8-28AC算法1n问题n假设词典中有两个词：aba，abcdn考虑输入串：bababcdabn如何迅速找出输入串中词典词的所有出现？n简单解决办法n逐字查词典：效率太
16、低nAC算法n将词典构造成一个自动机，一次扫描完成31谢谢观赏2019-8-28AC算法232谢谢观赏2019-8-28AC算法333谢谢观赏2019-8-28AC算法434谢谢观赏2019-8-28AC算法535谢谢观赏2019-8-28AC算法636谢谢观赏2019-8-28AC算法737谢谢观赏2019-8-28AC算法838谢谢观赏2019-8-28AC算法939谢谢观赏2019-8-28AC算法1040谢谢观赏2019-8-28重复子串识别n目标：识别出文本中所有出现两次以上的子串n据香港文汇报报道，北京的台湾问题专家李家泉受访时指出，台北、高雄两市市长选举，尽管蓝、绿两政治势力进行
17、了激烈的斗争，但“北蓝南绿”的政治格局未被打破，由此可以预见，未来一段时间内两岸关系的改善很难有突破。李家泉指出，此次北高两市选举在两个大背景下进行，一是民进党执政两年来政绩相当差，自身危机感非常强；二是距离2004年“大选”只有一年多时间，两派都格外重视此次交锋，对泛绿阵营来说是政权保卫战，而对泛蓝阵营来说则是夺权演习战。因此可以看到斗争形势相当严峻而激烈。41谢谢观赏2019-8-28逐词递增算法1n首先记录所有二字串的出现位置和频度n删除只出现一次的二字串记录n对于出现两次以上的二字串，向后扩展一个字，记录所有三字串的出现位置和频度n删除只出现一次的三字串n重复上述过程，直到不再有重复串
18、为止42谢谢观赏2019-8-28逐词递增算法2n性能n最坏情况：前后两段文字完全相同n在最坏情况下，时间复杂度：O(n2)n算法改进n时间复杂度可以达到O(n)？n演示43谢谢观赏2019-8-28基于重复子串的新词发现n对于人民日报2002年和2001年语料分别进行重复子串识别n用2002年的重复子串集合减去2001年的重复子串集合n2002年出现词数大于20的词语而2001年没有出现过的重复子串：1005个nTop 1044谢谢观赏2019-8-28复习思考题n如果有一部人读的双语词典，你如何将它转换成机读词典？n如何利用语义词典进行词语相似度计算？n请实现逐字散列的词典检索算法。n汉语词典和英语词典在实现上有什么不同？n请查找文献，看看如何寻找一个好的散列函数。45谢谢观赏2019-8-28
