6

在我目前正在处理的程序中，有一个部分需要花费一些时间。基本上，我有一个字符串列表和一个目标短语。例如，假设目标短语是“成品库存”。现在，在过滤掉停用词 (of) 后，我想从列表中提取包含以下三个词之一的所有字符串：“库存”、“完成”和“商品”。现在，我将这个想法实现如下：

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;
            }
        }
    }
}

该列表包含超过 10 万个单词，因此完成每个目标短语的任务大约需要 0.4 到 0.8 秒。问题是，我有很多这样的目标短语要处理，而且秒数真的加起来了。因此，我想知道是否有人知道完成此任务的更有效方法？我在这里先向您的帮助表示感谢！

4

5 回答 5

6

您的 100k 单词列表可以（一次）添加到 HashSet。与其遍历您的列表，不如使用wordSet.contains()-a HashSet 为此提供恒定时间性能，因此不受列表大小的影响。

于 2013-08-09T00:33:32.403 回答
2

您可以获取巨大的单词列表并将它们添加到哈希映射中，然后当您的短语出现时，只需遍历短语中的单词并检查哈希映射。目前，您正在进行线性搜索，而我的建议是将其缩减为恒定时间搜索。

关键是最小化查找。使用这种技术，您将有效地索引您的巨大单词列表以进行快速查找。

于 2013-08-09T00:34:07.633 回答
1

您正在通过来自的每个元素targetWords，而不是同时检查来自 targetWords 的所有单词。此外，您在每次迭代中拆分单词列表而不真正需要它，从而产生开销。

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

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

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

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

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

于 2013-08-09T20:51:11.897 回答
1

如果您想要整个短语或只是 listOfWords 中的单个单词，我有点困惑。如果您尝试从 listOfWords 获取字符串，如果您的目标词之一在字符串中，这应该适合您。 

    String[] targetWords= new String[]{"inventory", "finished", "goods"};
    List<String> listOfWords = new ArrayList<String>();

    // build lookup map
    Map<String, ArrayList<String>> lookupMap = new HashMap<String, ArrayList<String>>();
    for(String words : listOfWords) {
        for(String word : words.split(" ")) {
            if(lookupMap.get(word) == null) lookupMap.put(word, new ArrayList<String>());
            lookupMap.get(word).add(words);
        }
    }

    // find phrases
    Set<String> extractedStrings = new HashSet<String>();
    for(String target : targetWords) {
        if(lookupMap.containsKey(target)) extractedStrings.addAll(lookupMap.get(target));
    }
于 2013-08-09T01:20:50.813 回答
0

我会尝试用它来实现它ExecutorService以并行搜索每个单词。 http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/ExecutorService.html

例如具有固定线程池大小：

Executors.newFixedThreadPool(20);
于 2013-08-09T00:25:21.300 回答