学位论文 > 优秀研究生学位论文题录展示

基于K最短路径的中文分词算法研究与实现

作　者: 李兆福
导　师: 张国印
学　校: 哈尔滨工程大学
专　业: 计算机应用技术
关键词: 分词歧义识别未登录词识别 N-最短路径 S-EK最短路径
分类号: TP301.6
类　型: 硕士论文
年　份: 2009年
下　载: 461次
引　用: 7次
阅　读: 论文下载

内容摘要

中文分词处于词法、句法、语义等语言层次的最底层。它是中文自然语言处理的一项基础性工作,也是中文信息处理领域的一项基础性课题,它是搜索引擎、自动翻译、语音识别、信息检索、自动分类、自动文摘、文本的自动校对以及数据挖掘等技术的重要组成部分,是直接影响中文信息处理技术发展的技术瓶颈。本文首先阐述了中文分词的研究背景与意义,对中文分词的国内外研究现状进行了分析,详细讲述了基于字符串匹配、统计和理解的三种典型中文分词方法,并对每种方法的优缺点进行了简要的概括,分析了几种中文分词相关的算法模型,并在分词规范、歧义识别、未登录词识别等方面总结了阻碍中文分词发展的几种主要技术难题。然后,本文对中科院汉语词法分析系统ICTCLAS的N-最短路径粗分模型算法进行了分析研究,并对该系统所生成的特殊有向图的特点和存储结构进行了描述。本文基于该中文分词系统生成的有向图,提出了S-EK最短路径算法模型,同时对该算法时间复杂度进行了分析。本文最后对S-EK最短路径算法与N-最短路径算法、Dijkstra算法在时间复杂度方面进行了对比分析,并给出了一个详细的S-EK最短路径算法求解实例。本算法采用通过局部求解重要节点集合而得到整个有向图的K最短路径的方案,降低了算法时间复杂度,并通过仿真实验进行了验证。

全文目录

摘要  5-6
Abstract  6-10
第1章绪论  10-18
  1.1 研究背景与意义  10-12
    1.1.1 研究背景  10-11
    1.1.2 研究意义  11-12
  1.2 中文分词的研究现状  12-15
  1.3 中文分词的应用  15
  1.4 论文研究内容与组织结构  15-18
    1.4.1 论文的研究内容  15-16
    1.4.2 论文的组织结构  16-18
第2章中文分词方法研究  18-28
  2.1 中文分词的主要方法  18-22
    2.1.1 基于字符串匹配的方法  18-20
    2.1.2 基于统计的分词方法  20-21
    2.1.3 基于理解分词的方法  21-22
  2.2 中文分词的路径算法模型  22-25
    2.2.1 Dijkstra算法模型  22-23
    2.2.2 Floyd算法模型  23-24
    2.2.3 N-最短路径算法模型  24-25
  2.3 中文分词的技术难点  25-27
    2.3.1 分词规范  25-26
    2.3.2 歧义识别  26
    2.3.3 未登录词识别  26-27
  2.4 本章小结  27-28
第3章 S-EK图与求解算法模型  28-45
  3.1 S-EK最短路径图  28-31
    3.1.1 S-EK图的特点  28-29
    3.1.2 S-EK图的实例  29-30
    3.1.3 S-EK图的特例  30-31
    3.1.4 S-EK图节点存储数据结构  31
  3.2 S-EK最短路径算法  31-35
    3.2.1 S-EK最短路径算法相关定义  32-33
    3.2.2 S-EK最短路径算法模型  33-35
  3.3 算法时间复杂度分析  35-38
    3.3.1 AIPS算法时间复杂度  36-37
    3.3.2 ACS算法时间复杂度  37-38
    3.3.3 S-EK最短路径算法时间复杂度  38
  3.4 S-EK最短路径算法求解实例  38-44
  3.5 本章小结  44-45
第4章 S-EK最短路径算法实现及实验结果分析  45-55
  4.1 S-EK最短路径算法实现  45-46
  4.2 实验设计及结果  46-52
    4.2.1 实验设计  46-47
    4.2.2 实验结果  47-52
  4.3 实验结论  52-54
  4.4 本章小结  54-55
结论  55-56
参考文献  56-59
攻读硕士学位期间发表的论文和取得的科研成果  59-60
附录A S-EK最短路径算法部分代码  60-65
致谢  65

基于K最短路径的中文分词算法研究与实现

内容摘要

全文目录

相似论文