Java Anagram內存不足

Question

我正試圖解決年齡偏大的問題。感謝這裏的許多教程，我可以遍歷一組字符串，遞歸地查找所有排列，然後將它們與英語單詞列表進行比較。我發現的問題是，經過大約三個字（通常是像「變形」），我得到一個OutOfMemory錯誤。我嘗試將我的批次分成小集，因爲它似乎是消耗我所有記憶的遞歸部分。但是，即使只是「歪像」鎖起來......

在這裏，我從文件中讀取單詞到列表現在

Scanner scanner = new Scanner(resource.getInputStream()); 
    while (scanner.hasNext()) { 
     String s = scanner.nextLine(); 
     uniqueWords.add(s.toLowerCase()); 
    } 

我打破他們分成更小的組，並調用一個類來生成字謎：

List<List<String>> subSets = Lists.partition(new ArrayList(uniqueWords), SET_SIZE); 

for (List<String> set: subSets) { 
     // tried created as class attribute & injection, no difference 
     AnagramGenerator anagramGenerator = new AnagramGenerator(); 
     List<Word> anagrams = anagramGenerator.createWordList(set); 
     wordsRepository.save(anagrams); 
     LOGGER.info("Inserted {} records into the database", anagrams.size()); 
} 

最後我發生器：

public class AnagramGenerator { 

private Map<String, List<String>> map = new Hashtable<>(); 
public List<Word> createWordList(List<String> dictionary) { 

    buildAnagrams(dictionary); 

    List<Word> words = new ArrayList<>(); 
    for (Map.Entry<String, List<String>> entry : map.entrySet()) { 
     words.add(new Word(entry.getKey(), entry.getValue())); 
    } 
    return words; 
    } 

private Map<String, List<String>> buildAnagrams(List<String> dictionary) { 

     for (String str : dictionary) { 
      String key = sortString(str); 
      if (map.get(key) != null) { 
       map.get(key).add(str.toLowerCase()); 
      } else { 
       if (str.length() < 2) { 
        map.put(key, new ArrayList<>()); 
       } else { 
        Set<String> permutations = permutations(str); 
        Set<String> anagramList = new HashSet<>(); 

        for (String temp : permutations) { 
         if (dictionary.contains(temp) && !temp.equalsIgnoreCase(str)) { 
          anagramList.add(temp); 
         } 
        } 
        map.put(key, new ArrayList<>(anagramList)); 
       } 
      } 
     } 
     return map; 
    } 

    private Set<String> permutations(String str) {  
     if (str.isEmpty()) { 
      return Collections.singleton(str); 
     } else { 
      Set<String> set = new HashSet<>(); 
      for (int i = 0; i < str.length(); i++) 
       for (String s : permutations(str.substring(0, i) + str.substring(i + 1))) 
        set.add(str.charAt(i) + s); 
      return set; 
     } 
    } 

編輯： 基於優秀的反饋我已經改變了我的發電機從排列到工作查找：

public class AnagramGenerator { 
private Map<String, Set<String>> groupedByAnagram = new HashMap<String, Set<String>>(); 

    private Set<String> dictionary; 

