[boost] RFC: edit_distance / edit_alignment library

Subject: [boost] RFC: edit_distance / edit_alignment library
From: Erik Erlandson (eje_at_[hidden])
Date: 2013-06-25 22:38:27

Boost Community,

I cooked up a library that provides a pair of functions: edit_distance() and edit_alignment().  The library currently lives here:
https://github.com/erikerlandson/edit_distance

Some short example programs are here:
https://github.com/erikerlandson/edit_distance/tree/master/examples

A few example expressions:

// the edit distance (aka levenshtein distance)
unsigned dist = edit_distance("abc", "bcd");

// using a custom cost function for insertion, deletion, substitution
unsigned dist = edit_distance("abc", "bcd", custom_cost_function());

// accepts arbitrary sequences, ranges, range adaptors
unsigned dist = edit_distance(as_vector("abc"), as_list("bcd") | boost::adaptors::reversed);

// obtain the edit distance and the list of the edit operation codes (in output iterator)
unsigned dist = edit_alignment("abc", "bcd", std::ostream_iterator<edit_opcode>(std::cout, "")).second;

// adaptors to add edit operation costs and sequence elements to the edit operation output
unsigned dist = acquire<elements>(acquire<costs>(edit_alignment))("abc", "bcd", std::ostream_iterator<boost::tuple<edit_opcode, unsigned, char, char> >(std::cout, "")).second;

I'm interested in community feedback on whether these would be a useful addition to boost::algorithms.  I envision these as the first additions to an eventually-larger library of other kinds of string distances, dynamic programming, and other algorithms for sequence alignment.