走进全文搜索

http://www.phpx.com/happy/thread-124696-1-1.html

作者:NP ? 甜甜

 

为什么我要写这种东西？因为趋势。或者说是为了实现。我总是喜欢做一些看起来无意义的事情……
    搜索，是互联网的每一步！
    提到搜索，最有名的当然是Google、baidu这类全网搜索引擎，提到开发工具，恐怕要算是Lucene了。Lucene是一个开源的全文搜索的工具包，由Java编写，是Apache软件基金会的一个项目。Lucene现在有了很多Java之外的语言版本，比如.NET、Perl等，Lucene4c也在开发中。c语言版本似乎要等上一段时间，因为c版本的结构将和标准的Java版差很多，因为这两种语言根本是一种写法……
    在ZendFramework里还有一个Lucene的PHP版本实现，也可以算是Lucene的一种语言分支，不过PHP Lucene并不像Perl Lucene实现得那么完整，它有很多的方法都是空的，它只是实现了Lucene的功能，提供一个可用的平台。当然PHP Lucene的代码质量还是很不错的。
    前些日子有看过PHP Lucene和标准Java Lucene在相同环境下的比较，PHP Lucene可以说是惨不忍睹，创建索引的速度和搜索速度都已经超过可承受极限，或者是我们使用的方法不当，但是PHP Lucene对索引文件的Optimizer动作是空的，这个让打散的索引无法合并。虽然根据以往的经验，PHP的IO性能要好过Java，但是这次对比应该反应的是PHP Lucene的实现方式上有问题，因为后来我把它的索引文件转移到tmpfs上，发现没有任何好转。
    与此不同的是Perl Lucene，前一阵刚升级到1.25，它的性能是很稳定的，它没有严格地追随Java版的实现结构，因为Perl的语法很灵活，而且它的IO和字符串性能都足够好，Perl Lucene我没有做过什么详细的测试。
    这次的目的是在BSM中扩展全文搜索模块，我不打算用Lucene，因为PHP Lucene确实还不成熟，我也不希望有BSM中有Java成分。BSM里只有几个Daemon是Perl的。我不需要Lucene那么复杂，只要用自己的方式实现一个简单的全文搜索功能就可以了。BSM的整体概念就是简单高效很多模块只有一个文件，我不需要那么多的功能，只要它够快够稳定就可以了。虽然在PHP上追求“快”有一点变态。
* * * * * * * * * * * *
    全文搜索不是MySQL的LIKE %%，对于普通的数据库索引，LIKE %%几乎是无效的，全文索引的实际概念是有效地把文字拆成词，再对这些词做反向的索引，Lucene中这个叫做“倒排”，区别于传统索引的“这篇文章中有什么词”，倒排实际上记录的是“这个词在哪些文章中出现”，搜索的时候实际就是把搜索字符串按照同样的规则再次拆分成词或非词单元，然后在索引中取出这些词所在的文章号的并集（或交集）。比如有一个词“中国”，它的索引可能是这个样子：
    中国：1-25:12-84:37-90
    它的含义是“中国”这个词在1号文章的第25个字处、12号文章的第84字处、37号文章的第90字处出现。这就是一个包含位置信息的倒排索引。当用户搜索“中国”的时候，引擎只要按照一定的规则定位到这条索引上，就可以迅速地取出“中国”出现的位置。然后它可以根据文章ID来到数据库或者其它上地方取出一部分文章做摘要返回给用户，而不需要每篇文章都从头到尾遍历一次查找“中国”。
    基于这个概念，Lucene创建了非常有效的倒排索引，同时Lucene的索引是包含词频的。然而Lucene是基于“大索引”的，它实际上在维护一个大的数据库，在创建索引的时候它也会创建一些小的索引，当小索引达到一定量的时候，Lucene会把它们合并在一起，也就是PHP Lucene缺少的Optimizer部分。
    BSM中的搜索部分依然使用倒排，不过不同于Lucene，我的实现方式是散列。当然它会导致不小的空间浪费，不过可以省去很多计算文件偏移量的麻烦。BSM把索引打散成几乎无数个小的部分，每一个部分通过SQLite引擎来维护，处理这些小的数据表，SQLite是很拿手的。而且一个特定的Hash算法可以一次就定位到文件，它的效率是很高的。
