Является ли азбука Морзе без пробелов однозначно расшифровываемой?

54

Все ли строки азбуки Морзе однозначно расшифрованы? Без пробелов,

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

может быть, Hello Worldно, возможно, первая буква 5- на самом деле это выглядит очень маловероятным, произвольная последовательность точек и тире должна иметь уникальный перевод.

Можно использовать неравенство Крафта, но это относится только к префиксным кодам .

Код Морзе с пробелами - это префиксный код, в котором сообщения всегда могут быть уникально декодированы. Как только мы удалим пробелы, это больше не так.


В случае, если я прав, и все сообщения азбуки Морзе не могут быть однозначно декодированы, есть ли способ перечислить все возможные сообщения? Вот некоторые связанные упражнения, которые я нашел на codegolf.SE

Джон Мангуаль
источник
7
Вы, кажется, уже ответили на свой вопрос?
Рафаэль
7
«Азбука Морзе без пробелов» не является азбукой Морзе. Пробелы являются частью спецификации, потому что без них код не будет расшифрован.
Стивен Кеннеди
1
@StephenKennedy Это уже в вопросе. Вы прочитали это полностью?
Рафаэль
3
Скрипт Perl для вывода списка возможных сообщений для кода. Не осознавал, что это чисто теоретическое сообщество. :)
Squeezy
1
Вы действительно уверены, что ваш принятый ответ вообще считается ответом или даже намеком на что-либо? Я имею в виду, что очевидно, что ET = A ... что доказывает, что Спилберг был прав: ET - Чужой.
Бабу

Ответы:

91

Ниже приведены правдоподобные сообщения, но они имеют совершенно другое значение:

SOS HELP      = ...---...  .... . .-.. .--.        => ...---.........-...--.
I AM HIS DATE = ..  .- --  .... .. ...  -.. .- - . => ...---.........-...--.
celtschk
источник
6
Милый, но уже было установлено, что Морс без пробелов неоднозначен, поэтому я не думаю, что это стоит намного больше, чем комментарий.
Дэвид Ричерби
37
ОП , кажется, спрашивая , можно ли интерпретировать одну серию из точек и тире без пробелов , как два «реальных» сообщений , в отличие от произвольных последовательностей Т и Е . Первый SOS! Помогите! состоит из двух междометий, и второе « Я - его дата» - это грамматическое и разумное английское предложение, поэтому оба являются действительными сообщениями. Это дает краткий ответ на вопрос, приводя пример.
CJ Деннис
2
@ CJDennis Вопрос совсем не говорит об этом. Он спрашивает, являются ли строки Морзе однозначно дешифруемыми, и есть ли способ перечислить все строки, которые кодируют данную последовательность, если точки и тире. Это вообще ничего не говорит о том, что строки должны иметь значение на английском языке.
Дэвид Ричерби
2
Существует как конкретный (контр) пример, так и общий способ изучения проблемы, и оба они имеют отношение к хорошим ответам. см., например, доказательства / опровержения от
lakatos
3
"Что это говорит, прапорщик?" I AM HIS DATE«Итак, Амелия решила сбежать со старым Нунаном , хммм. Вероятно, нам следует оставить это при себе».
Dotancohen
36

Цитирую Дэвида Ричерби из комментариев:

Поскольку ⋅ представляет E и - представляет T, любое сообщение Морзе без пробелов можно интерпретировать как строку в{E,T}

Кроме того, поскольку A, I, M и N представлены четырьмя возможными комбинациями двух символов Морзе (⋅-, ⋅⋅, -, -⋅, соответственно), любое сообщение без пробелов также можно интерпретировать как строку в , Обратите внимание, что для любого сообщения Морзе длиной> 1 это отличается от интерпретации Дэвида. Таким образом, единственными сообщениями с уникальными интерпретациями являются сообщения длиной 1 (и, я полагаю, 0, если это считается сообщением), то есть ⋅, представляющий E, и -, представляющий T.{A,I,M,N}{E,T}?

Вот некоторый JavaScript, который расскажет вам все возможные интерпретации строки .и -. Струны длиной до 22 запускаются менее чем за секунду, но все, что выше этого, начинает работать довольно медленно - я бы, например, не пытался декодировать HELLO WORLD с его помощью. Вы можете открыть консоль JavaScript в своем браузере, вставить ее, а затем вызвать, например decode('......-...-..---'),. (В этом примере запись # 2446 является предполагаемой строкой "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'
};

Код для удаления только строк из реальных слов немного длиннее, поэтому я поместил его здесь . Он работает под node.js и ожидает файл в /usr/share/dict/words-2500. Словарь, который я использую, можно найти здесь . Это не наивно - оно сокращает, так как оно работает намного быстрее на больших входах.

