一种基于树形结构的排序方法
一种基于树形结构的排序方法
【技术领域】
[0001 ]本发明涉及数据处理领域，具体涉及一种基于树形结构的排序方法。
【背景技术】
[0002]随着互联网的飞速发展，信息的指数增长，数据形式的多样性，人们很难在海亮的信息中快速地找到符合自己需求的部分。全文数据库的出现，大大改善了这一现状。全文数据库，也称为文本数据库，它是管理海量文本的系统。全文数据库要完成的工作仍然是传统数据库的两大功能:存储和检索，具体而言就是文本数据的存储和任意字符串的检索。作为检索条件的字符串可以是常量型字符串，也可以是正则表达式(或其他方式，比如距离限制等等)表示的一组具有共同特征的字符串集合。
[0003]目前比较常见和流行的全文检索模型有以下几种模型:署名文件(SignatureFiles)、位图(Bit Map)、倒排表(Inverted List)、Σ2矩阵Pat树和Pat数组等等。这些模型在专家们的努力下，已经相当成熟并在实践中得到广泛应用。
[0004]从书目索引延伸出来的方法就是现在应用最广泛的倒排表模型。它具有创建索引速度较快的特点，在网络搜索引擎中广泛应用。但其所需的存储空间较大，查询速度较慢。署名文件虽然实现简单，但是要找到一个合适的散列函数和一个宽度适合的矢量非常困难，而且因对象而异。如果没有选择好，则查询结果就会出现相当的不确定性。位图文件索引结构思路简单，使用方便，时间效率高，在布尔检索上尤其高效，但是其空间效率很低，即使使用了位图压缩算法，仍然难以接受。Pat树模型的最大优点是检索效率很高，尤其对模型特殊的检索，如前缀检索、范围检索等检索效率更高。然而同位图模型一样，空间效率极低，而且创建过程中空间开销更大，创建效率也很低。Pat数组是对Pat树的修改，它将Pat树的叶节点串行化就得到了 Pat数组。Pat数组虽然很大程度上压缩了创建过程中的开销，但是，因为采用数组的存储方式，其创建和合并需要移动大量的数据，动态性很难令人满意。
【发明内容】
[0005]至少部分的解决现有技术中存在的问题，本发明提出一种基于树形结构的排序方法，用于中文搜索引擎中对中文网页数据的处理，包括:
[0006]步骤SlOO，网页数据预处理；
[0007]步骤S200，建立网页数据索引文件；
[0008]步骤S300，接收用户输入的查询字符串，根据网页数据索引进行检索；
[0009]步骤S400，对检索到的结果进行排序，将排序结果展示给用户。
[0010]所述的基于树形结构的排序方法，其中，步骤S200中的所述网页数据索引文件是对处理后的网页数据所建立的网页数据索引组成的文件。
[0011]所述的基于树形结构的排序方法，其中，所述网页数据索引为字索引和/或词索引。
[0012]所述的基于树形结构的排序方法，其中，步骤SlOO进一步包括:
[0013]首先对抓取的原始网页进行分类，然后再按照分类分别提取网页中的文本信息，得到分类后的文本信息;生成网页索引文件的过程包括为原始网页的每个分类分别建立网页索引文件。
[0014]所述的基于树形结构的排序方法，其中，所述网页数据索引是基于二元内相关后续树创建的索引。
[0015]所述的基于树形结构的排序方法，其中，在步骤S200中，建立网页数据索引文件进一步包括:
[0016]首先，判断每个分类的文本信息的容量，当所述分类的容量小于IGB时，为所述分类的文本信息建立字索引，当所述分类的容量大于等于IGB时，为所述分类的文本信息建立词索引。
[0017]所述的基于树形结构的排序方法，进一步包括:
[0018]将查询字符串分别分解为字和词，对于网页数据索引是字索引的情况，按字根据所述字索引来进行检索;对于网页数据索引是词索引的情况，按分词根据所述词索引来进行检索。
[0019]所述的基于树形结构的排序方法，其中，在为所述网页数据建立词索引之前，还包括对文本信息进行分词的步骤，具备包括:利用分词词典对文本进行分词操作形成标引词隹A
口 O
[0020]所述的基于树形结构的排序方法，所述分词操作具体包括:
[0021]采用基于PATRICIA树结构的词典，具体采用增量最大匹配法切分，即对于一个字串，从长度为2的子串开始，对A1A1H，在词典中查找是否是词，如果不是则将仏单独成词，然后子串后移一个字，继续查找Ai+1Ai+2;如果是词，则需要将子串长度加一，判断Ai+1Ai+2Ai+3是否是词，如果不是，则将A1+1A1+2切分出来，如果是则继续加一，直到查找不到词为止。
[0022]所述的基于树形结构的排序方法，进一步包括:
[0023]分词完成后，对切分出的词条去除停用词，然后统计词条集合中相邻词的频率，生成一个双词频率表。
[0024]本发明采用二元内相关后续树模型为网页数据创建索引，同时考虑了字索引和词索引的优缺点，在减少索引空间的同时提尚了检索效率。
【附图说明】
[0025]图1为本发明基于树形结构的排序方法的流程图；
【具体实施方式】
[0026]下面将结合本发明的附图，对本发明的技术方案进行清楚、完整地描述。这里将详细地对示例性实施例进行说明，其示例表示在附图中。下面的描述涉及附图时，除非另有表示，不同附图中的相同数字表示相同或相似的要素。以下示例性实施例中所描述的实施方式并不代表与本发明相一致的所有实施方式。相反，它们仅是与如所附权利要求书中所详述的、本发明的一些方面相一致的装置和方法的例子。
[0027]首先，对本发明中用到一些术语介绍如下:
[0028](I)源文档库:源文档库是指由网络爬虫从互联网上抓取的原始网页文件集合，用来建立索引为用户检索使用，该集合不是静态的，根据抓取的策略或者定期批量更新，或者增量更新，主要以保证系统的时新性为主，即将新出现的网页尽量及时的抓取过来建立索弓丨，满足用户的检索需求；
[0029](2)预处理:预处理是指对抓取的网页文件进行处理的过程，包括:建立索引网页库、网页信息提取，建立索引网页库就是要实现给定一个网页的URL，在索引网页库中能够找到该URL所对应的网页；网页信息提取就是从网页中提取建立索引所需要的文本信息，包括标题、正文等；
[0030](3)文本:源文档库经过预处理步骤的网页信息提取所形成的文本信息的集合，是建立索引的直接对象；
[0031](4)分词词典:分词词典是分词操作的基础，是汉语词汇的集合，用来在分词时辨别并切分出文本中的单词；
[0032](5)分词操作:分词操作就是将文本切分成词汇组合的过程，预处理后的文本和用户输入的查询字符串都是它的操作对象，它能依据分词词典在文本字符串中正确匹配到词汇，剔除掉停用词，输出标引词或检索词的集合；
[0033](6)建立内相关后续树索引:该操作就是对文本分词后形成的标引词集合建立内相关后续树的过程；
[0034](7)词索引文件:词索引文件就是上一步操作中生成的索引文件，在词索引文件中每个标引词都有一棵以它为根的后续树，树的结点中包含了标引词所在文本的编号以及它的后续信息；
[0035](8)查询字符串:用户的查询需求通常是以字符串的形式来表示的，最简单的查询字符串往往是单个的词，对于较长的查询字符串，如短语或句子，要进行分词处理，所采用的分词算法应和对文本使用的分词算法一致，以保证检索结果的准确性；
[0036](9)检索操作:对于检索词的集合根据内相关后续树模型的查找算法，在词索引文件中进行查找，将匹配到的文本号输出到结果集；
[0037](10)结果集:结果集是一般是指通过检索操作所得到的查询字符串所在的文本号，得到的文本可能是一系列的文档，这就需要按照一定的信息检索模型对文档集合处理，得出相关程度最大的文档集合，呈现给用户。
[0038]内相关后续树的相关定义:
[0039](I)后续:对文本T中的字符串am2来说，a2称为ai的后续，文本T最后一个字符的后续称为结束符，用“#，，来表示。后续的定义是内相关后续树模型的基础，文本中总会有相同的字符出现，具体来说就是有相同的字或词，如果某一个索引项a出现了 k次，那么a就会有k个后续(a不是文本的结尾)，记作a[s]，s = l，2，…，k。
[0040](2)—元后续 表达式与一元后续树:假设全文T是由字符串ai，a2，...，an，#组成的，如果其中的au = ai2 =…= aik是相同的字符，记为a，而au+i，ai2+i，…，aik+i分别是它们的后续，则所有的3和它的后续就构成了一个一元后续表达式3(311+1，312+1^..，aik+l)，用一棵树来描述此表达式的话，a是树根，au+i，ai2+i，…，aik+i是它的后续结点，这棵树就成为a的一兀后续树。
[0041 ] (3) 二元后续表达式与二元后续树:对一元后续表达式进行扩展，如果原文T中有相同的字符串aiiaii+i = ai2ai2+i =…= aikaik+i，记作ab，则所有的ab和其后续就构成了一个二兀后续表达式，记作a(b(aii+2，ai2+2,..，aik+2))。
[0042]举例:在文本abcbacabacc#中(本发明举例中的文本都以此文本为例，命名为T)，ab字符串出现了2次，则其文本库存在一个二元后续表达式为:a(b(c，a))。用树来表示这个表达式的话，将all+2，al2+2，…，alk+2这些后续用其在以b为根的一元后续树中它们所在分支的序号来表示，对于上例来说二元后续表达式可以改为:a(b(l，3))的二元后续树表示为:a是树根，aii+i，ai2+i，...，aik+i是a的后续，(au+i,tagi)，(ai2+i，tag2)，…，(aik+i，tagk)则作为a的后续结点，其中，tagi，tag2...，tagk分为是以aii+i，ai2+i，...，aik+i为根的一元后续树中au+i，ai2+i，…，aik+i的后续所在分支的序号。以上述文本T为例，a的后续依次为b、c、b、c，相应的后续结点依次为(13，1)、((:，2)、(13，3)、((3，3)。
[0043]内相关后续树的定义:由一个源文档库中全部文档的所有索引项的后续树组成的森林，叫做这个源文档库的内相关后续树，当所述后续树为二元后续树时，该内相关后续树为二元内相关后续树。
[0044]参见图1，本发明提出的一种基于树形结构的排序方法，用于中文搜索引擎中对中文网页数据的处理，包括:
[0045]步骤SlOO，网页数据预处理；
[0046](I)提取网页中的文本信息，生成相应的文本并对文本进行编号。这一过程主要工作是将网页文件中的文本信息提取出来，生成用于建网页数据索引的文档。
[0047](2)生成网页索引文件。
[0048]需要一个网页索引文件来记录文本编号和其来源网页的相关信息，如网页标题、URL和网页大小等信息，其作用有两方面:一是在建立后续的网页数据索引阶段，后续树结点中只需要记录文档的编号，而不是冗长的文件名；二是在检索阶段可以根据文本编号从网页索引文件中找出源网页的URL信息，从而以特定的方式输出到结果显示页面上。
[0049](3)将文本中的标点符号去掉，使文本成为短字符串的集合。
[0050]该步骤的输入是抓取到的网页文件，输出是待切词的文本。
[0051 ]步骤S200，建立网页数据索引文件
[0052]为步骤SlOO处理后的网页数据建立网页数据索引文件。网页数据索引文件是对处理后的网页数据所建立的索引组成的文件。可以为所述网页数据建立字索引，也可以为所述网页数据建立词索引。所述索引是基于二元内相关后续树创建的索引。所述网页数据索引文件可以为网络搜索引擎的搜索提供服务。
[0053]在中文检索系统中，索引的语言单元可以分为字和词两种，由此出现了两种不同的建索引库策略:基于字表的建库策略和基于词表的建库策略。基于字表的建库策略，是指将源文档中的每个汉字均作为标引的基本单元，为每个不同的字都建立一个字表，字表中记录了该字在不同文档中的所有出现位置，在检索时对查询字符串中的单字所检索到的记录进行逻辑乘运算从而获得最终的结果集。基于字表建库的优点主要有:字表规模小、查全率高，缺点是当源文档数量大时索引文件占用的存储空间很大。
[0054]基于词表的建库策略就是以能表达一定语言意义的词为索引项建立索引库。这种建库思想一般需要对源文档进行分词操作，也就是将源文档中的字符集合分解为词的集合，检索的时候同样需要对检索字符串分词，然后对每个词在索引文件中查找记录，求交后最后得到检索结果集。基于词表建库的优点主要有:检索速度快、查准率高，缺点是查全率不尚。
[0055]本发明的一实施例兼顾了上述两种建立索引库的优缺点。同时采用了两种建立索引库的方法。
[0056]本发明上述实施例的基础上，在步骤SlOO中，网页数据预处理进一步包括首先对抓取的原始网页进行分类，然后再按照分类分别提取网页中的文本信息，得到分类后的文本信息；生成网页索引文件的过程包括为原始网页的每个分类分别建立网页索引文件。在步骤S200中，建立网页数据索引文件进一步包括:首先，判断每个分类的文本信息的容量，当所述分类的容量小于IGB时，为所述分类的文本信息建立字索引，当所述分类的容量大于等于IGB时，为所述分类的文本信息建立词索引。
[0057]上述实施例中，所述二元内相关后续树定义如下:
[0058](I)后续:对文本T中的字符串am2来说，a2称为ai的后续，文本T最后一个字符的后续称为结束符，用来表示;文本中总会有相同的字符出现，具体来说就是有相同的字或词，如果某一个索引项a出现了k次，a不是文本的结尾，那么a有k个后续，记作a[s]，s = l，2，...，k;
[0059](2)—元后续表达式与一元后续树:假设全文T是由字符串ai，a2，...，an，#组成的，如果其中的au = ai2 =…= aik是相同的字符，记为a，而au+i，ai2+i，…，aik+i分别是它们的后续，则所有的3和它的后续就构成了一个一元后续表达式3(311+1，312+1^..，aik+l)，用一棵树来描述此表达式，a是树根，au+i，ai2+i，…，aik+i是它的后续结点，这棵树就是a的一兀后续树；
[0060](3) 二元后续表达式与二元后续树:对一元后续表达式进行扩展，如果原文T中有相同的字符串aiiaii+i = ai2ai2+i =…= aikaik+i，记作ab，则所有的ab和其后续就构成了一个二兀后续表达式，记作a(b(aii+2，ai2+2，...,aik+2))；
[0061 ] (4)a的二元后续树表示为:a是树根，au+i，ai2+i，…，aik+i是a的后续，(au+i, tagi)，(ai2+i, tag2)，…，(aik+i,tagk)则作为a的后续结点，其中，tagi，tag2...，tagk分为是以au+i，ai2+i，…，aik+i为根的一兀后续树中au+i，ai2+i，…，aik+i的后续所在分支的序号；
[0062](5)内相关后续树的定义:由一个源文档库中全部文档的所有索引项的后续树组成的森林，叫做这个源文档库的内相关后续树，当所述后续树为二元后续树时，该内相关后续树为二元内相关后续树；
[0063]上述实施例中，基于二元内相关后续树创建索引的过程具体包括:
[0064]第一阶段是扫描文本，统计双字频率，也就是统计每个字符后续的个数，为初始化树时分配空间提供参考，具体步骤是:读入文本的开始两个字符A和B，如果B不是文本的结尾，则将双字AB的频度Freq[A][B]加1，将字串指针后移一个字，统计BC的频度Freq[B][C]，C是B的后续，循环进行直到文本结尾，则文本中所有双字的频度统计完成，生成该文本的双字频度表；
[0065]以文本T为例，ab这个双字的频度为2，ac这个双字的频度为2，bc这个双字的频度为1，......
[0066]第二阶段是二元内相关后续树的建立过程，初始化二元内相关后续树，为每个索引项建立后续树，再次扫描文本，将文本中所有字符的后续及后续编号填入它的后续树中，直到文本扫描完毕，将建好的二元内相关后续树模型输出到文本形成索引文件，具体步骤是:首先对二元内相关后续树初始化，为每个字符分配存储空间，接下来读入文本的开始两个字符A和B，如果B不是文本的结尾，将A树的分支数加一，然后把B和B的位置信息Pos(B)写入A树中，后移字符串一个位置，读取下一个双字B和C，再执行一遍上面的步骤，直到文本的结尾，最后将建成的二元内相关后续树输出到文本中。
[0067]举例:以文本T为例，a、b、c的初始逻辑位置分别为:Pos(a) = l ;Pos(b) = l ;Pos(c)=1(因为一开始每棵树中都只有根结点一个结点)。读入ab，将a的位置加一，S卩Pos(a) = 2(因为a树增加了一个分支，加一后是得到了下一分支的分支号)，然后将b及b的位置信息Pos (b)写入a的后续树的第Pos (a)_l个分支上(Pos (a)_l分支就是a树的待写入值的当前分支)，即把(b，l)写入树a的第I个分支;接下来，读入下一个字符C，则b的位置Pos(b) + l = 2，将(3及(:的位置信息Pos(c)写入b的后续树的第Pos(b)_l个分支上，即把((:，1)写入树13的第一个分支;这样循环执行下去，直到读入文本的末尾时，将(#，0)写入c的后续树中的最后一个分支，该文本的一.兀内相关后续树索引建立完毕。
[0068]对于为文本信息建立词索引，在建立词索引之前还包括对文本信息进行分词的步骤，具备包括:利用分词词典对文本进行分词操作形成标引词集合。
[0069]本发明中的分词词典采用基于PATRICIA树结构的词典，具体采用增量最大匹配法切分，即对于一个字串，从长度为2的子串开始，对A1Am，在词典中查找是否是词，如果不是则将六1单独成词，然后子串后移一个字，继续查找A1+1A1+2;如果是词，则需要将子串长度加一，判断Ai+1Ai+2Ai+3是否是词，如果不是，则将Ai+1Ai+2切分出来，如果是则继续加一，直到查找不到词为止。
[0070]由于长词出现的频率比较低，因此这种方法在匹配次数上较正向减字最大匹配法要少得多，时间性能较好。在增量匹配的过程中，由于词典的结构是PATRICIA树结构，具有前缀查询的功能，所以在增一匹配时，可以对新增字的二进制码从上一个匹配成功的词的最后一个比较位处接着比较，无需再从树根重新查找，这样一来通过一次遍历的过程就可以查找到最长词，查找的效率有了明显的改进。
[0071]分词完成后，对切分出的词条去除停用词，然后统计词条集合中相邻词的频率，生成一个双词频率表，为索引的创建做准备。
[0072]有了文本信息的索引，就可以基于索引进行了文本的检索，文本的检索方法是和相应的索引模型紧密关联的。
[0073]本发明还进一步包括步骤S300，接收用户输入的查询字符串，根据网页数据索引进行检索。对于不同的索引模型，具体的检索过程会不同。
[0074]在本发明的一个实施例中，将查询字符串分别分解为字和词，对于网页数据索引是字索引的情况，按字根据所述字索引来进行检索;对于网页数据索引是词索引的情况，按分词根据所述词索引来进行检索。
[0075]对于索引为二元内相关后续树模型的情况，具体的检索过程为:
[0076]第一阶段，针对网页数据索引是字索引的情况进行检索；
[0077]首先顺序读入查询字符串分解后的每一个字，取第一个字A，针对字索引，在二元内相关后续树中找到以A为根的树，然后在树A的叶子中逐个分支地匹配查询字符串的下一个字B，匹配到B的话则将B的后续编号加入队列，直到A的全部分支都匹配结束;转到以B为根的树，从队列中取出B树的分支号，查找相应的叶子结点来匹配字符串中的下一个字C，如此循环直到有一次匹配过程中没有匹配到或者查询字符串全部匹配结束，如果匹配成功，则意味着找到了包含查询字符串的原文；
[0078]第二阶段，针对网页数据索引是词索引的情况进行检索；
[0079]首先顺序读入查询字符串分解后的每一个词，取第一个词A，针对词索引，在二元内相关后续树中找到以A为根的树，然后在树A的叶子中逐个分支地匹配查询字符串的下一个词B，匹配到B的话则将B的后续编号加入队列，直到A的全部分支都匹配结束;转到以B为根的树，从队列中取出B树的分支号，查找相应的叶子结点来匹配字符串中的下一个词C，如此循环直到有一次匹配过程中没有匹配到或者查询字符串全部匹配结束，如果匹配成功，则意味着找到了包含查询字符串的原文。
[0080]本发明还进一步包括步骤S400，对检索到的结果进行排序，将排序结果展示给用户。
[0081]本发明不对排序方法进行限定，可以使用各种现有的排序技术对排序结果进行排序。
[0082]本发明一实施例中，为了提高检索效率，进一步的，针对网页数据索引是词索引的情况，将词索引文件中的索引词作为文本信息，基于所述内相关后续树模型对所述索引词再建立索引，从而进一步提尚检索的效率。
[0083]本发明采用二元内相关后续树模型为网页数据创建索引，同时考虑了字索引和词索引的优缺点，在减少索引空间的同时提尚了检索效率。
[0084]本领域技术人员在考虑说明书及实践这里公开的发明后，将容易想到本发明的其它实施方案。本申请旨在涵盖本发明的任何变型、用途或者适应性变化，这些变型、用途或者适应性变化遵循本发明的一般性原理并包括本发明未公开的本技术领域中的公知常识或惯用技术手段。
[0085]应当理解的是，本发明并不局限于上面已经描述并在附图中示出的精确结构，并且可以在不脱离其范围进行各种修改和改变。本发明的范围仅由所附的权利要求来限制。
【主权项】
1.一种基于树形结构的排序方法，用于中文搜索引擎中对中文网页数据的处理，包括: 步骤SlOO，网页数据预处理； 步骤S200，建立网页数据索引文件； 步骤S300，接收用户输入的查询字符串，根据网页数据索引进行检索； 步骤S400，对检索到的结果进行排序，将排序结果展示给用户。2.如权利要求1所述的基于树形结构的排序方法，其中，步骤S200中的所述网页数据索引文件是对处理后的网页数据所建立的网页数据索引组成的文件。3.如权利要求2所述的基于树形结构的排序方法，其中，所述网页数据索引为字索引和/或词索引。4.如权利要求2所述的基于树形结构的排序方法，其中，步骤SlOO进一步包括: 首先对抓取的原始网页进行分类，然后再按照分类分别提取网页中的文本信息，得到分类后的文本信息;生成网页索引文件的过程包括为原始网页的每个分类分别建立网页索引文件。5.如权利要求4所述的基于树形结构的排序方法，其中，所述网页数据索引是基于二元内相关后续树创建的索引。6.如权利要求4所述的基于树形结构的排序方法，其中，在步骤S200中，建立网页数据索引文件进一步包括: 首先，判断每个分类的文本信息的容量，当所述分类的容量小于IGB时，为所述分类的文本信息建立字索引，当所述分类的容量大于等于IGB时，为所述分类的文本信息建立词索引。7.如权利要求6所述的基于树形结构的排序方法，进一步包括: 将查询字符串分别分解为字和词，对于网页数据索引是字索引的情况，按字根据所述字索引来进行检索;对于网页数据索引是词索引的情况，按分词根据所述词索引来进行检索。8.如权利要求7所述的基于树形结构的排序方法，其中，在为所述网页数据建立词索引之前，还包括对文本信息进行分词的步骤，具备包括:利用分词词典对文本进行分词操作形成标引词集合。9.如权利要求8所述的基于树形结构的排序方法，所述分词操作具体包括: 采用基于PATRICIA树结构的词典，具体采用增量最大匹配法切分，即对于一个字串，从长度为2的子串开始，对A1A^1，在词典中查找是否是词，如果不是则将仏单独成词，然后子串后移一个字，继续查找Ai+1Ai+2;如果是词，则需要将子串长度加一，判断Ai+1Ai+2Ai+3是否是词，如果不是，则将A1+1A1+2切分出来，如果是则继续加一，直到查找不到词为止。10.如权利要求9所述的基于树形结构的排序方法，进一步包括: 分词完成后，对切分出的词条去除停用词，然后统计词条集合中相邻词的频率，生成一个双词频率表。
【专利摘要】本发明提出了一种基于树形结构的排序方法，用于中文搜索引擎中对中文网页数据的处理，包括：步骤S100，网页数据预处理；步骤S200，建立网页数据索引文件；步骤S300,接收用户输入的查询字符串，根据网页数据索引进行检索；步骤S400,对检索到的结果进行排序，将排序结果展示给用户。本发明采用二元内相关后续树模型为网页数据创建索引，同时考虑了字索引和词索引的优缺点，在减少索引空间的同时提高了检索效率。
【IPC分类】G06F17/30
【公开号】CN105488114
【申请号】CN201510817371
【发明人】陈虹宇, 罗阳, 苗宁
【申请人】四川神琥科技有限公司
【公开日】2016年4月13日
【申请日】2015年11月20日
【技术领域】
[0001 ]本发明涉及数据处理领域，具体涉及一种基于树形结构的排序方法。
【背景技术】
[0002]随着互联网的飞速发展，信息的指数增长，数据形式的多样性，人们很难在海亮的信息中快速地找到符合自己需求的部分。全文数据库的出现，大大改善了这一现状。全文数据库，也称为文本数据库，它是管理海量文本的系统。全文数据库要完成的工作仍然是传统数据库的两大功能:存储和检索，具体而言就是文本数据的存储和任意字符串的检索。作为检索条件的字符串可以是常量型字符串，也可以是正则表达式(或其他方式，比如距离限制等等)表示的一组具有共同特征的字符串集合。
[0003]目前比较常见和流行的全文检索模型有以下几种模型:署名文件(SignatureFiles)、位图(Bit Map)、倒排表(Inverted List)、Σ2矩阵Pat树和Pat数组等等。这些模型在专家们的努力下，已经相当成熟并在实践中得到广泛应用。
[0004]从书目索引延伸出来的方法就是现在应用最广泛的倒排表模型。它具有创建索引速度较快的特点，在网络搜索引擎中广泛应用。但其所需的存储空间较大，查询速度较慢。署名文件虽然实现简单，但是要找到一个合适的散列函数和一个宽度适合的矢量非常困难，而且因对象而异。如果没有选择好，则查询结果就会出现相当的不确定性。位图文件索引结构思路简单，使用方便，时间效率高，在布尔检索上尤其高效，但是其空间效率很低，即使使用了位图压缩算法，仍然难以接受。Pat树模型的最大优点是检索效率很高，尤其对模型特殊的检索，如前缀检索、范围检索等检索效率更高。然而同位图模型一样，空间效率极低，而且创建过程中空间开销更大，创建效率也很低。Pat数组是对Pat树的修改，它将Pat树的叶节点串行化就得到了 Pat数组。Pat数组虽然很大程度上压缩了创建过程中的开销，但是，因为采用数组的存储方式，其创建和合并需要移动大量的数据，动态性很难令人满意。
【发明内容】
[0005]至少部分的解决现有技术中存在的问题，本发明提出一种基于树形结构的排序方法，用于中文搜索引擎中对中文网页数据的处理，包括:
[0006]步骤SlOO，网页数据预处理；
[0007]步骤S200，建立网页数据索引文件；
[0008]步骤S300，接收用户输入的查询字符串，根据网页数据索引进行检索；
[0009]步骤S400，对检索到的结果进行排序，将排序结果展示给用户。
[0010]所述的基于树形结构的排序方法，其中，步骤S200中的所述网页数据索引文件是对处理后的网页数据所建立的网页数据索引组成的文件。
[0011]所述的基于树形结构的排序方法，其中，所述网页数据索引为字索引和/或词索引。
[0012]所述的基于树形结构的排序方法，其中，步骤SlOO进一步包括:
[0013]首先对抓取的原始网页进行分类，然后再按照分类分别提取网页中的文本信息，得到分类后的文本信息;生成网页索引文件的过程包括为原始网页的每个分类分别建立网页索引文件。
[0014]所述的基于树形结构的排序方法，其中，所述网页数据索引是基于二元内相关后续树创建的索引。
[0015]所述的基于树形结构的排序方法，其中，在步骤S200中，建立网页数据索引文件进一步包括:
[0016]首先，判断每个分类的文本信息的容量，当所述分类的容量小于IGB时，为所述分类的文本信息建立字索引，当所述分类的容量大于等于IGB时，为所述分类的文本信息建立词索引。
[0017]所述的基于树形结构的排序方法，进一步包括:
[0018]将查询字符串分别分解为字和词，对于网页数据索引是字索引的情况，按字根据所述字索引来进行检索;对于网页数据索引是词索引的情况，按分词根据所述词索引来进行检索。
[0019]所述的基于树形结构的排序方法，其中，在为所述网页数据建立词索引之前，还包括对文本信息进行分词的步骤，具备包括:利用分词词典对文本进行分词操作形成标引词隹A
口 O
[0020]所述的基于树形结构的排序方法，所述分词操作具体包括:
[0021]采用基于PATRICIA树结构的词典，具体采用增量最大匹配法切分，即对于一个字串，从长度为2的子串开始，对A1A1H，在词典中查找是否是词，如果不是则将仏单独成词，然后子串后移一个字，继续查找Ai+1Ai+2;如果是词，则需要将子串长度加一，判断Ai+1Ai+2Ai+3是否是词，如果不是，则将A1+1A1+2切分出来，如果是则继续加一，直到查找不到词为止。
[0022]所述的基于树形结构的排序方法，进一步包括:
[0023]分词完成后，对切分出的词条去除停用词，然后统计词条集合中相邻词的频率，生成一个双词频率表。
[0024]本发明采用二元内相关后续树模型为网页数据创建索引，同时考虑了字索引和词索引的优缺点，在减少索引空间的同时提尚了检索效率。
【附图说明】
[0025]图1为本发明基于树形结构的排序方法的流程图；
【具体实施方式】
[0026]下面将结合本发明的附图，对本发明的技术方案进行清楚、完整地描述。这里将详细地对示例性实施例进行说明，其示例表示在附图中。下面的描述涉及附图时，除非另有表示，不同附图中的相同数字表示相同或相似的要素。以下示例性实施例中所描述的实施方式并不代表与本发明相一致的所有实施方式。相反，它们仅是与如所附权利要求书中所详述的、本发明的一些方面相一致的装置和方法的例子。
[0027]首先，对本发明中用到一些术语介绍如下:
[0028](I)源文档库:源文档库是指由网络爬虫从互联网上抓取的原始网页文件集合，用来建立索引为用户检索使用，该集合不是静态的，根据抓取的策略或者定期批量更新，或者增量更新，主要以保证系统的时新性为主，即将新出现的网页尽量及时的抓取过来建立索弓丨，满足用户的检索需求；
[0029](2)预处理:预处理是指对抓取的网页文件进行处理的过程，包括:建立索引网页库、网页信息提取，建立索引网页库就是要实现给定一个网页的URL，在索引网页库中能够找到该URL所对应的网页；网页信息提取就是从网页中提取建立索引所需要的文本信息，包括标题、正文等；
[0030](3)文本:源文档库经过预处理步骤的网页信息提取所形成的文本信息的集合，是建立索引的直接对象；
[0031](4)分词词典:分词词典是分词操作的基础，是汉语词汇的集合，用来在分词时辨别并切分出文本中的单词；
[0032](5)分词操作:分词操作就是将文本切分成词汇组合的过程，预处理后的文本和用户输入的查询字符串都是它的操作对象，它能依据分词词典在文本字符串中正确匹配到词汇，剔除掉停用词，输出标引词或检索词的集合；
[0033](6)建立内相关后续树索引:该操作就是对文本分词后形成的标引词集合建立内相关后续树的过程；
[0034](7)词索引文件:词索引文件就是上一步操作中生成的索引文件，在词索引文件中每个标引词都有一棵以它为根的后续树，树的结点中包含了标引词所在文本的编号以及它的后续信息；
[0035](8)查询字符串:用户的查询需求通常是以字符串的形式来表示的，最简单的查询字符串往往是单个的词，对于较长的查询字符串，如短语或句子，要进行分词处理，所采用的分词算法应和对文本使用的分词算法一致，以保证检索结果的准确性；
[0036](9)检索操作:对于检索词的集合根据内相关后续树模型的查找算法，在词索引文件中进行查找，将匹配到的文本号输出到结果集；
[0037](10)结果集:结果集是一般是指通过检索操作所得到的查询字符串所在的文本号，得到的文本可能是一系列的文档，这就需要按照一定的信息检索模型对文档集合处理，得出相关程度最大的文档集合，呈现给用户。
[0038]内相关后续树的相关定义:
[0039](I)后续:对文本T中的字符串am2来说，a2称为ai的后续，文本T最后一个字符的后续称为结束符，用“#，，来表示。后续的定义是内相关后续树模型的基础，文本中总会有相同的字符出现，具体来说就是有相同的字或词，如果某一个索引项a出现了 k次，那么a就会有k个后续(a不是文本的结尾)，记作a[s]，s = l，2，…，k。
[0040](2)—元后续 表达式与一元后续树:假设全文T是由字符串ai，a2，...，an，#组成的，如果其中的au = ai2 =…= aik是相同的字符，记为a，而au+i，ai2+i，…，aik+i分别是它们的后续，则所有的3和它的后续就构成了一个一元后续表达式3(311+1，312+1^..，aik+l)，用一棵树来描述此表达式的话，a是树根，au+i，ai2+i，…，aik+i是它的后续结点，这棵树就成为a的一兀后续树。
[0041 ] (3) 二元后续表达式与二元后续树:对一元后续表达式进行扩展，如果原文T中有相同的字符串aiiaii+i = ai2ai2+i =…= aikaik+i，记作ab，则所有的ab和其后续就构成了一个二兀后续表达式，记作a(b(aii+2，ai2+2,..，aik+2))。
[0042]举例:在文本abcbacabacc#中(本发明举例中的文本都以此文本为例，命名为T)，ab字符串出现了2次，则其文本库存在一个二元后续表达式为:a(b(c，a))。用树来表示这个表达式的话，将all+2，al2+2，…，alk+2这些后续用其在以b为根的一元后续树中它们所在分支的序号来表示，对于上例来说二元后续表达式可以改为:a(b(l，3))的二元后续树表示为:a是树根，aii+i，ai2+i，...，aik+i是a的后续，(au+i,tagi)，(ai2+i，tag2)，…，(aik+i，tagk)则作为a的后续结点，其中，tagi，tag2...，tagk分为是以aii+i，ai2+i，...，aik+i为根的一元后续树中au+i，ai2+i，…，aik+i的后续所在分支的序号。以上述文本T为例，a的后续依次为b、c、b、c，相应的后续结点依次为(13，1)、((:，2)、(13，3)、((3，3)。
[0043]内相关后续树的定义:由一个源文档库中全部文档的所有索引项的后续树组成的森林，叫做这个源文档库的内相关后续树，当所述后续树为二元后续树时，该内相关后续树为二元内相关后续树。
[0044]参见图1，本发明提出的一种基于树形结构的排序方法，用于中文搜索引擎中对中文网页数据的处理，包括:
[0045]步骤SlOO，网页数据预处理；
[0046](I)提取网页中的文本信息，生成相应的文本并对文本进行编号。这一过程主要工作是将网页文件中的文本信息提取出来，生成用于建网页数据索引的文档。
[0047](2)生成网页索引文件。
[0048]需要一个网页索引文件来记录文本编号和其来源网页的相关信息，如网页标题、URL和网页大小等信息，其作用有两方面:一是在建立后续的网页数据索引阶段，后续树结点中只需要记录文档的编号，而不是冗长的文件名；二是在检索阶段可以根据文本编号从网页索引文件中找出源网页的URL信息，从而以特定的方式输出到结果显示页面上。
[0049](3)将文本中的标点符号去掉，使文本成为短字符串的集合。
[0050]该步骤的输入是抓取到的网页文件，输出是待切词的文本。
[0051 ]步骤S200，建立网页数据索引文件
[0052]为步骤SlOO处理后的网页数据建立网页数据索引文件。网页数据索引文件是对处理后的网页数据所建立的索引组成的文件。可以为所述网页数据建立字索引，也可以为所述网页数据建立词索引。所述索引是基于二元内相关后续树创建的索引。所述网页数据索引文件可以为网络搜索引擎的搜索提供服务。
[0053]在中文检索系统中，索引的语言单元可以分为字和词两种，由此出现了两种不同的建索引库策略:基于字表的建库策略和基于词表的建库策略。基于字表的建库策略，是指将源文档中的每个汉字均作为标引的基本单元，为每个不同的字都建立一个字表，字表中记录了该字在不同文档中的所有出现位置，在检索时对查询字符串中的单字所检索到的记录进行逻辑乘运算从而获得最终的结果集。基于字表建库的优点主要有:字表规模小、查全率高，缺点是当源文档数量大时索引文件占用的存储空间很大。
[0054]基于词表的建库策略就是以能表达一定语言意义的词为索引项建立索引库。这种建库思想一般需要对源文档进行分词操作，也就是将源文档中的字符集合分解为词的集合，检索的时候同样需要对检索字符串分词，然后对每个词在索引文件中查找记录，求交后最后得到检索结果集。基于词表建库的优点主要有:检索速度快、查准率高，缺点是查全率不尚。
[0055]本发明的一实施例兼顾了上述两种建立索引库的优缺点。同时采用了两种建立索引库的方法。
[0056]本发明上述实施例的基础上，在步骤SlOO中，网页数据预处理进一步包括首先对抓取的原始网页进行分类，然后再按照分类分别提取网页中的文本信息，得到分类后的文本信息；生成网页索引文件的过程包括为原始网页的每个分类分别建立网页索引文件。在步骤S200中，建立网页数据索引文件进一步包括:首先，判断每个分类的文本信息的容量，当所述分类的容量小于IGB时，为所述分类的文本信息建立字索引，当所述分类的容量大于等于IGB时，为所述分类的文本信息建立词索引。
[0057]上述实施例中，所述二元内相关后续树定义如下:
[0058](I)后续:对文本T中的字符串am2来说，a2称为ai的后续，文本T最后一个字符的后续称为结束符，用来表示;文本中总会有相同的字符出现，具体来说就是有相同的字或词，如果某一个索引项a出现了k次，a不是文本的结尾，那么a有k个后续，记作a[s]，s = l，2，...，k;
[0059](2)—元后续表达式与一元后续树:假设全文T是由字符串ai，a2，...，an，#组成的，如果其中的au = ai2 =…= aik是相同的字符，记为a，而au+i，ai2+i，…，aik+i分别是它们的后续，则所有的3和它的后续就构成了一个一元后续表达式3(311+1，312+1^..，aik+l)，用一棵树来描述此表达式，a是树根，au+i，ai2+i，…，aik+i是它的后续结点，这棵树就是a的一兀后续树；
[0060](3) 二元后续表达式与二元后续树:对一元后续表达式进行扩展，如果原文T中有相同的字符串aiiaii+i = ai2ai2+i =…= aikaik+i，记作ab，则所有的ab和其后续就构成了一个二兀后续表达式，记作a(b(aii+2，ai2+2，...,aik+2))；
[0061 ] (4)a的二元后续树表示为:a是树根，au+i，ai2+i，…，aik+i是a的后续，(au+i, tagi)，(ai2+i, tag2)，…，(aik+i,tagk)则作为a的后续结点，其中，tagi，tag2...，tagk分为是以au+i，ai2+i，…，aik+i为根的一兀后续树中au+i，ai2+i，…，aik+i的后续所在分支的序号；
[0062](5)内相关后续树的定义:由一个源文档库中全部文档的所有索引项的后续树组成的森林，叫做这个源文档库的内相关后续树，当所述后续树为二元后续树时，该内相关后续树为二元内相关后续树；
[0063]上述实施例中，基于二元内相关后续树创建索引的过程具体包括:
[0064]第一阶段是扫描文本，统计双字频率，也就是统计每个字符后续的个数，为初始化树时分配空间提供参考，具体步骤是:读入文本的开始两个字符A和B，如果B不是文本的结尾，则将双字AB的频度Freq[A][B]加1，将字串指针后移一个字，统计BC的频度Freq[B][C]，C是B的后续，循环进行直到文本结尾，则文本中所有双字的频度统计完成，生成该文本的双字频度表；
[0065]以文本T为例，ab这个双字的频度为2，ac这个双字的频度为2，bc这个双字的频度为1，......
[0066]第二阶段是二元内相关后续树的建立过程，初始化二元内相关后续树，为每个索引项建立后续树，再次扫描文本，将文本中所有字符的后续及后续编号填入它的后续树中，直到文本扫描完毕，将建好的二元内相关后续树模型输出到文本形成索引文件，具体步骤是:首先对二元内相关后续树初始化，为每个字符分配存储空间，接下来读入文本的开始两个字符A和B，如果B不是文本的结尾，将A树的分支数加一，然后把B和B的位置信息Pos(B)写入A树中，后移字符串一个位置，读取下一个双字B和C，再执行一遍上面的步骤，直到文本的结尾，最后将建成的二元内相关后续树输出到文本中。
[0067]举例:以文本T为例，a、b、c的初始逻辑位置分别为:Pos(a) = l ;Pos(b) = l ;Pos(c)=1(因为一开始每棵树中都只有根结点一个结点)。读入ab，将a的位置加一，S卩Pos(a) = 2(因为a树增加了一个分支，加一后是得到了下一分支的分支号)，然后将b及b的位置信息Pos (b)写入a的后续树的第Pos (a)_l个分支上(Pos (a)_l分支就是a树的待写入值的当前分支)，即把(b，l)写入树a的第I个分支;接下来，读入下一个字符C，则b的位置Pos(b) + l = 2，将(3及(:的位置信息Pos(c)写入b的后续树的第Pos(b)_l个分支上，即把((:，1)写入树13的第一个分支;这样循环执行下去，直到读入文本的末尾时，将(#，0)写入c的后续树中的最后一个分支，该文本的一.兀内相关后续树索引建立完毕。
[0068]对于为文本信息建立词索引，在建立词索引之前还包括对文本信息进行分词的步骤，具备包括:利用分词词典对文本进行分词操作形成标引词集合。
[0069]本发明中的分词词典采用基于PATRICIA树结构的词典，具体采用增量最大匹配法切分，即对于一个字串，从长度为2的子串开始，对A1Am，在词典中查找是否是词，如果不是则将六1单独成词，然后子串后移一个字，继续查找A1+1A1+2;如果是词，则需要将子串长度加一，判断Ai+1Ai+2Ai+3是否是词，如果不是，则将Ai+1Ai+2切分出来，如果是则继续加一，直到查找不到词为止。
[0070]由于长词出现的频率比较低，因此这种方法在匹配次数上较正向减字最大匹配法要少得多，时间性能较好。在增量匹配的过程中，由于词典的结构是PATRICIA树结构，具有前缀查询的功能，所以在增一匹配时，可以对新增字的二进制码从上一个匹配成功的词的最后一个比较位处接着比较，无需再从树根重新查找，这样一来通过一次遍历的过程就可以查找到最长词，查找的效率有了明显的改进。
[0071]分词完成后，对切分出的词条去除停用词，然后统计词条集合中相邻词的频率，生成一个双词频率表，为索引的创建做准备。
[0072]有了文本信息的索引，就可以基于索引进行了文本的检索，文本的检索方法是和相应的索引模型紧密关联的。
[0073]本发明还进一步包括步骤S300，接收用户输入的查询字符串，根据网页数据索引进行检索。对于不同的索引模型，具体的检索过程会不同。
[0074]在本发明的一个实施例中，将查询字符串分别分解为字和词，对于网页数据索引是字索引的情况，按字根据所述字索引来进行检索;对于网页数据索引是词索引的情况，按分词根据所述词索引来进行检索。
[0075]对于索引为二元内相关后续树模型的情况，具体的检索过程为:
[0076]第一阶段，针对网页数据索引是字索引的情况进行检索；
[0077]首先顺序读入查询字符串分解后的每一个字，取第一个字A，针对字索引，在二元内相关后续树中找到以A为根的树，然后在树A的叶子中逐个分支地匹配查询字符串的下一个字B，匹配到B的话则将B的后续编号加入队列，直到A的全部分支都匹配结束;转到以B为根的树，从队列中取出B树的分支号，查找相应的叶子结点来匹配字符串中的下一个字C，如此循环直到有一次匹配过程中没有匹配到或者查询字符串全部匹配结束，如果匹配成功，则意味着找到了包含查询字符串的原文；
[0078]第二阶段，针对网页数据索引是词索引的情况进行检索；
[0079]首先顺序读入查询字符串分解后的每一个词，取第一个词A，针对词索引，在二元内相关后续树中找到以A为根的树，然后在树A的叶子中逐个分支地匹配查询字符串的下一个词B，匹配到B的话则将B的后续编号加入队列，直到A的全部分支都匹配结束;转到以B为根的树，从队列中取出B树的分支号，查找相应的叶子结点来匹配字符串中的下一个词C，如此循环直到有一次匹配过程中没有匹配到或者查询字符串全部匹配结束，如果匹配成功，则意味着找到了包含查询字符串的原文。
[0080]本发明还进一步包括步骤S400，对检索到的结果进行排序，将排序结果展示给用户。
[0081]本发明不对排序方法进行限定，可以使用各种现有的排序技术对排序结果进行排序。
[0082]本发明一实施例中，为了提高检索效率，进一步的，针对网页数据索引是词索引的情况，将词索引文件中的索引词作为文本信息，基于所述内相关后续树模型对所述索引词再建立索引，从而进一步提尚检索的效率。
[0083]本发明采用二元内相关后续树模型为网页数据创建索引，同时考虑了字索引和词索引的优缺点，在减少索引空间的同时提尚了检索效率。
[0084]本领域技术人员在考虑说明书及实践这里公开的发明后，将容易想到本发明的其它实施方案。本申请旨在涵盖本发明的任何变型、用途或者适应性变化，这些变型、用途或者适应性变化遵循本发明的一般性原理并包括本发明未公开的本技术领域中的公知常识或惯用技术手段。
[0085]应当理解的是，本发明并不局限于上面已经描述并在附图中示出的精确结构，并且可以在不脱离其范围进行各种修改和改变。本发明的范围仅由所附的权利要求来限制。
【主权项】
1.一种基于树形结构的排序方法，用于中文搜索引擎中对中文网页数据的处理，包括: 步骤SlOO，网页数据预处理； 步骤S200，建立网页数据索引文件； 步骤S300，接收用户输入的查询字符串，根据网页数据索引进行检索； 步骤S400，对检索到的结果进行排序，将排序结果展示给用户。2.如权利要求1所述的基于树形结构的排序方法，其中，步骤S200中的所述网页数据索引文件是对处理后的网页数据所建立的网页数据索引组成的文件。3.如权利要求2所述的基于树形结构的排序方法，其中，所述网页数据索引为字索引和/或词索引。4.如权利要求2所述的基于树形结构的排序方法，其中，步骤SlOO进一步包括: 首先对抓取的原始网页进行分类，然后再按照分类分别提取网页中的文本信息，得到分类后的文本信息;生成网页索引文件的过程包括为原始网页的每个分类分别建立网页索引文件。5.如权利要求4所述的基于树形结构的排序方法，其中，所述网页数据索引是基于二元内相关后续树创建的索引。6.如权利要求4所述的基于树形结构的排序方法，其中，在步骤S200中，建立网页数据索引文件进一步包括: 首先，判断每个分类的文本信息的容量，当所述分类的容量小于IGB时，为所述分类的文本信息建立字索引，当所述分类的容量大于等于IGB时，为所述分类的文本信息建立词索引。7.如权利要求6所述的基于树形结构的排序方法，进一步包括: 将查询字符串分别分解为字和词，对于网页数据索引是字索引的情况，按字根据所述字索引来进行检索;对于网页数据索引是词索引的情况，按分词根据所述词索引来进行检索。8.如权利要求7所述的基于树形结构的排序方法，其中，在为所述网页数据建立词索引之前，还包括对文本信息进行分词的步骤，具备包括:利用分词词典对文本进行分词操作形成标引词集合。9.如权利要求8所述的基于树形结构的排序方法，所述分词操作具体包括: 采用基于PATRICIA树结构的词典，具体采用增量最大匹配法切分，即对于一个字串，从长度为2的子串开始，对A1A^1，在词典中查找是否是词，如果不是则将仏单独成词，然后子串后移一个字，继续查找Ai+1Ai+2;如果是词，则需要将子串长度加一，判断Ai+1Ai+2Ai+3是否是词，如果不是，则将A1+1A1+2切分出来，如果是则继续加一，直到查找不到词为止。10.如权利要求9所述的基于树形结构的排序方法，进一步包括: 分词完成后，对切分出的词条去除停用词，然后统计词条集合中相邻词的频率，生成一个双词频率表。
【专利摘要】本发明提出了一种基于树形结构的排序方法，用于中文搜索引擎中对中文网页数据的处理，包括：步骤S100，网页数据预处理；步骤S200，建立网页数据索引文件；步骤S300,接收用户输入的查询字符串，根据网页数据索引进行检索；步骤S400,对检索到的结果进行排序，将排序结果展示给用户。本发明采用二元内相关后续树模型为网页数据创建索引，同时考虑了字索引和词索引的优缺点，在减少索引空间的同时提高了检索效率。
【IPC分类】G06F17/30
【公开号】CN105488114
【申请号】CN201510817371
【发明人】陈虹宇, 罗阳, 苗宁
【申请人】四川神琥科技有限公司
【公开日】2016年4月13日
【申请日】2015年11月20日
最新回复(0)