Luceneを用いた全文検索

自分が開発・運営しているQMACloneでは全文検索エンジンにtritonn-MySQLを使用している。tritonnを使用する場合、yumやaptでインストールすることができるMySQLパッケージを使うことが実質できなくなってしまう(正確には共存できるはずだが面倒)。このためメンテナンスや他のパッケージとの競合の解消が面倒になってしまう。

最近Twitterが全文検索エンジンにLuceneを採用したと聞き、自分も試してみることにした。

QMACloneにLuceneを組み込むにあたり、問題データ自体はMySQLに持たせ、ゲームサーバーの起動時に問題データをLuceneでインデックスに変換するという形にした。これは既存のソースコードの兼ね合いからである。書いたコードを備忘録を兼ねて掲載する。

インデックス化

まずは問題データをDocument化してIndexWriteでインデクスデータに変換する部分。

	private Document convertProblemDataToDocument(PacketProblemData problemData) {
		final Document document = new Document();

		// 問題番号
		final String problemId = "" + problemData.problemId;
		document.add(new Field(FIELD_PROBLEM_ID, problemId, Store.YES, Index.NO));

		// 問題文
		String sentence = problemData.sentence;
		sentence = Normalizer.normalize(sentence, Normalizer.Form.NFKC);
		document.add(new Field(FIELD_SENTENCE, sentence, Store.NO, Index.ANALYZED));

		// 問題文+選択肢+解答+問題ノート
		String searchQuery = problemData.getSearchQuery();
		searchQuery = Normalizer.normalize(searchQuery, Normalizer.Form.NFKC);
		document.add(new Field(FIELD_SEARCH, searchQuery, Store.NO, Index.ANALYZED));

		// 作問者
		String creator = problemData.creator;
		creator = Normalizer.normalize(creator, Normalizer.Form.NFKC);
		document.add(new Field(FIELD_CREATOR, creator, Store.NO, Index.ANALYZED));

		// ジャンル
		NumericField numericField = new NumericField(FIELD_GENRE, Store.NO, true);
		numericField.setIntValue(problemData.genre);
		document.add(numericField);

		// 出題形式
		numericField = new NumericField(FIELD_TYPE, Store.NO, true);
		numericField.setIntValue(problemData.type);
		document.add(numericField);

		// ランダム
		numericField = new NumericField(FIELD_RANDOM_FLAG, Store.NO, true);
		numericField.setIntValue(problemData.randomFlag);
		document.add(numericField);
		return document;
	}

Luceneは原則的には文字列しか扱うことができない。一方、元の問題データにはジャンル・出題形式・ランダムフラグは整数として持たせてある。これらの整数のデータをLuceneで扱うためにNumericFieldを使った。これとNumericRangeQueryを併用すると、Trie木を使って数値データを高速に検索できるようになるらしい。

続いてインデックスの作成部分。

	private class ProblemIndexWriter implements ProblemProcessor {
		private final IndexWriter indexWriter;

		public ProblemIndexWriter(IndexWriter indexWriter) {
			this.indexWriter = indexWriter;
		}

		@Override
		public void process(PacketProblemData problemData) throws Exception {
			final Document document = convertProblemDataToDocument(problemData);

			indexWriter.addDocument(document);
		}
	}

	public DirectDatabase() {
		delete(indexFileDirectory);
		indexFileDirectory.mkdirs();

		synchronized (lockIndexWriter) {
			IndexWriter writer = null;
			try {
				final FSDirectory d = FSDirectory.open(indexFileDirectory);
				final CJKAnalyzer analyzer = new CJKAnalyzer(Version.LUCENE_30);
				writer = new IndexWriter(d, analyzer, true, IndexWriter.MaxFieldLength.LIMITED);
				processProblems(new ProblemIndexWriter(writer));
				writer.optimize();
			} catch (Exception e) {
				e.printStackTrace();
			} finally {
				if (writer != null) {
					try {
						writer.close();
					} catch (Exception e2) {
						e2.printStackTrace();
					}
					writer = null;
				}
			}
		}

		ThreadPool.getInstance().addDailyTask(runnableUpdateIndex);
	}

日本語の解析にはCJKAnalyzerを使った。これはbi-gramで文章を区切ってTermに変換するクラスだ。Lucene 3.0.*でCJKAnalyzerを使用する場合は「contrib/analyzers/common/lucene-analyzers-3.0.2.jar」をビルドパスに含める必要がある。

