O código Morse sem espaços é exclusivamente decifrável?

54

Todas as seqüências de código Morse são decifráveis ​​de maneira única? Sem os espaços,

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

poderia ser, Hello Worldmas talvez a primeira letra seja uma 5- na verdade, parece muito improvável que uma sequência arbitrária de pontos e traços deva ter uma tradução única.

Pode-se usar a desigualdade de Kraft, mas isso só se aplica aos códigos de prefixo .

Código morse com espaços é o código de prefixo no qual as mensagens sempre podem ser decodificadas exclusivamente. Depois que removemos os espaços, isso não é mais verdade.


Caso eu esteja certo, e todas as mensagens do código Morse não possam ser decodificadas exclusivamente, existe uma maneira de listar todas as mensagens possíveis? Aqui estão alguns exercícios relacionados que encontrei no codegolf.SE

john mangual
fonte
7
Parece que você já respondeu sua própria pergunta?
Raphael
7
"Código Morse sem espaços" não é código Morse. Os espaços fazem parte da especificação porque sem eles o código não é decifrável.
Stephen Kennedy
11
@StephenKennedy Isso já está em questão. Você leu completamente?
Raphael
3
Script Perl para listar possíveis mensagens para um código. Não sabia que era uma comunidade puramente teórica. :)
Squeezy
11
Você realmente tem certeza de que sua resposta aceita se qualifica como uma resposta, ou mesmo como uma dica para alguma coisa? Quero dizer, é óbvio que ET = A ... o que prova que Spielberg estava certo: ET é um alienígena.
babou

Respostas:

91

A seguir, são duas mensagens plausíveis, mas com um significado completamente diferente:

SOS HELP      = ...---...  .... . .-.. .--.        => ...---.........-...--.
I AM HIS DATE = ..  .- --  .... .. ...  -.. .- - . => ...---.........-...--.
celtschk
fonte
6
Bonito, mas já está estabelecido que Morse sem espaços é ambíguo, então eu realmente não acho que isso valha muito mais que um comentário.
David Richerby
37
O OP parece estar perguntando se uma série de pontos e traços sem espaços poderiam ser interpretadas como duas mensagens "reais" em oposição a seqüências arbitrárias de T e E . O primeiro SOS! Socorro! é composto de duas interjeições e o segundo em que eu sou seu encontro é uma frase gramatical e sensata em inglês, de modo que ambas são mensagens válidas. Isso responde à pergunta de forma sucinta, fornecendo um exemplo.
CJ Dennis
2
@CJDennis A pergunta não diz nada disso. Ele pergunta se as strings Morse são exclusivamente decifráveis ​​e se existe uma maneira de listar todas as strings que codificam para uma determinada sequência, se pontos e traços. Não diz nada sobre as strings terem que ter significado em inglês.
David Richerby
2
existe um exemplo (contrário) específico e uma maneira geral de estudar o problema, e ambos são relevantes para boas respostas. veja, por exemplo, provas / refutações por lakatos
vzn
3
"O que diz, alferes?" I AM HIS DATE"Então Amelia decidiu fugir com o velho Noonan , hummm. Devemos provavelmente guardar isso para nós mesmos."
dotancohen
36

Citando David Richerby dos comentários:

{E,T}

{A,I,M,N}{E,T}?

