5

文字間のスペースを失ったモールス信号がいくつかあります。私の課題は、メッセージが何を言っているかを見つけることです。これまでのところ、組み合わせが非常に多いため、ちょっと迷っています。

ここに私が持っているメッセージに関するすべての情報があります。

  • 出力は英語になります
  • 意味のある翻訳が必ずある
  • ここにメッセージの例があります-..-...-...-...-..-.-.-.-.-..-.-.-.-.-.-.-.-.-.-..-...-.
  • メッセージは 70 文字以下にする必要があります
  • モールス信号はより長いストリームから取得されたため、最初または最後のグループが切り取られ、有効な翻訳がない可能性があります

誰かが賢い解決策を持っていますか?

4

3 に答える 3

8

これは簡単な問題ではありません。なぜなら、ruakh が示唆したように、与えられたメッセージには実行可能な文がたくさんあるからです。たとえば、「JACK AND JILL WENT UP THE 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))))
于 2011-12-04T13:07:18.050 に答える
0

これまでの単語のリスト S、これまでの現在の単語 W、現在の記号 C の 3 つを維持します。

  • S は良い言葉だけにする必要があります。「ザ・クイック」
  • W は、単語の有効なプレフィックスである必要があります。[「ブロ」]
  • C は、文字の有効な接頭辞である必要があります。'.-'

ここで、新しいシンボルを指定して、たとえば「-」としましょう。これで C を拡張します (この場合は「.--」が得られます)。C が完全な文字 (この場合は文字 'W') である場合、それを W に追加するか、さらに記号を追加して文字をさらに拡張し続けるかを選択できます。W を拡張する場合、それを S に追加する (有効な単語の場合) か、さらに拡張し続けるかを選択できます。

これは検索ですが、ほとんどのパスはすぐに終了します (W が任意の単語の有効な接頭辞でない場合は停止でき、C が文字の接頭辞でない場合は停止できます)。

より効率的にするには、動的プログラミングを使用して冗長な作業を回避し、試行を使用してプレフィックスを効率的にテストできます。

コードはどのように見えるでしょうか? 文字列が英単語であるかどうかをテストする「is_word」関数と、文字列が有効な単語の先頭であるかどうかをテストする「is_word_prefix」関数を省略すると、次のようになります。

morse = {
    '.-': 'A',
    '-...': 'B',
    etc.
}

def is_morse_prefix(C):
    return any(k.startswith(C) for k in morse)

def break_words(input, S, W, C):
    while True:
        if not input:
            if W == C == '':
                yield S
            return
        i, input = input[0], input[1:]
        C += i
        if not is_morse_prefix(C):
            return
        ch = morse.get(C, None)
        if ch is None or not is_word_prefix(W + ch):
            continue
        for result in break_words(input, S, W + ch, ''):
            yield result
        if is_word(W + ch):
            for result in break_words(input, S + ' ' + W + ch, '', ''):
                yield result

for S in break_words('....--', [], '', ''):
    print S
于 2011-12-01T23:16:24.813 に答える
0

これが「賢い」かどうかはわかりませんが、幅優先検索を試してみます (BRPocock の正規表現のアイデアに暗示されている深さ優先検索とは対照的です)。文字列が次のようになっているとします。

.---.--.-.-.-.--.-...---...-...-..
J   A C   K  A N D  J   I L   L

状態から始めます('', 0)(''はこれまでにデコードしたものです。0モールス符号文字列での位置です)。0 の位置から開始して、可能な最初の文字は. E.- A.-- W.--- Jおよび.---- 1です。したがって、 states ('E', 1)('A', 2)('W', 3)('J', 4)、および('1', 5)をキューにプッシュします。state をキューから取り出した後('E', 1)、state ('ET', 2)('EM', 3)、およびをキューに入れます('EO', 4)

ここで、可能な状態のキューが非常に急速に大きくなります — { ., -} は両方とも文字であり、{ , , } のすべてと { .., .-, , , , }のすべてがそうであるため、各パスで状態の数を渡します少なくとも3倍に増加するため、ユーザーからのフィードバックを受け取る仕組みが必要です。特に、ユーザーに「この文字列が で始まるのはもっともらしいですか?」と尋ねる何らかの方法が必要です。ユーザーが「いいえ」と言った場合は、状態を破棄する必要があります。-.--.....-.-..---..-.---.---EOS3AIOSF("EOS3AIOSF", 26)あなたのキューから。理想的なのは、ユーザーに現在のすべての状態をときどき表示する GUI を提示し、続行する価値のある状態を選択できるようにすることです。(もちろん、「ユーザー」もあなたのことです。英語には代名詞が不足しています。「あなた」がプログラムを指す場合、どの代名詞がユーザー プログラマーを指すのでしょうか?!)

于 2011-12-01T23:00:29.917 に答える