論文

DBSJ Letters Vol.6, No.4

文単位転置インデックスによる近接検索手法
Sentence-based Inverted File for Proximity Search

植松 幸生 ♥井上 孝史 ♠大和田 勇人 †藤岡 健吾 ♦片岡 良治 ♣Yukio UEMATSU
Takafumi INOUE
Hayato OHWADA

Kengo FUJIOKARyoji KATAOKAindexes which sentences have the morphemes. We change
the index structure from morpheme-based position data
to sentence-based position data to detect adjacency more
eﬃciently. An experiment shows that our method is more
eﬀective in that it oﬀers 3% higher precision than an existing technique while reducing the index size by 15%,and improving the speed by 3%.

1.

はじめに近年 Web や PC のデスクトップにいたるまで大量の電子化された文書が遍在しており，このような大量な文書を対象として高速かつ高精度に検索することは常に求められている．このような要求に対して，形態素解析を用いて検索対象となる文書を分かち書きし，転置インデックスを利用する全文検索エンジンが広く用いられている [1][5]．形態素解析を利用する事で，文字のN-gram を用いて検索する手法 [6] と比較して，検索漏れが起こる可能性はあるが，不必要な単語の部分マッチが起きにくく高精

大規模な電子文書データを対象とする全文検索を少ないリソー
スで，精度良く，高速に行う事は重要である．既存の全文検索で度に検索出来るため，Google， Yahoo!，goo 等多くの商用検索エンジンでもこの方法が取られている．

は検索条件が複合語の場合の連接処理のコストと，その連接処理

形態素解析を用いた転置インデックスでは高精度な検索を実現によって再現率が犠牲になるという問題点があった．そこで，本するために，ある形態素を持つ文書番号だけでなく，その文書番研究ではインデックスに保存される単語の位置情報を文単位で号中での出現位置情報を保存している (転置リスト)．この転置リ構成する文単位転置インデックスを提案する．文単位転置イン

ストは複数の形態素で構成される語 (複合語) が検索条件としてデックスでは検索結果集合の特定を連接ではなく近接 (文中で複与えられた場合，複合語を構成する形態素同士が検索対象中で隣合語を構成する単語が共起すること) に変更する事でコストを低り合っている (連接) かを確認するための処理 (連接処理) に利用減し，複合語がそのまま出現しなくても検索されるため再現率向されるが，その処理コストは大きく，全ての出現位置情報を保存上も期待できる．また，さらなる精度向上のために検索語が複数するためインデックスサイズの肥大化の原因となっている．の際にその単語の出現距離を考慮して提示順序を決定する方法もそこで本研究では高精度な全文検索を低コストに実現するためあわせて提案する．評価実験として本提案の全文検索システムをに，転置リストに保存される単語の位置情報を文単位で構成する実装し，情報検索の標準データセットである IREX IR のデータ文単位転置インデックスを提案する．文単位転置インデックスでに適用，提案手法は既存手法と比較して，インデックスサイズをは，検索結果集合を特定する際に従来の連接ではなく近接 (ある15% 削減，速度を 3% 向上，Precision@N において 3% 程度

文中で複合語を構成する形態素が共起すること) に変更し，複合向上する事を確認した．

語が文書にそのまま出現しなくても，複合語を構成する形態素が文内で共起した文書を検索結果とする．提案手法は再現率を向上

We propose a proximity search method that uses a
sentence-based inverted ﬁle. Past research has attempted
to reduce the adjacency processing cost of compound
word queries for Japanese full text search. Strict adjacency processing may degrade the recall ratio of thesearch results. In our method, adjacency processing isreplaced by checking proximity (co-occurrence of morphemes in sentences of the source documents). To checkproximity, we look up a sentence-based inverted ﬁle that♥

正 会 員 日 本 電 信 電 話 株 式 会 社 ，NTT サ イ バ ー ソリュー ション 研 究 所 / 東 京 理 科 大 学 理 工 学 研 究 科

uematsu.yukio@lab.ntt.co.jp
日 本 電 信 電 話 株 式会社，NTT サイバースペース 研 究 所
fujioka.kengo@lab.ntt.co.jp♠正会員 日本電信電話株式会社，NTT サイバーソリューション研究所 inoue.takafumi@lab.ntt.co.jp♣
正会員 日本電信電話株式会社，NTT サイバーソリューション研究所 kataoka.ryoji@lab.ntt.co.jp†
東京理科大学 理工学部 ohwada@ia.noda.tus.ac.jp

