文字列アルゴリズムの学びかた

はてなエンジニアアドベントカレンダー2016

こんにちは！はてなアプリケーションエンジニアの id:takuya-a です。

みなさんは、このような疑問をもったことはありませんか？

  • grep はどのように文字列を検索しているのか？
  • MeCab はどうやって辞書を高速にルックアップしているのか？
  • パーサやコンパイラを作りたいけど、何から始めればいいのか？

本稿では、「文字列アルゴリズムとはどんなものなのか？」「なぜ重要なのか？」「何を知っておくべきか？」「どうやって勉強すればいいのか？」といった疑問にお答えしていこうと思います。

文字列アルゴリズムの意外な応用や、モチベーションを保ちやすい勉強のしかた、文字列アルゴリズムを勉強するために行った社内での取り組み、実装するときのコツといったトピックについても触れています。

このエントリは、はてなエンジニアアドベントカレンダー2016の22日目の記事です。昨日は id:syou6162 さんによる はてな社内で行なっている機械学習勉強会について紹介します でした。

文字列アルゴリズムとは

文字列処理は、プログラミングにおいて日常的に使われるわりには、文字列アルゴリズムについてはあまり知られていないように思います。くわしい説明は後にして、ここでは文字列アルゴリズムの分野をごく簡単に紹介します。

もっとも基本的な文字列アルゴリズムは、部分文字列検索（パターンマッチ）でしょう。 複数のファイルから検索する場合はとくに全文検索と呼ばれます。 とくに grep などの文字列検索ツールへの応用が有名ですね。

その他にも、パターンの数が数百万以上になっても高速に検索するアルゴリズムや、いくつかの文字の違いを許容するあいまい検索などの複雑な検索にも対応できるアルゴリズムもあります。

さらに、音声認識やデータ圧縮、時系列パターンマイニングといった、単なる文字列検索にとどまらない応用があり、数々のアルゴリズムの分野のなかでも文字列アルゴリズムは特に重要であると考えています。

なぜ文字列アルゴリズムを学ぶのか

ここでは応用先を中心に、文字列アルゴリズムを学ぶことでできるようになることを紹介します。以下のように多様な応用があります。

  • 全文検索
    • 検索エンジンには様々な応用がある
    • 転置インデックスの辞書やあいまい検索など
  • パーサ・コンパイラ
    • オートマトンの理論を共通の基礎とする
    • 自分の DSL を作ったり、独自のパーサを書いたり
  • 自然言語処理
    • 自然言語処理は文字列を扱うことが多いので、文字列アルゴリズムの重要度は高い
    • 形態素解析などには直接応用されている
  • 機械学習
    • 文字列（単語など）を素性とする機械学習で応用可能
    • 精度や前処理のパフォーマンス向上が狙える
  • 音声認識
  • パターンマイニング
    • 時系列データ解析・ログ解析など
    • 類似パターンや繰り返しのパターンを発見する
  • データ圧縮
    • bzip2 などの圧縮アルゴリズムに応用されている（文字列アルゴリズムの一種である BW 変換を利用）

これら以外にも、基礎を知っていれば意外なアプリケーションに利用できることもあります。たとえば、ISUCON6 で出題されたことが記憶に新しい、はてなキーワードのキーワードリンク作成（テキストのキーワード部分にリンクをつける処理）でも、後述するトライ木を利用することで高速に行うことができます。そのほか、テキスト中からn回以上現れるフレーズを高速に抽出する、などの応用もあります。

また、文字列アルゴリズムは、工夫すればバイナリにも適用することができます（「番兵とヌル文字」を参照）。つまり、アルゴリズムによっては、なんらかのデータの並び (sequence) でさえあれば適用できる可能性があります。あなたの発想次第で、意外なところが高速化できたり、アプリケーションをもっと大規模なデータに適用できるようになるかもしれません。

最初に知っておくべきこと

文字列アルゴリズムの世界は広大なので、そのすべてを一度に勉強するのは難しいと考えています。興味のある分野で関連領域をひとつずつ潰していくのがおすすめです。

