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

它首先通过“字谜指纹”（苗条的想法）建立的所有词的索引，然后通过变它只能输出多于一个字的条目。