Suffix Trieを使って文字列マッチングする

文字列マッチングを行うためのアルゴリズムとして、Suffix Trieを使った探索というものがある。これはテキストからSuffix Trieという構造を作り、パターンをつかってそれを辿ることで、パターンの長さmに対して、O(m)の計算量で探索できるものである。

今回はJavaでSuffix Trieを使った探索をしてみた。

トライ木とパトリシア

先にトライ木とパトリシアについて紹介。

今回Suffix Trieという構造を調べていると、同じような構造としてSuffix Treeというものが出てきて混乱した。よく調べてみると、Suffixの集合をトライ木という構造で実装したものがSuffix Trieで、パトリシアという構造で実装したものがSuffix Treeらしい。

トライ木はnodeを連結していって、その枝に1文字を割り当てて辿れるようにした構造。トライ木は枝に1文字しか割り当てない構造上非常にメモリを食うので、複数文字格納するようにしてメモリ効率をよくしたものをパトリシアと言うらしい。詳しくは以下を参照。

• http://www.geocities.jp/m_hiroi/light/pyalgo09.html
• https://ja.wikipedia.org/wiki/%E3%83%88%E3%83%A9%E3%82%A4%E6%9C%A8
• https://ja.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%9C%A8

枝に複数文字入れるということは、普通に実装が大変そうな予感がしたので、今回はトライ木構造を使うSuffix Trieの方を実装することにした。

Suffix Trieを使ったマッチングとは

Coursera の Algorithms on Strings 受けました - たにしきんぐダム のSuffix Trieの説明が分かりやすい。

まず、テキストの全てのSuffix集合を使ってトライ木を作る。これで例えば「nana」というテキストなら、上記の記事のような構造が出来る。

「Coursera の Algorithms on Strings 受けました」から引用

あとは「na」というパターンでマッチしようとすると、このトライ木を辿ったら以下のようになり、辿ったノードの下の全ての葉ノードの数字がマッチした位置となる。

他にも次の記事が参考になる。

• http://www.cs.jhu.edu/~langmea/resources/lecture_notes/tries_and_suffix_tries.pdf
• サービス終了のお知らせ

実装

次のフローで文字列マッチングが出来ることが分かった。

• 与えられたテキストからトライ木を構築する
• 与えられたパターンでトライ木を辿り、辿った全ての子ノードを返す

というわけで実装は以下のとおりとなる。new SuffixTrie(text)とするとトライ木が構築され、そのインスタンスでsearchPatternするとpositionのリストが返ってくるようになっている。 https://github.com/shibayu36/algorithm-study/tree/master/algorithms-on-string/src/main/java あたりにコードは置いてある。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

// new SuffixTrie(text).searchPattern(pattern)とすれば
// text中からpatternがどこに出現するかpositionのリストを返してくれる
public class SuffixTrie {
  public String text;
  public SuffixTrieNode root;

  public SuffixTrie(String text) {
    // 番兵を入れておけば、葉ノードからさらに枝が生えることがなくなるので
    // 構築や探索が楽になる。
    this.text = text + "\0"; // マッチングしやすいように番兵を入れておく
    this.root = new SuffixTrieNode();

    // 全てのSuffixを一つずつTrie木に追加していく
    for (int i = 0; i < this.text.length(); i++) {
      this.insertSuffix(new Suffix(this.text, i));
    }
  }

  // Suffix一つをTrie木に追加する
  private void insertSuffix(Suffix suffix) {
    SuffixTrieNode node = this.root;

    // 1文字ずつrootから辿りながらnodeを作成していく
    for (int i = 0; i < suffix.length(); i++) {
      Character c = suffix.charAt(i);
      if (node.children.containsKey(c)) {
        // 既に辿る枝があれば辿る
        node = node.children.get(c);
      }
      else {
        // なければ次のノードを作る
        SuffixTrieNode newNode = new SuffixTrieNode();
        node.children.put(c, newNode);
        node = newNode;
      }
    }

    // 辿った最後が葉なので、そこにSuffixのpositionを入れておく
    node.position = suffix.index;
  }

