一种改进的中文分词算法

一种改进的中文分词算法 祁文青 () 黄石理工学院计算机学院 ,湖北 黄石 435003 摘 要 :汉语自动分词是汉语信息处理的前提 ,词库是汉语自动分词的基础 。文章提出了一种在对词库进行改 造的基础上改进的匹配算法 ,突破了最大匹配分词算法分词的长度限制 ,提高了中文分词的速度和效率 。 关键词 :中文信息处理 ; 中文分词 ; 最大匹配法分词算法 文献标识码 : A中图分类号 : TP30116 An Im proved M ax im um M a tch ing M ethod for Ch inese W ord Segm en ta tion Q i W enqing ( )Schoo l of Comp u te r Sc ience, Huangsh i In stitu te of Techno logy, H uangsh i H ube i 435003 Abstrac t: Ch inese wo rd segm enta tion is the p repa ra tion fo r Ch inese info rm a tion p roce ssing. The d ic tiona ry m echan ism is a ba sic componen t of Chinese wo rd segmen ta tion system s. In th is p ape r, the autho r pu ts fo rwa rd an imp roved M axim um M a tching M e thod fo r Ch ine se W o rd Segm entation on a new d ic tiona ry mechanism compa red w ith existing typ ical d ic tion2 a ry m echan ism s, wh ich imp roves the speed and effic iency of Ch ine se wo rd segmen ta tion system s. Key words: Chine se info rm a tion p rocessing; Chine se wo rd segm entation; M axim um M a tch ing M e thod fo r Ch inese W o rd Segmen ta tion 111 理解式切分法 理解式切分法其分 词 系 统 由 词 库 、知 识 库 和 推 0 引言 理机部分组成 。词库中存放 词 条 ; 知 识 库 中 存 放 形 式化的语言规则 、语法知识 以及 语 言 学 家 在 分 词 过中文分词技术属于 自 然 语 言 处 理 技 术 范 畴 , 对 于一句 话 , 人 可 以 通 过 自 己 的 知 识 来 明 白 哪 些 是 程中进行推理判断的常识 和 经 验 ; 推 理 机 制 利 用 词 词 , 哪些不 是 词 , 但 如 何 让 计 算 机 也 能 理 解 ? 其 处 库和知识库提供的大量数 据 与 知 识 , 模 拟 语 言 学 家 理过程就 是 分 词 算 法 。汉 语 文 本 中 含 有 许 多 歧 义 的逻辑思维过程 , 实现自 动 分词 。这 实 际 上 是 一 个 字段 , 句中某个片段存在两 种 或 两 种以 上 的 切 分 形 自动分词的专家系统 。这种 系 统 开 销 很 大 , 除 了 理 式 。 论上的困难 外 , 还 存 在 系 统 复 杂 度 的 问 题 , 实 现 困 难 。 112 机械匹配法 1 传统中文分词算法 机械匹 配 算 法 主 要 基 于 字 符 串 匹 配 的 原 理 。 在匹配时不 进 行 语 法 分 析 , 也 不 进 行 语 义 分 析 , 只 , 人们己经提出了许 多 计 算 机 自 动 切 分 词 算 法 是机械地匹配比较 。即它以 足 够 大 的 词 库 为 依 据 , (这些算法大致 可 分 为 两 类 : 理 解 式 切 分 法 或 称 知 采用一定的 处 理 策 略 将 文 本 中 的 字 串 与 词 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 中 的 ) () 识分词法 和机械匹配法 或形态分词法 。 词逐一匹 配 , 若 成 功 , 则 认 定 该 串 为 词 。常 用 分 词 收稿日期 : 2007 - 04 - 10 ( ) 作者简介 :祁文青 1968— ,女 ,湖北省黄石人 ,副教授 ,硕士 。 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 有正向 最 大 匹 配 法 、逆 向 最 大 匹 配 法 、最 少 切 , 会把词库 中所 有 的 首 字 都 取 出 多 。尤其是第一层 [ 1 - 4 ] 来 作 为 根 节 点 的 子 节 点 , 这 意 味 着 如 果 首 字 有 分法 。机械分词法中常用的的最大匹配分词算 4 0 0 0 个的话 , 根节 点 就 有 4 0 0 0 个 儿 子 。当 然 随 着 法易于实现 , 但是存在很多明显的缺陷 : 第一 , 长度 树层数的增多 , 节点的儿子数也会减少 , 毕 竟 以“感 限制 , 由于最大匹配法必须 首 先 设 定一 个 匹 配 词 长 冒 ”开头的词在整个词库也只有四十多个 , 而以“感 的初始值 , 词 长 过 长 , 效 率 就 比 较 低 ; 词 长 过 短 , 长 冒清 ”开头的词则只有两三个了 。这 意 味 着如 果 设 词就会被 切 错 。第 二 , 效 率 低 , 即 使 可 以 将 字 长 设 计得不 合 理 , 树 的 匹 配 遍 历 过 程 并 不 完 全 是 线 性 成相当 短 , 例 如 词 长 为 5 , 当 我 们 的 大 数 词 长 为 2 时 , 至少有 3 次 的 匹 配 算 法 是 浪 费 掉 的 。第 三 , 最 大匹配的并不一定是想要 的 分词 方 式 , 最 大 匹 配 法 ) ( ) ( 的 。最 坏 的 查 找 算 法 是 O N N 代 表 儿 子 数 。 基于的理念是找到最大的 匹 配词 , 但有 的 时 候 除 了 当然如果建词库时将儿子 有 序 排 列 , 再 按 照 二 分 查 最大匹配词外 , 也可能只 需 要 这 个词 的 一 部 分 。基 ( ) 找的方法 , 则 我 们 的 复 杂 度 会 减 到 O logN , 这 样 于以上 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 , 提 出 改 进 的 解 决 方 案 , 使 分 词 算 法 的 的复杂度 已 经 可 以 接 受 了 。但 是 还 有 更 简 单 又 更 效率 、分词的长度限制甚至歧义处理上得到提高 。 快的存储方 式 , 那 就 是 哈 希 表 , 毕 竟 在 哈 希 表 里 查 找东西时它的效率几乎是 线 性 的 , 而 且 实 现 起 来 要 比二分查 询 简 单 得 多 。当 然 用 哈 希 表 要 付 出 存 储 空间变大的代价 , 但这样的 代价 来 换 取 速 度 与 简 单 性也是值得的 。找到有终结 符 的 字 后 , 必 须 要 将 它 2 改进的中文分词算法 建成一个完整的词 。这时必 须 能 从 字 个 往 上 回 溯 , 直到找到 根 结 点 。因 此 我 们 在 每 个 节 点 里 都 保 存 2 11 建立词库 了父节点的指针 。 为了使最大匹配法 分 词 算 法 在 效 率 、分 词 的 长 212 算法 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 思想 度限制甚至歧义处理上得 到 提高 , 必须 要 有 一 个 词 有了以上的中文词 库 后 , 再 来 看 一 下 分 词 的 步 库 , 将全文中的词与词库 去 匹 配 。这需 要 对 词 库 进 骤 : 行改造 , 使词库更适合用 于 匹 配 与分 词 。将 关 系 数( ) 1 首先将要分的全文按标点符号 打 散成 一 个据库的词按字打散 , 并存 放 到 层 次数 据 库 中 。以 下 一个的句子 。 就是一个层次词库示例 , 如图 1 所示 。 ( ) 2 开始将 要 处 理 的 句 子 在 树 状 结 构 中 遍 历 , 如果找到匹 配 的 就 继 续 , 如 果 遇 到 灰 色 的 终 止 符 , 我们就发现这个词是一个 完 整 的 词 了 , 这 样 就 可 以 把这个词作为一个分词了 。 ( ) ( ) 3 从分词后的下 一 字 开 始 继 续 做 步 骤 2 这 样的遍历 , 如此循环往复就将词分完了 。 可以看到 , 字符 匹 配 效 率 几 乎 是 线 性 的 。取 出 每一个字去树上找到相应 的 匹 配 , 每 次 的 匹 配 代 价 ) ( ) (都是 O 1 如 果 词 库 用 Hash 表 的 话 , 这 样 匹 配 下来的时 间 复 杂 度 就 是 字 符 串 本 身 的 长 度 。对 于 一个长度为 n 的字符串来 说 , 它 的 分 词 复 杂 度 是 O 2 ( ) ) ( n 。而最大 匹 配 的 平 均 复 杂 度 是 O n。当 然 这里没有考虑歧义包容与 分 支 处 理 等情 况 , 即 使 加 上这些复杂度仍然是有限的 。 当遇到分 支 时 , 会 分 解 成 两 条 路 线 , 例 如 当 匹 图 1 层 次 词 库 示 例 图 配到“感冒 ”的“冒 ”时 , 我 们 会 发 现 一个 终 止 符 , 代 灰色的 字 表 示 树 上 面 的 字 串 是 可 以 单 独 组 成 一个词的 , 例如“感冒 ”它本身是词库里可以找到的 词 , 所有灰色的表示的是 终 止 符 。而白 色 则 表 示 树 上面的字串是无法单独成词的 , 例如“感冒解 ”是不 ( ) 汇聚到一个点 , 变成一个分支 。例如 :“感 冒 解 毒胶 d ictNode . inU seCoun t ; 囊 可 以 治 感 冒 ”, 在 分 词 的 时 候 可 能 会 出 现“感 ( 2 Token cu rToken = new Token d ic tNode . get冒 ”,“解毒 ”,“感 冒 解 毒 ”,“感 冒 解 毒 胶 囊 ”等 多 ( ) TokenV a lue , 个分支 , 但是当我 们 到 达“囊 ”这 个 点 的 时 候 , 所 有 ( ) 1 - d ic tNode . token . sta rtO ffse t + po s + 的分支又会汇集到一起 , 因 为 接 下 来要 处 理 的 都 是 ( () ) ) getL evel , token . sta rtO ffse t + po s + 1 ; “可以治感冒 ”这 个 字 符 串 。如 果 有 办 法 在 汇 聚 以 后只处理一个分支 , 那么算 法 的 时 间复 杂 度 就 不 会 ( ) tokenQ ueue . offer cu rToken ; 象原来想象的那么坏 。 ( enqueueToken po s + 1 , d ic tNode . Emp ty _ 而这刚好利用动态 规 划 法 来 处 理 , 将 所 有 的 子 ) Node ; 问题 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 在 公 有 的 变 量 里 。当 遇 到 的 子 问 题 已 经 / /截完上一个词 , 开始截下一个词 被处理过一次了 , 就直接 跳 过 。这 样节 约 的 结 果 可 } 以使算法复杂度得到质的 改 变 , 当 然由 于 中 文 的 变 ( ) enqueueToken po s + 1 , d ictNode ; 化多端 , 无法精确估计使用 动 态 规 划法 后 算 法 复 杂 / /继续往下 , 看能不能组成更大的词 度得到了多大的提高 。下面是分词的核心算法 : } 它是一个递归的过 程 , 初 始 时 我 们 调 用 的 参 数 里 po s为 0 , 这 样 它 就 会 一 级 一 级 递 归 下 去 并 将 所 p riva te vo id ( enqueueToken in t po s, D ic tnode 有可能的分词放入到 tokenQ ueue 里 。 )p aren tNode 213 中文分词的实验结果{ 选择一 篇 2 0 0 0 字 的 文 章 , 然 后 根 据 两 种 算 法 ( ( ) ( ) ) if po s > = token. te rm Text . length 编写的分词器对它进行处 理 , 中 文 分 词 实 验 结 果 如 { / /如果长度超出了就表示分词结束 表 1 所示 。 re tu rn; } / / 用动态规划法 来 判 断 从 当 前 位 置 的 字 符 开 表 1 中文分词算法耗时表 始分词是否已经进行过了 分词算法 耗时 A na lyze r ( )(if ( isTokened po s && p aren tNode. getL evel 基于正向 ) = = 0 L ucene 80m s 最大匹配法 { Ch ine seA na lyze r 改进的分词算法 63m s re tu rn; } ( (由此可见 , 改进算法的分词 速 度 超 过 在网 上 找 ) if p a ren tNode. getL eve l = = 0 到的基于正向最大匹配法的 L ucene 分词器 。 { ( ) se tTokened po s ; } 3 结束语 ( ) String strP refix = token. te rmText . sub string ( ) po s , po s + 1 ; 改进的分词算法实 现 的 关 键 在 建 立 词 库 , 有 许 多的细节需要注意 。 ?首先 是 词 库 的 保 存 格 式 , 最 ( ) D ictNode d ic tNode = ge tD ictTree . 2 bu ildO r 简单 的 方 法 是 利用 java 的 se ria liza tion 的 功 能 , 把 整 ()Ge tSubNodes strP refix , p a ren tNode ; 个内存中的 树 状 结 构 直 接 序 列 化 成 磁 盘 的 文 本 文 ()if nu ll = = d ic tNode ()件 , 且读写的效率也会相当的高 。 下转第 3 7 页 { ( enqueueToken po s + 1 , D ic tNode . Emp ty_Node ) ; Connect U sing Tr_ t1 ; 对象 , 可 以 用 SQLCA 与 一 个 数 据 库 连 接 。在 创 建 事务对象前 , 应 考 虑 它 的 使 用 范 围 , 可 根 据 需 要 声 Connect U sing Tr_ t2 ; [ 3 ] 明为全局 对 象 或 实 例 对 象 。该 例 给 出 了 要 在 同 . . . . . . 如果需要访问多于 两 个 数 据 库 时 , 可 以 仿 照 以 的 数 据 grades 一个数据 窗 口 中 同 时 连 接 数 据 源 为 上方法 , 设计出同时访问多个不同数据库的程序 。 库和 SQL se rver数据库的程序代码 : Tran saction Tr_ t1 Tran saction Tr_ t2 4 结束语 / /建立事务对象 Tr_ t1 = C rea te Tran sac tion 综上所述 , 介 绍 了 多 个 数 据 库 之 间 自 动 连 接 , Tr_ t2 = C rea te Tran sac tion 限于篇 幅 , 对 其 他 一 些 次 要 的 内 容 不 再 讨 论 。程 / /给事务对象的属性赋值 序在 PB 8. 0 下调试通过 , 并在实际项目的设计 和 使 Tr_ t1. DBM S = " ODBC " 用中提高了软件开发效率和设计质量 。 Tr_ t1. A u toComm it = False 参 考 文 献 Tr_ t1. DB Pa rm = " ConnectString= ’D SN = grade s’ " Tr_ t2. DBM S = " M SS M icro soft SQL Se rve r 7. x" [ 1 ] 陈明 , 杨劲松. POW ERBU ILD ER 8. 0 高级编程技术 [M ]. 北京 : 希望电子出版社 , 2002 Tr_ t2. D ataba se = " studen t" 王 蓉. POW ERBU ILD ER 7. 0 应 用 开 发 技 术 详 解 Se rverN ame = " 1 9 2. Tr_ t2. 1 6 8. 3 1. 1 5 " [ 2 ] [M ]. 北京 : 电子工业出版社 , 2000 Tr_ t2. Log Id = " DBA " 网 冠 科 技. POW ERBU ILD ER 7. 0 时 尚 编 程 百 例 [ 3 ] Tr_ t2. A u toComm it = False [M ]. 北京 : 机械工业出版社 , 2001 DB Pa rm = " " Tr_ t2. / /建立数据库连接 (), 分词 算 法 的 种 类 很 多 , 到 底 哪 种 分 词 算 目前 上接第 2 5 页 法的准确度和效率更高 , 尚 无定 论 。对 于 任 何 一 个 ?树的父子节点的导航 。树 并不 是 一 颗 二 叉 树 , 父 成熟的分词系统来说 , 不可 能单 独 依 靠 某 一 种 算 法 亲的子节点会有好多 。尤其 是第 一 层 , 把 词 库 中 所 来实现 , 都需 要 综 合 不 同 的 算 法 , 需 要 多 种 算 法 来 有的首字都取出来作为根 节 点的 子 节 点 , 这 意 味 着处理不同的问题 。 如果首 字 有 4 0 0 0 个 的 话 , 根 节 点 就 有 4 0 0 0 个 儿 子 。当然随着树层数的增多 , 节 点 的儿 子 数 也 会 减 少 , 这意味着 如 果 设 计 得 不 合 理 , 树 的 匹 配 遍 历 过 参 考 文 献 ( ) 程并不 完 全 是 线 性 的 。最 坏 的 查 找 算 法 是 O n [ 1 ] 揭春雨 ,刘源 ,梁南元. 论汉语自动分词方法 [ J ]. 中 ( ) n 代表儿子数 。如果在 建词 库 时 使 用 哈希 表 , 找 ( ) 文信息学报 , 1989 1: 36 - 40 东西时的效率几乎是线性 的 , 而 且 实现 起 来 也 很 简 黄吕宁. 中文信息处理中的分词问题 [ J ]. 中文信息 单 。当然用哈希表要付出存 储空 间 变 大 的 代 价 , 但 [ 2 ] ( ) 学报 , 1990 1: 89 - 92 这样的代 价 来 换 取 速 度 与 简 单 性 也 是 的 。 ?找 到 黄俊杰. 书面汉语自动分词的研究 [ J ]. 计算机杂 有终结符的 字 后 , 必 须 要 将 它 建 成 一 个 完 整 的 词 。 [ 3 ] ( ) 志 , 1991 1: 17 - 20