$shibayu36->blog;

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

algorithm

Suffix Arrayを使った文字列マッチング

あるPatternがあるText中のどこに含まれるかという文字列マッチングの実装を最近してみている。前回、Suffix Trieでの文字列マッチングを行った。blog.shibayu36.orgSuffix Trieを利用すると、Suffix Trieを最初に構築したあと、実際にパターンを検索するの…

Suffix Trieを使って文字列マッチングする

文字列マッチングを行うためのアルゴリズムとして、Suffix Trieを使った探索というものがある。これはテキストからSuffix Trieという構造を作り、パターンをつかってそれを辿ることで、パターンの長さmに対して、O(m)の計算量で探索できるものである。今回は…

文字列マッチングのためのLCP Arrayを構築する

前回のブログ記事で、文字列マッチングをするためのSuffix Arrayという構造を構築した。このSuffix Arrayという構造だけでも、テキスト長をn、パターン長をmとして、の計算量で文字列マッチングできるようになった。 suffix arrayを一番簡単なアルゴリズムで…

suffix array構築のメモリ効率を良くする - アルゴリズム学習(その7)

blog.shibayu36.org上の記事で、一番簡単なアルゴリズムでのsuffix arrayの構築を実装してみた。しかしこれをベンチマークしようとして、10万文字くらいの文字列に対して適応してみると、Java heap spaceというエラーが出てしまい、計算できなかった。こうな…

suffix arrayを一番簡単なアルゴリズムで実装する - アルゴリズム学習(その6)

文字列アルゴリズムを学んでいると、suffix array(接尾辞配列)という配列が出てくる。これは文字列の接尾辞の集合を辞書順にソートし、その順でそれぞれの接尾辞の文字列中の開始位置のindexを格納した配列のことである。以下が参考になる。 接尾辞配列 - Wi…

力づく法・分割統治法・動的計画法 - アルゴリズム学習(その5)

アルゴリズムの設計手法として、力ずく法・分割統治法・動的計画法というような考え方があった。新しいアルゴリズムを学ぶ時、どの設計手法でやっているのだろうかと意識しておくと、頭に入りやすい気がした。そこで、自分の頭を整理するためにメモを書いて…

Javaでスタックとキューを実装 - アルゴリズム学習(その4)

Java データ構造とアルゴリズム基礎講座作者: 長尾和彦出版社/メーカー: 技術評論社発売日: 2008/12/26メディア: 大型本購入: 4人 クリック: 171回この商品を含むブログ (13件) を見る 今回はスタックとキュー。非常に基本的なデータ構造だし、だいたい知っ…

Javaで冪集合を生成する - アルゴリズム学習(その3)

同僚に冪集合作ってみては、と言われたので作った。冪集合はhttp://www.geocities.jp/k27c8_math/math/set_theory/power_set.htmとかに書いてあるとおり、渡された集合の部分集合全体。 考え方 思いついたのは以下の考え方。 [ 1, 2, 3 ]と渡されたとする 冪…

Javaで組み合わせを生成する - アルゴリズム学習(その2)

Javaで順列生成アルゴリズムを実装する - アルゴリズム学習(その1) - $shibayu36->blog;で順列を作ったので、続いて組み合わせを作ってみた。 考え方 いろんな考え方があると思うけど、僕が最初に思いついたのは次の考え方。 [ 1, 2, 3, 4, 5 ]から3つ取り出…

Javaで順列生成アルゴリズムを実装する - アルゴリズム学習(その1)

アルゴリズムを勉強しようと思って、以下の本のアルゴリズムをJavaで自分で考えて再実装するという取り組みをやっている。以下の本は基本的なアルゴリズムが簡単に説明されていて、しかも薄いのでやりやすい。アルゴリズムの勉強のしかた - きしだのはてなを…