* * * * * * * * * * * *
    搜索的一个最重要的问题就是如何有效地拆分文字，西方的拉丁语系比较容易处理，因为它就是以词为单位的书写方式，比如英文，可以简单地通过空格、标点符号、特殊字符完成有效地切分，稍微麻烦一点的就是词性，比如英文的时态、复数形式、特殊的宾格等等，处理这个问题已经有了很多成熟的方案，比如Perl的Linhua包。英文的分词实际上是很容易的。
    对于东方文字，最典型的就是中文，它是按照字为单位组织句子的，词与词之间没有明显的分割，不像英文中有空格，如何有效地分割中文是个极其复杂的全球性问题。汉语是世界上最难学的语种之一，也表现在计算机处理上……目前比较通用的中文分词技术包括字元分词、词典匹配、语义分词等。
    字元分词是最简单直接的分词方法，包括如二元、三元等。它的划分方式就是相邻的字就按照词来计算，而不管它有没有什么实际意义。比如“我是中华人民共和国的公民”，按照二元分词可以划分为“我是 是中 中华 华人 人民 民共 共和 和国 国的 的公 公民”。二元分词简单高效，但是它会制造出很多冗余数据，因为像“民共”、“国的”这些根本就是毫无意义的“词”。二元分词的索引通常比原文还要大。
    词典分词是依靠词典匹配的方式来完成划分，实现它需要一个词库表，包含了大量的中文词汇，分词就是以这个词库表（词典）为基础进行，词典划分有正向、逆向、双向以及最大划分、最小划分、最优划分等方式，还有混合几种的变体。举上例“我是中华人民共和国的公民”，按照正向最大分词方法，从句首开始，到句尾逐字递减，直到匹配出词典中的一个词，或者剩下一个单字。首先匹配到的是“我是”，然后将“我是”从句子中拿掉，重复上面的过程，匹配出“中华人民共和国”，再重复过程，这次找不到词典中的词，剩下一个“的”字，最后匹配出“公民”。这样整句划分为“我是 中华人民共和国 的 公民”。它实现了比二元分词更有效的划分。其中“的”字可以根据需要做出取舍。
    也可以从逆向匹配，就是从句尾开始查词典。根据统计学观点来看，汉语的词组一般都是前后等长或前短后长，所以一些人认为逆向匹配比正向匹配产生歧义的几率要小。比如“研究生命的起源”，按照逆向匹配可以正确地划分为“研究 生命 的 起源”，但是按照正向匹配，结果就是“研究生 命 的 起源”，这就是一个错误的划分。
    基于语义分析的分词技术是目前研究最多，也相对不成熟的分词方式，它的基本概念是对中文语义的理解，它也需要依靠词典，不过这个词典更趋近于知识库，它的词是包含词性的，语义分析器依靠高效的人工智能算法提取出句子的摘要部分，也就是中学语文课上我们常做的“划分句子结构”“提取主干”（好多横线竖线圈圈叉叉把语文书画得乱七八糟）。
    BSM中包含了一个二元分词和一个正向最大匹配的词典分词（可以很容易地改为逆向），它简单地实现了中文切分，同时它的结果包含有位置信息（字节偏移量）。或者过段时间我会用更好的分词方法来替换它，不过就我现在的情况，只打算做到这个程度。人懒没办法。
    我公开PHP实现部分（其实就是全部，但是PHP只是一个低效率的实现方式，我没有使用太多的PHP本身特性，甚至mb函数都没有用，就是为了方便地向C和perl迁移）。区别于BSM的其它模块，搜索部分的SQLite连接没有使用数据库封装类，因为它的性质是“文件操作”。
    BsmSearch的索引保存方式如下：单词的MD5前2位和次2位组成两级hash目录，一共有65536个目录，从第16位到第24位为文件名，后面剩下8位以后可能会留下做校验。当然这个hash算法可以随时修改。这样一个12字节的key，我已经测试过目前的26万词库，没有重复出现。每一个索引文件是一个SQLite数据库，它包含以下结构：

1. CREATE TABLE bsm_index (
   
2.        t_id INTERGER DEFAULT 0,
   
3.        position INTERGER DEFAULT 0,
   
4.        d_flag BOOLEAN DEFAULT f
   
5.       )

复制代码

t_id是文章编号，可以修改为CHAR，如果不使用数字ID话。t_id上创建有索引。
    它用以下的函数生成key：
