Czy kod Morse'a bez spacji jest jednoznacznie rozszyfrowywany?

Czy wszystkie ciągi kodu Morse'a są jednoznacznie rozszyfrowalne? Bez spacji

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

może być, Hello Worldale być może pierwsza litera jest 5- w rzeczywistości wydaje się bardzo mało prawdopodobne, aby dowolna sekwencja kropek i myślników miała unikalne tłumaczenie.

Można użyć nierówności Krafta, ale dotyczy to tylko kodów prefiksów .

Kod Morse'a ze spacjami jest kodem prefiksu, w którym wiadomości mogą zawsze być jednoznacznie dekodowane. Po usunięciu spacji nie jest to już prawdą.

Jeśli mam rację i nie można jednoznacznie odkodować całej wiadomości Morse'a, czy istnieje sposób na wylistowanie wszystkich możliwych wiadomości? Oto kilka powiązanych ćwiczeń, które znalazłem na codegolf.SE

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

Oba są prawdopodobne, ale mają zupełnie inne znaczenie:

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

Cytując Davida Richerby'ego z komentarzy:

$\{E,T\}^*$

$\{A,I,M,N\}^*\{E,T\}?$

Oto kilka skryptów JavaScript, które pokażą wszystkie możliwe interpretacje ciągu .i -. Ciągi o długości do 22 biegną w czasie krótszym niż sekunda, ale wszystko, co jest większe, zaczyna być dość wolne - na przykład nie próbowałbym dekodować za jego pomocą HELLO WORLD. Możesz otworzyć konsolę JavaScript w przeglądarce, wkleić to, a następnie zadzwonić na przykład decode('......-...-..---'). (W tym przykładzie pozycja # 2446 jest zamierzonym ciągiem „CZEŚĆ”).

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

Kod do przycinania tylko ciągów prawdziwych słów jest nieco dłuższy, więc umieściłem go tutaj . Działa pod node.js i oczekuje pliku o /usr/share/dict/words-2500. Słownik, którego używam, można znaleźć tutaj . Nie jest naiwny - przycina się, więc działa znacznie szybciej przy większych nakładach.

Słownik składa się z listy 2500 słów, które znalazłem gdzieś w Internecie, pomniejszonej o kombinacje 1, 2 i 3 liter, które uważałem za nie słowa. Ten algorytm jest wrażliwy na zbyt wiele krótkich słów do wyboru i drastycznie spowalnia, jeśli pozwolisz, powiedzmy, na każdą literę jako słowo (patrzę na ciebie /usr/share/dict/words).

Algorytm kończy się sortowaniem na podstawie liczby słów, więc „interesujące” będą, mam nadzieję, na górze. Działa to świetnie HELLO WORLD, działa w mniej niż sekundę i zwraca oczekiwane wyrażenie jako pierwsze trafienie. Z tego dowiedziałem się również, że DATA SCIENTIST(jedyne inne zdanie, którego próbowałem) Morse koduje to samo co NEW REAL INDIA.

Edycja: szukałem ciekawszych przez kilka minut. Słowa SPACESi SWITCHsą morsagramy. Jak dotąd są to najdłuższe pary pojedynczych słów, jakie znalazłem.

Wystarczy zauważyć, że niektóre krótkie kombinacje liter dają niejednoznaczne dekodowania. Wystarczy jedna niejednoznaczna sekwencja, ale widzę następujące:

ATE ~ P
EA ~ IT
MO ~ OM

itd. Jak zauważa David Richerby w komentarzach, każda litera jest równoważna ciągowi znaków Es i Ts, co czyni Kod Morse'a niejednoznacznym jako sposób kodowania dowolnych sekwencji liter; powyższe kombinacje pokazują, że jest to prawdą nawet w przypadku możliwych kombinacji liter w języku angielskim (na przykład MEAT~ MITT). Być może ciekawym ćwiczeniem kodowania byłoby znalezienie wszystkich ciągów pięciu lub mniej liter, które można pomylić z czymś innym, ograniczając się do kombinacji liter, które faktycznie można znaleźć w tekście angielskim (używając jednego lub więcej słów), pogrupowanych według klasy równoważności.

Na przykładzie oryginalnym tak się dzieje

HELLO WORLD ~ HAS TEAM NO MAID TOE

i chociaż prawa strona jest być może nierealna, nawet jako częściowa wiadomość, z pewnością jest to ciąg angielskich słów, który można znaleźć w mniej niż 15 minut bez pomocy komputera. Można to uznać za dowód, że wiele wyrażeń w języku angielskim można błędnie odczytać jako inną (być może bezsensowną) sekwencję angielskich słów.

Kod Morse'a jest w rzeczywistości kodem trójkowym, a nie kodem binarnym, więc spacje są konieczne. Gdyby nie było spacji, spowodowałoby to wiele niejednoznaczności, nie tyle w przypadku całej wiadomości, co pojedynczych liter.

Na przykład 2 kropki to I, ale 3 kropki to S. Jeśli transkrybujesz i usłyszysz dwie kropki, czy od razu piszesz „I”, czy czekasz, aż usłyszysz kolejną kropkę (lub myślnik)?

Odpowiedź jest taka, że ​​każda wartość jest oddzielona spacją, więc są zgrupowane razem. Kiedy operatorzy wpisują komunikaty w Morse, robią pauzę o tej samej długości co myślnik po każdej sekwencji kodu literowego, aby wskazać koniec sekwencji.

Nawet jeśli napisałeś program sztucznej inteligencji, aby spojrzeć na pełne zdanie na raz i dowiedzieć się, jaka była logiczna interpretacja wiadomości, nadal będzie wiele drobnych dwuznaczności i błędów pisowni, które mogłyby

kilka notatek nie ujętych w innych (dobrych) odpowiedziach, ale które na ogół nie badają wcześniejszej wiedzy i nie przytaczają żadnych rzeczy (dla mnie nieodłączna część informatyki ).

• ta ogólna teoria CS należy do kategorii segmentacji tekstu, a także „podziału słów” / „ujednoznacznienia”, chociaż tam teoria jest nieco inna, polega na dzieleniu sekwencji symboli na słowa (ze zmiennymi literami) itp., gdzie symbole są jednostkami. tutaj ciągi są podzielone na litery, w których litery mają zmienną długość, ale teoria jest analogiczna, chociaż nie dokładnie 1-1. tj. mapowanie między zdaniami-na-słowa, zmiennymi słowami-literami długości i zdaniami-na-słowami, zmiennymi słowami / literami.

• jak zauważyli inni, można to zbadać empirycznie. i ktoś zrobił to z jednej strony (istnieje wiele sposobów na zbadanie tego) i „opublikował” wyniki na stronie internetowej z dużym katalogiem / tabelą wyników.

  Znalazłem 25 787 niejednoznacznych słów kodu Morse'a. Składa się z 10330 różnych strun Morse'a. Niejednoznaczne słowo Morse'a o najwyższej częstotliwości ma 13 możliwych słów dawcy. Wyniki są pogrupowane poniżej w tabelach na podstawie częstotliwości słów, które mają tę samą reprezentację Morse'a.

• wow, „kontekst ma znaczenie” ... prawie identyczne pytanie „tłumaczenie kodu Morse'a bez spacji” na stackoverflow sprzed 3 lat ma obecnie 0 głosów.

Ogólnie istnieje wykładniczo wiele możliwych dekodowań, ale jeśli naprawdę chcesz, możesz wymienić je wszystkie. Możesz także wymienić je w zwięzły sposób, czyli zwięźle przedstawić je wszystkie. Ponieważ jest to nic innego jak ćwiczenie programistyczne, wzywam cię do zrobienia tego sam.

To powiedziawszy, fakt, że istnieje dwuznaczność, nie wyklucza możliwości rozszyfrowania wiadomości lub przynajmniej dużych części wiadomości. Zakładając model probabilistyczny dla tekstu reprezentowanego przez kod Morse'a - dla pewności możemy założyć, że jest on angielski i używać statystycznych właściwości języka angielskiego - możliwe jest zasadniczo dekodowanie wiadomości, chociaż pewne lokalne niejednoznaczności mogą być nieuniknione. Powodem jest to, że większość dekodowań odpowiada nie-sensownemu tekstowi jawnemu. Aby to zrobić, należy rozszerzyć algorytm programowania dynamicznego z poprzedniego akapitu, aby oszacować prawdopodobieństwo każdego dekodowania, a następnie wybrać dekodowanie maksymalnego prawdopodobieństwa. Takie podejście ma większą szansę na sukces, gdy wiadomość się wydłuża.

Jak zdefiniować / rozpoznać / wygenerować język wszystkich możliwych dekodowań.

Oczywiście, bez spacji, kod Morse'a nie jest już jednoznacznie rozszyfrowywany.

Możliwe jest jednak podanie w skondensowanej formie wszystkich możliwych sposobów jego dekodowania. Jest to w rzeczywistości podobne do tego, co dzieje się w przetwarzaniu mowy: z unikalnego strumienia dźwięków (lub fonemów) musisz znaleźć wszystkie sposoby, w jakie można je rozłożyć na sekwencję słów. Algorytmy do wykonania tej czynności tworzą tak zwane słowo kratowe. Przykład znajdziesz w części „niejednoznaczności leksykalnej” tej odpowiedzi .

W przypadku binarnego kodu Morse'a (bez spacji) masz tylko kropki i myślniki, ale problem jest taki sam.

Możesz uzyskać wszystkie tłumaczenia w następujący sposób.

$T$

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

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

Szczegóły są łatwe do ustalenia. Ale zapytaj, czy potrzebujesz więcej.

Niektóre pseudo-kod dla solwera, który da wszystkie możliwe interpretacje. Opiera się to na kilku szybkich przemyśleniach, więc mile widziane są dodatkowe informacje. Metoda przyjmuje dwa wejścia, jeden z dotychczas przetłumaczonego tekstu, a drugi kodu Morse'a.

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

}

Spowoduje to wyświetlenie wszystkich możliwych kombinacji liter i cyfr bez spacji między „słowami”. Jeśli chcesz udowodnić dwuznaczność, to na pewno by to zrobiło. Jeśli chcesz uzyskać znaczące wiadomości, spróbuj poszukać kodu służącego do tłumaczenia hashtagów na czytelny język.

Korzystając z powyższego, napisałem program w języku C #, który robi powyższe. Zatrzymałem go przed uruchomieniem 22 milionów możliwości dla powyższego ciągu, który może przełożyć się na witaj świecie. Odpowiednik „Hello” w kodzie Morse'a przyniósł 20 569 możliwych wyników. Nie podałem też liczb. Byłoby to wyższe, gdybym im pozwolił.