文字列リストをTRIE Optimizeされた正規表現に
Posted feedbacks - Ruby
最適化されてるとはほど遠いですが, 一応Trie構造は作れたと思います. 出力結果: program(ist(i(c(ally)?)|(st)?)?)|(m(a(t(i(c(ally)?)|(st)?)?)|(r)?)|(er)?)?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | Words = %w(program programist programistic programma programmar
programmatic programmatically programmatist programmer)
class Array
def index2(&block)
j = nil or each_with_index{|x, i| j = i if yield x} and j
end
end
class Trie
def initialize(words)
@words = words
max = 0 and @words.each{|x| max = x.size if x.size > max}
@trie = Array.new(max){Array.new}
end
def run
@words.each{|str| add(str)}
substitute
puts rep(@trie)
end
def add(str)
(ary = str.split(//)).size.times{|i|
x, y = ary[i], (i < ary.size-1 ? ary[i+1] : nil)
if (j = @trie[i].index2{|strc| strc[0] == x})
@trie[i][j][1].index2{|char| char == y} ?
next : @trie[i][j][1] << y
else
@trie[i] << [x, [y]]
end
}
end
def substitute #文字をインデックスに置換
(@trie.size-1).times{|i|
@trie[i].size.times{|j|
trie = @trie[i][j][1]
trie.map!{|x| @trie[i+1].index2{|y| x == y[0]}}.all?{|x| x} ?
trie.sort! : trie.compact! && trie.sort!.unshift(nil)
}
}
end
private
def rep(ary, i = 0)
trie = ary[0][i]
if ary.size == 1
trie[0]
else
if trie[1].size != 1
trie[0] + trie[1].map{|x|
if x
suffix = (x == trie[1].compact.max ? '?' : '|')
"(#{rep(ary[1..-1], x)})#{suffix}"
else
''
end
}.join
else
trie[0] + (trie[1][0] ? rep(ary[1..-1], trie[1][0]) : '')
end
end
end
end
trie = Trie.new(Words)
trie.run
|
dankogai
#4038()
[
Perl
]
Rating0/2=0.00
これは、実例を見た方が簡単だと思います。 CPANにRegexp::Assembleというモジュールがあるのですが、要はこれの簡易版を作って欲しいということです。私自身、同様のことを行うモジュールを過去にいくつか作っています(e.g Regexp::Optimizer)。
ここでは、文字列のリストを受け取って、それをTRIE化した正規表現に出来ればOKです。Regexp::AssembleやRegexp::Optimizerは正規表現を受け取ってそれをTrie化することも可能ですし、Perl 5.10では内部的にTrie Optimizationを行ったりするのですが、そこまでの機能は求めません。
なお、ここで言う「正規表現」は、必ずしもPerl互換のものである必要はありません。それがTrieになっていることをきちんと示せればOKです。
とはいうものの、Perl5互換になっていた方が、サポートしている環境が多くて有用性は高そうです。可能であればそうして下さい。
Dan the Regexp Assembler
see: Trie (en.wikipedia)
Rating0/2=0.00-0+
[ reply ]