$shibayu36->blog;

ある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万文字を超えても文字列マッチングできるようになった。アルゴリズムの力を実感できる。

興味本位で自分のアルゴリズム実装repository( https://github.com/shibayu36/algorithms )のテストをCircleCIで動かしてみようと考えた。基本的にCircleCIはcircle.ymlに設定を追加したら終わりなのだけど、何を設定すればいいか少し調べる必要があったのでメモ。

設定

Configuring CircleCI - CircleCI などを見ながら、最終的なcircle.ymlは以下のようになった。Circle CIでJavaを使ってビルドする | さにあらずや CircleCIでJUnitの結果を見る - Qiita あたりも参考になった。

machine:
  java:
    version: oraclejdk8
  timezone: Asia/Tokyo
  environment:
    GRADLE_OPTS: -Xmx4G
  post:
    - sudo service mysql stop
    - sudo service postgresql stop

checkout:
  post:
    - chmod +x ./gradlew

dependencies:
  override:
    - ./gradlew testClasses --stacktrace

test:
  override:
    - ./gradlew --full-stacktrace check
  post:
    - mkdir -p $CIRCLE_TEST_REPORTS/junit/
    - find . -type f -regex ".*/build/test-results/.*xml" -exec cp {} $CIRCLE_TEST_REPORTS/junit/ \;

まずmachineセクションでサーバのセットアップをする。

今ならoraclejdk8を設定したらJava8を利用できる
GRADLE_OPTSではヒープサイズを4GBに設定している
- https://circleci.com/docs/oom/ によると、メモリは4GBまで使えるので最大まで使えるように
- 昔はgradleのdaemonを起動するため-Dorg.gradle.daemon=trueも付けていたけど、今はデフォルトでdaemonが起動するため必要ないようだった
デフォルトでMySQLやPostgresが起動しているため、使えるメモリを増やすため、落としておく
- mongodも起動してそうだったので、落としても良いかも?

checkoutフェーズではgradlewの実行権限を追加するだけ。

dependenciesフェーズではテストの依存をインストールする。Gradleを使っていれば、./gradlew testClasses --stacktraceだけでOK。

testフェーズでは実際にテストを動かす。

テストだけじゃなくて静的解析系も動かすために./gradlew --full-stacktrace checkにしている
- プラグインを入れてなければ./gradlew --full-stacktrace testと同様っぽい？このあたりはちゃんと調べてない
- https://docs.gradle.org/current/userguide/java_plugin.html 見ると、Gradleタスクの詳細はわかりそう
$CIRCLE_TEST_REPORTSにテストレポートのxmlを突っ込むと、テストレポートをCircleCIで見れるようになるので、postフェーズにそれを記述
- https://circleci.com/docs/test-metadata/#gradle-junit-results

確認

これでテストが実行できるようになった。https://circleci.com/gh/shibayu36/algorithms で確認できた。

失敗すると https://circleci.com/gh/shibayu36/algorithms/5 な感じ
成功すると https://circleci.com/gh/shibayu36/algorithms/10 な感じ

まとめ

Java8 + Gradleプロジェクトで簡単にCI回せるようになって便利。

$shibayu36->blog;

クラスター株式会社のソフトウェアエンジニアです。エンジニアリングや読書などについて書いています。

勇者のクズ読んだ

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

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

実装とテスト

この方式の時間計算量

まとめ

CircleCIでJava8 + Gradleプロジェクトのテストを行う

設定

確認

まとめ

参考