龙语文字构造讨论

Saphira · 2024-06-11 17:30:35

前段时间一直在想一个问题：~~众所周知，龙类一般生活在原生态区域。如果用爪子将文字刻在树干或者各类石头上难免会被环境一定程度侵蚀，破坏文字传递的信息。~~是否存在一种文字，可允许其占有表面积的任意10%消失但不损失信息？

以现实世界的数字举例，用爪子在树上写下"0123456789"（假设每个数字都占1平方厘米的面积），消失的10%恰好是一个完整数字，那显然会导致信息损失，故不符合命题。

初步猜想符合命题的文字应注重“计算”，文字的所有部分实际上都参与“推理并检验其他部分完整性”这个过程。

拓展问题：能否做到任意消失20%而不损失信息？文字可做到的极限消失率（不损失信息情况下的最大消失面积百分比）是多少？

Amorphous · 2024-06-12 04:56:59

当然是存在的！ [大笑]

例如，我使用这样的一种方法：

鉴于用爪子在木材上写字实际上是一件很麻烦的事情（木材的纹理走向导致各个方向的阻力不一致，没法好好写字），我只使用最简单的两种符号：1和x，这样刻起来简单，而且又好认。（后面为了计算方便，将x写作0）

假设我们一次传递四个字（位）的信息，为了满足容错的要求，我们需要多余的三个字来补充，最后，文字的形式是：

d1 d2 d3 d4 p1 p2 p3

然后规定使用这样的方法来计算p1,p2和p3，其中的加法的结果是不进位并对2取余数的，也就是：

1 + 0 = 1
1 + 1 = 0
0 + 0 = 0

p1 = d2 + d3 + d4
p2 = d1 + d3 + d4
p3 = d1 + d2 + d4

现在，假设我需要实际写出的文字是：

1 0 1 0

现在我们计算p1 p2 p3，

p1 = 0 + 1 + 0 = 1
p2 = 1 + 1 + 0 = 0
p3 = 1 + 0 + 0 = 1

附加在d位的后面，得到最终写成的文字：

1 0 1 0 1 0 1

好了，现在让我们尝试模糊（消失）其中的一位，例如让0被看错成1,反之亦然。

一共有7种出错情况，让我们分两类讨论。

当看错的是d位的时候：
使用d1举例：
现在，我们错误地读取了：

0 0 1 0 1 0 1

让我们重新计算p1 p2 p3，得到的结果是：

0 0 1 0 1 1 0

可以看到三个p位中只有p1的值符合，而p2 p3都不符合，这说明p1计算过程中不包含而p2 p3计算包含的位发生了错误，查看等式发现是d1（因为p1计算等式中没有出现d1，而p2 p3中出现了），因此，将d1反转即可解读正确的文字：

1 0 1 0

同理，出错在d2 d3位上的错误也可以这样被修正。
进一步，如果p1 p2 p3 的值都不符合，这提示我们出现错误的是d4，将d4反转即可得到正确的信息。

当错误的是p位的时候：
因为规定了至多一位出错，所以p1 p2 p3中必定只有一个p的值与计算结果不符合，这种情况下说明错误肯定出现在p位，没有影响到我们实际的前四位信息，可以直接读出信息。
例如当错误出现在p1时，我们读到：

1 0 1 0 0 0 1

而根据计算，应当是：

1 0 1 0 1 0 1

一个p位不符，出错肯定在p位上，直接读取前四位即可。

总之，通过这种方法，我们做到了即使14%的文字出错，其中的信息仍然能够被正确读取。
对于你的扩展问题：很容易看出如果我们要求更高的容错率，只需要增加p位即可，20%完全可以做到，只要你留下足够的冗余位用于纠错。

实际上，你的问题可以理解为：能否在一条带宽无限大的信道上，找到一种无误码的编码方式，而信息论指出：当信号传输速率尚未达到香农极限时，可以找到零错误率的编码方法，在这里你实际上没有限制信道的带宽（也就是我能写多少个字），所以本质上这是一条无限大带宽的信道，因此，只要错误率不是100%，一定可以找到零错误的编码方式。

Saphira · 2024-06-12 10:33:40

假设我们一次传递四个字（位）的信息

7个数字为一组，十组就有70个数字，消失10%允许消失总计7个数字。如果每组各消失1个数字则能根据这个纠错方法成功还原出正确的信息，那万一消失的7个数字在同一组里呢？这个数字组的信息就彻底丢失了。
~~我甚至不知道该数组是否存在过，更不用说还原出信息了~~

