strange test?

[chrisjbaik]

Hi,

Thanks for making this package; I've been trying to use it for a project.

One question about one of the tests:

edit-distance-js/test/ted.test.coffee

Line 64 in 0c39456

shouldBeSymmetrical "(b,c)a", "b", 2, [["a", null], ["c", "b"], ["b", null]]

It seems to me that the alignment should show [a, null], [b, b], and [c, null] like the preceding test and have a distance of 2; as the alignment is written, wouldn't the distance be 3 with a remove, remove, rename operation?

[schulzch]

The tree edit distance is position-sensitive, thus it has to be a different edit path than the previous one. I can not remember why the edit path is correct. If you are still suspicious I suggest you to inspect the fdist and tdist cost tables and trace along with the backtracking.

In case you want to find an isomorphism that neglects order, but not structure (nested sets instead of lists), this can be done a lot easier and faster, e.g., using the Hopcroft–Karp algorithm or Hungarian algorithm.

[chrisjbaik]

Hm. I don't think I'm as much concerned that the order of the tree affects the result, but rather that the returned alignment doesn't seem to match the cost? The test shows:

• ["a", null] - a cost 1 remove operation
• ["c", "b"] - a cost 1 rename operation
• ["b", null] - a cost 1 remove operation

Shouldn't the returned distance then be 3 in this case?

I also tested this on a Python implementation of the algorithm, and the result is different from this library.

[schulzch]

I've added correctness test cases from APTED and none of them fail.

I'm pretty sure that the Python implementation is wrong here. Do not get confused by the mappings, since epsilons are kind-of "free".