させるが，適合率を下げてしまう可能性があるので，後述する評価実験より精度の変化を明らかにする．
また，検索精度向上の一手法として，複数の単語が検索条件として入力された際に検索対象中の出現位置情報に基づいて提示順序を決定する近接検索 (Proximity Search) [3][4] が近年注目されている．本研究では文単位転置インデックスによって効果的に近接検索を行う方法も合わせて提案し，さらなる精度向上を目指す．

2.

転置インデックスを用いた全文検索♦

1

本章では既存の転置インデックスによる全文検索の処理方法を示し，問題点を明らかにする．全文検索の処理は大きく分けて，検索条件 (クエリ) を含む文書を特定する “Lookup” と検索条件を含む文書の中で検索条件とのスコアを算出する “Ranking” の2 つの処理からなる．このスコアの降順に並べた際に，適合文書

日本データベース学会 Letters Vol.6, No.4

論文

DBSJ Letters Vol.6, No.4

文書ID：133

東京都は日本の首都です．都知事は石原．．．

文書ID：144

東京の都ホテルは中々よいホテルです．

文単位転置インデックス

3.

前述した問題を解決するインデックスの構成方法として文単位
Q(東京都)→ 東京／都の転置インデックス (文単位転置インデックス) を提案する．従転置インデックス

来は複合語で検索された際の Lookup には連接を利用していた

TF POSが，これをある区切られた区間での共起 (近接) に変更し，再現

133

2122 144

31率を向上させる．また，近接を求める事に特化した文単位の転置

都 133

2223 144

13ID
東京45...

リストを利用する事で，複数の単語が検索条件となった場合の出図1170 ...

既存の全文検索システムのおける転置リストの格納方法

Fig. 1 Typical Index Structure of Full Text Search System

現位置を考慮したスコア (近接スコア) の算出を行い精度向上を図るとともに，高速に近接検索を実現する．

3.1

文単位転置リスト

本研究では転置リストの出現位置情報をある区切られた区間毎(本提案では文単位) に集約して保持し，近接に特化したインデッを検索結果の上位に提示する事が求められる．

クスを構成する．この区切られた区間を文単位で保持する転置リ

2.1

既存の全文検索エンジンにおける複合語処理

ストの事を本研究では文単位転置リストと呼ぶ．既存手法では形既存の全文検索エンジンの具体例として， goo 画像検索等で用態素 t の文書 d における位置情報は下記のようなデータ構造で保いられている Infobee/Evangelist[5] を例にあげ，転置インデックスによる “Lookup” と “Ranking” 処理の流れを説明する．
まず入力としてクエリ集合 Q = {q1, q2 . . . qn } が与えられ存されていた．

inverted list(t, d) =< n; pos1 , pos2 , . . . posn >る．この各クエリを形態素解析し，形態素 t に分割する．例え

ここで，n は形態素 t の文書 d 中の TF，posn は出現位置でいずば q1=” 東京都” だった場合，q1 = {t1 = 東京，t2 = 都 } とれも整数で保存される．例えば例文として下記 (dex ) が与えられ一般的に分割される．次にこの形態素 t をキーとして転置インたとする．

デックスから転置リストを獲得する．形態素をキーとして獲得す

東京 駅 の 改札 口 の 近く の 土産 屋 では 東京 土産 を 売る方法としては，PATRICIA 木を利用する．この PATRICIAって いる． 東京 に 行った とき は そこ で お 土産 を 買う ．

木のリーフ部に保持される転置リストは図 1 のような構造で保転置リスト inverted list( 東京 , dex ) 及び inverted list( の存されている．図中の ID はドキュメントに付与された文書 IDで TF(Term Frequency) が文書 ID における形態素の出現頻度，POS がその形態素の出現位置情報である．例えば図中の “東京”に対応する転置リストの先頭は文書 ID133 で，その文書の “東京” という形態素の出現頻度は 2 で出現位置は 1 と 22 番目である事を示している．よって，“東京都” という複合語検索は， t1と t2 の転置リストを参照し， t1 の次に t2 が出現する文書 (文書ID133 の 2 番目か 23 番目の形態素が “都” であること) を特定, dex ) は下記のように表現される．
inverted list( 東京 , dex ) =< 3; 1, 12, 18 >inverted list( の , dex ) =< 2; 3, 6 >ここで，例文 dex における “東京” という形態素の TF が 3 で，その出現位置はそれぞれ 1，12，18 形態素目であることを示す．
それに対し，本研究では正確な出現位置を保持するのではなく，する事で実現される．この処理をクエリ集合に含まれる形態素のその形態素が何文目に出現したかを保存する．提案する文単位転いずれかを持つ全ての文書集合に対して行うため，大きな処理コ置リストは下記のようなデータ構造を持つ．