这个方法恐怕并不能保证连续的数字消失后依然可以还原，这就是我强调“任意消失10%”的原因。 [被炸]

最后修改： Saphira (2024-06-12 11:10:10)

安德Endur~ · 2024-06-12 17:19:10

提高通信系统可靠性的方法：增加冗余码 [被炸]
反正提高信道可靠性就得降低有效性了。
信号载波可以让信息在消息量不变的情况下冗余出一堆量出来，这堆量是可以随意糟蹋但是放在码里的。控制信道误码率在百分之十，可以通过一些方法计算出需要的编码方式。
特殊的编码方式可以识别错误信息，有的也可以通过一些算法把原码算出来，我记得QR好像遮住一部分还是能识别的。

[↑] @Saphira 写道: 7个数字为一组，十组就有70个数字，消失10%允许消失总计7个数字。如果每组各消失1个数字则能根据这个纠错方法成功还原出正确的信息，那万一消失的7个数字在同一组里呢？这个数字组的信息就彻底丢失了。 …

误码率不是说每100码里就有10个是错的，恢复成功率也不是百分百。

USB的串口也是普通的校验手段，外接摄像头以后传输出问题会一小排一小排出问题，UART也没提供恢复数据的方案。
显存出问题了一个画面里是每隔一段有一个小白块块，这时候会直接卡死，这是一整个储存介质出问题了，假如这个庞大系统通过特殊爪段允许内存重排，GPU应该是能不用这个显存来进行输出的，只管后续buffer充出去就行。
一般常用的手段是哈希值校验或者依据fft的校验方法。
对传统介质并且不能做高强度计算的生物来说，多复制几份应该是比设计一套冗余去冗余编码和解码更简单的——

最后修改：安德Endur~ (2024-06-12 17:35:57)

Lunamis午月 · 2024-06-12 19:48:08

[↑] @Amorphous 写道: 当然是存在的！ 例如，我使用这样的一种方法：鉴于用爪子在木材上写字实际上是一件很麻烦的事情（木材的纹理走向导致各个方向的阻力不一致，没法好好写字），我只 …

好奇这种内容算不算密码学。最近对密码相关的内容稍微瞭解了一点发现完全是打开新世界大门啊！

shiningdracon · 2024-06-12 20:37:52

@Saphira 写道: 这个方法恐怕并不能保证连续的数字消失后依然可以还原，这就是我强调“任意消失10%”的原因。

“任意”这个条件有点难处理。

我看到帖子的第一反应是冗余存储，第二反应是二维码（二维码带冗余纠错）。但是它们不符合“任意”+ “百分比”。
有“百分比”这个条件，靠“多抄几遍”就不行了。

第三想到的是全息摄影，把全息摄影的底片砸碎了，从每个碎片中都能还原出完整图像（只是分辨率会下降）。但这个就不是“文字”了，还是不符合条件。

最后修改： shiningdracon (2024-06-12 21:13:39)

shiningdracon · 2024-06-12 21:07:19

这样或许可以
用0123456789做原料拼成0123456789的字符画，可以任意丢失10%的字符而不影响解读

Saphira · 2024-06-12 21:23:16

用0123456789做原料拼成0123456789的字符画，可以任意丢失10%的字符而不影响解读

想了一下确实是好办法，各部分能检验其他部分的完整性。
（小问题是每个数字占的像素其实不一样。简单点说，虽然“十”和“龘”都是一个字，但是占的屏幕显示面积没法比，“十龘”消失10%没准能让“十”变成“一”）
不知道能不能顺着这个思路把“字”也加进来，而不仅仅局限于数字

龍爪翻書 · 2024-06-12 21:55:33

前一阵子正好看到一张图，好像就是删除10%也能保留原始意思?

安德Endur~ · 2024-06-13 00:06:05

有“百分比”这个条件，靠“多抄几遍”就不行了。

但多抄几遍，所有的副本合起来作为一个显示的结果就可行了嘛，QR也能用这个方法。但是卷积确实是不符合条件的，所以得用fft了。

Saphira · 2024-06-13 00:31:50

但多抄几遍，所有的副本合起来作为一个显示的结果就可行了嘛，QR也能用这个方法。

单个qr码消失的10%恰好是版本信息就扫不出来了，多抄几遍合起来会有一种可能：消失的10%全部集中于各qr码的版本信息
这样就都扫不出来了 [被炸]