processProblems()はMySQLから問題データを取得して、引数で指定したハンドラに渡すメソッドである。ProblemIndexWriterは送られてきた問題データを上記のconvertProblemDataToDocument()でDocumentに変換してIndexWriterに渡すクラスである。これでゲームサーバーの起動時に問題データのインデックス化ができる。

問題データ更新

問題データが更新されたらインデックスも更新する。やり方はほとんど植えと同じなので割愛。更新の場合はaddDocument()の代わりにupdateDocument()が使える。

問題検索

続いて問題検索の部分。

	private static final String LUCENE_ESCAPE_CHARS = "(&&)|(\\|\\|)|[\\+\\-\\!\\(\\)\\{\\}\\[\\]\\^\\\"\\~\\*\\?\\:\\\\]";
	private static final Pattern LUCENE_PATTERN = Pattern.compile(LUCENE_ESCAPE_CHARS);
	private static final String REPLACEMENT_STRING = "\\\\$0";

	public static String escapeQuery(String t) {
		return LUCENE_PATTERN.matcher(t).replaceAll(REPLACEMENT_STRING);
	}

	private BooleanQuery concatenateQueries(List<Query> queries) {
		final BooleanQuery result = new BooleanQuery();
		for (Query query : queries) {
			result.add(query, Occur.MUST);
		}
		return result;
	}

	private List<Query> queryStringToLuceneQueries(String field, String queryString) throws ParseException {
		// 互換合成
		queryString = Normalizer.normalize(queryString, Form.NFKC);

		final CJKAnalyzer analyzer = new CJKAnalyzer(Version.LUCENE_30);
		final QueryParser parser = new QueryParser(Version.LUCENE_30, field, analyzer);

		final List<Query> queries = new ArrayList<Query>();
		final Scanner scanner = new Scanner(queryString);
		while (scanner.hasNext()) {
			final String t = scanner.next();
			final String escaped = escapeQuery(t);
			final Query q = parser.parse(escaped);
			queries.add(q);
		}
		return queries;
	}

	private Query bitFlagToQuery(String field, int bitFlag) {
		final BooleanQuery query = new BooleanQuery();
		int begin = -1;
		for (int i = 0; i < 31; ++i) {
			if ((bitFlag & (1 << i)) == 0) {
				if (begin == -1) {
					continue;
				}
				final Query q = NumericRangeQuery.newIntRange(field, begin, i, true, false);
				query.add(q, Occur.SHOULD);
				begin = -1;
			} else {
				if (begin == -1) {
					begin = i;
				}
			}
		}

		return query;
	}

	public PacketProblemData[] searchProblem(final String queryString, final String creater, int genre, int type, int randomFlag) {
		final boolean queryEmpty = (queryString == null || queryString.isEmpty());
		final boolean createrEmpty = (creater == null || creater.isEmpty());
		if (queryEmpty && createrEmpty && genre <= 1 && type <= 1) {
			return new PacketProblemData[0];
		}

		if (genre == 0 || (genre & 1) == 1) {
			genre = (1 << Constant.NUMBER_OF_GENRE) - 1;
		}
		if (type == 0 || (type & 1) == 1) {
			type = (1 << Constant.NUMBER_OF_TYPE) - 1;
		}
		if (randomFlag == 0 || (randomFlag & 1) == 1) {
			randomFlag = (1 << Constant.NUMBER_OF_RANDOM) - 1;
		}

		final BooleanQuery query = new BooleanQuery();

		// 問題文
		if (!queryEmpty) {
			try {
				for (Query q : queryStringToLuceneQueries(FIELD_SEARCH, queryString)) {
					query.add(q, Occur.MUST);
				}
			} catch (Exception e) {
				e.printStackTrace();
				return null;
			}
		}

		// 作成者
		if (!createrEmpty) {
			try {
				for (Query q : queryStringToLuceneQueries(FIELD_CREATOR, creater)) {
					query.add(q, Occur.MUST);
				}
			} catch (Exception e) {
				e.printStackTrace();
				return null;
			}
		}

		// ジャンル
		query.add(bitFlagToQuery(FIELD_GENRE, genre), Occur.MUST);

		// 出題形式
		query.add(bitFlagToQuery(FIELD_TYPE, type), Occur.MUST);

		// ランダムフラグ
		query.add(bitFlagToQuery(FIELD_RANDOM_FLAG, randomFlag), Occur.MUST);

		IndexReader reader = null;
		try {
			reader = IndexReader.open(FSDirectory.open(indexFileDirectory), true);

			final Searcher searcher = new IndexSearcher(reader);

			final TopDocs docs = searcher.search(query, MAX_NUMBER_OF_SEARCH_REUSLTS);
			final List<Integer> problemIds = new ArrayList<Integer>();
			for (ScoreDoc doc : docs.scoreDocs) {
				final Document document = reader.document(doc.doc);
				final int problemId = Integer.parseInt(document.get(FIELD_PROBLEM_ID));
				problemIds.add(problemId);
			}

			if (problemIds.isEmpty()) {
				return new PacketProblemData[0];
			}
			return getProblemData(problemIds);

		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			if (reader != null) {
				reader.clone();
				reader = null;
			}
		}

		return null;
	}

