大规模中英文单词模糊搜索问题的分析(二)

  经过了大约一个星期时间的考虑,也研究了一下各种开源项目的情况。

  本来满怀期待地发现了拼写检查器Jazzy的源码研究起来,不过后来发现Jazzy已经两年无人问津了,还是有那么点失望的,不过总的来讲,从拼写检查这个思路上,还是找到了一点新的思路的。

  原来使用编辑距离的方法计算单词之间的距离,现在这个核心思想还是没有变,在索引的问题上也有了更多一些的考虑。

  目前考虑下来的主要处理流程是这样的:

1. 对所有库中的人名进行分词,英文按照单词边界进行拆分,而中文按照单个汉字进行拆分,拆分完的汉字全部转换为拼音,这一步比较简单。完成以后就产生了两张二维表,分别是单词表(词典,包含单词、引用计数、是否来自黑名单数据)和倒排索引表(包含单词id、数据库原始条目的id、单词index)。这样就完成了类似Lucene的倒排索引。

2. 为了更好地计算编辑距离,需要建立四张编辑距离权值表(二维表replacement、swap和一维表insert、delete),四张表都不是十分精确的,但是作为索引确实没有十分精确的必要,因为具体的相似度还是依赖于对于单条记录的详细检查。

3. 服务器守护进程随时以流水线方式处理单词与单词之间的相似关系,采用拼写检查器的方法找到字典中的近似单词。

4. 实际向服务器送出查找请求时,服务器首先找到能够精确匹配所有单词的条目,逐条进行相似度检查。如果结果已经过多,那么没有必要再进行后续的查找。如结果较少,那么继续匹配部分单词完全匹配的条目。

5. 如果结果仍然较少,则首先根据编辑距离权值表进行短距离的变换,尝试匹配变换后的结果。

6. 如果仍然没有足够的结果,那么去查找单词近似关系表,如果该单词的近似条目可用,则立即查询得到结果。

7. 如果该单词的近似关系表还没有建立完成,那么提高该单词近似关系处理的优先级,使其立即完成,并进行结果查询。

8. 如果根据待测样本中存在于字典中的单词无法找到足够的项,那么进一步查找不存在于字典中的项,查找流程按照5、6、7的方式进行,建立完成后该单词会被增加到字典中,用以加速下一次的查找。

基于Levenshtein距离算法的编辑距离算法

 

  public static final int getDistance(String word, String similar) {

    //get the weights for each possible operation
    final int costOfDeletingSourceCharacter = config.getInteger(Configuration.COST_REMOVE_CHAR);
    final int costOfInsertingSourceCharacter = config.getInteger(Configuration.COST_INSERT_CHAR);
    final int costOfSubstitutingLetters = config.getInteger(Configuration.COST_SUBST_CHARS);
    final int costOfSwappingLetters = config.getInteger(Configuration.COST_SWAP_CHARS);
    final int costOfChangingCase = config.getInteger(Configuration.COST_CHANGE_CASE);

    int a_size = word.length() + 1;
    int b_size = similar.length() + 1;
    int[][] matrix = new int[a_size][b_size];
    matrix[0][0] = 0;

    for (int i = 1; i != a_size; ++i)
      matrix[i][0] = matrix[i - 1][0] + costOfInsertingSourceCharacter; //initialize the first column

    for (int j = 1; j != b_size; ++j)
      matrix[0][j] = matrix[0][j - 1] + costOfDeletingSourceCharacter; //initalize the first row

    word = " " + word;
    similar = " " + similar;

    for (int i = 1; i != a_size; ++i) {
      char sourceChar = word.charAt(i);
      for (int j = 1; j != b_size; ++j) {

        char otherChar = similar.charAt(j);
        if (sourceChar == otherChar) {
          matrix[i][j] = matrix[i - 1][j - 1]; //no change required, so just carry the current cost up
          continue;
        }

        int costOfSubst = costOfSubstitutingLetters + matrix[i - 1][j - 1];
        //if needed, add up the cost of doing a swap
        int costOfSwap = Integer.MAX_VALUE;
        boolean isSwap = (i != 1) && (j != 1) && sourceChar == similar.charAt(j - 1) && word.charAt(i - 1) == otherChar;
        if (isSwap)
          costOfSwap = costOfSwappingLetters + matrix[i - 2][j - 2];

        int costOfDelete = costOfDeletingSourceCharacter + matrix[i][j - 1];
        int costOfInsertion = costOfInsertingSourceCharacter + matrix[i - 1][j];

        int costOfCaseChange = Integer.MAX_VALUE;
        String strSrcChar = "" + sourceChar;
        String strOtherChar = "" + otherChar;

        if (strSrcChar.compareToIgnoreCase(strOtherChar) == 0)
          costOfCaseChange = costOfChangingCase + matrix[i - 1][j - 1];

        matrix[i][j] = minimum(costOfSubst, costOfSwap, costOfDelete, costOfInsertion, costOfCaseChange);
      }
    }
    int cost = matrix[a_size - 1][b_size - 1];

    if (false)
      System.out.println(dumpMatrix(word, similar, matrix));

    return cost;
  }

大规模中英文单词模糊搜索问题的分析

  最近有一个关于在大规模的中英文词库中的模糊搜索问题。

  这个问题具有几个特点:

  • 每条记录都比较短。
  • 记录的数量多,大约600万条记录。
  • 对解的数量要求高于对解的质量要求。
  • 有对中英文支持的要求。

  对于单一的字符串模糊匹配问题,实际上是单纯的人工智能问题,站在模式识别的角度,就是计算与目标单词的距离,我们实际上需要通过求最一般合一来算出单词之间的编辑距离,这个编辑距离越大,匹配度就越低。如果想更进一步,那么借助遗传算法的思想,随着用户的操作来动态调整每一步编辑的权值(默认所有编辑行为的权值都为1),如果用户认可某次匹配,则对此次匹配所用到的所有编辑行为降低权值。

  而对于这样的一个实际问题,首先我们不可能将600万条记录全部取出逐一检测匹配度,势必要进行一个事先的筛选。因此,大致的流程应该是这样:

  1. 针对所有数据建立倒排索引。
  2. 从索引查找到疑似的匹配项。
  3. 对疑似匹配项的匹配度进行逐个检查,去掉匹配度低的结果。
  4. 按匹配度从高到低输出结果。

  针对此问题,还有以下一些问题需要解决。

  而求编辑距离必须使用基于代价函数的广度优先搜索,否则,无法保证最优解,在权值全部相同的情况下,就等同于一般的广度优先搜索,修改步数增加以后,内存开销明显增加。

  为了减小索引,加快索引速度,必须要合并类似的索引项,对于中文,根据拼音-汉字库将汉字一律合并至为对应拼音是可行的。

  但是对于英文,不可能以字符为单位进行索引,而如果以单词为单位进行索引,拼写错误就无法从索引中找出相应项。如果对无法找到的项进行广度优先的编辑,试图从索引中找出最近似的条目,对于索引查询的开销也是极高的。

  单词拆分对索引也是一个考验,因为如果某个单词无法匹配,其实则可能可以进行拆分,比如helloworld,有9种方法分成两个单词,那么需要对9种拆分方法逐个进行查询,开销也是很大的。如果在这个基础上再考虑拼写错误,那么开销就是平方级的增长了。