Saphira · 2024-06-13 00:49:30

[↑] @龙爪翻书写道: 前一阵子正好看到一张图，好像就是删除10%也能保留原始意思? …

单字目前来看确实不难，消失10%不影响辨认。
难的是句子和更长的段落，集中消失10%有可能消失的是占面积较小的字，易改变原文意思。

Amorphous · 2024-06-13 03:06:44

[↑] @Saphira 写道: 单字目前来看确实不难，消失10%不影响辨认。难的是句子和更长的段落，集中消失10%有可能消失的是占面积较小的字，易改变原文意思。 …

不过，其实也不难，如果你的需要是能够应对无限长的文字任意部分不可辨认，仍然能够正常读取的话，那么我还可以想到这样的一种方法 [灵感] ：

仍然，我们假设只使用两种文字，发送的信息是:1 0 1

首先，让我们对文字按照位进行递增编号，假设我们要传达的是：

编号：0 1 2
信息：1 0 1

然后，我们来找出一个系数对2取余数的多项式，使得：
当 x 取编号的值时，多项式的值(模2)与信息对应位的值相等。

找出这种多项式的方法如下：

对于所有信息位为 1 的第i位，对于非i的所有编号，计算所有下面式子的乘积：

(x-除了i的所有编号)/(i - 除了i的所有编号)

然后将所有信息位为 1 的位计算出的结果全部相加。

例如，在给出的信息中，第0位和第2位的信息为1，所以我们需要对这两位进行计算：

i = 0
l(0) = (x-1)*(x-2)/(0-1)(0-2) = (x^2-3x+2)/2
i = 2
l(2) = (x-0)*(x-1)/(2-0)(2-1) = (x^2-x)/2

然后我们将所有的l相加，得到

F(x) = (2x^2 -4x +2 )/2 = x^2 -2x + 1

然后记得将多项式的系数对2取余数来简化运算：

F(x) = x^2 + 1 (x项的系数对2取余数得0所以没了)

我们可以检验一下，此时得到的F(x) = x^2 + 1这个多项式在x取编号的值的时候，所得到的值（对2取余）就是信息的值：

F(0) = 0 + 1 = 1
F(1) = 1 + 1 = 2 对2取余数 = 0
F(2) = 4 + 1 = 5 对2取余数 = 1

可见得到的值是完全正确的，现在，假设我们需要在k位信息损坏后仍然可以读取信息，我们将编号延长k，并且将每一个延长的编号代入F(x)来得到多余的信息的值。
例如我们让k=1：
F(3) = 9 + 1 对2取余数 = 0
所以有：

编号：0 1 2 3
信息：1 0 1 0

现在，我们完成了书写信息的部分。

现在让我们引入损坏，并尝试解读信息。当然，如果是多余的信息位损坏了，自然不用管，直接读取信息位即可，而如果有一个信息位被损坏，我们则可以再次执行剩下的三位重复之前的找出多项式的算法：
例如：第0位不可辨认：

编号：0 1 2 3
信息：? 0 1 0

现在，只有第2位信息为1，于是我们忽略第0位，对这一位进行计算：

i = 2
l'(2) = (x-1)(x-3)/(2-1)(2-3) = (x^2 + 4x + 3)/(-1)
F(x) = l'(2) = x^2 + 1 (对2取余)

可见，我们成功地恢复了多项式，然后，对于丢失的第0位，将x=0代入F(x)得到F(0) = 1：

编号：0 1 2 3
信息：1 0 1 0

我们成功恢复了损坏的信息。

可见，这个方法可以非常方便地将任意长度(m)位的信息扩展为m+k位，其中在任意位置丢失不超过k位信息即可还原原始信息。

实际上，这个方法的原理使用了多项式函数的性质，我们实际上将m位信息看作了一个多项式函数在0到m-1处的取值，然后使用了修改版的拉格朗日插值法，找到了一个满足这些位置处的取值，并且次数不超过m-1次的唯一的多项式（相当于将信息编码在了多项式上），然后对这个多项式过采样了k个样本。根据多项式函数的性质，可以使用这m+k个样本中的任意m个样本，再次使用拉格朗日插值恢复原始的多项式，进而通过代入的方法恢复任意位上的信息，但是，直接使用拉格朗日插值法有可能会得到系数很大的多项式，将值代入会造成很大的空间浪费，因此我这里其实还利用了模p有限域来剔除不必要的信息，这里p为了计算方便取的是2，并且因此假设语言中只有两个字母，因此其实这个方法可以扩展到有任意多字母的文字上，例如英文有26个字母，这种情况下可以选择使用大于26的最近的质数作为模数进行取余，例如29。

