更快地构建trie

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

此外,如果你的数据是静态的(即你没有在电话上更新它),请考虑 DAFSA 为您的任务。它是存储单词最有效的数据结构之一(在大小和速度方面都必须优于“标准”尝试和基数尝试,在速度方面优于简洁尝试,在大小方面往往优于简洁尝试)。有一个很好的C++实现: dawgdic -您可以使用它从命令行构建DAFSA,然后使用Java读取器来生成数据结构(示例实现为 here ).

您可以将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;
    }
}

只需构建一个大的String[]并对其进行排序。然后可以使用二进制搜索来查找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;
}

这里有一个相当紧凑的格式,用于在磁盘上存储trie。我将通过它的(高效的)反序列化算法来指定它。初始化初始内容为trie的根节点的堆栈。一个接一个地阅读字符,并按如下方式进行解释。字母a-Z的意思是“分配一个新节点,使其成为当前堆栈顶部的子节点,并将新分配的节点推到堆栈上”。字母表示子节点所在的位置。空格的含义是“将堆栈顶部节点的有效标志设置为true”。退格(\b)的意思是“弹出堆栈”。

例如,输入

TREE \b\bIE \b\b\bOO \b\b\b

给出单词列表

TREE
TRIE
TOO

。在桌面上,使用任意方法构造trie,然后通过以下递归算法(伪代码)进行序列化。

serialize(node):
    if node is valid: put(' ')
    for letter in A-Z:
        if node has a child under letter:
            put(letter)
            serialize(child)
            put('\b')

这不是一个神奇的子弹,但你可能可以通过这样做来稍微减少你的运行时间 一个大内存分配 而不是一群小家伙。

当我使用“节点池”而不是依赖于单独的分配时,我在下面的测试代码中看到了大约10%的加速(对不起,C++,而不是Java):

#include <string>
#include <fstream>

#define USE_NODE_POOL

#ifdef USE_NODE_POOL
struct Node;
Node *node_pool;
int node_pool_idx = 0;
#endif

struct Node {
    void insert(const std::string &s) { insert_helper(s, 0); }
    void insert_helper(const std::string &s, int idx) {
        if (idx >= s.length()) return;
        int char_idx = s[idx] - 'A';
        if (children[char_idx] == nullptr) {
#ifdef USE_NODE_POOL
            children[char_idx] = &node_pool[node_pool_idx++];
#else
            children[char_idx] = new Node();
#endif
        }
        children[char_idx]->insert_helper(s, idx + 1);
    }
    Node *children[26] = {};
};

int main() {
#ifdef USE_NODE_POOL
    node_pool = new Node[400000];
#endif
    Node n;
    std::ifstream fin("TWL06.txt");
    std::string word;
    while (fin >> word) n.insert(word);
}

尝试预先分配空间所有可能的孩子(256)都有大量浪费的空间。你让你的缓存哭了。将这些指向子级的指针存储在可调整大小的数据结构中。

有些尝试会通过使用一个节点来表示一个长字符串来进行优化,并仅在需要时将该字符串分解。

您可以使用sqlite之类的数据库和嵌套集或celko树来存储trie,而不是使用简单的文件,还可以使用三元搜索trie构建更快、更短(节点更少)的trie。

我不喜欢通过数组中的索引来寻址节点的想法,但这只是因为它需要再添加一个(指针的索引)。但使用预先分配的节点阵列,您可能会在分配和初始化上节省一些时间。您还可以通过为叶节点保留前26个索引来节省大量空间。因此,您不需要分配和初始化180000个叶节点。

还有索引,您将能够以二进制格式从磁盘读取准备好的节点阵列。这必须快几倍。但我不知道如何在你的语言上做到这一点。这是Java吗?

如果您检查了源词汇表是否已排序,您还可以通过将当前字符串的某些前缀与前一个前缀进行比较来节省一些时间。例如,前4个字符。如果他们相等,你可以开始你的

for(int level=0;level<key.length();等级++){

从第5级开始循环。

是空间效率低下还是时间效率低下?如果你正在滚动一个普通的trie,那么在处理移动设备时,空间可能是问题的一部分。看看patricia/radix的尝试,尤其是当你将其用作前缀查找工具时。

尝试: http://en.wikipedia.org/wiki/Trie

Patricia/三根: http://en.wikipedia.org/wiki/Radix_tree

您没有提到一种语言,但这里有两种前缀尝试在Java中的实现。

常规trie: http://github.com/phishman3579/java-algorithms-implementation/blob/master/src/com/jwetherell/algorithms/data_structures/Trie.java

Patricia/Radix(空间效应)trie: http://github.com/phishman3579/java-algorithms-implementation/blob/master/src/com/jwetherell/algorithms/data_structures/PatriciaTrie.java

一般来说,避免在Java中使用大量从头开始的对象创建,这既缓慢又有巨大的开销。更好地实现您自己的内存管理池类,例如一次性分配50万个条目。

此外,对于大型词典来说,序列化太慢。使用二进制读取来快速填充上面提出的基于数组的表示。