使用 Java 对文本文件执行二进制搜索

Question

我有一个大约 100 万字的大文本文件。我这样做是为了一个 android phone 游戏，我只是想看看文本文件中是否存在某个单词。将任何东西加载到内存中不是一种选择。 android phone 内存和处理器太弱了，读取这个文件大约需要 20 秒。

我修改了这个文本文件，使其宽度相等。每个单词是 50 个字符 + 1 个换行符。但是，我对如何正确实现二进制搜索有点困惑，因为我一直对我应该为 seek() 添加多少字节才能正常工作感到困惑。

public static long search(RandomAccessFile file, String target)
            throws IOException {

    file.seek(0);
    String line = file.readLine();

    if(line.equals(target))
        return 1;

    long start = 0;
    long end = file.length();
    long mid = (start + end -50)/2;

    while(start <= end)
    {
        file.seek(mid);
        line = file.readLine();
        if(line.compareTo(target) < 0)
            start = mid + 51;
        else if(line.equalsIgnoreCase(target))
            return 1;
        else
            end = mid - 51;

        mid = (start + end)/2;
    }

    if(start > end)
        return 0;

    return -1;
}

我第一次设置结束时减去 50，因为最后一个单词没有换行。经过几次迭代后，这将停止正常工作。我不知道如何正确地完成这项工作。谁能指导我做错了什么？

Answer 1

通过将文件包装在 AbstractList 中，您可以利用开箱即用的二进制搜索实现：

final int size = (int) ((file.length() + LINE_BREAK_LEN) / (WORD_LEN + LINE_BREAK_LEN));
return Collections.binarySearch(
    new AbstractList<String>() {
        public String get(int pIdx) {
            try {
                file.seek((WORD_LEN + LINE_BREAK_LEN) * pIdx);
                return file.readLine();
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        }

        public int size() {return size;}
    },
    target,
    Comparator.comparing(String::toLowerCase)
);

请注意，换行符只会使代码复杂化，可以从文件中省略。

Answer 2

Waite 的回答很好，但缺少标记接口的实现 RandomAccess。没有它，Collections.binarySearch 默认执行顺序 O(n) 搜索，这是您绝对不希望的。

不幸的是 Java 似乎不允许匿名类扩展和实现（或实现超过 1 件事），因此您需要使用稍微更冗长的替代方法：

  public static long search(RandomAccessFile file, String target) throws IOException {

    final int size = (int) ((file.length() + LINE_BREAK_LEN) / (WORD_LEN + LINE_BREAK_LEN));

    class FileAsList extends AbstractList<String> implements RandomAccess {
      @Override
      public String get(int pIdx) {
        try {
          file.seek((WORD_LEN + LINE_BREAK_LEN) * pIdx);
          return file.readLine();
        } catch (IOException ex) {
          throw new RuntimeException(ex);
        }
      }

      @Override
      public int size() {
        return size;
      }
    }

    var list = new FileAsList();
    return Collections.binarySearch(list, target, Comparator.comparing(String::toLowerCase));
  }

使用 Java 对文本文件执行二进制搜索

Performing a binary search on a text file using Java

java

file

binary-search