一种基于启发式方法的信息搜索方法

摘要

本发明涉及一种基于启发式方法的信息搜索方法，其步骤包括：根据信息的特征确定与信息重要性相关的参数类型，每一参数类型包含至少一个关键字，同类型参数内的关键字分成不同级别并设置不同的权值；采用散列方式存储各参数类型、关键字及其权值，并建立索引；对于每一条待定信息，获取其关键字向量并在所述索引中找出关键字及权值，对不同类型参数内的关键词的权值进行合并得到该信息的权值，然后以权值上限减去该信息的权值得到启发信息；根据启发信息运用启发算法得到每一条待定信息的总估价，进而确定最有价值的信息并输出搜索结果。本发明的启发式搜索方式保证了信息的时效性，可以节省计算时间与空间，提高信息搜索效率和准确率。

说明书

技术领域

本发明属于网络技术、信息搜索技术领域，涉及一种基于启发式方法的信息搜索方法。

背景技术

目前信息搜索、检索技术已取得了很大发展。一些信息比如新闻等具有时效性、地域性、 政治性等特点，对于如何搜索最有价值的信息是一个典型的NP难题。对于重要信息的定义， 不同的国家，不同的地域、不同的媒体都是千差万别的，如何在众多的信息中，自动搜索出 最有价值的，必须选择一种有效的策略。

此类NP问题一般具有求解条件不完备、不确定性等特点。用常规的搜索算法很难搜索 到最优的结果。现有的一些方法，存在搜索效率低、计算时间与空间耗费过多的问题。现在 计算重要信息主要是通过关键词搜索和聚类两种思路，但是这两种思路都有相应的缺陷，比 如：关键词搜索主要通过关键词命中次数来定义信息的重要性，虽然效率很高，但是准确度 很差；聚类方法虽然精确度很高，但是存在计算时间过长，时效性不够的缺点。

启发式搜索算法是解决NP难题时常用到的一种算法。启发式算法的运用综合了关键词 搜索和聚类的优点，在保证时间及时性的同时，提高重要信息搜索的准确度。下面对启发式 算法做一些简要介绍。

启发式搜索的基本思路是：预先确定好一个函数，它能反映该结点与目标结点的接近程 度，这个函数叫启发函数（heuristic function)。启发式搜索就是在问题状态空间中对每一个搜 索的位置进行评估，由此得到最好的位置，再从这个位置进行搜索直到解决问题。应用此算 法可以节省无谓的搜索路径，提高搜索的效率。

在启发式搜索中，对位置的估价是十分重要的，不同的估价可能有不同的效果。启发算 法中启发函数的具体构造如下：

f(n)=g(n)+h(n)

其中f(n)表示对节点n的总估价，g(n)表示从起始状态到节点n的已知估价，h(n)表示节 点n本身的预测估价，即启发信息。

例如博弈树的搜索过程是一个典型的启发式搜索，如图1所示。采用启发函数表示该图 中的节点信息，在f(n)=g(n)+h(n)中，g(n)表示节点所在的深度，h(n)表示节点的启发信息。 如何选择启发信息是此种算法的关键。在这里启发信息是黑下完一手白方填满相应的空白格 后所能连成线的数目。白方连线越少，表明黑方下的越成功。在上述节点各子节点的估价由 左到右为f(1)=g(1)+h(1)=1+2=3，f(2)=2,f(3)=2,f(4)=2,f(5)=2。由上述函数可以得出，第一个节 点代价较高，就不再考虑了。

发明内容

现有的信息搜索方法，尤其是对于如何搜索最有价值的新闻、论坛等信息，现有方法还 无法很好的解决，存在搜索效率低、计算时间与空间耗费过多的问题。本发明提供一种基于 启发式方法的信息搜索方法，可以节省计算时间与空间，提高信息搜索效率。

为实现上述目的，本发明采用的技术方案如下：

一种基于启发式方法的信息搜索方法，其步骤包括：

1）根据信息的特征确定与信息重要性相关的参数类型，每一种参数类型包含至少一个关 键字，将同类型参数内的关键字分成不同级别，并对各级别设置不同的初始权值，将不同类 型参数的最大的关键字权值相加作为权值上限；

