刚刚查看了关于后缀数组的http://en.wikipedia.org/wiki/Suffix_array 。
它说它需要 O(n long) 空间，而字母的大小是 sigma。空间需求将是 O(blog sigma) 位？
想不出两个人的想法。。
这是我对后缀数组的了解。
后缀数组是具有 n 个整数的整数数组。那么，它需要 O(n)*8 个字节吗？作为一个整数，我们需要 8 个字节。而对于数组本身，我们需要 O(n) 个字节吗？假设有 n 个字符。
问问题
86 次
1 回答
0
实际上，后缀数组——假设没有使用压缩技术——是一个整数数组。但整数并不需要正好 8 个字节。
存储一个整数需要多少位？答案取决于整数的范围。如果范围是 [0,2)，即您感兴趣的唯一数字是 0 和 1，那么您需要 1 位来存储该整数。
如果您的范围是 [0,4)，即您要表示 0、1、2 和 3，那么您需要两位：00、01、10 和 11 是您可以用来表示的两位的四种可能组合四个不同的数字。
如果范围是最多 8 个数字，则需要 3 位，最多 16 个则需要 4 位，等等。一般来说，对于 R 不同数字的范围，您需要 ceil(log 2 (R)) 位。
后缀数组需要多少位？我假设文本的长度是 N 个字符。那么后缀数组的长度也是N，它的每个整数都指一个文本位置，即每个整数的范围是[0,N)。因此，您需要 ceil(log 2 (N)) 位来存储每个整数，并且由于总共有 N 个整数，因此总空间要求为 N ceil(log 2 (N)) 位（不包括为文本本身占用的空间）。
（但请注意，最近对后缀数组的大部分研究都是关于压缩它们，即找到仅使用 O(N) 位的方法（这称为简洁表示），甚至更少，即 o(N) 位（真正的压缩). 上面的简单计算仅适用于不使用任何压缩技术的标准情况。)
（还要注意，在实践中，许多实现将简单地使用unsigned intor 或类似的东西来表示整数，然后你会得到N*sizeof(int)*CHAR_BIT以位为单位的大小要求。）
于 2013-06-25T06:14:19.780 回答