« ノイズでGo! | メイン | ODROIDにオドロイド »

アルファベット26文字で文を作る

Blogmag , 近代プログラマの夕4

Posted at 2010/01/10 14:32:16 by hortense

 パングラム(pangram)の話。
 昨日の日記で、むかしの原稿をスキャンしてあげました(「twitterはコミュニケーション革命なんかじゃない」の補足っぽい話)。ところが、いまどきのOCRソフトで読んでみたらなんともきれいにテキストデータになっている。とういことで、以下、掲載しなおしますね。

 ちなみに、さっき文字直ししながら読み直してみたんだけど、私の頭は、もっぱらパングラムのほうにいっている(編集長になって2年目でいちばん忙しい時期のはずだが)。遺伝的アルゴリズムについては、それのために、ちょちょいとかじって遊びでプログラムを書いてみたら偶然動いたというような感じなんですけどね。しかも、あまり詳細については触れていない(ちゃんと遺伝的アルゴリズムをやりたい人は、最新の情報をフォローしてみることをお勧めします)。

※『月刊アスキー』1992年7月号(ASCII Vol.16 #7 July 1992)より。「,.」を「。、」に変更。ネット向けに段落あけるなどしましたが、本文は、基本的に掲載時のままです。

------------------------------------------------------
■ことば遊び・コンピュータ

(9)パングラム2

コンピュータによるパングラム(アルファベットのA~Zをすべて使った文)の作成を試みる。前号では、コンピュータを使っアナグラムやパングラムの例を、いろいろと探しまわってみた。今回は、筆者が試みたコンピュータ・パングラムのアブローチと結果を紹介する。また、遺伝的アルゴリズムを参考にしたプグラムでもバングラムを試みてみる。

26文字の完全パングラム


 アナグラムやパングラムの話でかならず名前が登場するのが、ギリスの数学者オーガスタス・ド・モルガンである。前回紹介した「英語ことば遊び事典』(“The Oxford Guide to Word”)の日本語訳、大修館書店刊)にもこの人のパングラムが登場する。

I, quartz pyx, who fling muck beds.
(石英の聖体容器なるわが身より、この肥やしを投げつける)

 同書では触れていないが、正確には、同僚との合作らしいこのパングラム、よく見ると、jの代わりにiを、vの代わりにuを使っている。つまり、26文字のパングラムといっても、アルファベット26字すべてを1回だけ使った完全パングラムではなくて、iとuが2回使われていて、jとvは使われていない。

 これじや、パングラムとしては不完全ではないかという人もいるかもしれないが、長いアナグラムの歴史の中では、アルファベットの中では比較的新しいjはiで、vはuで表現することが許されるルールもあるのだという。

 文の意味のほうだが、あまりにも難解で、相当なイマジネーションを要求されるものになっている。「石芙の聖体容器なる……」という日本語訳も、かなり苦労しているのではなかろうか? このパングラムは、『ことば遊びコレクション』(織田正吉著、講談社刊)でも紹介されている。これの弁解のためではないと思うが、「私の知る限りでは、一般に通用しない言葉や固有名詞を使わずに、アルファベット全部を使い、意味の通る文章を作るのに成功したものは、まだいない」と、ド・モルガンは述べているそうだ。

 これは19世紀の数学者の話だが、今でもあまり事情が変わっていないことを、前回のこのページを読まれた方ならご理解いただけるだろう。26文字やそこらで作られるパングラムが、なんらかの風景なり事情を表現しているように見えるだけで、大変なものなのである。一般に知られているパングラムの多くは、10以上の文字の重複があって、全体の長さが35~40文字以上のものばかりだ。

 そのような中でも完全パングラム (アルファベット26文字を1回ずつ使った文)として、かなりの出来であるとド・モルガンが認めているのが、アメリカのドミトリ・ボーグマンによる次のような作品だという。

Cwm, fjord-bank glyphs vext quiz.
Zing! Vext cwm fly jabs kurd qoph.

 最初の作品は、『英語ことば遊び事典』でも紹介されていて「渓
