中文文本检索的新型全文索引模型

### 中文文本检索的新型全文索引模型 在当今信息爆炸的时代，电子中文文档数量飞速增长，对能够快速访问大量文本文件的中文文本检索系统的需求也日益迫切。传统的全文检索系统虽能提供在线文本访问支持，但在中文文本处理上存在诸多挑战。本文将介绍一种新型的中文文本检索全文索引模型，它基于有向图邻接矩阵的概念，有望解决传统方法的一些问题。 #### 1. 背景与问题提出 随着中国大陆、台湾、新加坡等地电子中文文档的大量涌现，对中文文本检索系统的需求不断增加。全文检索系统是提供在线文本访问支持的常用方式，用户可以使用文档中的任意单词或句子作为有效查询。一般来说，全文检索系统会使用索引来实现高效的文档检索，常见的文本索引方法包括倒排列表、签名文件、PAT树和PAT数组等。 然而，英文中广泛使用的基于单词的索引方法在中文中应用并不容易，因为中文文本没有明确的单词边界分隔符，进行基于单词的索引需要先进行分词，而准确的中文分词可能需要对句子进行深入分析，这是一项具有挑战性的任务。另一方面，基于字符的索引方法虽然不依赖分词，适合中文文本，但会消耗大量的存储空间，因为需要对文本数据库中的每个字符进行索引并存储其位置信息，这对于存储资源有限的应用场景（如基于CD的文本检索系统）并不友好。 #### 2. 新型索引模型介绍 为了解决上述问题，提出了一种基于有向图邻接矩阵的全文索引模型。下面详细介绍该模型的相关概念和构建步骤。 ##### 2.1 基本定义 - **字符集与字符串**：定义一个有限的中文字符集Σ，它包含中文文本中可能出现的中文字符、字母、数字、标点符号和其他符号。一个文本字符串是Σ中字符的有限序列，字符串的长度用|w|表示，也可以将字符串w看作一个函数w:{1,…,|w|}→Σ，w(j)表示字符串w中第j个位置的字符。 - **有向图**：对于字符串w，设V⊆Σ是w中唯一字符的集合，存在一个有向图TDG=<Vg, Eg>，其中Vg是顶点集，且Vg = V，即V中的每个字符对应Vg中的一个顶点；Eg是有向边集，每条边对应w中出现的一个二元组（bigram），方向从第一个字符指向第二个字符。由于一个字符可能在字符串的不同位置出现，字符串的有向图通常是有向循环图。 - **简单字符串（s - 字符串）**：简单字符串是指其中最多只有一个字符可以出现两次的字符串，等价于其有向图最多包含一个循环的字符串。可以证明，s - 字符串中的所有二元组都是唯一的。 ##### 2.2 字符串分割算法 为了将任意字符串分割成一系列s - 字符串，给出以下算法： ```plaintext 算法1. 将任意字符串w分割成一系列s - 字符串 1) 设置k = 1; 2) 从字符串w的第一个字符w(1)扫描到最后一个字符w(|w|) 3) 如果存在两个字符w(i) , w(j) 使得w(j) = w(i) (1 ≤ j < i ≤ |w|)，则转到5); 4) 否则转到9); 5) sk = w(1) w(2)…w(i); 6) 如果i < |w|，则执行 7) k = k + 1; w = w(i) w(i + 1)…w(|w|); 转到2); 8) 否则转到10) 9) sk = w; 10) 结果是(s1, s2, …, sk)，其中si(|si|) = si + 1(1) (1 ≤ i < k)。 ``` ##### 2.3 加权有向图与邻接矩阵 - **加权有向图**：建立字符串的加权有向图的步骤如下： 1. 使用算法1将字符串分割成一系列s - 字符串，并按照定义为这些s - 字符串进行全局编号。 2. 根据定义1构建字符串的有向图。 3. 将有向图中的每条边与该边对应的二元组所在的s - 字符串的编号关联起来。 4. 将共享相似二元组的有向边合并为一条有向边，并将它们对应的编号合并为一个集合作为合并后边的权重。 - **邻接矩阵**：字符串的邻接矩阵A定义为A = [aij]，其中aij = Lw(li, lj)，Lw(li, lj)是与有向边lilj相关联的编号集合。 下面通过一个例子来说明这些概念： 考虑一个中文文本字符串w1: “




”，其有向图的顶点集Vg = {“”, “”, “”, “”, “
”, “”, “”}，有向边集Eg = {“
”, “
”, “
”, “
”, “”, “
”, “

”, “
”, “”}。使用算法1将w1分割成五个s - 字符串：s1 = “

”，s2 = “

”，s3 = “