文字列マッチングのためのLCP Arrayを構築する

前回のブログ記事で、文字列マッチングをするためのSuffix Arrayという構造を構築した。このSuffix Arrayという構造だけでも、テキスト長をn、パターン長をmとして、の計算量で文字列マッチングできるようになった。

• suffix arrayを一番簡単なアルゴリズムで実装する - アルゴリズム学習(その6) - $shibayu36->blog;
• suffix array構築のメモリ効率を良くする - アルゴリズム学習(その7) - $shibayu36->blog;

しかし、前処理としてSuffix ArrayからLCP Array(Longest Common Prefix Array)という構造をさらに作っておくと、という計算量で文字列マッチングが出来るようになるらしい。そこで、今回はLCP Array(Longest Common Prefix Array)の構築を実装してみる。今回はまだ構造構築までなので、文字列マッチングの実装はしていない。

実装は https://github.com/shibayu36/algorithm-study/tree/master/algorithms-on-string/src/main/java においてあるので、参考にどうぞ。

LCP Arrayとは

• https://en.wikipedia.org/wiki/LCP_array
• http://www.geocities.jp/m_hiroi/light/pyalgo60.html

あたりの説明が分かりやすい。「LCP ArrayとはSuffix Arrayにおいて、隣同士のSuffixの最長共通接頭辞の長さを格納した配列」とのこと。これを使うことでSuffix Arrayを構築するときよりも、さらに文字列マッチングの効率を上げることが出来る。

これだけだとよくわからないので、例を挙げてみる。例えばbananaというテキストがあったとすると、Suffixをソートしたものは以下のようになる。(Suffix Arrayはpositionを並べたものなので、[ 5, 3, 1, 0, 4, 2 ]になる)

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

すると、この並びで隣同士のSuffixで、最長共通接頭辞の長さを調べると

- aとanaなら1文字
- anaとananaなら3文字
- ananaとbananaなら0文字
- bananaとnaなら0文字
- naとnanaなら2文字

となるため、LCP Arrayは[ 1, 3, 0, 0, 2 ]となる。

単純なアルゴリズムを考える

では実際にLCP Arrayを構築してみる。単純に考えればSuffixをソートしたもの(suffixes)を使うと、以下のような順で構築できる。suffixesの配列長をnとしている。

• suffixes[0]とsuffixes[1]で、先頭から1文字ずつ比較し、一致した文字列長をlcpArray[0]に入れる
• suffixes[1]とsuffixes[2]で、先頭から1文字ずつ比較し、一致した文字列長をlcpArray[1]に入れる
• ...
• suffixes[n-2]とsuffixes[n-1]で、先頭から1文字ずつ比較し、一致した文字列長をlcpArray[n-2]に入れる

n-1番目のSuffixはsuffixes配列の最後なので、その次の比較対象がない。そのため、n-2番目とn-1番目の比較までで終了となる。

これをJavaで実装したものは以下のようになる。これで、検索したいテキスト(text)のSuffix Array(suffixArray)を先に作っておいて、LCPArray1.make(text, suffixArray)とすれば、LCP Arrayを取得することが出来る。

public class LCPArray1 {
  public static Integer[] make(String text, Integer[] suffixArray) {
    text += "\0"; // 番兵を入れておく

    int size = suffixArray.length;
    Integer[] lcpArray = new Integer[size];
    Arrays.fill(lcpArray, 0);
    for (int i = 0; i < size - 1; i++) {
      lcpArray[i] = calcLCP(text, suffixArray[i], suffixArray[i + 1]);
    }

    return lcpArray;
  }

  private static int calcLCP(String text, int pos1, int pos2) {
    int lcp = 0;
    while (text.charAt(pos1 + lcp) == text.charAt(pos2 + lcp)) {
      lcp++;
    }
    return lcp;
  }
}

これでひとまずLCP Arrayの生成はできた。しかし、この実装は、textの長さをnとすると、n回ループを回していて、かつcalcLCPでn文字分の比較があり得るので、時間計算量はである。そのため、この実装では遅くなる可能性があり、もっと速いアルゴリズムが求められる。

kasai's アルゴリズムで構築する