本当はTermQueryが使いたかったのだが、何らかの原因で正しく検索ができなかった。おそらく文字のノーマライズ処理のあたりが原因だと思う。このためCJKAnalyzerとQueryParserを使うことにした。

LuceneではQuery Parserに渡すクエリに「+ - && || ! ( ) { } [ ] ^ " ~ * ? : \」が含まれている場合、先頭に「\」を付けてエスケープしなければならない。これらのエスケープ処理をescapeQuery()で行っている。

bitFlagToQuery()ではビットフラグをNumericRangeQueryに変換している。複数のジャンル・問題形式・ランダムフラグが指定されたときは、この部分で絞り込みを行う。

類似問題検索

類似問題の検索部分。QMACloneでは独自実装した関連文書検索エンジンを使用している。これはWikipediaのタイトル一覧とニコニコ大百科の記事タイトル一覧を単語辞書と見立てて、tf-idfを元に類似文書を見つけるという物である。少し前に流行ったやり方だと思う。この自家製関連文書検索エンジンは極稀に検索に失敗する場合がある。失敗した場合はMySQLの全文検索エンジンを使って検索し直すようにしていた。この失敗した場合の検索ルーチンをLuceneに置き換えてみた。

	public PacketProblemData[] searchSimilarProblemDataFromDatabase(PacketProblemData problemData) {
		IndexReader reader = null;
		try {
			reader = IndexReader.open(FSDirectory.open(indexFileDirectory), true);

			final Searcher searcher = new IndexSearcher(reader);

			final String[] fields = new String[] { FIELD_SEARCH };
			final Analyzer analyzer = new CJKAnalyzer(Version.LUCENE_30);
			final MoreLikeThisQuery query = new MoreLikeThisQuery(problemData.getSearchQuery(), fields, analyzer);

			final TopDocs docs = searcher.search(query, 10);
			final List<Integer> problemIds = new ArrayList<Integer>();
			for (ScoreDoc doc : docs.scoreDocs) {
				final Document document = reader.document(doc.doc);
				final int problemId = Integer.parseInt(document.get(FIELD_PROBLEM_ID));
				problemIds.add(problemId);
			}

			if (problemIds.isEmpty()) {
				return new PacketProblemData[0];
			}
			return getProblemData(problemIds);

		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			if (reader != null) {
				reader.clone();
				reader = null;
			}
		}

		return null;
	}

MoreLikeThisQueryは類似文書の検索クエリである。他のクエリと同様に扱うことができるので便利だと思う。使用する場合は「contrib/queries/lucene-queries-3.0.2.jar」をビルドパスに含める必要がある。

ちなみに自家製検索エンジンとMoreLikeThisQueryで検索した場合の違いはこんな感じ。クエリは"「Google」で2020年完成予定の 人工知能で会話しつつ検索などを行うサービスを 「Google　○○○○○」という？ ＢＲＡＩＮ"。まずは自家製検索エンジン。

