Apakah kode Morse tanpa spasi dapat diuraikan secara unik?

Apakah semua string kode Morse dapat diuraikan secara unik? Tanpa ruang,

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

bisa jadi Hello Worldtetapi mungkin huruf pertama adalah 5- pada kenyataannya tampaknya sangat tidak mungkin urutan titik dan garis sewenang-wenang harus memiliki terjemahan yang unik.

Seseorang mungkin menggunakan ketidaksetaraan Kraft tetapi itu hanya berlaku untuk kode awalan .

Kode morse dengan spasi adalah kode awalan di mana pesan selalu dapat diterjemahkan secara unik. Setelah kami menghapus spasi ini tidak lagi benar.

Jika saya benar, dan semua pesan kode Morse tidak dapat diterjemahkan secara unik, apakah ada cara untuk membuat daftar semua pesan yang mungkin? Berikut adalah beberapa latihan terkait yang saya temukan di codegolf.SE

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

Berikut ini adalah pesan yang masuk akal, tetapi memiliki arti yang sama sekali berbeda:

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

Mengutip David Richerby dari komentar:

Karena ⋅ mewakili E dan - mewakili T, pesan Morse apa pun tanpa spasi dapat diartikan sebagai string dalam $\{E,T\}^*$

Lebih lanjut, karena A, I, M, dan N diwakili oleh empat kemungkinan kombinasi dari dua karakter morse (⋅-, ⋅⋅, -, -⋅, masing-masing), pesan apa pun tanpa spasi juga dapat diartikan sebagai string dalam $\{A,I,M,N\}^*\{E,T\}?$. Perhatikan bahwa untuk setiap pesan Morse dengan panjang> 1, ini berbeda dari interpretasi David. Dengan demikian, satu-satunya pesan dengan interpretasi unik adalah yang panjangnya 1 (dan, saya kira, 0, jika itu dianggap sebagai pesan) - yaitu, ⋅, mewakili E, dan -, mewakili T.

Berikut ini beberapa JavaScript yang akan memberi tahu Anda semua kemungkinan interpretasi dari serangkaian .dan -. String dengan panjang hingga 22 berjalan di bawah satu detik, tetapi sesuatu yang lebih tinggi dari itu mulai menjadi sangat lambat - Saya tidak akan, misalnya, mencoba untuk memecahkan kode HELLO WORLD dengan itu. Anda dapat membuka konsol JavaScript di browser Anda, menempelkannya di, dan kemudian memanggil, misalnya,decode('......-...-..---') ,. (Dalam contoh ini, entri # 2446 adalah string yang dimaksud "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'
};

Kode untuk memangkasnya menjadi hanya untaian kata-kata nyata sedikit lebih lama, jadi saya taruh di sini . Ini berjalan di bawah node.js dan mengharapkan file di /usr/share/dict/words-2500. Kamus yang saya gunakan dapat ditemukan di sini . Ini tidak naif - itu memangkas saat berjalan, sehingga berjalan jauh lebih cepat pada input yang lebih besar.

Kamus ini terdiri dari daftar 2.500 kata teratas yang saya temukan di internet di suatu tempat, minus beberapa kombinasi 1-, 2-, dan 3- huruf yang saya anggap bukan kata-kata. Algoritme ini sensitif untuk memiliki terlalu banyak kata pendek untuk dipilih, dan melambat secara drastis jika Anda mengizinkan, katakanlah, setiap huruf sebagai kata (Saya melihat Anda,/usr/share/dict/words ).

Algoritma selesai dengan mengurutkan berdasarkan jumlah kata, sehingga yang "menarik" diharapkan akan berada di atas. Ini berfungsi dengan baik HELLO WORLD, berjalan di bawah satu detik dan mengembalikan frase yang diharapkan sebagai hit pertama. Dari sini saya juga belajar bahwa DATA SCIENTIST(satu-satunya frasa lain yang saya coba) kode morse sama dengan NEW REAL INDIA.

Sunting: Saya mencari yang lebih menarik selama beberapa menit. Kata-kata SPACESdan SWITCHmorsagram. Sejauh ini mereka adalah pasangan kata tunggal terpanjang yang saya temukan.