もっと速いアルゴリズムが必要であると書いたが、LCP Arrayの構築はkasai's アルゴリズムという、で計算できるアルゴリズムがある。そこでこちらも実装してみる。

この論文 でアルゴリズムが説明されていて、また http://www.geocities.jp/m_hiroi/light/pyalgo60.html の記事が日本語の説明として詳しい。

このアルゴリズムの基本としては、Suffixの長い順にループして計算していけば、前のループで計算したLCPを使って文字の比較回数を減らせるというものだ。

具体的に考える

しかし、論文や記事の説明だけを見てもよくわからないので、ひとまず具体的に先程のbananaの例を考えてみる。

まずbananaのSuffixをソートしたものは

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

だが、これを長い順に計算したい。つまり以下が計算順である。

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

計算は以下のようになり、先程と同様LCP Arrayは[ 1, 3, 0, 0, 2 ]となる。

- banana : na     (lcpArray[3]=0)
- anana  : banana (lcpArray[2]=0)
- nana   : null   (lcpArray[5]=なし)
- ana    : anana  (lcpArray[1]=3)
- na     : nana   (lcpArray[4]=2)
- a      : ana    (lcpArray[0]=1)

さて、よくよく見てみると、4行目の計算で比較しているanaとanana(LCP=3)から、それぞれ先頭1文字ずつ削ったものが次の比較であるnaとnanaとなっている。そのため、2文字目までは一致しているとみなして、3文字目から文字比較することで、文字の比較回数を減らせるということだ。ここまでが具体例を使った考え方である。

汎用的に考える

しかし、どんな場合でもこのように考えられるのか疑問に思えるので、もう少し汎用的に考えてみる。

まず、Suffix Arrayとして以下のように並んでいるとする。...はそれ以外のSuffixがたくさん並んでいるという意味で読んで欲しい。

- ...
- abcfh   (lcp=3)
- abcgdef
- ...

まずabcfhとabcgdefのそれぞれにおいて先頭一文字を削ったもの、つまりbcfhとbcgdefは、Suffix Arrayの性質上、もちろんSuffix Arrayのどこかに含まれる。

また、先頭が2文字以上マッチしていれば、先頭を1文字削っても辞書順は変わっていないはずである。つまり先頭一文字削ったものは以下のように並んでいるはずである。

- ...
- bcfh
- ...
- bcgdef
- ...

あとは、bcfhの隣も必ず先頭2文字は一致しているのかを考えたら良い。これもそこまで難しくなくて、Suffixが辞書順に並んでいるなら、bcfhとbcgdef間のSuffixは、少なくとも先頭はbcから始まっているよねということだ(それ以外から始まっていたらどうなるか試してみると理解できると思う)。

- ...
- bcfh
- bc????
- ...
- bcgdef
- ...

これらから、abcfhのLCPを計算したあと、それを一文字削ったbcfhのLCPを計算するときは、少なくとも2文字はマッチしていると考えて、3文字目から比較してもよいということになる。

ここまでを理解したら、この論文 も大体理解できるようになると思う。

実装する

ここまでをまとめると、次のように計算していけば良い。

• LCPはSuffixの長い順に計算する
• 前のループステップでLCPが2以上(1文字削ってもLCPが1以上)であれば、前のLCP-1分の文字比較はスキップしてその次から比較をスタートすれば良い
• 前のループステップでLCPが0か1なら、もう一度1文字目から比較していく

これをJavaで実装してみると以下のようになった。検索したいテキスト(text)のSuffix Array(suffixArray)を先に作っておいて、LCPArray2.make(text, suffixArray)とすれば、LCP Arrayを取得することが出来る。

