RubyでSuffixArray
RubyでSuffixArrayを使う場合には普通saryを使うと思いますが、勉強のためにたつをさんのPerlのコードを参考にRubyで実装してみました。SuffixArrayって意外と簡単に作れるんですね。
今回は自分でバイナリサーチのアルゴリズムを実装しています。Ruby標準では提供されていないのかな。んー。
#!/usr/bin/env ruby
class Array
def bsearch(key, left = 0, right = self.size - 1, &comp)
return -1 if left > right
mid = (left + right) / 2
case comp.call(mid)
when 0
mid
when -1
bsearch(key, mid + 1, right, &comp)
else
bsearch(key, left, mid - 1, &comp)
end
end
end
class SuffixArray
def initialize(word)
@word = word
@sary = Array.new(@word.size){|i| i }
@sary.sort! do |i, j|
@word[i .. -1] <=> @word[j .. -1]
end
end
def search(key)
i = @sary.bsearch(key) do |mid|
@word[@sary[mid], key.size] <=> key
end
(i >= 0) ? @sary[i] : -1
end
end
sary = SuffixArray.new('abracadabra')
p sary
# => #<SuffixArray:0x81093b0 @sary=[10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2], @word="abracadabra">
p sary.search('ra')
# => 9
sary = SuffixArray.new('mississippi')
p sary
# => #<SuffixArray:0x810858c @sary=[10, 7, 4, 1, 0, 9, 8, 6, 3, 5, 2], @word="mississippi">
p sary.search('ppi')
# => 8
