Javaで学ぶアルゴリズム -文字列探索（Boyer-Moore法）

文字列探索（Boyer-Moore法）

このアルゴリズムでは検索文字列（パターン）の前処理を行い、検索対象テキストの前処理は行わない。したがって、テキストについて何度も検索を行わない場合に適している（他のアルゴリズムではテキスト側に前処理を施し、繰り返し検索を行うことで前処理のコストを償却する）。テキスト上の全文字をチェックする必要はなく、前処理で得た情報を活用してスキップしながら処理していく。一般にパターン文字列が長いほど検索が高速化される。検索文字列とテキストの間での不一致が発生するたびに、不一致であったという情報を最大限に利用して照合しなくてもいい位置を可能な限り排除することで、効率を向上させている。

KMP法より優れていて、実際の文字列探索では広く利用されているんだって。

実行環境

• JUnit 5
• Java 8

テストコード

BoyerMooreSearchTest.java

import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.junit.jupiter.api.Assertions.assertThrows;

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Nested;
import org.junit.jupiter.api.Test;

public class BoyerMooreSearchTest {

	private String text;

	@BeforeEach
	void setUp() {
		text = "これはテストです。This is a test. もう一度テストします。";
	}

	@DisplayName("パターンがテキスト内に存在する場合")
	@Nested
	class PatternExists {

		@DisplayName("パターンがテキストの最初に存在する場合、0が返ること")
		@Test
		void testPatternExistsAtBeginning() {
			assertThat(BoyerMooreSearch.bmSearch(text, "これ"), is(0));
		}

		@DisplayName("パターンがテキストの中間に存在する場合、その位置が返ること")
		@Test
		void testPatternExistsInMiddle() {
			assertThat(BoyerMooreSearch.bmSearch(text, "test"), is(19));
		}

		@DisplayName("パターンがテキストの最後に存在する場合、その位置が返ること")
		@Test
		void testPatternExistsAtEnd() {
			assertThat(BoyerMooreSearch.bmSearch(text, "します"), is(32));
		}

		@DisplayName("パターンがテキストに複数存在する場合、最初の位置を返すこと")
		@Test
		public void testPatternExistsMultipleTimes() {
			assertThat(BoyerMooreSearch.bmSearch(text, "テスト"), is(3));
		}

		@DisplayName("パターンが空の場合、0が返ること")
		@Test
		void testPatternIsEmpty() {
			assertThat(BoyerMooreSearch.bmSearch(text, ""), is(0));
		}

		@DisplayName("テキストとパターンが共に空の場合、0が返ること")
		@Test
		void testBothTextAndPatternEmpty() {
			assertThat(BoyerMooreSearch.bmSearch("", ""), is(0));
		}
	}

	@DisplayName("パターンがテキスト内に存在しない場合")
	@Nested
	class PatternNotExists {
		@DisplayName("パターンがテキストに存在しない場合、-1が返ること")
		@Test
		void testPatternNotExists() {
			assertThat(BoyerMooreSearch.bmSearch(text, "成功"), is(-1));
		}

		@DisplayName("パターンの文字列の長さがテキストよりも大きい場合、-1が返ること")
		@Test
		void testPatternLongerThanText() {
			String longPattern = "これはテストです。This is a test. もう一度テストします。失敗";
			assertThat(BoyerMooreSearch.bmSearch(text, longPattern), is(-1));
		}

		@DisplayName("テキストが空の場合、-1が返ること")
		@Test
		void testTextIsEmpty() {
			assertThat(BoyerMooreSearch.bmSearch("", "テスト"), is(-1));
		}
	}

	@DisplayName("例外が投げられる場合")
	@Nested
	class ExceptionThrown {
		@DisplayName("渡されるパターンがnullの場合、NPEが投げられること")
		@Test
		void testPatternIsNull() {
			assertThrows(NullPointerException.class, () -> {
				BoyerMooreSearch.bmSearch(text, null);
			});
		}

		@DisplayName("渡されるテキストがnullの場合、NPEが投げられること")
		@Test
		void testTextIsNull() {
			assertThrows(NullPointerException.class, () -> {
				BoyerMooreSearch.bmSearch(null, "テスト");
			});
		}
	}
}

文字列探索（Boyer-Moore法）アルゴリズム

BoyerMooreSearch.java

public class BoyerMooreSearch {

	/**
	 * Boyer-Mooreアルゴリズムを用いて、指定されたテキスト内でパターンを検索する
	 * @param text 検索対象のテキスト
	 * @param pattern 検索したいパターン
	 * @return パターンがテキスト内で最初に出現する開始インデックス
	 */
	public static int bmSearch(String text, String pattern) {

		if (pattern.isEmpty()) {
			return 0;
		}

		int textIndex;
		int patternIndex;
		int[] skipTable = new int[Character.MAX_VALUE + 1];

		// スキップテーブルの作成
		// 全ての位置に対してパターンの長さを初期値として設定
		for (textIndex = 0; textIndex <= Character.MAX_VALUE; textIndex++) {
			skipTable[textIndex] = pattern.length();
		}
		for (textIndex = 0; textIndex < pattern.length(); textIndex++) {
			skipTable[pattern.charAt(textIndex)] = pattern.length() - textIndex - 1;
		}

		// テキスト内でパターンを探索
		textIndex = pattern.length() - 1; // パターンの末尾
		while (textIndex < text.length()) {
			// パターンの末尾から比較を開始
			patternIndex = pattern.length() - 1;

			while (patternIndex >= 0 && text.charAt(textIndex) == pattern.charAt(patternIndex)) {
				textIndex--;
				patternIndex--;
			}
			if (patternIndex < 0) {
				// パターンの末尾まで一致した場合、パターンが見つかっているので、
				// パターンが最初に出現する位置を返す
				return textIndex + 1;
			}
			// スキップテーブルと不一致の位置に基づいてパターンをシフト
			textIndex += Math.max(skipTable[text.charAt(textIndex)], pattern.length() - patternIndex);
		}
		return -1;
	}
}