public class LCPArray2 {
  public static Integer[] make(String text, Integer[] suffixArray) {
    text += "\0"; // 番兵を入れておく

    // 文字の長さ順にLCPを計算できるように、
    // suffixArray内のどこに位置するか、
    // 文字列長さ順に並べた配列を用意する
    int size = suffixArray.length;
    Integer[] rank = new Integer[size];
    for (int i = 0; i < size; i++) {
      rank[suffixArray[i]] = i;
    }

    Integer[] lcpArray = new Integer[size];
    int lcp = 0;
    for (int i = 0; i < size; i++) {
      // suffixArray中のindex番目のLCPを計算する
      int index = rank[i];
      int pos1 = suffixArray[index];
      // indexが最後なら、次の比較するものはないので、lcpは0で終わり
      if (index == size - 1) {
        lcpArray[index] = lcp = 0;
        continue;
      }

      int pos2 = suffixArray[index + 1];
      lcpArray[index] = lcp = calcLCP(text, pos1, pos2, lcp);

      // 次は一文字削ったものなので、lcpは1減らす
      lcp--;
      // lcpがもともと0か1なら、-1か0なので、そのときは1文字目から再開
      if (lcp <= 0) lcp = 0;
    }

    return lcpArray;
  }

  private static int calcLCP(String text, int pos1, int pos2, int lcp) {
    while (text.charAt(pos1 + lcp) == text.charAt(pos2 + lcp)) {
      lcp++;
    }
    return lcp;
  }
}

速度検証と考察

アルゴリズムの速度検証をやってみると、さらに理解が深まると思ったので、検証をしてみた。テストケースとしては

• bananapanamaという文字列を1000回繰り返したもの
• ランダムな100000文字
• https://ja.wikipedia.org/wiki/%E6%94%BF%E6%95%99%E5%88%86%E9%9B%A2%E3%81%AE%E6%AD%B4%E5%8F%B2 のテキスト全体
  • Wikipediaで一番長い文章はこれらしい
• 上記Wikipediaを2回繰り返したテキスト

調べることは、「文字の比較回数」と「全体の速度」とする。

ベンチマーク用のコードは次のとおり*1。

https://github.com/shibayu36/algorithm-study/blob/master/algorithms-on-string/src/test/java/LCPArrayBenchmark.java

public class LCPArrayBenchmark {
  @Test
  public void make() throws Exception {
    long begin;
    Integer[] suffixArray, lcpArray;
    String text = StringUtils.repeat("bananapanama", 1000);
    suffixArray = SuffixArray2.make(text);

    // warmup
    LCPArray1.make(text, suffixArray);
    LCPArray2.make(text, suffixArray);

    System.out.println("---- bananapanama x 1000 ----");
    begin = currentTimeMillis();
    lcpArray = LCPArray1.make(text, suffixArray);
    System.out.println("lcp array1 compareNum: " + LCPArray1.compareNum);
    System.out.println("lcp array1: " + (currentTimeMillis() - begin) + "ms");

    begin = currentTimeMillis();
    lcpArray = LCPArray2.make(text, suffixArray);
    System.out.println("lcp array2 compareNum: " + LCPArray2.compareNum);
    System.out.println("lcp array2: " + (currentTimeMillis() - begin) + "ms");

    System.out.println("---- random 100000 chars ----");
    text = RandomStringUtils.randomAlphabetic(100000);
    suffixArray = SuffixArray2.make(text);

    begin = currentTimeMillis();
    lcpArray = LCPArray1.make(text, suffixArray);
    System.out.println("lcp array1 compareNum: " + LCPArray1.compareNum);
    System.out.println("lcp array1: " + (currentTimeMillis() - begin) + "ms");

    begin = currentTimeMillis();
    lcpArray = LCPArray2.make(text, suffixArray);
    System.out.println("lcp array2 compareNum: " + LCPArray2.compareNum);
    System.out.println("lcp array2: " + (currentTimeMillis() - begin) + "ms");

    // 指定のファイル URL のファイルをバイト列として読み込む
    // sample.txtにhttps://ja.wikipedia.org/wiki/%E6%94%BF%E6%95%99%E5%88%86%E9%9B%A2%E3%81%AE%E6%AD%B4%E5%8F%B2 がコピペされているとする
    try {
      byte[] fileContentBytes = Files.readAllBytes(Paths.get("./sample.txt"));
// 読み込んだバイト列を UTF-8 でデコードして文字列にする
      text = new String(fileContentBytes, StandardCharsets.UTF_8);
    }
    catch (Exception e) {}
    suffixArray = SuffixArray2.make(text);

    System.out.println("---- Wikipedia ----");
    begin = currentTimeMillis();
    lcpArray = LCPArray1.make(text, suffixArray);
    System.out.println("lcp array1 compareNum: " + LCPArray1.compareNum);
    System.out.println("lcp array1: " + (currentTimeMillis() - begin) + "ms");

    begin = currentTimeMillis();
    lcpArray = LCPArray2.make(text, suffixArray);
    System.out.println("lcp array2 compareNum: " + LCPArray2.compareNum);
    System.out.println("lcp array2: " + (currentTimeMillis() - begin) + "ms");

    text = text + text;
    suffixArray = SuffixArray2.make(text);

    System.out.println("---- Wikipedia x 2 ----");
    begin = currentTimeMillis();
    lcpArray = LCPArray1.make(text, suffixArray);
    System.out.println("lcp array1 compareNum: " + LCPArray1.compareNum);
    System.out.println("lcp array1: " + (currentTimeMillis() - begin) + "ms");

    begin = currentTimeMillis();
    lcpArray = LCPArray2.make(text, suffixArray);
    System.out.println("lcp array2 compareNum: " + LCPArray2.compareNum);
    System.out.println("lcp array2: " + (currentTimeMillis() - begin) + "ms");
  }
}

