Crate tree_edit_distance

Overview

This crate provides an implementation of a recursive generalized version of the Levenshtein distance for arbitrary sequences that finds the smallest possible diff between two trees, according to a user-defined measure for the cost of inserting and removing nodes. The smallest possible diff is defined by the the lowest cost sequence of edits that transforms one tree into the other.

Example

use tree_edit_distance::{Edit, diff, Node};
use std::mem::{discriminant, Discriminant};

enum Json {
    Null,
    Bool(bool),
    Number(f64),
    String(String),
    Array(Vec<Json>),
    Map(Vec<(String, Json)>),
}

impl<'n> Node<'n> for Json {
    type Kind = Discriminant<Json>;
    fn kind(&self) -> Self::Kind {
        discriminant(self)
    }

    type Weight = u64;
    fn weight(&self) -> Self::Weight {
        1
    }

    type Child = &'n Self;
    type Children = Box<[Self::Child]>;
    fn children(&'n self) -> Self::Children {
        match self {
            Json::Array(a) => a.iter().collect(),
            Json::Map(m) => m.iter().map(|(_, v)| v).collect(),
            _ => Box::default(),
        }
    }
}

macro_rules! json {
    ($( $tokens:tt )*) => {
        // ...
    };
}

let john = json! {
    "name": "John Doe",
    "age": 43,
    "phones": [
        "+44 1234567",
        "+44 2345678"
    ]
};

let jane = json! {
    "name": "Jane Doe",
    "maiden name": "Smith",
    "age": 40,
    "phones": [
        "+44 7654321",
    ]
};

let (edits, cost) = diff(&john, &jane);

assert_eq!(cost, 2);

assert_eq!(&*edits, &[
    Edit::Replace(Box::new([
        Edit::Replace(Box::default()),      // "name"
        Edit::Insert,                       // "maiden name"
        Edit::Replace(Box::default()),      // "age"
        Edit::Replace(Box::new([            // "phones"
            Edit::Replace(Box::default()),
            Edit::Remove
        ])),
    ]))
]);

Enums

Edit

A single operation between two Nodes.

Traits

Node

An abstraction for a generic tree.

Functions

diff

Finds the lowest cost sequence of Edits that transforms one tree of Nodes into the other.