{"created":"2021-03-01T06:19:26.737237+00:00","id":2828,"links":{},"metadata":{"_buckets":{"deposit":"9a0433d1-3128-4cc5-9a7d-2704aeaa8ea7"},"_deposit":{"id":"2828","owners":[],"pid":{"revision_id":0,"type":"depid","value":"2828"},"status":"published"},"_oai":{"id":"oai:repository.dl.itc.u-tokyo.ac.jp:00002828","sets":["6:291:292","9:233:280"]},"item_7_biblio_info_7":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2004-04-15","bibliographicIssueDateType":"Issued"},"bibliographic_titles":[{}]}]},"item_7_date_granted_25":{"attribute_name":"学位授与年月日","attribute_value_mlt":[{"subitem_dategranted":"2004-04-15"}]},"item_7_degree_grantor_23":{"attribute_name":"学位授与機関","attribute_value_mlt":[{"subitem_degreegrantor":[{"subitem_degreegrantor_name":"University of Tokyo (東京大学)"}]}]},"item_7_degree_name_20":{"attribute_name":"学位名","attribute_value_mlt":[{"subitem_degreename":"博士(工学)"}]},"item_7_description_5":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"　膨大な情報の中から必要な情報を的確に見つけ出すことが情報検索であり、情報検索は情報化社会における基本的な技能の一つに位置づけられる。文書検索はテキスト文書を検索対象とする情報検索である。本研究がテキストを対象としたのは、テキストが知識を表現する上で最も主要なメディアという地位にあるからである。電子化文書の増大・検索ユーザの拡大・文書共有化の進展という最近のIT革命の進展に伴い、文書検索に対するニーズも非常に高まっている。//　文書検索の対象は自然言語で記述されたテキストである。文法・語彙等の特性は言語によって異なるため、言語ごとに相応しい文書検索モデル・実装方法も異なる。特に、検索高速化のために必要不可欠な索引において、索引の基本要素である索引単位として何を選択するかは性能および運用しやすさに大きく影響する。代表的な索引方式には単語を索引単位とする単語索引とn-gram(n文字組)を索引単位とするn-gram索引がある。単語を分かち書きせず、造語力の高い日本語においてはn-gram索引が広く利用されているが、n-gram索引には検索速度が遅いという問題がある。その理由は、ユーザから与えられる検索文字列が索引単位であるn-gramに一致するとは限らず、一致しない場合には複数のn-gramを用いて検索結果を求める必要があるからである。特に検索文字列がn-gramよりも長い場合には、検索文字列中のn-gramが全て出現する文書を特定(候補文書特定処理と呼ぶ)した上で、そのような文書においてn-gramが適切な相対位置にあって検索文字列を構成していることの確認(位置検査処理と呼ぶ)が必要であり、高速化の余地が大きい。//　本論文では、日本語文書を対象としたn-gram索引の検索処理の高速化について研究する。高速化の基本原理は、n-gram索引における検索コスト増大の主要因である位置検査処理を可能な限り省略・低減するというものである。n-gram索引における検索高速化の従来研究は、複数のnを組み合わせる、文字種に応じてnを調整する等のn-gram抽出法に集中していた。これに対し、本研究は検索処理法および索引の物理編成法の改良による高速化である点に特徴がある。//　検索処理法の改良では位置検査の削減・省略に着目した。日本語では造語力の高さから長い複合語がいくらでも生成されるため、n-gram抽出法の工夫だけではn-gram索引における検索速度低下要因の位置検査を無くすことが不可能だからである。位置検査省略による検索高速化という考え方は従来研究にも存在している。しかし、従来研究が単一検索文字列の場合のみを極めて限定的に扱っていたのに対し、本研究では以下の3点について拡張する。//(1)単一検索文字列処理において、省略するn-gramを動的に選択するように拡張//従来は候補文書特定と位置検査の両フェーズに同一のn-gram群を静的に選択していた。これに対し、本研究では両フェーズの処理特性の違いに着目して異なるn-gram群を索引内容に応じて動的に選択する。実際には、位置検査用には検索文字列を被覆するn-gram群のなかからn-gramの文書頻度の合計が最小となる組み合わせ(最小頻度パスと呼ぶ)を動的に選択し、候補文書特定には最小頻度パスにそれらの前後にある文書頻度の少ないものを加えたn-gram群を用いる選択n-gram法を提案した。選択n-gram法により、位置検査を行うべき文書数を削減するとともに位置検査自体のコストも低減し、単一検索文字列の検索処理を高速化できる。//(2)AND・OR・ANDNOTの論理演算子に拡張//従来は単一検索文字列の処理のみを高速化の対象にしており、論理演算子処理を対象とする研究はなかった。これに対し本研究では、論理演算子の処理アルゴリズムを複数の検索文字列の論理関係を考慮することで不要な位置検査を行なわないように改良し、検索を高速化する。AND，OR，ANDNOTの3種類の論理演算子について、この考えに基づく拡張省略法を提示した。さらに、演算子が入れ子になった複合条件に対しても拡張省略法が適用できることを示した。//(3)ランキング検索に拡張//ランキング検索では検索条件に対する文書スコアに応じて検索された文書を順序付けする。文書スコア計算には文書頻度・文書内頻度の2種類の頻度情報が必要であるが、両頻度を求めるたびごとに位置検査が発生するため検索コストが増大する。従来研究としてn-gramの頻度情報に基づいてスコア計算するスコア合成法が提案されているが、検索精度の低下という問題があった。これに対し、検索精度を低下させることがないように検索文字列の頻度情報に基づいてスコア計算しつつ、頻度情報を求める際に必要な位置検査を可能な限り削減する2つの高速化手法を提案した。1つ目の順序入れ替え法は、検索文字列が出現する文書を特定すると同時に文書内頻度も求めることで、従来必要であった文書頻度を単独で求める処理を省略する。もう1つの頻度推定法は、検索文字列を構成するn-gramの頻度情報から文書頻度および文書内頻度を近似的に求めることで位置検査を省略する。これら2つの高速化手法は組み合わせ可能であり、相乗効果が期待できる。なお、推定頻度は必ずしも正しい値にならないため、頻度推定法によるランキング結果は基本方式のものと同一とは限らないが、検索精度への影響は極めて小さいと考えられる。//　n-gram索引のファイル形式としては、n-gramの各文書における出現位置を格納可能である転置ファイルが一般的である。本研究では、位置検査省略による検索高速化手法向けの転置ファイルの物理編成法も提案する。単語索引用転置ファイルの物理編成法は従来から研究されており、その一部はn-gram索引に対しても有効である。本研究では、n-gram索引では検索処理が候補文書特定と位置検査の2つのフェーズから構成され、文書内出現位置は位置検査でしか用いられないという処理特性に着目した物理編成法を提案する。具体的には、n-gramの出現情報を、文書IDとそれ以外の文書内頻度・出現位置情報に分離して配置するとともに、出現情報を圧縮する際にブロック化する。以上の工夫により、ページアクセスおよび検索時の伸長処理を大幅に削減することが可能となる。//　提案高速化手法の評価実験を行った。単一文字列と論理演算子については新聞記事8年分、85万文書(テキスト量748MB)を用いて評価した。ランキング検索については論文要旨33万文書(テキスト量267MB)から成るテストコレクションNTCIR-1を用いて評価した。以下の表は評価結果のまとめである。//　この表は、全データの読み込みを伴うCOLD、条件評価フェーズにおけるデータ読み込みのみのWARM、データ読み込みを伴わないHOTの3つ場合について、従来手法に対する提案手法の検索速度の向上率を示している。ランキング検索については、高速化効果が最大であった順序入れ替え法と頻度推定法を組み合わせの結果を用いている。この結果から提案手法により検索が大幅に高速化され、特にAND演算子、ランキング検索に対する効果が大きいことが確認できる。また、COLD，WARM，HOT となるにしたがって高速化効果が大きく、HOTでは73〜250%に達していることから、提案手法はディスクアクセスよりもCPU処理の削減に効果が大きいことがわかる。//　つぎにランキング検索における単語索引n-gram索引の性能比較結果を示す。//　この表で、n-gram索引は従来方式、改良n-gram索引は提案方式の結果である。改良n-gram索引では検索精度をほとんど低下させることなく検索を高速化した結果、単語索引に対する検索時間の差異が小さくなることが確認できた。特にHOTにおいては検索時間の差は約10%と小さい。本実験はbi-gram索引を使用するというn-gram索引にとって不利な状況での測定結果ということを考慮すると、検索が遅いというn-gram索引の問題点は提案手法によりかなり克服できたと言える。//　また、物理編成法の改良に関する性能評価も行った。本研究で提案した出現位置情報の分離とブロック化自体の組み合わせにより、基本的な転置ファイルの物理編成法に対して 81%(COLD)，128%(WARM)，860%(HOT)の高速化を達成できることを確認した。//　本研究の成果は全文検索エンジンであるFTSサーバとして製品化され、当社の図書管理システムやオフィス向け文書管理システムなどで広く採用されている。FTS最初のバージョンの開発時に行った性能比較によれば、当時市場で最高速であるという評判の商用文書検索システムに対して2.5倍(HOT)から4.0倍(COLD)高速であり、提案高速化手法の有効性が製品レベルでも確認できた。//　今後の課題としては、日本語以外の言語に対する提案手法の有効性の検証、更新性能を考慮した複数索引への対応、質問拡張の高速化検討などがあげられる。日本語以外の言語の対応では中国・韓国語等の東アジアの言語が主な対象となるが、言語特性から提案手法が有効であることが期待できる。複数索引への対応についてはランキング検索の高速化が問題となるが、順序入れ替え法を拡張することで対応可能と考えられる。質問拡張については、選択する関連語の選択時の頻度取得が速度上の問題となるが、頻度推定法の適用により対応可能と考えられる。","subitem_description_type":"Abstract"}]},"item_7_dissertation_number_26":{"attribute_name":"学位授与番号","attribute_value_mlt":[{"subitem_dissertationnumber":"乙第15998号"}]},"item_7_full_name_3":{"attribute_name":"著者別名","attribute_value_mlt":[{"nameIdentifiers":[{"nameIdentifier":"7428","nameIdentifierScheme":"WEKO"}],"names":[{"name":"オガワ, ヤスシ"}]}]},"item_7_identifier_registration":{"attribute_name":"ID登録","attribute_value_mlt":[{"subitem_identifier_reg_text":"10.15083/00002822","subitem_identifier_reg_type":"JaLC"}]},"item_7_select_21":{"attribute_name":"学位","attribute_value_mlt":[{"subitem_select_item":"doctoral"}]},"item_7_subject_13":{"attribute_name":"日本十進分類法","attribute_value_mlt":[{"subitem_subject":"007","subitem_subject_scheme":"NDC"}]},"item_7_text_22":{"attribute_name":"学位分野","attribute_value_mlt":[{"subitem_text_value":"Engineering (工学)"}]},"item_7_text_24":{"attribute_name":"研究科・専攻","attribute_value_mlt":[{"subitem_text_value":"Department of Electronic Engineering, Graduate School of Engineering (工学系研究科電子工学専攻)"}]},"item_7_text_27":{"attribute_name":"学位記番号","attribute_value_mlt":[{"subitem_text_value":"第15998号"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"小川, 泰嗣"}],"nameIdentifiers":[{"nameIdentifier":"7427","nameIdentifierScheme":"WEKO"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2017-05-31"}],"displaytype":"detail","filename":"K-215998-1.pdf","filesize":[{"value":"5.2 MB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"K-215998-1.pdf","url":"https://repository.dl.itc.u-tokyo.ac.jp/record/2828/files/K-215998-1.pdf"},"version_id":"75808d52-b6ec-4968-9e06-8e72166f6169"},{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2017-05-31"}],"displaytype":"detail","filename":"K-215998-2.pdf","filesize":[{"value":"7.1 MB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"K-215998-2.pdf","url":"https://repository.dl.itc.u-tokyo.ac.jp/record/2828/files/K-215998-2.pdf"},"version_id":"81f14403-61b8-4a84-83f3-74b2b1f5c321"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"thesis","resourceuri":"http://purl.org/coar/resource_type/c_46ec"}]},"item_title":"日本語文書を対象としたn-gram索引による高速検索手法の研究","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"日本語文書を対象としたn-gram索引による高速検索手法の研究"}]},"item_type_id":"7","owner":"1","path":["280","292"],"pubdate":{"attribute_name":"公開日","attribute_value":"2012-03-01"},"publish_date":"2012-03-01","publish_status":"0","recid":"2828","relation_version_is_last":true,"title":["日本語文書を対象としたn-gram索引による高速検索手法の研究"],"weko_creator_id":"1","weko_shared_id":null},"updated":"2022-12-19T03:44:44.898449+00:00"}