Ist Morsecode ohne Leerzeichen eindeutig entschlüsselbar?

54

Sind alle Morse-Code-Zeichenfolgen eindeutig entschlüsselbar? Ohne die Räume,

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

könnte sein, Hello Worldaber vielleicht ist der erste Buchstabe ein 5- in der Tat sieht es sehr unwahrscheinlich aus, dass eine willkürliche Folge von Punkten und Strichen eine eindeutige Übersetzung haben sollte.

Man könnte möglicherweise die Kraft-Ungleichung verwenden, aber das gilt nur für Präfix-Codes .

Morsecode mit Leerzeichen ist ein Präfixcode, in dem Nachrichten immer eindeutig dekodiert werden können. Sobald wir die Leerzeichen entfernen, ist dies nicht mehr wahr.


Gibt es eine Möglichkeit, alle möglichen Nachrichten aufzulisten, falls ich recht habe und alle Morse-Code-Nachrichten nicht eindeutig dekodiert werden können? Hier sind einige ähnliche Übungen, die ich auf codegolf.SE gefunden habe

John Mangual
quelle
7
Sie scheinen Ihre eigene Frage bereits beantwortet zu haben?
Raphael
7
"Morsecode ohne Leerzeichen" ist kein Morsecode. Die Leerzeichen sind Teil der Spezifikation, da der Code ohne sie nicht entschlüsselbar ist.
Stephen Kennedy
1
@StephenKennedy Das kommt schon in Frage. Hast du es komplett gelesen?
Raphael
3
Perl-Skript zum Auflisten möglicher Nachrichten für einen Code. Wusste nicht, dass dies eine rein theoretische Gemeinschaft war. :)
Squeezy
1
Sind Sie wirklich sicher, dass Ihre akzeptierte Antwort überhaupt als Antwort oder sogar als Hinweis auf irgendetwas qualifiziert ist? Ich meine, es ist offensichtlich, dass ET = A ... was beweist, dass Spielberg Recht hatte: ET ist ein Alien.
Babou

Antworten:

91

Die folgenden Meldungen sind beide plausibel, haben jedoch eine völlig andere Bedeutung:

SOS HELP      = ...---...  .... . .-.. .--.        => ...---.........-...--.
I AM HIS DATE = ..  .- --  .... .. ...  -.. .- - . => ...---.........-...--.
Celtschk
quelle
6
Süß, aber es wurde bereits festgestellt, dass Morse ohne Leerzeichen mehrdeutig ist, und ich denke nicht, dass dies viel mehr wert ist als ein Kommentar.
David Richerby
37
Die OP scheint zu fragen , ob eine Reihe von Punkten und Strichen ohne Leerzeichen als zwei „echte“ Nachrichten interpretiert werden könnte , als auf beliebige Sequenzen von gegenüberliegenden T und E . Das erste SOS! Hilfe! besteht aus zwei Interjektionen und die Sekunde, in der ich sein Date bin, ist ein grammatikalischer und vernünftiger englischer Satz, so dass beide gültige Botschaften sind. Dies beantwortet die Frage kurz und bündig mit einem Beispiel.
CJ Dennis
2
@CJDennis Die Frage sagt das überhaupt nicht. Es wird gefragt, ob Morsezeichenfolgen eindeutig entschlüsselbar sind und ob es eine Möglichkeit gibt, alle Zeichenfolgen aufzulisten, die für eine bestimmte Sequenz codieren, wenn Punkte und Bindestriche verwendet werden. Es sagt überhaupt nichts darüber aus, dass die Streicher im Englischen eine Bedeutung haben müssen.
David Richerby
2
Es gibt sowohl ein spezifisches (Gegen-) Beispiel als auch eine allgemeine Methode, um das Problem zu untersuchen, und beide sind für gute Antworten relevant. siehe zB Beweise / Widerlegungen von lakatos
vzn
3
"Was sagt es, Fähnrich?" I AM HIS DATE"Also hat Amelia beschlossen, mit dem alten Noonan zu fliehen , hmmm. Wir sollten das wahrscheinlich für uns behalten."
Dotancohen
36

Zitat von David Richerby aus den Kommentaren:

Da ⋅ E und - T darstellt, kann jede Morse-Nachricht ohne Leerzeichen als Zeichenfolge in interpretiert werden{E,T}

{EIN,ich,M,N}{E,T}?

