より速い文字列マッチング/反復法？

Question

私が現在取り組んでいるプログラムでは、少し時間がかかります。基本的には、私はストリングと1つのターゲットフレーズのリストを持っています。例として、ターゲットフレーズが「完成品の在庫」であるとします。ストップワード（of）を除外した後、 "inventory"、 "finished"、 "goods"の3つの単語のいずれかを含むすべての文字列をリストから抽出します。次のように今、私はアイデアを実装：

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以上の単語が含まれており、これでそれは各ターゲットフレーズのためのタスクを完了するためにrounghly 0.4 0.8秒かかります。物事は、私は処理するこれらの目標フレーズの多くを持って、秒が実際に追加されます。したがって、私は誰かがこの作業を完了するためのより効率的な方法を知っているかどうか疑問に思っていましたか？事前に助けてくれてありがとう！

Answer 1

あなたが代わりに同時に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 

があなたの正規表現文字列でのバックスペース引用符を倍増することを忘れないでください：

私はあなたのtargetWords 1（コンパイル）regular expressionに結合することを示唆しています。正規表現エンジンは通常、パフォーマンスのために最適化されているが - - あなたはあなた自身の高速マルチ文字列検索をロールバックする必要がありますが、正規表現の速さに満足していない場合

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 string matching algorithmは、テキスト内のいくつかの固定文字列を検索するために最適化されていますが、もちろんこのアルゴリズムを実装するのは、単純にパターンを作成する場合と比較してかなり簡単です。

Answer 2

私はExecutorServiceでそれを実装して、各単語の検索を並列化しようとします。例えば http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/ExecutorService.html

固定スレッドプールサイズを有する：

Executors.newFixedThreadPool(20); 

Answer 3

100Kワードのリストは、HashSetのに（1回）追加することができます。リストを反復するのではなく、wordSet.contains()を使用してください。これはHashSetによって一定のパフォーマンスが得られるため、リストのサイズの影響を受けません。

Answer 4

巨大な単語リストをハッシュマップに追加して、フレーズが来たら、フレーズ内の単語をループし、ハッシュマップをチェックするだけです。現在、あなたは線形検索を行っています。私が提案していることは、一定の時間の検索に削減します。

キーはルックアップを最小限に抑えることです。この手法を使用すると、高速検索のためにあなたの巨大な単語リストを効果的に索引付けできます。

Answer 5

全体のフレーズが必要な場合や、listOfWordsの単語だけの場合は少し混乱します。 listOfWordsから文字列を取得しようとしている場合、目的の単語の1つが文字列内にあれば、これはうまくいくはずです。

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