Ruby

ベルマンフォードのアルゴリズムで実行される結果も逐次表示

離散最適化理論の課題が出ていたので、ベルマンフォードのアルゴリズムを実装してみることにした。アルゴリズムが実行されていく様子の例もレポートに貼ろうと思ったんだけど、アルゴリズムはもうあるんだから、その様子をruby-graphvizとかで吐けばいいじゃ…

はてダラのテキストを検索する

恐らくこのブログを一番検索しているのはid:syou6162なんだけど、毎回http://d.hatena.ne.jp/syou6162から検索するのは面倒すぎる。日記ははてダラで書いているので、テキストはローカルにある。じゃあ、grepで探せよ、という話なんだけど、htmlで表示してく…

指標を全部実装してみた

この前の続き。先週の水曜で大体作ってしまっていたんだが、使い方ミスっててバグってると勘違いしていたorz。 出現頻度と連接頻度に基づく専門用語抽出 - Seeking for my unique color. とりあえずpneの1985年分のテキストを食わせて、それぞれの指標で上位…

トポロジカルソートのベンチマークらしきもの

離散最適化理論の課題を提出し終わったので、貼ってみるテスト。トポロジカルソートのためのところは前にちょちょいと書いたんですが 説明用の図 巨大なグラフを作る用の関数 計算時間をplotするための関数 などなどの付近も書いたので、貼ってみます。例を…

深いコピー?

なんかメモ。 tmp = ["hoge","fuga"] list =[tmp,"piyo"] pp list tmp.clear pp list 実行結果。 [["hoge", "fuga"], "piyo"] [[], "piyo"]

出現頻度と連接頻度に基づく専門用語抽出

この前の続き。先週の週末にやるつもりだったけど、暇がなかった。 MeCabで区切った単語を再びつなげる - yasuhisa's blog 前回の流れとしては 専門用語を一つの単語として取ってくるのは難しい MeCabを使うと細かくなりすぎる 専門用語には名詞のsequenceが…

系列アライメントのアルゴリズムをRubyで実装した

動的計画法分かんない しかも、なんか一次元じゃなくて二次元っぽいから怖い>< と思ってgkbrしていた次回アルゴリズムデザインのゼミで担当の系列アライメント(p246 6.6)のアルゴリズムですが、ミスドでホットカフェオレを3杯くらいおかわりしていたら結構…

コスト最小法によるViterbiアルゴリズムを実装してみた

前回は単語数最小法によるViterbiアルゴリズムを使って、「猫はうろうろ」を形態素解析しました。 www.yasuhisay.info 単語数最小法では、単語の品詞などは見ておらず、ただただ単語数を最小にするように動的計画法であるViterbiを動かしていきます。品詞を…

猫はうろうろ

にゃーにゃー、ではなくてw。情報学類(今名前変わったんだっけか)のほうで出ている自然言語処理の講義ほうで、形態素解析をするための「wikipedia:ビタビアルゴリズム(Viterbi algorithm)」というのを勉強しました(GWの前くらいに)。なんか全然分かっていな…

ダイクストラ法による最短路検索

昨日までに書いていたグラフはコストとかそういうの考えていなかったんだけど、ダイクストラをやろうということでコストも考えることにしました。ダイクストラでedgeとそこまでの距離のhashを作りながら、そこまでのを記憶しておくhashも用意。最短路を探す…

トポロジカル順序付け

トポロジカル順序付けは有向無閉路グラフ(directed acyclic graph)について定義されるものである。閉路がない有向グラフだと必ず順番のようなものを付けることができる。具体的にどういうものに使えるか、というと 仕事の順番 服を着る順番 講義科目の履修順…

全ての連結成分の集合を求める

有向グラフにおける連結成分の集合みたいなのがどうだったか忘れたので、無向グラフ化(両方を有向にするっぽい感じで)して考えることにした。 # -*- coding: utf-8 -*- require 'pp' require 'set' class Graph def initialize(edges) @edges = edges @nodes…

幅優先探索→深さ優先探索でした><

バックトラックとかしなくていいので、結構簡単にできた。 # -*- coding: utf-8 -*- require 'pp' class Graph def initialize(edges) @edges = edges @nodes = Hash.new{|h,k| h[k] = []} end def add_edge(edge) @edges.push edge unless @edges.index(edg…

グラフを扱うためのライブラリを覗いてみる

index グラフの勉強だけじゃなくてRubyの勉強にもなりそうなソースだなーと思ったので、メモしておく。ファイルは2つとなっていて把握しやすい。 graph.rb graph_algorithm.rb graph.rb module Graphとclass DirectedHashGraph、DirectedHashGraphを拡張した…

分割統治法の中のcounting inversionsを実装してみた

アルゴリズムデザインのゼミでmiyaga50が「counting inversions」について発表していた。 マージソートな考え方を使っているアルゴリズム 協調フィルタリングのようなランキングを使うようなシステムで使われる 嗜好がどれくらい違うかを測る尺度に使える メ…

Ruby&Perlでマージソート