2）采用散列方式存储各参数类型、各参数类型对应的关键字及其权值，并建立索引；

3）对于每一条待定信息，获取其关键字向量，并在所述索引中找出对应键字及相应的权 值，通过对不同类型参数内的关键词的权值进行合并得到该信息的权值，然后以所述权值上 限减去该信息的权值，得到该信息的启发信息；

4）根据所述启发信息，运用启发算法得到每一条待定信息的总估价，进而确定最有价值 的信息，并输出信息搜索结果。

进一步地，步骤3）通过分词处理获取所述关键字向量。

进一步地，步骤4）所述启发算法采用的启发公式为：

f(n)=g(n)+h(n)，

其中，f(n)为总估价，g(n)为信息的本身价值，h(n)为启发信息。

进一步地，所述启发公式为多启发函数：

f(n)=g(n)+h1(n)+h2(n)，

其中，f(n)为总估价，g(n)为信息的本身价值，h1(n)为转载率决定的启发信息，h2(n)为关 键字决定的启发信息。

进一步地，g(n)由信息在网站页面的位置决定，越重要的位置权值越小。

进一步地，步骤4）还根据不同信息的价值对信息进行排序。

本发明采用启发式搜索，在状态空间中对每一个搜索的位置进行评估，得到最好的位置， 再从这个位置进行搜索直到目标结果集。该启发式搜索方法解决了单纯关键词搜索的准确性 问题，同时有保证了信息的时效性，从而提高了信息搜索效率，是解决信息重要性问题中达 到实际工程应用的一种解决方案。

附图说明

图1是启发式搜索的实例介绍示意图。

图2是实施例中应用启发式方法进行新闻搜索的示意图。

图3是实施例中启发式算法的流程图。

图4是实施例中采用现有的关键词搜索方法的信息发现结果。

图5是实施例中采用本发明的启发式搜索方法的信息发现结果。

具体实施方式

下面通过具体实施例和附图，对本发明做进一步说明。

本实施例中的信息为具有时效性、地域性、政治性等特点的新闻信息，在两天内不同时 段进行六次对重点新闻的采样，其中门户网站以新浪为主要来源，主要参照媒体搜狐，次要 参考qq新闻和网易；搜索网站主要参考百度和Google。

经过分析，门户网站重要新闻有以下特点：以国内新闻为主，以新浪为例在24条新闻中 国内新闻占18—20条。百度新闻频道重要新闻32条，国内新闻23-25条。

国内新闻特点一般具有下述特点中的一条或几条：1）国家领导人或有突出贡献的名人； 2)突发事件；3）国家关系特别是大国关系；4）地理位置；5）媒体重要报道；6）农民问题； 7）反腐倡廉；8）本媒体新闻；9）重要政策性新闻。

国际新闻有以下几条特点：1）重要国家重要活动；2）突发事件；3）军事事件；4）民 主与人权；5）重要国家领导人。

根据以上特点，首先为启发式搜索作一些共用设定。其中一个推论是：在一定时期，每 一条新闻的价值，亦即权值有一个相对固定的上限。新闻的特点确定后，将每一种特点定义 为一个参数类型，而且至多一个参数；每一个参数类型下至少包含一个关键字。对于各参数 类型及关键字规定如下：

1）每个参数类型本身没有权值，其权值由其下属的关键字决定。

2）参数内的关键字可按照重要性分成不同级别，不同的级别的关键字有不同的权值。例 如国家领导人可以分级，国家主席、总理为第一级，厅局为第二级，第一级为10分，以下逐 步降低。

3）同参数内的关键字不重复计算。

4）不同的参数间可以进行权值合并运算。

5）突发事件权重加大。比如灾难、恐怖事件等。

作了上述假设后，对关键字采用散列方式存储，以参数为索引。针对每一条新闻，通过 索引搜索确定其启发信息，具体处理流程如下：

a)查找每一条新闻，通过分词处理找出其关键字，然后在索引中找出关键字及对应的权 值。

