edit_distance.h File Reference

#include "nfa.h"
#include <cstddef>
#include <optional>
#include <string>

Include dependency graph for edit_distance.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	levenshtein_automatont
	Simple automaton that can detect whether a string can be transformed into another with a limited number of deletions, insertions or substitutions. More...

Detailed Description

Author

Diffblue Ltd.

Loosely based on this blog post: http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata Provides a way to compute edit distance between two strings

No conversion to DFA or other optimisations are done here because for our use case (i.e. suggestions for errors in command line specifications) this is fast enough without them.

Definition in file edit_distance.h.