Re: [boost] [gsoc-2013] proposal for approximate string matching

Here is a prototype for the interface: Part A. basic similarity metrics (use edit distance as an example) (1) int edit_distance(const Range1T&, const Range2T&); // return edit distance. (2) int edit_distance(const Range1T&, const Range2T&, int threshold); // return edit distance if it is no larger than threshold, else return -1 or threshold + 1. (3) int edit_distance(const Range1T&, const Range2T&, equal_func); // use uqual_func to determine whether two elements are equal or not.

For these first three, I'd typically expect them to return an unsigned integer. The ideal type might be the size_type of implied sequence containers, if it can be acquired, since the maximum possible distance is a function of the maximum supported sequence size.

(4) int edit_distance(const Range1T&, const Range2T&, insert_cost_func, delete_cost_func, substitute_cost_func); // use three cost functions to calculate the cost for one insert/delete/substitute operation.

For this last one, I would want the return type for distance to be governed by the return type of the cost functionals. So, if insert_cost_func and friends return float, then the edit distance would also return float. Even more generally, I might want the final return type for all edit_distance variants to be selectable as a template parameter (and perhaps influence the internal types used to compute it). I'm open to ideas here.

(5) some functions to return the sequence of operations?

I think that since you are focusing on supporting the search and join algorithms, distance variants that can return the sequence of edit-ops ought to be low priority. They could be added in the future, without impacting the library design.

Part B. string similarity search and join algorithms, focus on edit distance class searcher { void insert(IDType id, const string &word); // insert a word to the index, id is used as an identifier of this word. void erase(IDType id); // erase a word from the index, id should be the same one used in insertion process. vector<Result> search(const string &query, int threshold); // performing similarity search, which will return all the strings which are similar to the query string. Result may be a pair of the id and real edit distance. };

This searcher class has the feel of some kind of container class, and maybe ought to be designed with an eye toward satisfying one of the standard container interfaces. I noticed you were considering only supporting one category of sequence distance function (edit_distance) here, but if you make the distance-function into a template parameter, you might be able to use it with all your planned distance functions "for free"

class joiner { vector<PairResult> join(const string_and_id_container &R, const string_and_id_container &S, int threshold); // performing similarity join. Usually we are doing on-line join, which means we cannot pre-build the index. So we only need this one function. It will return all the pair where r is in R and s is in S and r is similar to s. PairResult may be a tuple of r's id, s's id and real edit distance. };

(4) Proposed Milestones and Schedule Now – June 15 To be more familiar with the Boost library. Discuss the details and interfaces with my mentor and on the develop mail list. June 15 – July 15 Develop a beta version of the approximate matching library. Most functions will be done at this time. July 15 – August 1 Review my code and improve its performance and quality. Discuss with my mentor for mid-term evaluation and future works. August 1 – September Write documentation, test code for my library. Make it "boost" like.

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost