LoginSignup
11
10

More than 5 years have passed since last update.

@posikiku(Hiroaki Kikuchi)

Apache Luceneで学ぶ情報検索の基礎 -- Boolean Retrieval

Last updated at Posted at 2016-08-30

検索エンジンを簡単に構築できるソフトウェアが利用可能になったことで、検索エンジンをブラックボックスとして利用するだけで十分なことも多くなりました。しかし、シンプルな検索エンジンにとどまらない、より高度で先進的な情報獲得システムを発明しようと思った時、検索エンジンの核をなすコンセプトを理解することには大きな価値がありますが、このような基礎的な部分の学習に長大な時間を費やすことも難しいのが現実だと思います。この記事(から始まるであろう一連の記事群)は、短時間で検索アプリケーションの全体像を理解するための、必要最低限の情報検索についての学術的な知識をコードなどの実例を用いて説明することを目的としています。

はじめに

主に以下に述べる２つのリソースに基づきつつ筆者の経験を基に、情報検索についてのエッセンシャルな情報をできるだけ短時間に学べるようにまとめることを目的にしたいと考えています。

Introduction to Information Retrieval

情報検索について学び始めるほとんどの人が参照する教科書的な情報源として有名なスタンフォード大学のInformation Retrieval (IR, 情報検索)に関する講義です。授業の講義資料Introduction to Information Retrievalはインターネット上でダウンロード可能です。また、日本語訳の書籍「情報検索の基礎」も出版されています。

Apache Lucene Core

「検索エンジン」という概念が確立して技術もコモディティ化するのに伴って、現在ではオープンソースでもApache Solrや、Elasticsearchといったソフトウェアをインストールするだけで簡単に検索エンジンシステムが構築できるようになりました。それに対して、Apache Lucene Core (以下、単純にLucene)は、「情報検索ライブラリ」です。Apache SolrやElasticsearchといった「検索エンジン」の内部で核となる検索のためのデータ構造とそのアクセスのためのコンポーネントとして使われています。この一連の記事が続く限り、できるだけLuceneによる具体的なコードを使用して情報検索の仕組みを説明しようと考えています。この記事では、2016年8月の時点での最新版であるLucene 6.2を使用しています。LuceneはJARファイルとして提供されているので、ダウンロードしてJavaアプリケーションのクラスパスに加えることでAPIが呼出せます。またMavenリポジトリも利用可能です。

Boolean Retrieval (Boolean検索、論理検索)

今回は、最も単純な情報検索の手法とも言えるBoolean Retrievalについて述べたいと思います。この手法は、あるTerm(用語)が、文書に含まれているか否かの2値で検索がマッチするかどうかを判定します。"My cats are very cute."という文書があり、query(検索文)がcuteであれば、この文書はqueryにマッチすることになります。

Boolean検索という名が示す通り、ANDやORといった論理演算も可能です。cats AND smartというqueryは文書"My cats are very cute."にはマッチしませんが、cats OR smartはマッチします。

Inverted Index (転置索引)

Inverted index(転置索引、単純にindexとも呼ばれる)は、検索対象となるテキスト文書を、文書IDから検索対象となるキーワードの構造から、キーワードから文書ID方向へ「転置」したデータ構造のことです。Boolean retrievalにおいて最も基本的でよく使われているデータ構造と言えるかと思います。

たとえば、以下のようなID0,1を持つ2つのテキスト文書(文字列)があったとして、

元文書
  String doc0 = "My cats are very cute.";
  String doc1 = "My dog is not so cute.";

各文書に含まれる単語を抽出すると、文書IDに対して以下のような単語列を得ることができます。

文書to単語列
  String[] doc0 = {"My", "cats", "are", "very", "cute". "."};
  String[] doc1 = {"My", "dog", "is", "not", "so", "cute", "."};

これを「転置」すると、各単語からそれを含む文書ID列へのデータ構造を得ることができます。この形がInverted Indexです。また、Inverted indexを構築する処理は一般にIndexingと呼ばれます。この例ではJavaのLinkedHashMapで実装していますが、情報検索アプリケーションに特化した実装をApache Lucene Coreは提供してくれます。

転置索引
  LinkedHashMap<String, int[]> index;

  index.get("cats"); // {0}
  index.get("cute"); // {0, 1}

