Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

HASHで文字列検索 (この記事を編集する[管理者用])

過去の記事で時々,hashでごにょごにょするとか言ってると思うのだけども,その話.
長さ n 文字列 A と長さ m の文字列 B が与えられたとき, BA の部分文字列になっているかどうかを判定する問題を考える.

KMP法 ( Wikipedia JP ) とかBM法 ( Wikipedia JP ) で十分だと思うのだけど,使える道具が多いに越したことないのでHASHでやってしまう方法をメモしておく.
一般的に知られている方法なのかどうかわからないのだけど,たぶん何処かにある話で名前もついているのかもしれない.
計算時間量は O( n + m ).

以下出てくるHASHの値はunsigned intやunsigned long longなどで勝手に2^32もしくは2^64などの法で考えているとする.
文字列 B のHASHを適当な定数を c として
 c^{ m - 1 } B [ 0 ] + c^{ m - 2 } B [ 1 ] + ... + c^0 B [ m - 1 ]
とする.
文字列 Ai 文字目から i + m - 1 文字目で作られる部分文字列のHASHが H だとすると,
i + 1 文字目から i + m 文字目で作られる部分文字列のHASHは
 c H + A [ i + m ] - c^m A [ i ]
で計算される.
c^m は何回も使うので最初に計算しておく.
こうやって計算すれば, A の長さ m の部分文字列すべてのHASHを O( n ) で計算することができる.

(2008/10/15 13:00追記)
Rabin-Karp アルゴリズム ( Wikipedia EN ) というらしい.
コメントで教えてもらった.

分割数 (この記事を編集する[管理者用])

分割数ちょっと計算したのでメモ.
 Par( n , k ) := n 個のものを k 個に分ける分け方.

例えば,
 Par( 7, 2 ) = 3.
  なぜなら, 7 = 1+6 = 2+5 = 3+4.
 Par( 7, 3 ) = 4.
  なぜなら,7 = 1+1+5 = 1+2+4 = 1+3+3 = 2+2+3.

DPで計算する方法は良く知られている気がする.
今回はそれじゃなくてk が小さいとき計算してみた.

k = 1 )
 Par( n, 1 ) = 1

k = 2 )
 Par( n, 2 ) = floor( n / 2 )

k = 3 )
 Par( 6 m + 1 , 3 ) = 3 m^2 + m
 Par( 6 m + 2 , 3 ) = 3 m^2 + 2 m
 Par( 6 m + 3 , 3 ) = 3 m^2 + 3 m + 1
 Par( 6 m + 4 , 3 ) = 3 m^2 + 4 m + 1
 Par( 6 m + 5 , 3 ) = 3 m^2 + 5 m + 2
 Par( 6 m + 6 , 3 ) = 3 m^2 + 6 m + 3

強連結成分分解 (この記事を編集する[管理者用])

強連結という言葉の定義ぐらいしかしらなくて,駄目駄目な思いをしたのでメモしておく.
ACM/ICPCでグラフに強いチームメイトがいたせいなのか個人戦だとグラフは駄目駄目.
いい加減,基礎的なことぐらいできるようになりたいな….

有向グラフにおいて,ノード uv の同値関係を
 u ~ vu から v に到達できる かつ v から u に到達できる
で定義する.
この同値関係に基づいて,同値類で分類することを強連結成分分解という.

で,なんと,強連結成分分解は計算時間 O( ノード数 + 枝数 ) でできてしまう.
Spaghetti SourceにDFS 1回で分解を行うソースコードがあるけど,パッと見でどうやっているのかわからなかったので,よりスタンダード(らしい)な方法を書いておく.
 http://www.hgc.jp/~tshibuya/classes/shibuya20050225.pdf
に方法自体は書いてある.証明は厳密にはまだ考えてないけど,いくつか例を書いてやってみると上手くいっているのが確認できる.
で,アルゴリズムは単純で以下の通り.
 Step 1. 番号がついていないノードをランダムに選び,そのノードを始点としてpost orderで番号をつけていく.
 Step 2. 枝の向きを変えた,逆グラフをつくる.
 Step 3. まだ強連結成分に属していないノードの中で,番号の一番大きなノードから(まだ強連結成分に属していないノードのみを経由して)到達できるノードの集合が1つの強連結成分.
 Note: Step 1でつけられる番号は一意ではない.

これからコード書こう.

2部グラフの最大流問題と最大マッチング問題と最小点被覆問題 (この記事を編集する[管理者用])

最大流と最大マッチングが同値なのはほぼ自明で,最小カットと同値なのまでは説明しているWebページも沢山あるけども,最小点被覆との関係(König-Egervary theorem)をちゃんと書いてる(日本語の)Webページが少なかったのでメモしておく.

Flowは左から右に流れる.左側の節点とか右側の節点とかいう言葉の意味はなんとか理解してもらう.
点被覆とは,節点集合で,グラフからその節点集合を除くと枝が全くなくなるものをいう.
最小点被覆は,点被覆の中で,節点の数が最も少ないもの.

2部グラフの最小点被覆の節点数は,2部グラフの最大マッチングに一致する.
2部グラフの最大マッチングが与えられたとき,どのようにして,最小点被覆を得るかと言うと,
 左側の節点のうち,最大マッチングの枝に繋がっていないもの
を全部取ってきて,それから到達できる節点の集合を求める.
ただし,到達できるというのは,左側の節点から右側の節点に移動する際は,最大マッチングに含まれていない枝しか通ってはいけなくて,右側の節点から左側の節点に移動する際は,最大マッチングに含まれている枝しか通ってはいけない.
で,到達できる節点の集合が求まったら,最小点被覆は,左側の節点の中で到達できなかったものと右側の節点のうち到達できたものを合わせたものである.

そうやって作られた節点集合が点被覆になっていることはほぼ自明.
それの節点数が最大マッチングと一致することも最大マッチングであることを考えれば簡単に理解できる.
最大マッチングより少ない節点数の点被覆が存在しないこともほぼ自明.

到達できる節点集合とか言っているのだけど,それが最大マッチングの意味ではごちゃごちゃしててわかりにくいのだけども,最大流問題で考えれば簡単になる.
到達できる節点集合は,ソースからFlowを流すことができる向きにのみ移動して到達できる節点集合(からソースを除いたもの)に一致する.

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。