Hier ist ein JavaScript, das Ihnen alle möglichen Interpretationen einer Zeichenfolge von .und zeigt -. Saiten mit einer Länge von bis zu 22 laufen in weniger als einer Sekunde, aber etwas Höheres wird langsam - ich würde zum Beispiel nicht versuchen, HELLO WORLD damit zu entschlüsseln. Sie können eine JavaScript-Konsole in Ihrem Browser öffnen, diese einfügen und dann beispielsweise aufrufen decode('......-...-..---'). (In diesem Beispiel ist Eintrag # 2446 die beabsichtigte Zeichenfolge "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'
};

Der Code zum Beschneiden auf nur Zeichenfolgen mit echten Wörtern ist etwas länger, daher setze ich ihn hier ein . Es läuft unter node.js und erwartet eine Datei unter /usr/share/dict/words-2500. Das Wörterbuch, das ich benutze, finden Sie hier . Es ist nicht naiv - es verkürzt sich, so dass es bei größeren Eingaben viel schneller läuft .

Das Wörterbuch besteht aus einer Liste von 2500 Wörtern, die ich irgendwo im Internet gefunden habe, abzüglich einiger 1-, 2- und 3-Buchstaben-Kombinationen, die ich nicht für Wörter hielt. Dieser Algorithmus reagiert empfindlich darauf, dass zu viele kurze Wörter zur Auswahl stehen, und verlangsamt sich drastisch, wenn Sie beispielsweise jeden einzelnen Buchstaben als Wort zulassen (ich sehe Sie an /usr/share/dict/words).

Der Algorithmus endet mit der Sortierung nach der Anzahl der Wörter, so dass die "interessanten" hoffentlich ganz oben stehen. Dies funktioniert hervorragend HELLO WORLD, wenn weniger als eine Sekunde vergangen ist und die erwartete Phrase als erster Treffer zurückgegeben wird. Daraus habe ich auch gelernt, dass DATA SCIENTIST(die einzige andere Phrase, die ich ausprobiert habe) Morse die gleichen Codes hat wie NEW REAL INDIA.

Edit: Ich habe ein paar Minuten nach interessanteren gesucht. Die Wörter SPACESund SWITCHsind Morsagramme. Bisher sind sie das längste Einzelwortpaar, das ich gefunden habe.

Aaron Dufour
quelle
3
Haben Sie gerade das Wort Morsagram erfunden ? Ich mag es sehr, aber eine Websuche lieferte einen einzigen Link - zu dieser Site.
BmyGuest
Ich habe mir auch die Freiheit genommen, diese interessante Frage in eine offene Herausforderung für Puzzling.SE zu verwandeln, mit einem Hinweis auf diesen Beitrag hier.
BmyGuest
@BmyGuest Ja, das ist ein komplett erfundenes Wort. Ich mag es aber irgendwie.
Aaron Dufour
17

Es genügt zu bemerken, dass bestimmte kurze Buchstabenkombinationen mehrdeutige Dekodierungen ergeben. Eine einzige mehrdeutige Sequenz reicht aus, aber ich sehe folgendes:

ATE ~ P
EA ~ IT
MO ~ OM

usw. Wie David Richerby in den Kommentaren festhält, entspricht jeder Buchstabe einer Folge von Es und Ts, was den Morsecode zweideutig macht, um beliebige Folgen von Buchstaben zu codieren. Die obigen Kombinationen zeigen, dass dies auch für plausible Buchstabenkombinationen in Englisch zutrifft (z. B. MEAT~ MITT). Vielleicht wäre es eine interessante Codierungsübung, alle Zeichenfolgen mit fünf oder weniger Buchstaben zu finden, die mit etwas anderem verwechselt werden könnten, und sich auf Buchstabenkombinationen zu beschränken, die tatsächlich im englischen Text zu finden sind (unter Verwendung eines oder mehrerer Wörter), gruppiert nach Äquivalenzklassen.

Mit Ihrem ursprünglichen Beispiel ist es auch so

HELLO WORLD ~ HAS TEAM NO MAID TOE

und während die rechte Seite vielleicht sogar als Teilbotschaft unrealistisch ist, handelt es sich sicherlich um eine Folge englischer Wörter, die ohne Computerhilfe in weniger als 15 Minuten gefunden werden könnten. Dies könnte als Beweis dafür angesehen werden, dass viele Phrasen im Englischen als eine andere (möglicherweise unsinnige) Folge von englischen Wörtern falsch interpretiert werden könnten.

Niel de Beaudrap
quelle
MT vs TM ist ein sehr kurzes Beispiel.
Raphael
2
@Raphael MT == TM == O Alle drei sind die gleiche Reihenfolge. Das macht es sehr schwierig zu übersetzen.
Red_Shadow
10

