¿Es el código Morse sin espacios únicamente descifrable?

54

¿Son todas las cadenas de código Morse exclusivamente descifrables? Sin los espacios,

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

podría ser, Hello Worldpero tal vez la primera letra es una 5, de hecho, parece muy poco probable que una secuencia arbitraria de puntos y guiones deba tener una traducción única.

Posiblemente se pueda usar la desigualdad de Kraft, pero eso solo se aplica a los códigos de prefijo .

El código Morse con espacios es un código de prefijo en el que los mensajes siempre se pueden decodificar de forma única. Una vez que eliminamos los espacios, esto ya no es cierto.


En el caso de que tenga razón, y todos los mensajes de código Morse no se puedan decodificar de forma exclusiva, ¿hay alguna manera de enumerar todos los mensajes posibles? Aquí hay algunos ejercicios relacionados que encontré en codegolf.

john mangual
fuente
77
¿Parece que ya has respondido tu propia pregunta?
Rafael
77
El "código Morse sin espacios" no es un código Morse. Los espacios son parte de la especificación porque sin ellos el código no es descifrable.
Stephen Kennedy
1
@StephenKennedy Eso ya está en la pregunta. ¿Lo leíste por completo?
Rafael
3
Script de Perl para enumerar posibles mensajes para un código. No me di cuenta de que se trataba de una comunidad puramente teórica. :)
Squeezy
1
¿Está realmente seguro de que su respuesta aceptada califica como una respuesta o incluso como una pista para algo? Quiero decir que es obvio que ET = A ... lo que demuestra que Spielberg tenía razón: ET es un Alien.
babou

Respuestas:

91

Los siguientes son mensajes plausibles, pero tienen un significado completamente diferente:

SOS HELP      = ...---...  .... . .-.. .--.        => ...---.........-...--.
I AM HIS DATE = ..  .- --  .... .. ...  -.. .- - . => ...---.........-...--.
celtschk
fuente
66
Lindo, pero ya se ha establecido que Morse sin espacios es ambiguo, así que realmente no creo que valga mucho más que un comentario.
David Richerby
37
El PO parece estar preguntando si una serie de puntos y rayas sin espacios podrían ser interpretados como dos mensajes "reales" en lugar de secuencias arbitrarias de T y E . El primer SOS! ¡Ayuda! está compuesto por dos interjecciones y la segunda que soy su cita es una oración gramatical y sensata en inglés, por lo que ambos son mensajes válidos. Esto responde la pregunta sucintamente al proporcionar un ejemplo.
CJ Dennis
2
@CJDennis La pregunta no dice eso en absoluto. Pregunta si las cadenas Morse son descifrables de manera única y si hay una manera de enumerar todas las cadenas que codifican una secuencia dada si hay puntos y rayas. No dice nada sobre las cadenas que tienen que tener significado en inglés.
David Richerby
2
hay un ejemplo específico (contador) y una forma general de estudiar el problema, y ambos son relevantes para la (s) buena (s) respuesta (s). ver, por ejemplo, pruebas / refutaciones por lakatos
vzn
3
"¿Qué dice, alférez?" I AM HIS DATE"Entonces Amelia decidió fugarse con el viejo Noonan , hmmm. Probablemente deberíamos guardar esto para nosotros mismos".
dotancohen
36

Citando a David Richerby de los comentarios:

{E,T}

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

Aquí hay algunos JavaScript que le indicarán todas las posibles interpretaciones de una cadena de .y -. Cadenas de hasta 22 de longitud se ejecutan en menos de un segundo, pero cualquier cosa más alta que eso comienza a ser bastante lenta; por ejemplo, no trataría de decodificar HELLO WORLD con ella. Puede abrir una consola JavaScript en su navegador, pegar esto y luego llamar, por ejemplo decode('......-...-..---'),. (En este ejemplo, la entrada # 2446 es la cadena deseada "HOLA").

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'
};

El código para podarlo solo a cadenas de palabras reales es un poco más largo, así que lo puse aquí . Se ejecuta en node.js y espera un archivo en /usr/share/dict/words-2500. El diccionario que estoy usando se puede encontrar aquí . No es ingenuo: se poda a medida que avanza, por lo que funciona mucho más rápido en entradas más grandes.

El diccionario consta de una lista de las 2500 palabras principales que encontré en Internet en alguna parte, menos algunas combinaciones de 1, 2 y 3 letras que no consideré palabras. Este algoritmo es sensible a tener demasiadas palabras cortas para elegir, y se ralentiza drásticamente si permite, por ejemplo, cada letra individual como palabra (lo estoy mirando,/usr/share/dict/words ).