ストがかかる．
また，Ranking 方式としては文書とクエリ間のスコアを算出するポピュラーな手法として，TF·IDF や BM25[2] がある．
Infobee/Evangelist では選択可能であるが，その中でも精度が高いと言われる BM25 を本稿では利用する．

2.2

既存手法の問題点

転置リストから “Lookup”，“Ranking” 処理を行う方法について述べた．しかしながら，これらの方法は以下の問題点がある．

1. 複合語に対して連接処理を行う事により，再現率を犠牲にしてしまう．また，その処理コストは高い．

2. 形態素の位置情報が多くのリソースを利用してしまう．
3. 複数の検索条件が入力となった場合，検索条件の出現位置を考慮する事で精度が上がる事が報告されているが，転置リス
トから効果的に求める方法は明らかにされていない．

2

sent inverted list(t, d) =< m; spos1 , spos2 , . . . sposm >sposm は，形態素 t が文書 d のどの文に出現したかを保持し，形態素 t が文のどの位置に出現したかは保持しない．例えばある文に 2 回同じ形態素 t が出現したしても，1 つに集約される．先ほどの dex を例に “東京” 及び “の” における形態素の文単位転置リストは下記のように表現される．

sent inverted list( 東京 , dex ) =< 2; 1, 2 >sent inverted list( の , dex ) =< 1; 1 >上記において “東京” は 1 文目と 2 文目に出現する事を示している．また，“の” は同一文内で 2 度出現しているため，集約されている．図 2 にその概念図を示す．図 2 上部の文書の形態素列に対して，各単位の転置インデックスがどのような情報を保持す日本データベース学会 Letters Vol.6, No.4

論文

DBSJ Letters Vol.6, No.4
東京 都 は 狭い

転置インデックス
文単位転置インデックス
文書単位転置インデックス

1234． でも ， 人 は 多い
567

1

89wd (q) =102|N | − df (q) + 0.5(k1 + 1)co occ(Q, d)∗ log()(2)
K + co occ(Q, d)df (q) + 0.5dl(d)K = k1 (1 − b + b)(3)avdl

上式で pscore が単語が近接した際のスコア (近接スコア) であ
位置情報無しデックスでは，“東京”,“都”“は”,“狭い”,“．” がすべて 1 である．

る．BM 25(Q, d) は BM25 で得られた Q と d のスコアで，式(1) の右辺第 2 項が近接した際に加算するスコアである．本スコ
アは BM25 における tf (q, d) を co occ(Q, d) に変更した物である．co occ(Q, d) は Q に含まれる全てのクエリ q の d 中での文内共起回数に相当する．α は近接スコアをどの程度効かせるかの係数で，今回は全ての文で Q が共起した場合に，pscore(Q, d)が元の BM 25(Q, d) の最大 1.5 倍のスコアが与えられるように
α = 0.5 とした．また，BM25 の係数 b, k1 は経験的に k1 = 1.2,b = 0.75 をそれぞれ利用した．

3.24.

図 2 文単位転置インデックス概念図

Fig. 2 Basic Concept of Sentence-based Position Dataるのかを示している．転置インデックスでは，各形態素に対してユニークな位置情報を保持しているのに対して，文単位転置イン

文単位転置インデックスの効果

文単位転置インデックスは再現率向上，速度向上，リソース削評価実験

提案手法の有効性を検証するために評価実験を行った．実験減の 3 つの効果がある．再現率向上に関しては，提案手法は複合データとしては情報検索の標準データセットである IREX IR語を構成する形態素がある文内で共起しているだけで検索結果とのデータを用いた． IREX IR は毎日新聞 2 年分の 866MB，するため，連接処理を行った場合と比較して多くの検索結果を返す事が出来る．しかしながら，ユーザの入力した表記とは異なる

212,433 記事で構成され，総クエリ数は 30 である．このデータを用いて，精度，速度，インデックスサイズの 3 つの観点で評価文書を検索結果とするため，適合率を低下させてしまう可能性もを行った．