数学的基礎とデータ構造 (アルゴリズムイントロダクション)のp28付近にあるマージソートをRubyでそのまま書きくだす簡単なお仕事。2行で書けるとかそんなの知るか。 require 'pp' def merge_sort(a, p = 1, r = a.length) def merge(a, p, q, r) n1 = q - p …

専門用語の辞書の加工

こんな感じになっている辞書から zygoma (解剖)頬骨 zygomatic 頬骨の zygomycete (生物)接合菌 zygomycosis (病名)接合菌症 zygote 接合体, 接合子 zygote nuclei (解剖)《複》接合体核 zygote nucleus (解剖)接合体核 zygotene 合糸期, ザイゴテ…

PNEのtxtからkeywordを引っこ抜く

専門用語の辞書を作りたい。そう考えるとPNEのkeywordとかはそのまま辞書の単語として登録できそうなので、引っこ抜いてくることにした。原型はここを参考にしつつ。 年ごとに頻度の高い単語をファイルに出力する - Seeking for my unique color. nkfにファ…

単語の登場回数がどういう分布をしているか見てみる

今日は講習会があっていたので、蛋白質核酸酵素のほうを調べるお仕事ができていなかったので、電車の中で書いてみる*1。単語の登場回数というのはたぶんlong tailをしているんだろうなーというのは予想がつくんだけど、どのくらいlong tailなのかを調べてみ…

いわゆる車輪の再開発をしていたようだ

卒論で頭がおかしくなっているらしい。普通に考えたらなんで自分で作るのか意味不明なんだけど、考えた時は書いた後だった。Text::Hatenaとかではてな記法をhtmlに変換してから、hprictで必要な要素を貫き出してもっかいText::Hatenaで加工してやればよいだ…

Text::Hatenaを活用しまくる

目次 はてな記法で静的コンテンツ生成のためにText::Hatenaを使うことにした わりとうまくいった なぜかTeX記法も見れた iPhone上での使いやすさが結構やばい 変換用のソースと一括変換用のソース 内容 Blogとか動的なコンテンツじゃなくて、静的なコンテン…

Twitterでfollowしなおすスクリプト→おまけでTwitterの発言数統計で遊んでみた

アカウント消して復活させるとふぉろーしているのにふぉろーしていないみたいな状態になったので、remove&followするためのスクリプトを書こうとした。まず、ふぉろーしている人たちのリストをスクレイピングして持ってこようと思ったらなんか謎のエラー。 >…

irbをESSのように使いたい!!→refeでヘルプも引けるようにした

ESSを知らない人向けに説明すると C-cC-nで今いる行をirbに飛ばしたい!! C-cC-pで今パラグラフ*1をirbに飛ばしたい!! ということがやりたいです。inf-ruby-modeとかでできるのかもしれないけど、昔使って思った通りに行かなかった記憶がある。というかESS li…

IRCでTwitterをごにょごにょできるのを作った

それtigで(ry、という話なんですが、Growlでアイコンと一緒に表示させるのがtigでやろうとして挫折したので、自分でごにょごにょしました。といってもIRC botを自分で作っていたら卒業できなくなるので、nadokaさんを使うことにしました。 Nadoka: IRC Clien…

RieceのLogから加工してircに定期的に発言させるBot

Limechatとかで検索ができなさげなので、もうbotを作ることにした。channelにfiltterをかけたchannelみたいなのってすぐに作れないもんなのかなー?tig.rbでtwitterの発言とかはrieceのlogにたまってきている。だから、定期的にそのlogを特定userとかでgrepみ…

Stanford Engineering Everywhere(SEE)からHandoutsとなっているpdfをかたっぱしからダウンロードしてくるRubyスクリプト

まあ、誰か書いてるだろうけど。 require 'rubygems' require 'mechanize' url = "http://see.stanford.edu/see/materials/icspmcs106a/handouts.aspx" agent = WWW::Mechanize.new source = Hpricot(agent.get_file(url)) (source/"a[@href^='http://course…

遺伝的アルゴリズムをRで書いてみた

Rejectセキュリティ&プログラミングキャンプでは極度の体調不良*1により、あんまりコーディングしてる時間が取れなかったのですが、それでもなんとか自分がやろうと思っていたところができました。集合知プログラミングの11章「進化する知性」ということで、…

Pythonで「へー」と思ったいくつかのこととRubyとの比較

集合知プログラミングのコードはpythonで書かれている。で、多言語で同じことをやろうとするとpythonの「へー」というところがいくつかあったので、まとめてみます。勘違いがありまくると思いますが、指摘してもらえるとうれしいです。pythonはもう1年以上や…

RとRubyで集合知プログラミングをするための準備

集合知プログラミングっぽいことををRejectセキュリティ&プログラミングキャンプでやろうかなーと思ってるんですが、データ操作とかは当日やりたくないのでぼちぼち準備とかしてみました。apiとか使ってごにょごにょでもいいんですが、とりあえず自分が購読…

Rubyで猛烈にはまった

超時間を無駄にしてしまった。Leopardにディフォルトで入っているRubyとMacportから入れたRubyがあるらしく、どっちを使っているのかを考えないとだめらしい。Rubyだけじゃなくて、gemも同様であった。アンインストール&インストールMacportのgemを入れよう…