一个讨论题目，关于数据恢复的算法

earthengine

现有一个zip压缩过的文件，由于不适当地被当作文本文件进行了UNIX文本到MSDOS文本的转换，因此已经损坏。

但是，经过观察，损坏的文件有如下特征：

1、文件中所有的0x0D 0x0A字符串（有近1万处出现）要么原本是0x0A被转换成了0x0D 0x0A，要么原本就已经是0x0D, 0x0A
2、所有的0x0D字符串都没有动过。
3、文件中已经不存在单独出现的0x0A数据点。

现在已经完成了如下修复工作

1、假设所有0x0D 0x0A都是从0x0A转换来的前提下，目录区已经完全恢复（除了偏移量不正确）
2、文件中没有压缩的较小文本文件已经全部复原。
3、大约还有70个错误当作0x0A的数据点，这造成了20个文件解压时出现CRC校验错误。其余100多个文件都没有问题了。

剩下来的问题是一个排列组合。对于每一个错误文件（压缩后数据），以下信息是已知的：

1、错误文件内所有的0x0A的个数（在原始错误文件中，它们全部都是0x0D 0x0A），用T表示
2、其中要变成0x0D 0x0A的个数（因为正确的压缩后大小是已知的），用C表示
3、解压缩后的CRC32值（如果这个值有错，则压缩头的长度加大，解压时要出现一个“文件名与目录不相符”的错误，但这没有发生，因此我们假定所有的CRC都是正确的）
4、所有文件均使用RFC1951的"Deflate"算法进行。

T的最大值约1000, C的最大值约30，而文件解压后最大大小约2M。
现在要问，什么样的算法可以代价最小地找出所有错误所在的位置，而使得解压后的CRC值相符呢？
最笨的算法是，对每一个错误组合，试解压文件，然后计算CRC。这样对于以上最大值的情况，光是组合的数目已经是天文数字…………

[ 本帖最后由 earthengine 于 29-9-2009 19:19 编辑 ]

key

最好查一下dox2unix的源代码。如果有trim()之类的算法，你这个恢复就不用做了。
另外，zip文件有entry结构，这个结构可能有助于你部分恢复数据

原帖由 earthengine 于 27-9-2009 17:24 发表

                               
登录/注册后可看大图

现有一个zip压缩过的文件，由于不适当地被当作文本文件进行了UNIX文本到MSDOS文本的转换，因此已经损坏。

但是，经过观察，损坏的文件有如下特征：

1、文件中所有的0x0D 0x0A字符串（有近1万处出现）要么原本是 ...

earthengine

原帖由 key 于 28-9-2009 21:44 发表

                               
登录/注册后可看大图

最好查一下dox2unix的源代码。如果有trim()之类的算法，你这个恢复就不用做了。
另外，zip文件有entry结构，这个结构可能有助于你部分恢复数据

谢谢，

1、可以确认trim()是没有的，因为目前为止（把所有0x0D 0x0A 替换为0x0A后）文件长度和正确长度相比只少了70多个字节，且对于一些没有压缩的小文件来说，能够手工恢复正常。
2、我们正是利用了zip文件的结构，才能取得截止现在为止的成果。应该说，近200个文件恢复到只剩20个无法恢复，这个成果算是不错了。
3、剩下这20个文件是硬骨头，目前看来必须深入到压缩算法和CRC校验这一级别来寻找思路。

earthengine

简单概括一下问题：
一个2M大小的文件（已知CRC32值）使用deflate算法压缩，压缩结果有30个地方被删除了0x0D这个字节，而可能出错的地方有1000处。
问：能否/如何从1000个可能出错点里找到30个，当填充0x0D到该30个地方后可以解压为原来一样大小且CRC32相同的文件？

someonehappy

虽然不懂压缩算法，不过看上去这还就是个1000选30的排列组合问题，结果确实是天文数字，好像是2.x的57次方。
哪怕知道CRC32值了，应该也只能是对给定的数据进行校验，不可能因此猜测出数据来。减少检验次数的办法也许只有把这整个文件分段处理。比如说，取包含前10个0x0A 的数据片断，如果有办法对给定的片断做校验测试，得出结论说这个给定的值是正确的，或者肯定是错误的，那就可以减少需要测试的组合数，不过前提是这样分段作检验测试是可行的。