26°

Lucene FuzzyQuery 原理

基于Levenshtein Edit Distance(莱温斯坦编辑距离)基础上,对索引文档进行模糊搜索

  • Levenshtein算法是计算两个字符串之间的最小编辑距离的算法,
  • 所谓的最小编辑距离就是把字符串A通过添加删除替换字符的方式转变成B所需要的最少步骤
    • 比如:你文档里有个xiaopingguo字符,你拿“xiapngguo”去匹配,这时我们知道他们的编辑距为2,
      • 具体步骤就是ap之间插入一个字母o,pn之间插入一个字母i,所以编辑距为2,
  • 代码详见LevenshteinTest
    • /**
       * @author Jly
       * @date 2020/1/16  19:40
       */
      public class LevenshteinTest {
      
      <span style="color:#cc7832">public static int </span><span style="color:#ffc66d">levenshtein</span>(String str1<span style="color:#cc7832">,</span>String str2) {
          <span style="color:#cc7832">int </span>n = str1.length()<span style="color:#cc7832">;
      

      int m = str2.length(); if ( n == 0) return m; if ( m == 0) return n; int[][] Arr = new int[m + 1][n + 1]; int cost = 0; for(int i=0;i<=n;i++) Arr[0][i] = i; for(int j=0;j<=m;j++) Arr[j][0] = j; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if (str1.charAt(i-1) == str2.charAt(j-1)) cost = 0; else cost = 1; Arr[j][i] = Arr[j-1][i]+1<Arr[j][i-1]+1?Arr[j-1][i]+1:Arr[j][i-1] +1 ; Arr[j][i] = Arr[j][i]<Arr[j-1][i-1]+cost?Arr[j][i]:Arr[j-1][i-1]+cost; } int nEdit = Arr[m][n]; return nEdit; }

      <span style="color:#cc7832">public static void </span><span style="color:#ffc66d">main</span>(String[] args) {
          System.<em>out</em>.println(<em>levenshtein</em>(<span style="color:#6a8759">"acdf"</span><span style="color:#cc7832">, </span><span style="color:#6a8759">"abc"</span>))<span style="color:#cc7832">;
      

      System.out.println(111); } }

  • FuzzyQuery的最大编辑距最大为2 ,超过2的直接抛弃
    • 意思就是如果你用字母“abs”去搜索“absolutely”(两者编辑距为7)
      • 在构建FuzzyQuery实例对象的时候,如果你把maxEdits设置为2,肯定搜不出来这毫无疑问
      • 可是如果把maxEdits设置为7,FuzzyQuery对象构造都通不过,默认只支持编辑距0~2的查询
      • 特此提醒!官方提示:
        • 因为编辑距设置太大会返回很多不相关的内容,官方不推荐你这么做,
        • 如果你需要支持这种功能,官方建议你移步到spellCheck模块(拼写检查模块)
  • prefixLength 表示指定长度的前缀会被认为是100%相似
    • 默认prefixLength是等于零的
    • prefixLength长度可以加快匹配速度,因为你已经告诉了FuzzyQuery前N个字符是完全相同的,自然查询速度加快了
  • maxExpansions ​​​​​​​设置在指定编辑距之内的所有Term的最大容量是多大
    • 因为这些Term最终是要放入一个优先级队列(PriorityQueue)中的,
    • 然后通过BooleanQuery拼接成条件的,
    • 而BooleanQuery能拼接的条件个数是有限制的,所以弄个maxExpansions最大值设置,默认值是50,一般默认值就可以了,
      • 除非出现了too many boolean clause异常时你才需要适当调大这个值

本文由【Java搬砖工程师】发布于开源中国,原文链接:https://my.oschina.net/u/3847203/blog/3159441

全部评论: 0

    我有话说: