Incorrect TED Result?

[MilanConrad]

I tested the touzet_kr_set_tree_index ted algorithm on a basic example of two slightly altered HTML-trees. I converted the trees to the bracket notation by converting them to a python dict first, then to the bracket notation using the json2bracket script. Checking the converted results by hand, i saw that they were correct. However, i only inserted 3 diffs between the document which can be optimally applied using 3 rename operations. However, the TED-Result is 14 in this case, which is wrong. Therefore, i have two questions:

• Is it possible that there are edge cases where a non-optimal tree edit distance result is returned?
• Is there a way to get the sequence of operations leading to the computed tree edit distance?

My testing data in bracket notation:

{\{\}{"tag"{"[document]"}}{"attributes"{\{\}}}{"children"{[]{1{"html"}}{2{\{\}{"tag"{"html"}}{"attributes"{\{\}}}{"children"{[]{1{\{\}{"tag"{"head"}}{"attributes"{\{\}}}{"children"{[]{1{\{\}{"tag"{"title"}}{"attributes"{\{\}}}{"children"{[]{1{"Test Page"}}}}}}}}}}{2{\{\}{"tag"{"body"}}{"attributes"{\{\}}}{"children"{[]{1{\{\}{"tag"{"h1"}}{"attributes"{\{\}}}{"children"{[]{1{"Welcome to My Page"}}}}}}{2{\{\}{"tag"{"p"}}{"attributes"{\{\}}}{"children"{[]{1{"Hello, World!"}}}}}}}}}}}}}}}}}

{\{\}{"tag"{"[document]"}}{"attributes"{\{\}}}{"children"{[]{1{"html"}}{2{\{\}{"tag"{"html"}}{"attributes"{\{\}}}{"children"{[]{1{\{\}{"tag"{"head"}}{"attributes"{\{\}}}{"children"{[]{1{\{\}{"tag"{"title"}}{"attributes"{\{\}}}{"children"{[]{1{"Updated Test Page"}}}}}}}}}}{2{\{\}{"tag"{"body"}}{"attributes"{\{\}}}{"children"{[]{1{\{\}{"tag"{"h1"}}{"attributes"{\{\}}}{"children"{[]{1{"Welcome to the Updated Page"}}}}}}{2{\{\}{"tag"{"h2"}}{"attributes"{\{\}}}{"children"{[]{1{"Additional Section"}}}}}}{3{\{\}{"tag"{"p"}}{"attributes"{\{\}}}{"children"{[]{1{"Hello, Universe!"}}}}}}}}}}}}}}}}}

Result:
Incorrect TED result: 14 instead of 3

[mateuszpawlik]

Hi @MilanConrad Thanks for the feedback. I will certainly look into that but unfortunately I cannot commit when exactly.

In the meantime you could add your example (or better a smaller example) into our test cases and run the tests:

• TED computation test
• parser tests

This should simplify finding the problem.

The tests should also execute on a pull request so feel free to file one.

Please write the exact command or a code snippet of how you executed the algorithm.

An to answer your questions:

Is it possible that there are edge cases where a non-optimal tree edit distance result is returned?

All exact TED algorithms we implemented, should return the optimal result. That includes touzet_kr_set_tree_index executed using the ted function or ted_k function with a proper upper bound value.

Is there a way to get the sequence of operations leading to the computed tree edit distance?

Unfortunately, we haven't implemented that so far.