圧縮(Programmers 17684)

🧑‍💻 あっしゅく

新入社員の魚餅会社は、KakaoTalkに送信された情報を圧縮し、伝送効率を向上させる.情報を圧縮しても伝達する情報は変えられないので,圧縮前の情報の完全回復を実現するための無損圧縮アルゴリズムを決定する.

エフィッチは、複数の圧縮アルゴリズムにおいて、性能が良く、簡単なLZW(Lempel-Ziv-Welch)圧縮を実現することを決定した.LZW圧縮は1983年に発表されたアルゴリズムで、画像ファイルフォーマットGIFなど多様なアプリケーションで使用されている.

LZW圧縮は以下のプロセスを経た.
辞書は、すべての長さ1の単語

を含むように初期化される.

辞書で現在の入力と一致する最長文字列wを検索する.

wに対応する辞書のインデックス番号を出力し、入力からwを削除する.

入力に未処理の次の文字がある場合は、辞書に(c)、w+c対応の単語を登録する.

の第2段階に戻る.

圧縮アルゴリズムが英語の大文字のみを処理する場合、辞書は次のように初期化されます.辞書のインデックス番号は整数値で、1から始まるとします.

インデックス番号123...242526単語ABC...XYZ
例えば

でKAKAOを入力します.

現在辞書にはKAKAOの頭文字Kが登録されているが、KAから2番目の文字がないため、1番目の文字Kに対応するインデックス番号11が出力され、次の文字Aを含むKAが辞書の27番目となる.

の2番目のアルファベットAは辞書にありますが、3番目のアルファベットのAKは辞書にありませんので、Aのインデックス番号1を出力し、AKを辞書に28番目に登録します.

辞書には

の3文字目から始まるKAがあるので、KAに対応するインデックス番号27、29番目の登録KAOが出力され、以下の文字Oが含まれる.

は、最後に、未処理文字Oに対応するインデックス番号15を出力する.

現在の入力(w)の次の文字(c)出力辞書(w+c)KA 1127:KAAK 128:AKAO 2729:KAOO 15を追加
この過程を経て,5文字の文章KAKAOは4つのインデックス番号[11,1,27,15]に圧縮された.

入力TOBEORNOTTOBEORTEORNOTの場合、以下の圧縮が行われます.

現在入力(w)次文字(c)追加出力辞書(w+c)TO 2027:TOOB 1528:OBBE 229:BEEO 530:EOOR 530:ORRN 1832:RNNOOT 1533:OTT 2035:TTTOB 2736:TOBBEO 2937:BEOORT 3138:ORTTOBE 3639:TOBEEOR 3040:ORNO-34:OROT 34

入力フォーマット

入力として、英語の大文字のみからなる文字列msgが与えられる.msgの長さは1文字以上,1000文字以下である.

出力フォーマット

指定した文字列を圧縮したインデックス番号を配列として出力します.

I/O例

msganswerKAKAO[11, 1, 27, 15]TOBEORNOTTOBEORTOBEORNOT[20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34]ABABABABABABABAB[1, 2, 27, 29, 28, 31, 30]

🧑‍💻 解決策

キー、アルファベット順の値を持つ辞書を作成します.

で入力した文字列に移動し、buffer変数を使用して次の値を接続します.

🧑‍💻 コード#コード#

def solution(msg):
   answer = []
   dic_al = {
       'A': 1, 'B': 2, 'C': 3, 'D': 4, 'E': 5, 'F': 6,
       'G': 7, 'H': 8, 'I': 9, 'J': 10, 'K': 11, 'L': 12,
       'M': 13, 'N': 14, 'O': 15, 'P': 16, 'Q': 17, 'R': 18,
       'S': 19, 'T': 20, 'U': 21, 'V': 22, 'W': 23, 'X': 24,
       'Y': 25, 'Z': 26
   }
   dic_size = 26
   buffer = ""
   for al in msg:
       test = buffer + al
       if test in list(dic_al.keys()):
           buffer = test
       else:
           answer.append(dic_al[buffer])
           dic_size += 1
           dic_al[test] = dic_size
           buffer = al
   if buffer:
       answer.append(dic_al[buffer])

   return answer

🧑‍💻 総評

論理構想は簡単ですが、どのように書くかを考える場合は、空の文字列に追加したいと思います.

昨日の文字列問題もそうでしたが、文字列問題はほぼ似ています.

練習者