更快地构建Trie树

Question

我正在制作一个移动应用程序，需要进行数千次快速字符串查找和前缀检查。为了提高速度，我使用我的单词列表构建了Trie，其中约有180,000个单词。

一切都很好，但唯一的问题是，在我的手机上构建这个庞大的Trie（它有大约400,000个节点）目前需要大约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(键的长度)

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 IDE：http://play.google.com/store/apps/details?id=com.jimmychen.app.sand

- Bruce

---

我无法在 Android Gingerbread 上安装 IDE？ - Micromega

我建议从性能分析开始。至少要测量哪一部分用于(1)从文件中读取，(2)在trie中查找位置和(3)创建新节点。 - maxim1000

@布鲁斯，你是否尝试过二分查找技术？我发现它有很好的结果。 - Justin

@Justin 是的，我确实尝试过了，但速度似乎不够快。我只需要两个查询：一个前缀是否存在，一个单词是否存在。我不需要所有以前缀开头的字符串。顺便说一下，我统计了前缀存在搜索的数量，大约有10,000个...所以二分搜索方法比较慢，因为使用dawg，整个算法只需要 ~60毫秒就能完成。 - Bruce

@Bruce 好的，很高兴你找到了解决方案。我从未发现过一个前缀查询比1毫秒慢，同样对于单个字符串的存在性也是如此，但也许我的手机更快一些。 - Justin

性能比较 DAFSA内存消耗：16020976 DAFSA（毫秒）：[100] 0 DAFSA（毫秒）：[10000] 5 DAFSA（毫秒）：[1000000] 28

trie内存消耗：12946984 trie（毫秒）：[100] 0 trie（毫秒）：[10000] 6 trie（毫秒）：[1000000] 131

List内存消耗：1761728 List（毫秒）：[100] 23 List（毫秒）：[10000] 696 List（毫秒）：[1000000] 71752

Set内存消耗：2341616 Set（毫秒）：[100] 0 Set（毫秒）：[10000] 1 Set（毫秒）：[1000000] 22 - Amit Kumar Gupta

Answer 1

双数组字典树非常快速，因为所有数据都存储在线性数组中。 它们还非常快速进行查找，但插入可能很昂贵。 我敢打赌，在某处有一个Java实现。

此外，如果您的数据是静态的（即您不在手机上更新数据），请考虑DAFSA来完成您的任务。 它是存储单词最有效的数据结构之一（必须比“标准”尝试和基数尝试都更好，无论是对于大小还是速度，比紧凑尝试速度更快，通常比紧凑尝试大小更好）。 有一个很好的C ++实现：dawgdic - 您可以使用它从命令行构建DAFSA，然后使用Java读取器读取生成的数据结构（例如实现在这里）。

- Mikhail Korobov

---

嗨。经过长时间的努力，我已成功创建了DAWG并从Java中读取它。它很小（537K）且速度非常快。然而，有一个问题阻止我永久关闭这个问题 - Github代码只能检查一个字符串是否是字典中任何单词的前缀，它无法检查该字符串是否是完整的单词。我浪费了一整天的时间来尝试解决这个问题。我的应用程序没有这个功能就无法工作。你能看一下吗？ - Bruce

@EvgenyKluev 是的，我可以这样做 - 但是我真的认为这个功能在那段代码中已经存在了 - 我只是找不到它。正在等待Mikhail的回复。顺便说一下，这里有一些测试DAWG的代码：https://dl.dropboxusercontent.com/u/19729481/DawgTest.7z 没有按预期工作。 - Bruce

嗨@Bruce，'contains'方法中缺少一个检查 - 它应该仅在与索引关联的值存在时返回True（return hasValue(index)而不是return true应该可以解决）。我自己没有测试/使用过Java实现；它可能适用于编写它的软件，但不适用于一般的Java实现。很抱歉浪费了您的时间。这个Python实现经过了大量测试，我非常确定它可以正确地工作：https://github.com/kmike/DAWG-Python/blob/eeb1aa11adb21eb6bc81274dea51950/dawg_python/wrapper.py#L34 - 如果有疑问，请参考它。 - Mikhail Korobov

啊，当然还有“规范”的C++源代码：https://code.google.com/p/dawgdic/source/browse/trunk/src/dawgdic/dictionary.h#78 - Mikhail Korobov

为了方便您，这里提供一个Eclipse项目的链接，用于测试dawg的Java实现，这样您就不必自己制作了 - https://dl.dropboxusercontent.com/u/19729481/DawgTest.7z - Bruce

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;
    }
}

- el.pescado - нет войне

---

我考虑过这个问题，但无法继续下去。如何表示trie的递归结构？数组中的父节点和子节点索引有什么关系？如何确保生成的trie与具有相同字节表示的其他trie不同？ - Bruce

@Bruce - 我看不出问题。 树的递归结构由这些索引值定义，这些索引值与其他所有内容一起进行序列化。 父节点和子节点索引相关联，因为子节点索引存储在父节点中，代替了子节点引用。 通过遍历整个数组来序列化数据，忽略 Trie 结构。 索引就是索引，无论它们是在文件中还是在数组中。 您不必进行二进制序列化（但如果您想要可以）- 如果您将一个节点序列化为每行文本（例如 CSV 文件），则节点编号也是行号。 - user180247

