早く卒論書けって言われた・・

  1. Suffix Treeの性質と作り方を理解
  2. O(k^2n)のアルゴリズムを実装
    • 論文のためのアルゴリズムで実装は遅いだろうという結論に達した。
  3. シンプルで遅いアルゴリズムも実装
  4. いくつかの特徴的なテキストで2つの速度を比較
  5. ミスなし回文をWikipedia青空文庫から探索
  6. ミスあり回文も同様に調べる
  7. 実装したものをRailsに乗っける
  8. 卒論を書く


間違いの数を例えば2としたときにあるテキストから回文を探すのにハミング距離を用いたときと、レーベンシュタイン距離を用いたときでは当然検出数はレーベンシュタイン距離の方が多くなるはずである。実際試してみるとそうなるが、あるフィルタリングをかけるとこの関係が逆になってしまう。今行っているフィルタリングは例えばこういうものだ。

テキスト:しんぶんしがしんぶんし
回文1 :|         |
回文2 :|   |
回文3 :      |   |

縦棒は回文が見つかったときの左端と右端である。このようなテキストでは回文2と回文3は回文1に完全に内包されるから無いものとして扱っても問題ないだろう。このフィルタリングを行うとレーベンシュタイン距離を使った回文の方が少なくなってしまうというのは、こちらの方が広い範囲の回文を見つけているということになるのか?はたまたプログラムの実装の問題なのか?


時間が無いのにはまってしまった。