Morsecode ist eigentlich ein ternärer Code, kein binärer Code, daher sind die Leerzeichen erforderlich. Wenn keine Leerzeichen vorhanden wären, würde sich eine Menge Mehrdeutigkeit ergeben, nicht so sehr bei der gesamten Nachricht, sondern bei einzelnen Buchstaben.

Zum Beispiel sind 2 Punkte ein I, 3 Punkte ein S. Wenn Sie transkribieren und zwei Punkte hören, schreiben Sie sofort "I" oder warten Sie, bis Sie einen weiteren Punkt (oder Strich) hören?

Die Antwort ist, dass jeder Wert durch Leerzeichen getrennt ist, sodass sie zusammen gruppiert sind. Wenn Operatoren Nachrichten in Morse eingeben, machen sie nach jeder Buchstabencodesequenz eine Pause von der gleichen Länge wie ein Bindestrich, um das Ende der Sequenz anzuzeigen.

Selbst wenn Sie ein KI-Programm schreiben, um einen vollständigen Satz nach dem anderen zu betrachten und herauszufinden, was die logische Interpretation der Nachricht ist, würde dies zu vielen geringfügigen Unklarheiten und Rechtschreibfehlern führen

Tyler Durden
quelle
2
Ihr letzter Satz scheint abgeschnitten worden zu sein.
David Richerby
2
@DavidRicherby Ja, das liegt daran, dass ich versucht habe, einen Beitrag mit Morsecode ohne Leerzeichen zu verfassen.
Tyler Durden
4

ein paar Notizen in anderen (gut) Antworten nicht abgedeckt , aber die Forschung Vorwissen im Allgemeinen nicht und zitieren jede Sachen (für mich ein wesentlicher Bestandteil der Computerwissenschaft ).

  • Diese allgemeine Theorie von CS fällt in die Kategorie der Textsegmentierung und auch "Wortteilung" / "Disambiguierung", obwohl die Theorie dort etwas anders ist, es geht darum, Folgen von Symbolen in Wörter (mit variablen Buchstaben) usw. zu teilen, in denen die Symbole vorkommen sind Einheiten. Hier sind die Zeichenfolgen in Buchstaben aufgeteilt, wobei die Buchstaben eine variable Länge haben. Die Theorie ist jedoch analog, wenn auch nicht genau 1-1. dh Abbildung zwischen Sätzen in Wörtern, variablen Wortbuchstabenlängen und Sätzen in Wörtern, variablen Wort- / Buchstabenlängen.

  • wie andere darauf hingewiesen haben, kann dies empirisch untersucht werden. und jemand tat das aus einem Blickwinkel (es gibt mehrere Möglichkeiten, dies zu untersuchen) und veröffentlichte die Ergebnisse auf einer Webseite mit einem großen Verzeichnis / einer großen Ergebnistabelle.

    Ich habe 25.787 mehrdeutige Morse-Codewörter gefunden. Dies besteht aus 10.330 verschiedenen Morsezeichenfolgen. Das mehrdeutige Morsewort mit der höchsten Häufigkeit enthält 13 mögliche Spenderwörter. Die Ergebnisse sind in Tabellen zusammengefasst, die auf der Häufigkeit von Wörtern basieren, die dieselbe Morse-Darstellung aufweisen.

  • wow, "context matters" ... eine fast identische Frage "Übersetzen von Morsecode ohne Leerzeichen" zum Stackoverflow von vor 3 Jahren hat derzeit 0 Stimmen.

vzn
quelle
2

Im Allgemeinen gibt es exponentiell viele mögliche Dekodierungen, aber wenn Sie wirklich wollen, können Sie sie alle auflisten. Sie können sie auch prägnant auflisten, dh für alle eine prägnante Darstellung geben. Da dies nichts weiter als eine Programmierübung ist, fordere ich Sie auf, es selbst zu tun.

Die Tatsache, dass Mehrdeutigkeiten vorliegen, schließt jedoch nicht aus, dass die Nachricht oder zumindest große Teile der Nachricht entschlüsselt werden können. Unter der Annahme eines Wahrscheinlichkeitsmodells für den durch den Morsecode dargestellten Text - zur Sicherheit können wir davon ausgehen, dass er englisch ist und statistische Eigenschaften des Englischen verwendet - kann es möglich sein, die Nachricht im Wesentlichen zu decodieren, obwohl einige lokale Mehrdeutigkeiten unvermeidbar sein können. Der Grund ist, dass die meisten Decodierungen nicht-sinnlichen Klartext entsprechen. Die Möglichkeit besteht darin, den Algorithmus für die dynamische Programmierung aus dem vorherigen Absatz zu erweitern, um die Wahrscheinlichkeit jeder Decodierung abzuschätzen, und dann die maximale Wahrscheinlichkeit für die Decodierung auszuwählen. Dieser Ansatz hat mehr Erfolgschancen, wenn die Nachricht länger wird.

