java - 从其他字符串集合的示例中拆分字符串

Question

我想构建一个字符串集合(任何复杂的数据结构，如集合)，我可以有效地使用它作为“示例”来了解我可以在何处拆分给定的字符串。
例如，我有这个 String 集合:

• abaco 代码，交换。
• 粗体词可以是粗体。
• 树文件夹和树叶。

和给定的字符串:

• omecodeexchangeuthercanbetreofword

并从算法中获得类似的东西:

• 一些代码交换可以是单词树

“ome”和“uther”部分无法拆分，因此将保持原样(如果我将这部分标记为 NOT-RECOGNIZED 就好了)。我尝试分析 KMP 算法，但离我的需求太远了，我想以高效的时间方式组织集合(小于集合大小的线性)。

忘记说了:

• 拆分是在字符串上，自然语言单词和俚语单词混合在一起，全部没有空格
• 我已经尝试过基于加权词词典的动态算法，但是在错误拆分(“错误”我指的是自然语言)时，对于等效权重的错误太多了
• 我需要这个拆分的最佳结果，使用字符串集合中的单词序列作为“好例子”

Answer 1

Dynamic Programming在这里可能会有帮助。

f(0) = 0
f(i) = min { f(j) + (dictionary.contains(word.substring(j,i)) ? 0 : i-j)  for each j=0,...,i }

想法是使用上述递归函数进行详尽搜索，同时尽量减少不“适合”的字母数量。使用DP技术，您可以避免重复计算并高效地得到正确答案。

获取实际的分区可以通过记住每一步选择了什么 j 来完成，并从最后到第一步追溯你的步骤。

Java代码:

    String word = "omecodeexchangeuthercanbetreeofword";
    Set<String> set = new HashSet<>(Arrays.asList("abaco", "code", "exchange", "bold", "word", "can", "be", "tree", "folder", "and", "of", "leaf"));
    int n = word.length() + 1;
    int[] f = new int[n];
    int[] jChoices = new int[n];
    f[0] = 0;
    for (int i = 1; i < n; i++) {
        int best = Integer.MAX_VALUE;
        int bestJ = -1;
        for (int j = 0; j < i; j++) {
            int curr = f[j] + (set.contains(word.substring(j, i)) ? 0 : (i-j));
            if (curr < best) {
                best = curr;
                bestJ = j;
            }
        }
        jChoices[i] = bestJ;
        f[i] = best;
    }
    System.out.println("unmatched chars: " + f[n-1]);
    System.out.println("split:");
    int j = n-1;
    List<String> splits = new ArrayList<>();
    while (j > 0) { 
        splits.add(word.substring(jChoices[j],j));
        j = jChoices[j];
    }
    Collections.reverse(splits);
    for (String s : splits) System.out.println(s + " " + (set.contains(s)?"(match)":"(does not match)"));