Le code Morse sans espaces est-il uniquement déchiffrable?

Toutes les chaînes de code Morse sont-elles uniquement déchiffrables? Sans les espaces,

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

pourrait être, Hello Worldmais peut-être que la première lettre est un 5- en fait, cela semble très improbable, une séquence arbitraire de points et de tirets devrait avoir une traduction unique.

On pourrait éventuellement utiliser l' inégalité de Kraft mais cela ne s'applique qu'aux codes de préfixe .

Le code Morse avec espaces est un code de préfixe dans lequel les messages peuvent toujours être décodés de manière unique. Une fois les espaces supprimés, ce n'est plus le cas.

Dans le cas où j'ai raison et que tous les messages en code Morse ne peuvent pas être décodés de manière unique, existe-t-il un moyen de répertorier tous les messages possibles? Voici quelques exercices liés que j'ai trouvés sur codegolf.SE

• https://codegolf.stackexchange.com/questions/36735/morse-decode-golf
• https://codegolf.stackexchange.com/questions/131/morse-code-translator

Les deux messages suivants sont plausibles, mais ont une signification complètement différente:

SOS HELP      = ...---...  .... . .-.. .--.        => ...---.........-...--.
I AM HIS DATE = ..  .- --  .... .. ...  -.. .- - . => ...---.........-...--.

Citant David Richerby des commentaires:

Puisque ⋅ représente E et - représente T, tout message Morse sans espaces peut être interprété comme une chaîne dans$\{E,T\}^*$

De plus, puisque A, I, M et N sont représentés par les quatre combinaisons possibles de deux caractères morse (-, ⋅⋅, -,-,, respectivement), tout message sans espace peut également être interprété comme une chaîne dans . Notez que pour tout message Morse de longueur> 1, ceci est distinct de l'interprétation de David. Ainsi, les seuls messages avec des interprétations uniques sont ceux de longueur 1 (et, je suppose, 0, si cela compte comme un message) - c’est-à-dire, ⋅, représentant E, et -, représentant T.$\{A,I,M,N\}^*\{E,T\}?$

Voici un code JavaScript qui vous indiquera toutes les interprétations possibles d’une chaîne de caractères .et -. Des chaînes allant jusqu'à 22 longueurs en moins d'une seconde, mais tout ce qui est plus élevé commence à devenir assez lent - je ne voudrais pas, par exemple, essayer de décoder HELLO WORLD avec. Vous pouvez ouvrir une console JavaScript dans votre navigateur, la coller puis appeler, par exemple decode('......-...-..---'). (Dans cet exemple, l'entrée n ° 2446 correspond à la chaîne "BONJOUR".)

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

Le code pour l'élaguer aux chaînes de mots réels est un peu plus long, donc je le mets ici . Il fonctionne sous node.js et attend un fichier à /usr/share/dict/words-2500. Le dictionnaire que j'utilise peut être trouvé ici . Ce n'est pas naïf - il taille au fur et à mesure, de sorte qu'il fonctionne beaucoup plus vite avec des entrées plus volumineuses.

Le dictionnaire contient une liste de 2 500 mots que j'ai trouvés sur Internet quelque part, moins certaines combinaisons de 1, 2 et 3 lettres que je considérais comme non pas des mots. Cet algorithme est sensible à la possibilité de choisir un trop grand nombre de mots courts et ralentit considérablement si vous autorisez, disons, chaque lettre en tant que mot (je vous regarde, /usr/share/dict/words).

L'algorithme finit par trier en fonction du nombre de mots, donc les "intéressants" seront, espérons-le, au sommet. Cela fonctionne très bien HELLO WORLD, en moins d’une seconde et en retournant la phrase attendue comme premier coup. De cela, j’ai aussi appris que DATA SCIENTIST(la seule autre phrase que j’ai essayée) les codes morse sont les mêmes que NEW REAL INDIA.

Edit: J'ai cherché d'autres plus intéressantes pendant quelques minutes. Les mots SPACESet SWITCHsont des morsagrammes. Jusqu'à présent, ils constituent la plus longue paire à mot unique que j'ai trouvée.

Il suffit d'observer que certaines courtes combinaisons de lettres donnent des décodages ambigus. Une seule séquence ambiguë suffit, mais je peux voir ce qui suit:

ATE ~ P
EA ~ IT
MO ~ OM

etc. Comme le note David Richerby dans les commentaires, toute lettre est équivalente à une chaîne de caractères Es et Ts, ce qui rend le code Morse ambigu en tant que moyen de coder des séquences de lettres arbitraires; les combinaisons ci-dessus montrent que cela est vrai même pour les combinaisons de lettres plausibles en anglais (par exemple, MEAT~ MITT). Un exercice de codage intéressant pourrait être de trouver toutes les chaînes de cinq lettres ou moins qui pourraient être confondues avec autre chose, en se limitant aux combinaisons de lettres pouvant être trouvées dans le texte anglais (en utilisant un ou plusieurs mots), regroupées par classe d’équivalence.

En utilisant votre exemple original, il arrive également que

HELLO WORLD ~ HAS TEAM NO MAID TOE

et si le membre de droite est peut-être irréaliste, même en tant que message partiel, il s'agit certainement d'une séquence de mots anglais, que l'on pourrait trouver en moins de 15 minutes sans assistance informatique. Cela pourrait être considéré comme une preuve que de nombreuses phrases en anglais pourraient être mal identifiées comme une séquence différente (peut-être absurde) de mots anglais.

Le code Morse est en réalité un code ternaire, pas un code binaire, les espaces sont donc nécessaires. Si les espaces n'existaient pas, il en résulterait beaucoup d'ambiguïté, non pas tant avec le message en entier, mais avec des lettres individuelles.

Par exemple, 2 points est un I, mais 3 points est un S. Si vous transcrivez et que vous entendez deux points, écrivez-vous immédiatement "I" ou attendez-vous jusqu'à ce que vous entendiez un autre point (ou tiret)?

La réponse est que chaque valeur est séparée par un espace, elles sont donc regroupées. Lorsque les opérateurs saisissent des messages en morse, ils font une pause de la même longueur qu’un tiret après chaque séquence de code lettre pour indiquer la fin de la séquence.

Même si vous écriviez un programme d'IA pour examiner une phrase complète à la fois et comprendre quelle était l'interprétation logique du message, il subsisterait de nombreuses petites ambiguïtés et fautes d'orthographe qui

quelques notes non couvertes par d’autres (bonnes) réponses, mais qui ne font généralement pas de recherche sur les connaissances antérieures et ne citent aucune substance (pour moi une partie intrinsèque de la science informatique ).

• cette théorie générale de la CS entre dans la catégorie de la segmentation du texte et aussi du "fractionnement des mots" / "la désambiguïsation" bien que la théorie soit un peu différente, sa division des séquences de symboles en mots (avec des lettres variables), etc. sont des unités. Ici, les chaînes sont divisées en lettres où les lettres ont une longueur variable, mais la théorie est analogue mais pas exactement 1-1. c'est-à-dire la correspondance entre les phrases en mots, les longueurs de mots variables, et les phrases en mots, les longueurs de mots / lettres variables.

• comme d'autres l'ont souligné, cela peut être étudié de manière empirique. et quelqu'un l'a fait d'un point de vue (il y a plusieurs façons d'étudier cela) et a "publié" les résultats sur une page Web avec un grand répertoire / tableau de résultats.

  J'ai trouvé 25 787 mots de code morse ambigus. Ceci est composé de 10 330 cordes Morse distinctes. La plus haute fréquence du mot Morse ambigu a 13 mots donneurs possibles. Les résultats sont regroupés ci-dessous dans des tableaux en fonction de la fréquence des mots partageant la même représentation morse.

