Czy kod Morse'a bez spacji jest jednoznacznie rozszyfrowywany?

54

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

John Mangual
źródło
7
Wygląda na to, że już odpowiedziałeś na swoje pytanie?
Raphael
7
„Kod Morse'a bez spacji” nie jest kodem Morse'a. Spacje są częścią specyfikacji, ponieważ bez nich kodu nie można odczytać.
Stephen Kennedy,
1
@StephenKennedy To już pytanie. Czy przeczytałeś to całkowicie?
Raphael
3
Skrypt Perla do listy możliwych komunikatów dla kodu. Nie zdawałem sobie sprawy, że to czysto teoretyczna społeczność. :)
Squeezy
1
Czy naprawdę jesteś pewien, że zaakceptowana odpowiedź w ogóle kwalifikuje się jako odpowiedź, a nawet jako wskazówka do czegokolwiek? Mam na myśli, że jest oczywiste, że ET = A ... co dowodzi, że Spielberg miał rację: ET jest kosmitą.
babou

Odpowiedzi:

91

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

SOS HELP      = ...---...  .... . .-.. .--.        => ...---.........-...--.
I AM HIS DATE = ..  .- --  .... .. ...  -.. .- - . => ...---.........-...--.
celtschk
źródło
6
Urocze, ale już ustalono, że Morse bez spacji jest niejednoznaczny, więc nie sądzę, aby było to warte dużo więcej niż komentarza.
David Richerby,
37
PO wydaje się być pytanie, czy jedna seria kropek i kresek bez spacji może być interpretowany jako dwa „prawdziwych” wiadomości w przeciwieństwie do dowolnych sekwencji T i E . Pierwsze SOS! Wsparcie! składa się z dwóch wtrąceń, a druga jestem jego randką jest gramatycznym i rozsądnym zdaniem w języku angielskim, więc oba są ważnymi wiadomościami. To odpowiada zwięźle na pytanie, podając przykład.
CJ Dennis,
2
@CJDennis Pytanie wcale tego nie mówi. Pyta, czy łańcuchy Morse'a są jednoznacznie rozszyfrowalne i czy istnieje sposób wyszczególnienia wszystkich łańcuchów kodujących daną sekwencję, jeśli kropki i myślniki. Nic nie mówi o ciągach, które muszą mieć znaczenie po angielsku.
David Richerby,
2
istnieje zarówno konkretny (przeciwny) przykład, jak i ogólny sposób badania problemu i oba są istotne dla dobrych odpowiedzi. patrz np. dowody / odrzucenia przez lakatos
dniu
3
„Co to znaczy, chorąży?” I AM HIS DATE„Więc Amelia postanowiła uciekać się do starego Noonana , hmmm. Prawdopodobnie powinniśmy to zachować dla siebie.”
dotancohen,
36

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.

Aaron Dufour
źródło
3
Czy właśnie wymyśliłeś słowo morsagram ? Bardzo mi się podoba, ale wyszukiwarka internetowa podała pojedynczy link - do tej strony.
BmyGuest,
Pozwoliłem sobie również przekształcić to interesujące pytanie w otwarte wyzwanie na Puzzling.SE z pewnym odniesieniem do tego postu tutaj.
BmyGuest,
@BmyGuest Tak, to całkowicie wymyślone słowo. Ale trochę mi się podoba.
Aaron Dufour,
17

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.

Niel de Beaudrap
źródło
MT vs TM to bardzo krótki przykład.
Raphael
2
@Raphael MT == TM == O Wszystkie trzy są tej samej sekwencji. To bardzo utrudnia tłumaczenie.
Red_Shadow
10

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

Tyler Durden
źródło
2
Twoje ostatnie zdanie wydaje się być obcięte.
David Richerby,
2
@DavidRicherby Tak, to dlatego, że próbowałem napisać pocztę przy użyciu kodu Morse'a bez spacji.
Tyler Durden,
4

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.

vzn
źródło
2

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.

Yuval Filmus
źródło
Czy algorytm Viterbi nie robi czegoś podobnego do tego, co opisałeś? Czy jest to właściwe pytanie tutaj, czy cstheory.SE? Wyliczenie wykładniczego wzrostu liczby dekodowań.
John Mangual
1
Zgadza się, pomysł polega na zastosowaniu programowania dynamicznego. Oszacowanie wykładniczego wzrostu prawdopodobnie pasuje tutaj lepiej niż cstheory.
Yuval Filmus,
w rzeczywistości jest to bardzo podobne do tego, co robi się w celu identyfikacji słów w przetwarzaniu mowy. Rezultatem jest tak zwane słowo kratowe, czyli skondensowana reprezentacja wszystkich sekwencji słów, które mogłyby pasować do analizowanej sekwencji dźwiękowej.
babou
1

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

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

TWTW

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

Babou
źródło
0

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ł.

Red_Shadow
źródło
Wynik takiego algorytmu byłby dowodem na to, że każdy pojedynczy łańcuch jest niejednoznaczny, ale nie dowodziłby, że wszystkie łańcuchy są niejednoznaczne.
David Richerby,
@DavidRicherby Wszystkie ciągi długości> 1 są niejednoznaczne. Udowodniono to gdzie indziej na tej stronie. Próbowałem odpowiedzieć na drugą część pytania i zapewnić sposób na ekstrapolację wszystkich możliwych rozwiązań z ciągu.
Red_Shadow
Czy z ciekawości podzieliłbyś się swoim programem C #? Moja wersja Perla zawiera 19796 możliwych rozwiązań dla odpowiednika „HELLO”. Najprawdopodobniej zapomniałem jednak
wydać
1
Prawdziwy kod źródłowy jest tutaj offtopic; opublikuj go w innym miejscu (pastebin, Gist, ...) i tylko link do niego.
Raphael