[PHP]
function _get_word_key ($word)
{
  $word_md5 = md5 ($word);
  
  $ret = substr ($word_md5, 0, 4) . substr ($word_md5, 16, 8);
  
  return $ret;
}
[/PHP]
    生成索引的函数如下：
[PHP]
function _write_index ($itemid, $tokens)
{
  $ret = array ();
  
  foreach ($tokens as $position => $word) {
   $word = strtolower ($word);
   $word_key = $this->_get_word_key ($word);
   $ret[$word_key][] = $position;
  }
  
  unset ($word_key);
  
  foreach ($ret as $word_key => $indexes) {
   $base_dir1 = substr ($word_key, 0, 2);
   $base_dir2 = substr ($word_key, 2, 2);
   $index_filename = substr ($word_key, 4);
   
   $dir = $this->index_dir . $base_dir1 . '/';
   if (!is_dir ($dir))
    @mkdir ($dir);
   
   $dir = $dir . $base_dir2 . '/';
   if (!is_dir ($dir))
    @mkdir ($dir);
   
   $index_filename = $dir . $index_filename;
   
   $index_dh = sqlite_open ($index_filename);
   $sql = "SELECT name FROM sqlite_master WHERE type = 'table' AND name = 'bsm_index'";
   $res = sqlite_query ($sql, $index_dh);
   $t_list = sqlite_fetch_all ($res);
   
   if (is_array ($t_list) && count ($t_list) == 0) {
    // Create a Index Table
    $sql = "CREATE TABLE bsm_index (
       t_id INTERGER DEFAULT 0,
       position INTERGER DEFAULT 0,
       d_flag BOOLEAN DEFAULT f
      )";
    $res = sqlite_query ($sql, $index_dh);
   
    $sql = "CREATE INDEX t_id ON bsm_index(t_id)";
    $res = sqlite_query ($sql, $index_dh);
   }
   
   foreach ($indexes as $position) {
    $sql = "INSERT INTO bsm_index (t_id, position) VALUES ($itemid, $position)";
    sqlite_query ($sql, $index_dh);
   }
   sqlite_close ($index_dh);
  }
  
  return $res;
}
[/PHP]
    首先它会判断两级目录是否存在，不存在的话会自动创建，如果为了节省IO时间，可以预先准备好所有的目录。然后函数根据传入的tokens（分词结果）在SQLite的bsm_index表中插入信息。根据使用了一段时间后的情况，每个词的索引添加量都不大，所以INSERT没有使用事务。
[PHP]
function search ($query)
{
  $queries = $this->_tokenizer_dict ($this->_normalize_text ($query));
  
  $c = 0;
  $ret = array ();
  foreach ($queries as $query_item) {
   $word_key = $this->_get_word_key (strtolower ($query_item));
   
   $base_dir1 = substr ($word_key, 0, 2);
   $base_dir2 = substr ($word_key, 2, 2);
   $index_filename = $this->index_dir . $base_dir1 . '/' . $base_dir2 . '/' . substr ($word_key, 4);
   
   if (!@is_readable ($index_filename))
    return false;
   
   $index_dh = sqlite_open ($index_filename);
   $sql = "SELECT t_id FROM bsm_index WHERE d_flag = 'f' GROUP BY t_id";
   $res = sqlite_query ($sql, $index_dh);
   
   while ($t_id = sqlite_fetch_single ($res)) {
    $ret[$c][] = $t_id;
   }
   $c ++;
  }
  
  for ($i = 0; $i < $c; $i ++) {
   $arr[] = '$ret[' . $i . ']';
  }
  
  $tmp = implode (',', $arr);
  $tmp = '$base_ret = array_intersect (' . $tmp . ');';
  eval ($tmp);
  
  return ($base_ret);
}
[/PHP]
    这是一个简单的搜索，它还不完整，比如没有处理交并复合的情况，结果也没有带有位置信息，不过这个容易解决，昨天晚上太困了……哈哈。搜索使用建立索引同样的分词方式_tokenizer_dict来创建queries，根据word_key快速地定位到某个SQLite文件上。在早期版本使用纯文件时，它的定位速度极快，现在使用SQLite，包括库文件初始化，也可以保证在几毫秒的时间内完成搜索定位。
    下面是两个分词算法，一个是二元分词，一个是词典分词：
