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

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

  • abaco代码,交换。
  • 粗体字可以大胆。
  • 树文件夹和叶子树。

和给定的字符串:

  • omecodeexchangeuthercanbetreeofword

并从算法中获得如下内容:

  • ome代码交换uther可以是word树

部分“ome”和“uther”不能被分割,因此将保持原样(如果我将此部分标记为NOT-RECOGNIZED,那将是很好的)。 我尝试分析KMP算法,但距离我的需求太远了,我想以有效的时间方式组织集合(小于线性到集合大小)。

我忘了说:

  • 分裂是在字符串上,自然语言单词与俚语单词混合,所有单词都没有空格
  • 我已经尝试过基于加权单词字典的动态算法,但是对于错误分割上的等效权重的错误主题太多(“错误”我的意思是自然语言)
  • 我需要这个分割的最佳结果,使用字符串集合中的单词序列作为“好例子”

动态编程在这里很有帮助。

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

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

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

Java代码:

  String word = "omecodeexchangeuthercanbetreeofword"; Set 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 : (ij)); 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 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)")); 

这可以使用正则表达式轻松完成,正则表达式针对性能进行了高度优化。

 public static void main(String[] args) { List splitWords = Arrays.asList("abaco", "code", "exchange", "bold", "word", "can", "be", "tree", "folder", "and", "of", "leaf"); String splitRegex = ""; for (int i = 0; i < splitWords.size(); i++) { if (i > 0) splitRegex += "|"; splitRegex += splitWords.get(i); } String stringToSplit = "omecodeexchangeuthercanbetreeofword"; Pattern pattern = Pattern.compile(splitRegex); Matcher matcher = pattern.matcher(stringToSplit); int previousMatchEnd = 0; while (matcher.find()) { int matchStart = matcher.start(); int matchEnd = matcher.end(); if (matchStart != previousMatchEnd) System.out.println("Not recognized: " + stringToSplit.substring(previousMatchEnd, matchStart)); System.out.println("Match: " + stringToSplit.substring(matchStart, matchEnd)); previousMatchEnd = matchEnd; } if (previousMatchEnd != stringToSplit.length()) System.out.println("Not recognized: " + stringToSplit.substring(previousMatchEnd, stringToSplit.length())); } 

输出:

 Not recognized: ome Match: code Match: exchange Not recognized: uther Match: can Match: be Match: tree Match: of Match: word