3

对于生物信息学项目，我需要在Ruby中压缩大量位串（仅包含 0 和 1 的字符串）为更小的字符串以减少内存使用。

所以理想情况下，像“0001010010010010010001001”这样的字符串会变成像“2a452c66”这样的字符串。我首先使用 MD5 哈希，直到我读到一些关于我想避免的可能冲突的内容。

我尝试了很多 unpack、to_i、to_s 等的不同组合，但似乎无法获得正确的组合。

解决方案应该：

  • 保留任何前导 0。
  • 可逆。
  • 压缩（显然）。
  • 并且输出应该避免奇怪的字符。最好我想留在字母数字空间。(a-zA-Z0-9)。

谢谢！

4

2 回答 2

4

尝试：

FORMAT = '%0.*b'

bitmask = "0001010010010010010001001"
bitmask.to_i(2) # => 2696329
hexval = bitmask.to_i(2).to_s(16) # => "292489"
FORMAT % [bitmask.size, hexval.to_i(16)] # => "0001010010010010010001001"

它正在做的是：

  • to_i(2)将字符串从二进制转换为其整数值只是为了显示正在发生的事情。
  • to_i(2).to_s(16)将其转换为字符串的十六进制表示。
  • FORMAT包含一个printf格式字符串，表示将传入的值转换为其二进制字符串表示形式 ( %b)，其前导0字节 ( %0b) 为未知长度 ( %0.*b)，它从传递的第一个参数 ( bitmask.size) 中获得。

这是另一个使用更长位掩码的示例：

bitmask = "11011110101011011011111011101111"

hexval = bitmask.to_i(2).to_s(16) # => "deadbeef"
FORMAT % [bitmask.size, hexval.to_i(16)] # => "11011110101011011011111011101111"

还有更长的时间：

bitmask = "1101111010101101101111101110111111111110111011011010110111011010"

hexval = bitmask.to_i(2).to_s(16) # => "deadbeeffeedadda"
FORMAT % [bitmask.size, hexval.to_i(16)] # => "1101111010101101101111101110111111111110111011011010110111011010"
于 2013-08-14T15:43:57.783 回答
3

只是一个有趣的观察：如果您想将 base-2 字符串转换为更高的 base（例如 base-n），压缩比为1/log2(n). 这意味着，如果您按照其他答案的建议转换为十六进制，您将获得原始文件的 25% 的压缩。一直移动到基数 64（仅比纯字母数字多 2 个符号），您将跳转到大约 17% 的压缩。这只是取决于你想在哪里进行权衡！

或者，如果您可以摆脱可逆性要求，只保留相等性，MD5 就可以了。请参阅MD5 产生冲突之前有多少随机元素？剧透：很多。您将阅读到的碰撞“问题”是有目的的碰撞；密码学家使用他们的 MD5 知识来发现冲突。出于所有实际目的，意外碰撞是不可能的。

更新

就在 Ruby 中实际实现 base64 编码而言，我不知道。我实际上并不了解鲁比。如果它本身不受支持，我会做一个由所有字母数字字符 + 2 组成的数组（因此数组长 64），然后使用该 6 位二进制数将 6 位二进制数字块转换为相应的字符作为字符数组中的索引。如果您想使用 62（或任何其他非二次幂），那么算法会有所不同。

于 2013-08-15T15:28:50.990 回答