テキストの比較アルゴリズム

この仕事は2002(平成14)年５月ごろのことですが、タッチタイピングの練習プログラムを作成していたときに、MS-Excelで二つのテキストの比較アルゴリズムを考えておりました。そのときにスウェーデンにあるstockholm biofinformatics centerのホームページに、ダイナミックプログラミング（DP）を使ったNeedleman/Wunsshのデータアラインメントの記事を読んでいると、これがタイピングの比較アルゴリズムにも応用できないかと考えたのが最初でした。

ダイナミックプログラミングは、日本語で動的計画法とも呼ばれておりますが、情報処理の分野では幅広く利用されている手法であると思います。最初は以下のようにMS-Excelを利用して、このタイピングの比較アルゴリズム問題を考えておりました。まず、二つの文字列のマッチしている数だけ、表の中の数字がだんだんと増えていくように、スコアリングと呼ばれる式に従い表を埋めていきます。その後、バックトレースというアルゴリズムで、アラインメントをしていくわけですが、これには再帰的な定義が利用できるのではないかと思い、実験用のプロトタイプはprologというプログラム言語で書いてみました。

この結果、非常に良いテキスト比較の能力があるということが分かってきて、この分野の研究をされておられた大学関係の情報処理学会正会員の方に、話を持っていきました。このときにはprolog言語で書いたせいか、結果が求まるまでの時間が随分とかかったことで、JAVAで高速化できるなら、ソフト作成費は出しましょうという話になりました。

そこで、苦心しながらもJAVAのプログラムに取り組んだ結果、2002年９月には無事に完成したソフトウェアを納品することができました。このソフトウェアで使用されている練習テキストは、米合衆国では有名なタイピングテキストに基づくもので、練習テキストを選択した後、お手本が表示されますので、そのすぐ下にお手本を見ながらタイピングしていくという単純なものです。そして、入力が終り「Analyze」ボタンをクリックしますと、削除、挿入、誤り、入れ代わりなどの内容を表示してくれます。

当時は、WindowsOS上でSUNマイクロシステムズ社のJ2SDK1.4.0というバージョンを使用しておりました。今回は、このときと全く同じプログラムをubuntuOS上に、SUNマイクロシステムズ社のJDK1.6.24というバージョンで動作するように移植しました。さらに、「Analyze」ボタンをクリックしてから、結果が表示されるまでの処理時間も計測するように追加しました。その動作結果をいくつか以下に提示しております。動作速度はほとんど数ミリ秒以下で済んでいますので、ボタンをクリックしてからほぼ瞬時に結果が表示されていることが数値でも確かめられます。（使用したパソコンのCPU速度は、430MHz程度のものです）　なお、削除された文字だけは、お手本のテキストの下にしか表示できませんので、そのようにしております。

Ｄ：削除（Delete）　Ｉ：（Insert）　Ｅ：（Error）　Ｘ：（Exchange）

例１

例２

例３

例４

例５

例６

例７

JAVAソフトの作成が終わった後、納品先の大学関係者だった方に、共同で論文を出しませんかという打診をしたところ、特に名前を入れる必要はありませんよというような返事があったこともあり、この件についての学会講演はいまだにしておりません。

この仕事で非常に重要な点は、基準となるお手本のテキストがないと、挿入や削除という定義ができないということではないかとみております。ここで例７において、以下のように、お手本と打ったテキストが逆の立場になったとすると、ちょうど挿入と削除が全く逆になるということです。（以下の例で、正解率Rate=0%は、お手本の文字数に対して、誤った文字数が非常に多いために、計算結果が負になるものはゼロパーセントとしております）

すなわち、基準となるモデルがあってこそ、はじめてダイナミックプログラミングによる比較という意味が出てくるものと考えられます。近年は、世界中にDNA情報をはじめ、ゲノム解析の研究者が多額の資金を調達して、ヒトゲノムの研究をされておられるようです。しかし、その根本となる人間の基準となる情報モデルが作れるのかどうかということが最大の問題ではないでしょうか。

ヒトは、約30億といわれる長さの塩基対があるといわれております。宇宙の年齢を約200億年とすると、現在は宇宙のビッグバンから約63京秒ほど経過していると考えられるわけですが、その時間内にこれだけの生態系と人間という高度な知的生命体が活動しているということは、太古に地球上の無機物が有機物へ転換し、あらゆる生命が誕生し、魚類、爬虫類、哺乳類などに進化して、現在ヒトが万物の霊長類として地上に住んでいると考えられます。21世紀の初頭には、世界の人口が61億3,400万人といわれておりました。本当にこの人々のすべてのゲノム情報を使って、ヒトのゲノム情報が完全に解析できるのでしょうか。

仮に一人の人間のゲノム情報サイズを30億と考えますと、G（グアニン）T（チミン）A（アデニン）C（シトシン）の４種類の塩基対を２ビットで表わすことができるので、８ビット＝１バイトで４つのサイズが記憶できますが、ダイナミックプログラミングを利用した解析の場合には、マッチングした数に応じてスコアリング数が増えていきますので、配列の一つの要素は最大32ビットは準備しておく必要があります。

すなわち、二次元配列ですから、一つのセルあたり30億を二乗した分に、さらに４バイト（32ビット）を掛けた記憶容量がないと、ダイナミックプログラミングによって情報をアラインメントできないということになります。大体このオーダーが36メガ・テラバイト（エクサバイト）という巨大な容量になると考えられます。このような記憶装置を調達するには、現在巨額の費用がかかるのは明らかだと思います。

もちろん、前述したようにヒトゲノムの基準モデルがあって、はじめてダイナミックプログラミングによる情報アラインメントというものが意味を持ってくるものと考えらます。従って基準モデルを作るために、基準モデルを使って比較しないと意味のないところに、基準モデルではないもの同士をいくら比較しても、得られるものはほとんど意味のない情報ではないでしょうか。

おそらく予測としては、人類がヒトゲノムの基準モデルを獲得する可能性は極めて低いのではないかとみております。これらのことに人類が時間とお金を多量に使うことが、本当に人類全体の幸福につながるのでしょうか。物質文明の急速な進歩発展の中で、人間は大自然により生かされているという簡単なことが忘れ去られることがないように、これからも科学の進歩を見守っていきたいと考えております。

《追記》
かつてライプニッツやゲーデルが神の存在を学問的に証明する試みを行ったことは有名な話ですが、このページの内容も、間接的に世界や人間を創造している神が存在することを知らせる意味があるのではないかと考えています。つまり神と人間は、神と人間ほど違うのだという結論が導かれたことを示唆するものだといえるのではないでしょうか。

[1]タッチタイピングとは、キーボードを使って「手元を見ない」、「打ち間違っても気にしないで練習を行う」ということにより、目からの文字情報が脳を通じて、手や指の運動系列に変換され、スムーズな打鍵運動として形成されることです。