之前介绍过倒排索引,不过因为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在原文中的位置, 然而实际上, 我并没有使用它们.
  • 其四, 之前提到的, 负载均衡之类的事情, 我开了个头, 但并没有做下去. 只能等有空再说了.

Yu

Ideals are like the stars: we never reach them, but like the mariners of the sea, we chart our course by them.

4 Comments

Jingyuan Liu · October 29, 2015 at 03:04

Google Chrome 46.0.2490.71 Google Chrome 46.0.2490.71 Mac OS X  10.10.5 Mac OS X 10.10.5

As for the TODO list point 3, what is the use for integrating the citation num into an inverted index? For ranking?

By the way, if you want comments from America, you should do it in English, hahahahah.

    yu · October 29, 2015 at 09:35

    Google Chrome 46.0.2490.80 Google Chrome 46.0.2490.80 Mac OS X  10.11.1 Mac OS X 10.11.1

    @Jingyuan Liu
    Yep, I do wanna to add the position of terms, citation number of papers and something else into ranking, those information are all important features to boost the result.

    yu · October 29, 2015 at 09:42

    Google Chrome 46.0.2490.80 Google Chrome 46.0.2490.80 Mac OS X  10.11.1 Mac OS X 10.11.1

    @Jingyuan Liu additionally, give my project one more fork plz!

    https://github.com/argcv/argcv <<<< this one !

Leave a Reply to Jingyuan Liu Cancel reply

Your email address will not be published. Required fields are marked *