优化倒排索引Java

Question

我正在尝试为维基百科页面创建倒排索引，但我运行ning 内存不足。我不确定我还能做些什么来确保它不会运行内存不足。然而，我们谈论的是 390 万个单词。

indexer.java

public void index() {
    ArrayList<Page> pages = parse(); // Parse XML pages
    HashMap<String, ArrayList<Integer>> postings = getPostings(pages);
}

public HashMap<String, ArrayList<Integer>> getPostings(ArrayList<Page> pages) {
    assert pages != null;

    englishStemmer stemmer = new englishStemmer();
    HashSet<String> stopWords = getStopWords();
    HashMap<String, ArrayList<Integer>> postings = new HashMap<>();
    int count = 0;
    int artCount = 0;

    for (Page page : pages) {

        if (!page.isRedirect()) { // Skip pages that are redirects.

            StringBuilder sb = new StringBuilder();
            artCount = count; // All the words until now
            boolean ignore = false;

            for (char c : page.getText().toCharArray()) {

                if (c == '<') // Ignore words inside <> tags.
                    ignore = true;

                if (!ignore) {
                    if (c != 39) {
                        if (c > 47 && c < 58 || c > 96 && c < 123) // Character c is a number 0-9 or a lower case letter a-z.
                            sb.append(c);

                        else if (c > 64 && c < 91) // Character c is an uppercase letter A-Z.
                            sb.append(Character.toLowerCase(c));

                        else if (sb.length() > 0) { // Check if there is a word up until now.

                            if (sb.length() > 1) { // Ignore single character "words"

                                if (!stopWords.contains(sb.toString())) { // Check if the word is not a stop word.

                                    stemmer.setCurrent(sb.toString());
                                    stemmer.stem(); // Stem word s

                                    String s = sb.toString(); // Retrieve the stemmed word

                                    if (!postings.containsKey(s)) // Check if the word already exists in the words map.
                                        postings.put(s, new ArrayList<>()); // If the word is not in the map then create an array list for that word.
                                    postings.get(s).add(page.getId()); // Place the id of the page in the word array list.
                                    count++; // Increase the overall word count for the pages
                                }
                            }
                            sb = new StringBuilder();
                        }
                    }
                }

                if (c == '>')
                    ignore = false;
            }
        }
        page.setCount(count - artCount);
    }
    System.out.println("Word count:" + count);
    return postings;
}

优点

这种方法的一些优点是：

只需获取关联的 ArrayList 的大小，即可获取给定单词出现的次数。
查找给定单词在页面中出现的次数相对容易。

优化

当前优化：

忽略常用词（停用词）。
词根提取并存储。
忽略非英语单词的常见维基百科标签（包含在停用词列表中，例如：lt、gt、ref .. 等）。
忽略 < > 标签中的文本，例如：<pre>, <div>

限制

随着单词的出现次数，数组列表变得非常大，当数组列表必须增长时，这种方法的主要缺点就来了。创建了一个新的数组列表，并且需要将先前数组列表中的项目复制到新的数组列表中。这可能是一个性能瓶颈。链接列表在这里更有意义吗？因为我们只是添加更多的事件而不是读取事件。这也意味着，由于链表不依赖数组作为它们的底层数据结构，它们可以无限制地增长，并且在它们太大时不需要被替换。

替代方法

我考虑过在处理完每个页面后将每个单词的计数转储到数据库中，例如 MongoDB，然后追加新出现的单词。它将是：{word : [occurrences]} 然后让 GC 在处理完每个页面后清理 postings HashMap。

我还考虑过将页面循环移动到 index() 方法中，以便 GC 可以在新页面之前清理 getPostings()。然后在每一页之后合并新的 postings，但我认为这不会减轻内存负担。

至于哈希图，树图是否更适合这种情况？

执行

在我的机器上，这个程序运行在所有 4 个内核上使用 90 - 100% 并占用大约 2-2.5GB RAM。运行一个半小时后：GC Out of memory.

我也考虑过增加此程序的可用内存，但它也需要运行在我的教师机器上。所以它需要在没有任何 "hacks".

的情况下作为标准运行

我需要帮助进行相当大的优化，我不确定还有什么可以帮助我。

Answer 1

ArrayList 是替换为您必须编写的 class 索引的候选对象。它应该使用 int[] 来存储索引值和使用基于其所属词的整体增长率的增量的重新分配策略。（ArrayList 以旧值的 50% 递增，这对于稀有词可能不是最优的。）此外，它应该通过存储第一个索引和后续数字的负数来为优化范围的存储留出空间，例如，

..., 100, -3,...   is index values for 100, 101, 102, 103

这可能会以几个周期为代价保存频繁出现的词的条目。

考虑在输入一定数量的索引值后转储帖子 HashMap 并继续使用空映射。如果文件是按键排序的，则可以相对简单地合并两个或多个文件。

Answer 2

TL;DR 无论您做什么，您的数据结构很可能无法放入内存。

旁注：您实际上应该解释您的任务是什么以及您的方法是什么。您不这样做并期望我们阅读并插入您的代码。

你基本上做的是构建一个单词的多重映射 -> 维基百科文章的 ID。为此，您解析每个非重定向页面，将其分成单个单词并通过添加单词 -> 页面 ID 映射来构建多图。

让我们粗略估计一下这个结构有多大。您的假设是大约 400 万个单词。 EN Wikipedia 中大约有 500 万篇文章。英语的平均单词长度约为 5 个字符，因此我们假设每个单词 10 个字节，每个文章 ID 4 个字节。我们得到大约 40 MB 的单词（地图中的键），20 MB 的文章 ID（地图中的值）。
假设一个类似于 multihashmap 的结构，您可以估计 hashmap 的大小约为 32*size + 4*capacity。

到目前为止这似乎是可以管理的，几十 MB。

但是将有大约 400 万个集合来存储文章的 id，每个集合的大小约为 8*size（如果您采用数组列表），其中的大小是一个单词将在其中遇到的文章数量. 根据 http://www.wordfrequency.info/，前 5000 个单词在 COCAE 中被提及超过 3 亿次，所以我希望维基百科在这个范围内。
这将是大约 2.5 GB 仅用于文章 ID 仅用于 5k 热门词。这是一个很好的提示，表明您的倒排索引结构可能会占用太多内存，无法容纳在一台机器上。

不过，我认为您对生成的结构的大小没有问题。您的代码表明您首先将页面加载到内存中，然后再处理它们。那肯定不行。

您很可能需要以类似流的方式处理页面并使用某种数据库来存储结果。基本上有上千种方法可以做到这一点，我个人会在 AWS 上使用 PostgreSQL 作为数据库，利用 UPSERT 功能进行 Hadoop 作业。

优化倒排索引Java

Optimize inverted index Java

java

optimization

garbage-collection

优点

优化

限制

替代方法

执行