谷のフィヨルドの片側に刻まれた古代の碑文は変わり者を悩ませる」と訳されている。2つ目は、前回紹介した「渓谷にまぎれ込んだハエが、プンプンうなり声を上げ、クルド人の書いたヘブライ語のアルファベット19番目の文字をつついている」に酷似していて、文意もほぼ同じものになりそうだ。どちらも私が普段使っている辞書では、とても手に負えないボキャブラリを含んでいる。

 パングラムは、アナグラムの延長であると、この連載の中でも述ぺたことがあると思う。しかし、すでにある単語や文に含まれる文字を並べ替えて別の単語や文を作るというアナグラムと、AからZまで機械的に並んだ文字列を並べ替えて文を作るというパングラムでは、まるで事情が違うということが身にしみて分かってきた。その証拠にパングラムとしてはかなり苦しい30文字程度の文でも、アナグラムなら、

A Merry Christmas and a Happy New Year.
(メリー・クリスマス、新年おめでとう)
May many a red wreath carry happiness.
(願わくは、数多くの赤い花輪が幸福をもたらさんことを)

といった、美しく、しかも優れた作品が作られている(訳は「ことば遊びコレクション』による)。アナグラムとパングラムでは、文字の出現頻度という統計的な問題で、決定的な違いがあったわけだ(図1)。

pangram_zu1.jpg

