标签: random-access

我正在寻找一个支持解压期间随机访问的通用压缩库。我想将维基百科压缩成单一的压缩格式，同时我想从中解压/提取个别文章。

当然，我可以单独压缩每篇文章，但这不会给出太大的压缩率。我听说 LZO 压缩文件由许多可以单独解压缩的块组成，但我还没有找到 API+文档。我也可以在 zlib 中使用 Z_FULL_FLUSH 模式，但还有其他更好的选择吗？

请推荐适合以下任务的技术.

我有一个相当大的(500MB)数据块,基本上是一个数字矩阵.数据熵很低(应该是可以很好地压缩的)并且存储位置很昂贵.

我正在寻找的是,使用一个良好的压缩算法(比如说,GZip)压缩它,并使用能够偶尔随机访问的标记.随机访问,如"从原始(未压缩)流中的位置[64位地址]读取字节".这与ZLIB等经典的deflator库有点不同,它可以让你连续解压缩流.我想要的是,每个字节读取的延迟,例如,多达1MB的解压缩工作的随机访问.

当然,我希望使用现有的库而不是重新发明NIH轮.

我们的一个应用程序目前依赖映射驱动器来访问本地网络上的大型媒体文件 (20-100MB)。

我们想将其更改为某种 Web 服务，以便我们可以使其更安全并将其移动到 Web 服务器（不依赖于本地网络）。

因为它们是大型媒体文件，所以我们需要随机访问这些文件（以便我们可以从任何点开始播放视频）。

我们有许多不同类型的媒体文件（MPEG、WMV、MOV、AVI 等），因此我们宁愿不将它们编码为特定格式。我们更喜欢一种允许我们访问文件的技术，就好像它是本地文件一样。

我们应该使用什么技术？

在RandomAccess的java doc中,类编写了"List实现使用的Marker接口,表明它们支持快速(通常是恒定时间)随机访问.此接口的主要目的是允许通用算法改变它们的行为以提供良好的性能.适用于随机或顺序访问列表."

但我发现了一些奇怪的事情

这是java.util包中AbstractList.java中的subList方法

public List<E> subList(int fromIndex, int toIndex) {
    return (this instanceof RandomAccess ?
            new RandomAccessSubList<>(this, fromIndex, toIndex) :
            new SubList<>(this, fromIndex, toIndex));
}

RandomAccessSubList类的实现:

class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
    RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
        super(list, fromIndex, toIndex);
    }

    public List<E> subList(int fromIndex, int toIndex) {
        return new RandomAccessSubList<>(this, fromIndex, toIndex);
    }
}

SubList类实现:

