更快地构建trie

9 回答

• 22

  Double-Array tries保存/加载非常快，因为所有数据都存储在线性阵列中 . 它们的查找速度也非常快，但插入的成本可能很高 . 我打赌在某处有一个Java实现 .

  此外，如果您的数据是静态的（即您不在手机上更新），请考虑DAFSA为您的任务 . 它是存储单词最有效的数据结构之一（必须优于"standard"尝试和基数尝试的大小和速度，比简洁的速度尝试更好，通常比简洁的大小尝试更好） . 有一个很好的C实现：dawgdic - 您可以使用它从命令行构建DAFSA，然后使用Java reader获取结果数据结构（示例实现是here） .

  回复于 2024-04-20T06:14:51+08:00
• 1

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

  回复于 2024-04-20T06:14:51+08:00
• 3

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

  回复于 2024-04-20T06:14:51+08:00
• 0

  这不是一个神奇的子弹，但你可以通过做 one big memory allocation 而不是一堆小孩来减少你的运行时间 .

  当我使用“节点池”而不是依赖于单独的分配时，我在下面的测试代码中看到了大约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);
  }
  

  回复于 2024-04-20T06:14:51+08:00
• 0

  只需构建一个大的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);
  }
  

  获取String数组和前缀，在数组中打印出前缀的出现次数

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

  回复于 2024-04-20T06:14:51+08:00
• 0

  尝试预先释放空间所有可能的孩子（256）都有大量的浪费空间 . 你正在让你的缓存哭泣 . 将这些指针存储在可调整大小的数据结构中 .

  一些尝试将通过使一个节点表示长字符串来优化，并且仅在需要时断开该字符串 .

  回复于 2024-04-20T06:14:51+08:00
• 1

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

  回复于 2024-04-20T06:14:51+08:00
• 0

  我不喜欢通过数组中的索引来寻址节点的想法，但仅仅因为它需要再添加一个（指针的索引） . 但是对于预分配节点阵列，您可以在分配和初始化上节省一些时间 . 您还可以通过为叶节点保留前26个索引来节省大量空间 . 因此，您不需要分配和初始化180000个叶节点 .

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

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

  for（int level = 0; level <key.length（）; level）{

  循环从第5级 .

  回复于 2024-04-20T06:14:51+08:00
• 1

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

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

  Patricia / Radix 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

  回复于 2024-04-20T06:14:51+08:00