搜索部分核心算法1 - TheCAT Project

搜索部分的核心算法
create table ***(
keyword varchar(20);
BinaryStream BinaryStreamType;
);
BinaryStream is an vector of
struct {
  FileId :FileIdType // such as int(10);
  index :SmallInt; //记录了 keyword在FileNameOf(FileId)中的位置，
           //如果FileNameOf (FileId)中多次包含了keyword这个词,则将 index设为零
           //sample: "ld"在"world"中的位置为 4
           // so we set the index 4
  }
and the vector is ordered by FileId     //*** this is very important

假设存在这样一个文件名"HelloWorld" 并设其fileid 为 FileIdOf("helloworld")
当我们搜索"world"这个词时,
我们就取出 "wo" "rl" "ld" 分别对应的BinaryStreamOf("wo") , BinaryStreamOf("rl"),BinaryStreamof("ld")
从中我们发现了 FileIdOf("helloworld") 是这三个 BinaryStream 的交集中的元素
并且 index("wo",FileIdOf("helloworld"))=6;
   index("rl",FileIdOf("helloworld"))=8;
   index("ld",FileIdOf("helloworld"))=9;
   他们之间的差满足一定的关系，相信大家一眼就可以看出
这样我们就可以确定这个FileId 对应的那个 FileName一定含有 "world"这个词，而不是"worrld"，”or wo ld" 之类的词

前面提到过 fileid要按大小顺序排列
这样的作用是取交之时比较方便 ,时间复杂度为 length(vector("wo"))+length(vector("rl"))+length(vector("ld")
也就是说只要对vector 进行一次遍历就够了