なお、Inverted indexにおいてTermをルックアップするためのデータ部分はDictionary(語彙辞書)、Termから紐づけられた文書IDの列のデータ部分1をPostingsと呼びます。

Apache Luceneによる単純なBoolean検索アプリケーション

実際に、Apache Luceneを使った(筆者が思う)最も簡単な検索アプリケーション2の実装例を見ていきたいと思います。以下にコードを示します。Mavenリポジトリを参照したpom.xmlのdependencyも示しておきます。

dependencies
  <dependencies>
    <dependency>
        <groupId>org.apache.lucene</groupId>
        <artifactId>lucene-core</artifactId>
        <version>6.2.0</version>
    </dependency>
    <dependency>
        <groupId>org.apache.lucene</groupId>
        <artifactId>lucene-analyzers-common</artifactId>
        <version>6.2.0</version>
    </dependency>
  </dependencies>
VerySimpleIndexingAndSearchExample.java

package qiita;

import java.io.File;
import java.io.IOException;
import java.util.Arrays;

import org.apache.lucene.analysis.core.WhitespaceAnalyzer;
import org.apache.lucene.document.Document;
import org.apache.lucene.document.TextField;
import org.apache.lucene.document.Field.Store;
import org.apache.lucene.index.DirectoryReader;
import org.apache.lucene.index.IndexReader;
import org.apache.lucene.index.IndexWriter;
import org.apache.lucene.index.IndexWriterConfig;
import org.apache.lucene.index.LeafReader;
import org.apache.lucene.index.PostingsEnum;
import org.apache.lucene.index.Term;
import org.apache.lucene.index.TermsEnum;
import org.apache.lucene.search.BooleanQuery;
import org.apache.lucene.search.DocIdSetIterator;
import org.apache.lucene.search.IndexSearcher;
import org.apache.lucene.search.Query;
import org.apache.lucene.search.TermQuery;
import org.apache.lucene.search.TopDocs;
import org.apache.lucene.search.BooleanClause.Occur;
import org.apache.lucene.store.Directory;
import org.apache.lucene.store.FSDirectory;
import org.apache.lucene.util.BytesRef;

public class VerySimpleIndexingAndSearchExample {

    public static final void main(String[] args) throws IOException {

        // Indexing
        {
            Directory dir = FSDirectory.open(new File("/tmp/index").toPath());
            IndexWriter writer = new IndexWriter(dir, new IndexWriterConfig(new WhitespaceAnalyzer()));
            try {
                Document doc_0 = new Document();
                doc_0.add(new TextField("body", "My cats are very cute", Store.NO));

                Document doc_1 = new Document();
                doc_1.add(new TextField("body", "My dog is not so cute", Store.NO));

                writer.addDocuments(Arrays.asList(doc_0, doc_1));
                writer.commit();
            } finally {
                writer.close();
            }
        }



        // Search
        {
            Directory dir = FSDirectory.open(new File("/tmp/index").toPath());
            IndexSearcher searcher = new IndexSearcher(DirectoryReader.open(dir));

            Query query;
            TopDocs results;

            // A term query which matches two documents
            query = new TermQuery(new Term("body", "cats"));
            results = searcher.search(query, 10); // search for the top 10 documents ordered by relevancy

            System.out.println(results.totalHits + " documents matched for query: " + query);
            System.out.println("The top result's score is " + results.scoreDocs[0].score);

            // A term query which matches two documents
            query = new TermQuery(new Term("body", "cute"));
            results = searcher.search(query, 10); // search for the top 10 documents ordered by relevancy

            System.out.println(results.totalHits + " documents matched for query: " + query);
            System.out.println("The top result's score is " + results.scoreDocs[0].score);

            // A term query which does not match any document
            query = new TermQuery(new Term("body", "monkey"));
            results = searcher.search(query, 10); // search for the top 10 documents ordered by relevancy

            System.out.println(results.totalHits + " documents matched for query: " + query);
            System.out.println("TopDocs should be empty. Length: " + results.scoreDocs.length); 

            // A boolean query concatenated with OR
            BooleanQuery.Builder bqBuilder = new BooleanQuery.Builder();
            bqBuilder.add(new TermQuery(new Term("body", "cute")), Occur.SHOULD);
            bqBuilder.add(new TermQuery(new Term("body", "monkey")), Occur.SHOULD);
            query = bqBuilder.build(); // cute OR monkey 
            results = searcher.search(query, 10); // search for the top 10 documents ordered by relevancy
            System.out.println(results.totalHits + " documents matched for query: " + query);
            System.out.println("The top result's score is " + results.scoreDocs[0].score);

        }

        // Scan the inverted index
        {
            Directory dir = FSDirectory.open(new File("/tmp/index").toPath());
            IndexReader reader = DirectoryReader.open(dir);

            // Top level IndexReader consists of multiple leaves. 
            LeafReader leafReader = reader.leaves().get(0).reader();
            // Retrieve the term list 
            TermsEnum termsEnum = leafReader.terms("body").iterator();
            final String targetWord = "cats";
            // Look up the word "cats" in the index
            if(termsEnum.seekExact(new BytesRef(targetWord))) {
                PostingsEnum postings = termsEnum.postings(null);
                while(postings.nextDoc() != DocIdSetIterator.NO_MORE_DOCS) {
                    // Only in docid zero.
                    System.out.println(targetWord + " is found in doc:" + postings.docID());
                }
            }
        }
    }

}

