更快的字符串匹配/迭代方法？

Question

在我目前正在开发的程序中,有一部分需要花费一些时间.基本上,我有一个字符串列表和一个目标短语.例如,假设目标短语是"成品库存".现在,在过滤掉停用词(of)之后,我想从列表中提取包含三个词之一的所有字符串:"inventory","finished"和"goods".现在,我实现了如下想法:

String[] targetWords; // contains "inventory", "finished", and "goods"
ArrayList<String> extractedStrings = new ArrayList<String>();

for (int i = 0; i < listOfWords.size(); i++) {
    String[] words = listOfWords.get(i).split(" ");
    outerloop:
    for (int j = 0; j < words.length; j++) {
        for (int k = 0; k < targetWords.length; k++) {
            if (words[j].equalsIgnoreCase(targetWords[k])) {
                extractedStrings.add(listOfWords.get(i));
                break outerloop;
            }
        }
    }
}

该列表包含超过100k个单词,并且使用这个单词,每个目标短语完成任务需要0.4到0.8秒.事情是,我有很多这些目标短语需要处理,秒数真的加起来.因此,我想知道是否有人知道更有效的方法来完成这项任务？我在这里先向您的帮助表示感谢!

Answer 1

您的100k单词列表可以添加(一次)到HashSet.使用wordSet.contains()- 而不是遍历列表,HashSet为此提供了恒定时间性能,因此不受列表大小的影响.

Answer 2

您正在传递 中的每个元素targetWords，而不是同时检查 targetWords 中的所有单词。此外，您会在每次迭代中拆分单词列表，而实际上并不需要它，从而产生了开销。

\n\n

我建议您将您的组合targetWords成一个（编译的）正则表达式：

\n\n

(?xi)  # turn on comments, use case insensitive matching\n\\b     # word boundary, i.e. start/end of string, whitespace\n(      # begin of group containing \'inventory\' or \'finished\' or \'goods\'\n inventory|finished|goods  # bar separates alternatives\n)      # end of group\n\\b     # word boundary\n

\n\n

不要忘记将正则表达式字符串中的退格用双引号引起来。

\n\n

import java.util.regex.*;\n...\nPattern targetPattern = Pattern.compile("(?xi)\\\\b(inventory|finished|goods)\\\\b");\nfor (String singleString : listOfWords) {\n  if (targetPattern.matcher(singleString).find()) {\n    extractedStrings.add(singleString);\n  }\n}\n

\n\n

如果您对正则表达式的速度不满意 - 尽管正则表达式引擎通常针对性能进行了优化 - 您需要推出自己的高速多字符串搜索。Aho \xe2\x80\x93Corasick 字符串匹配算法针对在文本中搜索多个固定字符串进行了优化，但当然与简单地创建 Pattern 相比，实现该算法需要相当多的努力。

\n