[PHP]
function _tokenizer ($text)
{
  // UTF8_only
  // 2-Base Cut
  $len = strlen ($text);
  $mbc = '';
  $last_mbc = '';
  $tmp = '';
  $tokens = array ();
  
  for ($i = 0; $i < $len; $i++) {
   $c = $text[$i];
   $v = ord ($c);
   
   if ($v > 0xe0) {
    // 3-bytes chars
    $tmp = '';
    $mbc = $c . $text[$i + 1] . $text[$i + 2];
    $i += 2;
   }
   
   elseif ($v > 0xc0) {
    // 2-bytes chars
    $tmp = '';
    $mbc = $c . $text[$i + 1];
    $i ++;
   }
   
   else {
    $mbc = '';
    if ($c == ' ') {
     if ($tmp) {
      $p = $i - strlen ($tmp);
      $tokens[$p] = $tmp;
     }
     
     $tmp = '';
    }
    else {
     $tmp .= $c;
    }
   }
   
   if ($mbc) {
    if ($last_mbc) {
     $p = $i - strlen ($last_mbc . $mbc) + 1;
     $tokens[$p] = $last_mbc . $mbc;
    }
    $last_mbc = $mbc;
   }
   
   else {
    $last_mbc = '';
   }
  }
  
  return $tokens;
}

function _tokenizer_dict ($text, $non_word = false)
{
  $len = strlen ($text);
  $mbc = '';
  //$mbc_str = '';
  $mbc_str = array ();
  $tmp = '';
  $tokens = array ();
  
  for ($i = 0; $i < $len; $i++) {
   $c = $text[$i];
   $v = ord ($c);
   
   if ($v > 0xe0) {
    // 3-bytes chars
    $tmp = '';
    $mbc = $c . $text[$i + 1] . $text[$i + 2];
    $i += 2;
   }
   
   elseif ($v > 0xc0) {
    // 2-bytes chars
    $tmp = '';
    $mbc = $c . $text[$i + 1];
    $i ++;
   }
   
   else {
    $mbc = '';
    if ($c == ' ') {
     if ($tmp) {
      $p = $i - strlen ($tmp);
      $tokens[$p] = $tmp;
     }
     
     $tmp = '';
    }
   
    else {
     $tmp .= $c;
    }
   
    if (count ($mbc_str) > 0) {
     // Div_dict
     //mb_internal_encoding ('UTF-8');
     $start_offset = $i - strlen (implode ('', $mbc_str));
     $mbc_str_left = $mbc_str;
     while (count ($mbc_str_left)) {
      //$mb_len = mb_strlen ($mbc_str_left);
      $mb_len = count ($mbc_str_left);
      $word = '';
      
      for ($j = ($mb_len > 4 ? 4 : $mb_len); $j >= 1; $j --) {
       //$test = mb_substr ($mbc_str_left, 0, $j);
       $test = '';
       for ($k = 0; $k < $j; $k++) {
        $test .= $mbc_str_left[$k];
       }
      
       //$mb_test_len = mb_strlen ($test);
       if ($j == 1) {
        // 1 only
        $word = $test;
       }
      
       else {
        if ($this->dict->find ($test)) {
         $word = $test;
        }
       }
      
       if ($word) {
        //$mbc_str_left = mb_substr ($mbc_str_left, $mb_test_len);
        
        $arr_tmp = array ();
        for ($k = $j; $k < $mb_len; $k++) {
         $arr_tmp[] = $mbc_str_left[$k];
        }
        
        $mbc_str_left = $arr_tmp;
        if (!$non_word) {
         if ($j > 1)
          $tokens[$start_offset] = $word;
        }
        else
         $tokens[$start_offset] = $word;
        
        $start_offset += strlen ($word);
        continue 2;
       }
      }
     }
    }
   
    //$mbc_str = '';
    $mbc_str = array ();
   }
   
   if ($mbc) {
    $mbc_str[] = $mbc;
   }
  }
  
  return $tokens;
}
[/PHP]
    可以看到注释掉的信息，是mb_函数部分，我去掉他们，一方面是为了迁移，一方面是mb_很慢。我偷懒地使用了不完整的UTF8切字，只判断2个字节的和3个字节的，其实只有UTF3，呵呵……以后再说。
