找回密码
 FreeOZ用户注册
查看: 1558|回复: 4
打印 上一主题 下一主题

[论坛技术] 一个讨论题目,关于数据恢复的算法

[复制链接]
跳转到指定楼层
1#
发表于 27-9-2009 18:24:30 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?FreeOZ用户注册

x
现有一个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 编辑 ]
回复  

使用道具 举报

2#
发表于 28-9-2009 22:44:32 | 只看该作者
最好查一下dox2unix的源代码。如果有trim()之类的算法,你这个恢复就不用做了。
另外,zip文件有entry结构,这个结构可能有助于你部分恢复数据

原帖由 earthengine 于 27-9-2009 17:24 发表
现有一个zip压缩过的文件,由于不适当地被当作文本文件进行了UNIX文本到MSDOS文本的转换,因此已经损坏。

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

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

评分

参与人数 1威望 +20 收起 理由
earthengine + 20 谢谢分享!

查看全部评分

回复  

使用道具 举报

3#
 楼主| 发表于 29-9-2009 14:30:03 | 只看该作者
原帖由 key 于 28-9-2009 21:44 发表
最好查一下dox2unix的源代码。如果有trim()之类的算法,你这个恢复就不用做了。
另外,zip文件有entry结构,这个结构可能有助于你部分恢复数据


谢谢,

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

使用道具 举报

4#
 楼主| 发表于 29-9-2009 20:24:25 | 只看该作者
简单概括一下问题:
一个2M大小的文件(已知CRC32值)使用deflate算法压缩,压缩结果有30个地方被删除了0x0D这个字节,而可能出错的地方有1000处。
问:能否/如何从1000个可能出错点里找到30个,当填充0x0D到该30个地方后可以解压为原来一样大小且CRC32相同的文件?
回复  

使用道具 举报

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

使用道具 举报

您需要登录后才可以回帖 登录 | FreeOZ用户注册

本版积分规则

小黑屋|手机版|Archiver|FreeOZ论坛

GMT+11, 14-12-2024 04:20 , Processed in 0.034688 second(s), 21 queries , Gzip On, Redis On.

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表