From c8b4abf55672fb27eca97e921ca0e12057dcc0cf Mon Sep 17 00:00:00 2001 From: Patrick Simianer Date: Thu, 8 May 2014 17:56:31 +0200 Subject: correct, but still slow --- example/grammar | 15 +++++++++++++ example/grammar.3.gz | Bin 0 -> 65565 bytes example/grammar.x | 5 +++++ grammar | 15 ------------- grammar.rb | 9 ++++++-- intersect.rb | 62 +++++++++++++++++++++++++++++---------------------- 6 files changed, 62 insertions(+), 44 deletions(-) create mode 100644 example/grammar create mode 100644 example/grammar.3.gz create mode 100644 example/grammar.x delete mode 100644 grammar diff --git a/example/grammar b/example/grammar new file mode 100644 index 0000000..1d72ce5 --- /dev/null +++ b/example/grammar @@ -0,0 +1,15 @@ +[S] ||| [NP,1] [VP,2] ||| [1] [2] ||| logp=0 +[S] ||| ich sah ein kleines haus ||| +[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 [1] a [2] 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 +[JJ] ||| kleines ||| little ||| logp=0 use_little=1.0 +[VP] ||| [V,1] [NP,2] ||| [1] [2] ||| logp=0 +[V] ||| sah ||| saw ||| logp=-0.25 use_saw=1.0 diff --git a/example/grammar.3.gz b/example/grammar.3.gz new file mode 100644 index 0000000..59e6234 Binary files /dev/null and b/example/grammar.3.gz differ diff --git a/example/grammar.x b/example/grammar.x new file mode 100644 index 0000000..7ff74b5 --- /dev/null +++ b/example/grammar.x @@ -0,0 +1,5 @@ +[X] ||| lebensmittel [X,1] +[X] ||| schuld [X,1] +[X] ||| an +[X] ||| europäischer [X,1] +[X] ||| inflation diff --git a/grammar b/grammar deleted file mode 100644 index 45608e7..0000000 --- a/grammar +++ /dev/null @@ -1,15 +0,0 @@ -[S] ||| [NP,1] [VP,2] ||| [1] [2] ||| logp=0 -[S] ||| ich sah ein kleines haus ||| - ||| - -[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 -[JJ] ||| kleines ||| little ||| logp=0 use_little=1.0 -[VP] ||| [V,1] [NP,2] ||| [1] [2] ||| logp=0 -[V] ||| sah ||| saw ||| logp=-0.25 use_saw=1.0 diff --git a/grammar.rb b/grammar.rb index 3ee8105..8a08cc1 100644 --- a/grammar.rb +++ b/grammar.rb @@ -69,11 +69,13 @@ class Grammar def initialize fn @rules = [] + @glue_rules = [] ReadFile.readlines_strip(fn).each_with_index { |s,j| - #STDERR.write '.' - #puts "\n" if j%100==0&&j>0 + STDERR.write '.' + STDERR.write "\n" if (j+1)%80==0 @rules << Rule.from_s(s) } + STDERR.write "\n" end def to_s @@ -83,9 +85,12 @@ class Grammar end def add_glue_rules + # see https://github.com/jweese/thrax/wiki/Glue-grammar @rules.map { |r| r.lhs.symbol }.reject { |s| s=='S' }.uniq.each { |s| @rules << Rule.new(NT.new('S'), [NT.new(s)]) + @glue_rules << @rules.last @rules << Rule.new(NT.new('S'), [NT.new('S'), NT.new('X')]) + @glue_rules << @rules.last } end diff --git a/intersect.rb b/intersect.rb index 0aff6c4..e4db7eb 100644 --- a/intersect.rb +++ b/intersect.rb @@ -48,6 +48,7 @@ class Item < Rule @dot = rule_or_item.dot else @span = Span.new + @dot = 0 end end @@ -60,7 +61,7 @@ def visit n, depth, skip=0 (depth-skip).times { |i| i += skip 0.upto(n-(i+1)) { |j| - yield j, j+i+1 if block_given? + yield j, j+i+1 } } end @@ -86,7 +87,7 @@ def init active_chart, passive_chart, grammar, input, n if k == r.rhs.size passive_chart.add(r, j, j+k, j+k, k) else - (j+k).upto(n) { |l| active_chart.add(r, j, l, j+k, k) } + (j+k).upto(n) { |l| active_chart.add r, j, l, j+k, k } end } } @@ -97,23 +98,21 @@ def init active_chart, passive_chart, grammar, input, n } end -def scan item, passive_chart, input, i, j - while item.rhs[item.dot].class == T - if item.rhs[item.dot].word == input[item.span.left+item.dot].word +def scan item, passive_chart, input + while item.rhs[item.dot].class == T + break if item.span.right > input.size-1 + if item.rhs[item.dot].word == input[item.span.right].word item.dot += 1 - item.span.right = item.span.left+item.dot - if item.dot == item.rhs.size - passive_chart.add(item, i, j, item.span.left+item.dot, item.dot) - break - end + item.span.right += 1 + break if item.dot == item.rhs.size else break end end end -def parse i, j, sz, active_chart, passive_chart, g, input - active_chart.at(i,j).each_with_index { |active_item,q| +def parse i, j, sz, active_chart, passive_chart, input + active_chart.at(i,j).each_with_index { |active_item,z| 1.upto(sz) { |span| break if span==(j-i) i.upto(j-span) { |k| @@ -123,9 +122,9 @@ def parse i, j, sz, active_chart, passive_chart, g, input new_item = Item.new active_item new_item.span.right = passive_item.span.right new_item.dot += 1 - scan new_item, passive_chart, input, i, j + scan new_item, passive_chart, input if new_item.dot == new_item.rhs.size - passive_chart.at(i,j) << new_item + passive_chart.at(i,j) << new_item if new_item.span.left==i&&new_item.span.right==j else active_chart.at(i,j) << new_item end @@ -139,13 +138,15 @@ def parse i, j, sz, active_chart, passive_chart, g, input to_add_passive = [] passive_chart.at(i,j).each { |passive_item| active_chart.at(i,j).each { |active_item| + next if active_item.rhs[active_item.dot].class!=NT if passive_item.lhs.symbol == active_item.rhs[active_item.dot].symbol + next if not active_item.span.right==passive_item.span.left new_item = Item.new active_item new_item.span.right = passive_item.span.right new_item.dot += 1 - scan new_item, passive_chart, input, i, j + scan new_item, passive_chart, input if new_item.dot == new_item.rhs.size - to_add_passive << new_item + to_add_passive << new_item if new_item.span.left==i&&new_item.span.right==j else to_add_active << new_item end @@ -161,29 +162,36 @@ def preprocess s end def main - #input = "ich sah ein kleines haus".split.map { |i| T.new i } - input = preprocess "lebensmittel schuld an europäischer inflation" + #input = preprocess 'ich sah ein kleines haus' + #input = preprocess 'lebensmittel schuld an europäischer inflation' + input = preprocess 'offizielle sind von nur' # 3 prozent' # ausgegangen , meldete bloomberg .' n = input.size - puts "reading grammar .." - g = Grammar.new 'grammar.x' + puts 'reading grammar' + #g = Grammar.new 'example/grammar' + #g = Grammar.new 'example/grammar.x' + g = Grammar.new 'example/grammar.3.gz' # 4th segment of newstest2008 - puts "adding glue rules .." + puts 'adding glue rules' g.add_glue_rules - #puts "adding pass-through rules .." + #puts 'adding pass-through rules' #g.add_pass_through_rules input - puts "initializing charts .." + puts 'initializing charts' passive_chart = Chart.new n active_chart = Chart.new n init active_chart, passive_chart, g, input, n - puts "parsing .." - visit(n, n, 1) { |i,j| - parse i, j, n, active_chart, passive_chart, g, input + active_chart.at(0, 1).each_with_index { |i,x| puts "#{x}. #{i.to_s}" } + puts passive_chart.at(0,1).size + + puts 'parsing' + visit(n, n, 1) { |i,j| + STDERR.write " span (#{i}, #{j})\n" + parse i, j, n, active_chart, passive_chart, input } - + puts "---\npassive chart" visit(n, n, 0) { |i,j| puts "#{i},#{j}"; passive_chart.at(i,j).each { |item| puts ' '+item.to_s if item.span.left==i&&item.span.right==j }; puts } end -- cgit v1.2.3