Yuval Filmus
quelle
Macht der Viterbi-Algorithmus nicht etwas Ähnliches wie das, was Sie beschrieben haben? Ist die Quantifizierung des exponentiellen Wachstums der Anzahl der Decodierungen eine geeignete Frage für diese Frage oder cstheory.SE?
John Mangual
1
Richtig, die Idee ist, dynamische Programmierung zu verwenden. Die Schätzung des exponentiellen Wachstums passt hier wahrscheinlich besser als in die Theorie.
Yuval Filmus
Tatsächlich ist dies sehr ähnlich zu dem, was getan wird, um Wörter in der Sprachverarbeitung zu identifizieren. Das Ergebnis ist ein sogenanntes Wortgitter, dh eine komprimierte Darstellung aller Wortsequenzen, die mit der analysierten Klangsequenz übereinstimmen könnten.
Babou
1

Wie man die Sprache aller möglichen Dekodierungen definiert / erkennt / generiert.

Ohne Leerzeichen ist der Morsecode eindeutig nicht mehr zu entziffern.

Es ist jedoch möglich, alle möglichen Arten der Dekodierung in komprimierter Form anzugeben. Dies ist tatsächlich ähnlich wie bei der Sprachverarbeitung: Aus einem eindeutigen Strom von Klängen (oder Phonemen) müssen Sie alle Möglichkeiten finden, wie sie in eine Folge von Wörtern zerlegt werden können. Die Algorithmen dafür erzeugen ein sogenanntes Wortgitter. Ein Beispiel finden Sie im Abschnitt "Lexikalische Mehrdeutigkeit" dieser Antwort .

Im Fall von binärem Morsecode (keine Leerzeichen) haben Sie nur Punkte und Bindestriche, aber das Problem ist dasselbe.

Sie können alle Übersetzungen wie folgt erhalten.

T

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

TWTW

Die Details lassen sich leicht herausarbeiten. Aber fragen Sie, ob Sie mehr brauchen.

babou
quelle
0

Ein Pseudocode für einen Löser, der alle möglichen Interpretationen liefert. Dies basiert auf ein paar kurzen Überlegungen, daher wären zusätzliche Beiträge willkommen. Die Methode akzeptiert zwei Eingaben, eine aus dem bisher übersetzten Text und die zweite aus dem Morsecode.

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)
        }

}

Dadurch werden alle möglichen Kombinationen von Buchstaben und Zahlen ohne Leerzeichen zwischen "Wörtern" ausgegeben. Wenn Sie die Zweideutigkeit beweisen wollten, würde dies sicherlich tun. Wenn Sie aussagekräftige Nachrichten erhalten möchten, suchen Sie nach Code, mit dem Hashtags in eine lesbare Sprache übersetzt werden sollen.

Unter Verwendung des oben genannten habe ich ein Programm in C # geschrieben, das das oben genannte tut. Ich habe es daran gehindert, 22 Millionen Möglichkeiten für die oben genannte Zeichenfolge zu nutzen, die sich in "Hallo Welt" übersetzen lassen. Das Morse-Code-Äquivalent von "Hallo" ergab 20.569 mögliche Ergebnisse. Ich habe auch die Zahlen nicht aufgenommen. Das wäre höher, wenn ich es ihnen erlauben würde.

Red_Shadow
quelle
Die Ausgabe eines solchen Algorithmus wäre ein Beweis dafür, dass eine einzelne Zeichenfolge mehrdeutig ist, aber es würde nicht beweisen, dass alle Zeichenfolgen mehrdeutig sind.
David Richerby
@DavidRicherby Alle Zeichenfolgen mit einer Länge> 1 sind mehrdeutig. Dies wurde an anderer Stelle auf dieser Seite bewiesen. Ich habe versucht, den zweiten Teil der Frage zu beantworten und ein Mittel bereitzustellen, um alle möglichen Lösungen aus einer Zeichenfolge zu extrapolieren.
Red_Shadow
Würden Sie aus Neugier Ihr C # -Programm teilen? Meine Perl-Version enthält 19796 mögliche Lösungen für das "HELLO" -Äquivalent. Höchstwahrscheinlich habe ich jedoch vergessen, einige Fälle auszugeben ...
Squeezy
1
Echter Quellcode ist hier offtopisch; Bitte veröffentlichen Sie es an einer anderen Stelle (Pastebin, Gist, ...) und verlinken Sie es nur.
Raphael