所谓URL智能匹配，简单来说，就是要在内存中实现一个微型的搜索引擎。为了便于说明，假设需要识别的只有以下这5个网站，网站名称对应搜索引擎中的术语是“文档”，每个文档都有其对应的ID、文档长度和URL ID（其实是URL ID列表，下文再解释，这里姑且认为就是URL ID）。
整个URL匹配过程的核心部分，可细分为三个步骤：
- 把用户输入文本按倒排索引查找最匹配的一个文档ID，详见“匹配文档ID”一节；
- 按文档ID查找URL ID列表，详见“查找URL ID列表”一节；
- 对每个URL ID查找对应的URL，详见“查找URL”一节。
一、匹配文档ID
1. 倒排索引
倒排索引（Inverted Index）是搜索引擎的基石，它用来存储在全文搜索下某个字（或者单词）在文档中的存储位置的映射关系。以红黑树方式表达（具体实现可多样化，不一定使用红黑树）的倒排索引结构如下。其中，圆形节点（key）是倒排索引上的字，矩形方框（value）是一个列表，每个列表元素表示该字对应的文档ID和该字在该文档中出现的位置。例如，“百度百科”在上表中，文档ID为173，“百”字是其中的第1个和第3个字，那么就表示为“173.1.3”。
2. 最长公共子序列
怎样利用倒排索引搜索是核心中的核心。在这里，还要引入一个最长公共子序列（Longest Common Subsequence）的概念。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件的序列中最长的，则 S 称为这些序列的最长公共子序列。要注意子序列subsequence不同于子串substring，子序列不要求连续，而子串要求连续。
LCS与两段文字的比值可以描述两段文字之间的雷同程度，从而可以推导出一个非常有用的位于0和1之间的小数，这个小数可以称为匹配度，它有两个非常实际的应用，一是反抄袭，二是搜索：
因此，URL智能匹配的思路就是，对用户输入文本，通过倒排索引逐个与URL配置库中的锚文本（URL对应的名字）计算LCS和匹配度，然后匹配度最大的锚文本对应的URL就是用户想要的搜索结果。
3. 搜索步骤
展开来说，搜索步骤如下：
- 使用一个X*Y的二维数组（以下记为array[X+1][Y+1]，下标都从1开始，第0行和第0列目前都看作是冗余空间），来记录用户输入的每个字在倒排索引中的位置信息，该二维数组每一行对应一个文档，实际应用中，除了第0行以外，有多少文档，二维数组就有多少行，也就是说，X是文档数量；每一列对应文档位置，Y是最长的那个文档的长度。
- 记录了每个字的位置信息之后，就可以分别计算用户输入文本与各个命中的文档的LCS长度。
- 再使用上述公式计算各个命中的文档的匹配度。
- 最后在多个匹配度中，取最高、且超过阈值的那个文档ID。
4. 实例分析
为了便于理解，再举个例子，假如用户输入文本是“上微博”，处理过程如下：
- 初始化array[X+1][Y+1]，数组全部数据清零；
- 处理“上”字，倒排索引没有命中该字，二维数组没有任何修改；
- 处理“微”字，倒排索引能够命中该字，而且是文档ID为520（微博）的第1个字和文档ID为250（腾讯微博）的第3个字，于是，array[520][1] = 2，array[250][3] = 2，其中，数组元素的值2表示“微”字在用户输入文本中的位置；
- 处理“博”字，倒排索引能够命中该字，而且是文档ID为520（微博）的第2个字和文档ID为250（腾讯微博）的第4个字，于是，array[520][2] = 3，array[250][4] = 3，其中，数组元素的值3表示“博”字在用户输入文本中的位置；
- 计算“上微博”与文档ID为520的那个文档，即“微博”的LCS的长度，结果为2，再计算匹配度：(2×2) / (3×2) = 0.67；
- 计算“上微博”与文档ID为250的那个文档，即“腾讯微博”的LCS的长度，结果也为2，再计算匹配度：(2×2) / (3×4) = 0.33；
- 假如阈值设定是0.6，由于0.67已超过阈值且匹配度最高，那么520将作为最终返回的文档ID，由后续步骤处理，假如阈值设定是0.7，那么没有一个命中结果能够超过阈值，本次搜索将返回失败。
5. 优化方法
上述方法需要遍历整个二维数组，为了加速遍历过程，可以在二维数组上增加两列，变成array[X+1][Y+3]，同时利用上本来就没有使用的第0列，保存一些额外信息：
- 倒数第一列保存有命中的文档ID列表，命中的文档个数由另外一个变量记录，这样遍历二维数组时就只需要遍历倒数第一列指示的那些行，其余的行就不需要遍历；
- 倒数第二列保存该行最后一个命中的位置，这样遍历该行时就不需要遍历该位置之后的列；
- 第0列保存该行对应的文档的长度信息，方便计算匹配度。
二、查找URL ID列表
一般情况下，一个文档对应一个URL，但也有“一词多义”情况，一个文档对应多个URL。比如，手机浏览器站点和PC浏览器站点通常就不一样。再比如，用户输入“淘宝网”，应该指向淘宝的主站点：http://3g.taobao.com/，用户输入“淘宝衣服”，一般是想用淘宝的站内搜索引擎搜索衣服，应该指向淘宝的搜索站点：http://wap.taobao.com/browse/wap_search.htm?q=衣服。因此，像这样的文档，至少应该配置两个URL ID，一个文档ID对应一个URL ID列表。核心模块应当返回这些URL列表，由业务模块根据返回的属性和其它条件，来判断取舍。
回到上文的例子，假如UC浏览器支持的5个网站都可能对应多个URL，那么可以以红黑树表达如下。其中，圆形节点（key）是文档ID，矩形方框（value）是一个列表，列表元素的关键属性就是URL ID。
三、查找URL
这部分很容易理解，以红黑树表达如下。其中，圆形节点（key）是URL ID，矩形方框（value）就是其URL。
四、总结
以上算法，可以说已经是一个搜索引擎算法的雏形，但受到内存的限制，倒排索引和匹配度二维数组都要占用一定内存空间，特别是二维数组，由文档数量和文档长度的乘积决定，如果是多线程，一般还得要求每个线程拥有私有的匹配度计算空间，使得它只适合在小型项目中使用。
No comments:
Post a Comment