Decoder.java
4.04 KB
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
package is2.parser;
import java.util.ArrayList;
import java.util.concurrent.ExecutorService;
import is2.data.DataFES;
import is2.data.Parse;
import is2.util.DB;
/**
* @author Bernd Bohnet, 01.09.2009
*
* This methods do the actual work and they build the dependency trees.
*/
final public class Decoder {
public static final boolean TRAINING = true;
public static long timeDecotder;
public static long timeRearrange;
/**
* Threshold for rearrange edges non-projective
*/
public static float NON_PROJECTIVITY_THRESHOLD = 0.3F;
static ExecutorService executerService =java.util.concurrent.Executors.newFixedThreadPool(Parser.THREADS);
// do not initialize
private Decoder() {};
/**
* Build a dependency tree based on the data
* @param pos part-of-speech tags
* @param x the data
* @param projective projective or non-projective
* @param edges the edges
* @return a parse tree
* @throws InterruptedException
*/
public static Parse decode(short[] pos, DataFES x, boolean projective, boolean training) throws InterruptedException {
long ts = System.nanoTime();
if (executerService.isShutdown()) executerService = java.util.concurrent.Executors.newCachedThreadPool();
final int n = pos.length;
final Open O[][][][] = new Open[n][n][2][];
final Closed C[][][][] = new Closed[n][n][2][];
ArrayList<ParallelDecoder> pe = new ArrayList<ParallelDecoder>();
for(int i=0;i<Parser.THREADS ;i++) pe.add(new ParallelDecoder(pos, x, O, C, n));
for (short k = 1; k < n; k++) {
// provide the threads the data
for (short s = 0; s < n; s++) {
short t = (short) (s + k);
if (t >= n) break;
ParallelDecoder.add(s,t);
}
executerService.invokeAll(pe);
}
float bestSpanScore = (-1.0F / 0.0F);
Closed bestSpan = null;
for (int m = 1; m < n; m++)
if (C[0][n - 1][1][m].p > bestSpanScore) {
bestSpanScore = C[0][n - 1][1][m].p;
bestSpan = C[0][n - 1][1][m];
}
// build the dependency tree from the chart
Parse out= new Parse(pos.length);
bestSpan.create(out);
out.heads[0]=-1;
out.labels[0]=0;
timeDecotder += (System.nanoTime()-ts);
ts = System.nanoTime();
if (!projective) rearrange(pos, out.heads, out.labels,x,training);
timeRearrange += (System.nanoTime()-ts);
return out;
}
/**
* This is the parallel non-projective edge re-arranger
*
* @param pos part-of-speech tags
* @param heads parent child relation
* @param labs edge labels
* @param x the data
* @param edges the existing edges defined by part-of-speech tags
* @throws InterruptedException
*/
public static void rearrange(short[] pos, short[] heads, short[] labs, DataFES x, boolean training) throws InterruptedException {
int threads =(pos.length>Parser.THREADS)? Parser.THREADS: pos.length;
// wh what to change, nPar - new parent, nType - new type
short wh = -1, nPar = -1,nType = -1;
ArrayList<ParallelRearrange> pe = new ArrayList<ParallelRearrange>();
while(true) {
boolean[][] isChild = new boolean[heads.length][heads.length];
for(int i = 1, l1=1; i < heads.length; i++,l1=i)
while((l1= heads[l1]) != -1) isChild[l1][i] = true;
float max = Float.NEGATIVE_INFINITY;
float p = Extractor.encode3(pos, heads, labs, x);
pe.clear();
for(int i=0;i<threads;i++) pe.add(new ParallelRearrange( isChild, pos,x,heads,labs));
for(int ch = 1; ch < heads.length; ch++) {
for(short pa = 0; pa < heads.length; pa++) {
if(ch == pa || pa == heads[ch] || isChild[ch][pa]) continue;
ParallelRearrange.add(p,(short) ch, pa);
}
}
executerService.invokeAll(pe);
for(ParallelRearrange.PA rp :ParallelRearrange.order)
if(max < rp.max ) {
max = rp.max; wh = rp.wh;
nPar = rp.nPar; nType = rp.nType ;
}
ParallelRearrange.order.clear();
if(max <= NON_PROJECTIVITY_THRESHOLD) break; // bb: changed from 0.0
heads[wh] = nPar;
labs[wh] = nType;
}
}
public static String getInfo() {
return "Decoder non-projectivity threshold: "+NON_PROJECTIVITY_THRESHOLD;
}
}