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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
|
#!/usr/bin/env ruby
# ISSUES
# new rule already in global g?
# R+S = R
# variants?
#
class Rule
attr_accessor :nt, :f, :e, :features, :alignment
def initialize(s=nil)
return if !s
a = s.strip.split ' ||| '
@nt = a[0].strip
@f = a[1].split.map{|i| i.strip}
@e = a[2].split.map{|i| i.strip}
@features = {}
a[3].split.each { |i|
name,value = i.split '='
@features[name] = value.to_f
}
@alignment = a[4].strip
end
def to_s
feature_string = []
@features.each_pair { |name,value| feature_string << "#{name}=#{value}" } if @features
feature_string = feature_string.join ' '
return "#{@nt} ||| #{f.join ' '} ||| #{@e.join ' '} ||| #{feature_string} ||| #{@alignment}"
end
def rule_string
return "#{@f.join '_'}|||#{@e.join '_'}"
end
end
class Range
attr_accessor :from, :to
def initialize
@from = nil
@to = nil
end
def to_s
return "#{@from}--#{@to}"
end
def correct(n)
t = @from
@from = n - @to
@to = n - t
end
end
def ignore(rule)
return true if (rule.f[0].match('\[X,\d\]')&&rule.f[-1].match('\[X,\d\]')&&rule.e[0].match('\[X,\d\]')&&rule.e[-1].match('\[X,\d\]'))
return false
end
def is_sub(first, second, dir='left')
if dir=='right'
first = first.reverse; second = second.reverse
end
second_index = 0
match = false
first_range = Range.new; second_range = Range.new
first.each_with_index { |i,first_index|
break if i.match('\[X,\d\]') #(/\[X,\d\]/)
break if second_index > second.size-1
if i == second[second_index]
if !match
first_range.from = first_index
first_range.to = first_index
second_range.from = second_index
second_range.to = second_index
match = true
else
first_range.to = first_index
second_range.to = second_index
end
second_index += 1
else
first_range.from = first_range.to = second_range.from = second_range.to = nil
end
}
if dir=='right' && first_range.from&&first_range.to&&second_range.from&&second_range.to
first_range.correct(first.size-1)
second_range.correct(second.size-1)
end
return first_range, second_range if (first_range.from&&first_range.to&&second_range.from&&second_range.to)&&
(first_range.from>0||first_range.to>0||second_range.from>0||second_range.to>0)
return false
end
def merge(r, s, r_f_range, s_f_range, r_e_range, s_e_range, dir)
#ret = []
new_rule = Rule.new
new_rule.f = Array.new(s.f)
new_rule.e = Array.new(s.e)
if dir == 'left'
return nil if r_f_range.from==0&&r_e_range.from==0
(r_f_range.from-1).downto(0) { |i| new_rule.f.unshift r.f[i] }
(r_e_range.from-1).downto(0) { |i| new_rule.e.unshift r.e[i] }
elsif dir == 'right'
return nil if r_f_range.from==r.f.size-1&&r_e_range.from==r.e.size-1
(r_f_range.to+1).upto(r.f.size-1) { |i| new_rule.f << r.f[i] }
(r_e_range.to+1).upto(r.e.size-1) { |i| new_rule.e << r.e[i] }
end
return new_rule
end
def test
a = ["der", "eurozone", "[X,1]", "die", "[X,2]"]
b = ["eurozone"]
x = ["the", "eurozone", "[X,1]", "[X,2]"] # ???
y = ["eurozone", "members"]
r,s = is_sub(a,b)
puts "#{r} #{s}"
r,s = is_sub(b,a)
puts "#{r} #{s}"
r,s = is_sub(x,y)
puts "#{r} #{s}"
r,s = is_sub(y,x)
puts "#{r} #{s}"
puts
puts
a = ["schuld", "an", "[X,1]", "inflation"]
b = ["schuld"]
x = ["blamed", "for", "[X,1]", "inflation"]
y = ["for", "responsible"]
r,s = is_sub(a,b)
puts "#{r} #{s}"
r,s = is_sub(b,a)
puts "#{r} #{s}"
r,s = is_sub(x,y)
puts "#{r} #{s}"
r,s = is_sub(y,x)
puts "#{r} #{s}"
exit
end
test if ARGV[0] == 'test'
# read rules
rules = []
strings = {}
if ARGV[0] != 'test'
while line = STDIN.gets
rules << Rule.new(line)
strings[rules[-1].rule_string] = true
end
end
# main
done = {}
rules.each_with_index { |r,i|
next if ignore(r)
rules.each_with_index { |s,j|
next if done.has_key?(i)||ignore(s)||i==j
possible_overlap = false
r.f.each { |i|
if s.f.include? i
possible_overlap = true
break
end
}
next if !possible_overlap
# left, R->S
range_f_first, range_f_second = is_sub(r.f, s.f)
range_e_first, range_e_second = is_sub(r.e, s.e)
if range_f_first&&range_f_second&&range_e_first&&range_e_second
#puts "R: #{r.f} ||| #{r.e}\nS: #{s.f} ||| #{s.e}"
#puts "f:(#{range_f_first} #{range_f_second}) e:(#{range_e_first} #{range_e_second})\n"
new_rule = merge(r, s, range_f_first, range_f_first, range_e_first, range_e_second, 'left')
#puts "NEW #{new_rule}" if new_rule
puts "X" if (new_rule && !strings.has_key?(new_rule.rule_string))
#puts
end
# left, S->R
range_f_first, range_f_second = is_sub(s.f, r.f)
range_e_first, range_e_second = is_sub(s.e, r.e)
if range_f_first&&range_f_second&&range_e_first&&range_e_second
#puts "S: #{s.f} ||| #{s.e}\nR: #{r.f} ||| #{r.e}"
#puts "f:(#{range_f_first} #{range_f_second}) e:(#{range_e_first} #{range_e_second})\n"
new_rule = merge(s, r, range_f_first, range_f_first, range_e_first, range_e_second, 'left')
#puts "NEW #{new_rule}" if new_rule
puts "X" if (new_rule && !strings.has_key?(new_rule.rule_string))
#puts
end
# right, R->S
range_f_first, range_f_second = is_sub(r.f, s.f, 'right')
range_e_first, range_e_second = is_sub(r.e, s.e, 'right')
if range_f_first&&range_f_second&&range_e_first&&range_e_second
#puts "Rr: #{r.f} ||| #{r.e}\nSr: #{s.f} ||| #{s.e}"
#puts "f:(#{range_f_first} #{range_f_second}) e:(#{range_e_first} #{range_e_second})\n"
new_rule = merge(r, s, range_f_first, range_f_first, range_e_first, range_e_second, 'right')
#puts "NEW #{new_rule}" if new_rule
puts "X" if (new_rule && !strings.has_key?(new_rule.rule_string))
#puts
end
# right, S->R
range_f_first, range_f_second = is_sub(s.f, r.f, 'right')
range_e_first, range_e_second = is_sub(s.e, r.e, 'right')
if range_f_first&&range_f_second&&range_e_first&&range_e_second
#puts "Sr: #{s.f} ||| #{s.e}\nRr: #{r.f} ||| #{r.e}"
#puts "f:(#{range_f_first} #{range_f_second}) e:(#{range_e_first} #{range_e_second})\n"
new_rule = merge(s, r, range_f_first, range_f_first, range_e_first, range_e_second, 'right')
#puts "NEW #{new_rule}" if new_rule
puts "X" if (new_rule && !strings.has_key?(new_rule.rule_string))
#puts
end
}
done[i] = true
}
|
