时间戳

首页 > 解决方案 > 双数组特里与三重数组特里

data-structures - 双数组特里与三重数组特里

问题描述

我正在阅读这篇文章：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意思，为什么？

我想了解使用双数组特里而不是三重数组特里有什么好处。

标签： data-structures

解决方案

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

在三重数组 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 和 check 数据，并且我们不会像第三个那样重复 base 信息。

在二数组中，下一个称为 base 并且 base 被丢弃，因为它并不是真正必要的。它存储和管理数据，这是很有价值的东西。

推荐阅读