哦，抱歉昨天我完全误读了，可能太累了。现在我明白了，好简单啊。我会尝试并告诉你结果的。 - Bruce

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;
}

- Justin

---

字典单词。相信我，我需要在O（长度）时间内找到一个键是否是字典中任何单词的前缀。否则会有巨大的时间惩罚。通过使用数组，我如何确定一个键是任何单词的前缀？ - Bruce

利用二分查找，您应该能够在O(log N)的时间复杂度内找到字典中的前缀，其中N是字典中单词的数量。我会在我的答案中添加一些代码以提供示例。 - Justin

@Bruce 使用上述算法，在我的手机上查找一个包含200000个字符串元素的数组中存在一个由3个字母组成的前缀只需要不到1毫秒的时间。 - Justin

@Bruce，它还在大约5毫秒内找到了以给定3个字符前缀开头的1000多个字符串。 - Justin

@Bruce 具有讽刺意味的是，在我的手机上，这种方法的表现与Trie执行前缀查找的表现一样好，并且在返回所有包含前缀的字符串方面击败了Trie（优势很大）。 - Justin

Answer 4

这里是一种在磁盘上存储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')

- David Eisenstat

Answer 5

这并不是一种万能方法，但你可以通过进行一个大的内存分配而不是许多小的分配来稍微减少运行时间。

在下面的测试代码中（不是Java而是C ++，抱歉），当我使用“节点池”而不是依赖单个分配时，我看到了大约10％的加速。

#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);
}

- Nate Kohl

Answer 6

尝试预分配所有可能的子节点空间（256）的Tries会有大量浪费的空间。这会让您的缓存受到影响。将这些指向子节点的指针存储在可调整大小的数据结构中。有些Tries会通过使用一个节点来表示长字符串并仅在需要时拆分该字符串来进行优化。

- DanielV

Answer 7

你可以使用类似sqlite的数据库和嵌套集或Celko树来存储trie，而不是简单的文件。你还可以使用三分搜索trie构建更快、更短（节点更少）的trie。

- Micromega

Answer 8

我不喜欢在数组中通过索引来寻址节点的想法，仅仅因为它需要多进行一次加法操作（指针加上索引）。但是使用预分配节点的数组，你可以在分配和初始化上节省一些时间。而且通过保留前26个索引给叶节点，你也可以节省很多空间。这样，你就不需要分配和初始化180000个叶节点。

此外，通过索引，你将能够以二进制格式从磁盘中读取准备好的节点数组。这应该会快上几倍。但是我不确定你所使用的语言是什么。是Java吗？

如果你已经确认你的源词汇表已经进行了排序，你还可以通过比较当前字符串的一些前缀与前一个字符串来节省一些时间。例如，前4个字符。如果它们相等，你可以从第5层开始你的循环：

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

循环。

- Mikhail M

Answer 9

它是空间低效还是时间低效？如果你正在使用普通trie，那么在处理移动设备时空间可能是问题的一部分。尝试使用patricia/radix trie，特别是当您将其用作前缀查找工具时。

Trie: 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 / 基数（占用空间更少）trie： http://github.com/phishman3579/java-algorithms-implementation/blob/master/src/com/jwetherell/algorithms/data_structures/PatriciaTrie.java

- Justin

---

不，正如我在问题中提到的那样，时间是问题，而不是空间。它可能需要大约40MB的空间，这是可行的。我已经实现了所有功能 - 我只是想加快速度。请查看编辑后的问题。 - Bruce

@Bruce 我觉得令人惊讶的是，从180k个单词构建一棵trie树需要10秒钟的时间。例如，在我的本地PC上（2.0 GHz处理器和1GB内存），从200k个单词构建一个trie树只需要471毫秒，并且消耗34MB的内存，而从相同的数据构建压缩trie树则需要541毫秒并且消耗22MB的内存。我建议尝试使用开源版本，看看是否能获得更好的结果。 - Justin

"我的手机上10秒钟" - Bruce

@Bruce 我理解你的意思，但是你的trie性能如此之高，令人惊讶。我会在我的HTC上运行相同的代码，并回来检查。 - Justin

谢谢！顺便说一下，这是我的Trie树代码：http://pastebin.com/QkFisi09 单词列表：http://www.isc.ro/lists/twl06.zip 我在这个IDE上运行它：http://play.google.com/store/apps/details?id=com.jimmychen.app.sand&hl=en - Bruce

@Bruce 你会很高兴知道，我的Trie在我的手机上表现与你的相似。使用200K个条目加载Trie大约需要7秒钟。 - Justin

Answer 10

一般来说，Java中尽量避免从头开始创建大量对象，这既慢又有巨大的开销。最好实现自己的池类进行内存管理，一次性分配例如50万个条目。

另外，对于大型词汇表来说序列化太慢了。使用二进制读取快速填充上述提出的基于数组的表示即可。

- jochenleidner