Indexing

下記のコードは/tmp/indexディレクトリに先に挙げた2つの文書をindexingしています。

        // Indexing
        {
            Directory dir = FSDirectory.open(new File("/tmp/index").toPath());
            IndexWriter writer = new IndexWriter(dir, new IndexWriterConfig(new WhitespaceAnalyzer()));
            try {
                Document doc_0 = new Document();
                doc_0.add(new TextField("body", "My cats are very cute", Store.NO));

                Document doc_1 = new Document();
                doc_1.add(new TextField("body", "My dog is not so cute", Store.NO));

                writer.addDocuments(Arrays.asList(doc_0, doc_1));
                writer.commit();
            } finally {
                writer.close();
            }
        }

ここでは最もシンプルなWhitespaceAnalyzerを使って文書から単語を抽出しています3。これはその名の通り、空白で区切られた文字列をTermとしてindexingするもので、語の活用の補正(e.g. cats -> cat, is -> be)やピリオドの除去といった言語処理などは一切行いません。

Luceneでは、検索対象となるtermの空間をfieldと呼ばれる複数の空間に分割できます。今回の単純な例では、下記のようにbodyというfieldに文書全体の文字列をindexingします。例えば、"title"や"author"など、複数のFieldを用意すれば、著者(author)の"Jobs"と本文(body)に現れただけの"Jobs"を区別した検索が可能となります。Store.NOについては今は気にしなくてもかまいません。

doc_0.add(new TextField("body", "My cats are very cute", Store.NO));

IndexWriter#commit()を呼び出すのを忘れないように気をつけましょう。commitの実行で初めてindexはディレクトリに静的に固定され検索可能になります。

Search

一方、下記のコードはindexingの結果構築されたindexに対して検索を行うコードです。IndexSearcher#search(Query, int)をたった1行実行するだけで、inverted indexに対して検索を行い、queryに対するスコア順に並んだ検索結果を指定した数だけ取得することができます。Luceneでのスコアはデフォルトでは文書内のtermの出現数、索引内でのtermの珍しさや文書の長さなどから計算されますが、詳細はまた別の機会に触れることとさせてください4。

        // Search
        {
            Directory dir = FSDirectory.open(new File("/tmp/index").toPath());
            IndexSearcher searcher = new IndexSearcher(DirectoryReader.open(dir));

            Query query;
            TopDocs results;

            // A term query which matches two documents
            query = new TermQuery(new Term("body", "cats"));
            results = searcher.search(query, 10); // search for the top 10 documents ordered by relevancy

            System.out.println(results.totalHits + " documents matched for query: " + query);
            System.out.println("The top result's score is " + results.scoreDocs[0].score);

            // A term query which matches two documents
            query = new TermQuery(new Term("body", "cute"));
            results = searcher.search(query, 10); // search for the top 10 documents ordered by relevancy

            System.out.println(results.totalHits + " documents matched for query: " + query);
            System.out.println("The top result's score is " + results.scoreDocs[0].score);

            // A term query which does not match any document
            query = new TermQuery(new Term("body", "monkey"));
            results = searcher.search(query, 10); // search for the top 10 documents ordered by relevancy

            System.out.println(results.totalHits + " documents matched for query: " + query);
            System.out.println("TopDocs should be empty. Length: " + results.scoreDocs.length); 

            // A boolean query concatenated with OR
            BooleanQuery.Builder bqBuilder = new BooleanQuery.Builder();
            bqBuilder.add(new TermQuery(new Term("body", "cute")), Occur.SHOULD);
            bqBuilder.add(new TermQuery(new Term("body", "monkey")), Occur.SHOULD);
            query = bqBuilder.build(); // cute OR monkey 
            results = searcher.search(query, 10); // search for the top 10 documents ordered by relevancy
            System.out.println(results.totalHits + " documents matched for query: " + query);
            System.out.println("The top result's score is " + results.scoreDocs[0].score);

        }

