双数组trie vs三数组trie

Question

我正在读这篇文章：https://linux.thai.net/~thep/datrie/，在Double-Array Trie一节的开头，它说

The tripple-array structure for implementing trie appears to be well defined, 
but is still not practical to keep in a single file. 
The next/check pool may be able to keep in a single array of integer couples, 
but the base array does not grow in parallel to the pool, 
and is therefore usually split.

the base array is usually split是什么意思?为什么？

我想知道使用双数组trie而不是三数组trie有什么好处。

Answer 1

我可以部分回答你的问题。

在三重数组trie中，我们有三个数组: base，next和check。基数组包含trie的不同状态。在下一个数组中，我们多次存储所有状态:一次是当它们是开始状态时，另一次是每次另一个状态转换到它们时。该支票拥有过渡的所有权。

使用三元组对trie进行建模的一种方法是使用三个数组( base、next和check )对结构进行建模。这是一个基本的实现。

trie {
  base:  array<S>;
  next:  array<S>;
  check: array<S>;
}

因为next和check具有有意义的数据、状态和所有权，所以对于同一索引处的转换，我们可以将这些数据成对建模。因此，数据结构有两个数组:基数组和对数组，包含下一个数组并在一个位置检查数据。

trie {
  base: array<S>;
  transition: array<Pair>;
}

Pair {
  next:  array<S>;
  check: array<S>;
}

我们可以将此实现用于：

trie {  
  transition: array<Triple>;
}

Triple {
  base: array<S>;
  next:  array<S>;
  check: array<S>;
}

这是一个糟糕的实现，因为它看起来像第一个，但基数组数据在每个转换中都是重复的。

在第二个实现中，base从next和check中分离，我们可以同时检索next和检查数据，并且我们不会像第三个中那样复制base信息。

在两个数组中，next被称为base，base被删除，因为它实际上并不是必需的。它存储和管理数据，这是很有价值的东西。