El algoritmo termina ordenando según el número de palabras, por lo que las "interesantes" estarán en la parte superior. Esto funciona muy bien HELLO WORLD, se ejecuta en menos de un segundo y devuelve la frase esperada como el primer éxito. De esto también aprendí que DATA SCIENTIST(la única otra frase que probé) codifica morse igual que NEW REAL INDIA.

Editar: Busqué más interesantes durante unos minutos. Las palabras SPACESy SWITCHson morsagramas. Hasta ahora son el par de una sola palabra más largo que he encontrado.

Aaron Dufour
fuente
3
¿Acabas de inventar la palabra morsagram ? Me gusta mucho, pero una búsqueda en la web proporcionó un enlace único a este sitio.
BmyGuest
También me he tomado la libertad de convertir esta interesante pregunta en un desafío abierto en Puzzling.SE con alguna referencia a esta publicación aquí.
BmyGuest
@BmyGuest Sí, esa es una palabra completamente inventada. Me gusta un poco.
Aaron Dufour
17

Es suficiente observar que ciertas combinaciones cortas de letras dan decodificaciones ambiguas. Una sola secuencia ambigua es suficiente, pero puedo ver lo siguiente:

ATE ~ P
EA ~ IT
MO ~ OM

etc. Como David Richerby señala en los comentarios, cualquier letra es equivalente a una cadena de Es y Ts, lo que hace que el Código Morse sea ambiguo como una forma de codificar secuencias arbitrarias de letras; las combinaciones anteriores muestran que esto es cierto incluso en combinaciones de letras plausibles en inglés (por ejemplo, MEAT~ MITT). Quizás un ejercicio de codificación interesante sería encontrar todas las cadenas de cinco o menos letras que podrían confundirse con otra cosa, restringiendo las combinaciones de letras que realmente se pueden encontrar en el texto en inglés (usando una o más palabras), agrupadas por clase de equivalencia.

Usando su ejemplo original, también sucede que

HELLO WORLD ~ HAS TEAM NO MAID TOE

y aunque el lado derecho tal vez sea poco realista, incluso como un mensaje parcial, sin duda es una secuencia de palabras en inglés, y una que se puede encontrar en menos de 15 minutos sin ayuda de la computadora. Esto podría tomarse como evidencia de que muchas frases en inglés podrían interpretarse erróneamente como una secuencia diferente (posiblemente sin sentido) de palabras en inglés.

Niel de Beaudrap
fuente
MT vs TM es un ejemplo muy corto.
Raphael
2
@Raphael MT == TM == O Los tres son la misma secuencia. Eso hace que sea muy difícil traducir.
Red_Shadow
10

El Código Morse es en realidad un código ternario, no un código binario, por lo que los espacios son necesarios. Si no hubiera espacios, se generaría mucha ambigüedad, no tanto con todo el mensaje, sino con letras individuales.

Por ejemplo, 2 puntos es una I, pero 3 puntos es una S. Si está transcribiendo y escucha dos puntos, ¿escribe inmediatamente "I" o espera hasta escuchar otro punto (o guión)?

La respuesta es que cada valor está separado por espacios, por lo que se agrupan. Cuando los operadores escriben mensajes clave en Morse, hacen una pausa de la misma longitud que un guión después de cada secuencia de código de letras para indicar el final de la secuencia.

Incluso si escribiera un programa de IA para mirar una oración completa a la vez y descubrir cuál era la interpretación lógica del mensaje, aún habría muchas pequeñas ambigüedades y errores ortográficos que podrían

Tyler Durden
fuente
2
Su última oración parece haber sido truncada.
David Richerby
2
@DavidRicherby Sí, eso es porque traté de hacer publicaciones usando el Código Morse sin espacios.
Tyler Durden
4

algunas notas que no están cubiertos en otras respuestas (bueno), pero que generalmente dont la investigación y el conocimiento previo citan ninguna materia (para mí una parte intrínseca del equipo de ciencia ).

  • esta teoría general de CS cae en la categoría de segmentación de texto y también "división de palabras" / "desambiguación" aunque allí la teoría es un poco diferente, se trata de dividir secuencias de símbolos en palabras (con letras variables), etc., donde los símbolos son unidades aquí las cadenas se dividen en letras donde las letras tienen una longitud variable, pero la teoría es análoga, aunque no exactamente 1-1. es decir, mapeo entre oraciones en palabras, longitudes de letra variable de palabras y oraciones en palabras, longitudes de palabra / letras variables.

  • Como otros han señalado, esto puede estudiarse empíricamente. y alguien lo hizo desde un ángulo (hay varias formas de estudiar esto) y "publicó" los resultados en una página web con un gran directorio / tabla de resultados.

    Encontré 25,787 palabras de código Morse ambiguas. Esto está hecho de 10,330 cuerdas Morse distintas. La palabra Morse ambigua de mayor frecuencia tiene 13 posibles palabras de donantes. Los resultados se agrupan a continuación en tablas basadas en la frecuencia de las palabras que comparten la misma representación Morse.

  • wow, "el contexto importa" ... una pregunta casi idéntica "traducir código morse sin espacios" en stackoverflow de hace 3 años actualmente tiene 0 votos.

