Java实现短语列表模糊搜索（允许多1个插入词）高效方案求解

需求说明 #

• 输入为两个字符串列表：模式短语列表Patterns、查询语句列表Queries
• 实现过程禁止引入任何第三方依赖库
• 模糊匹配规则：查询语句中命中模式短语的对应片段，最多允许插入1个额外单词
• 输出要求：返回每条查询语句对应的所有匹配短语片段集合

基础验证用例 #

基础用例及预期输出如下：

// 模式短语集合
P = {"i would have", "they love", "i analyzed", "made decision"};
// 查询语句集合
queries = {"since this morning i have analyzed all the data from the company and made my decision",
         "they love the idea"};
// 预期输出
// [["i have analyzed", "made my decision"], ["they love"]]

原有暴力实现的局限 #

原有暴力实现代码可通过上述基础用例，代码如下：

private static ArrayList<ArrayList<String>> fuzzy_search(String[] P, String[] queries) {
    ArrayList<ArrayList<String>> result = new ArrayList<>();
    for(String query : queries){
        ArrayList<String> queryTokens = new ArrayList(Arrays.asList(query.split(" ")));
        ArrayList<String> matches = new ArrayList<>();
        for(String pattern : P){
            String[] patternTokens = pattern.split(" ");
            ArrayList<Integer> ii = new ArrayList<>();
                for (String patternToken : patternTokens){
                    int i = queryTokens.indexOf(patternToken);
                    if(i >=0)
                        ii.add(i);
                    else {
                        ii.clear();
                        break;
                    }
                }
            if(!ii.isEmpty()){
                int n = ii.get(ii.size()-1) - ii.get(0);
                if(n==ii.size() || n == ii.size()-1){
                    StringBuilder sb = new StringBuilder();
                    for(int kk = ii.get(0); kk< ii.get(ii.size()-1)+1; kk++) {
                        sb.append(queryTokens.get(kk));
                        if (kk != ii.get(ii.size() - 1))
                            sb.append(" ");
                    }
                    matches.add(sb.toString());
                }
            }
        }
        result.add(matches);
    }
    return result;
}

该实现无法覆盖复杂场景，核心问题包括：

• 调用indexOf仅返回单词第一次出现的索引，无法匹配同一单词在查询语句中多次出现的命中场景
• 未校验匹配到的模式词索引是否严格递增，会出现跨片段错误匹配
• 无法识别同一模式在查询语句不同位置的多次命中
• 间隔单词数校验逻辑粗糙，无法准确判断“最多插入1个额外词”的规则

复杂场景验证用例 #

需要适配的复杂测试用例及预期结果如下：

{
  "queries": [
    "close box son add bad strong afford down bad middle",
    "business become for department chap offer business become for chap tell afford aware bad name business become for committee chap normal around egg expect learn prepare balance goodbye lot forget welcome"
  ],
  "phrases": [
    "balance goodbye lot forget",
    "health contact ever big",
    "business become for chap",
    "approach field",
    "else after blow inform",
    "around egg expect learn",
    "add bad",
    "increase accept",
    "close box",
    "afford bad"
  ],
  "expected_output": [
    [
      "close box",
      "add bad",
      "afford down bad"
    ],
    [
      "business become for department chap",
      "business become for chap",
      "afford aware bad",
      "business become for committee chap",
      "around egg expect learn",
      "balance goodbye lot forget"
    ]
  ]
}

内容的提问来源于stack exchange，提问作者OTUser