Aqui está um JavaScript que mostra todas as interpretações possíveis de uma sequência de caracteres de .e -. Seqüências de caracteres de até 22 caracteres são executadas em menos de um segundo, mas qualquer coisa maior do que isso começa a ficar bem lenta - eu não tentaria, por exemplo, decodificar HELLO WORLD com ela. Você pode abrir um console JavaScript no navegador, colá-lo e chamar, por exemplo decode('......-...-..---'),. (Neste exemplo, a entrada # 2446 é a sequência pretendida "HELLO".)

var decode = function(code) {
  var cache = {
    '0': ['']
  };
  for(var start = 0;start < code.length;start++) {
    for(var len = 1;len < 6;len++) {
      if(start + len > code.length) continue;
      if(!cache[start + len]) cache[start + len] = [];
      var curCode = code.slice(start, start + len);
      if(dict[curCode]) {
        for(var i_start = 0;i_start < cache[start].length;i_start++) {
          cache[start + len].push(cache[start][i_start] + dict[curCode]);
        }
      }
    }
  }
  return cache[code.length];
};

var dict = {
  '.-': 'A',
  '-...': 'B',
  '-.-.': 'C',
  '-..': 'D',
  '.': 'E',
  '..-.': 'F',
  '--.': 'G',
  '....': 'H',
  '..': 'I',
  '.---': 'J',
  '-.-': 'K',
  '.-..': 'L',
  '--': 'M',
  '-.': 'N',
  '---': 'O',
  '.--.': 'P',
  '--.-': 'Q',
  '.-.': 'R',
  '...': 'S',
  '-': 'T',
  '..-': 'U',
  '...-': 'V',
  '.--': 'W',
  '-..-': 'X',
  '-.--': 'Y',
  '--..': 'Z',
  '.----': '1',
  '..---': '2',
  '...--': '3',
  '....-': '4',
  '.....': '5',
  '-....': '6',
  '--...': '7',
  '---..': '8',
  '----.': '9',
  '-----': '0'
};

O código para removê-lo apenas para seqüências de palavras reais é um pouco mais longo, então eu o coloco aqui . Ele é executado em node.js e espera um arquivo em /usr/share/dict/words-2500. O dicionário que estou usando pode ser encontrado aqui . Não é ingênuo - corta como vai, por isso corre muito mais rápido em entradas maiores.

O dicionário consiste em uma lista das 2.500 palavras que encontrei na Internet em algum lugar, menos algumas combinações de 1, 2 e 3 letras que não considerava palavras. Esse algoritmo é sensível a ter muitas palavras curtas para escolher e diminui drasticamente se você permitir, digamos, cada letra individual como uma palavra (estou olhando para você /usr/share/dict/words).

O algoritmo termina classificando com base no número de palavras, portanto, as "interessantes" devem estar no topo. Isso funciona muito bem HELLO WORLD, rodando em menos de um segundo e retornando a frase esperada como o primeiro hit. Com isso, também aprendi que DATA SCIENTIST(a única outra frase que tentei) os códigos morse são iguais a NEW REAL INDIA.

Edit: Eu procurei por mais interessantes por alguns minutos. As palavras SPACESe SWITCHsão morsagramas. Até agora, eles são o par mais longo de uma palavra que encontrei.

Aaron Dufour
fonte
3
Você acabou de inventar a palavra morsagram ? Eu gosto muito, mas uma pesquisa na web forneceu um único link - para este site.
BmyGuest
Também tomei a liberdade de transformar essa questão interessante em um desafio aberto no Puzzling.SE, com alguma referência a esta postagem aqui.
BmyGuest
@BmyGuest Sim, é uma palavra completamente inventada. Eu meio que gosto disso, no entanto.
Aaron Dufour
17

Basta observar que certas combinações curtas de letras produzem decodificações ambíguas. Uma única sequência ambígua é suficiente, mas posso ver o seguinte:

ATE ~ P
EA ~ IT
MO ~ OM

etc. Como David Richerby observa nos comentários, qualquer letra é equivalente a uma sequência de Es e Ts, o que torna o Código Morse ambíguo como uma maneira de codificar seqüências arbitrárias de letras; as combinações acima mostram que isso é verdade mesmo em combinações plausíveis de letras em inglês (por exemplo, MEAT~ MITT). Talvez um exercício de codificação interessante seja encontrar todas as seqüências de cinco ou menos letras que possam ser confundidas com outra coisa, restringindo as combinações de letras que podem ser encontradas no texto em inglês (usando uma ou mais palavras), agrupadas por classe de equivalência.

Usando seu exemplo original, também acontece que

HELLO WORLD ~ HAS TEAM NO MAID TOE

e, embora o lado direito seja talvez irreal, mesmo como uma mensagem parcial, é certamente uma sequência de palavras em inglês, que pode ser encontrada em menos de 15 minutos sem a ajuda do computador. Isso pode ser tomado como evidência de que muitas frases em inglês podem ser interpretadas incorretamente como uma sequência diferente (possivelmente sem sentido) de palavras em inglês.

Niel de Beaudrap
fonte
MT vs TM é um exemplo muito curto.
Raphael
2
@Raphael MT == TM == O Todos os três são da mesma sequência. Isso torna muito difícil a tradução.
Red_Shadow
10

O Código Morse é na verdade um código ternário, não um código binário, portanto os espaços são necessários. Se os espaços não existissem, haveria muita ambiguidade, não tanto com a mensagem inteira, mas com letras individuais.

Por exemplo, 2 pontos é um I, mas 3 pontos é um S. Se você está transcrevendo e ouve dois pontos, escreve imediatamente "I" ou espera até ouvir outro ponto (ou traço)?

A resposta é que cada valor é separado por espaço, para que sejam agrupados. Quando os operadores digitam mensagens em Morse, eles fazem uma pausa do mesmo tamanho que um hífen após cada sequência de código de letras para indicar o fim da sequência.

Mesmo se você escrevesse um programa de IA para analisar uma frase completa de cada vez e descobrir qual era a interpretação lógica da mensagem, ainda haveria muitas ambiguidades e erros de ortografia que

Tyler Durden
fonte
2
Sua última frase parece ter sido truncada.
David Richerby
2
@DavidRicherby Sim, é porque eu tentei postar usando o Código Morse sem espaços.
Tyler Durden
4

algumas notas não abordadas em outras (boas) respostas, mas que geralmente não pesquisam conhecimentos prévios e citam qualquer coisa (para mim uma parte intrínseca da ciência da computação ).

  • essa teoria geral do CS se enquadra na categoria de segmentação de texto e também de "divisão de palavras" / "desambiguação", embora a teoria seja um pouco diferente, trata-se de dividir seqüências de símbolos em palavras (com letras variáveis), etc., onde os símbolos são unidades. aqui as strings são divididas em letras em que as letras têm comprimento variável, mas a teoria é análoga, embora não seja exatamente 1-1. ou seja, mapeamento entre sentenças em palavras, comprimento variável da palavra-letra e sentenças em palavras, comprimento variável da palavra / letra.

  • como outros já apontaram, isso pode ser estudado empiricamente. e alguém fez isso de um ângulo (existem várias maneiras de estudar isso) e "publicou" os resultados em uma página da web com um grande diretório / tabela de resultados.

    Encontrei 25.787 palavras ambíguas do código Morse. Isso é feito de 10.330 seqüências Morse distintas. A palavra Morse ambígua de maior frequência possui 13 palavras possíveis de doadores. Os resultados estão agrupados abaixo em tabelas com base na frequência de palavras que compartilham a mesma representação Morse.

  • uau, "o contexto importa" ... uma pergunta quase idêntica "traduzindo código morse sem espaços" no stackoverflow de 3 anos atrás atualmente tem 0 votos.

vzn
fonte
2

Em geral, existem exponencialmente muitas decodificações possíveis, mas se você realmente quiser, pode listar todas elas. Você também pode listá-los de maneira sucinta, ou seja, fornecer uma representação sucinta de todos eles. Como isso não passa de um exercício de programação, eu desafio você a fazer isso sozinho.

Dito isto, o fato de haver ambiguidade não impede a capacidade de decifrar a mensagem, ou pelo menos grandes partes da mensagem. Assumindo um modelo probabilístico para o texto representado pelo código Morse - por definição, podemos assumir que é inglês e usar propriedades estatísticas do inglês - pode ser possível decodificar essencialmente a mensagem, embora algumas ambiguidades locais possam ser inevitáveis. A razão é que a maioria das decodificações corresponde a texto sem sentido. A maneira de fazer isso é estender o algoritmo de programação dinâmica do parágrafo anterior para estimar a probabilidade de cada decodificação e, em seguida, escolher a decodificação de probabilidade máxima. Essa abordagem tem mais chances de ter sucesso à medida que a mensagem fica mais longa.

Yuval Filmus
fonte
O algoritmo Viterbi não faz algo semelhante ao que você descreveu? Quantificando o crescimento exponencial do número de decodificações, essa é uma pergunta apropriada para aqui, ou cstheory.SE?
21413 John Mangual
11
É isso mesmo, a ideia é usar a programação dinâmica. A estimativa do crescimento exponencial provavelmente se encaixa aqui melhor do que a história.
Yuval Filmus
na verdade, isso é muito semelhante ao que é feito para identificar palavras no processamento de fala. O resultado é o que é chamado de treliça de palavras, que é uma representação condensada de todas as sequências de palavras que podem corresponder à sequência de som analisada.
babou
1

Como definir / reconhecer / gerar o idioma de todas as decodificações possíveis.

Claramente, sem espaços, o código morse não é mais decifrável exclusivamente.

No entanto, é possível fornecer de forma condensada todas as formas possíveis de decodificá-lo. Na verdade, isso é semelhante ao que é feito no processamento de fala: a partir de um fluxo único de sons (ou de fonemas), você precisa encontrar todas as maneiras pelas quais ele pode ser decomposto em uma sequência de palavras. Os algoritmos para fazer isso produzem o que é chamado de treliça de palavras. Você encontrará um exemplo na seção "ambiguidade lexical" desta resposta .

No caso do código Morse binário (sem espaços), você tem apenas pontos e traços, mas o problema é o mesmo.

A maneira como você pode obter todas as traduções é a seguinte.

T

wnWn+10nL={w}=L(W)T(L)T(L)

TWTW

Os detalhes são facilmente resolvidos. Mas pergunte se você precisa de mais.

babou
fonte
0

Algum pseudo-código para um solucionador que dará todas as interpretações possíveis. Isso se baseia em algumas reflexões rápidas, portanto contribuições adicionais serão bem-vindas. O método aceita duas entradas, uma do texto traduzido até agora e a segunda do código morse.

MorseSolver (string textSoFar, string codeRemaining)
{
    if(codeRemaining length == 0) output textSoFar
    else
    {
        codeLength = length of code remaining
        read 1 through (min of 5 or codeLength) characters from codeRemaining
        for each set of characters
        {
            call an IsMorseCode method that checks if the characters 
              input are valid morse code
            if they are valid add the translated character to textSoFar 
              and remove the characters from codeRemaining, then call 
              the MorseSolver again with the new strings)
        }

}

Isso produzirá todas as combinações possíveis de letras e números sem espaços entre as "palavras". Se você quisesse provar a ambiguidade, isso certamente o faria. Se você deseja receber algumas mensagens significativas, tente procurar um código destinado a traduzir hashtags em linguagem legível.

Usando o acima, eu escrevi um programa em C # que faz o acima. Eu parei de rodar em 22 milhões de possibilidades para a string acima que pode ser traduzida para olá mundo. O equivalente do código Morse a "Hello" resultou em 20.569 resultados possíveis. Eu também não incluí os números. Isso seria maior se eu permitisse.

Red_Shadow
fonte
A saída de um algoritmo desse tipo seria uma prova de que qualquer string individual é ambígua, mas não provaria que todas as strings são ambíguas.
David Richerby
@DavidRicherby Todas as cadeias de comprimento> 1 são ambíguas. Isso já foi comprovado em outras partes desta página. Eu estava tentando responder a segunda parte da pergunta e fornecer um meio de extrapolar todas as soluções possíveis de uma string.
Red_Shadow
Por curiosidade, você compartilharia seu programa C #? Minha versão do Perl apresenta 19796 soluções possíveis para o equivalente "HELLO". Provavelmente eu esqueci de enviar alguns casos ...
Squeezy
11
O código fonte real é offtopic aqui; publique-o em outro lugar (pastebin, Gist, ...) e vincule-o apenas.
Raphael