From 441c8b4ad17c0d029b2247c367111395e7ad068c Mon Sep 17 00:00:00 2001 From: Douglas Gregor Date: Wed, 30 Dec 2009 17:23:44 +0000 Subject: Implement edit distance for StringRef git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@92309 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Support/StringRef.cpp | 31 +++++++++++++++++++++++++++++++ 1 file changed, 31 insertions(+) (limited to 'lib/Support/StringRef.cpp') diff --git a/lib/Support/StringRef.cpp b/lib/Support/StringRef.cpp index 2d023e4895..9084ea6ece 100644 --- a/lib/Support/StringRef.cpp +++ b/lib/Support/StringRef.cpp @@ -8,6 +8,7 @@ //===----------------------------------------------------------------------===// #include "llvm/ADT/StringRef.h" +#include using namespace llvm; // MSVC emits references to this into the translation units which reference it. @@ -35,6 +36,36 @@ int StringRef::compare_lower(StringRef RHS) const { return Length < RHS.Length ? -1 : 1; } +/// \brief Compute the edit distance between the two given strings. +unsigned StringRef::edit_distance(llvm::StringRef Other, + bool AllowReplacements) { + size_type m = size(); + size_type n = Other.size(); + + std::vector previous(n+1, 0); + for (std::vector::size_type i = 0; i <= n; ++i) + previous[i] = i; + + std::vector current(n+1, 0); + for (size_type y = 1; y <= m; ++y) { + current.assign(n+1, 0); + current[0] = y; + for (size_type x = 1; x <= n; ++x) { + if (AllowReplacements) { + current[x] = min(previous[x-1] + ((*this)[y-1] == Other[x-1]? 0u:1u), + min(current[x-1], previous[x])+1); + } + else { + if ((*this)[y-1] == Other[x-1]) current[x] = previous[x-1]; + else current[x] = min(current[x-1], previous[x]) + 1; + } + } + current.swap(previous); + } + + return previous[n]; +} + //===----------------------------------------------------------------------===// // String Searching //===----------------------------------------------------------------------===// -- cgit v1.2.3-18-g5258