$shibayu36->blog;

株式会社はてなでエンジニアをしています。プログラミングや読書のことなどについて書いています。

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

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

極大部分文字列とは何か

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

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

という感じだろうか。

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

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

まとめ

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

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