開発者支援を目的とした WWWソフトウェア検索エンジンの構築

Presentation on theme: "開発者支援を目的とした WWWソフトウェア検索エンジンの構築"— Presentation transcript:

1 開発者支援を目的とした WWWソフトウェア検索エンジンの構築
2003年3月18日(火曜日) 奈良先端科学技術大学院大学 情報科学研究科 ソフトウェア工学講座 松本 健一、門田 暁人、亀井 俊之、 大杉 直樹、玉田 春昭

2 過去に開発されたソフトウェアに関する知見のデータベースと，
背景 過去に様々なソフトウェアが開発されているが，その知識が有効に蓄積・利用されていない． 似たようなソフトウェアが様々な場所で開発されている． 同じような問題で，ソフトウェア開発が滞ることがある． ソフトウェアに関する 知見データベース クエリ 検索結果 検索エンジン 過去に開発されたソフトウェアに関する知見のデータベースと， 検索エンジンが必要ではないか． 検索者

3 WWW の公開データをソフトウェアに関する知見の
背景 一方，WWW には多くの情報が共有されている． ソフトウェア開発の手助けとなるような情報もたくさんある． ソースコードそのものやそのコメント ソフトウェア開発途中に得られた知見のメモ 掲示板の過去ログ WWW の公開データをソフトウェアに関する知見の データベースとして利用する． ソフトウェアに関する 知見データベース クエリ 検索エンジン 検索者 検索結果

4 目的 WWW を対象としたソフトウェア検索エンジンを構築する． ソフトウェア資源をWWWから収集し，ユーザに提供する．
ソフトウェア資源とは，ソースコードやソフトウェアの実行ファイル，開発日記や Tips など，ソフトウェア開発に役立ちそうな公開ファイル全般を指す． 本発表では，java のソースコードにターゲットを絞る．

5 ソフトウェア検索 利用者支援 開発者支援 ソフトウェアを利用するために，ソフトウェアの名称やだいたいの働きをキーとして，検索する．
ソフトウェア開発の手助けとするために，行数や変数の数，使っているパッケージやメソッドなどをキーとしてソースコードなどを検索する．

6 ソフトウェア検索（利用者支援） 登録型ソフトウェアライブラリ
窓の杜，Vector，Download. COM など． 管理者の選んだオンラインソフトなどを説明文とともにデータベースに納めておき，キーワードによる全文検索を行う． 窓の杜 Vector

7 ソフトウェア検索（利用者支援・開発者支援）
登録型プロジェクトライブラリ，登録型ソースコードライブラリ SourceForge や Layer-8 など． 登録されているプロジェクトやソースコードに対して，キーワードで検索を行う． SourceForge Layer-8 Technology

8 ソフトウェア検索（検索エンジン） これらのサービスはデータベースを人手で作っており，WWW 全体を対象に検索できない．
クエリを入力し，その結果の周辺を人手でブラウジングし，情報を集める． ex) java のソーティングに関するソースコードを得たい場合，「java sort」とクエリを作って検索し，その周辺をブラウジングする． 手間と時間がかかる．

9 ソフトウェア資源を事前に収集して解析し，検索できるように
ソフトウェア検索（開発者支援） あるプログラムが作りたくて，参考になりそうなコードを読みたい． あるクラス，パッケージの典型的な使い方が知りたい． あるアルゴリズムについて，コメントが多く書いてあるコードを読みたい． 特定の型の変数を引数と返り値に持つメソッドを知りたい． ソフトウェア資源を事前に収集して解析し，検索できるように しておかなければならない．

10 巡回ロボットを用いて，ソフトウェア資源を
提案手法 集めた資源を解析し， データベースに納める． WWW ユーザからのクエリに対し， 適切な資源を提供する． 解析データ 解析 検索 収集 インタフェース 巡回ロボットを用いて，ソフトウェア資源を 収集する． 検索結果 ソフトウェア資源 収集データ ・資源へのポインタ （url） ・解析結果 クエリ ユーザ

11 収集（基本方針） ソフトウェア資源がなさそうなところは極力巡回しない． WWWすべてを網羅して巡回することは不可能． 巡回の基本的な戦略
ソフトウェア資源が存在しそうなところを起点として巡回を始める． 巡回しながら簡単な見積もりを行い，巡回路を制御する．

12 受け取った URL を解析し，（Aタグを抽出）
収集部（巡回ロボット） 巡回ロボットの一般的なアルゴリズム． 巡回の中心となるポイント． 選んだ URL を新たな起点とする． 起点URL ・・・ どれを優先的に巡回するか． 巡回アルゴリズム 巡回ロボット 受け取った URL を解析し，（Aタグを抽出） 新たに URL を得る． 起点URLと，巡回アルゴリズムによって 巡回ロボットは性格付けがなされる． ソフトウェア資源収集用に工夫する．

13 ソフトウェア資源を扱っているコミュニティ内を巡回する．
収集部（WWWの特徴） ページはリンクによって連結されているが，連結されるページは共通のトピックスを扱っている傾向がある． 料理のレシピを公開しているサイトは同じようにレシピを公開しているサイトにリンクする傾向にあり，またソフトウェア資源を公開しているサイトは同じようなサイトにリンクする傾向がある． 巨視的に見ると，共通のトピックスを持ったコミュニティが形成されているといえる． sourceforge とかではない！ 個人的なページの集まり． ソフトウェア資源を扱っているコミュニティ内を巡回する．

14 コミュニティの近くの URL を得るために，検索エンジンを使う．
ソフトウェア資源を扱っているコミュニティを発見する． WWW Search Engines コミュニティの近くの URL を得るために，検索エンジンを使う． Query ? コミュニティ内でよくでる単語 コミュニティ

