算法 [codewars] 上一道关于摩斯电码的习题 我看了答案也没想明白

2604249649 · 2022年12月25日 · 最后由 mikasa 回复于 2023年12月12日 · 545 次阅读

原题链接:Decode the Morse code, advance

本题的关键是要找出比特串的传输速率,我想了很久也没想明白,然后我看了答案之后就更不明白了

...
t = bits.scan(/1+|0+/).map { |x| x.length }.min
...

答案大多使用类似上面的方法来求出比特串的传输率,我没明白为啥找到 0 串和 1 串长度最小的那个就一定是当前比特串的传输速率

有大佬知道这题比特串的传输率到底是怎么求的么?

摩尔斯电码实际上是一个声音,声音是有长、有短的,短点称“嘀”,长一些的称“嗒”,。嘀嗒实际上都是信号连通状态。题目中,有个自动化的设备,按照固定速度接收声音(想象一个接收员拿笔在纸上记录接听到的声音,该接收员 A 的听写记录速度是固定的,每分钟记录 60 次,每秒听一次记一次)。A 开始记录。

发送方开始发送:嘀嗒滴 暂停 答滴答。

熟练发送方:嘀(1 秒)停顿 嗒(3 秒)停顿 嘀(1 秒)暂停 嗒(3 秒)停顿 嘀(1 秒)停顿 嗒(3 秒)

由于记录方每秒记录一次,如果是接收到信号,就会记录 1,暂停时就会记录 0,所以记录方 A 会在纸上写:1011101000111010111(假设停顿为 0,暂停为 000)

不熟练方发送:嘀(2 秒)停顿 嗒(6 秒)停顿 嘀(2 秒)暂停 嗒(6 秒)停顿 嘀(2 秒)停顿 嗒(6 秒)

则记录方记录的为:1101111110110001111110110111111

可以看出,上面的传输同样的信息(都是滴答滴 嗒嘀嗒),不熟练发送方,记录方的记下的字符串要长的多,所以串长越小,速度越快(在速度固定的情况下,通常认为同一个发送方不会发送的忽快忽慢,是以固定速度发送,找到最短的就是发送速度)。

以上理解不知妥否,仅供探讨。

y9info 回复
  1. 假设我只需要发送一个字母‘T',’T'对应的摩尔斯电码是一个‘-’(三个时间单位)。
  2. 我假定一个时间单位可以传输 2 个比特位,那么它对应的比特串就是‘111111‘,使用参考答案给的方案,逆向计算出的比特传输率就是 6 了,明显不对啊。
  3. 不论假定一个时间单位可以传输多少个比特位,对于只传输单个字母‘T'而言,这种找 0 串和 1 串长度最小值的方法貌似都不适用

T'对应的摩尔斯电码是一个‘-’(三个时间单位),这里三个时间单位,翻译一下,其实你想表达的是,这里的‘-’(嗒)需要三个‘.’(嘀)的时间长度,我们假设一个时间单位是 1 微秒,也就是‘-’(111)需要 3 微秒;

假定一个时间单位可以传输 2 个比特位(11),也就是可以理解为接收方 1 微秒可以抄写 11(两个 1),这里结果应该是 3/2=1.5,这么变成了 6 了?是不是哪里概念梳理有误?

在我看来,’T'对应的摩尔斯电码是一个‘-’(三个时间单位),这里 3 个时间单位就可以理解为 3 个比特(111),要用连续的 111 来表示这个‘-’(嗒)时间很长。而‘.’(嘀)只要用一个 1 来表示即可。在嘀切换成嗒的时候,中间有停顿,信号中断(不中断怎么知道有嘀切换成了嗒?),所以这个停顿的信号中断可以表示为 0,也即在这个时间单位里边没有信号收到。(题目意思也是这样的,单词之间中断为 7 个时间单位,为 0000000)

  1. "Dot" – is 1 time unit long. 嘀 1 个时间单位 1
  2. "Dash" – is 3 time units long.嗒 3 个时间单位 111
  3. Pause between dots and dashes in a character – is 1 time unit long.嘀嗒之间中断(间隔),1 个时间单位,即:0
  4. Pause between characters inside a word – is 3 time units long.字母之间中断(间隔),3 个时间单位,即:000
  5. Pause between words – is 7 time units long. 单词之间中断(间隔),7 个时间单位,即:0000000

假设我们在 11:01:00 至 11:01:05 之间截获了一段字符串 1110011111100100100111000

那么有个问题,这里的第 6 位到第 11 位之间有“111111”(6 个 1),那么这 6 个 111 是不是当然的就代表发送方想发送 TT 呢?(按照上面所述 111 代表‘-’(嗒),也就是代表字母 T)。实际上,这还真不一定,因为假若发送方是个非常手慢的电报发送员,正常人是三个时间单位发 111 就搞定 T 的发送,但是这个手慢的,慢慢腾腾,速度只有别人的一半速度,他可能需要双倍的时间才能发送一个他想发送的 1。但是在接收方看来,这两个时间单位都是有信号状态,所以记作 11,但实际上在手慢的发送方来看,他只想发一个 1,只不过耗费了双倍时间。

所以我们要想翻译这串 1110011111100100100111000,首先要搞清楚发送方是个手慢的还是手快的电报员,也就是“传输率”。“我没明白为啥找到 0 串和 1 串长度最小的那个”实际上就是找出嘀或者嘀嗒中间中断(间隔)的那个时间单位,因为嘀或嘀嗒之间中断(间隔)都是占用 1 个时间单位,是上述 5 种情形中最小的(对应 1 和 3 两种情形,时间单位为 1)。找到手慢的发报员的 1 个时间单位,再折算为标准的嘀嗒,最后换算为字母和字符串就翻译出来了。

以题目中的“1100110011001100000011000000111111001100111111001111110000000000000011001111110011111100111111000000110011001111110000001111110011001100000011”为例,会发现最短的也是 00 或者 11。这时候我们会发现很奇怪,难道嘀嗒之间不是 1 个 0 吗?滴不是应该一个 1 吗?怎么会出现最小两个 0 或两个 1 的情况?这不符合常理。

那么只能理解为,发送信号的发报员是个慢手,他发原本想发报一个 0,但是我们这边收到显示是两个 0;他原本想发送一个 1(嘀),但是我们收到两个 1(滴滴)。这就说明收报的速度是发报速率的两倍,同样时间,发报员发出一个信号,结果收到两个信号。这样的话,这个字符串就要 2 位折算为 1 位,也就是“11”替换为 1,“00”替换为 0。

按照速率折换后,上述字符串转换为字符串 B:10101010001000111010111011100000001011101110111000101011100011101010001。

再对上述字符串 B,按照 1-5 的规则,对应翻译一下,就是题目的“···· · −·−− ·−−− ··− −·· ·”,两者完全能对上

需要 登录 后方可回复, 如果你还没有账号请 注册新账号