Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 TreeEditDistance

Source Notebook

Calculate the edit distance between two Tree objects

Contributed by: Arnab Datta

ResourceFunction["TreeEditDistance"][t1,t2]

gives the edit distance between Tree objects t1 and t2.

Details

The edit distance is the minimum number of node deletion, insertion and substitution operations needed to transform one tree into another.

Examples

Basic Examples (2) 

Create two expression trees:

In[1]:=
{t1, t2} = {ExpressionTree[2 Cos[i \[Pi]]], ExpressionTree[2 Sin[j \[Pi]]]}
Out[1]=

Compute the edit distance between the two trees:

In[2]:=
ResourceFunction["TreeEditDistance"][t1, t2]
Out[2]=

Applications (3) 

Create two notebooks with similar content:

In[3]:=
nb1 = CreateDocument[{TextCell["Heading", "Section"], TextCell["Subsection", "Subsection"], TextCell["Some text"], TextCell["Heading 2", "Section"], TextCell["Subsection", "Subsection"], TextCell["abcd"], TextCell["Subsection 2", "Subsection"], TextCell["defg"]}]; nb2 = CreateDocument[{TextCell["Heading 1", "Section"], TextCell["Some text"], TextCell["Heading 2", "Section"], TextCell["Subsection", "Subsection"], TextCell["See spot run"], TextCell["Subsection 2", "Subsection"], TextCell["run spot run"]}];

Import the notebooks and convert to expression trees:

In[4]:=
Row[{t1 = ExpressionTree[ NotebookImport[nb1, _, "FlattenCellGroups" -> False], ImageSize -> Medium], t2 = ExpressionTree[ NotebookImport[nb2, _, "FlattenCellGroups" -> False], ImageSize -> Medium]}, Spacer[36]]
Out[4]=

Compute the edit distance between two expression trees:

In[5]:=
ResourceFunction["TreeEditDistance"][t1, t2]
Out[5]=

Publisher

Arnab Datta

Version History

  • 1.0.0 – 18 July 2022

Source Metadata

  • Citation:
    • Zhang K., Shasha D., "Simple fast algorithms for the editing distance between trees and related problems." SIAM Journal on Computing, vol. 18, no. 6, 1245-1262, 1989.
      DOI: 10.1137/0218082

License Information