没有分隔符的莫尔斯 - 最佳算法

Question

在摩尔斯电码中，有点和 破折号 以 1-4 为一组，由分隔符分隔。每组代表一个字母。单词之间有两个分隔符。三句之间.

解密基本摩尔斯电码的应用程序非常容易制作。但我的问题是，没有分隔符时如何解决问题？我知道会有大量无意义的结果，但这不是我的意思。我只需要以最高效的方式得到所有可能的结果。

这将是一个输入：

......-...-..---

这将是众多输出之一：

hello

你会怎么做？

Answer 1

读完“嘀”或“哒”后，您有两个选择：终止字母或继续当前字母。这将导致您的代码出现很多分歧，递归方法可能是实现这一点的好方法。

保留到目前为止可能的字符串的缓冲区，并在您到达字符串末尾并且与字母末尾重合时打印（或存储）结果。

这是 C 中的一个实现：

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

static const char *letter = "**ETIANMSURWDKGOHVF*L*PJBXCYZQ**";

void morse_r(char *buf, int len, const char *str, int code)
{
    if (*str == '[=10=]') {
        // end of string; print if staring new letter
        if (code == 1) printf("%.*s\n", len, buf);
    } else if (code < 16) {
        if (*str == '.') code = 2 * code;                    
        if (*str == '-') code = 2 * code + 1;

        // continue letter
        morse_r(buf, len, str + 1, code);

        // start new letter
        buf[len++] = letter[code];
        morse_r(buf, len, str + 1, 1);
    }
}

void morse(const char *str)
{
    char buf[strlen(str)];

    morse_r(buf, 0, str, 1);
}

int main()
{
    morse("......-...-..---");

    return 0;
}

这个实现非常简单。它使用简单的查找机制并且不检查字母是否实际存在。（letter 数组中的星号是有效的摩尔斯电码，但它们不是拉丁字母。）

这种方法也相当蛮力：它一遍又一遍地重新计算尾部。尾部的记忆将为孤独字符串的处理器节省大量额外工作。

而且，如您所知，将会有很多无意义的结果。上面的代码产生 20569 个字符串（其中一些带有星号，即无效）。当您在途中进行合理性或字典检查时，您可以防止许多递归。例如，连续的许多点会产生很多重复Es的废话。

编辑： 正如 Jim Mischel 指出的那样，对摩尔斯电码查找工作原理的解释是有序的。 Yves Daoust 在他的回答中提到了 trie。 A trie 是树形结构，用于存储单词；每个节点可以有与字母表中的字母一样多的 children。摩尔斯电码只有两个字母：滴（.）和哒（-）。因此，摩尔斯电码树是一棵二叉树。

尝试次数通常很少；单词相当长，许多字母组合不存在。莫尔斯尝试是密集的：莫尔斯字母编码很短，几乎每个组合都被使用。树可以存储为线性 "flat" 数组，类似于 heap。节点由其在数组中的索引 i 表示。左边的child就是2*i，右边的child就是2*i + 1.

在另一个 Morse-related 问题的 answer I posted 中可以找到更好更详细的解释，我从中获取了我在上面示例中使用的查找代码。

Answer 2

IMO 最有效的方法是使用 trie。这是一棵树，每个节点最多有两个儿子，一个用于 .，一个用于 -，当这些字符在给定阶段可能出现时。除了指向子节点的链接之外，节点还有一个 "terminal" 字符，表示从根节点到该节点的路径编码的字符；终端字符可以是零，表示路径不对任何字符进行编码（字符串未完成）。

由于摩尔斯字母表很小，您甚至可以手动构建 trie。这是其中的一部分。

. => E
    . => I
        . => S
        - => U
    - => A
        . => R
        - => W
- => T
    . => N
        . => D
        - => K
    - => M
        . => G
        - => O

要利用 trie，请编写一个递归函数，将输入流中的一个位置和 trie 中的一个节点作为输入。如果节点有终止字符，则将终止字符附加到输出字符串并将节点重置为 trie 的根。同时，跟随匹配下一个输入符号的儿子继续探索trie。

以下是示例中递归执行的几个第一步（分析前四个输入符号）：

. => E
    .|. => EE
        .|.|. => EEE
            .|.|.|. => EEEE
            .|.|.. => EEI
        .|.. => EI
            .|..|. => EIE
            .|... => ES
    .. => I
        ..|. => IE
            ..|.|. => IEE
            ..|.. => II
        ... => S
            ...|. => SE
            .... => H

Answer 3

你可以分 2 次完成。第一个将标记字母可能结束的位置，第二个将提取所有可能的字符串。

您可以将第一关实现为动态规划。如果可以将前 x 个字母解析为某些字符，则 possible[x] 为真。您从 possible[0] = true 开始，然后为所有其他 x 计算 possible 的值。要计算它，你需要最后的 1、2、3 和 4 个字符，如果它们匹配一些现有的莫尔斯代码，并且可能对应于字符串其余部分的值为真，那么标记 possible[x] 也为真。这是 O(N)。

现在你必须提取所有可能的单词。所以，从头开始，用possible向量来剔除错解。在这里你应该再次尝试最后的 1-4 个字符，看看它们是否匹配，如果它们匹配，则相应的 possible 位置为真，那么你将它作为一个可能的字符并递归调用该函数以生成所有解决方案剩下什么。不幸的是，在最坏的情况下（当可能进行分区时），这是指数级的 O(4^N)。实际上，这将运行通过与输入字符串匹配的可能单词的数量，因此如果只有几个选项，此传递也会很快。

请注意，字符串越长，您就越有可能拥有更多选择和更多可能的解释。

如果您另外将可能的单词限制在预定义的集合中，您可以修改第一遍以使用单词而不是单个字母。那么可能的解释数量应该会减少很多，即使在更长的字符串上，你的算法也会很快。

没有分隔符的莫尔斯 - 最佳算法

Morse without separators - best algorithm

algorithm

cryptography

morse-code

processing-efficiency