$shibayu36->blog;

クラスター株式会社のソフトウェアエンジニアです。エンジニアリングや読書などについて書いています。

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

tech

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

極大部分文字列とは何か

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

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

という感じだろうか。

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

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

まとめ

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

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

参考

田中圭一さんの「うつヌケ」を読んで欲しい

book

田中圭一さんの「うつヌケ」というコミックエッセイを読んだ。とにかくむちゃくちゃ良かった。

うつヌケ　うつトンネルを抜けた人たち　【電子書籍限定　フルカラーバージョン】 (角川書店単行本)

うつヌケ　うつトンネルを抜けた人たち　【電子書籍限定　フルカラーバージョン】 (角川書店単行本)

Amazon

いろんな人にインタビューしていて、それぞれごとに「なぜうつ病になったか」「うつ病になってどうなったか」「どうやってうつ病から脱出できたか」が語られる。そのため、うつ病になっている人がどうやって戻ればいいかとか、うつ病になりそうなのをどう止めるかなどを知ることができる。ちなみに自分はうつ病経験者で、2か月ほど休職もしているので、全ての事例であるある集を眺めている感じだった。

今まさにうつ病に苦しんでいる人も参考になると思うけど、個人的には次のようなうつ病になりやすそうな人にこそ読んでして欲しいと思った。

  • 劣等感を感じやすい人
  • 責任感の強い人
  • ちょっとしたことで不安を感じやすい人
  • 不眠や過眠を経験したことがある人
  • 朝起きて今日一日嫌だなーと思ったことのある人
  • etc

以上のような人は、いつでもうつ病になる可能性があると僕は思っている。そういう人に、他人にヘルプを出すハードルや、病院に行くハードルを下げてもらうためにも是非読んで欲しい。ヘルプを出せたり、うまく逃げることさえ出来れば、うつ病で死ぬこともないと思う。

何度も言うけど、最近ちょっとでも精神的に辛いと思っている人はとにかく読んでくれ。

「数学ガール/乱択アルゴリズム」を読んだ

tech book

アルゴリズム読み物を読みたくて、いろんなところでオススメされている数学ガールの乱択アルゴリズムを読んだ。なかなか興味深かった。

数学ガール/乱択アルゴリズム (数学ガールシリーズ 4)

数学ガール/乱択アルゴリズム (数学ガールシリーズ 4)

Amazon

この本で興味深かったことは以下の二点。

  • 具体例 -> 規則性 -> 一般化で考える
  • アルゴリズムの実行ステップ数の数学的な解析

具体例 -> 規則性 -> 一般化で考える

この本で、問題を考えるときは、具体例を考える -> 規則性を見つけ出す -> 一般化する、という3ステップで考える、ということが書かれていた。

例えば「n枚のカードを一列に並べる方法は、全部で何通りあるか」という問題を考えてみる。この時、n枚のカードのまま一般的に考えようとしてよく分からなくなってしまうという失敗をしてしまうことが多い。そうではなくて、

  • まずは1枚ならどうか、2枚ならどうか、3枚ならどうかと具体例を考える
  • 具体例を見つめて、規則性を探し、イメージを付ける
  • 最後にnの場合でどうなるか、一般化して考える

と、3ステップで考えると良い。


このことは非常に当たり前のことなんだけど、なぜかいつも慌てて一般的に考えて理解不能に陥ることが多い。そのようにならないように、具体例 -> 規則性 -> 一般化という言葉を頭に留めておきたい。

アルゴリズムの実行ステップ数の数学的な解析

この本で特に興味深かったのは、アルゴリズムの実行ステップ数を解析する部分。普通のアルゴリズムの書籍だと、ループの回数の解析でリニアサーチはO(n)、バイナリサーチはO(log n)、バブルソートはO(n^2)、クイックソートはO(n log n)のように説明されていることが多い。しかし、この本では擬似コードの1行1行の実行ステップ数を考え、それを数学的に計算することでオーダーを求めるという、別視点での解析をしている。解析方法にもいろいろあることが知れたのが良かった。

以下のアルゴリズムを数学的に解析しているので、興味があれば読んでみると良さそう。

まとめ

アルゴリズム読み物として、数学ガール/乱択アルゴリズムを読んだ。読み物はいくつも読んだし、少し飽きてきた部分もあるので、とりあえずアルゴリズム読み物系は置いておき、本格的にアルゴリズムの勉強をしようかなと思う。

今は文字列関係のアルゴリズムに一番興味があり、また最近Elasticsearchを触ることもあったので、全文検索エンジンを実装することでアルゴリズムの学習を進めていきたい。あとdiffのアルゴリズムも興味があるので、そのあたりも機会があったらやっていきたい。あとはきちんとアルゴリズムクイックリファレンスを読んでおきたい。

[asin:4774167533:detail]

diffの動作原理を知る～どのようにして差分を導き出すのか：一般記事｜gihyo.jp … 技術評論社

アルゴリズムクイックリファレンス 第2版

アルゴリズムクイックリファレンス 第2版

Amazon

読書ノート

  • アルゴリズムの持っている特徴は、入力・出力・明確性・実効性・有限性 41
    • 入力があると、その出力が存在する
    • 手順が明確である
    • 手順を実際に行うことができる
    • 実行時間が有限である
  • 40ページから、リニアサーチのアルゴリズムの解析が始まる。ここでいつもだったら特に検討せずにO(n)とか話すことが多いが、ちゃんと実行ステップを計算していくのが良い。
  • 問題を考えるときは、具体例を考える -> 規則性を見つけ出す -> 一般化する、というフローで考えていく 73
  • オーダーの記法
    • Θ記法: ちょうどf(n)のオーダー
    • Ω記法: 少なくともf(n)のオーダー
    • O記法 : たかだかf(n)のオーダー
  • オーダーを表す時、logに底を書かない理由 203
  • バイナリサーチの実行ステップ数を数学的に解析する方法が210から始まる 210
  • バブルソートの実行ステップ数の解析 225
  • 比較ソートの最大比較回数が少なくともn * lognのオーダーになるかを、比較木を利用して証明する 229
  • クイックソートの実行ステップ数を数学的に解析する 390