Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
class CkySolver
def initialize(&init_proc)
@init_proc = init_proc
end
def solve(n, &callback)
a = Array.new(n * n)
n.times {|i| a[i*n + i] = @init_proc.call(i) }
(n - 1).times do |d|
(n - d - 1).times do |i|
j = i + d + 1
(i..(j - 1)).each do |k|
a[i*n + j] = callback.call(a, i, j, k)
end
end
end
a
end
end
data = [
{w: "I", p: [:N, :NP]},
{w: "saw", p: [:V, :VP]},
{w: "a", p: [:DET]},
{w: "girl", p: [:N, :NP]},
{w: "with", p: [:PREP]},
{w: "a", p: [:DET]},
{w: "telescope", p: [:N, :NP]},
]
chomsky_form =
[
[:S, [:NP, :VP]],
[:NP, [:DET, :N]],
[:NP, [:NP, :PP]],
[:VP, [:V, :NP]],
[:VP, [:VP, :PP]],
[:PP, [:PREP, :NP]],
]
solver = CkySolver.new {|i| data[i].merge(i: i) }
n = data.length
result = solver.solve(data.length) do |a, i, j, k|
bc = [a[i*n + k]&.fetch(:p), a[(k+1)*n + j]&.fetch(:p)]
_a = chomsky_form.find {|k, v| bc[0]&.include?(v[0]) && bc[1]&.include?(v[1]) }&.first
if a[i*n + j]
a[i*n + j][:p] << _a if _a
a[i*n + j]
else
_a && { p: [_a] }
end
end
result.each_slice(n) do |row|
pp row
end
Owner

youchan commented Feb 1, 2018

自然言語処理 (放送大学教材)のP.90のCKY法をrubyで解いてみた。
どこから来たのかという情報を残していないので、これだけだと構文木を作るところまではできない。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment