インデックス作成とランキング (c.f.『世界でもっとも強力な9のアルゴリズム』)

書籍『世界でもっとも強力な9のアルゴリズム』の1つ目のアルゴリズムの章をチラ見しました。解説に使われた例が、どう書くの問題みたいだなぁと思ったので、試しにJavaで書いてみました。

世界でもっとも強力な9のアルゴリズム

1つ目は、「検索エンジンに複数の検索語を与えた時、それらの語が最も近接して出現するページを検索結果の上位として返す」というアルゴリズムです。

問題の定義（残念ながら不完全ですが）

図で説明するとこんな感じです。

入力は、検索語と検索対象ページ群とします。

検索語

半角スペースで区切った複数の英単語です。

検索対象ページ群

簡単のため、単なる文字列を検索対象ページと考えることにします。文字列は英語の文章で、単語境界は半角スペースです。1〜n個のページが与えられます。

出力では、検索語が最も近接して出現する検索対象ページの番号を返してください。番号は、入力時の検索対象ページ群のn番目（0オリジン）に対応します。

• 検索語および検索対象ページに、特殊文字が出現することを考慮する必要はありません。

#同じ順位のページが複数ある場合を考えていませんでした（そのため、この文章は問題として不完全です）。入力時の順序に従うものとする、ということにすれば、テストデータが準備しやすいかも。

解答

public class WordPosition {
	private Integer pageNo;
	private Integer position;

	public WordPosition(Integer n, Integer p) {
		pageNo = n;
		position = p;
	}

	public Integer getPageNo() {
		return pageNo;
	}

	public Integer getPosition() {
		return position;
	}
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

	public String solve(final String input, final List<String> pages) {
		String[] keywords = input.split(" ");

		Map<String, List<WordPosition>> indexes = new HashMap<>();
		indexes = getIndex(indexes, keywords, pages);

		List<Map.Entry<Integer, Integer>> result = rank(indexes);
		return String.valueOf(result.get(0).getKey());
	}

	protected Map<String, List<WordPosition>> getIndex(
			final Map<String, List<WordPosition>> indexes,
			final String[] keywords, final List<String> pages) {
		Map<String, List<WordPosition>> result = new HashMap<>();
		for (int i = 0; i < keywords.length; i++) {
			List<WordPosition> contents = getWordPositions(keywords[i], pages);
			result.put(keywords[i], contents);
		}
		return result;
	}

	protected List<WordPosition> getWordPositions(final String keyword,
			final List<String> pages) {
		List<WordPosition> result = new ArrayList<>();
		for (int i = 0; i < pages.size(); i++) {
			result.addAll(searchOnePage(pages.get(i), i, keyword));
		}
		return result;
	}

	protected List<WordPosition> searchOnePage(final String target,
			final int pageNo, final String keyword) {
		List<WordPosition> result = new ArrayList<>();
		String[] targetWords = target.split(" ");

		Pattern p = Pattern.compile(keyword + "(.|:|;|,|!|\\?)*",
				Pattern.CASE_INSENSITIVE);

		for (int wordNo = 0; wordNo < targetWords.length; wordNo++) {
			Matcher m = p.matcher(targetWords[wordNo]);
			if (m.find()) {
				result.add(new WordPosition(pageNo, wordNo));
			}
		}
		return result;
	}

	protected List<Map.Entry<Integer, Integer>> rank(
			final Map<String, List<WordPosition>> indexes) {
		Map<Integer, Integer> map = new HashMap<>();
		for (String word : new HashSet<>(indexes.keySet())) {
			List<WordPosition> list = indexes.get(word);
			for (WordPosition each : list) {
				Integer pageNo = each.getPageNo();
				List<Integer> positions = getOtherPositions(indexes, pageNo,
						word);
				if (positions.isEmpty() == false) {
					int gap = getMinGap(positions, each.getPosition());
					if (map.containsKey(pageNo)) {
						map.put(pageNo, Math.min(map.get(pageNo), gap));
					} else {
						map.put(pageNo, gap);
					}
				}
			}
		}

		List<Map.Entry<Integer, Integer>> result = new ArrayList<>(
				map.entrySet());
		Collections.sort(result, new Comparator<Map.Entry<Integer, Integer>>() {
			@Override
			public int compare(Entry<Integer, Integer> o1,
					Entry<Integer, Integer> o2) {
				return o1.getValue().compareTo(o2.getValue());
			}
		});
		return result;
	}

	protected int getMinGap(final List<Integer> positions, final Integer position) {
		Integer result = Math.abs(position - positions.get(0));
		for (Integer each : positions) {
			result = Math.min(result, Math.abs(position - each));
		}
		return result;
	}

	protected List<Integer> getOtherPositions(
			final Map<String, List<WordPosition>> indexes,
			final Integer pageNo, final String currentWord) {
		List<Integer> result = new ArrayList<>();
		Set<String> keySet = indexes.keySet();
		keySet.remove(currentWord);
		for (String each : keySet) {
			List<WordPosition> list = indexes.get(each);
			for (WordPosition word : list) {
				if (pageNo == word.getPageNo()) {
					result.add(word.getPosition());
				}
			}
		}
		return result;
	}
}

import static org.junit.Assert.assertEquals;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

public class TestMain {
	@Test
	public void testSolve() throws Exception {
		test("1", "cute paw", "My cat is cute.", "My cat has a cute paw!",
				"The paw of our cat is very cute.");
		test("2", "black company",
				"The brand coller of that company is black.",
				"Is that your company?", "A black company was broke.",
				"The company was named BLACK CHOCOLATE.");
	}

	private void test(String expected, String word, String... page) {
		Main main = new Main();
		List<String> pages = new ArrayList<>();
		for (String each : page) {
			pages.add(each);
		}
		assertEquals(expected, main.solve(word, pages));
	}
}

考えたこと

1

［検索対象ページ番号］と［語の出現位置］をセットで保持するために、タプルが欲しくなりました。しかし、タプルが欲しいならJava以外を使った方がよさそうです。

2

また、途中でジェネリクスの引数に名前をつけたいと感じたのですが、そう思った時点で諦めてクラスを作るのがよい気がしました。

3

MapをValueでソートする一般的な書き方を知らないことに気づきました。Comparatorの実装クラスを作るんですよね、きっと。たぶん。おそらく。

4

このテストの書き方は、オフラインリアルタイムどう書くで問題を解く時にもよくやっているのですが、どのケースでコケたのかが分からないので正直よくないと思います。サンプルデータをごっそり渡しつつ、いい感じにassertしたい。どう書けばいいのか。