我想创建维基百科页面,但是我一直在运行内存的倒排索引。我不确定还有什么可以做的,以确保它不会耗尽内存。不过,我们正在谈论3.9亿字。优化倒排索引的Java
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,裁判...等)。内
< >
标签如 - 忽略文本:
<pre>, <div>
限制
数组列表成为出现单词的数量令人难以置信的大,这种方法的主要缺点来当一个数组列表有增长。将创建一个新的数组列表,并且需要将前一个数组列表中的项目复制到新的数组列表中。这可能是一个可能的性能瓶颈。链接列表会更有意义吗?因为我们只是添加更多的事件而不读取事件。这也意味着,因为链表不依赖于数组作为其基础数据结构,所以它们可以无限制地增长,并且当它们太大时不需要被替换。
替代方法
我已经考虑了每个单词的计数倾销到像的MongoDB数据库之后,每个页面已经被处理,然后追加新事件。这将是:{word : [occurrences]}
,然后让GC在每个页面处理完成后清除postings
HashMap。
我也考虑将页面循环移动到index()
方法中,以便GC可以在新页面前清理getPostings()
。然后在每页后合并新的postings
,但我不认为这会减轻内存负担。
至于哈希映射将树图是这种情况更适合?
执行
在我的机器这个程序使用90的所有4个内核运行 - 100%大约需要2-2.5GB RAM。它运行了一个多小时,然后:GC Out of memory
。
我也考虑增加这个程序的可用内存,但它也需要在我的教师机器上运行。所以它需要在没有任何“黑客”的情况下作为标准运行。
我需要帮助进行相当多的优化,我不确定还有什么可以帮助的。
关于代码质量的注意事项:在单一方法中,您正在做太多事情。我全心全意地推荐你学习R.马丁的“干净的代码”。含义:你花了很多时间来写这个问题 - 在编写代码时花费一些时间是非常明智的。此外:不幸的是你的问题还是有点“非常广泛”。您可能会尝试着重于您设计中的“较小”方面;而不是提出整个事情,并要求提供“一般性帮助”。 – GhostCat
你首先给出你的方法的优点,但你忘了解释你的方法是什么。你是否期望我们尝试阅读你的代码,并明确你想要实现的目标?代码应该实现什么,它使用的算法和数据结构是什么? – RealSkeptic
考虑使用 - [Xmx参数](http://stackoverflow.com/a/14763095/1362755)简单地增加JVM的堆限制。或者只是用概率数据结构表示单词(具有几个字节长度的散列)。您还需要查看语言处理库,因为您的方法不适用于不使用空格分隔单词的语言(例如中文)。 – the8472