基礎的な文字列アルゴリズムには、ざっと以下のようなものがあります。

  • 文字列のソート
  • 部分文字列検索（パターンマッチング）
  • 複数パターンマッチング・辞書データ構造
  • 正規表現マッチング
  • あいまい検索

まずは、具体的なアルゴリズムを勉強し始める前に、各アルゴリズムの特徴と使いどころをつかむところから始めましょう。それぞれに代表的なアルゴリズムを、後ほど特徴とともに簡単に説明します。また、思い立ったときにすぐ学習を始められるように、参考リンクなどのリソース集を併記しますので、興味が湧いたときにのぞいてみてください。

どうやって勉強するか

経験上、文字列アルゴリズムを勉強するモチベーションを保ち、理解していくうえで最も効果的だったのは、自分が作りたいものを実装してみる ことでした。

前職では全文検索エンジンを開発していたのですが、自分にとって一番のブラックボックスは形態素解析でした。形態素解析器の中身を知りたい！という興味から、Kuromoji という Java の形態素解析器のソースコードを読み始めたり、 NLP の資料や論文を読んでみたものの、「理解した！」と思うにはほど遠い状況でした。

そこで、自分が好きだった JavaScript で形態素解析器をゼロから書いてみようと思い立ち、ダブル配列（後述する、トライ木というデータ構造の一種）とビタビアルゴリズム（動的計画法の一種）による形態素解析器を実装しました。実装してみることで、処理のどこに時間がかかるのか、データはどのように保存されてどう読み出されるのかなど、形態素解析の動作が手に取るようにわかるようになりました（とはいえ、辞書のクセにはずっと翻弄され続けていますが…）。

目的とするアプリケーションの部品が組み上がっていくのは、とても楽しい経験でした。アルゴリズムだけを勉強しようとしていたとしたら、間違いなく挫折していたと思います。

ここで言いたかったのは、文字列アルゴリズムの教科書を開く前に、まず 作りたいものを探すことから始めるという勉強法もある 、ということです。 最初は簡単なアルゴリズムを応用したものでよいと思います。解きたい問題、作りたいアプリケーションによって、関連するアルゴリズム・分野を深掘りしていくと、教科書的に勉強するよりもはるかに深い理解が得られます（また、その副産物として新しい OSS ができることもあります）。

モチベーションを保つ上でもうひとつ重要なことは、「仲間を探す」ことです。ひとりで自分を高め続けるのはとても苦しいことですが、苦労や感動を共有できる人がひとりでもいれば、学習を継続できる確率は飛躍的に高まるでしょう。

社内勉強会の取り組みについて

「作りたいものを実装してみる」以外の、もうひとつの勉強法として、仲間を集めて勉強会を開催するという手があります。今回は、社内で実施している、文字列アルゴリズム勉強会の取り組みについて紹介します。

具体的には、カリフォルニア大学サンディエゴ校のオンライン講座 (MOOC) をみんなで受講しています。私は、文字列アルゴリズムのなかでもとくに接尾辞配列や、その関連アルゴリズムに苦手意識があったのですが、その勉強にちょうどいいオンライン講座をたまたま見つけました。それが Coursera で開講されている Algorithms on Strings です。社内で紹介したところ、幸い興味をもってくれた仲間を集めることができました。

機械学習の社内勉強会でも Coursera を活用していたこともあり、同じような形式で進めています。

  • 昼休みや夜に、講義ビデオをみんなで見る
  • わからないところは適宜ホワイトボードを使ったりして話し合う
  • 週末にプログラミング課題を実装する

この講座の一番いいところは、毎週プログラミング課題が出ることです。課題では、実装すべき関数の入力と出力が明確に決められており、本質的ではない部分はあらかじめ実装されている雛形が提供されています。これにより、 文字列アルゴリズムを実装するための心理的ハードルが極限まで下がっている状態 になっています。あとはやるだけです。

ひとつ残念な点は、無料で受講しているかぎり課題が採点されないことです！ただ、課題ができなくてずるずる遅れていく…といったことがないので、内容さえある程度理解していれば毎週気軽に参加できるというメリットもあります（もちろん実装したほうが理解は深まりますが）。

現在は（講座本来のペースからは遅れながらも）最終週までたどりつくことができています。なんとか年内には完走できそうです！

代表的な文字列アルゴリズム

