アルゴリズムでコンピュータはさらに賢くなる

古今和歌集の和歌と注釈の中から検索する

ふつうテキスト検索というと文字の並びの中から、検索語を探し出すことを指します。その場合、文字は同じ方向に1列に並んでいるだけです。この中から検索することは、コンピュータの力を借りれば難しいことではありません。しかし、本来、文章はそのような一直線の文字列だけではありません。
古今和歌集で和歌が並んでいるところを想像してください。これだけなら一直線の文字列ですが、後世の人たちが、自分が読みやすいように注釈を加えたとします。意味がわかりやすいように、文字を間に入れる、あるフレーズを別のフレーズに置き換える、また文字を消してしまう。このような加筆・変更・削除の情報が原文と一緒に表示されているとき、この中からある検索語を探すにはどうしたらいいでしょう。すぐ思いつくのは、変更された和歌のパターンをすべて書き出すという方法です。しかし、1つの和歌の変更箇所が多い場合、その組み合わせの数は多くなり、書き出す作業に負担がかかります。

文字列を重ねて並べ、すべてを一挙に表示

原文と注釈を一緒に書こうと思えば、文字の並びは二重になります。加筆された部分は、その部分だけ二手に分かれます。変更は元のフレーズと変更後のフレーズに、削除は削除前と削除後に分かれます。文字列は、ある部分から二つに分かれ、合流するというパターンを重層的に繰り返すことになります。これは、すべてのパターンを書き出すより少ない文字数で済み、かつ同じ情報を持っています。ただ、文章が重なっているため、意味をたどるには何度も行ったり来たりする必要があります。これでは検索が難しいので、同じ枝分かれパターンを別の文字に置き換えることで、1列のテキストになるように戻してやります。実は、このやり方はデータを圧縮するという点でもメリットがあります。
検索といっても、その要求はさまざまです。高度な要求を可能にするアルゴリズムを考えることは、ソフトウェアをつくる上での楽しみでもあります。

※夢ナビ講義は各講師の見解にもとづく講義内容としてご理解ください。

※夢ナビ講義の内容に関するお問い合わせには対応しておりません。

先生情報 / 大学情報

九州工業大学情報工学部知能情報工学科教授坂本比呂志先生

興味が湧いてきたら、この学問がオススメ！

情報工学

先生が目指すSDGs

メッセージ

ソフトウェアを作る面白さは、アイデアだけでコンピュータの進歩以上の能力を引き出せることです。コンピュータはハードウェアの進歩によって、10倍、100倍と高速になりますが、そのためには莫大な開発費や生産設備コストがかかります。しかし、ソフトウェアは、アイデアがあれば千倍、1万倍のスピードを得ることも可能です。インターネットをはじめとする情報の増大によって、高速な検索技術への需要などはますます高まっていきます。ぜひ、ソフトウェアづくりに挑戦してほしいですね。

九州工業大学に関心を持ったあなたは

「情報工学」は、高度情報化社会の進展の中で、ますます必須知識・技術となっています。
九州工業大学情報工学部は1986年に創設された日本初、現在も国立大学で唯一の情報工学部です。知能情報工学科、情報・通信工学科、知的システム工学科、物理情報工学科、生命化学情報工学科の５学科があり、それぞれの分野において、高度な専門技術を身につけた人材を養成します。これまでに1万人を超える情報通信技術者を生みだし、様々な分野で日本の情報通信革命を支えています。