b)一条新闻进行匹配时，相匹配的不同参数类型下的关键字越多，每个关键字级别越高， 那么这条新闻的权重越大。通过对不同类型参数内的关键字的权值进行合并，得到该新闻的 权值。

c)以事先固定的权值上限减去上一步计算得到的该新闻的权值，得到的权值为这条新闻 的启发信息。

上述“权值上限”通过将不同类型参数内的最大的关键字权值相加得到。比如有3个参 数类型：

参数1：关键字1的权值为10；关键字2的权值为9，关键字3的权值为8；

参数2：关键字1的权值为9；关键字2的权值为7；

参数3：只有1个关键字，权值为8；

则权值上限为：10+9+8=27。

上述“对不同类型参数内的关键词的权值进行合并”，是将从索引中查找到的各关键字的 权值相加。比如，仍以上面3个参数为例，对于一条新闻，若从索引中查找得到的对应的关 键字为参数1的关键字2和参数2的关键字1，则将查到的该两个关键字的权值相加，即 9+9=18，作为该条新闻的权值。进而用权值上限减去该条新闻的权值，得到该条新闻的启发 信息。

当然，在搜索空间展开时，仍然有一些重要的启发信息加入进来。例如，当头条新闻展 开时，如果在多家媒体他都是头条，那么这条新闻的权重为0，理所当然地成为头条新闻。 有时这条新闻是本网内部的新闻，那这条新闻可以定义为权值极大，这条新闻没有价值。

相应的启发公式可以设定为多启发函数：

f(n)=g(n)+h1(n)+h2(n)

其中，f(n)为总估价（即新闻的总的价值、总的重要性），g(n)为新闻位置等决定的本身 价值，h1(n)为转载率等决定的启发信息，转载率是在信息获取的时候，通过计算相同新闻的 数量而得到，h2(n)为关键字决定的启发信息。

现在考虑一种启发信息的情况，即由关键字决定启发信息的情况：

f(n)=g(n)+h(n)

其中g(n)为新闻的在网站页面的位置所决定的，越重要的位置权值越小，h(n)是新闻的启 发信息，是由关键字决定的，由确定的新闻价值上限减去这条新闻权值得到的。因此越重要 的新闻权值越小。

图2是应用上述方法进行新闻搜索的示意图，其中第一层为新浪的起始节点，第二层为 不同的重要新闻，第三层为新闻的不同标题。如该图所示，暂时只考虑一种启发信息。先从 新浪新闻A中找出五条新闻，利用启发算法找到相对价值较大的一条，如A1，然后再搜索 出与此新闻相关的标题，再利用启发算法找到最有价值的标题，如A11。当然也可以搜狐为 出发点，搜出重要新闻后，然后二者相比较，按权值的大小进行新闻的排序。

启发式算法的流程如图3所示，对其具体描述如下：

首先，设OPEN表和CLOSE表，OPEN表存储未搜索的节点，CLOSE表存储已搜索的 节点。

Step1：把初始节点S0放入OPEN表；

Step2：若OPEN表为空，则搜索失败，退出；

Step3：若OPEN表不为空，移出OPEN表中的第一个结点放入CLOSE表中，记该结点 为N；

Step4：若N=目标结点，则搜索成功，结束；

Step5：若N不可扩展，转到Step2；

Step6：扩展N，生成一组子结点，将这些子结点放到OPEN表中；

Step7：按估价函数f(n)对OPEN表中的结点从小到大排序，转到Step2。

经过对同一批数据的算法应用比较，在使用之前的基于关键词搜索算法时，重要信息发 现经和新浪、搜狐和百度对比，在前10条中，命中3条，如图4所示；在运用本发明的启发 式搜索方法后，在前10条中，命中6条，如图5所示，准确率相对之前的算法，提高了100%。

尽管为说明目的公开了本发明的具体实施例和附图，其目的在于帮助理解本发明的内容 并据以实施，但是本领域的技术人员可以理解：在不脱离本发明及所附的权利要求的精神和 范围内，各种替换、变化和修改都是可能的。本发明不应局限于本说明书最佳实施例和附图 所公开的内容，本发明要求保护的范围以权利要求书界定的范围为准。