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
@youchan

This comment has been minimized.

Show comment Hide comment
@youchan

youchan Feb 1, 2018

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

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