Double Array

高速なTrie実装として知られているDouble ArrayをRubyで実装してみた。インターンで実装したハッシュのTrieとの速度を比較してみるとおもしろそう。配列しか使ってないし、1byte単位で枝葉を構成していくので、メモリ効率は確実にいいと思うんだけど。まだ改良の余地はいろいろとありますが。

#!/usr/bin/ruby

class Trie
	def encode(char)
		l = 0
		u = @code.length - 1
		while (l  char
				u = m - 1
			elsif @code[m] < char
				l = m + 1
			else
				return m + 1
			end
		end
		return -1
	end

	def initialize(file)
		@base = [1]
		@check = [0]
		@code = Array.new
		words = Array.new
		io = open(file)
		while line = io.gets
			line.chomp!
			words.push(line)
			line.each_byte {|c| @code[c] = c }
		end
		io.close
		words.sort!
		@code.compact!
		_search(0, 0, words.length, 0, words)
	end

	def match(word)
		check = 0
		base = @base[check]
		word.each_byte do |c|
			i = base + encode(c)
			if (@check[i] != check)
				break
			end
			base = @base[i]
			check = i
		end
		return @check[base] == check
	end

	def _search(i, l, u, parent, words)
		stack = Array.new
		tmp = Array.new
		sons = Array.new
		j = l
		p = nil
		while j < u
			word = words[j]
			if i  0)
			base = 0
			flag = 0
			begin
				base += 1
				tmp.each do |c|
					break if (@check[base + c] != nil)
					flag += 1
				end
			end while flag != tmp.length
			tmp.each do |c|
				@base[parent] = base
				son = base + c
				@check[son] = parent
				@base[son] = - 1 if c == 0
				sons.push(son)
			end
		end
		stack.push(j)
		l = stack.shift
		if stack.length > 0
			i += 1
			(stack.length).times do
				u = stack.shift
				son = sons.shift
				_search(i, l, u, son, words)
				l = u
			end
		end
	end
end

構築部分にバグがありそうな感じです。