コンピュータで完全パングラム!


 完全パングラムを、コンピュータを使って求めてみた話を前回までに紹介した。その方法は、アナグラムを求めるために作ったアナグラマ(穴蔵マ)というプログラムに、ほんのちょっとだけ手を加えたものだった。アナグラマについては、1992年4月号のこのページでアルゴリズムを、ソースコードは5月号のリストページに掲載している。

 アナグラマのこのバージョンの特徴は、まさに、文字の出現頻度の統計的データを利用したヒューリスティックによって成立している。アルゴリズムの教科書にあるような組み合わせ問題のプログラムでは、とうてい手に負えない問題のはずが、なんでもない工夫で許容範囲内の時間で処理できたわけだ(とはいってもスーパーアスキー編集部にある現行最高速クラスのワークステーションを使って数十時間はかかったのだが……。

 さて、アナグラマで求めたパングラムだが、前回にもちょっと触れたように、かなり厳しい内容のものしか求められていない。たとえば、

Hemp bldgs iinx frowzy TV quack.
(大麻で建てたビルが運のつき、テレビでいいかげんなことばっかりいっていたうす汚いあの野郎も、もうこれで終わりさ)
Quartz sphinx, few Jock gym blvd.
(水晶のスフィンクスよ、ジョックに体操用の遊歩道を無期限で貸し与えん)

などである。ご指摘を待つまでもなく、略語が含ま坑そいたりするわけなので、完全パングラムというにはおこがましいかもしれない。とはいえ、コンピュータによって完全パングラムのようなものを求めることができるわけだ。このプログラムをより強化するとすれば、スーパーアスキー編集部にマシン時間とメモリを占有しすぎて怒られないようにする高速化と辞書を充実するしか手がない。辞書の充実が、英和辞典にも載っていないような、一般の人々の使う単語から離れたものを加えるだけとしたら、ド・モルガンの指摘と同じように、これよりまともな完全パングラムを見つけることは難しいかもしれない。現在使用している辞書はスペルチェッカのデータをペースにした約6万語で、普段使うような単語はほぼカバーしている。

計算機的でないアプローチ


 完全パングラムが難しいなら、若干の文字の重複は許してもアルファベット26文字すべてを使ったパングラムを作ってみたくなるのが人情というものである。前回では、すでにその種のパングラムをコンピュータで求めた例があることを紹介した。現在のところ40文字以上あるパングラムしか作られていないとのことだったが、キャッシェル・ファレルという人によって、なんとか文の形になっだものが求められているのだった。

 私は、アナグラムや完金パングラムのときとは別の、何か気利いたアプローチはないかと考えた。そんな折に思いついたのが、遺伝的アルゴリズムである。

 遺伝的アルゴリズムは、本誌でも1991年6月号と7月号でスタジオ・ゲンの宮沢丈夫さんが「現代科学の最先端をあなたのパソコンで!」という連載で扱っている。前号でも触れた"Scientifoc American"(日本版は日経サイエンス)のA・K・デュードー氏のコラムでも紹介されたことがあったが、実際にプログラムを作成してソースコードを示しながら解説したものは、一般に読めるものとしては、官沢さんのものしかないかもしれない。それから、だいぶ前に編集部の吉田とNTT基礎研究所の竹内郁雄先生を訪ねたときに、これが面白いよと、米国の論文のコピーで見せられたのが、まさにこの遺伝的アルゴリズムだった。

 遺伝的アルゴリズムは、旧釆の機械的数学的なアプローチと異なり、文字どおり生物の遺伝をモデルにしたものである。

乱交の末、自然淘汰されるプログラム


 遺伝的アルゴリズムにっいては、本誌のパックナンバーをお持ちでない方のために、ざっとおさらいしておくことにしよう。もっとも、今回のプログラム(パングラマチストと名づけた)も理論的なパックグラウンドまで立ち入る余裕がなかったので、かならずしもこのとおりでない部分もある。

 遺伝的アルゴリズムの考え方は、J・H・ホランドという米国の科学者によって確立された。本誌の宮沢さんの連載では、1991年6月号で「巡回セールスマン間題」、7月号では「ナップザック問題」と、いずれも旧来のいかにもコンピュータ的なアプローチでは、膨大な計算量になってしまう「NP一完全」と呼ばれる種類の問題をテーマにしている。今回のパングラムの作成は、かなり趣は異なるもののやはり計算量が爆発する組み合わせ問題である。

 遺伝的アルゴリズムは、生物の遺伝、そしてダーウィン進化論的仕組みをシミュレートする。つまり、ランダムに個体のかけ合わせを行ない、その中でより強く、優秀なアウトプットが自動的 生き残っていくというアルゴリズムなのだ(図2)。

pangram_zu2.jpg

 「人間の性的な衝動は、より優れた入格を求めて働く」といっ 作家がいるが、まさに遺伝的アルゴリズムの核心もこれである。

 私のプログラムでは、パングラムとなるべき単語のグループそものを遺伝子としてモデル化することにした。最初は、ランダに単語を集めて、たとえば100の個体からなる集団を作る。こ最初の状態では1つの個体は、たとえば図3のように、まったくパングラムにも何にもなっていないような遺伝子となる。

pangram_zu3.jpg

 集団ができたら、次は交差だ。交差というと意味がよく分からないが、集団の中の適当な遺伝子同士を結婚させて、子供を作らるのである。子供の遺伝子は、親の遺伝子を適当なところで2つに切り、繋いだものとする(図4)。

pangram_zu4.jpg

 問題は、誰と誰を結婚させるかだ。私のプログラムでは、なんと100個の個体のうち優れた個体10を、総当たり制で交差させることにした。フィーリングカッブル5対5で、女の子5人全員が男子の5人全員にOKサインを出すようなものである。進化主義民族学でいえば、まさに乱婚時代(ヘテリズム)の様相である。乱婚時代が終わって(1万数千午くらい前)、家族や邑が形成され始めてから人類の発展は始まったというから、本当にこれでよいのかしらんとも思えないでもないが、10×10=100で、単純に次の世代の集団の個体数も100というのが分かりやすい。

 どの個体が優れているか? つまり、どの個体が生存競争に生き残って交差に参加できるかは、一重複している文字の数と登場していない文字の数の合計で評価することにした。より完成度の高いパングラムは、同じ文字をあまり重複して使っていないもののはずである。

 突然変異は、文字どおり交差して増殖した後に、ランダムに単語を投げ込むことで行なうことにした。発生の確率は適宜変更できるようにプログラムしてある。これで、1世代の誕生から次の世代の1サイクルが完了である。これを繰り返し、淘汰のための評価のところでパングラムができたかどうかをウォッチしてやればよいというわけなのである。

 交差のプロセスのところをはじめとして、なにぶん試行錯誤的なところがある。一夫一婦制のプログラムももちろん書いてみた。さまざまな因子を持った遺伝子が同時に生存しやすいという形となる。問題によってはこちらのほうが向くだろう。

プログラムの結婚の行方


 遺伝的アルゴリズムは、遣伝子をどう設計するかが、最も大きなカギではないかと、宮沢さんは指摘していたが、ここでは、パングラムを構成する単語のグループをそのまま遺伝子にするというかなりいいかげんな方法をとった。それにもかかわらず、このアプローチの御利益は、あっさりと目の前に現われてきた。

 本誌の1992年7月号の記事では、わずか20世代程度で、難問といわれるナップザック問題の最適解(もしくは、それに極めて近い解)を求めることができるとしていた。私のプログラムでも、同じ程度かそれ以下の世代交代で、はっきりしたパングラムへの収束が見られたのである。第1世代では、まったくランダムな単語の集まりだったのが、5世代目には早くも未使用文字が数文字になり、数十世代目でパングラムが求められるケースもあった(図5)。このへんは、実のところ突然変異の頻度や交差の仕方によって、かなり趣が変わってくる。意外だったのは、突然変異の頻度を抑えめ(十数~数十単語に1個)にしたほうが、収束のテンポが速いことだ。このへんのサジ加減が勝負になってくる。そんな行き当たリバッタリの方法で、ちゃんと答えまでたどりつけるのか? という疑問もあるだろう。従来のアルゴリズムは、キッチリ書いて、キッチリ動かし、なんらかの答えが求められるまで、 現在のソースコードの出来の良し悪しが判断できない。これに対して、遺伝的アルゴリズムでは、各世代の内容を画面に表示していけば、動かし始めてすぐに調子が分かり、手を下せるのである。

pangram_zu5.jpg

 三日三晩動かしたプログラムが結局間違っていて、まったくの無駄だったなどということは起こりにくいわけで、この点で「遣伝的アルゴリズムは、プログラマの精神衛生に良い」計算理論といえるのではないかと思う。

 ところで、このようにして最初に作ったプログラムでは、1つのパングラムにどんどん収束していくだけという動きだった。これは最適解を速やかに求められるという遺伝的アルゴリズムの醍醐味ではあるわけだが、たった1つのパングラムでは、面白くもなんともない。そこで、交差の部分に若千の工夫をして、次の世代がもっと変化に富んだ内容になるようにした。

 ともあれ、このプログラム (パングラマチスト)によって、いくつかのパングラムらしきものが出てきた。英語の文としては、かなり怪しいものばかりで、訳のぼうはいよいよ苦しいところだが、おつき合い願いたい。

Sphinx quiz cpmputer J, selfknowing avoidably.
(回避的に自己認識するスフィンクス問題計算機J)
Everything of jazzmen will be triplex quicksand.
(三重の危険こそ、ジャズマンたちにとって最も大切なものなのだろう)
Having work of zymurgy, objects equal expanders.
(醸造学の研究をすると、物体はエキスパンダーに等しくなる)
We vexed the debriefing of paiama zone's law quickty.
(我々は、パジャマ領域の法則を体験した話を迅速かつ綿密に検討した)
Murphy, vex as if you'd just quicksighted welch blazon.
(マーフィーよ、借金のごまかしを自慢げに記述した文書を一瞥したばかりであるかのごとく、怒りなさい)
He sez,"Job complex quails everything of wedlock."
(「仕事嫌悪症だと結婚生活の何もかもがおとおどしたものになる」と彼は言う)
"Who cemented byre jacks" is a quil of flagwaver prix.
(「牛小屋で働く人々をセメント詰めにしたのは誰か」というのが愛国者賞クイズになっている)
X'd (=executed)with zip, flybynight works equal curving jambs.
(元気よくなされたとしても、信頼できない仕事は、曲がっているよろいのすね当てに等しい)

 このプログラムは、実行を続ければそれだけ、新しいパングラムを書き出してくる仕組みである。今後のテーマとしては文して成立する単語の順列をうまい具合に組み立てる方法だろう。英語のテキストについては、実は、ちょっと面白いトリックがあるらしい。その話については、次回以降ということにしよう。
(ホーテンス・S・エンドウ)

------------------------------------------------------

0(ゼロ)グラムへようこそ「twitterはコミュニケーション革命なんかじゃない」

トラックバック

このページのトラックバックURL:

http://blogmag.ascii.jp/admin/mt-tb.cgi/3078

このページへのトラックバック一覧

myporn

Tracked on 2013年11月30日 18:55 from myporn

遠藤諭の東京カレー日記: アルファベット26文字で文を作る   続きを読む »

ASCII.jp Blogmag
[ブログマグ]
東京カレー日記

カテゴリー

最近の投稿

アーカイブ


Blog profile