Marathon Match 72

TopCoder マラソンマッチ

(2011年7月22日の記事を移行したものです。)

結果

7位/44 Rating 1694→1783
裏マッチだったので、強いのはcolunさんだけなのに、7位。結果のわりには、レートは上がったのは、たまたま自分より上の順位の人が新規の方ばかりだったから。結果を反省せねばなりません…。

問題

平文を圧縮してください。平文の文字列長は500ぐらい～100000。圧縮後の文字列の長さ（辞書みたいなかんじ）も決められてます。例えば、以下のようなかんじに圧縮してください。

S[1] = bpa4h2edn2b3k2d3z2e43b
S[2] = 3i3ufx4uku34gzfob4vlozd3m
S[3] = juquvqvrudlpqezzzchprdwi
S[4] = kozid3pvevaytgjxdmjpfbsfhxrtovqp

暗号の解凍アルゴリズムは決まってます。数字の部分xは、番号のS[x]の文字列に置き換えられます。解凍後の文字列が、元の文字列と同じであればあるほど高得点。その他、もとの平文はランダムで文字が置き換わる確率はテストケースで大きく異なります。
すごくざっくり言うと、「覚えられる単語数が極端に少ない辞書式圧縮で、劣化をできるだけ抑えよ」という問題です。

反省点

放送中に、chokudaiさん、yowaさんから頂いたアドバイスなどを元に反省。

  • 日記を書きながらやろう
    • 自分の考えが整理できます。
    • 最初のほうに思いついたアイディアを後で使いたくなったときにも使えます。
    • あとで日記を思い出しながら書く時間もはぶける（時間たってからの復習は、ものすごく時間がかかる）
  • 幅優先探索のメリット
    • 今回の問題は、深さ優先探索よりも幅優先探索のほうが有利。この問題では、「最初の単語を当てはめを間違うと、そのあとは全然ダメである。さっさと打ち切りたい。」　これに深さ優先探索を使ってしまうと、最初の単語の当てはめ方が良かったのかイマイチだったのかが分からないまま、どんどん深い方へ探索してします。幅優先探索であれば、他の候補と相対的に良い悪いを比較できます。最初の単語の当てはめ方が一番良かったものに、より多くの探索時間をかけるといったことも可能です。
  • 問題をよくよめ
    • 時間制限は毎回違います。今回は10秒と誤解してしまいましたが、本当は30秒でした。よく読みましょう。
    • 今回は数字の使われ方を理解してませんでした（必ず1種類につき1個～4個使われる）。普通のAlgorithmマッチでは、細かい条件も使える場合がとても多いので、よく読みましょう。
  • Marathonスコアが低い場合は、いいアイディアが思いついていないのではなく、基本的なアイディアに気づいていないだけ。
    • 一見いいアイディアがでてないようにみえますが、結果をみてみると大抵の人が思いつきそうなものをボロボロと落としていました。今回の問題もビューワを書いたほうがよかったかもしれません。
  • きめ細かくやる
    • 神頼みフェーズ手抜きすぎました。裏マッチでも意外とちゃんとやっている人が多かったです。特に相対スコアルールのとき、こういうところで点を落としやすいので気をつけましょう。

方針

  1. ボトムアップで、短い単語から、平文から数字に置き換えていく。
  2. トップダウンで、長い単語から、平文から数字に置き換えていく。（最終的に企画倒れ）
  3. 神頼みフェーズ（一番使われているのが多い文字で埋める）

ボトムアップで、短い単語から、平文から数字に置き換えていく。

  • S[x]の同じ長さの部分文字列の中で、たくさんでてくる「似たような」文字列を探す。探し方は以下の通り。
    • （このやり方より、「一番短い部分文字列は、必ず最初の32文字以内に現れる」の法則を使ったほうが、確実かつ高速だったと思います。全く気づけませんでした。ビューワ作ってれば気づいてたかも…）

