压缩一个简短但重复的字符串

本文关键字：字符串 一个 压缩 | 更新日期: 2023-09-27 18:36:57

我正在开发一个 Web 应用程序，该应用程序需要获取查询字符串（特别是 GET 而不是 POST）上的文件列表，如下所示：

http://site.com/app?things=/stuff/things/item123,/stuff/things/item456,/stuff/things/item789

我想缩短该字符串：

http://site.com/app?things=somekindofencoding

字符串不是很长，从 20-150 个字符不等。 这么短的东西并不适合 GZip，但它确实有很多重复，所以压缩应该是可能的。

我不想要字符串的数据库或字典 - URL 将由与使用它的应用程序不同的应用程序构建。我想要一个可逆的压缩来缩短这个 URL。它不需要是安全的。

有没有现有的方法可以做到这一点？我正在使用 C#/.Net，但很乐意从其他语言/堆栈中改编算法。

压缩一个简短但重复的字符串

如果你可以用BNF表示数据，你可以为数据构建一个解析器。 除了发送数据之外，您可以发送 AST，其中每个节点将被标识为一个字符（如果您有许多不同的节点，则为多个字符）。在您的示例中

我们可以有 

files : file files
      | 
file : path id
path : itemsthing
     | filesitem
     | stuffthingsitem

您可以将文件列表表示为 path[id1，id2,...,idn]，使用 0，1，2 作为路径，输入为：

/stuff/things/item123,/stuff/things/item456,/stuff/things/item789
/files/item1,/files/item46,/files/item7

然后你最终会得到?things=2[123,456,789]1[1,46,7]

其中/stuff/things/item用 2 表示，/files/item/用 [...] 中的每个数字1表示 ID 因此2[123]将扩展到 /stuff/things/item123

编辑 该方法不必是静态的。如果必须动态发现重复的项目，则可以使用相同的方法并在标识符和令牌之间传递映射。在这种情况下，上面的例子将是

?things=2[123,456,789]1[1,46,7]&tokens=2=/stuff/things/,1=/files/item

如果语法这么简单，当然会做得更好

?things=/stuff/things/[123,456,789]/files/item[1,46,7]

使用如此短的字符串将重复的部分压缩到小于唯一值是可能的，但很可能必须基于约束可能的值，否则在"压缩"时实际上会增加大小的风险

你可以尝试使用原始放气的zlib（没有zlib或gzip标头和尾部）。 它通常会提供一些压缩，即使在由可打印字符组成的短字符串上，也会查找并利用重复的字符串。 我还没有尝试过，但也可以看看 smaz 是否适用于您的数据。

我建议获取大量现实生活中的示例 URL，以用于对可能的压缩方法进行基准测试。

相关文章：