vzn
fuente
2

En general, hay exponencialmente muchas decodificaciones posibles, pero si realmente lo desea, puede enumerarlas todas. También puede enumerarlos de manera sucinta, es decir, dar una representación sucinta de todos ellos. Como esto no es más que un ejercicio de programación, te reto a que lo hagas tú mismo.

Dicho esto, el hecho de que haya ambigüedad no excluye la capacidad de descifrar el mensaje, o al menos grandes partes del mensaje. Suponiendo un modelo probabilístico para el texto representado por el código Morse, por seguridad, podemos suponer que es inglés y usar propiedades estadísticas del inglés, puede ser posible decodificar esencialmente el mensaje, aunque algunas ambigüedades locales pueden ser inevitables. La razón es que la mayoría de las decodificaciones corresponden a texto sin sentido. La forma de hacerlo es extender el algoritmo de programación dinámica del párrafo anterior para estimar la probabilidad de cada decodificación, y luego elegir la decodificación de máxima probabilidad. Este enfoque tiene más posibilidades de tener éxito a medida que el mensaje se alarga.

Yuval Filmus
fuente
¿El algoritmo de Viterbi no hace algo similar a lo que describiste? Cuantificar el crecimiento exponencial de la cantidad de decodificaciones, ¿es una pregunta apropiada aquí, o teoría.
John Mangual
1
Así es, la idea es usar programación dinámica. La estimación del crecimiento exponencial probablemente encaja aquí mejor que la teoría.
Yuval Filmus
en realidad, esto es muy similar a lo que se hace para identificar palabras en el procesamiento del habla. El resultado es lo que se llama una red de palabras, que es una representación condensada de todas las secuencias de palabras que podrían coincidir con la secuencia de sonido analizada.
babou
1

Cómo definir / reconocer / generar el lenguaje de todas las decodificaciones posibles.

Claramente, sin espacios, el código morse ya no es descifrable de manera única.

Sin embargo, es posible dar en forma condensada todas las formas posibles de decodificarlo. Esto es realmente similar a lo que se hace en el procesamiento del habla: a partir de un flujo único de sonidos (o de fonemas), debe encontrar todas las formas en que se puede descomponer en una secuencia de palabras. Los algoritmos para hacer esto producen lo que se llama una red de palabras. Encontrará un ejemplo en la sección "ambigüedad léxica" de esta respuesta .

En el caso del código Morse binario (sin espacios), solo tiene puntos y guiones, pero el problema es el mismo.

La forma en que puede obtener todas las traducciones es la siguiente.

T

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

TWTW

Los detalles se resuelven fácilmente. Pero pregunta si necesitas más.

babou
fuente
0

Algunos pseudocódigo para un solucionador que dará todas las interpretaciones posibles. Esto se basa en algunos pensamientos rápidos, por lo que sería bienvenido cualquier aporte adicional. El método acepta dos entradas, una del texto traducido hasta el momento y la segunda del 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)
        }

}

Esto generará todas las combinaciones posibles de letras y números sin espacios entre "palabras". Si quisieras probar la ambigüedad, esto ciertamente lo haría. Si desea obtener algunos mensajes significativos, intente buscar el código destinado a traducir hashtags a un lenguaje legible.

Usando lo anterior, escribí un programa en C # que hace lo anterior. Dejé de funcionar con 22 millones de posibilidades para la cadena anterior que se puede traducir a hello world. El equivalente del Código Morse de "Hola" resultó en 20,569 resultados posibles. Tampoco incluí los números. Eso sería mayor si los permitiera.

Sombra_roja
fuente
La salida de dicho algoritmo sería una prueba de que cualquier cadena individual es ambigua, pero no probaría que todas las cadenas son ambiguas.
David Richerby
@DavidRicherby Todas las cadenas de longitud> 1 son ambiguas. Eso se ha demostrado en otra parte de esta página. Intentaba responder la segunda parte de la pregunta y proporcionar un medio para extrapolar todas las posibles soluciones de una cadena.
Red_Shadow
Solo por curiosidad, ¿compartirías tu programa C #? Mi versión de Perl viene con 19796 posibles soluciones para el equivalente "HOLA". Lo más probable es que se olvidó de salida algunos casos, sin embargo ...
Squeezy
1
El código fuente real es offtopic aquí; publíquelo en otro lugar (pastebin, Gist, ...) y solo enlace a él.
Raphael