ここでは、代表的なアルゴリズムについて、ひとこと解説と、参考になる学習リソースを示します。

最初は、この解説ではおそらく意味不明だと思いますので、興味が湧いたらぜひ参考リンクの記事や書籍を読んでみてください。

1. Brute Force による文字列マッチング

  • もっともシンプルな部分文字列検索アルゴリズム
  • 1文字ずつずらしながら部分文字列すべてとテキストの文字を比較する
  • 文字がマッチしなかったらテキストの次の位置をみる
  • Brute force algorithm

2. KMP による文字列マッチング

  • 文字位置をスキップすることで比較回数を減らす
  • 理論上は重要
  • 実用上は後述する BM 法、とくに Quick-Search (Sunday のアルゴリズム) が使われている
  • Algorithms on Strings の3週目で登場

3. BM (Boyer-Moore) による文字列マッチング

4. Bitap (Shift-And / Shift-Or) アルゴリズムによる文字列マッチング

5. Rabin-Karp (Rolling hash) による文字列マッチング

  • 工夫した多項式ハッシュ関数を用いることで、テキストの長さに対して線形時間で検索可能
  • 位置nからm文字の部分文字列のハッシュ値から、位置n+1(1つずらした)からm文字の部分文字列のハッシュ値を高速に（ O(1) で）計算できる
  • 位置をずらしていった、すべて(|Text| 個)の部分文字列のハッシュ値を O(|Text|) で計算できる
  • 詳しくは蟻本ことプログラミングコンテストチャレンジブック 第2版「4-7 文字列を華麗に扱う」を参照

6. トライ木 (Trie) による複数パターンマッチング

7. 正規表現のマッチング

  • とても表現力の高いパターンマッチが可能
  • 有限オートマトン (FSA) の理論と関係が深い
  • 正規表現エンジンの実装は大きくわけると DFA 型と VM 型という2種類がある
    • DFA 型：正規表現を決定性有限オートマトン (DFA) に変換し、その上での状態遷移をシミュレートする
    • VM 型： 正規表現を仮想マシン (VM) 上のバイトコードに変換し、 VM 上でのバイトコード実行をシミュレートする
  • 正規表現エンジンをどう実装するかについては、正規表現技術入門を読むのがおすすめ

8. 接尾辞配列 (Suffix Array)

  • 検索対象のテキストを接尾辞配列というデータ構造（元テキストと同じ長さの配列）に変換する
  • 接尾辞配列を使うと、パターンに対して2分探索で検索できるようになる
    • 大きなテキストに対しても高速
    • http://www.slideshare.net/nobu_k/suffix-arraysolr
    • 単純な実装では O(|Pattern| log |Text|)
    • LCP (Longest Common Prefix) 配列をあらかじめ計算して持っておくことで O(|Pattern| + log |Text|) になる
    • LCP 配列の計算については接尾辞木の項目を参照
  • 線形オーダー O(|Text|) で接尾辞配列を構築するアルゴリズムがある

9. 接尾辞木 (Suffix Tree)

10. BW 変換 (Burrows-Wheeler Transform)

  • bzip2 の前処理として利用されている
  • BW 変換後の文字列 (BWT) はテキストと同じ長さの文字列になる
    • このとき、同じ文字が並びやすくなる、つまり元の文字列にくらべて圧縮が効きやすくなる
    • (英語の場合) nd の前には a が来やすい、みたいな性質を使っている（and という単語が頻出するので）
  • BWT から元のテキストが復元できる（逆変換が可能）
    • First-Last Property という性質を利用した LF-mapping を使う
    • Algorithms on Strings の2週目のビデオがわかりやすい
  • SA-IS を使うことで O(|Text|) で計算可能

11. FM-index

  • 圧縮インデックス
  • 通常の転置インデックスに比べて、動的な更新は難しい
  • 高速文字列解析の世界 7.5.2 に FM-index を使った検索についての解説がある

文字列アルゴリズムを実装するときのコツ

実用的なアプリケーションやライブラリを作るのは、試しに実装するよりもはるかに大変です。ここでは、実装のコツをいくつか紹介します。

テストを書く