Amorphous · 2024-06-13 03:38:10

@Lunamis午月写道: 好奇这种内容算不算密码学。最近对密码相关的内容稍微瞭解了一点发现完全是打开新世界大门啊！

其实是不算的，尽管它的确使用了与密码非常相似的数学知识，但是他们的目的是完全相反的 [大笑] ，一个是为了一定程度增强信息之间的关联，从而在丢失一部分时可以恢复，另一个是为了让信息之间产生尽可能复杂的关系，从而让分析变得几乎不可能。

不过，很高兴你会去了解这些知识，在当前的时代，对密码的基本瞭解是很有必要的，这是在当前的时代中保护个龙隐私强而有力的手段。 [装酷]

Saphira · 2024-06-13 19:47:06

让我们对文字按照位进行递增编号

只有第2位信息为1，于是我们忽略第0位

消失第一位后信息只剩下010，为什么在后续运算中默认消失的是第一位 (让i=2) 而不是最后一位 (让i=1)？
换句话说，当一只龙看到剩余的信息是010时，如何判断原来的信息不是010x而是x010？

最后修改： Saphira (2024-06-13 19:57:49)

Amorphous · 2024-06-14 02:07:35

@Saphira 写道: 判断原来的信息不是010x而是x010？

    如果按照你的这种计算方式的话，他不能判断，在统计错误对信息的影响时，一般认为每位信息只会损坏，但是不会缺失。并且每个位本身的位置是能够确定的，这种处理方式让我们能够更专注于分析其根本的原理。
    你给出的010x和x010已经说明了问题，即使只讨论这两种情况，就一共已经有对应了原始信息的四种可能性了，相当于有两位错误，但是冗余位只有一位，因此，纠错最多只能消除两种可能性，所以会得到两个可能的结果。
    但是，位置，本质上也是信息，因此这种情况可以规约到每个位本身确定的情况，正如你加入了位置不确定的条件，实际上可以规约到发送5位信息错误2位，实际错误率为40%，超过了之前方法纠错25%的能力范围，这是不能纠错的根本原因。

因此，如果要求不同步（不能确定信息开始的位置）仍然能够解码，我们必须增加位数，同时，为了实际使用考虑，你需要考虑如何验证解码出的信息的正确性的问题，我在此给出一个比较简单粗暴的解决方案，能够同时解决这两个问题。

不改动先前的方法，而是修改所发送的信息，最简单的方法例如在每次的原始信息后面添加32个1，这种情况下，你可以尝试n-1次解码（假设前导位最多丢失n位），但是尽量均匀选择，并且不要选择这些连续的1所在的位置，否则校验强度会下降，直到解码出后面以32个1结尾的信息，我在这里假设多项式插值的性质导致从错误的位置开始解码往往得到的是均匀、混沌、随机的结果，因此，出现32个1的可能性大约是(n-1)/2^32，大概在42亿次解码中才能误打误撞解密出错误的信息，其他情况可以被我们通过后面没有32个1的方式过滤掉，同样这样做的一个好处是假设错误不密集出现在32个1的位置上，你可以使用最大似然估计来猜测信息开始的位置，减少一部分计算。（这个方法看起来简单，但是实际上存在风险：如果你故意选择到了这32个1进行解码，那么一定会得到可以通过校验的错误结果）

但是，如果你需要更强的验证，你可以将这32个1改为前面所有信息位输入一个杂凑算法得到的摘要，你可以认为基本只有相同的信息才能得到相同的摘要，这里你可以使用SHA2-256作为计算摘要的杂凑算法，它输入（基本）任意长度信息，输出256位结果，分布非常均匀，发生错误解码，并且解码出的信息的摘要值刚好是后面填充的这256位数(这是这个方法强的根本原因)的可能性约为~~（这里是抗原像碰撞性）~~(n-1)/2^256，这个数字是一个货真价实的天文数字，你可以认为错误解码事实上不可能发生。

现在，从何处开始解码以及解码后如何校验的问题已经解决了。

鳞目界域-龙论坛

公告

#1 2024-06-11 17:30:35 | 只看该作者 | 使用小说阅读模式