文字列処理アルゴリズム

コンピュータ上で情報がどのように表現されているかは、何を基本にするかで捉えかたが違ってきます。 例えば、バイナリ・コードを基本にすると「すべての情報は0と1の列で表される」といえます。 あるいはそれを2進数と捉えて「すべての情報は整数で表現される」という人もいます。 しかし、あえて原始的に考えるならば、「すべての情報は文字列で表現される」のです。

情報の基本単位として文字(記号)を選択することは、人間にとって自然なことです。 また実際にコンピュータ上の多くのデータは、人間が読めるという意味で可読な文字列のデータ(テキストデータ)です。 拡張子が「.txt」や「.log」といった普通のテキストファイルはもちろん、近年急激に増加したHTMLやXML文書、ゲノムの遺伝子データも、すべては文字列データです。 そもそも計算理論の基礎である有限オートマトンや文脈自由言語・Turing機械などは、どれも文字列を対象にしています。 すなわち、文字列処理は情報理論において基本的かつ重要な存在なのです。

文字列を処理するアルゴリズム(計算手続き)はスペルチェックやデータマイニングなど様々な分野に応用されていますが、中でも情報検索は最も良く知られた活用方法でしょう。 例えば、フリーソフトウェアで有名な全文検索システムNamazuは、テキストデータ群から索引となるデータ構造を構築し、その索引構造を用いて文書ファイルを検索しますが、この索引構造を構築するためにいくつもの文字列処理アルゴリズムが用いられています。 また、ファイル中のキーワード検索ツールであるgrepや、InternetExplorerのページ検索(Ctrl-F)なども文字列処理アルゴリズムが使われています。

特に文字列照合(パターンマッチング)アルゴリズムを中心に、こうした基礎的な文字列処理のためのアルゴリズムやデータ構造に関して研究を行っています。

【共同研究者】

【関連URL】

圧縮データに対する文字列照合

ハードディスクやメモリの容量が十分に大きくなってきた今日、コンピュータを個人的に利用する範疇において「容量を減らすためにテキストデータを圧縮して保存する」ということはほとんどないでしょう。 Windowsにはフォルダごとに圧縮をかけて容量を小さくする機能がありますが、私はこの機能を使ったことがありません。 画像や音声データのようなマルチメディア・データならば圧縮して保存するのが当然ですが、テキストデータを圧縮することは百害あって一利なしと思われるでしょう。

しかし、例えば大量のログファイルや過去のメールデータなどは削除せずに圧縮保存しておくほうが得策です。 つまり「あまり頻繁には利用しないが、稀に参照することがあるかもしれない大量の文書群」は圧縮保存される場合があります。 ところが、そうした圧縮された文書ファイル群の中から必要な文書ファイルを探し出す作業は、案外たいへんで時間がかかります。 なぜならば、ファイルを探し出す作業の前に圧縮ファイルを元に戻す作業が必要だからです。 このような背景から「圧縮されたテキストを展開せずに文字列照合を行う」という研究の必要性が認められてきました。

本分野の研究が始まった1990年代初頭ごろは、「はたして展開せずに照合できるのか?」という理論的興味の研究がほとんどでしたが、1998年、我々の研究室が初めて実用的なアルゴリズムを開発しました。 そのアルゴリズムはLZW圧縮されたテキストから複数のキーワードを同時に照合でき、しかも展開してから照合するよりも高速なものでした。

その後も研究を重ね、現在ではさらに「圧縮していないテキストに対して照合処理を行うよりも高速に照合できるアルゴリズム」を開発しました。

【共同研究者】

【関連URL】

電子図書館

今日では、コンピュータ・ネットワーク環境が充実し、いつでも・どこでも・だれでも膨大な情報にアクセスできるようになりました。 図書館が提供するサービスも、電子ジャーナルや所蔵検索サービス、電子資料など、ネットワーク上で提供するものの割合が多くなってきました。 そのような背景の中、本学附属図書館研究開発室では、電子図書館のためのシステム開発に取り組んでいます。

【図書目録イメージ検索システム】

図書館が所蔵している図書を検索するウェブ上のシステムにはOPACがあります。 ところがOPACでは比較的最近の書誌情報しか検索できません。 というのも、多くの古い図書はOPACで検索できる電子情報が入力されていないからです。

特に歴史の長い図書館では、過去数十年にもわたって膨大な資料が蓄積され、またその書誌情報は目録カードとして蓄積されてきました。 これらの情報を遡及的に入力し、電子的な検索を可能にすることは、図書館にとって大変重要なことです。 今後遡及入力すべき目録カードの数は、全国の大学附属図書館全体で3,500万件余りと見積もられています。 本学附属図書館に限っても約161万件に上り、それらすべてを入力するために約13億円もの費用がかかると試算されました。