  // patternから出現するpositionのリストを返す
  public List<Integer> searchPattern(String pattern) {
    // まずpatternからマッチするnodeを取得する
    SuffixTrieNode matched = this.searchNode(pattern);
    if (matched != null) {
      // 取得したnodeの全ての葉ノードを取得すれば、positionのリストが得られる
      return matched.getAllLeafNodes().stream().map(
          node -> node.position
      ).collect(Collectors.toList());
    }
    else {
      return new ArrayList<>();
    }
  }

  // patternを辿ったnodeを返す
  // nodeが見つからなければnull
  private SuffixTrieNode searchNode(String pattern) {
    SuffixTrieNode node = this.root;
    for (int i = 0; i < pattern.length(); i++) {
      Character c = pattern.charAt(i);
      if (!node.children.containsKey(c)) {
        return null;
      }
      else {
        node = node.children.get(c);
      }
    }
    return node;
  }
}

class SuffixTrieNode {
  public int position; // どこからのsuffixの葉なのか
  public Map<Character, SuffixTrieNode> children = new HashMap<>();

  public SuffixTrieNode() {}

  public boolean isLeaf() {
    return this.children.isEmpty();
  }

  // あるノードの全ての葉ノードを返す
  public List<SuffixTrieNode> getAllLeafNodes() {
    if (this.isLeaf()) {
      List<SuffixTrieNode> nodes = new ArrayList<>();
      nodes.add(this);
      return nodes;
    }
    else {
      List<SuffixTrieNode> nodes = new ArrayList<>();
      for (SuffixTrieNode child : this.children.values()) {
        nodes.addAll(child.getAllLeafNodes());
      }
      return nodes;
    }
  }
}

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();
  }
}

実際に動かしてみる

実装は出来たので実際に動かしてみる。

まず自分のブログ記事を https://github.com/shibayu36/algorithm-study/blob/master/algorithms-on-string/blog1.txt においた。これから検索をしてみる。試したコードは以下のとおり。

import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Comparator;
import java.util.List;

public class SuffixTrieSearchSample {

  public static void main(String[] args) throws Exception {
    String text = "";

    try {
      byte[] fileContentBytes = Files.readAllBytes(Paths.get("./blog1.txt"));
      text = new String(fileContentBytes, StandardCharsets.UTF_8);
    } catch (Exception e) {}

    searchAndPrint(text, "基礎技術");
    System.out.println("");
    searchAndPrint(text, "モチベーション");
  }

  private static void searchAndPrint(String text, String pattern) {
    List<Integer> positions = new SuffixTrie(text).searchPattern(pattern);
    positions.sort(Comparator.naturalOrder());
    for (int position : positions) {
      int begin = Math.max(0, position - 5);
      int end = Math.min(text.length(), position + pattern.length() + 5);
      System.out.println(text.substring(begin, end));
    }
  }
}

結果は以下のようになり、正しく文字列マッチングできた。

基礎技術の学習のモ
寿命の長い基礎技術を、モチベ
の中でその基礎技術を実際のサ
開発の中で基礎技術との繋がり
寿命の長い基礎技術でも、モチ
ンを保って基礎技術を学習をす

術の学習のモチベーションをどう保つ
いないと、モチベーションをずっと保
が難しい
モチベーションが保てない
とりあえずモチベーションは保ちやす
きなければモチベーションを保つこと
礎技術を、モチベーションを保ちつづ
を得られ、モチベーションが増加する
で、さらにモチベーションを高められ
技術でも、モチベーションを保って学
どうやってモチベーションを保って基

このアルゴリズムの課題

このアルゴリズムは文字列マッチングの探索フェーズには早いスピードで探索できる一方で、トライ木の構築フェーズではn^2のメモリを使ったり、O(n^2)の計算量が必要になったりすることである。実際に1万文字程度の文章でマッチングしようとすると、メモリを使いすぎて固まってしまった。

