一种用于数据检索的搜索系统和方法及其在搜索引擎中的应用

摘要

一种用于信息检索的搜索系统包含一个用于存储正文T中的数据结构，一个包含分别关于正文T字和/或符号及其序列和序列P中的字和/或符号之间的匹配的近似程度的编辑距离尺度的组合尺度M，对将序列S的字或符号转换成序列P的编辑操作的成本函数进行加权；和用于分别确定分别在正文T和查询Q的后缀树表示中的字或字序列之间的匹配程度的搜索算法。该算法以查询Q搜索该数据结构，以与该查询的具体匹配检索信息。该搜索系统的一种用于信息检索的方法生成字间隔稀疏后缀树用于存储正文T中的字的后缀作为字序列信息，以及一个用于字序列S和P的与字的大小有关的编辑距离尺度，并且包括编辑距离的字加权成本函数，以及通过计算关于所有匹配的编辑距离确定字序列SR或被检索的信息R与一个查询Q的字序列PQ之间的匹配程度。还公开了该搜索算法在近似搜索引擎中的应用。

主权项

1．一种用于信息-特别是以正文T的形式存储的信息-检索的搜索系统，其中，信息检索以查询Q与被检索信息R之间的给定或不同程度的匹配而发生，其中，该搜索系统包含一个用于存储正文T的数据结构，一个测量查询Q与被检索信息R之间匹配程度的尺度M，以及用于执行搜索-特别是以键字为基础的全文搜索-的搜索算法，其特征在于，该数据结构包含一个以后缀树ST(T)为形式的树结构，用于存储正文T中的字、字序列和符号序列的后缀；尺度M包含关于正文T中的字或符号与查询Q之间匹配的近似度的编辑距离尺度与关于正文T中的字或符号的序列S与查询序列P之间匹配的近似度的编辑距离尺度的组合，后一个编辑距离尺度包括对将一种字或符号的序列S转换成另一种字或符号的序列P的编辑操作的成本函数进行加权，该搜索算法包含用于确定正文T与查询Q各自的后缀树表示中的字之间的匹配程度的第一算法和/或用于确定正文T与查询Q各自的后缀树表示中的字的序列之间的匹配程度的第二算法，所述第一和/或第二算法用以字、字序列、符号序列或者它们的组合为形式的查询Q搜索数据结构，使得信息R被根据查询Q而检索出来，前者与后者之间具有规定的匹配程度。