一个c++的索引总结

之前介绍过倒排索引,不过因为python实现的,效率够呛,而且因为是demo,很多细节完全没有考虑. 最近用c++断断续续终于写了一个稍微更好一点的程序(的半成品),若有兴趣,求 fork & star.

最近的习惯是准备一个比较统一的c++库,然后外面包一个具体业务的工程.这个工程也同样.它的很多底层的内容是在如下工程实现的.

从原理上说,它和之前的倒排索引其实别无二致,虽然有好多自以为绝妙的想法,可惜暂时没空,只能匆匆先弄个结果出来.

索引的目标是作为一个业务级别服务(通常可能是java,scala,python等)的后端作为它的身份,因此对外使用的是程序接口而不是基于http的RestFul形式接口.作为一个简单的程序, 它从前到后大致需要三个部分:

• TCP连接服务. 作为一个后端的后端,仍然需要有对外交互的通道
• 索引逻辑. 倒排索引的数据存储需要有一些特别的格式,以便查询
• 存储服务. 底层的数据存取(主要是各种键值对)

终于好像跑通了, 我打算介绍一点经验, 希望下次能比较好的绕开这些坑. 若能很神奇的帮助到了某个路过者, 那更是惊喜.

工程组织

首先需要使用一个工程来组织整个系统. 作为一个c++工程, 个人特别喜欢cmake, 因为cmake可以比较容易的处理依赖关系, 很多时候, 可以写很多general的代码, 以后依赖起来也很方便. 这一次的工程也是如此, 只需要在工程中添加几行代码, 即可很容易复用yuikns/argcv, 我一直在慢慢造的轮子集合.

ADD_SUBDIRECTORY(lib/argcv) # 添加子工程
INCLUDE_DIRECTORIES(${ARGCV_INCLUDE_DIR}) # 将子工程头文件加入搜寻路径
LINK_DIRECTORIES(${ARGCV_LIB_DIR}) # 将子工程库文件加入搜寻路径

需要依赖leveldb等开源工程的时候也很容易可以使用.cmake脚本一次调试多次使用.

不过偶尔也有不靠谱的时候, 若没有网络, 麻烦会非常大.

TCP服务

TCP的服务是一件非常简单方便的事情, 代码可以在此处看到, 可以看出,其实就是调用库文件tcp_listen.hh, 这个头文件之前介绍过. 其实就是按照云风的那篇博客为思路, 一路改吧改吧弄出来的. 本次其实也就是对那段代码的一个简单的应用.

实际使用中,为了保证客户端能正常交互,我设置成了先发送长度,再发送具体内容.若内容没有完全收到,则不开始下一步.

对于交互所用的数据格式, 我本来想用json来整的, 然而可惜并没有找到很好的库文件, 从c++角度看,无论效率还是代码编写都并不如人意. 所以使用protobuf作为内容. protobuf在cmake中工作并不困难, 虽然直接使用cmake的系统脚本有时候好像有点问题, 不过一些简单的改进即可搞定, 可以参考这个例子. 而在sbt管理的scala工程中, 一些简单的插件也可以让事情变得很简单. (挖个坑以后填).

索引逻辑

索引本身是基于TF-IDF的一个实现,计算公式也很容易, 它有很多变种, 我就取一种简单的.

首先已知一段文本, 对它进行stemm, tokenlize, analyze. 然后把结果存储.

存储的时候, 我会把信息编码. 因为最后存储的时候使用的是leveldb, 它有一个很好的特性, 它是字典序的, 因此可以很容易做出寻找"以xxx为前缀的"之类的工作. 因此我们可以把term,field name等作为前缀, 回头我们可以非常快得定位到目标. 其次, 我把多个信息放在一个key里面,这样就可以不用额外的查询来获取信息了. 比如uuid, 这是两个uint64_t的类型, 因此我只要附加在key的尾部,回头从后往前倒推即可还原数据.

而plain text的文本, 我则使用'\0'作为间隔. 这样可以很有效的识别文字,而不用费心先记录长度再记录内容了.

存储服务

系统使用leveldb作为实际存储服务.不过我使用了一些wrapper来包装了下它.主要是我以后想要再扩展一些其它的底层数据服务, load balance什么的我觉得还是蛮重要的.

TODO

• 其一, class tcp_listen本来非常适用于多线程的,而且相关代码其实也不困难, 代码编写过程中我也一直在保证线程安全, 只是调试多线程比较麻烦, 时间所限, 所以只能以后再说了.
• 其二, analyzer什么的目前做得还是特别特别简单, 甚至停用词都没有准备, 只是去除了一些符号. 我觉得这样很不好. 此外, 中文分词也是一个很有趣的问题, 52nlp有一篇科普讲的就是这个, 而现在还有人过一些词条可以作为资源. 实现其实并不很困难, 我打算最先把它给实现了
• 其三, 我仅以文本相似为匹配依据. 其实计算公式还应该更复杂一些. 比如本次, 我其实是存储了一些论文, 我完全可以把文章被引次数加入计算--然而我并没有.此外, 比如搜寻"data mining", 通过analyzer, 它被分成data和mining两个词分别搜索, 然后结果合并. 我存储了data和mining在原文中的位置, 然而实际上, 我并没有使用它们.
• 其四, 之前提到的, 负载均衡之类的事情, 我开了个头, 但并没有做下去. 只能等有空再说了.