1．4 研究方法和指导思想

PAT-Array（又称为Suffix Array）是在信息检索领域被成功使用的一种十分有效的数据结构。(1)、创建PAT-Array。
以字符串“tobeornottobe”为例。图1给出了一个简单的字符串“tobeornottobe”的左右PAT-Array及各自的LCP数组。为了方便实现左右后缀字符串的排序处理，在字符串的两端分别加入字符串中止标记($，其值为0)。图2给出了一个实际文本PAT-Array的可视化表示，左右两边分别表示文本的左右PAT-Array。
String “tobeornottobe”

#	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
String	$	t	o	b	e	o	r	n	o	t	t	o	b	e	$

Suffix array

#	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Left-index	14	3	12	4	13	7	5	8	2	11	6	1	9	10
Right-index	14	12	3	13	4	7	11	2	5	8	6	10	1	9

LCP arrays on both sides

#	1	2	3	4	5	6	7	8	9	10	11	12	13	14
LCPl	0	3	0	4	0	0	1	1	2	0	0	1	1	/
LCPr	0	2	0	1	0	0	3	1	1	0	0	4	1	/

图1 PAT-Array示例

PAT-Array示例

图2 实际文本（小说《笑傲江湖》片断）PAT-Array的可视化表示
(2)、实现PAT-Array数据结构上对重复字串进行抽取算法。
如图2右部所示，在右PAT-Array中，所有以“东”字开始的后缀字符串依“东”字右语境有序排列在一起。我们可以抽取到以“东”字开始的重复字符串，如：“东方不败不”、“东方不败为”、“东方不败之”、“东方不败也”、“东方不败仍是”、“东方不败”等等。但并不包含这些字串的子串，如：“东方”、“东方不”等等，这些子串并不是相邻两个后缀字符串的最大共有前缀(LCP)，它们的所有出现均包含在其它最大共有前缀中，如“东方不败”；相应的，由图2的左部，我们同样可以抽取以“败”字开始的所有重复字串，如：“上东方不败”、“与东方不败”、“为东方不败”、“魔教教主东方不败”、“教主东方不败”、“东方不败”。
通过分别扫描字串S的左右PAT-Array，可以分别获得左右重复字串列表(分别记为：L-list、R-list)，L-list和R-list中的重复字符串只能表示从某一个字符开始向左或向右重复出现两次或两次以上的字符串，只有同时在L-list和R-list中同时出现的字符串才是在不同上下文中重复出现的字符串。
(3)、以抽取的重复字串作为切分单元，加工原文本。
例如，抽取的重复字串有"to""be""or"，原文本为"tobeornottobe"，则加工后的原文本委“{to}{be}{or}not{to}{be}”。

5 论文的组织和安排

整个论文分为六个部分，绪论介绍分词处理技术相关的背景和基础知识以及这次论文的目标，后面各章节全部围绕系统的设计的各个细节来描述。分别为
第2章信息系统的系统分析，包括用户的各种需求和系统的各个结构，预先估计系统设计可能会遇到的困难，为设计系统构架，组织模块打好基础。
第3章系统模块设计与分析，把系统分为几个大的功能模块，想清楚模块之间的关系，资源的从属关。尽量避免模块间的功能重叠或混乱。
第4章这一章将详细描述各个模块的设计方法，将模块化为更小的功能块，阐述各个功能块的作用，各种数据结构设计的合理性和优越性。说明个系统模块的性能。
第5章分析整体系统难点，缺陷以及没有解决的问题，已经对系统以后改进发展的看法。
第6章对这次设计中各种性能优化，整体结构设计的经验进行总结。

第二章分词处理系统分析

2．1 对分词处理系统的功能要求进行分析

