0

我不是在谈论特定的语言，只是在一般情况下。我试图通过用其 ascii 值替换每个字符来找出压缩文本文件的方法，以便结果是一个大数字。由于可以用更少的字符在数学上表达一个大数字，因此可以压缩文件。

4

4 回答 4

2

嗯，是的，一个很大的数字可以用数学方法表示，这样做可能会节省一些空间。因此，如果将每个字符转换为其 ASCII 值，则每个字符都会从单个字节扩展为 1、2 或 3 个字节。即，“A”变为“65”。“z”变成“122”。对于大多数文本，将膨胀比计算为 2.5 比 1。

所以取一个 1,000 字节的文本文件。将所有字符转换为其对应的 ASCII 值。您现在有一个 2,500 位数的号码。在某些情况下，该数字可以用少于 1,000 个字符表示。但这些都是特殊情况。通常，您不会通过首先将数据转换为原始大小的 2.5 倍的形式来压缩数据。

但如果你想尝试，这很简单。

Open input file as binary
Open output file as text

for each byte in input
    cast the byte to an int and output its string representation

在 C 中，最后一条语句如下所示：

printf("%d", (int)c);

假设这c是您从输入文件中读取的字节。

您现在有一个文件，其中所有字符都是 0-9。例如：

Hello, world

变成

72,101,108,108,111,44,32,119,111,114,108,100,

除了逗号不会在那里：

721011081081114432119111114108100

欢迎您尝试使用您的技术提出压缩方案。我认为您会发现它适用于可能输入的非常小的子集，并且当它起作用时，需要很长时间才能找到合适的数学公式。通过下载维基百科的全文并尝试压缩单个文章来进行测试很容易。当你认为你有一些运行良好的东西时，我当然会对测试它感兴趣。

于 2013-10-21T21:01:34.217 回答
1

首先，我们陈述一些假设：

  1. 您希望进行“无损”压缩，即希望能够在压缩后恢复文件。（否则，我们可以只用单个位 1“表示”每个文件）
  2. 文件中的文本假定为 ASCII，它只是一个单字节字符序列（实际上我们使用什么编码并不重要，只是为了简化事情）
  3. 任何可能的字符都同样可能出现在文本中（即，我们正在谈论的宇宙都是可能的文件）
  4. 每个单字节字符的取值范围为 0-255（已知为扩展 ASCII）

第一个设置答案：将文本转换为数字没有优势，因为它已经是一个数字

使用这些假设，任何文件实际上已经是一个大数，更具体地说，是大二进制数。如果文件有长度n字符，它是一个带8*n位的二进制数。因此，“将其转换为大数”没有任何优势，因为它实际上已经是一个数字。

我希望你清楚这个概念。

现在我们继续讨论“将文本转换为数字以压缩它”的实际可能性

第二个设置答案：有 12.5% 的空间节省，假设文件中只存在前 128 个字符

如果您正在查看一小部分文本，即当我们仅使用 ASCII 的前 128 个字符（即违反假设 4 )，这是更常用的字符集。在这种情况下，我们实际上可以将每个字符表示为 7 位二进制数而不是 8 位。通过这样做，我们已经节省了 12.5% 的空间。

现在，更有趣的一个。

第三个设置答案：有一个东西叫Huffman Compression

霍夫曼压缩通过利用字符的自然分布以更少的位表示每个字符来节省空间。在自然文件中，某些字符出现的次数比其他字符多（即违反假设 3），如果我们使用较短的位序列来表示这些字符，以使用更多位来表示其他不太常见的字符为代价，我们实际上可以节省空间. 当文件仅包含重复多次的单个字符时，ASCII 上的 Huffman 压缩的最佳性能为 87.5%。

于 2013-10-22T01:52:10.463 回答
0

您可以尝试使用范围编码器。它可以使用一小部分位。

于 2013-10-21T21:05:11.120 回答
0

这里有一些很好的答案，但我想补充几点。 justhalf有我认为的最佳点：

让我们看看如何将文本“转换”为数字：

1）比如说，你有一组 ASCII 字节。对于每一个，你写一个 0 到 255 之间的数字。每个整数占用多少空间？- 与 ASCII 完全相同的空间：这并非巧合，ASCII 只是一组用于解释数字 0-255 最初含义的规则。

2）您将每个字符交换为一个数字，然后将它们链接起来，然后存储该数字。这看起来不错，也许如果您有一个将“a”与“1”交换的规则：“aaaaaa”将映射到 111111，它可以存储在一个字节中！但是'k'='11'和'aa'=11'呢？（这似乎打破了 Jim Mischel 的回应？）

但是，这里有一个更严重的问题：您将长度为 n 的字符串存储在具有 256^n 个可能值的一组字节中。这很严格：您可能在某些时候需要所有这些表示。

您现在创建了从这些值到数字的一对一映射。仍然会有完全相同数量的可能数字：256^n（n 个字符中的每一个都有 2^8 种可能性）。表示 256^n 可能性的最小方法是使用 log_2(256^n) 位。这是8n。这应该很熟悉。这与我们之前的 n 个长度为 8 的字节相同！

您遇到的问题是，在不了解输入字母的分布（每个字母出现的可能性）的情况下，您可能会遇到每个字符的可能性相同的情况。
因此，用比其他字符串更小的表示来编码一些字符串并没有任何好处。

但是，正如其他人所提到的，如果您确实知道输入的分布函数。假设你的文本是一串 DNA，而你只有四个字母：'G,T,A,C'。每个字母只需要两位，并且可以将输入压缩四倍！

如需更多阅读，请查看 Wiki on Information Theory。

于 2013-10-22T07:41:37.097 回答