基本的なことですが、テストを書きましょう。一般的にアルゴリズム・データ構造の実装は、バグが入り込みやすく、潰すのは難しいです。とくに境界条件のテストは念入りに行うようにしましょう。

文字列アルゴリズムは基本的には関数単位で実装でき、入力と出力が明確です。そのため、複雑なアプリケーションに比べてテストが書きやすいといえます。テストがしっかりあって、試行錯誤しやすい状態になっていると、パフォーマンスチューニングも格段にやりやすくなります。

簡単なものから実装する

これも基本的なことですが、まず思いつく最も簡単な実装を行い、そのあと効率的なコード・複雑なアルゴリズムを書きます。

文字列検索を考えたとき、まず最初に実装すべきは、力まかせ (Brute Force) による部分文字列検索です。複雑なアルゴリズムに進む前に、文字列アルゴリズムのもっとも基本的な道具である、以下の3つを使いこなせるようにしておきます。

  • 文字列から文字へのインデックスアクセス (charAt)
  • 文字列の長さ (length)
  • 文字の比較

「簡単なものから実装する」というルールは、他のアルゴリズムを実装するときにも使えます。「早すぎる最適化を避ける」というのは、ソフトウェア開発におけるベストプラクティスのひとつでもありますよね（なかなか実践できないことでも有名ですが）。

また、他の文字列検索アルゴリズムを実装するときのベースラインにもなります。「推測するな、計測せよ」という格言もありますが、より高度なアルゴリズムを実装するとき、ベースラインからどれくらい速くなったかは重要です。また、速いアルゴリズムを実装したはずなのにそんなに速くなってない、といったケースでバグを早期に発見できることがあります。

マルチバイト文字の扱い

  • 可変長の符号化方式を使っている場合は、文字単位でのインデックスアクセスが困難
  • Unicode であれば UTF-16/UTF-8 が主流
    • UTF-32 なら困難はない（固定長なので）
  • UTF-16/UTF-8 は可変長の符号体系
    • UTF-16: サロゲートペア
    • UTF-8: 1文字のサイズが可変(1バイト〜4バイト)
  • 検索結果として得られる位置は文字の位置ではない
    • UTF-16: サロゲートペアがない場合は文字の位置と一致
    • UTF-8: 位置はバイト配列の何バイト目かを表すにすぎない
  • UTF-16/UTF-8 であれば、文字の内部でヒットすることを避けられる
    • UTF-8: 文字の1バイト目かそうでないかが判定できる符号体系（ビット演算で判定可能）
    • UTF-16: 2バイトのコードポイントで判定できる符号体系
  • Unicode のサロゲートペアとは何か - ひだまりソケットは壊れない

番兵とヌル文字

アルゴリズムによっては番兵（何かしらの区切りや終端を表現する文字）が必要なものがあります。このとき、文字列中のどんな文字でもない文字を番兵として使うことになります。ヌル文字 \0 を使うことが多いようです。

しかし、バイナリに対して文字列アルゴリズムを適用したい場合、これが問題になります。バイナリを文字列として捉え、その中から検索したいとします。すると、バイナリには \0 が現れないことを保証できないため、番兵が用をなさなくなってしまいます。

つまり、バイナリも扱いたい場合は、番兵を陽に使わないような工夫が必要なのですが、アルゴリズムによって対処方法は異なりますし、実装難易度は跳ね上がります。頑張りましょう。

さらに学ぶために

まとめ

  • アルゴリズムを勉強するには、なにより実装してみることが大事
    • grep などの文字列検索アルゴリズムが具体的にイメージできるようになる
    • アルゴリズムをより深く理解できる
    • モチベーションを保ちやすい
  • 社内では文字列アルゴリズムの勉強にも Coursera を活用しています
    • わかりやすい講義ビデオ、雛形を用意してくれている課題
    • モチベーションまではコントロールしてくれない
    • 仲間を集めるなどの工夫もあるとよいですね
  • 抑えておくべき文字列アルゴリズムを簡単に紹介しました
    • 他にもおすすめのアルゴリズムがあれば教えてください！

はてなでは文字列が好きなエンジニアを募集しています。

hatenacorp.jp

明日のアドベントカレンダーは id:takuji31 さんです！