词典与词典编撰的研究.ppt

AC算法1 问题 假设词典中有两个词：aba，abcd 考虑输入串：bababcdab 如何迅速找出输入串中词典词的所有出现？ 简单解决办法 逐字查词典：效率太低 AC算法 将词典构造成一个自动机，一次扫描完成 AC算法2 AC算法3 AC算法4 AC算法5 AC算法6 AC算法7 AC算法8 AC算法9 AC算法10 重复子串识别 目标：识别出文本中所有出现两次以上的子串 据香港《文汇报》报道，北京的台湾问题专家李家泉受访时指出，台北、高雄两市市长选举，尽管蓝、绿两政治势力进行了激烈的斗争，但“北蓝南绿”的政治格局未被打破，由此可以预见，未来一段时间内两岸关系的改善很难有突破。李家泉指出，此次北高两市选举在两个大背景下进行，一是民进党执政两年来政绩相当差，自身危机感非常强；二是距离2004年“大选”只有一年多时间，两派都格外重视此次交锋，对泛绿阵营来说是政权保卫战，而对泛蓝阵营来说则是夺权演习战。因此可以看到斗争形势相当严峻而激烈。 逐词递增算法1 首先记录所有二字串的出现位置和频度 删除只出现一次的二字串记录 对于出现两次以上的二字串，向后扩展一个字，记录所有三字串的出现位置和频度 删除只出现一次的三字串 重复上述过程，直到不再有重复串为止 逐词递增算法2 性能 最坏情况：前后两段文字完全相同 在最坏情况下，时间复杂度：O(n2) 算法改进 时间复杂度可以达到O(n)？ 演示 基于重复子串的新词发现 对于《人民日报》2002年和2001年语料分别进行重复子串识别 用2002年的重复子串集合减去2001年的重复子串集合 2002年出现词数大于20的词语而2001年没有出现过的重复子串：1005个 Top 10 复习思考题 如果有一部人读的双语词典，你如何将它转换成机读词典？ 如何利用语义词典进行词语相似度计算？ 请实现逐字散列的词典检索算法。 汉语词典和英语词典在实现上有什么不同？ 请查找文献，看看如何寻找一个好的散列函数。 词典 词典与词典编撰的研究 词典学lexicology Theory and description of lexical information 计算词典学computational lexicology formal modelling of lexical information 词典编撰学lexicography Construction of dictionaries (databases, handbooks) 计算词典编撰学computational lexicography construction and production of dictionaries using electronic publishing 机读词典与人读词典 人读词典（Human Readable Dictionary） 格式不规范 数据完整性和一致性不好 非结构化 机读词典（Machine Readable Dictionary） 格式规范 数据完整性和一致性较好 结构化 机读词典的分类 按信息类型分类 语法词典 语义词典（包括同义词典） 双语词典 …… 按领域分类 通用词典 专业词典（术语词典） 专名词典 …… 人读词典（demo） 金山词霸 story 中古英语storie 古法语estoire 拉丁语historia n -ries (1)故事，小说；传闻； 轶事 Please read us a story! 请给我们读个故事！ (2) 谎话，假话 (3)（书籍、电影、戏剧等的）情节 (4)（报刊、杂志文章的）素材，题材 汉语语法信息词典 开发单位：北京大学计算语言学研究所 参考文献： 俞士汶等（1998）《现代汉语语法信息词典详解》，清华大学出版社、广西科学技术出版社1998年版。 规模：7万多词条 总库 词性库 名词时间词处所词方位词数词量词区别词代词动词形容词状态词副词介词连词助词语气词前接成分后接成分成语简称略语习用语语素标点符号 词性分库 动词代词 新华社词语数据库 全库分为中文和外文两个大类，主要包括中文新闻库、经济信息库、证券库、人物库、组织机构库、专题资料库等中文数据库，还包括Xinhua News Bulletin 、Who’s Who in China等英文数据库。共有28个库100多个子库，数据量达80多亿汉字，并以日均150万汉字的速度增长。 新华社词语数据库·国际组织 “２０００年问题”联合委员会/joint year 2000 council/ International “４·１９”运动/movement april 19/ Colombia “阿尔法６６” /alpha 66/ Cuba “俄罗斯地区”社会联盟/regions of russia group/ Russ