3

文字列を暗号化する特定の方法があるとしましょう。

  • 文字列の最後に、アルファベットの最初の文字である文字$を追加します。
  • 最初の文字を文字列の最後に連続的に移動して、取得したすべての文字列を形成します。
  • 取得したすべての文字列をアルファベット順に並べ替えます。
  • 各文字列の最後の文字を追加して、新しい文字列を作成します。

たとえば、FRUITという単語は次のように暗号化されます。

We append the character $ at the end of the word:
FRUIT$

We then form all the strings by moving the first character at the end:
FRUIT$
RUIT$S
UIT$FR
IT$FRU
T$FRUI
$FRUIT

Then we sort the new strings into alphabetical order:
$FRUIT
FRUIT$
IT$FRU
RUIT$F
T$FRUI
UIT$FR

The encrypted string:
T$UFIR

今私の問題は明らかです：与えられた文字列を元の形式に復号化する方法。

半週間頭をドキドキさせていて、ようやく紙切れになりました。

どうすればこれを続けることができますか？

私が発見したこと：

暗号化の最後のステップがある場合：

$FRUIT
FRUIT$
IT$FRU
RUIT$F
T$FRUI
UIT$FR

右端の列は暗号化された文字列自体であり、左端の列は常にアルファベット順になっているため、元の文字列の最初と最後の文字を知ることができます。$は常にアルファベットの最初であり、文字列に1回しか存在しないため、最後の文字は暗号化された文字列の最初の文字です。次に、右端の列から$文字を見つけ、左端の列の同じ行でその文字を検索すると、最初の文字が取得されます。

したがって、暗号化された文字列T $ UFIRについて知ることができるのは、元の文字列がF *** T $であるということです。ここで、*は不明な文字です。

これで私の考えは終わりです。今、私はワールドワイドウェブを利用して、別の人間に尋ねなければなりません：どうやって？

これは宿題だと言えます。私の家庭教師に精通しているので、これが動的計画法の問題であることに賭けます。

4

1 に答える 1

15

これが Burrows-Wheeler 変換です。

これは、一般的な繰り返しフレーズをグループ化する傾向があり、元に戻すことができるため、通常、圧縮アルゴリズムを支援するために使用されるアルゴリズムです。

文字列をデコードするには:

各文字に番号を付ける:

T$UFIR
012345

番号を付けたまま並べ替えます。文字が繰り返される場合は、繰り返される文字のインデックスが昇順で保持されるようにインデックスをセカンダリ ソート キーとして使用するか、そうでなければこれを保証するソート アルゴリズムを使用します。

$FIRTU
134502

これでデコードできます。'$' から開始し、関連付けられたインデックスを次の出力文字として使用します ('$' = 1 の場合、次の文字は 'F' です。'F' は 3 の場合、次の文字は 'R' などです)。 ...)

結果：

$FRUIT

マーカー文字を削除するだけで完了です。

于 2013-01-14T22:01:47.963 に答える