« | »

2008.11.06

Attacking Decipherment Problems Optimally with Low-Order N-gram Models

Sujith Ravi; Kevin Knight. Attacking Decipherment Problems Optimally with Low-Order N-gram Models.

文字列置換による暗号化は,平文が”decade”のときに,{(d→Q), (e→W), (c→B), (a→S)}という文字置換操作を行い,”QWBSQW”という暗号文を得るという操作である.本研究は,”QWBSQW”のような暗号文を受け取ったときに,その平文を解読する方法として,低次なn-gram言語モデルと,整数計画法を用いる手法を提案している.

整数計画法による定式化は,bi-gram言語モデルで近似された平文Mの生成確率 P(M) を目的関数とし,変数として,平文のi番目の文字がpで,(i+1)番目の文字がrかどうかを表現する0–1変数 link_{ipr},平文の文字pを暗号文の文字qへ置換するかどうかを表す0-1変数 key_{pq} を決定する.整数計画法の制約条件として,「平文と暗号文の文字の間に一対一の対応が取れていること」「あるノードの左側のエッジと右側のエッジの数が同じであること(平文のbi-gramをエッジとして一つのパスができることを保証する)」「エッジ変数群 link_{ipr} が,置換変数群 key_{pq} と矛盾しないこと」を導入している.

本論文では引用されていないが,CRFで確率を最大にするラベルシーケンス(argmax)を求める際,「それぞれのラベルはシーケンスの中に一回しか出現してはいけない」など,マルコフ性に反する制約を導入したいとき,整数計画法でargmaxを求める方法が提案されている(Roth and Yih. Integer linear programming inference for conditional random fields. ICML, 2005).本研究は,これと類似のアイディアで,文字の置換を表す変数とその制約を追加した手法と捉えることができる.

Trackback URL

Comment & Trackback

PHPで2つの文章の類似度を計算する…

PHPを使い、異なる2つの文章の類似度を計算するプログラムを紹介する。ブログなどで記事の転用判定に利用できるだろう。…

Comment feed

Comment





XHTML: You can use these tags:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>