module Levenshtein
	def levenshtein(a, b)
		if Inline::USABLE
			Inline.levenshtein(a, b)
		else
			PureRuby.levenshtein(a, b)
		end
	end

	module PureRuby
		def levenshtein(a, b)
			case
			when a.empty?
				b.length
			when b.empty?
				a.length
			else
				d = Array.new(a.length + 1) { |s|
					Array.new(b.length + 1, 0)
				}

				(0..a.length).each do |i|
					d[i][0] = i
				end

				(0..b.length).each do |j|
					d[0][j] = j
				end

				(1..a.length).each do |i|
					(1..b.length).each do |j|
						cost = (a[i - 1] == b[j - 1]) ? 0 : 1
						d[i][j] = [
							d[i-1][j  ] + 1,
							d[i  ][j-1] + 1,
							d[i-1][j-1] + cost
						].min
					end
				end

				d[a.length][b.length]
			end
		end

		module_function :levenshtein
	end

	module Inline
		begin
			require "rubygems"
			require "inline" # sudo gem install RubyInline

			inline do |builder|
				builder.c <<-'EOS'
					VALUE levenshtein (VALUE array1, VALUE array2) {
						VALUE ret;
						long len1 = RARRAY(array1)->len;
						long len2 = RARRAY(array2)->len;
						long i, j;

						long** d = ALLOC_N(long*, len1 + 1);
						for (i = 0; i <= len1; i++) {
							d[i] = ALLOC_N(long, len2 + 1);
							memset(d[i], 0, sizeof(d[i]));
						}

						for (i = 1; i <= len1; i++) d[i][0] = i;
						for (j = 1; j <= len2; j++) d[0][j] = j;
						for (i = 1; i <= len1; ++i) {
							for (j = 1; j <= len2; ++j) {
								int del = d[i-1][j  ] + 1;
								int ins = d[i  ][j-1] + 1;
								int sub = d[i-1][j-1] + (
									rb_equal(
										RARRAY(array1)->ptr[i-1],
										RARRAY(array2)->ptr[j-1]
									) ? 0 : 1
								);

								d[i][j] =
									(del <= ins && del <= sub) ? del:
									(ins <= del && ins <= sub) ? ins:
									sub;
							}
						}

						ret = LONG2FIX(d[len1][len2]);

						for (i = 0; i < len1; i++) free(d[i]);
						free(d);

						return ret;
					}
				EOS
			end

			module_function :levenshtein

			USABLE = true
		rescue LoadError
			USABLE = false
		end
	end
end


require 'rubygems'
require 'spec'

[Levenshtein::Inline, Levenshtein::PureRuby].each do |m|
	describe m do
		it "should return correct levenshtein distance" do
			[
				["kitten", "sitting", 3],
				["foo", "foo", 0],
				["", "", 0],
				["foO", "foo", 1],
				["", "foo", 3],
			].each do |a, b, expected|
				m.levenshtein(a.split(//), b.split(//)).should == expected
				m.levenshtein(b.split(//), a.split(//)).should == expected
			end
		end
	end
end

Spec::Runner.run

require "benchmark"

Benchmark.bm(10) do |x|
	n = 10000

	x.report("inline") do
		n.times {
			Levenshtein::Inline.levenshtein("kitten".split(//), "sitting".split(//))
		}
	end if Levenshtein::Inline::USABLE

	x.report("pureruby") do
		n.times {
			Levenshtein::PureRuby.levenshtein("kitten".split(//), "sitting".split(//))
		}
	end
end

なんか度々使うたびに移植している気がするのでメモ

ruby 1.8.6 (2008-08-11 patchlevel 287) [universal-darwin9.0]
                user     system      total        real
inline      0.330000   0.010000   0.340000 (  0.346537)
pureruby    2.500000   0.020000   2.520000 (  2.596968)

割とちょこちょこ触ることが多く、svn だと不便なので、http://github.com/cho45/net-irc に移動した

でもって要望があって気がむいたので 2ig.rb というものを作ってみた。

ruby example/2ig.rb --debug

で起動する

• 適当な名前でチャンネルに join (/join #foobar)
• トピックにスレのアドレスを設定 (/topic http://.../test/read.cgi/mmo/0000000000/)
• 流れてくる

実況スレみるにはいいかもしれない。(実況系の板でしか試してないのでほかの板だとへんかも)

• dat 取得 interval はデフォルトで90秒、トピックのスレアドレスに後に数字をいれると設定できる
  • '/topic http://.../test/read.cgi/mmo/0000000000/ 5' だと5秒ごと
• AA っぽいものは tinyurl に投げて URL 化している。
  • 改行が多く、記号の割合が多いものを AA と判断 (aa? メソッド)
• 1000 までいくと次スレを推測して提示する
  • 提示されたやつを /topic url.. すればチャンネルそのままで継続
  • 現スレのスレタイの数字+1が含まれるスレッド、直近にアドレスが投稿されたスレッド、編集距離を見て判断
    • 可能性が非常に高いスレッドが見つかった場合は色つき
• post 機能は実装してないのでだれかつくってほしい