在Java中搜索单词的最高效数据结构

Question

我有一个程序，它读取文档并搜索每一页中的给定搜索词。然后返回该词出现在哪些页面上。

例如，“brilliant”这个词出现在以下页面：1，4，6，8。

目前我将文件分成页面，并将其存储到ArrayList中。ArrayList的每个元素包含文档的一页。

然后我会将每个页面上的每个单词拆分并存储到一个HashMap中，其中KEY是该单词在文本中出现的位置（我需要知道这一点以进行其他功能），而VALUE是该单词。然后我使用以下方式搜索HashMap;

if (map.containsValue(searchString) == true)
                return true;
             else
                 return false;

我针对每个页面都执行此操作。 一切都正常，但我想知道是否有更有效的数据结构可用，该结构存储给定页面上出现的所有单词以及其位置？（因为在没有给定键的情况下搜索地图中的值是0（n））。 我需要能够通过此结构搜索并查找单词。请记住，我还需要稍后使用位置信息。 我用以下代码向地图填充文本中单词的位置：

    // text is the page of text from a document as a string
int key = 1; // position of the word in the text
    for (String element : text.split(" "))
            {
                map.put(key, element);
                key++;
            }

- Steve

Answer 1

为什么不使用一个单独的HashMap<String,ArrayList<Position>>来将单词映射到出现次数？文本中的每个单词都将成为映射中的一个键，页码和位置将形成条目列表。

由于列表值的存在，插入稍微有些棘手。

ArrayList<Position> positions = words.get(word);
if (positions == null) {
  positions = new ArrayList<Position>();
  words.put(word, positions);
}
positions.add(position);

如果您已经在使用Guava库，您可以使用Guava Multimap: http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Multimap.html （特别是当您已经在使用Guava库的其他功能时 - 我可能会避免仅为此目的引入库依赖）

编辑：将Integer更改为Position（并将其设置为列表），因为确切的位置是必需的。Position应该类似于

class Position {
  int page;
  int index; 
}

- Stefan Haustein

---

@Steve，每次搜索文档时您都执行O(n)，而不是对单个文档执行一次。这是一个巨大的区别。 - Thomas Jungblut

这个解决方案中单词的位置存储在哪里？ - Robby Cornelissen

不错的想法——这是一个倒排索引，并且非常适合这个任务。 - wchargin

我需要在软件后续的功能中使用位置。我需要检索每个搜索词之前和之后的单词。 - Steve

@RobbyCornelissen 我想这取决于应用程序是否存在问题。如果有问题，可以使用嵌套映射或两个并行映射。 - Stefan Haustein

Answer 2

我可能会使用Lucene或者来自Guava collections的一些内容，但是如果没有这些，我认为最高效的结构应该是：

HashMap<String, TreeMap<Integer, TreeSet<Integer>>> words;

        ^^^^^^          ^^^^^^^          ^^^^^^^
         word            page            position

使用words.get("brilliant").keySet();将立即为您提供所有出现“brilliant”的页面。如果我没有错，这是O(log n)而不是O(n)。

在阅读评论后，我认为您还需要第二个数据结构来查找每个搜索词之前和之后的单词：

TreeSet<Integer, TreeMap<Integer, String>> positions;

        ^^^^^^^          ^^^^^^^  ^^^^^^
         page            position  word

或者，使用页面和位置的两个列表的相应索引：

ArrayList<ArrayList<String>> positions;          

- Robby Cornelissen