Словарь состоит из списка топ-2500 слов, который я где-то нашел в Интернете, за исключением некоторых 1-, 2- и 3-буквенных комбинаций, которые я считал не словами. Этот алгоритм чувствителен к наличию слишком большого количества коротких слов для выбора и резко замедляется, если вы разрешите, скажем, каждую отдельную букву как слово (я смотрю на вас /usr/share/dict/words).

Алгоритм заканчивается сортировкой по количеству слов, поэтому «интересные», будем надеяться, будут наверху. Это прекрасно работает HELLO WORLD, работает меньше секунды и возвращает ожидаемую фразу как первый удар. Из этого я также узнал, что DATA SCIENTIST(единственная другая фраза, которую я пробовал) азбукой Морзе так же, как NEW REAL INDIA.

Изменить: я искал более интересные в течение нескольких минут. Слова SPACESи SWITCHморсаграммы. Пока что это самая длинная пара из одного слова, которую я нашел.

Аарон Дюфур
источник
3
Вы только что изобрели слово морсаграм ? Мне это очень нравится, но в веб-поиске есть одна ссылка - на этот сайт.
BmyGuest
Я также позволил себе превратить этот интересный вопрос в открытый вызов на Puzzling.SE со ссылкой на эту публикацию здесь.
BmyGuest
@BmyGuest Да, это полностью выдуманное слово. Хотя мне это нравится.
Аарон Дюфур
17

Достаточно заметить, что некоторые короткие комбинации букв дают неоднозначные расшифровки. Достаточно одной неоднозначной последовательности, но я вижу следующее:

ATE ~ P
EA ~ IT
MO ~ OM

и т.д. Как отмечает Дэвид Ричерби в комментариях, любая буква эквивалентна строке Es и Ts, что делает код Морзе неоднозначным как способ кодирования произвольных последовательностей букв; Приведенные выше комбинации показывают, что это верно даже для правдоподобных буквенных комбинаций на английском языке (например, MEAT~ MITT). Возможно, интересным упражнением в кодировании было бы найти все строки из пяти или менее букв, которые можно было бы принять за что-то другое, ограничиваясь буквенными комбинациями, которые на самом деле можно найти в английском тексте (используя одно или несколько слов), сгруппированными по классу эквивалентности.

Используя ваш оригинальный пример, также случается, что

HELLO WORLD ~ HAS TEAM NO MAID TOE

и хотя правая часть, возможно, нереалистична даже в виде частичного сообщения, это, безусловно, последовательность английских слов, которую можно найти менее чем за 15 минут без помощи компьютера. Это может быть принято как доказательство того, что многие фразы на английском языке могут быть неверно интерпретированы как другая (возможно, бессмысленная) последовательность английских слов.

Ниль де Бодрап
источник
МТ против ТМ - очень короткий пример.
Рафаэль
2
@Raphael MT == TM == O Все три имеют одинаковую последовательность. Это делает перевод очень сложным.
Red_Shadow
10

Код Морзе на самом деле является троичным кодом, а не двоичным кодом, поэтому пробелы необходимы. Если бы пробелов не было, возникла бы большая двусмысленность, не столько со всем сообщением, сколько с отдельными буквами.

Например, 2 точки - это I, а 3 точки - это S. Если вы транскрибируете и слышите две точки, вы сразу пишете «I» или ждете, пока не услышите еще одну точку (или тире)?

Ответ в том, что каждое значение разделено пробелами, поэтому они сгруппированы вместе. Когда операторы вводят сообщения Морзе, они делают паузу той же длины, что и тире после каждой последовательности буквенных кодов, чтобы указать конец последовательности.

Даже если бы вы написали программу ИИ, чтобы посмотреть на полное предложение за раз и выяснить, какова была логическая интерпретация сообщения, все равно было бы много мелких двусмысленностей и ошибок в написании

Тайлер Дурден
источник
2
Ваше последнее предложение, похоже, было усечено.
Дэвид Ричерби
2
@DavidRicherby Да, это потому, что я пытался сделать пост, используя азбуку Морзе без пробелов.
Тайлер Дерден
4

несколько заметок, не охваченных в других (хороших) ответах, но которые, как правило, не исследуют предыдущие знания и не цитируют какие-либо вещи (для меня неотъемлемая часть информатики ).

  • эта общая теория CS относится к категории сегментации текста, а также к «разделению слов» / «устранению неоднозначности», хотя теория немного отличается, она касается разделения последовательностей символов на слова (с переменными буквами) и т. д., где символы являются единицами. здесь строки разбиты на буквы, где буквы имеют переменную длину, но теория аналогична, хотя не совсем 1-1. то есть отображение между предложениями в слова, переменными словами, длинами букв и предложениями в словах, переменными словами / длинами букв.

  • как уже отмечали другие, это можно изучить эмпирически. и кто-то сделал это под одним углом (есть несколько способов изучить это) и «опубликовал» результаты на веб-странице с большим каталогом / таблицей результатов.

    Я нашел 25 787 неоднозначных азбуки Морзе. Это сделано из 10,330 различных строк Морзе. Самая неоднозначная азбука Морзе по частоте имеет 13 возможных донорских слов. Результаты сгруппированы ниже в таблицах на основе частоты слов, которые имеют одинаковое представление Морзе.

  • вау, "контекст имеет значение" ... почти идентичный вопрос "перевод кода Морзе без пробелов" в stackoverflow от 3 лет назад в настоящее время набрал 0 голосов.

