如何有效地存储一组字符串空间

Question

假设我们有一组字符串

{"abc","def","ghia"}

存储字符串的节省空间的方法是什么？此外，给定一个输入字符串，如"abc"或"abc1"，我需要找出"abc"（是）或"abc1"（否）是否在字符串列表中，如果不在，则添加到字符串列表中。

进一步假设所有字符串只有26个小写字母，字符串的长度从0到无穷大。

Answer 1

听起来你正在寻找一个trie。

然而，请注意，trie更像是一个集合，而不是一个列表，因为元素是无序的，并且（在一个简单的实现中）不支持重复。

Answer 2

这取决于您的限制。R-way trie是检索存储数据的快速方法之一，它还提供了一种确定数据是否在集合中的方法，但R-way需要（R+1）N内存空间，因此在您的情况下为27N（N表示数据数量，R表示您的字符域）。

还有其他类型的trie需要较少的内存，比如三元搜索trie。但它需要4N的空间。如果首先考虑的是内存的足迹，那么这就是OrderedDict。

因此，如果你不能忍受这样的使用，你可以创建自己的数据类型，5位数据类型。因为26个字符只能用5位来表示。例如，"abc"的ISO9959-1编码为"0b01100001、0b01100010、0b011000 11"，但是这些可以是0b00001 00010 00011[0]（0用于填充）。

nChars           1  2  3  4  5
8byte-rep        8 16 16 24 32
5bits-rep.       5 10 15 20 25    
actual-req       8 16 24 32 40
(with 8bits-packing)
diff(saving)     0  0  8  8  8