ある．例えば “東京都” という文字列を含む文書を検索条件としまず，精度評価に関しては与えられている 30 個のクエリから，“の” 等の助詞を削除し複数の単語の OR 検索とした． 評価対象
としては，下記の 3 つを比較した．て入力しているにも関わらず，“東京の都 (みやこ) ホテル” という文字列を含む文書が検索されてしまう場合がある．この点に関しては後述する評価実験によって，既存の連接処理を持つ転置インデックスとどちらが有利かを明らかにする．
また，複合語検索の際の速度向上，及びインデックスサイズを削減出来る．複合語が検索条件の場合，その複合語を構成する形態素が文内に共起する事を特定する際に，形態素の出現位置を加1. 形態素単位インデックス (全ての位置情報を保持する転置インデックス)
2. 文単位転置インデックス
3. 文単位転置インデックスかつ，複数語の際の近接スコアあり減算せずに求める事が出来る．リソース面では，一般的に転置リ文単位の切り方は様々な手法が存在するが，本実験では毎日新ストの位置情報は多くのリソースを使用するため圧縮した状態で聞データの句点表記である “。” と全角スペースを文の単位と保持される．提案する文単位転置インデックスは転置インデックして利用した．評価指標としては，IREX IR で公開されていスの保存すべき数値を小さく抑える事が出来る．例えば，図 2 でる trec eval を用いて precision@N を使用した．precision@N

は 1 から 10 までの数値を各形態素が保存しなければいけないのは検索結果上位 N 件での適合率を示す．本評価実験では N =5, 10, 15, 20, 30, 100, 200 件の際の適合率を測定した．
速度は与えられているクエリセット (30 クエリ) を 100 回ずつ検索し，それを 5 回試行し，平均速度を測定した．また，インデックスサイズに関しては転置リストの大きさ (位置情報のみ)に対し，文単位転置インデックスでは 1 と 2 を各形態素が保存すれば良い．よって，位置情報を小さくする事が出来るため，転置リストをより効果的に圧縮する事が期待出来る．

3.3

近接情報を考慮したスコア算出方法

前章までで文単位転置インデックスを利用して Lookup する方を同マシン上で測定した．

法について述べた．本章ではさらに近接情報を考慮した Ranking

表 1 は precision@N の結果で列の項目が検索結果数，行の項方法について述べる．複合語の連接処理を文内共起に変更した場目が比較手法である．太字の数値が最も高い値で，検索結果 30合のスコアは BM25 をそのまま利用する．複数の単語が検索条件までは文単位転置インデックス＋近接が最も良い結果を示して件となった場合は，個々の単語のスコアは BM25 によって算出いる．また，形態素単位と文単位転置インデックスのみを比較すするが，Q に含まれる q 全てが近接した時にさらにスコアを下ると，検索結果の上位においても文単位の方が精度が上回ってい記のように加算する．

る事が分かる．

pscore(Q, d) = BM 25(Q, d) + α ∗q∈Q3

表 2 に検索速度評価結果を示す．太字の数値が 5 回の平均速度

wd (q)(1)

で，括弧内は 5 回測定した内訳である．30 秒間で 3000 回の検索を実行しているので， 1 クエリ当り 10msec 程度の速度で検索し日本データベース学会 Letters Vol.6, No.4

論文

DBSJ Letters Vol.6, No.4
表1IREX IR データにおける精度評価 Precision@N (N=5 から 200)
Table 1 Comparison of Precision@N (N= 5 to 200)

N
形態素単位
文単位
文単位 + 近接

510152030100200

0.55330.55330.58670.49330.50670.54670.4756
0.47330.51780.44000.45670.50000.39780.41330.44780.21800.25000.24600.13230.15920.1455

表 2 IREX IR を対象とした平均検索速度

Table 2 Comparison of Average Retrieval Time(sec)
既存手法
提案手法

30.48 (31.507, 29.940, 30.530, 30.164, 30.234)
29.45 (29.381, 29.758, 29.630, 28.964, 29.537)

表3

IREX IR インデックス時のサイズ

Table 3 Comparison of Index Size(kbytes)
既存手法
提案手法