例えば、"ABCDEFABXDE"の中にある似たような部分文字列（長さ5）を知りたいとき
(1)連続する2文字のハッシュ値の登場回数をカウント
map[連続する2文字のハッシュ]++
AB 2点
BC 1点
CD 1点
DE 2点
EF 1点
FA 1点
BX 1点
XD 1点
(2)連続する文字列長xの間で、連続する2文字のハッシュが合計何回でてくるかカウント（合計はしゃくとり法で求めました）
ABCDE 2+1+1+2=6点
BCDEF 1+1+2+1=5点
CDEFA 1+2+1+1=5点
DEFAB 2+1+1+1=5点
EFABX 1+1+1+1=5点
FABXD 1+1+1+1=5点
ABXDE 1+1+1+1=5点
(3)最高得点のやつが、もっともよく出てくる似た文字列。（ただこの得点のつけ方だと長い文字列が必ず有利になるので、得点のつけ方は、若干調整してます。）
この場合、ABCDEが6点で最高。

  • これを深さ優先探索（←全然ダメ）でやりました。枝の数は、Sの数に応じて、調整しました。

トップダウンで、長い単語から、平文から数字に置き換えていく。（最終的に企画倒れ）

今回、問題が途中で変更になり、error値が大幅に大きくなりました。そこで、平文がerrorによりぐちゃぐちゃになっても、まだ残っている情報ってなんだろう？「実は長い平文のほうが、残っている情報が多いから、復元のチャンスがあるのでは？」と思い、やってみたのですが…

  • まず、同じ文字の間隔が多いところを探す

同じ文字の間隔を使えないか？

ABCDEFABXDE

A-A 文字の間隔 4
B-B 文字の間隔 4
D-D 文字の間隔 4
E-E 文字の間隔 4

よく出てくる単語は、同じ間隔がでてくる回数も多くなります。文字間隔が小さいと（特に26以下）役に立たないけど（鳩の巣原理）、文字間隔が大きいときは、実際の文字間隔だけが突出した値になります。平文が長ければ多ければ、誤差が大きくても正しい単語間隔が見つかりました。

  • 文字間隔から、実際の単語S[]の位置を探す

文字間隔dが既知となりました。文字間隔をdとしたとき、位置aと位置a+dが同じ文字になる場所を羅列します。横軸を単に順番のID（aの小さい順）、縦軸をaとしたとき、以下のようなグラフになります。

（エクセルシートのA列が、縦軸のaです）
このグラフを見ると傾きが平らな部分と、急でガタガタな部分にはっきりと分かれます。この平らな部分が実際単語がある部分、急な部分はたまたま同じ文字が現れた部分になります。というわけで、急な部文と平らな部分の境界が単語のスタート位置になるのが分かりますが、ここで問題がありました。

  • 単語の位置は少しでもずれて置き換えてしまうと、その後の結果がひどいことになる。
  • 意外と平らな部分とガタガタな部分の境界を正しく求めるのが難しい（１階微分・２階微分いろいろ試しました。）

というわけでトップダウンの方法は諦めました。ただ、この平らな部分の傾きからerrorを求めることができるので、それは副産物として使用しました。

個人用メモ

■ファーストインプレッションとその結果

    • 基本的には、dataの生成方法をヒントにすると、かなり簡単にできるかもしれない。
      • （結果）その通りだが、生成方法をちゃんと理解してなかった。
    • 見本のなかのerrorは予想できるのでは？
      • （結果）できた。そこそこ役にたった。
    • 必ずしも、見本どおりの圧縮をする必要はない。再現が高いほうが重要。
      • （結果）神頼みフェーズで使ったが、甘かった…
    • 必ずしも、圧縮文字列をすべて使う必要はない。短くてもOK
      • （結果）ぴったりじゃないと大体ダメなので…
    • トップダウン/ボトムアップ/両側探索それぞれメリットありそう。ケースによってかえれるので、１つにこだわる必要はない。
      • （結果）結局ボトムアップと神頼みだけになった。
    • トップダウンのときは、文字列の長さの予想が難しい
      • （結果）いろいろ試したが断念
    • いろんな区間長で調べる必要があるかも。
      • （結果）？？？。何ですか？？
    • エラーの予想は、ボトムアップの１段階目でできないか？
      • （結果）できた。これでもまぁまぁの結果だった。
    • 答えSの読みこみ、Sの登場文字列数との比較はすごい重要な気がする。
      • （結果）やった。問題のinputでない値も、結果の比較用に積極的に使おう。


■キーワード（調べ物するとき用）
似た文字列は似たハッシュ値になってれば分類できる？

    • 近似近傍点探索手法 Locality Sensitive Hashing(LSH)
    • k近傍法
    • kd木
    • Metric tree
    • ハッシュ
    • continuos
    • Locality sensitive hashing (LSH)
    • 類似文字列検索アルゴリズム
    • Divide Skip
    • ハミング距離
    • 宇野毅明