Cukuplah untuk mengamati bahwa kombinasi huruf-huruf pendek tertentu memberikan dekode yang ambigu. Sekuens ambigu tunggal sudah cukup, tapi saya bisa melihat yang berikut:

ATE ~ P
EA ~ IT
MO ~ OM

dll. Seperti yang ditulis David Richerby dalam komentar, huruf apa pun setara dengan string Es dan Ts, yang membuat Kode Morse ambigu sebagai cara penyandian urutan huruf yang sewenang-wenang; kombinasi di atas menunjukkan bahwa ini berlaku bahkan untuk kombinasi huruf yang masuk akal dalam bahasa Inggris (misalnya, MEAT~ MITT). Mungkin latihan pengkodean yang menarik adalah menemukan semua string dari lima atau lebih sedikit huruf yang dapat dikira sebagai sesuatu yang lain, membatasi kombinasi huruf yang sebenarnya dapat ditemukan dalam teks bahasa Inggris (menggunakan satu atau lebih kata), dikelompokkan berdasarkan kelas ekivalen.

Menggunakan contoh asli Anda, kebetulan juga demikian

HELLO WORLD ~ HAS TEAM NO MAID TOE

dan sementara sisi kanan mungkin tidak realistis bahkan sebagai pesan parsial, itu tentu saja urutan kata-kata bahasa Inggris, dan yang dapat ditemukan dalam waktu kurang dari 15 menit tanpa bantuan komputer. Ini dapat diambil sebagai bukti bahwa banyak frasa dalam bahasa Inggris dapat salah diartikan sebagai urutan kata-kata bahasa Inggris yang berbeda (mungkin tidak masuk akal).

Kode Morse sebenarnya adalah kode ternary, bukan kode biner, jadi spasi diperlukan. Jika ruang tidak ada, banyak ambiguitas akan dihasilkan, tidak begitu banyak dengan seluruh pesan, tetapi dengan huruf individual.

Misalnya, 2 titik adalah huruf I, tetapi 3 titik adalah huruf S. Jika Anda menyalin dan mendengar dua titik, apakah Anda segera menulis "Saya" atau Anda menunggu sampai Anda mendengar titik (atau tanda hubung) yang lain?

Jawabannya adalah bahwa setiap nilai dipisahkan oleh ruang sehingga mereka dikelompokkan bersama. Ketika operator memasukkan pesan dalam Morse, mereka membuat jeda dengan panjang yang sama dengan tanda hubung setelah setiap urutan kode huruf untuk menunjukkan akhir urutan.

Bahkan jika Anda menulis program AI untuk melihat kalimat lengkap pada suatu waktu dan mencari tahu apa interpretasi logis dari pesan tersebut, masih akan ada banyak ambiguitas dan salah eja yang akan

beberapa catatan tidak tercakup dalam jawaban (baik) lainnya tetapi yang umumnya tidak meneliti pengetahuan sebelumnya dan mengutip segala hal (bagi saya bagian intrinsik dari ilmu komputer ).

• teori umum CS ini jatuh ke dalam kategori segmentasi teks dan juga "pemisahan kata" / "disambiguasi" walaupun ada teori yang sedikit berbeda, tentang pemisahan urutan simbol menjadi kata-kata (dengan huruf variabel), dll, di mana simbol adalah unit. di sini string dibagi menjadi huruf-huruf di mana huruf memiliki panjang variabel, tetapi teorinya analog meskipun tidak persis 1-1. yaitu pemetaan antara kalimat-ke-kata, panjang-variabel-kata-huruf, dan kalimat-ke-kata, variabel-kata / panjang-huruf.

• seperti yang orang lain tunjukkan ini dapat dipelajari secara empiris. dan seseorang melakukannya dari satu sudut (ada beberapa cara untuk mempelajari ini) dan "menerbitkan" hasilnya pada halaman web dengan direktori besar / tabel hasil.

  Saya menemukan 25.787 kata kode Morse yang mendua. Ini terbuat dari 10.330 string Morse yang berbeda. Kata Morse ambigu frekuensi tertinggi memiliki 13 kata donor yang memungkinkan. Hasilnya dikelompokkan di bawah ini dalam tabel berdasarkan frekuensi kata yang memiliki representasi Morse yang sama.

