小聪明与大智慧 IDA

niexining

本文面向和我初等水平的计算机爱好者。
用一个活生生的例子，讲述数学在计算机科学中的威力。
具体来说，就是和IDA的第一次亲密接触，用到的数学知识是线性代数。
IDA(Information Dispersal Algorithm) 信息分散算法
是一个信息分存方案：
"该算法实现了将一个长为L的文件F分割成n份,每份长度为L/m,任何m份都可以重构原文件."
熟悉此算法的可以不往下看了。
上午11点多了还不想起床，这时室友在电脑旁已工作良久。他说：起来吧，我和你讨论一个
数学问题，一个算法。
他知道我对微型智力游戏是有兴趣的，我果然睡不着了。
问题是这样的：
有个文件要分成5份分开存储----因为这个通信传感器之类的东西, 每个传感器的存储量很小,
只能存文件的一部分,而且在野外传感器会损坏, 存储的东西就丢失了,现在要设计一种分存方案,
使得部分传感器上的数据丢失后,还能恢复全部数据. 当然这里是存储冗余和可靠性的一个折中.
互相启发提醒之下,我们很快得出以下办法:
先考虑简单的情况吧: 如果分成3份, 就是3个数: 1,2,3
按如下存储,即可:
A: 1,2
B: 2,3
C: 3,1
这样A,B,C中任意一个丢失,比如,B丢失, A,C的信息照样完整.
而这就像是一个串铁环,环环相扣,环与环之间有重复(或叫冗余).
环与环之间重复有多少，就是冗余参数了．一边的极限是：没有冗余：
A: 1
B: 2
C: 3
这样当然使每个传感器存的东西最少，但可靠性最差，只要有一个坏了，数据就恢复不了了．
另一边的极限是：全部都重复：即
A: 1,2,3
B: 1,2,3
C: 1,2,3
这最可靠，只要有一个传感器在就行．如题目所说，传感器存储量小，不能这样．
中间的过渡是其它情况了．
比如分成5分,你可以:
A: 1,2,3
B: 2,3,4
C: 3,4,5
D: 4,5,1
E: 5,1,2
这样,任意损坏了两个, 都是可以恢复的.
"而且"，我自信的说："所有其它的安排方法都会和这些方法等同. 这样已包含了全部的可能情况.
当然,这样子做,是基于每个传感器损坏都是等可能的.如果不是等可能,即某些传感器更容易坏,
那情况就复杂了"
这里面没有多少严格证明,所靠的很多是直觉. 直觉, 在很多情况下不是最有用的吗?
我不禁要为自己的聪明飘起来.
这种自大很可笑. 原因一是: 这个题我虽然以前没见过,但同样的方法是我见过的.
在解决我的"炸弹问题"时,最后的方法就是这样,而且这个方法不是来自我的原创.
原因二下午下午才明白. 但我还是忍不住很得意. 确实, 如我们这样的人, 也就只能在
这种自欺的小成就上找安慰了.
马上就12点了,赶紧下去吃了午饭(或早饭). 饭后,室友仍然在看那篇文章.
那文章就是关于提出和解决这个问题. 我们一起看, 因为是英文的, 以我们的水平,
共同方法就是猜意思. 先开始,似乎和我们所得出的方法是同类的. 它把一个文件分成,
n份, 份与份之间是由重复的(其实不是这意思,它的原意是
"该算法实现了将一个长为L的文件F分割成n份,每份长度为L/m,任何m份都可以重构原文件.").
"这只是一种不同的表达方法而已." 我想.
但看到后来, 向量出来了, 矩阵出来, 范德蒙矩阵也出来了. 我认为这只是对我们那种方法的
严格数学证明, 虽然我原以为要证明它需要的是群论之类的描述对称同构的方法.
但发现越来越难对上号了, 这显然是一种不同的方法. 我盯着考虑良久, 都没有看懂.
下午我有课. 上课回来, 室友已经看懂了这种方法.  原来, 他用的知识并不难. 虽然很巧妙.
只是我那种"先入为主"的观念, 老是想把它解释成我那样的反法,结果很久都看不懂.是这样的:
它不是简单地将文件机械切割然后分存, 而是设计到编码问题. 我们知道文件都是按字节存储的.
每个字节对应一个整数. 比如有32个数, 要求实现损坏 50% 还能恢复的可靠性, 存在8个传感器中.
先把数据分成4行8列,比如如下:
data = [
[5,6,7,5,4,7,8,0],
[2,1,5,9,7,4,2,9],
[3,4,6,7,4,3,2,7],
[8,7,6,8,9,4,6,3]]
用一个8行4列的范德蒙行列式
vand=[
[1,1,1,1],
[1,2,4,8],
[1,3,9,81],
[1,4,16,64],
...
] 去乘数据矩阵, 得到8行8列的结果记为result
把result的每行各存到一个传感器中. 每个传感器中存8个数即可.
如果有4个传感器损坏,也即result的相应4行损坏. 比如1,2,3,4都损坏,
我们只需用vand的5,6,7,8行组成的矩阵的逆去乘result的5,6,7,8行,
即可得到完整的data.
用式表示为:
vand * data = result, 分开看的话:
vand任四行 * data = result相应四行
那么:
data = (vand相应四行)的逆 * result剩余四行
vandermonde矩阵保证了任4行都是可逆的, 所以最后一个式子总能得出来.
而我的方案是这样的:
把文件切成8分.
A1: 1,2,3,4,5
A2: 2,3,4,5,6
A3: 3,4,5,6,7
.....
A8: 8,1,2,3,4
上面的数字代表分数,而不是世纪数据;
结果每个传感器需要存5份, 8份中的5份, 要存20个数

如果有兴趣,可以拿程序试验一下.


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u1/54441/showart_1881139.html