1

我有一个唯一随机整数的排序数组，其值为 1<=x<=1,000,000,000。我可以用来将它们存储在数据库中的最节省空间的压缩算法是什么？我在想可能涉及位域的东西..

编辑：该数组的大小最多为 1,000,000,000。

4

4 回答 4

3

用于narray有效处理 Ruby 中的大型数值数组。

它更快，并且使用更少的内存。http://narray.rubyforge.org/

至于DB存储部分。可以将编组添加到narray（默认情况下没有）：

# This adds support for Marshal to NArray - found it at: http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/194510
class NArray
  def _dump *ignored
    Marshal.dump :typecode => typecode, :shape => shape, :data => to_s
  end
  def self._load buf
    h = Marshal.load buf
    typecode = h[:typecode]
    shape = h[:shape]
    data = h[:data]
    to_na data, typecode, *shape
  end
end

. . . 这将非常有效，无需您编写特定代码。

如果数字是完全随机的，那么您可以通过压缩实现的目标将受到限制。真正的随机数据几乎是不可压缩的。

如果您对数字的排列方式有一个很好的约束模型，那么您可以使用这方面的知识来创建更好的压缩比。建议使用 a 的帖子Range就是一个极端的例子，但当然只有当你有一个非常简单的结构时才有效。

如果结构或多或少是任意的，只需编组数据并对其应用现成的压缩算法，例如zlib.

编辑：项目已排序的事实有助于更好地压缩。它还勾选了一个框narray- 它比您可以使用 Ruby 手动执行的任何操作都更快地对数字进行排序Array

示例代码：

require 'narray'
require 'zlib'

# Ten thousand integers . . .
n = NArray.int(10000).random(100000).sort

# Compressed . . .
stored = Zlib::Deflate.deflate( Marshal.dump(n), 9 )

stored.length

 => 14297

这还不错，每个数字 1.5 个字节（实际压缩率会有很大差异，但使用这种技术通常会看到每个数字不到 4 个字节）

于 2013-04-04T09:55:19.253 回答
1

1..1,000,000,000 可以保存在 32 位整数中。如果数组是稀疏的，一个合理的编码是将每个有效元素表示为 2 个 32 位整数，一个是元素值，另一个是元素索引。对于数组中的每个有效元素，您需要 64 位/2 个整数，再加上 32 位/一个整数来存储数组中有效元素的数量。

于 2013-04-04T02:57:04.550 回答
1

您在 1..1e9 范围内有 1e9 个随机唯一整数，按排序顺序排列。这意味着您恰好拥有该范围内的每个整数之一。这是您使用 ruby​​ 进行的最佳压缩：

存储这个：

"(1..10**9).to_a"

然后把它读回来eval。

于 2013-04-04T03:41:07.690 回答
0

您没有提及数据集的大小。数据需要多随机访问？使用位字段压缩它可能会起作用，但您会浪费时间解压缩数据，更不用说 Ruby 不如 C 处理此类数据的效率高。除非空间是一个主要问题，否则我会将其作为数据库存储在具有单个整数字段的表中。

于 2013-04-04T02:13:11.843 回答