• wow, "konteks penting" ... pertanyaan yang hampir identik "menerjemahkan kode morse tanpa spasi" di stackoverflow dari 3 tahun lalu saat ini memiliki 0 suara.

Secara umum ada banyak kemungkinan dekode, tetapi jika Anda benar-benar mau, Anda bisa mendaftar semuanya. Anda juga dapat membuat daftar mereka dengan cara ringkas, yaitu, memberikan representasi ringkas untuk mereka semua. Karena ini tidak lebih dari latihan pemrograman, saya menantang Anda untuk melakukannya sendiri.

Yang mengatakan, fakta bahwa ada ambiguitas tidak menghalangi kemampuan untuk menguraikan pesan, atau setidaknya sebagian besar pesan. Dengan asumsi model probabilistik untuk teks yang diwakili oleh kode Morse - untuk kepastian, kita dapat mengasumsikan bahwa itu adalah bahasa Inggris dan menggunakan sifat statistik bahasa Inggris - pada dasarnya dimungkinkan untuk memecahkan kode pesan, meskipun beberapa ambiguitas lokal mungkin tidak dapat dihindari. Alasannya adalah bahwa sebagian besar dekode sesuai dengan plainteks yang tidak masuk akal. Cara untuk melakukannya adalah memperluas algoritma pemrograman dinamis dari paragraf sebelumnya untuk memperkirakan kemungkinan setiap decoding, dan kemudian memilih decoding kemungkinan maksimum. Pendekatan ini memiliki lebih banyak peluang untuk berhasil karena pesannya semakin panjang.

Cara mendefinisikan / mengenali / menghasilkan bahasa dari semua kemungkinan dekode.

Jelas, tanpa spasi, kode morse tidak lagi dapat diuraikan secara unik.

Namun dimungkinkan untuk memberikan dalam bentuk yang kental semua cara yang mungkin untuk memecahkan kode itu. Ini sebenarnya mirip dengan apa yang dilakukan dalam pemrosesan pidato: dari aliran suara yang unik (atau dari fonem), Anda harus menemukan semua cara itu dapat diuraikan dalam urutan kata-kata. Algoritma untuk melakukan ini menghasilkan apa yang disebut kata kisi. Anda akan menemukan contoh di bagian "ambiguitas leksikal" dari jawaban ini .

Dalam kasus kode Morse biner (tanpa spasi), Anda hanya memiliki titik dan garis, tetapi masalahnya sama.

Cara Anda mendapatkan semua terjemahan adalah sebagai berikut.

$T$ yang mengenali kode Morse. Ketika suatu kode dikenali, huruf / digit yang bersangkutan adalah keluaran, dan ada (secara non deterministik) suatu transisi kosong kembali ke akar dari trie. Tetapi pada saat yang sama, kata kode dapat dilanjutkan menjadi yang lebih panjang (non-deterministik).

Lalu Anda mengambil urutan Morse Anda dari$w$$n$$W$$n+1$$0$$n$$L=\{w\}=\mathcal L(W)$$T(L)$$T(L)$

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

Detailnya mudah dikerjakan. Tetapi tanyakan apakah Anda membutuhkan lebih banyak.

Beberapa kode semu untuk pemecah yang akan memberikan semua kemungkinan interpretasi. Ini didasarkan pada beberapa pemikiran cepat, sehingga masukan tambahan akan diterima. Metode menerima dua input salah satu teks sejauh ini diterjemahkan, dan yang kedua dari kode 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)
        }

}

Ini akan menampilkan semua kombinasi huruf dan angka yang mungkin tanpa spasi antara "kata". Jika Anda ingin membuktikan ambiguitas, ini pasti akan berhasil. Jika Anda ingin mengeluarkan pesan yang berarti, cobalah mencari kode yang dimaksudkan untuk menerjemahkan tagar ke dalam bahasa yang dapat dibaca.

Dengan menggunakan di atas, saya menulis sebuah program dalam C # yang melakukan hal di atas. Saya menghentikannya dari menjalankan 22 juta kemungkinan untuk string di atas yang dapat diterjemahkan ke hello world. Kode Morse yang setara dengan "Halo" menghasilkan 20.569 hasil yang mungkin. Saya juga tidak memasukkan angka. Itu akan lebih tinggi jika saya mengizinkan mereka.