(57)【要約】【課題】  情報検索において、連接処理の誤検出が起こり得るもののインデックスサイズを削減する。【解決手段】  本発明は、文書データベースから文書を読み込み、該文書の文字列を単語毎に分割し、各単語が先頭から数えて何番目に位置するかを示す位置情報の数を、予め設定された固定長以下の数値で集約し、位置情報の列を１つの転置リストにマッピングし、その転置リストを転置インデックス記憶手段に追加する。  また、位置情報の数を集約する際に、固定長の代わりに、任意に指定された区切り文字を用いて集約することで、連接していない場合でも連接しているかのように動作することを防ぐ。【選択図】  図１
2010262379.tif 000002
【特許請求の範囲】
【請求項１】
文書データベースに蓄積された文書群からインデックスを作成し、転置インデックスを格納する検索インデックス記憶手段に格納し、作成されたインデックスから検索結果として返却する検索結果集合を特定する情報検索方法であって、
前記文書データベースから文書を読み込み、該文書の文字列を単語毎に分割し、各単語が先頭から数えて何番目に位置するかを示す位置情報の数を、予め設定された固定長以下の数値で集約し、第１の記憶手段に格納する位置情報集約ステップと、
前記第１の記憶手段から前記位置情報集約ステップで得られた位置情報の列を取得して第２の記憶手段の１つの転置リストにマッピングするマッピングステップと、
前記マッピングステップでマッピングされた前記転置リストを前記第２の記憶手段から取得して、前記転置インデックス記憶手段に追加する転置インデックス追加ステップと、
を行うことを特徴とする情報検索方法。
【請求項２】
前記位置情報集約ステップにおいて、
前記位置情報を集約する際に、前記固定長を用いる代わりに、前記位置情報の数を任意に指定された区切り文字を用いて集約する
請求項１記載の情報検索方法。
【請求項３】
文書データベースに蓄積された文書群からインデックスを作成し、転置インデックスを格納する検索インデックス記憶手段に格納するインデックス作成手段と、作成されたインデックスから検索結果として返却する検索結果集合を特定する検索結果集合特定手段と、を有する情報検索装置であって、
前記インデックス作成手段は、
前記文書データベースから文書を読み込み、該文書の文字列を単語毎に分割する単語分割手段と、
分割された各単語が先頭から数えて何番目に位置するかを示す位置情報の数を、予め設定された固定長以下の数値で集約し、第１の記憶手段に格納する位置情報集約手段と、
前記第１の記憶手段から前記位置情報集約ステップで得られた位置情報の列を取得して第２の記憶手段の１つの転置リストにマッピングする位置情報マッピング手段と、
前記位置情報マッピング手段でマッピングされた前記転置リストを前記第２の記憶手段から取得して前記転置インデックス記憶手段に追加する転置インデックス追加手段と、
を有することを特徴とする情報検索装置。
【請求項４】
前記位置情報集約手段は、
前記位置情報を集約する際に、前記固定長を用いる代わりに、前記位置情報の数を任意に指定された区切り文字を用いて集約する手段を含む
請求項３記載の情報検索装置。
【請求項５】
請求項３または４記載の情報検索装置を構成する各手段としてコンピュータを機能させるための情報検索プログラム。
【請求項６】
請求項５記載の情報検索プログラムを格納したことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報検索方法及び装置及びプログラム及びコンピュータ読み取り可能な記録媒体に係り、特に、蓄積された文書群の文書内に出現する単語の位置情報を利用してフレーズ検索や複合語の検索を高速かつ省メモリで行う検索インデックスを作成するための情報検索方法及び装置及びプログラム及びコンピュータ読み取り可能な記録媒体に関する。
【背景技術】
【０００２】
図１０は、一般的な情報検索装置の構成を示す。
【０００３】
同図に示す情報検索装置は、インデックスを作成し、検索インデックス記憶部３に格納するインデックス作成部１、検索インデックス記憶部３の作成されたインデックスを参照して検索結果集合を特定し、検索結果を返却する検索結果集合特定部２からなる。インデクス作成部１０は、形態素解析部１１、転置リスト作成部１２、転置インデクス追加部１３を有する。
【０００４】
ここで、本発明の対象であるインデックス作成部１に着目すると、フレーズや複合語を効率的に検索するために、一般的には転置インデックスに単語の位置情報を保持する。この位置情報のリストを「転置リスト」と呼ぶ。最もシンプルな転置リストの保持方法として、単語の位置情報を図１１のように保存する転置リストがある（例えば、非特許文献１参照）。この方式は、単語word_1が文書ＩＤ１に４回出現し、その位置情報が［１，３，５４，５８］であることを示す。当該方式のインデックスでは単語の位置情報を文書の先頭から数えて何番目に出現するかを保持している。この位置情報は検索語が複合語やフレーズの時に利用される。例えば、"東京都"というフレーズで検索した場合、word_1が"東京"、word_2が"都"だったとすると、ＩＤ１の文書は１番目の単語がword_1で、２番目の単語がword_2なので、"東京都"がフレーズとして出現したことがわかる。一方、ＩＤ１４４の文書は、word_1とword_2が隣り合って出現していないので、"東京"と"都"という単語が文書内で共起しているものの、フレーズでは出現していないことがわかる。このフレーズで出現しているかどうかチェックする処理を「連接処理」と呼ぶ。
【０００５】
具体的に、下記のような文書が入力された場合を例に、転置リストの作成方法を説明する。
【０００６】
例文：
ＩＤ＝１：『東京で東京都知事選挙が行われた。…。東京出身で東京都知事に立候補したのは３人で、…』
上記の例文において、東京の転置リストを作成する。図１２に、転置インデックス作成の詳細なフローを示す。
【０００７】
まず、インデックス作成部１の形態素解析部１１は、文字列を単語に分割する（ステップ１０）。
【０００８】
分割方法としては既存技術である「mecab(http://mecab.sourceforege.net/)」や「chasen(http://chasen.naist.jp/hiki/ChaSen/)」等の形態素解析を用いる。下記が上記の例文を形態素解析し、単語毎に分割した結果である。
【０００９】
例文：
ＩＤ＝１：東京／で／東京／都／知事／選挙／が／行わ／れ／た／。／…／。／東京／出身／で／東京／都／知事／に／立候補／した／の／は／３人／で／…
上記のスラッシュで区切られた区間が単語である。
【００１０】
次に、転置リスト作成部１２がｉ＝０と空の転置リストを作成する（ステップ１１）。
【００１１】
転置リストとは転置インデックスの各要素である。
【００１２】
ｉ番目の単語word(i)が行末（文書の末尾）かどうかを判定する（ステップ１２）。末尾でない場合は、word(i)に該当する転置リストにｉを追加する（ステップ１３）。この時のｉの値は位置情報を表す。例えば、上記文書が入力となった場合、word(1)は"東京"であり、行末ではないので、word(i)の転置リストに位置情報ｉを追加する。
【００１３】
次にｉを１つ進め（ステップ１４）、ステップ１２から繰り返す。
【００１４】
ステップ１２において、行末まで達した場合はステップ１５で全体の転置インデックスに作成した転置リストを検索インデックス記憶部３００に追加する。具体的には、上記の例文が文書番号１で、word_1が"東京"であったとすると、"東京"は、１，３，６５，６９番目の形態素として出現しているので、word_1の先頭の転置リストは図１１のようになっているのがわかる。これを全ての文書で繰り返すことで、検索の転置インデックスが作成される。
【００１５】
以上示したように、従来技術の転置インデックスは位置情報をその文書に出現する回数だけ保存されるため、インデックスサイズの肥大化を招く。
【先行技術文献】
【非特許文献】
【００１６】
【非特許文献１】Witten et. al., Managing Gigabytes, Morgan Kaufmann publishers,1999.
【発明の概要】
【発明が解決しようとする課題】
【００１７】
しかしながら、上記従来技術のインデックス形式の場合、連接処理のために保存される位置情報やメモリの使用量が大きく、また、連接処理を行う場合に文書内に出現する全ての単語について調べる必要があり、速度が遅いという課題がある。
【００１８】
本発明は、上記の点に鑑みなされたもので、連接処理の誤検出が起こり得るもののインデックスサイズを削減することが可能な情報検索方法及び装置及びプログラム及びコンピュータ読み取り可能な記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１９】
図１は、本発明の原理を説明するための図である。
【００２０】
本発明（請求項１）は、文書データベースに蓄積された文書群からインデックスを作成し、転置インデックスを格納する検索インデックス記憶手段に格納し、作成されたインデックスから検索結果として返却する検索結果集合を特定する情報検索方法であって、
文書データベースから文書を読み込み、該文書の文字列を単語毎に分割し（ステップ１）、各単語が先頭から数えて何番目に位置するかを示す位置情報の数を、予め設定された固定長以下の数値で集約し、第１の記憶手段に格納する（ステップ２）位置情報集約ステップと、
第１の記憶手段から位置情報集約ステップで得られた位置情報の列を取得して、第２の記憶手段の１つの転置リストにマッピングするマッピングステップ（ステップ３）と、
第２の記憶手段からマッピングステップでマッピングされた転置リストを取得して、転置インデックス記憶手段に追加する転置インデックス追加ステップ（ステップ４）と、を行う。
【００２１】
また、本発明（請求項２）は、位置情報集約ステップ（ステップ２）において、
位置情報を集約する際に、固定長を用いる代わりに、位置情報の数を任意に指定された区切り文字を用いて集約する。
【００２２】
図２は、本発明の原理構成図である。
【００２３】
本発明（請求項３）は、文書データベース３０に蓄積された文書群からインデックスを作成し、転置インデックスを格納する検索インデックス記憶手段３００に格納するインデックス作成手段００と、作成されたインデックスから検索結果として返却する検索結果集合を特定する検索結果集合特定手段２００と、を有する情報検索装置であって、
インデックス作成手段１００は、
文書データベース３０から文書を読み込み、該文書の文字列を単語毎に分割する単語分割手段１１０と、
分割された各単語が先頭から数えて何番目に位置するかを示す位置情報の数を、予め設定された固定長以下の数値で集約し、第１の記憶手段に格納する位置情報集約手段１３０と、
第１の記憶手段から位置情報集約手段１３０で得られた位置情報の列を取得して、第２の記憶手段の１つの転置リストにマッピングする位置情報マッピング手段１４０と、
第２の記憶手段から位置情報マッピング手段１４０でマッピングされた転置リストを取得して、転置インデックス記憶手段３００に追加する転置インデックス追加手段１５０と、を有する。
【００２４】
また、本発明（請求項４）は、位置情報を集約する際に、固定長を用いる代わりに、位置情報の数を任意に指定された区切り文字を用いて集約する手段を含む位置情報集約手段１３０を有する。
【００２５】
本発明（請求項５）は、請求項３または４記載の情報検索装置を構成する各手段としてコンピュータを機能させるための情報検索プログラムである。
【００２６】
本発明（請求項６）は、請求項５記載の情報検索プログラムを格納したコンピュータ読み取り可能な記録媒体である。
【発明の効果】
【００２７】
上述のように本発明では、各単語に保存される位置情報をセグメントに分割し、固定長を用いてそのセグメントの先頭から数えた数に位置情報を集約することで、連接処理の誤検出が起こり得るもののインデックスサイズを大きく削減できる。
【００２８】
また、区切り文字を用いることで、連接していない場合でも連接しているかのように動作することを防ぐことができる。
【図面の簡単な説明】
【００２９】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の第１の実施の形態における情報処理検索装置の構成図である。
【図４】本発明の第１の実施の形態における転置インデックスの作成例である。
【図５】本発明の第１の実施の形態における転置インデックスの構造例である。
【図６】本発明の第１の実施の形態における転置インデックス作成のフローチャートである。
【図７】本発明の第２の実施の形態における情報処理装置の構成図である。
【図８】本発明の第２の実施の形態における区切り文字を利用した転置インデックスの構造例である。
【図９】本発明の第２の実施の形態における転置インデックス作成のフローチャートである。
【図１０】一般的な情報検索装置の構成図である。
【図１１】従来技術による転置インデックスの構造例である。
【図１２】従来技術による転置インデックス作成のフローチャートである。
【発明を実施するための形態】
【００３０】
以下、図面と共に本発明の実施の形態を説明する。
【００３１】
図３は、本発明の一実施の形態における情報処理装置の構成を示す。
【００３２】
本発明の情報処理装置は、図１０に示した従来の情報検索装置と同様にインデクス作成部１００と検索結果集合特定部２００、検索インデックス記憶部３００から構成されるが、インデックス作成部１００の構成が異なる。
【００３３】
本発明のインデックス作成部１００は、外部の文書ＤＢ３０から文書群を読み込んで、文書毎に単語に分割する形態素解析部１１０、各単語毎に転置インデックスと単語の位置情報からなる転置リストを作成し、メモリ（図示せず）に格納する転置リスト作成部１２０、メモリ（図示せず）に格納されている各単語の位置情報の数を集約し、メモリ（図示せず）に格納する位置情報集約部１３０、メモリ（図示せず）から位置情報を取得して配列にマッピングする位置マッピング部１４０、マッピングされた配列を転置インデックス記憶部３００に追加書き込みする転置インデックス追加部１５０を有する。つまり、図１０の構成に、文書に含まれる位置情報の数を集約する位置情報集約部１３０と、その位置情報を配列にマッピングする位置情報マッピング部１４０を付加した構成である。
【００３４】
前述の従来技術の転置インデックスは、位置情報をその文書に出現する回数だけ保存されるため、インデックスサイズが大きくなるが、本発明では、位置情報の絶対値を固定長Ｌに圧縮する。具体的には固定長Ｌを予め設定し、その固定長内にインデックスが収まるようにインデックスを集約させることで実現する。
【００３５】
図４に、図１１で示した転置インデックスのword_1を固定長Ｌ＝６４で集約した例を示す。まず、従来技術では、文書ＩＤ＝１について、検索インデックス記憶部３に位置情報が「１，３，６５，６９」と保存されているが、本発明では、これを６４以下の数値に収めるために、位置情報集約部１３０において、位置情報の数値を「６４」の剰余に変換し、固定長Ｌ以下の数値で集約する。例えば、「６５」は「６４」で剰余をとると「１」となる。よって、「１，３，１，４」という列が得られる。これを位置情報マッピング部１４０で１つの転置リストにマッピングして本発明の転置インデックスである「１，３，４」という位置情報を最終的に得る。
【００３６】
図５に本発明を利用して全ての数値が「６４」以下になった転置インデックスの例を示す。同図中の全ての位置情報の値が「６４」以下になっている。これを利用して従来技術と同様の連接処理をする場合、実際には連接処理を行っても連接していないケースが起こる可能性があるが、インデックスサイズと計算量を大きく削減することができるというメリットがある。
【００３７】
図６は、本発明の一実施の形態におけるインデックスの作成のフローチャートである。
【００３８】
ステップ２０１）  形態素解析部１１０で文書ＤＢ３０から文書を読み込み、当該文書の文字列を単語毎に分割する。形態素解析の方法は従来技術と同様である。
【００３９】
ステップ２０２）  転置リスト作成部１２０は、position=0、ｉ＝０，１をセットし、メモリ（図示せず）上に空のインデックスを作成する。固定長Ｌは任意の値を与えることが可能であるが、値が小さければ小さいほどインデックスサイズが小さくなる代わりに、連接処理の誤検出も増える。
【００４０】
ステップ２０３）  word_(i)が行末であるかどうかをチェックし、行末でない場合はステップ２０４に移行し、行末の場合はステップ２０９に移行する。
【００４１】
ステップ２０４）  位置情報集約部１３０は、ｉが固定長Ｌより大きいかを確認し、大きい場合はステップ２０６に移行し、小さい場合はステップ２０５に移行する。
【００４２】
ステップ２０５）  位置情報集約部１３０は、固定長Ｌより小さい場合は、positionを１つ進め、ステップ２０７に移行する。
【００４３】
ステップ２０６）  位置情報集約部１３０は、positionを０に戻し、ステップ２０７に移行する。
【００４４】
ステップ２０７）  転置リスト作成部１２０は、メモリ（図示せず）上のword(i)の転置リストにpositionを追加する。
【００４５】
ステップ２０８）  ｉを１進め、ステップ２０３に戻る。
【００４６】
ステップ２０９）  ステップ２０３において行末である場合は、位置情報マッピング部１３０はメモリ（図示せず）から転置リストを読み込み、位置情報のマッピングを行う。マッピングは同じ位置情報をひとつにまとめることを指す。例えば、図４の例の場合は、文書ＩＤ＝１の位置情報［１，３，６５，６９］（図４（ａ））を固定長Ｌを利用して集約すると、［１，３，１，４］（図４（ｂ））となり、同じ位置情報である［ＩＤ＝１］をマッピングすると［１，３，４］（図４（ｃ））となる。このようにマッピングされた位置情報をメモリ（図示せず）に格納する。
【００４７】
ステップ２１０）  転置インデックス追加部１５０は、メモリ（図示せず）からマッピングされた転置リストを読み込み、全体の転置インデックスに当該転置リストを追加し、検索インデックス記憶部３００に格納し、インデックス作成部１００側の処理を終了する。
【００４８】
これにより、固定長Ｌ以下の位置情報で構成された転置インデックスが作成される。
【００４９】
［第２の実施の形態］
前述した位置情報の集約方法はＬを固定長で限定するため、ある文を区切ってしまう可能性がある。例文１において、固定長「４」で区切った場合は、下記のようになる。
【００５０】
例文（ＩＤ＝１）：／東京／で／東京／都
／知事／選挙／が／行わ
／れ／た／。／…／
よって、「都知事」と検索された場合、誤検出だけでなく検出漏れが起きることがある。そこで、本実施の形態では、第１の実施の形態で用いた固定長ではなく、区切り文字を利用したインデックス作成方法を示す。
【００５１】
図７は、本発明の第２の実施の形態における情報検索装置の構成を示す。
【００５２】
同図に示す情報検索装置は、図３の位置情報集約部１３０の代わりに、区切り文字を用いて位置情報を集約する区切り文字位置情報集約部２３０を設けた構成である。
【００５３】
区切り文字は任意に指定できるが、"。"を区切り文字にした場合は下記のようになる。
【００５４】
例文（ＩＤ＝１）：
／東京／で／東京／都／知事／選挙／が／行わ／れ／た／。
【００５５】
…
／東京／出身／で／東京／都／知事／に／立候補／した／の／は／３人／で／…
これにより誤検出は起きる可能性があるものの、検出漏れを防ぐことができる。
【００５６】
図８に区切り文字を利用して位置情報を集約した例を示す。図４との違いは６４以下の数値であっても、文の区切れがある場合は位置情報が集約されている点である。例えば、文書ＩＤ＝１７０は、従来技術の転置インデックスにおいては、［２，６，８，１０］であるのに対し、６番目の単語が文の区切りであったため、［２，６，２，６］と集約し、最終的に［２，６］にマッピングされている。このように文頭には同じ文字列が出現する可能性が高いため、こうしたマッピングはインデックスサイズ削減に貢献する可能性がある。
【００５７】
図９は、本発明の第２の実施の形態における転置インデックス作成のフローチャートである。
【００５８】
以下では図６との違いのみを詳細に説明する。
【００５９】
ステップ３０２）  区切り文字位置情報集約部２３０は、区切り文字をセットする。例えば、"。"や"．"などをセットすることができる。また、区切り文字を正規表現などのパターンで与えることも考えられる。
【００６０】
ステップ３０４）  区切り文字位置情報集約部２３０は、word(i)が前述した区切り文字であるかどうかを判断する。これが区切り文字である場合はステップ３０６に移行し、区切り文字でない場合はステップ３０５に移行する。
【００６１】
ステップ３０５）  区切り文字でない場合はpositionを１つ進め、ステップ３０７に移行する。
【００６２】
ステップ３０６）  区切り文字である場合はpositionを０としてステップ３０７に移行する。
【００６３】
ステップ３０７）  転置リスト作成部１２０は、メモリ（図示せず）上のword(i)の転置リストにpositionを追加する。
【００６４】
上記以外の処理は図６の動作と同様である。
【００６５】
このような手順により区切り文字を利用した転置リストを作成することができる。
【００６６】
なお、上記の情報処理装置の構成要素の各動作をプログラムとして構築し、情報処理装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００６７】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００６８】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００６９】
３０  文書データベース（ＤＢ）
１００  インデックス作成手段、インデックス作成部
１１０  単語分割手段、単語分割部
１２０  転置リスト作成部
１３０  位置情報集約手段、位置情報集約部
１４０  位置情報マッピング手段、位置情報マッピング部
１５０  転置インデックス追加手段、転置インデックス追加部
２００  検索結果集合特定手段、検索結果集合特定部
２３０  区切り文字位置情報集約部
３００  転置インデックス記憶手段、転置インデックス記憶部
【図１】
2010262379.tif 000003
【図２】
2010262379.tif 000004
【図３】
2010262379.tif 000005
【図４】
2010262379.tif 000006
【図５】
2010262379.tif 000007
【図６】
2010262379.tif 000008
【図７】
2010262379.tif 000009
【図８】
2010262379.tif 000010
【図９】
2010262379.tif 000011
【図１０】
2010262379.tif 000012
【図１１】
2010262379.tif 000013
【図１２】
2010262379.tif 000014