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

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 == '\0') {
        // 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 个字符串(其中一些带有星号，即无效)。当您在途中进行合理性或字典检查时，您可以防止许多递归。例如，连续的许多点会产生大量带有重复 E 的无意义单词。

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

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

可以在 answer I posted 中找到更好更详细的解释到另一个与莫尔斯相关的问题，我从那里获取了我在上面的示例中使用的查找代码。