このあたりはSuffix Treeや、Suffix Array、LCP Arrayを使うことで改善することが出来るようだ。

まとめ

今回はSuffix Trieによる文字列マッチングをJavaで実装してみた。とりあえずマッチングして動くようなものが出来たので満足。

以前、以下のような記事でSuffix ArrayやLCP Arrayの構築を試していた。これを使うと今回のメモリ効率や計算量の問題が改善されるので、これらの構造を使ったマッチングも実装してみたい。

• http://blog.shibayu36.org/entry/2016/12/29/19401
• suffix array構築のメモリ効率を良くする - アルゴリズム学習(その7) - $shibayu36->blog;
• 文字列マッチングのためのLCP Arrayを構築する - $shibayu36->blog;

これまでのアルゴリズム学習

• Javaで順列生成アルゴリズムを実装する - アルゴリズム学習(その1) - $shibayu36->blog;
• Javaで組み合わせを生成する - アルゴリズム学習(その2) - $shibayu36->blog;
• Javaで冪集合を生成する - アルゴリズム学習(その3) - $shibayu36->blog;
• Javaでスタックとキューを実装 - アルゴリズム学習(その4) - $shibayu36->blog;
• 力づく法・分割統治法・動的計画法 - アルゴリズム学習(その5) - $shibayu36->blog;
• suffix arrayを一番簡単なアルゴリズムで実装する - アルゴリズム学習(その6) - $shibayu36->blog;
• suffix array構築のメモリ効率を良くする - アルゴリズム学習(その7) - $shibayu36->blog;
• 文字列マッチングのためのLCP Arrayを構築する - $shibayu36->blog;

nanobenchを使ってJavaのベンチマークを取る

アルゴリズムを学習していると、ある実装の速度がどのくらいか計測したいことがよくある。これまでは、currentTimeMillisを利用して、愚直にベンチマークを取っていたのだけど、結構だるい感じだった。

調べてみると、jmh と nanobench という二つのツールがあった。jmhは使ってみたけど、非常に重厚で難しかったので、nanobenchを使ってみた。

ハマったこと

nanobench のREADME.mdを見ていると、nanobench.jarを落としてきて、以下のように実行すると良いと書いてある。

> javac ListBenchmark.java
> java -jar nanobench.jar ListBenchmark

しかし、Java初心者のためか、jarファイルのことがよく分からなかったり、classpathの問題でハマったり、とにかくハマりまくってうまく動かなかった。

また https://github.com/tokuhirom/nanobench/blob/master/examples/microbenchmarks/src/test/java/me/geso/microbenchmarks/HTMLEscapeTest.java に普通にIDEでも実行できそうなサンプルもあったのだが、今は動かなくなってしまっていた。

作戦と実装

とにかくIDEで出来たほうが手軽である。そこで、普通にmainメソッドが実装されたクラスを用意し、それを実行するとベンチマークをキックして実行してくれるようにしてみる。

まずはgradleでnanobenchを依存に追加しておく。

compile group: 'me.geso', name: 'nanobench', version: '0.2.0'

さらに以下のようにして、IDEで実行可能なベンチマークを作る。

src/main/java/ListBenchmark.java

import me.geso.nanobench.Benchmark;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;

public class ListBenchmark {

  public static void main(String[] args) throws Exception {
    // 10回warmupして3秒ずつベンチマークを取る
    // 内部クラスに実際のベンチマークを書いていく
    new Benchmark(new ListBenchmarkInner()).warmup(10).runByTime(3).timethese().cmpthese();
  }

  public static class ListBenchmarkInner {
    @Benchmark.Bench
    public void arrayList() {
      List<Integer> l = new ArrayList<>();
      for (int i = 0; i < 1_000_000; ++i) {
        l.add(i);
      }
    }

    @Benchmark.Bench
    public void linkedList() {
      List<Integer> l = new LinkedList<>();
      for (int i = 0; i < 1_000_000; ++i) {
        l.add(i);
      }
    }
  }
}

