java-搜索长度为1亿个字符的文本+？

Question

我想搜索一个文本文档（或多个文本文档），其中的字符总数可能高达1亿个字符+。

"FADE OUT."
312,719 - source length.
62,543,800 - source length multiplied by 200.
1) Phrase found in 6 ms - searched 312,719 characters. Used 261 mb.
2) Phrase found in 1 ms - searched 625,447 characters. Used 269 mb.
3) Phrase found in 0 ms - searched 1,250,903 characters. Used 284 mb.
4) Phrase found in 0 ms - searched 2,501,815 characters. Used 315 mb.
5) Phrase found in 0 ms - searched 5,003,639 characters. Used 33 mb.
6) Phrase found in 0 ms - searched 1,0007,287 characters. Used 159 mb.
7) Phrase found in 0 ms - searched 20,014,583 characters. Used 114 mb.
8) Phrase found in 0 ms - searched 40,029,175 characters. Used 229 mb.
9) Phrase found in 0 ms - searched 80,058,359 characters. Used 763 mb.
10) Phrase found in 0 ms - searched 160,116,727 characters. Used 916 mb.

源长度是我正在搜索的文本文件的平均大小。我把它乘以200，得到200个文本文件的平均大小。

那么，如何在不使用这么多RAM的情况下搜索文本文件呢？

Answer 1

这是一个非常简单的算法，有点类似于RabinKarp（RabinKarp更有效，但当然更复杂）方法find返回所提供短语的第一次出现的索引。（code）

public class SearchForPhrase {

    static int hash(String phrase) {
        int hash = 0;
        for (int i = 0; i < phrase.length(); i++) {
            hash += phrase.codePointAt(i);
        }
        return hash;
    }

    static boolean equals(Deque<Character> txt, String phrase) {
        int i = 0;
        for (Character c : txt) {
            if (!c.equals(phrase.charAt(i++))) {
                return false;
            }
        }
        return true;
    }

    static int find(String phrase, Reader in) throws Exception {

        int phash = hash(phrase);
        int hash;

        BufferedReader bin = new BufferedReader(in);
        char[] buffer = new char[phrase.length()];

        int readed = bin.read(buffer);

        if (readed < phrase.length()) {
            return -1;
        }

        String tmp = new String(buffer);
        hash = hash(tmp);
        if (hash == phash && tmp.equals(phrase)) {
            return 0;
        }

        Deque<Character> queue = new LinkedList<>();
        for (char c : buffer) {
            queue.add(c);
        }

        int curr;
        int index = 1;
        while ((curr = bin.read()) != -1) {

            hash = hash - queue.removeFirst() + curr;
            queue.add((char) curr);

            if (hash == phash && equals(queue, phrase)) {
                return index;
            }

            index++;

        }

        return -1;

    }

    public static void main(String[] args) throws Exception {

        StringWriter writer = new StringWriter();
        PrintWriter out = new PrintWriter(writer);
        out.println("Discuss the person's qualifications for the graduate study in the chosen field. Statements of past");
        out.println("performance, accomplishments, and contributions are helpful. The more relevant the items mentioned, andd");
        out.flush();

        System.out
                .println(find("Discuss", new StringReader(writer.toString())));
        System.out.println(find("the", new StringReader(writer.toString())));
        System.out.println(find("qualifications",
                new StringReader(writer.toString())));
        System.out.println(find("andd", new StringReader(writer.toString())));

    }

}

出：

0
8
21
199