Suffix Arrayを使った文字列マッチング

あるPatternがあるText中のどこに含まれるかという文字列マッチングの実装を最近してみている。前回、Suffix Trieでの文字列マッチングを行った。

blog.shibayu36.org

Suffix Trieを利用すると、Suffix Trieを最初に構築したあと、実際にパターンを検索するのはO(|Patternの長さ|)の時間計算量で文字列マッチング出来た。しかし、Suffix Trieを保持するために非常に多くのメモリを使用するため、あまり長いTextに適用できないという問題があった。

同じように文字列マッチングをする方法としてSuffix Arrayという構造を使う方法がある。Suffix Arrayの構造のメモリ使用量は|Text|の長さ * (IntかLongのバイト数)程度となり、メモリ使用量の問題を軽減することができる。そこで今回はSuffix Array構造を利用した文字列マッチングをしてみる。

Suffix Arrayを利用した文字列マッチングのイメージ

Suffix Arrayのマッチングの詳細については接尾辞配列 - Wikipedia やサービス終了のお知らせなどを参照してもらうとして、本記事では具体例をイメージするだけに留める。

Suffix Arrayはテキストの接尾辞集合を表すため、接尾辞が渡されたパターンから始まっていればマッチするというのが基本的な考え方である。

イメージを付けるために、Suffix Arrayを利用した文字列マッチングの具体例を上げてみる。今回はbananaというテキストから、anaというパターンを検索してみる。

bananaに接尾辞を辞書順ソートしたものは次のとおり。positionはテキスト中のどこから始まっているかを指す。ただし、パターン検索する時のコードを簡単にするために、$という番兵をテキストに入れている。

- $       (position=6)
- a$      (position=5)
- ana$    (position=3)
- anana$  (position=1)
- banana$ (position=0)
- na$     (position=4)
- nana$   (position=2)

あとはanaから始まる接尾辞を二分探索していく。二分探索の様子を以下に示す。

- $       (position=6) <- left
- a$      (position=5)
- ana$    (position=3)
- anana$  (position=1) <- middle (ana < anana$)
- banana$ (position=0)
- na$     (position=4)
- nana$   (position=2) <- right

- $       (position=6) <- left
- a$      (position=5) <- middle (ana > a$)
- ana$    (position=3)
- anana$  (position=1) <- right
- banana$ (position=0)
- na$     (position=4)
- nana$   (position=2)

- $       (position=6)
- a$      (position=5) <- left
- ana$    (position=3) <- middle (ana < ana$)
- anana$  (position=1) <- right
- banana$ (position=0)
- na$     (position=4)
- nana$   (position=2)

- $       (position=6)
- a$      (position=5) <- left
- ana$    (position=3) <- right
- anana$  (position=1)
- banana$ (position=0)
- na$     (position=4)
- nana$   (position=2)

あとはrightの場所からincrementしながら、anaが先頭一致するもの全てを探す。

- $       (position=6)
- a$      (position=5)
- ana$    (position=3) <- ana$はanaから始まるのでマッチ
- anana$  (position=1) <- anana$はanaから始まるのでマッチ
- banana$ (position=0) <- banana$はanaから始まらないのでマッチしない。辞書順に並んでいるため、これ以降は確実にanaから始まらないため、ここで探索終了。
- na$     (position=4)
- nana$   (position=2)

これによって探索結果は、文字列のposition 3と1となり、実際にbananaは0オリジンで1と3のいちにanaが存在するので、正しく探索できている。

実装とテスト

イメージはついたので、実装をする。コードは https://github.com/shibayu36/algorithms においている。

package org.shibayu36.algorithms;

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

public class SuffixArraySearch {
v  private Integer[] suffixArray;
  private String text;

  public SuffixArraySearch(String text) {
    // patternとsuffixが一致することがない方が
    // 探索がやりやすいので、番兵を入れておく
    this.text = text + "\0";

    // コンストラクタでSuffixArrayを構築する
    int n = this.text.length();
    Suffix[] suffixes = new Suffix[n];
    for (int i = 0; i < n; i++) {
      suffixes[i] = new Suffix(this.text, i);
    }
    Arrays.sort(suffixes);
    this.suffixArray = Arrays.stream(suffixes)
        .map(s -> s.index)
        .toArray(size -> new Integer[size]);
  }

  public List<Integer> searchPattern(String pattern) {
    if (pattern.length() == 0) {
      // patternが空文字なら全マッチ
      // ただし番兵の入った1番目は除く
      List<Integer> positions = new ArrayList<>(Arrays.asList(this.suffixArray));
      positions.remove(0);
      return positions;
    }

    // 二分探索をしながら、prefixがマッチしうる
    // 場所を探し出す
    int left = 0;
    int right = this.suffixArray.length - 1;
    while (right - left > 1) {
      int middle = (left + right) / 2;
      String suffix = this.text.substring(this.suffixArray[middle]);
      if (pattern.compareTo(suffix) > 0) {
        left = middle;
      }
      else {
        right = middle;
      }
    }

    // prefixがマッチするとしたらrightからなので
    // rightからprefixがマッチする限り、positionsに追加
    List<Integer> positions = new ArrayList<>();
    int index = right;
    while (true) {
      if (index >= this.suffixArray.length) break;
      if (!this.text.startsWith(pattern, this.suffixArray[index])) break;
      positions.add(this.suffixArray[index]);
      index++;
    }

    return positions;
  }
}

