1

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

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

这将是一个输入：

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

这将是众多输出之一：

hello

你会怎么做？

4

3 回答 3

3

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

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

这是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是一种用于存储单词的树形结构；每个节点可以有与字母表中的字母一样多的子节点。摩尔斯电码只有两个字母：dit ( .) 和 dah ( -)。因此，摩尔斯电码树是二叉树。

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

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

于 2016-01-25T06:55:09.343 回答
2

IMO 最有效的方法是使用 trie。这是一棵树，当这些字符在给定阶段是可能的时，每个节点最多有两个儿子，一个 for.和一个 for 。-除了到儿子的链接之外，节点还有一个“终端”字符，告诉从根到该节点的路径编码什么字符；终端字符可以是零，表示路径不编码任何字符（字符串未完成）。

由于莫尔斯字母很小，您甚至可以手动构建特里树。这是其中的一部分。

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

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

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

. => E
    .|. => EE
        .|.|. => EEE
            .|.|.|. => EEEE
            .|.|.. => EEI
        .|.. => EI
            .|..|. => EIE
            .|... => ES
    .. => I
        ..|. => IE
            ..|.|. => IEE
            ..|.. => II
        ... => S
            ...|. => SE
            .... => H
于 2016-01-25T09:43:56.183 回答
0

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

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

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

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

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

于 2016-01-25T11:55:25.940 回答