• wow, "context materials" ... une question presque identique "traduire le code morse sans espaces" sur stackoverflow à partir de 3ans a actuellement 0 votes.

En général, il y a de manière exponentielle beaucoup de décodages possibles, mais si vous le voulez vraiment, vous pouvez les lister tous. Vous pouvez également les lister de manière succincte, c'est-à-dire donner une représentation succincte pour tous. Puisqu'il ne s'agit que d'un exercice de programmation, je vous mets au défi de le faire vous-même.

Cela dit, le fait qu'il y ait une ambiguïté n'exclut pas la capacité de déchiffrer le message, ou du moins une grande partie du message. En supposant un modèle probabiliste pour le texte représenté par le code Morse - pour être précis, nous pouvons supposer que c'est l'anglais et utiliser les propriétés statistiques de l'anglais - il peut être possible de décoder essentiellement le message, bien que certaines ambiguïtés locales puissent être inévitables. La raison en est que la plupart des décodages correspondent à un texte en clair sans sens. Pour ce faire, vous devez étendre l'algorithme de programmation dynamique du paragraphe précédent afin d'estimer la vraisemblance de chaque décodage, puis choisir le décodage à vraisemblance maximale. Cette approche a plus de chance de réussir à mesure que le message s'allonge.

Comment définir / reconnaître / générer le langage de tous les décodages possibles.

Clairement, sans espaces, le code morse n'est plus uniquement déchiffrable.

Il est cependant possible de donner sous une forme condensée tous les moyens possibles pour le décoder. Cela ressemble en réalité à ce qui est fait dans le traitement de la parole: à partir d’un flux unique de sons (ou de phonèmes), vous devez trouver toutes les manières dont il peut être décomposé en une séquence de mots. Les algorithmes permettant de faire cela produisent ce qu'on appelle un réseau de mots. Vous trouverez un exemple dans la section "Ambiguïté lexicale" de cette réponse .

Dans le cas du code Morse binaire (sans espaces), vous n’avez que des points et des tirets, mais le problème est le même.

La façon dont vous pouvez obtenir toutes les traductions est la suivante.

$T$

$w$$n$$W$$n+1$$0$$n$$L=\{w\}=\mathcal L(W)$$T(L)$$T(L)$

$T$$W$$T$$W$

Les détails sont facilement élaborés. Mais demandez si vous avez besoin de plus.

Un pseudo-code pour un solveur qui donnera toutes les interprétations possibles. Ceci est basé sur quelques réflexions rapides, donc des contributions supplémentaires seraient les bienvenues. Method accepte deux entrées, l'une du texte traduit jusqu'à présent et la seconde du code 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)
        }

}

Cela produira toutes les combinaisons possibles de lettres et de chiffres sans espace entre les "mots". Si vous vouliez prouver l'ambiguïté, cela le ferait certainement. Si vous souhaitez obtenir des messages significatifs, essayez de rechercher un code destiné à traduire les hashtags dans un langage lisible.

En utilisant ce qui précède, j’ai écrit un programme en C # qui fait ce qui précède. Je l'ai empêché de courir à 22 millions de possibilités pour la chaîne ci-dessus qui peut se traduire par hello world. L'équivalent en code Morse de "Bonjour" a abouti à 20 569 résultats possibles. Je n'ai pas non plus inclus les chiffres. Ce serait plus élevé si je les autorisais.