开发,设计,生活

开发相关

  • 2012-09-28 11:42:31 2013-02-07 08:34:27[U] 开发相关

     sphinx-indexer 创建索引的算法,和数据结构分析

    1 概述

    这是基于开源的sphinx全文检索引擎的架构代码分析,本篇主要描述index索引服务的分析。 index的功能根据输入的数据创建索引文件,提供给searchd服务查询使用。 当前分析的版本 sphinx-2.0.4

    2 index 功能

    • 读取配置文件,解析输入数据源
    • 根据数据源,循环索引
    • 创建索引文件/合并索引

    3 文件表

     

    3.1 配置文件描述

     

    3.1.1 存储模式

    文档信息的存储模式,可选选项,默认值 extern

    • none 不保存文档信息,不保存属性
    • inline 文档信息与文档ID列表一同存储在spd文件中
    • extern 文档信息与ID分开存储在spa文件中

    3.1.2 索引部署模式

    • plain 本机索引(默认)
    • distributed 远程索引

    4 索引文件结构

     

    4.1 spa 文件

    存储文档属性,在extern文档信息存储模式下使用。

    spa文件格式 => 属性值存储
    itemitemitemitemitem
    docidattr0attr1attr mva(spm file position)
    spa文件格式 => 在文件的末尾存储每个属性的最大最小值
    itemitemitemitemitemitemitem
    attr0 minattr1 minattr0 maxattr1 maxattr mva max

    4.2 spi 文件

    存储词列表,词id和指向spd文件的指针。

    • wordid 采用crc32编码
    • 每64个word插入一个检查点,重新开始存储wordid和spd文件偏移的差值
    • 保存doc的计数值,hit的计数值
    spi文件格式 => 倒排索引存储
    itemitemitemitem
    wordid(crc32)或vlbspd文件偏移的差值doc的计数值hit的计数值
    spi文件格式 => 文件的末尾存储文件内的检查点信息
    itemitemitem
    checkpoint1 sWord lensWord在文件内的 offset

    4.3 spd 文件

    存储每个词id可匹配的文档id列表。

    文件格式 => 只有一次命中的时候
    itemitemitemitem
    docid vlbhit counthit fieldhit position
    文件格式 => 多次命中的时候
    itemitemitemitem
    docid vlbhit countfield maskhit file(spp) position 差值

    4.4 sph 文件

    存储索引头信息。

    格式0
    item0item1item2item3item4
    versionbitsdocinfo modeschemamin doc
    格式1
    item5item6item7item8item 9
    ckpoint posckpoint counttotal doctotal bytesindex setting
    格式2
    item10item 11item12item13
    tokenizerdictionarykill listmin max index

    4.5 spk 文件

    存储kill-lists信息。

    4.6 spm 文件

    存储mva数据

    • 分块存储
    • 多路归并排序,创建spm文件
    spm文件格式
    itemitemitem
    docidA a0,a1,a2 …B b0,b1,b2 …

    4.7 sps 文件

    存储字符串属性

    4.8 spp 文件

     

    4.8.1 第一次扫描创建的命中文件(临时存储命中信息)

    存储每个词的命中数。

    • 文件内分块存储
    • 块内同类递增排序,优先级为 wordid > docid > hitpos
    • 在wordid,docid相等的条件下,hitpos差分存储
    • 在wordid相等的条件下docid差分存储
    • wordid差分存储
    hit block 的存储结构列表如下
    itemitemitemitemitem
    wordid0docid0pos0, pos1, pos2 …hitcountfield mask
     docid1pos0, pos1, pos2 …hitcountfield mask
     docid2pos0, pos1, pos2 …hitcountfield mask
    wordid1docid0pos0, pos1, pos2 …hitcountfield mask
     docid1pos0, pos1, pos2 …hitcountfield mask

    差分注解:

    • 0, wordid0, wordid1 … 差分
    • 0, docid0, docid1, docid2 … 差分
    • 0, pos0, pos1, pos2 … 差分

    4.8.2 最终创建的spp文件格式

    当doc切换后存储的第一个是hit position, 后面存储的是差值。

    spp文件存储格式
    item
    hit position 差值

    4.9 sps 文件

    存储字符串属性数据。

    4.10 同义词文件/Synonym

    同义词文件格式
    from=>to
    AT &T=>AT&T
    AT & T=>AT & T
    standarten fuehrer=>Standartenfuehrer
    standarten fuhrer=>Standartenfuehrer
    Ms-Dos=>MS-DOS
    MS DOS=>MS-DOS

    5 算法

     

    5.1 字典

    double array trie 检索树

    5.2 分词算法

    逆向匹配的切分精度略高于正向匹配,歧义较少。 统计结果表明,单纯使用正向最大匹配的错误率为1/169,单纯使用逆向最大匹配的错误率为1/245。 对于机械分词方法,可以建立一个一般的模型,形式地表示为ASM(d,a,m),即Automatic Segmentation Model。其中,

    • d:匹配方向, 1表示正向,-1表示逆向;
    • a:每次匹配失败后增加/减少字串长度(字符数), 1为增字,-1为减字;
    • m:最大/最小匹配标志, 1为最大匹配,-1为最小匹配。

    5.3 文档id压缩 – Variable Byte Coding

     

    5.4 索引存储 – 多路归并排序

     

    6 线程模型

     

    7 程序内部数据结构

     

    7.1 建立索引 build index

     

    7.2 word position

    Hitpos
    field idmark endword pos
    1byte1bit23bit

    7.3 程序流程结构

     

    7.3.1 创建索引过程

    • 扫描配置文件。
    • 创建程序内部数据结构,schema, mva attr等。
    • 第一次遍历文档记录,连接数据库读取创建索引的记录。
    • 循环分词创建spa, spp文件(临时格式)(如果inline模式只创建spp文件), 如果非inplace模式,那么创建对应 tmp->spa, tmp->spp对应文件。
    • 第二次遍历文档记录,创建mva属性(非field mva attributes)。
    • 多路归并创建spm文件。
    • 更新并创建最终的spa文件,更新mva的位置信息到spa文件。
    • 读取临时格式的spp文件,多路归并创建spi,spd,spp文件。
    • 创建索引头文件sph。
    • 更新索引创建后的信息(例如存储当前已经简历索引的)释放资源