実行結果は以下のようになった。

---- bananapanama x 1000 ----
lcp array1 compareNum: 71874078
lcp array1: 389ms
lcp array2 compareNum: 23994
lcp array2: 6ms
---- random 100000 chars ----
lcp array1 compareNum: 326219
lcp array1: 11ms
lcp array2 compareNum: 199947
lcp array2: 25ms
---- Wikipedia ----
lcp array1 compareNum: 785373
lcp array1: 32ms
lcp array2 compareNum: 311735
lcp array2: 49ms
---- Wikipedia x 2 ----
lcp array1 compareNum: -592799649
lcp array1: 29132ms
lcp array2 compareNum: 625309
lcp array2: 58ms

「banamapanama x 1000」と「Wikipedia x 2」はkasai'sアルゴリズムのほうが圧倒的に比較回数も少なく実行時間も短い。「Wikipedia x 2」の比較回数に関しては、longでもオーバーフローして負数になるくらいである。

一方で、「random 100000 chars」と「Wikipedia」に関しては、むしろkasai'sアルゴリズムのほうが若干遅くなってしまっている。

この結果から、kasai'sアルゴリズムの仕組みをもう一度考えてみると、kasai'sアルゴリズムはLCPの値が大きくなればなるほど、次ステップの比較を多くスキップ出来るものである。そのため、「banamapanama x 1000」と「Wikipedia x 2」のようなLCPが非常に大きくなるようなテキストでは非常に効率的になる。逆にLCPが大きくなりにくい「random 100000 chars」と「Wikipedia」に関しては、比較回数の差がそこまでつかないので、他の処理を行っている分、愚直なアルゴリズムのほうが速くなりうる。

この特性を考えると、例えば遺伝子構造のような、ほとんど同じような文字列が並んでいるけど、たまに違うといったようなテキストには、莫大な効果を上げられるのだろう。

まとめ

今回はsuffix arrayを一番簡単なアルゴリズムで実装する - アルゴリズム学習(その6) - $shibayu36->blog;とsuffix array構築のメモリ効率を良くする - アルゴリズム学習(その7) - $shibayu36->blog; の続きで、文字列マッチングの探索効率を上げるLCP Arrayの構築を実装してみた。ここまで来たので、次はSuffix ArrayとLCP Arrayを利用しての時間計算量の探索を実装してみようと思う。

参考

• https://en.wikipedia.org/wiki/LCP_array
• http://www.geocities.jp/m_hiroi/light/pyalgo60.html
• http://alumni.cs.ucr.edu/~rakthant/cs234/01_KLAAP_Linear%20time%20LCP.PDF
• http://www.geocities.jp/m_hiroi/light/pyalgo60.html

これまでの学習

• 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;

*1:正確に測定するには何度も動かして平均を取る必要があるが、今回は大体把握できたら良いので、この程度に留めた