数据结构

数据结构分为：结构化数据和非结构化数据。

• 结果化数据拥有固定格式或有限长度的数据，比如关系型数据库；
• 非结构化数据不定长度，不定格式，比如word文档等。

也有些地方提出半结构化数据，比如XML、JSON、HTML等，这些可以根据需求按结构化数据来处理。也可以提取纯文本按照非结构化数据来处理。

数据搜索

针对不同的数据结构，对数据进行搜索也是不同的。

结构化数据搜索

对于结构化数据来说，由于数据有一定的结构可以采取一定的搜索算法来提升搜索速度，比如数据库数据可以通过sql来进行搜索。

非结构化数据搜索

而对于非结构化数据来说，一种可以通过顺序扫描；另一种就是想办法将非结构化的数据转换成结构化的数据，这就是索引。

将非结构化中数据的一部分提取出来，重新组织，使其变得有一定结构，然后对这些有一定结构的数据进行搜索，从而达到搜索相对较快的目的。这部分从非结构化数据中提取出来然后重新组织的信息，称之为索引。

这种先建索引，然后对索引进行搜索的过程叫做全文检索(full-text search)。

全文检索的过程

全文检索大体分为两个过程：索引创建、索引搜索。

• 索引创建：将结构化或非结构化中的数据提取出来，创建索引索引的过程。
• 索引搜索：根据用户的查询请求，搜索创建的索引，然后返回结果的过程。

全文检索中三个重要的问题：

• 索引里面是什么？
• 如何创建索引？
• 如何对索引进行搜索？

索引里面是什么？

顺序扫描很慢的原因是因为要搜索的信息和非结构化的数据不一致造成的。正常情况下通过文件搜索字符串比较容易，即文件到字符串的映射。而我们要搜索的信息是字符串到文件，即要字符串到文件的映射。所以如果索引中能够存储字符串到文件的映射，则会大大提高搜索速度。这种存储从字符串到文件映射信息是文件到字符串的反向过程，所以这种索引称为倒排索引(反向索引)。

倒排索引中一般存储了一系列字符串，称之为词典。每个词都指向包含此此的文档链表，这个文档链表称之为倒排表。

全文检索，由于存在索引创建过程，所以不一定比顺序扫描快，尤其是小数据量情况下。但是索引只需建立一次，以后每次搜索都可以使用。全文检索相对于顺序扫描优势之一：一次索引，多次使用。

如何创建索引？

1. 获取原文档(Document)

2. 将原文档传递给分词组件(Tokenzine)

   • 将文档分成一个个单独的单词
   • 去除标点符号
   • 去除停词(语言中最普通的一些词，没有特殊含义，一般情况不能作为搜索的关键词，索引创建索引时候被去掉，减少索引量)

   对于每种语言分词器都有一个停词(Stop word)集合表。经过分词之后得到的结果称之为词元(Token)

3. 将得到的词元传给语言处理组件(Languistic Processor)
   语言处理组件将得到的词元做一些语言相关处理，比如大写变小些、将单词缩减为词根形式、将单词转变为词根形式。语言处理组件得到的结果称之为词(Term)

4. 将词传递给索引组件(Indexer)

   • 利用得到的词创建索一个词典，词典是每个词和词所在的文档id。
   • 对词典按字母进行排序。
   • 合并相同的词(Term)成为文档倒排链表(Posting List)。

   文档倒排链表中有几个定义：

   • Document Frequency(DF)：文档词频，表示总共有多少文件包含此词(Term)。
   • Frequency：词频率，表示此文件中包含了几个词(Term)。

如何对索引进行搜索？

1. 用户输入查询语句
   查询语句也有一定的语法，查询语句的语法根据全文检索的实现而不同，最基本的比如AND、OR、NOT等

2. 对查询语句进行词法分析、语法分析、语言处理

   • 词法分析主要用来识别单词和关键字。
   • 语法分析主要根据查询语句的语法规则来形成一棵语法树。
   • 语言处理和创建索引一样：变小写、将单词缩减为词根、将单词转变为词根。

3. 搜索索引，得到符合语法树的文档

4. 根据得到的文档和查询语句的相关性，对结果进行排序。
   
   找出词对文档重要性的过程称之为计算词的重要性(Term weight)过程。词的权重表示词(Term)对文档的重要程度，越重要的词权重越大，因而在计算文档相关性上面发挥更大的作用。判断词之间的关系从而得到文档相关性的过程应用一种叫做向量空间模型的算法(Vector Space Model)。

计算权重的过程

影响一个词在文档中的重要性，主要有两个因素：

• Term Frequency(tf)：即该Term在文档中出现了多少次，tf越大说明越重要。
• Document Frequency(df)：即多少文档包含了此Term，df越大说明越不重要。

这只是典型的计算方式，不同的搜索引擎有不同的实现。

判断不同Term间的关系从而得到文档相关性的过程，也就是向量空间模型算法(VSM)

把文档看成一系列词，每个词都有一个权重，不同的词在文档中的权重来影响文档相关性打分计算。把文档中所有词的权重看作一个向量

    Document={term1,term2,…,termN}
    Document Vector={weight1,weight2,…,weightN}

同样把查询语句也看作一个文档，用向量表示

    Document={term1,term2,…,termN}
    Document Vector={weight1,weight2,…,weightN}

这样把所有的查询结果放到一个N维空间，然后通过计算夹角来为相关性打分，夹角越小，打分越高，相关性越大。