无词典分词是指不依靠词典把文章中的词提取出来, 词是汉字字符的一个结合模式, 但并不是每种结合模式都构成词, 只有那些具有确定语义或语法功能的汉字结合模式才是词, 而在不使用词典的情况下, 由于缺乏先验知识, 词是无法直接识别的. 但在统计意义上, 每个文档中的汉字结合模式是可以观察的. 如果一个词在一篇文档中重复出现的次数越多, 则这个词就越容易被识别出来, 反之,这个词在文档中只出现一次或很少出现, 则不易被识别. 无词典分词算法的主要思想就是利用汉字的结合模式在文档中重复出现的次数来判断这个结合模式是否是一个词. 而这种分词方法完全不依赖于词典, 因此称为无词典分词.
分词的目标是尽可能把文档中出现的词找出来, 词的识别精度也要尽可能高.
首先, 读入一篇文档, 把整篇文档存入一个字符串str 中. 根据此字符串生成一个后缀数组int S [ ]以及最长公共前缀信息数组int LCP[ ] . 后缀数组长度为字符串的长度, 最长公共前缀的长度为字符串str 的长度+ 1. 同时也得到后缀数组的最长公共前缀信息.
第二步, 存放汉字的结合模式。
第三步, 对存放中的汉字串(候选词) 进行处理和筛选, 最终得到的结果就是抽到的词.
最后, 利用前三步得到的是“词”对文档进行切分, 并把抽到的词和切分的结果存到文件中。并提供对选中新词进行切分和再切分功能。

2．2 对分词处理系统的性能要求进行分析

对性能要求首先要保证的就是稳定性，对于执行算法时间长的程序，要减少一切可能崩溃的可能。必须消除所有的内存泄漏。减少线程处理可能产生的错误，保障系统稳定运行。
另外一定要保证较高的查询速度，由于数据量可能非常大，导致索引量非常大。

第三章分词处理系统总体设计

3．1 对分词处理系统的总体构架

这次分词处理系统的主要构架有六个部分组成，包括重复字串分析参数准备模块、重复字串分析模块、重复字串(新词)筛选和结果保存模块、基于新词的切分模块、基于选中新词的切分模块和再切分模块。（见图1）
图1 分词处理系统总体构架

3．2 对分词处理系统的各模块功能说明

重复字串分析参数准备模块：负责指定源文件索引文件位置、背景语料索引位置和停用字符集合。
重复字串分析模块：根据源文件索引和背景语料索引进行分析，生成重复字串。
重复字串(新词)筛选和结果保存模块：提供界面让用户可以筛选重复字串，并且保存筛选的结果，以供基于选中新词的切分模块使用，同时提供功能让重复字串(新词)保存到系统词库里。
基于新词的切分模块：对重复字串分析模块分析出来的所有重复字串(新词)在源文件内进行查找和切分，并生成切分结果文件。
基于选中新词的切分模块：对重复字串(新词)筛选和结果保存模块筛选出来的重复字串(新词)在源文件内进行查找和切分，并生成切分结果文件。
再切分模块：对重复字串(新词)筛选和结果保存模块筛选出来的重复字串(新词)在对于上面两个切分模块生成的文件内进行再次查找切分，并生成切分结果文件。

3．3 对分词处理系统数据流的说明

在图1已经用箭头表示出了这个分词处理系统中数据的流动方向。
重复字串分析参数准备模块，它负责指定源文件索引文件位置、背景语料索引位置和停用字符集合。而这些数据是重复字串分析模块所需要的。
重复字串分析模块依赖于模块参数生成了重复字串。
重复字串(新词)筛选和结果保存模块使用原始的由重复字串分析模块分析出来的重复字串，并保存了筛选结果，同时使分析出来的结果可以保存到系统词库内。
基于新词的切分模块，它对重复字串分析模块分析出来的所有重复字串(新词)在源文件内进行查找和切分，并生成切分结果文件。
基于选中新词的切分模块，它对重复字串(新词)筛选和结果保存模块筛选出来的重复字串(新词)在源文件内进行查找和切分，并生成切分结果文件。
再切分模块，它对重复字串(新词)筛选和结果保存模块筛选出来的重复字串(新词)在对于上面两个切分模块生成的文件内进行再次查找切分，并生成切分结果文件。

友情链接

汕头招聘网 | 山东招聘网 | 郑州教育培训 | 软件下载