そしてmainをIDEから実行する。

Warm up: 10


Score:

arrayList:  3 wallclock secs ( 2.71 usr +  0.31 sys =  3.03 CPU) @ 125.92/s (n=381)
linkedList:  3 wallclock secs ( 3.10 usr +  0.02 sys =  3.12 CPU) @ 172.70/s (n=538)

Comparison chart:

               Rate  arrayList  linkedList
   arrayList  126/s         --        -27%
  linkedList  173/s        37%          --

これで、適当に内部クラスを作って、比べたいものごとにメソッドを追加していくだけで、ベンチマークを取れるようになった。Benchmark.pmのように簡単にベンチマークを取れて便利。

コードは https://github.com/shibayu36/java-playground/blob/master/src/main/java/ListBenchmark.java においてあるので、参考にどうぞ。

参考

• http://openjdk.java.net/projects/code-tools/jmh/
• https://github.com/tokuhirom/nanobench
• https://github.com/moznion/micro-html-escape/blob/7a74ac3fcce085332d478e7c38a9f9aac7eba276/author/BasicBench.java
• https://github.com/moznion/sprint-bench/blob/9ff61f5c6e5c2f566b716456a4a3d7566e5bb848/src/main/java/net/moznion/sprint/bench/BenchmarkApp.java

「世界でもっとも強力な9のアルゴリズム」読んだ

なんとなくアルゴリズム系の読み物読んでみたかったので読んだ。

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

この本は、著者が3つの基準で選んだ「偉大なアルゴリズム」について、エンジニアでなくても分かるような簡単な言葉を使って紹介してくれる本である。以下のようなアルゴリズムについて紹介している。

• 検索エンジンのインデクシング
• ページランク
• 公開鍵暗号法
• 誤り訂正符号
• パターン認識
• データ圧縮
• データベース
• デジタル署名

話題がかなり身近なものであり、説明が本当にわかりやすいため、とりあえずアルゴリズムを学ぶ前の読み物として非常におすすめ。個人的には検索エンジンやページランク、パターン認識あたりが興味深かった。この本を読んで、興味を持った部分について、さらに深く学習をしていくと良いかもと思った。

読書メモ

## 検索エンジンのインデクシング
- 検索エンジンの仕事の中で特に大きなものは、マッチングとランキングの2つ 324
- インデックスにページ番号と、ページ内の位置も保存している 411
    - これによりフレーズ検索もできる

## ページランク
- ページランクのランダムサーファーのシミュレーション 769

## パターン認識
- 最近傍法、決定木、ニューラルネットワーク 1649
- 標準的なアプローチは、パターン認識を「分類」の問題として扱うもの 1663
- 基本戦略は、大量の「分類ラベル付きデータ」をコンピュータに与えること 1691
- 最近傍法とは言葉通りに訓練データの中から最も近いものを探し、その分類を予測値とすること 1720
    - 最も近いk個を使う、k最近傍法もある
- 数字の文字認識なら、数字の間の空間的距離ではなく、数字のイメージの違いを計測するなどの方法がある 1743
- 決定木を訓練データを用いて作り上げる方法がある 1802
- ニューロンの性質 1845
    - 入力信号の合計が強ければ活性化する
    - 入力には「興奮性」のものと「抑制性」のものの二種類がある
- ニューロンの性質のようなネットワークを作ることをニューラルネットワークと呼ぶ 1869
- 重み付き信号 1901

## データ圧縮
- ロスレス圧縮
    - 前と同じトリック 2118
    - より短いシンボル 2158
- ロスあり圧縮 除外トリック 2250
- JPEGの除外トリック 2307

## データベース
- 先行書き込みログ(べき等になるように記述されている)を最初に作り、それを順に実行していくモデルにより、クラッシュしてもデータが不整合にならないようになっている 2551
- ロールバックは先行書き込みログを逆順に実行すればいい 2551 2666
- 2段階コミットプロトコル 2719

## デジタル署名
- べき乗を使ったデジタル署名 3134