242,090
213,647ている．結果を見ても分かる通り，既存手法と比較して提案手法[文献][1] Mike Cafarella and Doug Cutting. Building nutch: Open
source search. Queue, Vol. 2, No. 2, pp. 54–61, 2004.
[2] Stephen E. Robertson, Steve Walker, Micheline HancockBeaulieu, Aarron Gull, and Marianna Lau. Okapi at TREC3.
In Text REtrieval Conference, pp. 21–30, 1992.
[3] Tao Tao and ChengXiang Zhai. An exploration of proximity
measures in information retrieval. In SIGIR ’07: Proceedingsof the 30th annual international ACM SIGIR conference on
Research and development in information retrieval, pp. 295–302, New York, NY, USA, 2007. ACM Press.
[4] Chi Tian, Taro Tezuka, Satoshi Oyama, Keishi Tajima, andKatsumi Tanaka. Improving web retrieval precision based on
semantic relationships and proximity of query keywords. InDEXA, pp. 54–63, 2006.
[5] 竹野浩, 井上孝史. 分散型高速情報収集/全文 検 索シ ステ ム infobee/evangelist. NTT R&D, Vol. 52, No. 2, pp. 78–84, 2003.
[6] 平林幹雄, 江渡浩一郎. N.m-gram : ハッシュ値付き n-gram 法による転置インデックスの実現 (言語処理). 電子情報通信学会技術研究報
告. DE, データ工学, Vol. 106, No. 149, pp. 167–172, 2006.の方が平均して 3% 程度の速度向上が見られる．また，測定した

植松 幸生 Yukio UEMATSU

すべて結果において提案手法が上回っている事から検索速度向上

NTT サイバーソリューション研究所/東京理科大学社会人博士後期課程
所属．2003 年 東京理科大学大学院・理工学研究科修士課程修了．同年，日本電信電話株式会社入社．情報検索の研究開発に従事．日本データベース学会正会員．人工知能学会学生会員．に効果がある事が示された．
表 3 に IREX IR データをインデックスした際のインデックスサイズを示す．既存手法では元の文書データに対して 27% 程度になっている．提案手法では既存手法からさらに 15% 程度のサイズ低減が見られた．

5.

まとめと今後の課題

実験結果から文単位で位置情報を持つ転置インデックスを利用する事で，従来手法である全ての形態素の位置情報を持つ場合と比較して精度が高い事が示された．これは厳密な連接を行わず文単位での共起を利用する事で，検索結果の精度を下げずに，再現率を上げる事が出来たからである．精度の上昇はわずかだが，インデックスサイズ 15% の低減，速度 3% の向上が見られたため有効な手法であると言える．また複数語のクエリが入力になった
場合，それらの語が同じ文に出現する事を類似度のスコアに加算することによって，さらに検索精度が上がる事を確認した．今後の課題としては文抽出の問題がある．本論文では新聞コーパスを用いて実験を行ったため，文抽出のミスによる精度の低下がおきにくかったが，Web の文書を対象とした際の文抽出方法等議論する必要がある．具体的には NTCIR 及び TREC データを利用して実験を行い明らかにしたい．

4藤岡 健吾 Kengo FUJIOKA

NTT サイバースペース研究所 研究主任．1995 年東京大学大学院理学部物理学科修士課程修了．同年，日本電信電話株式会社入社．DB,WEBにおける検索技術の研究開発に従事．

井上 孝史 Takafumi INOUE

NTT サイバーソリューション研究所 主任研究員．1990 年京都大学大学
院工学研究科電気工学第二専攻修士課程修了． 同年，日本電信電話株式会社入社．主にテキスト処理， 情報検索の研究開発に従事． 日本データベース学会正会員．

片岡 良治 Ryoji KATAOKA

NTT サイバーソリューション研究所 主幹研究員．1987 年千葉大学大学
院電子工学先行修士課程修了．同年，日本電信電話株式会社入社． トランザクションの並行処理制御方式の研究，マルチメディア情報システムの研究，ポータルサービスシステムの研究開発に従事．情報処理学会会員．日本データベース学会正会員．

大和田 勇人 Hayato OHWADA

東京理科大学理工学部経営工学科教授． 1988 年東京理科大学大学院理工学研究科経営工学専攻博士後期課程修了． 同年，東京理科大学理工学部経営工学科助手． 1999 年同講師． 2001 年同助教授． 2005 年同教授，現在に至る．工学博士．主にデータマイニング，機械学習，帰納論理プロ
グラミングに興味を持つ．人工知能学会正会員，日本ソフトウェア科学会理事．

日本データベース学会 Letters Vol.6, No.4