SubList(AbstractList<E> list, int fromIndex, int toIndex) {
    if (fromIndex < 0)
        throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
    if (toIndex …

我有大量的图像文件需要在HDFS上存储和处理

我们假设有两种情况:

1. 图像小于5MB
2. 图像范围从50KB到20MB

我想用图像做4件事:

1. 我需要独立地为每个图像应用一些函数fnc().
2. 我需要不时从HDFS中提取特定图像(1000次/天)并将其显示在网站上.这些是特定图像的用户查询,因此延迟应该是几秒钟.
3. 每年一次必须删除一组图像.
4. 新图像将添加到系统中(每天1000张新图像)

解决方案设计IMO应考虑:

1. 小文件问题:
2. MR处理
3. 快速访问文件
4. 快速写入新文件不是一个大问题,因为图像不会立即使用.延迟几分钟或几小时就可以了.

我的第一个想法是聚合图像以处理小文件问题,满足1和2. 但我留下了快速随机访问图像问题和添加新图像.我不知道如何处理这件事.

我查看了sequenceFiles,HAR,mapFiles,combineFileInputFormat,Avro,但无法找到(3)和(4)的解决方案.因为我必须负责索引块的内容,搜索和删除或添加新文件可能会变得棘手.

另一种方法是使用HBase或HCatalog来存储图像,这将照顾(1)(2)(3)和(4),但代价是什么？我知道在数据库中存储二进制BLOBS并不是非常有效,特别是随着图像数量的增加,但我认为可能HBase或HCatalog处理这个有点不同.

感谢您的帮助!

编辑:

我刚刚在HBase上发现这个线程用于提供图像,显然Yfrog和ImageShack有数十亿条带有图像的记录,这是一个很好的阅读链接.虽然如果有人知道任何基准会很棒.

所以我很想知道,什么是随机访问？

我搜索了一下,找不到多少.我现在的理解是,在容器中的"块"随机放置(如看到这里).随机访问意味着我可以访问容器的每个块,无论在什么位置(所以我可以在不经过所有块之前读取它在第5个位置上所说的内容),而在顺序访问时,我必须经历第1个,第2个,第3和第4到达第5街区.

我对吗？或者如果没有,那么有人可以向我解释随机访问和顺序访问是什么？

根据PDF 1.7 规范，第 90 页，第 3.4 节：

前面的部分描述了单个对象的语法。本节介绍如何在 PDF 文件中组织对象以实现高效的随机访问和增量更新。规范的 PDF 文件最初由四个元素组成（见图 3.2）：

• 标识文件符合的 PDF 规范版本的单行标题

• 包含构成文件中包含的文档的对象的主体

• 包含有关文件中间接对象信息的交叉引用表

• 提供交叉引用表的位置和文件正文中某些特殊对象的位置的预告片

基本上，该结构具有标题，然后是正文内容，然后是交叉引用表，最后是给出外部参照表位置的尾部。这里的关键部分是trailer和xref表位于文件的末尾，该xref表包含正文内容的相关元数据（主要是 10 位字节偏移量）。

鉴于外部参照表本身位于PDF 文件的最末尾：

• 我的浏览器（谷歌浏览器）如何在整个文件下载完成之前部分显示 PDF 文件（前一百页左右）？

查看我部分下载的 PDF 文件的屏幕截图：

是否可以创建从node.js中的文件的特定位置读取的流？

我知道我可以使用更传统的fs.open/seek/read API,但在这种情况下,我需要以某种方式将它们包装在我的应用程序底层的流中.

我正在寻找存储 E = (K, V) 元素的有序列表并在最多 O(log(N)) 时间内支持以下操作的数据结构，其中 N 是元素数。内存使用不是问题。

• E get(index) // 通过索引获取元素
• int find(K) // 找到 K 匹配的元素的索引
• delete(index) // 删除索引处的元素，以下元素的索引减1
• insert(index, E) // 在索引处插入元素，后面元素的索引加1

我考虑了以下不正确的解决方案：

• 使用数组: find, delete,insert仍然是 O(N)
• 使用数组 + K 的映射来索引：delete并且insert仍然会花费 O(N) 来移动元素和更新映射
• 使用链表 + K 到元素地址的映射：get并且find仍然会花费 O(N)

在我的想象中，最后一个解决方案是最接近的，但不是链表，而是一个自平衡树，其中每个节点都存储其左侧的元素数量，这将使我们可以get在 O(log(N) ）。

但是我不确定我是否正确，所以我想问问我的想象是否正确，这种数据结构是否有名称，以便我可以寻找现成的解决方案。

这里的其他一些问题是关于能够仅压缩大压缩数据文件的一部分/块的问题。允许某种“随机访问解压缩”。Bzip2 一直是此类功能的推荐之一。

在Wikipedia和一些称为非正式规范的文档上阅读有关 bzip 的信息后，尚不完全清楚此功能在什么级别上单独解压缩 bzip2 文件的一部分。似乎有两种选择，a）它在 s 的级别上BzipStream，b）它甚至在 s 的级别上StreamBlock（据我所知， a 内部可以有一个或多个BzipStream）。

\n

BZipFile:=BZipStream+\n\xe2\x94\x94\xe2\x94\x80\xe2\x94\x80BZipStream:=StreamHeader StreamBlock* StreamFooter\n   \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80StreamHeader:=HeaderMagic Version Level\n   \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80StreamBlock:=BlockHeader BlockTrees BlockData\n   \xe2\x94\x82  \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80BlockHeader:=BlockMagicBlockCRC Randomized OrigPtr \n   \xe2\x94\x82  \xe2\x94\x94\xe2\x94\x80\xe2\x94\x80BlockTrees:=SymMapNumTrees NumSels Selectors Trees\n   \xe2\x94\x82     \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80SymMap:=MapL1 MapL2{1,16}\n   \xe2\x94\x82     \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80Selectors:=Selector{NumSels}\n   \xe2\x94\x82     \xe2\x94\x94\xe2\x94\x80\xe2\x94\x80Trees:=(BitLen Delta{NumSyms}{NumTrees}\n   \xe2\x94\x94\xe2\x94\x80\xe2\x94\x80StreamFooter:=FooterMagic StreamCRCPadding\n

Run Code Online (Sandbox Code Playgroud)\n

尽管bzip2经常受到赞扬，但在我看来，每个 BzipStream 中的存档数据不是字节对齐的，而是位对齐的，这表明单个块的单独解压并不是应该发生的事情，虽然我不能确定，因此这个问题:)

更新

看看man bzip2recover手册页就知道了

\n

bzip2 以块的形式压缩文件，通常为 900kbytes 长。每个块都是独立处理的。如果介质或传输错误导致多块 .bz2 文件损坏，则可以从文件中未损坏的块中恢复数据。

\n\n

每个块的压缩表示由 48 位模式定界，这使得能够以合理的确定性找到块边界。每个块还携带自己的 …