puzzle - 不带空格地翻译摩尔斯电码

Question

我有些摩尔斯电码丢失了字母之间的空格，我的挑战是找出消息中所说的内容。到目前为止，由于可能存在大量的组合，我有点迷失了。

这是关于我收到的消息的所有信息。

输出将为英语

总是会有有意义的翻译

这是示例消息-..-...-...-...-..-.-.-.-.-..-.-.-.-.-.-.-.-.-.-..-...-.

消息不应超过70个字符

莫尔斯电码是从较长的流中提取的，因此有可能第一个或最后一组被切除，因此没有有效的翻译

有没有人有一个聪明的解决方案？

Answer 1

这不是一个容易的问题，因为如ruakh所建议的，给定消息有很多可行的句子。例如，“JACK AND JILL WENT UP HILL”具有与“JACK AND JILL WALK CHISELED”相同的编码。由于这些都是语法句子，并且每个句子中的单词都很常见，因此在不深入研究自然语言的情况下，如何挑选一个或另一个(或其他40141055989476564163599个具有相同编码格式的英语单词序列中的任何一个)尚不明确加工。

无论如何，这是一个动态编程解决方案，用于解决查找最短句子(如果有平局，字符最少)的问题。它还可以计算与给定消息具有相同编码的句子总数。它需要一个英语单词词典在一个文件中。

接下来的增强应该是更好地衡量句子的可能性:单词频率，莫尔斯电码中的假阳性率(例如，“I”是一个常用词，但通常作为莫尔斯电码序列的其他序列的一部分出现) 。棘手的部分将是制定一个好的得分函数，该函数可以通过使用动态编程来计算的方式来表示。

MORSE = dict(zip('ABCDEFGHIJKLMNOPQRSTUVWXYZ', [
    '.-', '-...', '-.-.', '-..', '.', '..-.', '--.', '....',
    '..', '.---', '-.-', '.-..', '--', '-.', '---', '.--.',
    '--.-', '.-.', '...', '-', '..-', '...-', '.--', '-..-',
    '-.--', '--..'
]))

# Read a file containing A-Z only English words, one per line.
WORDS = set(word.strip().upper() for word in open('dict.en').readlines())
# A set of all possible prefixes of English words.
PREFIXES = set(word[:j+1] for word in WORDS for j in xrange(len(word)))

def translate(msg, c_sep=' ', w_sep=' / '):
    """Turn a message (all-caps space-separated words) into morse code."""
    return w_sep.join(c_sep.join(MORSE[c] for c in word)
                      for word in msg.split(' '))

def encode(msg):
    """Turn a message into timing-less morse code."""
    return translate(msg, '', '')

def c_trans(morse):
    """Construct a map of char transitions.

    The return value is a dict, mapping indexes into the morse code stream
    to a dict of possible characters at that location to where they would go
    in the stream. Transitions that lead to dead-ends are omitted.
    """
    result = [{} for i in xrange(len(morse))]
    for i_ in xrange(len(morse)):
        i = len(morse) - i_ - 1
        for c, m in MORSE.iteritems():
            if i + len(m) < len(morse) and not result[i + len(m)]:
                continue
            if morse[i:i+len(m)] != m: continue
            result[i][c] = i + len(m)
    return result

def find_words(ctr, i, prefix=''):
    """Find all legal words starting from position i.

    We generate all possible words starting from position i in the
    morse code stream, assuming we already have the given prefix.
    ctr is a char transition dict, as produced by c_trans.
    """
    if prefix in WORDS:
        yield prefix, i
    if i == len(ctr): return
    for c, j in ctr[i].iteritems():
        if prefix + c in PREFIXES:
            for w, j2 in find_words(ctr, j, prefix + c):
                yield w, j2

def w_trans(ctr):
    """Like c_trans, but produce a word transition map."""
    result = [{} for i in xrange(len(ctr))]
    for i_ in xrange(len(ctr)):
        i = len(ctr) - i_ - 1
        for w, j in find_words(ctr, i):
            if j < len(result) and not result[j]:
                continue
            result[i][w] = j
    return result

def shortest_sentence(wt):
    """Given a word transition map, find the shortest possible sentence.

    We find the sentence that uses the entire morse code stream, and has
    the fewest number of words. If there are multiple sentences that
    satisfy this, we return the one that uses the smallest number of
    characters.
    """
    result = [-1 for _ in xrange(len(wt))] + [0]
    words = [None] * len(wt)
    for i_ in xrange(len(wt)):
        i = len(wt) - i_ - 1
        for w, j in wt[i].iteritems():
            if result[j] == -1: continue
            if result[i] == -1 or result[j] + 1 + len(w) / 30.0 < result[i]:
                result[i] = result[j] + 1 + len(w) / 30.0
                words[i] = w
    i = 0
    result = []
    while i < len(wt):
        result.append(words[i])
        i = wt[i][words[i]]
    return result

def sentence_count(wt):
    result = [0] * len(wt) + [1]
    for i_ in xrange(len(wt)):
        i = len(wt) - i_ - 1
        for j in wt[i].itervalues():
            result[i] += result[j]
    return result[0]

msg = 'JACK AND JILL WENT UP THE HILL'
print sentence_count(w_trans(c_trans(encode(msg))))
print shortest_sentence(w_trans(c_trans(encode(msg))))