本システムは、このような状況を改善し、少しでも早く図書目録カード検索の電子化を実現させることを目指しています。 遡及入力の終了を待たずに、ウェブ上での書誌情報検索を実現するシステムです。 そのために、現存する目録カードをスキャナで読み取り、目録カードを画像にしてデータベース化しています。 このシステムによって、カードボックスからカードを探すイメージで、ウェブ上からカードを検索することができます。

【古医書画像データベース検索システム】

九州大学附属図書館医学分館では、数年間にわたる調査により数多くの古書が発見され、西洋の古医書や和書・漢書を多数含む国内有数のコレクションが構築されました。 現在、国内外の医史学者・医学者・歴史学者・医師・美術史家の方々を中心に、本コレクションの書物や挿絵に対する関心が高まっています。

本システムは、その古医書の画像データベースを効率よく閲覧するために、本学附属図書館研究開発室と医学分館が共同して開発しました。 全171タイトル約9500枚の画像すべてにキーワード情報を付加しており、自由なキーワードで画像を検索することができます。 また、300dpi以上の高精細画像を閲覧するために専用のビューアを開発しました。 特殊なプラグインソフトをインストールすることなく画像の拡大・縮小やスムーズな視点移動などが行えます。

【共同研究者】

【関連URL】

RFIDの図書館への適用

RFタグの貼付例
RFタグの貼付例

盗難防止ゲート
盗難防止ゲート(筑紫分館)

図書に書誌情報を貼り付けるデータキャリア技術としてはバーコードが主流ですが、近年RFID(Radio Frequency Identification)と呼ばれるシステムが注目を集めています。

RFIDとは、情報を電子的に保持しリーダ/ライタ装置と電磁誘導により非接触で情報を交換できる新しいデータキャリア技術です。 そのタグはRFタグとも呼ばれ、内蔵のICチップにアンテナをつけたものです。 RFタグ自らは電源を持たず、外部からの電磁誘導により供給された電力を用いて働きます。 このような特徴を持ったRFIDシステムを図書館業務に導入することにより、
 1)図書受入作業の効率化
 2)図書貸出・返却作業の効率化
 3)返却図書の配架作業の自動化
 4)書架からの該当図書の位置検索
 5)バーコードによる識別機能と
   タトルテープによる盗難防止機能の統合
などが実現できると期待されています。

本学附属図書館では全国の国立大学図書館に先駆け、平成14年に筑紫地区の分館において試験的にRFIDシステムの導入を行いました。 本研究では、RFIDシステムを用いた図書館の省力化を実現するための技術面・運用面での課題を明らかにし、その解決策を与え、次世代の図書館システムを提案することを目的としています。

【共同研究者】

【関連URL】

情報リテラシーとe-Learning

教育機関である大学の一員として図書館も学生の教育を担うという認識から、情報リテラシー教育の拠点となりうる図書館の在り方をこれまで模索してきました。 その一つの成果として、平成13年から情報検索講習会と称した一連の講習会を開催しています。 この講習会にはこれまで延べ1000人以上の人が参加し、ひとつの成功を収めたといえます。

しかしながら、時間がとれず目的の講習会に参加できなかったという受講者の声も少なくありませんでした。 また、一方では講習会を担当する職員各人の負担が甚大であり、通常の業務への影響が問題となってきました。 こうした背景から、情報リテラシー教育を効率よく行うためにネットワークを利用した遠隔教育(e-Learning)に着目し、そのための技術動向の調査を開始しました。

時期を同じくして本学情報基盤センターの井上 仁 先生らもe-Learningに注目しており、結果、Webブラウザを利用したWBT(Web Based Training)のためのコースウェアシステムとしてWebCTが本学の情報基盤センターに導入されました。 WebCTはカナダのブリティッシュコロンビア大学で開発され名古屋大学の情報メディア教育センターを中心に日本語化されたシステムです。 これにより、学習者は距離や時間の制限を受けることなく学習することができます。

本研究・教育活動は、平成14年度および平成15年度の九州大学教育研究プログラム・研究拠点形成プロジェクトとして採択され、附属図書館・情報基盤センター・医学部保健学科等を中心にWebCTコースコンテンツを作成することになりました(P&P種別C:研究課題名「eラーニングシステムを利用した学内教育基盤整備のためのモデル講義の構築」)。 これまでに研究開発室では、Web検索・OPAC・Webcat・WebcatPLUSなどの自習用コースコンテンツを作成しました。 今後は、Web of Scienceなどの文献検索システムや電子ジャーナルの利用方法を学ぶことのできるコースコンテンツを作成する予定です。

【共同研究者】

【関連URL】