diff options
| -rw-r--r-- | grammar | 3 | ||||
| -rw-r--r-- | intersect.rb | 104 |
2 files changed, 68 insertions, 39 deletions
@@ -1,8 +1,11 @@ [S] ||| [NP,1] [VP,2] ||| [1] [2] ||| logp=0 [S] ||| ich [VP,2] ||| i [1] [2] ||| logp=0 +[S] ||| ich sah ein [NN,1] haus ||| i saw a [NN,1] house ||| logp=0 +[S] ||| ich [V,1] ein [NN,1] haus ||| i saw a [NN,1] house ||| logp=0 [NP] ||| ich ||| i ||| logp=-0.5 use_i=1.0 [NP] ||| ein [NN,1] ||| a [1] ||| logp=0 use_a=1.0 [NN] ||| kleines haus ||| small house ||| logp=0 use_house=1 +[NN] ||| kleines haus ||| little house ||| logp=0 use_house=1 [NN] ||| [JJ,1] haus ||| [1] house ||| logp=0 use_house=1 [NN] ||| [JJ,1] haus ||| [1] shell ||| logp=0 use_shell=1 [JJ] ||| kleines ||| small ||| logp=0 use_small=1.0 diff --git a/intersect.rb b/intersect.rb index d8404a2..23d8fdb 100644 --- a/intersect.rb +++ b/intersect.rb @@ -44,48 +44,49 @@ input = "ich sah ein kleines haus".split.map { |i| Terminal.new i } passive_chart = Chart.new input active_chart = Chart.new input -# pre-fill passive chart w/ arity-0 rules -g.rules.reject { |r| r.arity>0 }.each { |r| +# pre-fill passive chart w/ 0-arity rules +g.rules.select { |r| r.rhs.first.class==Terminal }.each { |r| input.each_index.select{ |j| input[j].w==r.rhs.first.w }.each { |j| k = 1 if r.rhs.size > 1 - slice = input[j,j+(r.rhs.size-1)].map { |i| i.w } - if slice == r.rhs.map { |i| i.w } - k = r.rhs.size + z = r.rhs.index { |i| i.class==NonTerminal } + if z + z -= 1 + else + z = r.rhs.size-1 + end + slice = input[j..j+z].map { |i| i.w } + if slice == r.rhs[0..z].map { |i| i.w } + k = z+1 else next end end - passive_chart.at(j,j+k) << Item.new(r) - passive_chart.at(j,j+k).last.span.left = j - passive_chart.at(j,j+k).last.span.right = j+k - passive_chart.at(j,j+k).last.dot = k - } -} - -# pre-fill active chart with non 0arity rules starting with a (single(!)) T -g.rules.reject{|r| r.rhs[0].class==NonTerminal||r.arity==0}.each {|r| - input.each_with_index { |i,j| - if i.w==r.rhs.first.w - (j+2).upto(input.size) { |k| # no empty NT! - active_chart.at(j,k) << Item.new(r) - active_chart.at(j,k).last.span.left = j - active_chart.at(j,k).last.span.right = j+1 - active_chart.at(j,k).last.dot = 1 + if k == r.rhs.size + passive_chart.at(j,j+k) << Item.new(r) + passive_chart.at(j,j+k).last.span.left = j + passive_chart.at(j,j+k).last.span.right = j+k + passive_chart.at(j,j+k).last.dot = k + else + (j+k).upto(input.size) { |l| + active_chart.at(j,l) << Item.new(r) + active_chart.at(j,l).last.span.left = j + active_chart.at(j,l).last.span.right = j+k + active_chart.at(j,l).last.dot = k } end } } -# pre-fill active chart -s = g.rules.reject { |r| r.rhs.first.class!=NonTerminal}#.reject{|r| r.lhs.sym == 'S'} +# seed active chart +s = g.rules.reject { |r| r.rhs.first.class!=NonTerminal } (input.size).times { |k| 0.upto(input.size-(k+2)) { |i| s.each { |r| - active_chart.at(i,i+k+2) << Item.new(r) - active_chart.at(i,i+k+2).last.span.left = i - active_chart.at(i,i+k+2).last.span.right = i - active_chart.at(i,i+k+2).last.dot = 0 + active_chart.at(i,i+k+2) << Item.new(r) + active_chart.at(i,i+k+2).last.span.left = i + active_chart.at(i,i+k+2).last.span.right = i + active_chart.at(i,i+k+2).last.dot = 0 } } } @@ -105,46 +106,71 @@ def scan i, j, active_chart, passive_chart, input } end +def scan2 item, passive_chart, input, i, j + while item.rhs[item.dot].class == Terminal + if item.rhs[item.dot].w == input[item.span.left+item.dot].w + item.dot += 1 + item.span.right += 1 + if item.dot == item.rhs.size + passive_chart.at(i,j) << Item.new(item) + passive_chart.at(i,j).last.span.right = item.span.left+item.dot + end + end + end +end + # parse -def visit i, j, sz, active_chart, passive_chart, g, input +def parse i, j, sz, active_chart, passive_chart, g, input puts "| #{i},#{j}" - - # SCAN - scan i, j, active_chart, passive_chart, input - + #scan i, j, active_chart, passive_chart, input 1.upto(sz) { |span| break if span==(j-i) i.upto(j-span) { |k| - puts " #{k},#{k+span} (##{span})" - # COMPLETE - active_chart.at(i,j).each { |active_item| + puts " #{k},#{k+span} (##{span})" + # complete + active_chart.at(i,j).each { |active_item| passive_chart.at(k, k+span).each { |passive_item| if active_item.rhs[active_item.dot].class==NonTerminal && passive_item.lhs.sym == active_item.rhs[active_item.dot].sym next if not active_item.span.right==passive_item.span.left active_item.span.right = passive_item.span.right active_item.dot += 1 + scan2 active_item, passive_chart, input, i, j if active_item.dot == active_item.rhs.size passive_chart.at(i,j) << Item.new(active_item) end end } - } } + } + #scan i, j, active_chart, passive_chart, input + + } +end - scan i, j, active_chart, passive_chart, input +def visit n + n.times { |i| + 0.upto(n-(i+2)) { |j| + yield j, j+i+2 if block_given? + } } end + +visit(input.size) { |i,j| + puts "#{i},#{j}" +} + # once for each cell (input.size).times { |k| 0.upto(input.size-(k+2)) { |i| - visit i, i+k+2, input.size, active_chart, passive_chart, g, input + parse i, i+k+2, input.size, active_chart, passive_chart, g, input } } + puts "---" -passive_chart.at(3,5).each { |item| +passive_chart.at(0,5).each { |item| puts item.to_s } |