cube-pruning introduced in paper is different from Yizhou's implementation

[Travelinglight]

There’s difference between the cube-pruning algorithm introduced in the papers and the implementation by Yizhou.

In the paper, the cube-pruning goes like this:

1. let q loop through [s, t], and separate [s, t] into [s, q], [q+1, t]
2. for each separation, score the k cells at top-left, and get the highest score
3. keep the top k scored separation and q is the feature signature

But Yizhou’s implementation is like this:

1. let q loop through [s, t], and separate [s, t] into [s, q], [q+1, t]
2. for each separation, score the most top-left cell and push it into a heap
3. explore: repeatedly pop the heap, score the neighbouring cells of the cell popped, and push them into the heap
4. the first k popped cells and the scores is kept as the k best scores of [s, t]

The major differences are:

1. In the paper, only one score could be kept for one feature signature (separation), but in Yizhou’s implementation, it is possible for multiple scores being kept with the same feature signature.
2. In the paper, up to (t-s)*k cells are scored, but in Yizhou’s implementation, t - s + 4*k cells are scored

[anoopsarkar]

was this fixed in the cube pruning branch?

[Travelinglight]

@anoopsarkar I fixed it in pos-parser-merge-step-2 but it contains another bug. The accuracy dropped a lot, but I haven't found the reason.