class Suffix implements Comparable<Suffix> {
  public String text;
  public int index;

  public Suffix(String text, int index) {
    this.text = text;
    this.index = index;
  }
  public int length() {
    return text.length() - index;
  }
  public char charAt(int i) {
    return text.charAt(index + i);
  }

  public int compareTo(Suffix that) {
    if (this == that) return 0;  // optimization
    int n = Math.min(this.length(), that.length());
    for (int i = 0; i < n; i++) {
      if (this.charAt(i) < that.charAt(i)) return -1;
      if (this.charAt(i) > that.charAt(i)) return +1;
    }
    return this.length() - that.length();
  }

  public String toString() {
    return this.text.substring(this.index);
  }
}

テストは以下のとおり。テストのためにblog1.txtには、適当なデータを入れてみている。

package org.shibayu36.algorithms;

import static org.assertj.core.api.Assertions.assertThat;

import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.List;
import org.junit.Test;

public class SuffixArraySearchTest {

  @Test
  public void searchPatternForEmpty() throws Exception {
    SuffixArraySearch search = new SuffixArraySearch("");
    List<Integer> positions;

    positions = search.searchPattern("");
    assertThat(positions).isEmpty();

    positions = search.searchPattern("pattern");
    assertThat(positions).isEmpty();
  }

  @Test
  public void searchPatternForBanana() throws Exception {
    SuffixArraySearch search = new SuffixArraySearch("banana");
    List<Integer> positions;

    positions = search.searchPattern("");
    assertThat(positions).containsExactlyInAnyOrder(0, 1, 2, 3, 4, 5);

    positions = search.searchPattern("a");
    assertThat(positions).containsExactlyInAnyOrder(1, 3, 5);

    positions = search.searchPattern("na");
    assertThat(positions).containsExactlyInAnyOrder(2, 4);

    positions = search.searchPattern("ana");
    assertThat(positions).containsExactlyInAnyOrder(1, 3);

    positions = search.searchPattern("banana");
    assertThat(positions).containsExactlyInAnyOrder(0);

    positions = search.searchPattern("bananana");
    assertThat(positions).isEmpty();
  }

  @Test
  public void searchPatternForBlogSample() throws Exception {
    String text = "";

    // 指定のファイル URL のファイルをバイト列として読み込む
    try {
      byte[] fileContentBytes = Files.readAllBytes(Paths.get("./blog1.txt"));
      // 読み込んだバイト列を UTF-8 でデコードして文字列にする
      text = new String(fileContentBytes, StandardCharsets.UTF_8);
    } catch (Exception e) {}

    SuffixArraySearch search = new SuffixArraySearch(text);
    List<Integer> positions;

    positions = search.searchPattern("基礎技術");
    assertThat(positions).containsExactlyInAnyOrder(0, 518, 835, 881, 1039, 1097);
    for (int i : positions) {
      assertThat(text.substring(i)).startsWith("基礎技術");
    }

    positions = search.searchPattern("モチベーション");
    assertThat(positions).containsExactlyInAnyOrder(8, 287, 309, 398, 487, 524, 935, 1002, 1046, 1086);
    for (int i : positions) {
      assertThat(text.substring(i)).startsWith("モチベーション");
    }

    positions = search.searchPattern("正に今開発をしているサービスの分野");
    assertThat(positions).containsExactlyInAnyOrder(594);
    for (int i : positions) {
      assertThat(text.substring(i)).startsWith("正に今開発をしているサービスの分野");
    }
  }
}

この方式の時間計算量

この方式の時間計算量はSuffix Arrayの構築と、パターンの探索に分けられる。

パターンの探索は、二分探索をし、さらに毎回のパターンの長さ分文字列比較するので、O(|Patternの長さ| * log(|Textの長さ|))となる。

これらにより、Suffix Trieとくらべてメモリ使用量は改善されたが、探索効率は少々悪くはなった。ただし、Suffix Trieの場合、1万文字程度のテキストでもメモリ使用量が多すぎてマッチング自体ができなかったが、Suffix Arrayの方式であればWikipediaで一番文字が多いページ(16万字ほど) の検索も普通に行うことが出来た。

実際にこちらのコードで、Wikipediaで一番文字が多いページの文字列マッチングをするベンチマークを簡単に取ってみた。

constructAndSearch:  3 wallclock secs ( 2.99 usr +  0.06 sys =  3.05 CPU) @ 13.44/s (n=41)
onlySearch:  3 wallclock secs ( 3.08 usr +  0.05 sys =  3.13 CPU) @ 789.59/s (n=2469)

Comparison chart:

                        Rate  constructAndSearch  onlySearch
  constructAndSearch  13.4/s                  --        -98%
          onlySearch   790/s               5775%          --

一回のオペレーションで4パターン検索するようになっているので、

SuffixArray構造を作って4パターン検索するのは、秒間13回程度できた
既にSuffixArrayを作ってあれば、790 * 4 = 3160回ほどパターン検索できた

という結果となった。SuffixArray構造を作るのはやはり遅いが、これは別のアルゴリズムを採用することでさらに速くできるだろう。

まとめ

今回はSuffix Arrayという構造を利用して文字列マッチングする方法を実際に実装してみた。Suffix Trieを使った方法では1万文字程度のテキストに対してもメモリ使用量の問題でマッチングができなかったが、今回の手法では10万文字を超えても文字列マッチングできるようになった。アルゴリズムの力を実感できる。