建立trie更快

Question

我正在制作一个移动应用程序，它需要数以千计的快速字符串查找和前缀检查。为了加快速度，我从我的单词列表中做了一个Trie，它大约有18万个单词。

一切都很棒，但唯一的问题是，构建这个庞大的trie (大约有40万个节点)需要大约10秒的，这在我的手机上非常慢。

下面是构建trie的代码。

public SimpleTrie makeTrie(String file) throws Exception {
    String line;
    SimpleTrie trie = new SimpleTrie();

    BufferedReader br = new BufferedReader(new FileReader(file));
    while( (line = br.readLine()) != null) {
        trie.insert(line);
    }
    br.close();

    return trie;
}

运行在insert上的O(length of key)方法

public void insert(String key) {
    TrieNode crawler = root;
    for(int level=0 ; level < key.length() ; level++) {
        int index = key.charAt(level) - 'A';
        if(crawler.children[index] == null) {
            crawler.children[index] = getNode();
        }
        crawler = crawler.children[index];
    }
    crawler.valid = true;
}

我正在寻找直观的方法来更快地构建trie。也许我只在我的笔记本上构建了一次trie，以某种方式将它存储到磁盘上，然后从电话中的一个文件中加载它？但我不知道该怎么实现。

或者，是否还有其他前缀数据结构可以减少构建时间，但具有类似的查找时间复杂性？

如有任何建议，敬请见谅。提前谢谢。

编辑

有人建议使用Java序列化。我试过了，但是这段代码是非常的慢代码：

public void serializeTrie(SimpleTrie trie, String file) {
        try {
            ObjectOutput out = new ObjectOutputStream(new BufferedOutputStream(new FileOutputStream(file)));
            out.writeObject(trie);
            out.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public SimpleTrie deserializeTrie(String file) {
        try {
            ObjectInput in = new ObjectInputStream(new BufferedInputStream(new FileInputStream(file)));
            SimpleTrie trie = (SimpleTrie)in.readObject();
            in.close();
            return trie;
        } catch (IOException | ClassNotFoundException e) {
            e.printStackTrace();
            return null;
        }
    }

能不能让上面的代码更快一些？

我的trie：http://pastebin.com/QkFisi09

单词列表：http://www.isc.ro/lists/twl06.zip

用于运行代码的Android：http://play.google.com/store/apps/details?id=com.jimmychen.app.sand

Answer 1

Double-Array tries保存/加载非常快，因为所有数据都存储在线性数组中。它们也非常快地查找，但插入可能是昂贵的。我打赌在某个地方有一个Java实现。

另外，如果您的数据是静态的(即您没有在电话上更新它)，请考虑使用DAFSA作为您的任务。它是存储单词的最有效的数据结构之一(在大小和速度上都必须优于“标准”尝试和基尝试，比简洁的尝试速度要好，通常比简洁的尝试要好。有一个很好的C++实现：dawgdic --您可以使用它从命令行构建DAFSA，然后对结果的数据结构使用Java (示例实现是here)。

Answer 2

您可以将trie存储为一个节点数组，将对子节点的引用替换为数组索引。根节点将是第一个元素。这样，您可以轻松地从简单的二进制或文本格式存储/加载trie。

public class SimpleTrie {
    public class TrieNode {
        boolean valid;
        int[] children;
    }
    private TrieNode[] nodes;
    private int numberOfNodes;

    private TrieNode getNode() {
        TrieNode t = nodes[++numberOnNodes];
        return t;
    }
}

Answer 3

只需构建一个大型String[]并对其进行排序。然后可以使用二进制搜索来查找字符串的位置。您也可以根据前缀进行查询，而不需要做太多的工作。

前缀查找示例：

比较方法：

private static int compare(String string, String prefix) {
    if (prefix.length()>string.length()) return Integer.MIN_VALUE;

    for (int i=0; i<prefix.length(); i++) {
        char s = string.charAt(i);
        char p = prefix.charAt(i);
        if (s!=p) {
            if (p<s) {
                // prefix is before string
                return -1;
            }
            // prefix is after string
            return 1;
        }
    }
    return 0;
}

在数组中查找前缀并返回其位置(MIN或MAX表示未找到)

private static int recursiveFind(String[] strings, String prefix, int start, int end) {
    if (start == end) {
        String lastValue = strings[start]; // start==end
        if (compare(lastValue,prefix)==0)
            return start; // start==end
        return Integer.MAX_VALUE;
    }

    int low = start;
    int high = end + 1; // zero indexed, so add one.
    int middle = low + ((high - low) / 2);

    String middleValue = strings[middle];
    int comp = compare(middleValue,prefix);
    if (comp == Integer.MIN_VALUE) return comp;
    if (comp==0)
        return middle;
    if (comp>0)
        return recursiveFind(strings, prefix, middle + 1, end);
    return recursiveFind(strings, prefix, start, middle - 1);
}

获取字符串数组和前缀，在数组中输出前缀的出现。

private static boolean testPrefix(String[] strings, String prefix) {
    int i = recursiveFind(strings, prefix, 0, strings.length-1);
    if (i==Integer.MAX_VALUE || i==Integer.MIN_VALUE) {
        // not found
        return false;
    }
    // Found an occurrence, now search up and down for other occurrences
    int up = i+1;
    int down = i;
    while (down>=0) {
        String string = strings[down];
        if (compare(string,prefix)==0) {
            System.out.println(string);
        } else {
            break;
        }
        down--;
    }
    while (up<strings.length) {
        String string = strings[up];
        if (compare(string,prefix)==0) {
            System.out.println(string);
        } else {
            break;
        }
        up++;
    }
    return true;
}