TermQueryは、用語の存在の有無でヒットの可否が判定されるqueryの最も基本的な実装です。下記のコードでqueryはTermcuteを含む文書を問い合わせます。よって結果として2文書がマッチすることになります。

            // A term query which matches two documents
            query = new TermQuery(new Term("body", "cute"));
            results = searcher.search(query, 10); // search for the top 10 documents ordered by relevancy

BooleanQuery.Builderを使うことで、ANDやOR相当のQueryを生成することができます。下記のコードではOccur.SHOULDを節の修飾子としていることで「あってもなくてもよい」という条件で節を足しているので、cute OR monkeyという意味合いの検索になります。monkeyを含む文書はありませんが、cuteは2文書に含まれているので、結果としては2文書がマッチすることになります。

            // A boolean query concatenated with OR
            BooleanQuery.Builder bqBuilder = new BooleanQuery.Builder();
            bqBuilder.add(new TermQuery(new Term("body", "cute")), Occur.SHOULD);
            bqBuilder.add(new TermQuery(new Term("body", "monkey")), Occur.SHOULD);
            query = bqBuilder.build(); // cute OR monkey

Inverted Index Scan

IndexSearcher#search(Query, int)一行だけで検索を行えることは説明しました。たとえば単純なTermQueryを評価するとき、このAPIの内部では、

  1. DictionaryをseekしてTermを探し出し、
  2. そのTermに紐づくPostingsを走査することでTermを含む文書IDを見つけ出す

ことでqueryは評価されます。下記のコードは、catsというTermに対するPostingsを取得してそれを含む文書IDをイテレートするためのコードです。Luceneは、こういったプリミティブな処理を行うためのAPIが提供されています。通常Apache Solrなどの検索エンジンソフトウェアを使うだけの場合にはこのようなコードを意識することはないかと思いますが、情報検索の基本を理解する上で非常に重要です。

        // Scan inverted index
        {
            Directory dir = FSDirectory.open(new File("/tmp/index").toPath());
            IndexReader reader = DirectoryReader.open(dir);

            // Top level IndexReader consists of multiple leaves. 
            LeafReader leafReader = reader.leaves().get(0).reader();
            // Retrieve the term list 
            TermsEnum termsEnum = leafReader.terms("body").iterator();
            final String targetWord = "cats";
            // Look up the word "cats" in the index
            if(termsEnum.seekExact(new BytesRef(targetWord))) {
                PostingsEnum postings = termsEnum.postings(null);
                while(postings.nextDoc() != DocIdSetIterator.NO_MORE_DOCS) {
                    // Only in docid zero.
                    System.out.println(targetWord + " is found in doc:" + postings.docID());
                }
            }
        }

まとめ

情報検索の最初の最初の一歩として、Inverted indexとBoolean retrievalの概念についてApache Luceneによる実例を通して述べました。今後、Introduction to Information Retrievalに沿う形でもっと踏み込んだ内容についても書いてみたいと思います。

  1. 実際にはTermの文書中の位置などのデータもPostingsに格納できます。詳細はこちらから先取りできます。 ↩

  2. 繰り返しになりますが、Apache Lucene Coreは「ライブラリ」なのでアプリケーションの仕組み自体は実装者が実装する必要があります。この例では単純なJava Standaloneアプリケーションです。 ↩

  3. 多くのLucene解説本ではStandardAnalyzerを紹介するケースが多いと思いますが、StandardAnalyzerは不要語の除去などの簡単な言語処理をも含むので、より説明を単純にするためにWhitespaceAnalyzerを使っています。 ↩

  4. とはいえ詳細を知りたい方のためにリンクを貼っておきます。 ↩

11
10
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
11
10