    public AnagramGenerator(Set<String> dictionary) { 

     this.dictionary = dictionary; 
    } 

public List<Word> searchAlphabetically() { 

     List<Word> words = new ArrayList<>(); 
     for (String word : dictionary) { 
      String key = sortString(word); 
      if (!groupedByAnagram.containsKey(key)) { 
       groupedByAnagram.put(key, new HashSet<>()); 
      } 
      if (!word.equalsIgnoreCase(key)) { 
       groupedByAnagram.get(key).add(word); 
      } 
     } 

     for (Map.Entry<String, Set<String>> entry : groupedByAnagram.entrySet()) { 
      words.add(new Word(entry.getKey(), new ArrayList(entry.getValue()))); 
     } 

     return words; 
    } 
private String sortString(String goodString) { 

     char[] letters = goodString.toLowerCase().toCharArray(); 
     Arrays.sort(letters); 
     return new String(letters); 
    } 

它多一點的調整，從而它自己的字謎，但除此之外，這個我不加一個字似乎正在快速發展。而且，代碼更清潔。感謝大家！

Answer 1

正如長字所指出的那樣，排列的數量很快就會變得巨大。

/usr/share/dict/british-english在Debian上有99,156行。有更長的單詞列表，但讓我們以此爲例。

九個字母單詞的排列數是9！ = 362,880

因此，對於9個字母或更多的單詞，嘗試字典中每個單詞的計算工作量要少於嘗試每個輸入單詞的排列。

10! milliseconds = ~1 hour 
12! milliseconds = ~5.54 days 
15! milliseconds = ~41.44 years 

而且你會幸運地處理每毫秒一次置換，所以你可以看到你很快就會爲一個數字，是完全不切實際一起工作的排列。堆棧和堆的影響以相同的速度增長。

所以，儘量算法（僞）：

sorted_input = sort_alphabetically(input_word) 
for each dictionary_word // probably a file readline() 
    sorted_dictionary_word = sort_alphabetically(dictionary_word) 
    if(sorted_dictionary_word = sorted_input) 
     it's an anagram! Handle it 
    end 
end 

同樣，你可以很快地寫出所有字典詞算法爲查找數據結構。再次僞代碼;在Java中，你可以使用Map<String, List<String>>或Apache的共享或番石榴一個MultiMap：

multimap = new MultiMap<String, String> // or whatever 

    def build_dict: 
     for each dictionary_word // probably a file readline() 
      multimap.add(
       sort_alphabetically(dictionary_word), 
       dictionary_word) 
     end 
    end 

    def lookup_anagrams(word): 
     return multimap.get(sort_alphabetically(word)) 
    end 

這佔用的內存中等量（整部字典，加上位的密鑰和地圖間接費用），而是意味着一旦結構被創建，你就可以非常便宜地一遍又一遍地查詢。

如果你想找到兩個字的anagrams，你需要一個更復雜和有趣的算法。但即使如此，避免蠻橫排列整個搜索空間對於您的成功至關重要。

Answer 2

做一個快速計算：「變形」有12個字母，它給出12！ = 479,001,600個排列。每個字符串至少需要12個字節（假設UTF-8只帶有ASCII字符），這意味着總大小爲12 * 479,001,600字節，大約爲6 GB。

現在，據我所知，默認堆大小設置爲1GB或（如果小於）四分之一的可用內存。這比所需的6GB少。

有兩種方式出於此：

• 執行程序時增加堆大小，但由於置換增長也不會爲不再言語工作呈指數：只用一個以上的字母，「完成」已需要78GB。

• 通過置換進行流式傳輸，而不是將它們實現爲一組字符串。具體來說，這意味着仍然使用遞歸，但不是存儲每個遞歸生成的排列，而是立即處理，然後在轉移到下一個時被遺忘。現在

，如果它需要針對整個字典完成的，另一種方法，如果你有機會到集羣，可能是計算與自身字典的笛卡爾積，它存儲的分佈式文件系統像HDFS（應該是10億個條目的數量級），然後使用MapReduce並行處理所有對，並輸出相互之間的字形對。這是更多的努力，但複雜性從單詞長度的指數下降到字典大小的二次方。

Answer 3

這裏是一個融合了超薄的做法與我的答案，「僞Java代碼」：

Map<String, Set<String>> groupedByAnagram = new HashMap<String, Set<String>>(); 

for(String word: dictionary) 
{ 
    String footprint = sort_alphabetically(word); 
    if(!groupedByAnagram.contains(footprint)) 
    { 
    groupedByAnagram.put(footprint, new HashSet<String>>()); 
    } 
    groupedByAnagram.get(footprint).insert(word); 
} 

for(Set<String> anagram: groupedByAnagram.values()) 
{ 
    if(anagram.size() > 1) 
    { 
    System.out.println("Anagram found."); 
    for (String word: anagram) 
    { 
     System.out.println(word); 
    } 
    } 
} 

它首先通過「字謎指紋」（苗條的想法）建立的所有詞的索引，然後通過變它只能輸出多於一個字的條目。