14

「プログラミングの課題（プログラミングコンテストトレーニングマニュアル）」は、おそらくアルゴリズムに関する最も優れた演習の本の1つです。最初の11の演習を解決しましたが、「CryptKicker」の問題で立ち往生しています。

Crypt Kicker
テキストを暗号化する一般的ですが安全でない方法は、アルファベットの文字を並べ替えることです。言い換えると、アルファベットの各文字は、テキスト内で一貫して他の文字に置き換えられます。暗号化を元に戻せるようにするために、2つの文字が同じ文字に置き換えられることはありません。

あなたの仕事は、各行が異なる置換のセットを使用し、復号化されたテキスト内のすべての単語が既知の単語の辞書からのものであると仮定して、テキストのいくつかのエンコードされた行を復号化することです。

入力
入力は、整数nを含む行と、それに続くn個の小文字（行ごとに1つ）で構成され、アルファベット順になります。これらのn個の単語は、復号化されたテキストに表示される可能性のある単語の辞書を構成します。
辞書に続いて、数行の入力があります。各行は上記のように暗号化されます。

辞書には1,000語しかありません。16文字を超える単語はありません。暗号化された行には小文字とスペースのみが含まれ、長さは80文字を超えません。

出力
各行を復号化し、標準出力に出力します。複数の解決策がある場合は、誰でもかまいません。
解決策がない場合は、アルファベットのすべての文字をアスタリスクに置き換えてください。

サンプル入力6
と
ディック
ジェーン
パフ
スポット
ヤートル

bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd

サンプル出力
ディックとジェーンとパフとスポットとヤートル..。

この演習を解決するには、どのような戦略を取る必要がありますか？私は古典的で野蛮なバックトラックソリューションを考えていましたが、もっとインテリジェントなものが見つかるまでそれを避けようとしています。

PS：これは宿題とは関係ありません。私は自分の全体的なスキルを向上させようとしているだけです。

4

5 に答える 5

9

KeyArray は置換テーブルを保持します。

  • 空の KeyArray から開始します。これはバージョン 0 です

  • 最長の暗号化された単語と最長の辞書単語を照合し、KeyArray に追加します (最長が 2 つある場合は、いずれかを選択します)。これがバージョン 1 です。

  • 次に長い暗号化された単語のいくつかの文字を解読します。

  • 復号化された文字が、同じ長さの辞書単語の同じ位置にある文字と一致するかどうかを確認します。
  • 一致するものがない場合は、バージョン 0 に戻って別の単語を試してください。

  • 一部の文字が一致する場合は、残りの文字を KeyArray に追加します。これがバージョン 2 です。

  • 次に長い暗号化された単語のいくつかの文字を解読します。

  • 復号化された文字が辞書の単語の同じ位置にある文字と一致するかどうかを確認します。
  • 一致する単語がない場合は、バージョン 1 に戻って別の単語を試してください
  • 一部の文字が一致する場合は、残りの文字を KeyArray に追加します。これがバージョン 3 です。

すべての単語が解読されるまで繰り返します。

バージョン 0 で、最も長い単語が短い単語で部分的な復号化を作成しない場合、おそらく解決策はありません。

于 2010-02-01T09:44:02.937 に答える
3

バックトラッキングを実行する前に可能性を列挙することで、マイナーな最適化を行うことができます。Python の場合:

dictionary = ['and', 'dick', 'jane', 'puff', 'spot', 'yertle']
line = ['bjvg', 'xsb', 'hxsn', 'xsb', 'qymm', 'xsb', 'rqat', 'xsb', 'pnetfn']

# ------------------------------------

import collections

words_of_length = collections.defaultdict(list)

for word in dictionary:
  words_of_length[len(word)].append(word)

possibilities = collections.defaultdict(set)
certainities = {}

for word in line:
    length = len(word)
    for i, letter in enumerate(word):
        if len(words_of_length[length]) == 1:
            match = words_of_length[length][0]
            certainities[letter] = match[i]
        else:
            for match in words_of_length[length]:
              possibilities[letter].add(match[i])

for letter in certainities.itervalues():
    for k in possibilities:
        possibilities[k].discard(letter)

for i, j in certainities.iteritems():
    possibilities[i] = set([j])

# ------------------------------------

import pprint
pprint.pprint(dict(possibilities))

出力：

{'a': set(['c', 'f', 'o']),
 'b': set(['d']),
 'e': set(['r']),
 'f': set(['l']),
 'g': set(['f', 'k']),
 'h': set(['j', 'p', 's']),
 'j': set(['i', 'p', 'u']),
 'm': set(['c', 'f', 'k', 'o']),
 'n': set(['e']),
 'p': set(['y']),
 'q': set(['i', 'j', 'p', 's', 'u']),
 'r': set(['j', 'p', 's']),
 's': set(['n']),
 't': set(['t']),
 'v': set(['c', 'f', 'o']),
 'x': set(['a']),
 'y': set(['i', 'p', 'u'])}

単一要素の可能性がある場合は、それらを入力から除外して、アルゴリズムを再実行できます。

編集:リストの代わりに設定に切り替え、印刷コードを追加しました。

于 2010-02-01T08:41:59.647 に答える
0

もう1つの可能な最適化は、処理するのに「十分な」テキストがあり、テキストの言語を知っている場合、文字の頻度を使用できます（:を参照http://en.wikipedia.org/wiki/Letter_frequency）。もちろん、これは6/7ワードを処理する場合の非常に近似的なアプローチですが、デコードするページが数ページある場合は最速の方法になります。

編集：マックスの解決策については、文字を繰り返すなど、単語のいくつかの特徴を抽出することもできます。明らかに、辞書のパフと暗号化されたテキストのqymmは、二重文字で終わる4文字の単語だけであることに注意すると、3文字の正解が得られます。より複雑なシナリオでは、各文字のカップルの可能性を絞り込むことができるはずです。

于 2010-02-01T09:50:29.353 に答える