15 ? × 収集部（見積もり） ある程度探索した時点での資源の発見具合によって，探索の深さを制御する． Search Engines 探索
ソフトウェア資源 収集データ × 検索結果 Query 見込みが無さそうなら中断， まだありそうなら深く探索する． n 回たどった時点で，資源が m 個見つかっていれば，さらに n 回たどる． その後，さらに n 回たどった時点で m 個見つかれば n 回延長する． （n, m : 定数）

16 目的のリンクを優先的に探索できるように，
収集部（巡回アルゴリズム） WWW ページ構造の特徴を生かし，巡回路を決定する． 外部へのリンク 目的のリンクを優先的に探索できるように， 特徴を発見する． ・ URL （dl, products など） ・ リンクの文字列 （ダウンロード, software など） ソフトウェア資源

17 収集部（巡回アルゴリズム） ひとつのサイトにあまり固執することなく，次へ進む． ソフトウェアとは関係のないサイトに陥ってしまうことを避ける．
外部へのリンク 同一ドメイン内では， n’ 回たどった時点で，資源が m’ 個 見つかっていれば，さらに n’ 回たどる． ( n’ < n, m’ < m )

18 解析部 収集したソフトウェア資源を解析し，インデクシングを行う． 圧縮ファイルは解凍し，ソースコードや関連ドキュメントを取り出す．
慣例的に説明に用いられるテキスト（readme.txt など）を資源の説明としてデータベースに納める． 資源を発見したページに出現する特徴的な単語や，タイトルタグなどに含まれる文字列を資源の説明としてデータベースに納める．

19 解析部 ソフトウェアメトリクスとシンボル情報を取得する． ソフトウェアメトリクス シンボル情報 LOC サイクロマティック数 演算子数 ・・
パッケージ名 クラス名 メソッド名 メソッドの引数の型と数・返り値の型

20 解析部 クラスとメソッドにテーブルを分けて，データベースに納める． classTable methodTable
date : DATETIME className : CHAR LOC : INT numMethods : INT ・・・ methodTable methodName : CHAR class : CHAR

21 検索部 ユーザからクエリを受け取り情報を提供する． データベースから，SQL 文を用いてデータを取り出す．
select * from classTable where className like ‘%bubbleSort%’ and LOC < 30 and .. 簡単に SQL 文を作成できるインタフェースを用意する． ブラウザ

22 システムの試作 プロトタイプの実装を行った． 約24時間巡回ロボットを運用した．
ソフトウェアメトリクスの測定には，†javancss を用い，測定したパラメータは以下の通り． パッケージ名，クラス名，メソッド名 メソッド数 引数の数と型 コード行数，コメント行数 javadoc 形式でコメントが記述されているかどうか 約24時間巡回ロボットを運用した． クラス数約 2,000 個 メソッド数約 35,000 個 †

23 システムの試作（インタフェース）

24 システムの試作（想定検索１） 「バブルソート」のアルゴリズムが知りたい！ メソッド名を対象に「bubblesort」で検索．
Google で「bubblesort java」で検索すると，一応コードは得られるが，わざわざhtml形式に書き直してくれている解説サイトなどで，量は少ない．

25 システムの試作（想定検索１） SortAlgo.bubbleSort() public class SortAlgo { ・・・
int[] intArray;void bubbleSort() { CAT.info( "Entered the sort method."); for(int i = intArray.length -1; i >= 0 ; i--) { NDC.push("i=" + i); OUTER.debug("in outer loop."); for(int j = 0; j < i; j++) { NDC.push("j=" + j); INNER.debug( "in inner loop."); if(intArray[j] > intArray[j+1]) swap(j, j+1); NDC.pop(); }

26 システムの試作（想定検索２） singleton パターンについて，コメントが多く書かれたソースを見たい！
クラス名を対象に，「singleton」を含み，javadoc が50%以上のものを検索．

27 システムの試作（想定検索３） メソッド名に「Stream」を含み，引数として String を受け取るメソッドを検索．

28 まとめ 開発者支援を目的として，WWWを対象にソフトウェア資源をその特徴を生かして検索できるシステム構築法を述べた．

29 今後の課題 検索エンジンのクエリを自動的に改良できるようにする． 巡回路の制御法の最適値を実験によって確かめる． インタフェースを考える．
資源が発見されたページの特徴的な単語を加える． 巡回路の制御法の最適値を実験によって確かめる． インタフェースを考える． 検索結果の表示順を考える． 利用頻度や，利用関係をもとにスコアリングを行う．

30 システムの試作 集めた資源について 検索エンジンに与えるクエリによって，有効な資源の割合が大きく影響された．
有効でない資源 ： 市販ソフトのアップデートファイルや，ソースの含まれていない圧縮ファイルなど． 「java, download」 では，有効な資源は 86%であった． 「java, sample」 では，有効な資源は 69%であった． URL の先読みから資源が見つかった例は両方とも1割以下であった．

31 著作権について ロボットの運用は，基本的に robots.txt† に従う． Google の画像検索の場合
ロボット型検索エンジンに対する命令を記述するためのファイルで，自分のページが検索エンジンのデータベースに登録されないように指示するもの． Google の画像検索の場合 Google イメージ検索によって表示される画像は、著作権で保護されている場合があります。 Google のサービスを通して画像を検索し、アクセスすることはできますが、Web 上で表示する以外にそれらを使用する権利を許諾することはできません。 従って、Google のサービスを通して検索した画像をご使用になる場合は、そのサイトの所有者にお問い合わせになり、必要な許可を取得してください。 †A Standard for Robot Exclusion