$shibayu36->blog;

最近、コンピュータサイエンスなどの基礎的な知識を学習するように心がけている。できる限り今後も長い期間役に立つ、寿命の長い技術や知識を付けておきたいためである。その一貫でアルゴリズムを学習してみている。

学習をはじめて感じた課題

しかし、とりあえずアルゴリズムを学習してみると、学習を続けられるか分からないという課題も感じた。

寿命の長い技術であるほど、日々の開発にすぐに利用できないことが多い
- 例えばアルゴリズムを学んだとしても、それが役立つまでいくにはある程度長い時間が必要
日々の開発に利用できていないと、モチベーションをずっと保ち続けるのが難しい
モチベーションが保てないと、結局途中で勉強をやめてしまい、日々の開発に利用できるレベルまでたどり着けない

流行りの技術とかは、すぐに開発に導入してみるとかができるので、とりあえずモチベーションは保ちやすい。しかし、数学とかアルゴリズムとかLinux カーネルの内部構造とかは、ずっと勉強していればほぼ確実に役立ちそうだけど、日々の開発にずっと利用できなければモチベーションを保つことが難しい。

では、どうすれば寿命の長い基礎技術を、モチベーションを保ちつづけながら学習し続けることができるのだろうか。

自分の中の解決策

それで最近いろいろ考えてみたのだけど、自分の中では「正に今開発をしているサービスの分野の、基礎分野を学習していく」と良いではないかと考え始めた。

例えば、小説投稿サービスは文字を扱う分野である。そこで、ざっくりアルゴリズム全体を学ぼうとせず、アルゴリズムの中でも特に文字に関係することを学んだり、全文検索エンジンの中身を学ぶようにする。他にも、ソーシャルな要素が強いサービスならグラフのアルゴリズムを学んだり、AWSをメインで運用するならOSの仕組みやネットワークの仕組みなどを学ぶなどが考えられる。

このようにすると、自分の中でその基礎技術を実際のサービスに利用できるレベルまでいかなかったとしても、実際のサービス開発の中で基礎技術との繋がりを見つけたりすることがある。繋がりを見つけられると、日々の開発で少しは役立った感を得られ、モチベーションが増加する。さらに、もしかしたらこういう風に応用できるかも？という夢想も出来ることもあり、それを試してみることで、さらにモチベーションを高められる。

このようなことを繰り返していくと、寿命の長い基礎技術でも、モチベーションを保って学習を続けられるのではないかと思った。

まとめ

どうやってモチベーションを保って基礎技術を学習をするかという点が最近の課題だった。ひとまず自分の中で指針を作ることが出来た。今は小説を扱うサービスを担当しているので、ひとまず文字列アルゴリズムや全文検索の中身を学習していくことから始めようかなと思う。

今は文字列マッチングの学習をしているので、これが一段落ついたら、検索エンジン自作入門を読みながら、自分で実装してみたい。

検索エンジン自作入門 ~手を動かしながら見渡す検索の舞台裏

作者:山田浩之,末永匡
技術評論社

Amazon

LCP Arrayとは

あたりの説明が分かりやすい。「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文字分の比較があり得るので、時間計算量は ${\mathcal{O} ( n ^ 2 ) }$ である。そのため、この実装では遅くなる可能性があり、もっと速いアルゴリズムが求められる。

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

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

この論文でアルゴリズムが説明されていて、また 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を利用して ${\mathcal{O} ( m + \log n ) }$ の時間計算量の探索を実装してみようと思う。

参考

これまでの学習

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