ВЗН
источник
2

В общем, экспоненциально много возможных расшифровок, но если вы действительно хотите, вы можете перечислить их все. Вы также можете перечислить их кратким образом, то есть дать краткое представление для всех из них. Поскольку это не более чем упражнение по программированию, я призываю вас сделать это самостоятельно.

Тем не менее, тот факт, что существует двусмысленность, не исключает возможности расшифровки сообщения или, по крайней мере, больших частей сообщения. Предполагая вероятностную модель для текста, представленного азбукой Морзе - для определенности мы можем предположить, что это английский язык и использовать статистические свойства английского языка - возможно, будет возможно существенно декодировать сообщение, хотя некоторые локальные неоднозначности могут быть неизбежны. Причина в том, что большинство расшифровок соответствуют бессмысленному тексту. Способ сделать это - расширить алгоритм динамического программирования из предыдущего абзаца для оценки вероятности каждого декодирования, а затем выбрать декодирование с максимальной вероятностью. Этот подход имеет больше шансов на успех, поскольку сообщение становится длиннее.

Юваль Фильмус
источник
Разве алгоритм Витерби не делает что-то похожее на то, что вы описали? Количественная оценка экспоненциального роста числа декодировок, это подходящий вопрос для здесь, или cstheory.SE?
Джон Мэнгуаль
1
Правильно, идея в том, чтобы использовать динамическое программирование. Оценка экспоненциального роста, вероятно, подходит здесь лучше, чем теория.
Юваль Фильмус
на самом деле, это очень похоже на то, что делается для идентификации слов при обработке речи. В результате получается так называемая решетка слов, которая представляет собой сжатое представление всех последовательностей слов, которые могут соответствовать анализируемой звуковой последовательности.
Бабу
1

Как определить / распознать / сгенерировать язык всех возможных расшифровок.

Ясно, что без пробелов код Морзе больше не является уникально дешифруемым.

Однако в сжатой форме можно дать все возможные способы его расшифровки. На самом деле это похоже на то, что делается при обработке речи: из уникального потока звуков (или фонем) вы должны найти все способы, которыми он может быть разложен в последовательность слов. Алгоритмы для этого производят так называемую решетку слов. Вы найдете пример в разделе «лексическая неоднозначность» этого ответа .

В случае двоичного кода Морзе (без пробелов) у вас есть только точки и тире, но проблема та же.

Вы можете получить все переводы следующим образом.

T

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

TWTW

Детали легко проработаны. Но спросите, нужно ли вам больше.

Babou
источник
0

Некоторый псевдокод для решателя, который даст все возможные интерпретации. Это основано на нескольких быстрых мыслях, так что дополнительный вклад будет приветствоваться. Метод принимает два ввода: один текст переведен, а второй - азбукой Морзе.

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

}

Это выведет все возможные комбинации букв и цифр без пробелов между словами. Если бы вы хотели доказать двусмысленность, это, безусловно, сделало бы это. Если вы хотите получить несколько значимых сообщений, попробуйте поискать код, предназначенный для перевода хэштегов на читаемый язык.

Используя вышеизложенное, я написал программу на C #, которая выполняет все вышеперечисленное. Я остановил его с 22 миллионами возможностей для вышеупомянутой строки, которая может перевести в привет мир. Эквивалент азбуки Морзе, эквивалентный «Hello», дал 20 569 возможных результатов. Я также не включил номера. Это было бы выше, если бы я позволил им.

Red_Shadow
источник
Вывод такого алгоритма будет доказательством того, что любая отдельная строка является неоднозначной, но это не доказывает, что все строки являются неоднозначными.
Дэвид Ричерби
@DavidRicherby Все строки длиной> 1 неоднозначны. Это было доказано в другом месте на этой странице. Я пытался ответить на вторую часть вопроса и предоставить средства для экстраполяции всех возможных решений из строки.
Red_Shadow
Просто из любопытства, не могли бы вы поделиться своей программой на C #? Моя версия Perl предлагает 19796 возможных решений для эквивалента "HELLO". Скорее всего, я забыл вывести некоторые случаи, хотя ...
Squeezy
1
Настоящий исходный код здесь оффтоп; пожалуйста, опубликуйте его в другом месте (pastebin, Gist, ...) и только ссылку на него.
Рафаэль