[PHP]
function _normalize_text ($text)
{
  $symbol = '`~!@#$%^&*()_+=|{}[]:;"<>,.?';
  $symbol = preg_quote ($symbol);
  $ret = preg_replace ("/[$symbol]/", ' ', $text);
  $ret = preg_replace ("/[\r\n\t]/", ' ', $ret);
  
  // For Chinese...
  $ret = str_replace ('“', ' ', $ret);
  $ret = str_replace ('”', ' ', $ret);
  $ret = str_replace ('‘', ' ', $ret);
  $ret = str_replace ('’', ' ', $ret);
  $ret = str_replace ('！', ' ', $ret);
  $ret = str_replace ('？', ' ', $ret);
  $ret = str_replace ('。', ' ', $ret);
  $ret = str_replace ('，', ' ', $ret);
  $ret = str_replace ('、', ' ', $ret);
  $ret = str_replace ('·', ' ', $ret);
  $ret = str_replace ('（', ' ', $ret);
  $ret = str_replace ('）', ' ', $ret);
  $ret = str_replace ('＃', ' ', $ret);
  $ret = str_replace ('《', ' ', $ret);
  $ret = str_replace ('》', ' ', $ret);
  $ret = str_replace ('；', ' ', $ret);
  $ret = str_replace ('：', ' ', $ret);
  $ret = str_replace ('……', ' ', $ret);
  $ret = str_replace ('　', ' ', $ret);
  $ret = str_replace ('——', ' ', $ret);
  
  // Cut Words...
  $ret = str_replace ('的', '的 ', $ret);
  $ret = str_replace ('是', '是 ', $ret);
  $ret = str_replace ('吗', '吗 ', $ret);
  $ret = str_replace ('吧', '吧 ', $ret);
  $ret = str_replace ('呀', '呀 ', $ret);
  
  $ret = preg_replace ("/\s+/", ' ', $ret);
  
  return (trim ($ret) . ' ');
}
[/PHP]
    上面这个函数对文字做了一些简单的预处理，扔掉了一些标点符号，主要就是为了把文章先分割成“句子”，实验性函数……
    我的词典是保存在内存中的，依靠memcached来维护，每一个词保存的就是一个名字为word_key，值为“t”的内存变量。memcached对这个词典进行了有效的散列。下面是词典class：
[PHP]
<?php
class BsmSearchDictMemcached
{
var $mc;

function BsmSearchDictMemcached ()
{
  global $dict_memcached_host, $dict_memcached_port;
  
  $this->mc = memcache ();
  $this->mc->add_server ($dict_memcached_host, $dict_memcached_port);
  
  return $this->mc;
}

function make_mem_dict ()
{
  global $dict_source_file;
  
  $fp = fopen ($dict_source_file, 'rb');
  
  while ($word = fgets ($fp)) {
   $word = trim ($word);
   $key = $this->_gen_mem_key ($word);
   $this->mc->set ($key, 't');
  }
  
  fclose ($fp);
}

function find ($word)
{
  $key = $this->_gen_mem_key ($word);
  
  if ($this->mc->get ($key) == 't')
   return true;
  
  else
   return false;
}

function _gen_mem_key ($word)
{
  if ($word) {
   $md5_word = md5 ($word);
   $key = substr ($md5_word, 0, 4) . substr ($md5_word, 16, 8);
   $key = 'dict_' . $key;
  }
  
  else
   $key = 'NO_KEY';
  
  return $key;
}
}
?>
[/PHP]
    一些参数是在BSM的配置文件中定义的，make_mem_dict是生成内存词典的方法，它从原始词典dict.dat中导出数据插入到内存中。
    一个使用实例：
[PHP]
<?php
define ('IN_BSM', true);
$phpEx = 'php';
error_reporting (2047);
require ('../include/kernel/common.inc.' . $phpEx);
require ($include_root . 'search/search.inc.' . $phpEx);
$search = new BsmSearch ('search/');
$str = '我是大傻瓜';
$start_time = array_sum (explode (' ', microtime()));
$db->sql_query ("INSERT INTO `data` SET `text` = '$str');
$id = $db->sql_nextid ();
$search->add_text ($id, $str);
print_r ($search->search ('傻瓜'));
$end_time = array_sum (explode (' ', microtime()));
$time = $end_time - $start_time;
echo ('<br>Spend Time: ' . $time . ' secs');
?>
[/PHP]
    它在数据库里插入一篇内容叫“我是大傻瓜”的文章，同时创建了索引，然后搜索“傻瓜”这个词，结果会返回刚刚那个ID，如果之前还插入过包含“傻瓜”的文章，会一起返回。
    BsmSearch基本算是写了个框框，还有很多没有实现，我不着急，慢慢做。
    抛砖了，希望大家多指正，嘿嘿