Java Anagram 运行内存不足

Question

我正在尝试解决古老的字谜问题。感谢那里的许多教程，我能够遍历一组字符串，递归地找到所有排列，然后将它们与英语单词列表进行比较。我发现的问题是，在大约三个词之后（通常是 "anamorphosis" 之类的词），我得到一个 OutOfMemory 错误。我尝试将我的批次分成小集合，因为它似乎是消耗我所有内存的递归部分。但即使只是 "anamorphosis" 也将其锁定...

这里我把文件中的单词读入List

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

现在我将它们分成更小的集合并调用 class 来生成字谜：

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

快速计算一下："anamorphosis" 有 12 个字母，得到 12！ = 479,001,600 个排列。每个字符串至少占用 12 个字节（假设 UTF-8 仅包含 ASCII 字符），这意味着总大小为 12 * 479,001,600 字节，大约为 6 GB。

现在，据我所知，默认堆大小设置为 1GB 或（如果更小）可用内存的四分之一。这小于所需的 6GB。

有两种解决方法：

在执行程序时增加堆大小，但它不适用于较长的单词，因为排列呈指数增长：仅多一个字母，"accomplishing" 就已经需要 78GB。
通过排列流式传输，而不是将它们具体化为一组字符串。具体来说，这意味着仍然使用递归，但不是存储每个递归生成的排列，而是立即处理，然后在继续下一个排列时忘记。

现在，如果需要对整个字典进行计算，另一种方法（如果您有权访问集群）可能是计算字典与自身的笛卡尔积，将其存储在分布式文件系统（如 HDFS）上（应该在十亿个条目的数量级），然后使用 MapReduce 并行遍历所有对，并输出彼此是变位词的对。这是更多的努力，但复杂性从单词长度的指数下降到字典大小的二次方。

Answer 2

对于较长的单词，排列的数量很快就会变得巨大。

/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 中，您可以使用来自 Apache Commons 或 Guava 的 Map<String, List<String>> 或 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

这会占用适量的内存（整个字典，加上一些键和映射开销），但这意味着一旦创建了结构，您就可以非常便宜地一遍又一遍地查询。

如果你想找到两个词的字谜，你将需要一个更复杂和有趣的算法。但即便如此，避免暴力破解整个搜索-space 排列对于您的成功至关重要。

Answer 3

这是一个结合了 slim 的方法和我的方法的答案，"Pseudo-Java code":

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

它首先通过"anagram fingerprint"（slim的想法）为所有单词建立一个索引，然后遍历它，只输出超过一个单词的条目。

Java Anagram 运行内存不足

Java Anagram running out of memory

java

anagram

Java Anagram 运行 内存不足

Java Anagram running out of memory

java

anagram

Java Anagram 运行内存不足