4

我有文本文件格式的原始数据，其中包含大量重复标记（~25%）。我想知道是否有任何算法可以帮助：（A）以紧凑的形式存储数据（B），但允许在运行时重新构成原始文件。

有任何想法吗？

更多细节：

  • 原始数据在纯 html+javascript 应用程序中使用，用于使用正则表达式进行即时搜索。
  • 数据由包含（区分大小写）字母字符和少量标点符号的标记组成。
  • 标记用空格、换行符分隔。

迄今为止最有前途的算法：下面讨论的简洁数据结构，但重构看起来很困难。

http://stevehanov.ca/blog/index.php?id=120

http://ejohn.org/blog/dictionary-lookups-in-javascript/

http://ejohn.org/blog/revised-javascript-dictionary-search/

PS：服务器端 gzip 目前正在使用，但它只是一个传输层优化，并无助于最大限度地利用离线存储。鉴于 25% 的大量重复性，应该可以以更紧凑的方式存储，不是吗？

4

2 回答 2

1

鉴于实际使用还不清楚，我不知道这是否有用，但对于最小的总大小（html+javascript+data），有些人想出了将文本数据存储在灰度 .png 文件中的想法，一个字节到每个像素。然后，一个小的加载器脚本可以将 .png 绘制到画布上，逐个像素地读取它并以这种方式重新组合原始数据。这使您无需在 Javascript 中实现压缩即可缩小压缩。有关更多详细信息，请参见此处。

请不要使用这样的技术，除非您有非常深奥的要求，例如对于规模受限的编程竞赛。你的同事会感谢你的:-)

于 2012-05-14T16:23:52.437 回答
1

一般来说，尝试在 JavaScript 中实现压缩是个坏主意。压缩正是 JS 最不擅长的工作类型：CPU 密集型计算。

请记住，JS 是单线程的1，因此在解压缩数据的整个过程中，您都会阻塞浏览器 UI。相反，HTTP gzipped 内容由浏览器异步解压缩。

鉴于您必须重建整个数据集（以便针对正则表达式测试每条记录），我怀疑 Succinct Trie 是否适合您。老实说，我怀疑你会得到比原生 gzipping 更好的压缩。

1 - 尽管有网络工作者。

于 2012-05-14T16:55:41.513 回答