使用正則表達式與Java的TreeSet或Collections.BinarySearch

我試圖創建一個匹配的程序，當給定一個字的一些正則表達式「C [AZ] T」，找到將匹配該列表中的正則表達式的所有單詞的話。我的例子的匹配將是CAT，CUT，COT。使用正則表達式與Java的TreeSet或Collections.BinarySearch

我的目標是儘可能快地爲非常大的單詞列表。我嘗試過使用Java的TreeSet實現，但是搜索需要很長的時間，因爲我必須迭代樹中的每個單詞。即使我在將這個列表放入樹中之前進行了隨機化處理，搜索速度也非常慢。

所以我的問題是，我可以使用內部Contains（），還是有一些Java提供的其他數據結構，可以使用正則表達式嗎？謝謝..

我正在考慮使用AVL或紅黑色「hashmap」（但不是真的），長度作爲鍵和單詞作爲值。這意味着我需要允許多個相同的密鑰，但每個密鑰映射到不同的值。所以我的get會返回一個值列表，而不是單個值。有什麼地方可以找到這種數據結構的實現嗎？或者至少有一個基地讓我開始..我真的不想推出自己的。

這裏是我到目前爲止的代碼：

public class WordSearch { 
    SortedSet<String> tree = new TreeSet<String>(); 
    List<String> list = new ArrayList<String>(); 

    public WordSearch(List<String> allWords) { 
     // long seed = System.nanoTime(); 
     // Collections.shuffle(allWords, new Random(seed)); // randomize 
     tree.addAll(allWords); 
    } 

    public List<String> solutions(String pattern, int max) { 
     pattern = pattern.toLowerCase().toUpperCase(); 
     pattern = pattern.replace("*", "[A-Z]"); 
     Pattern find = Pattern.compile(pattern); 
     int count = 0; 
     ArrayList<String> result = new ArrayList<String>(); 
     Iterator<String> it = tree.iterator(); 
     while (count < max) { 
      while (it.hasNext()) { 
       String word = it.next().toLowerCase().toUpperCase(); 
       Matcher match = find.matcher(word); 
       if (match.matches()) { 
        result.add(word); 
        count++; 
       } 
      } 
      break; 
     } 
     return result; 
    } 
}

來源

2013-12-08 kzs

如果你知道手之前，你的正則表達式/模式，你可以建立類似布隆過濾器，但是這真的不是所有從建立Collections像matchesPattern0不同，matchesPattern1等，這基本上是一個數據庫的索引如何工作。你可能也只想要一個前綴樹。

在你的情況下，數據結構將有助於的唯一方式是如果正則表達式被錨定，即指定了第一個或最後一個字符或字符範圍。否則，無論如何，您將必須查看整個數據結構。基本上，^C[A-Z]T$的情況是所以具體說，沒有人出去，併爲此建立一個優化的數據結構。

標識你感到聰明，迫切需要這個，你最好的選擇是一個Pattern轉換爲「最小」和方法「最大」，所以CAT和D，然後用SortedSet.subSet，並應用過濾器到結果。但實際上，這種優化很少起作用。

來源

2013-12-08 18:34:07

使用正則表達式與Java的TreeSet或Collections.BinarySearch

回答

相關問題