23

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

一切都很好，但唯一的问题是在我的手机上构建这个巨大的树（它有大约 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(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;
        }
    }

上面的代码可以更快吗？

我的尝试：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

4

10 回答 10

25

双数组尝试保存/加载非常快，因为所有数据都存储在线性数组中。它们的查找速度也非常快，但插入的成本可能很高。我敢打赌，某处有一个 Java 实现。

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

于 2013-09-27T21:08:16.090 回答
3

您可以将 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;
    }
}
于 2013-09-27T18:50:46.150 回答
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;
}
于 2013-09-27T18:53:52.020 回答
1

这是一种在磁盘上存储 trie 的相当紧凑的格式。我将通过它的（有效的）反序列化算法来指定它。初始化一个栈，其初始内容是树的根节点。逐个阅读字符并解释如下。字母AZ的含义是“分配一个新节点，使其成为当前栈顶的子节点，并将新分配的节点压入栈中”。字母表示孩子在哪个位置。空格的意思是“将栈顶节点的有效标志设置为真”。退格 (\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')
于 2013-09-27T20:29:55.160 回答
1

这不是灵丹妙药，但您可以通过分配一个大内存而不是一堆小的内存来稍微减少运行时间。

当我使用“节点池”而不是依赖于单独的分配时，我在下面的测试代码（C++，不是 Java，抱歉）中看到了约 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);
}
于 2013-09-28T04:07:54.790 回答
1

为所有可能的子节点（256 个）预先分配空间的尝试会浪费大量空间。你正在让你的缓存哭泣。将这些指向子节点的指针存储在可调整大小的数据结构中。

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

于 2013-09-28T04:45:36.893 回答
0

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

特里： http ://en.wikipedia.org/wiki/Trie

帕特里夏/基数特里： http ://en.wikipedia.org/wiki/Radix_tree

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

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

Patricia/​​Radix（空间高效）特里：http: //github.com/phishman3579/java-algorithms-implementation/blob/master/src/com/jwetherell/algorithms/data_structures/PatriciaTrie.java

于 2013-09-23T23:02:49.713 回答
0

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

此外，使用索引，您将能够以二进制格式从磁盘读取准备好的节点数组。这必须快几倍。但我不确定如何用你的语言做到这一点。这是Java吗？

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

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

从第 5 级循环。

于 2013-09-29T11:40:04.783 回答
0

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

于 2013-09-28T04:39:51.153 回答
0

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

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

于 2020-04-19T11:12:36.447 回答