[zz]打造自己的分布式搜索引擎底层架构（非Lucene）

打造自己的分布式搜索引擎底层架构（非Lucene）

大家知道，搜索引擎技术不仅仅是类似百度首页的应用，还可以衍生出数据分析工具，商务智能工具等许多有卖点的应用，甚至是社会化关系通道的发现。
甚至这些非搜索引擎的搜索引擎产品才是最重要的，因为你不需要去做百度做的事情。
所以，搜索引擎技术要了解原理，才可以扩展，离开Lucene也能做搜索引擎是非常重要的，利用这个积木，我们可以搭建房子和汽车。

搜索引擎要完成的目的，就是O(1)秒杀爬虫采集来的文章里关键字的搜索，丫的和数据库Like不同的效果优点是速度快，缺点是如果没建索引的字，搜不到。

本文是针对：打造一个自己的搜索引擎服务器的积木底层模块，给大家扩展思路和分析知识，同时为我下一步的工作打下基础。
但是这个基本思路我要保证是靠谱的，并且可以达到给大家分享数据结构知识的目的。

  
做自己的搜索引擎（非Lucene），需要两大几方面的知识：

一，简单够用的分布式；

二，基本的数据结构和算法，知道复杂度和数据结构的对应关系。

重点是二

所以本文会花时间讲解如何利用.Net自带的集合干这个事儿。

 

先快速把一部分带过：

1，文件+数据库服务器群，首先你要有大量的文章，爬虫采集来的或者你用啥办法搞来的，这些按T计算的文章一个机器放不下，也没必要放一起，因为硬盘并发性能比较差，你需要有一堆机器是存放这些文件的，处理文件的事儿，交给这些机器并发去处理，而不应该是

一个机器排队处理，如果用.NET来做WCF架构比较合适，WCF自己去搜索，本文不细谈。

2，Web服务器群，数据库要应付大量搜索请求，搜索引擎才有意义，所以Web负载均衡和反向代理是必要的，自己去搜反向代理，Nginx,Squid之类的词，本文不讲。

3，MemChached群，是分布式的哈希表，一个机器放不下我们期望的内存数量，自己去搜MemChached，本文不讲。

4，索引服务器群，就是定时或者一直在忙活简历索引的后台服务器，单独搞几台。

总之你需要4群服务器，每个群的数量看需要和你的钱数调整，没钱就都搞一个机器上，如果只是实验的话。

下面是本文的关键部分。
先说数据结构的原理：（数据结构和算法要解决的基本问题就是搜索和排序）

1，搜索：查找一个东西有还是没有，复杂度是O(1),哈希表，搜索引擎就是利用哈希表的这个特性,其他O(n)或O(logN)的搜索不适合干这个。
2，排序：如果大家都有，那么哪个文章词出现的频率就是决定显示的排序，排序，职业的做法是O(N*logN)时间空间都OK，如果你说只学过冒泡，那你拿鼠标拍自己的头吧,赶紧找本书看看为啥冒泡O(n^2)是业余的。
3，动态排序的概念是对于新插入的元素能以O(LogN)的复杂度到达自己应该站的位置，一般做法是二叉堆，在.Net里是SortedList<T,T>泛型容器，至于里边实现，不管他，反正满足我们需要的复杂度。

好，以上三个概念是我们解决一切问题的出发点，复杂度和数据结构的对应关系一定要形成大脑的条件反射，不需要你非要数据结构考试85分，但是这种意识是优秀程序员必备的。

分析搜索的过程：
0，高频字典：我们提前准备个高频字典，是哈希字典容器Dict<WordID(int),Word(string)>；这个可以放在集群MemCached里，也可以按照你的机器数量分段存放。

1，输入检验：用户输入一个词，先检验这个词在词典里要有编号，没编号的加进去，当然新放的不可能被搜到，建立索引后下次才能被搜到；

2, 哈希搜索：要达到O(1),我们必须知道这个词对应哪些文章。需要这样一个哈希字典容器Dict<WordID(int),SortedList<DocID(int),Freq(int)>>；这样能返回一堆排序好的文章。我们先假设按照词的频率去排序。

3，初始化分词：为了实现SortedList<T,T>，我们在第一次初始化分词，就是把文章里出现的二字，三字，四字长的等词汇，找出来，按照出现的频率进行排序，这个以文章为索引的也要建立。Dict<DocID(int),SortedList<WordID(int),Freq(int)>>
 http://topic.csdn.net/u/20070914/17/9A27E63A-CAD6-4955-8E14-61DC9357A8AD.html这里有我以前写的例子，本文不细说了。

4，分词作业：为了保证用户输入的都被索引，分词要形成作业，就是有个后台程序不断的维护这个搜索引擎的分词索引，还要及时把索引序列化到文件里，保存起来，以便下次开机后不需要再计算。

5,新加的文章需要进行3的步骤，新加的用户词汇，比如“给力”需要进行4的步骤。

其他辅助步骤
1，爬虫采集数据，文章的粒度，新闻要大文本存放，不论是数据库的Text字段还是纯文本，都要把HTML标签分解开来，如果对于微博，要分解到用户ID,文章ID，转发ID，粉丝ID等可以被计算的数值。
2，语义分析，如评论的正面还是负面，需要分拣数据，人工赋予智能。
3，文章重复或者相关性检测，利用关键字分布的频率，余弦算法（自己去搜索）来计算相似度。