3

我一直在考虑数据冗余,只是想在我继续这样做之前把所有的东西都写下来(此外还要仔细检查这个想法是否已经付诸实践)。

好了,就到这里吧。

互联网上充斥着冗余数据,包括文本、图像、视频等。因此,gzip 和 bzip2 通过 HTTP 进行动态压缩和解压缩已经付出了很多努力。像 Google 和 Facebook 这样的大型网站拥有整个团队,他们致力于加快页面加载速度。

我的“问题”与压缩仅基于每个文件gzip file.txt产量file.txt.gz)这一事实有关。毫无疑问,散布在互联网上的看似无关的数据之间存在许多共性。如果您可以存储这些公共块并在客户端或服务器端组合它们以动态生成内容怎么办?

为了能够做到这一点,人们必须在 Internet 上找到最常见的数据“块”。这些块可以是任何大小(这里可能有一个最佳选择),并且结合起来,需要能够表达任何可以想象的数据。

出于说明目的,假设我们有以下 5 块常见数据 - a, b, c, d, and e. 我们有两个文件包含这些块。我们有名为chunkand的程序combinechunk获取数据,通过 bzip2、gzip 或其他一些压缩算法对其进行压缩,并输出包含所述数据的块(压缩后)。combine扩展块并解压缩连接的结果。以下是它们的使用方法:

$ cat gettysburg.txt
"Four score and seven years ago...cont'd"
$ cat test.txt
"This is a test"
$ chunk gettysburg.txt test.txt
$ cat gettysburg.txt.ck
abdbdeabcbdbe
$ cat test.txt.ck
abdeacccde
$ combine gettysburg.txt.ck test.txt.ck
$ cat gettysburg.txt
"Four score and seven years ago...cont'd"
$ cat test.txt
"This is a test"

例如,当通过 HTTP 发送文件时,服务器可以chunk将数据发送给客户端,然后客户端可以combine处理分块数据并呈现它。

有没有人尝试过这个?如果不是,我想知道为什么,如果是,请发布您如何使这项工作。一个不错的第一步是详细说明您如何弄清楚这些块是什么。一旦我们弄清楚了如何获取这些块,然后我们就会弄清楚这两个程序chunkcombine可能如何工作。

我可能会对此给予赏金(取决于接收),因为我认为这是一个非常有趣的问题,具有现实世界的影响。

4

4 回答 4

3

您问是否有人以前做过类似的事情以及块大小应该是多少,我想我会向您指出我想到的两篇论文:

  • (一个团队)谷歌正试图通过利用文档之间共享的数据来加速网络请求。服务器将预先计算的字典传递给客户端,其中包含文档之间共有的数据,并在以后的请求中被引用。这一次仅适用于单个域,并且 - 目前 - 仅适用于 Google Chrome:基于 HTTP 的共享字典压缩

  • (一个团队)微软在他们的工作“使用远程差分压缩优化有限带宽网络上的文件复制”中确定,对于他们的文件系统同步情况,大约 2KiB 的块大小可以很好地工作。他们使用一定程度的间接性,以便重新创建文件所需的块列表本身被分成块——这篇论文读起来很有趣,并且可能会给你关于如何完成事情的新想法。

不确定它是否对您有帮助,但如果有帮助的话。:-)

于 2009-12-27T22:16:31.340 回答
1

您实际上不必为最常见的块分析它 - 事实上,这种分布式决策可能真的非常困难。这是怎么回事:

让我们以 HTTP 数据传输为例。将每个文件分成 10MiB 块(或您关心的任何大小,我确信每种方式都会对性能产生影响)并计算它们的 SHA-256(或一些您相当确定应该可以安全防止冲突的哈希)

例如,您有文件 F1,其中包含块 B1..Bn 和校验和 C1..Cn。现在,HTTP 服务器可以简单地使用列表 C1..Cn 响应对文件 F1 的请求

为了使它真正有用,客户端必须保留一个已知块的注册表 - 如果校验和已经存在,只需在本地获取块。完毕。如果不知道,要么从本地缓存中获取它,要么从刚刚获得校验和列表的远程 HTTP 服务器中获取块。

如果您曾经从任何服务器(甚至是完全不同的服务器)下载另一个文件,该文件恰好共享一个块,那么您已经下载了它,并且它与您选择的哈希算法一样安全。

现在这并没有解决存在偏移的情况(例如,一个文件是

AAAAAAAA

和另一个

BAAAAAAAA

压缩算法可能可以处理。但也许如果你自己压缩块,你会发现无论如何你都会节省大部分......

想法?

于 2009-12-27T21:34:09.987 回答
1

有一种更简单的方法来处理文本数据。目前,我们将文本存储为代表声音的字母流。但是,语言的单位是单词而不是声音。因此,如果我们有一个包含所有单词的字典,然后将指向这些单词的“指针”存储在文件中,我们就可以通过使用指针并查找单词列表来动态重构文本。

这应该立即将事物的大小减少 3 或 4 倍。在这种方法中,单词与您想到的块相同。下一步是常用词组,如“this is”、“i am”、“full moon”、“seriously dude”、“oh baby”等。

单词列表也有助于拼写检查,应该由操作系统实现。为什么拼写检查器不是操作系统的一部分?

于 2009-12-27T22:57:04.947 回答
0

与您的答案不完全相关,但您已经看到了。微软(和其他)已经提供了边缘网络来托管 jquery 库。您可以引用这些相同的 URI,并获得用户从不同站点访问文件以及浏览器缓存文件的好处。

但是,您在过去 20 分钟内引用了多少其他人引用的内容(任意数字。)?您可能会在一家有很多员工共享应用程序的大公司看到一些好处,但否则我认为您将很难确定您想要的块,这将超过共享它的任何好处。

于 2009-12-27T22:55:29.177 回答