極大部分文字列について調べた

社内の技術勉強会で極大部分文字列というワードが出てきたので、自分で調べた内容をメモ。内容があっているかは保証しない。

極大部分文字列とは何か

定義は全ての部分文字列を考慮した文書分類に書いてある
- これによると、「極大部分文字列の必要十分条件は，その部分文字列が内部節点に対応し，かつ，その節点に対応するBWT 配列が二種類以上の異なる文字を持つ場合である．」
- この論文の説明だけだとちょっと分かりにくい
実際に算出している例は http://d.hatena.ne.jp/takeda25/20101202/1291269994 。定義だけだとわかりにくいので、こちらを見ると理解しやすい。

極大部分文字列の算出を、自分の言葉で考えてみると

Suffix Treeのrootから特定節点までの文字列は、ある文字列中に少なくとも2回は出てくるパターンなので、極大部分文字列候補となる
BWTを見ると、あるSuffixの前の文字が分かる。BWTが一致していたなら、そのパターンはもう一文字大きいパターンに包含され、それは極大部分文字列とみなさない。

という感じだろうか。

極大部分文字列が何に役立つか

極大部分文字列がどういうときに使われるかを軽く調べると、以下のようなものがあった。基本的にはある文章の特徴抽出で、形態素解析やn-gramと対比して使われているようだった。

全ての部分文字列を考慮した文書分類
- https://ipsj.ixsq.nii.ac.jp/ej/?action=pages_view_main&active_action=repository_view_main_item_detail&item_id=47681&item_no=1&page_id=13&block_id=8
- 既存の形態素解析やN-gramを使った文書分類との比較で、極大部分文字列を使った文書分類を試みている
- 形態素解析がうまくいかない文書(日本語で未知語がたくさんあるとか)でも、文書分類の精度が上げられるとか
- 映画タイトルとかは一つの単位になってくれたほうが文書分類はやりやすいが、形態素として解析されてしまうと映画タイトルが分断されてしまい、適切な単位を得られない。極大部分文字列なら適切な単位が得られうるとか
極大部分文字列を使ったtwitter言語判定
- http://www.slideshare.net/shuyo/nlp2012-twitter-languagedetectionslide
- 3-gramをベースとした手法だとTwitterの言語判定が難しいので、極大部分文字列を利用している
極大部分文字列を用いた Web テキストの語義曖昧性解消
- http://www.anlp.jp/proceedings/annual_meeting/2012/pdf_dir/D5-2.pdf

まとめ

極大部分文字列について調べようとしたら、少し前に学習したSuffix Treeの内部ノードとなる条件や、BWTはSuffixの前の文字であるという特性がイメージできていたため、スムーズに理解が進んだ。このように、あるアルゴリズムの基本的な特性を覚えておくと、他のアルゴリズムや応用の理解がしやすくなるということを感じた。

あるアルゴリズムが「何に使われるか」だけではなく、「どうしてそのように使えるのか」について考えておくと、基本的な特性が学べる。そこまで深掘りしておけば、応用の学習をするときの理解の手助けになることが今回体験できた。今後も地道に基礎技術を学習していきたい。