您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

神奇的数据恢复算法

时间:2020-01-23 12:29:05  来源:  作者:
神奇的数据恢复算法

 

今天码哥给大家带来一种数据备份与修复的技术——里德所罗门编码。

里德所罗门编码可是应用场景很多,例如我们耳熟能详的RAID(磁盘阵列),又例如在UDP传输中降低丢包导致的数据缺失的情况等等。

什么是里德所罗门编码

这里,先要介绍一种纠错方法——极大距离可分法(MDS)。这是一种很常见的纠错方法,它将原始数据分成等长的N份,并根据这N份数据生成M个冗余的校验数据。此时,M+N块数据中任意M块数据损失,也可以通过剩余N块数据经过计算来恢复原始数据。

里德所罗门纠错算法就是经典的MDS算法。

里德所罗门编码的理论基础

  • 范德蒙矩阵
神奇的数据恢复算法

 

  • 有限域算法
    • 伽罗华域

这里我们那先不过多解释,大家先对矩阵型形式混个脸熟,至于伽罗华域我们后面会说到。

里德所罗门编码的原理

在开始前,我们不得不引入一个数学问题——插值问题

在一些工程实践中,某些变量间是存在函数关系的,但通常不能用公式表示,只能用实验观测得到y=f(x),即一系列xi在函数上的值。有些公式非常复杂,计算其完整公式并不划算,因此我们希望用另一个函数p(x)来尝试逼近f(x)。

此时,假设在二维空间中有n个点,(x1, y1), (x2, y2), …, (xn, yn),希望得到一个多项式的解:

神奇的数据恢复算法

 

这个多项式可以满足我们的当前条件:

神奇的数据恢复算法

 

实际上,可以推演如下:

神奇的数据恢复算法

 

可以看到矩阵A即为范德蒙矩阵,而如果每个点的x值互不相同,那么范德蒙矩阵的行列式值必不为零(略过证明),那么矩阵A就存在逆矩阵。

由此,我们那可以看到,通过对插值问题的讨论,我们发现了一种数据恢复方式,即:

矩阵A * 矩阵B = 矩阵Y

矩阵A的你矩阵 * 矩阵Y = 矩阵B

下面,我们来说一下在里德所罗门编码中如何进行的编解码的。

例如,我有两段数据:

data = [
  [1,2,3,4],
  [5,6,7,8]
]

下面是构建系数矩阵A,A的构建方式是,上方为一单位矩阵,下方是范德蒙矩阵,且:

  1. 单位矩阵的行数与数据矩阵的行数一致,本例中为两行。
  2. 范德蒙矩阵的行数与冗余数据个数保持一致,本例中为一行。并且每行中的ai为前一行的值加1,首行的a1为1。

那么构建出的系数矩阵A为:

A = [
  [1, 0],
  [0, 1],
  [1, 1]
]

编码即为矩阵乘法,得到的结果为:

result = data * A = [
  [1,2,3,4],
  [5,6,7,8],
  [6,8,10,12]
]

可以看到,前两行与原始数据一样,最后一行则是冗余数据。

下面,我们来模拟解码过程,假设我们丢失了第二个数据[5,6,7,8],那么恢复过程如下:

首先,构建系数矩阵A':

A' = [
  [1, 0],
  [1, 1]
]

可以看到,我们跳过了[0, 1],是因为该行对应的数据丢失了,因此构建时也要相应去掉。

然后我们要对A'求逆,得到A'':

A'' = [
  [1, 0],
  [-1, 1]
]

最后,利用矩阵乘法恢复原始数据:

data = A'' * B = [
  [1,2,3,4],
  [5,6,7,8]
]

到此,似乎已经完成了数据丢失后的恢复,但细心的读者可能发现了,在计算逆矩阵的时候可能会存在小数,会造成精度损失,因此,恢复后的数据会和原始数据不一致。

这就是我们接下来要介绍的,数域的作用。

伽罗华域

为了避免矩阵运算中出现小数导致的精度损失,我们要将整个矩阵运算从实数域迁移到伽罗华域中。

伽罗华域是一种有限数域,其值范围为[0, 2^8-1],即0~255。

那么如何进行迁移呢?答案很简单,我们将矩阵中用到的加减乘除四则运算进行一些变换。

在伽罗华域中:

  1. 加法 a + b:被转换为实数域内的异或运算,即 a ^ b。
  2. 减法 a - b:同样是异或运算 a ^ b。
  3. 乘法 a * b:ilog((log(a)+log(b))%255),其中ilog为反对数运算,log为对数运算。伽罗华域上的对数与反对数运算结果在网上是有归纳总结的,可以直接查表获取,因此运算速度会非常快。
  4. 除法 a / b:如果a小于b,则结果为 c = ilog(255 - log(a) - log(b));否则,c = ilog(log(a) - log(b))。

由于本篇为纯理论类文章,涉及较多数学概念,如有纰漏还望告知,感谢您的观看!



Tags:数据恢复算法   点击:()  评论:()
声明:本站部分内容来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除,谢谢。
▌相关评论
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表
▌相关推荐
今天码哥给大家带来一种数据备份与修复的技术——里德所罗门编码。里德所罗门编码可是应用场景很多,例如我们耳熟能详的RAID(磁盘阵列),又例如在UDP传输中降低丢包导...【详细内容】
2020-01-23   数据恢复算法  点击:(6)  评论:(0)  加入收藏
相关文章
    无相关信息
最新更新
栏目热门
栏目头条