173047 - 5 - 9 - サーバのサービスをすべて選びなさい - DNS - SMTP - DHCP -  - DNS - SMTP - DHCP - VTEC - 
174780 - 1 - 4 - 2010年よりサービスを開始するコナミの電子マネーシステムは？ - PASELI -  -  -  -  -  -  -  - 
174781 - 1 - 7 - 2010年よりサービスを開始するコナミの電子マネーシステムです。 - ＰＡＳＥＬＩ -  -  -  -  -  -  -  - 
128595 - 2 - 6 - テニスにおいてサーバーがサービスゲームを取得することを○○○という？%n○を答えなさい - キープ -  -  -  -  -  -  -  - 
35275 - 4 - 6 - Googleの検索バーに%n「人生、宇宙、すべての答え」と打ち込むと%n電卓機能が示す答えはいくつ？%n数字で答えなさい。 - ４２ -  -  -  -  -  -  -  - 
163987 - 3 - 7 - Google社が開発・配布している、%n写真を検索したり共有するためのソフトウェアです - ＰＩＣＡＳＡ -  -  -  -  -  -  -  - 
56017 - 4 - 11 - 次の古語とその意味の%n正しい組み合わせを答えなさい - 会話をする - 歳をとる - 遠ざかる - 塞ぎ込む - こととふ - ねぶ - かる - くんず - 
185084 - 4 - 7 - 回答例を元に質問者の思い浮かべた%n人物やキャラクターを当てる%nインターネット上で話題となった人工知能の名前 - アキネーター -  -  -  -  -  -  -  - 
68562 - 4 - 7 - 『Google』や『Yahoo』等が有名な%n検索エンジンを２つに分けると%n『ロボット型』と『？型』 - ディレクトリ -  -  -  -  -  -  -  - 
32137 - 4 - 6 - 「Google」で2020年完成予定の%n人工知能で会話しつつ検索などを行うサービスを%n「Google　○○○○○」という？ - ＢＲＡＩＮ -  -  -  -  -  -  -  -

「Google」「サービス」という単語に引っかかっているらしい。続いてMoreLikeThisQuery。

32137 - 4 - 6 - 「Google」で2020年完成予定の%n人工知能で会話しつつ検索などを行うサービスを%n「Google　○○○○○」という？ - ＢＲＡＩＮ -  -  -  -  -  -  -  - 
182705 - 4 - 8 - 2011年完成予定の東京スカイツリーの%n最寄り駅です。 - なりひらばし -  -  -  - 業平橋 -  -  -  - 
158864 - 4 - 12 - 香港一高い建物になる2010年完成予定のこの超高層ビルは？ - 環球貿易広場 - 国際金融中心 - 西九龍電波塔 - 香港上海銀行 -  -  -  -  - 
158237 - 4 - 9 - 次のうち%nGoogleが提供するサービスに%n実際にあるものを全て選びなさい - Google Earth - Google Sky - Google Moon - Google Mars - Google Earth - Google Sky - Google Moon - Google Mars - 
62940 - 4 - 9 - 次のうち、2007年6月現在、検索エンジン「Google」にアクセスできるアドレスを全て選びなさい。 - http://www.google.tv/ - http://www.google.info/ - http://www.google.kg/ - http://www.google.cc/ - http://www.google.tv/ - http://www.google.info/ - http://www.google.kg/ - http://www.google.cc/ - 
80279 - 4 - 10 - 次のGoogleのサービスを開始されたのが早い順に選びなさい。 - Gmail - Google Video - Google Earth - Chrome -  -  -  -  - 
30862 - 3 - 3 - solitude%w%nEternally　Beyond%w%nDialogue　Symphonie%w%w%nLa　dix　croix - Moi dix Mois -  -  -  - Moi dix Mois - Sulfulic Acid - Brain Hacker - MALICE MIZER - 
84336 - 4 - 4 - 脳・神経に関係する英単語で、「脳」といえば？ - brain -  -  -  -  -  -  -  - 
12858 - 1 - 2 - 次のうち、%nアニメ『攻殻機動隊』シリーズの%n舞台となる年代は？ - 西暦2030年代 -  -  -  - 西暦2030年代 - 西暦2020年代 - 西暦2040年代 - 西暦2050年代 - 
128401 - 5 - 7 - 北海道夕張市の大夕張ダムの下流に%n現在建設中のダムは「夕張○○○○○ダム」？ - シューパロ -  -  -  -  -  -  -  -

「完成予定」「Google」「2020年」という単語に引っかかっているらしい。