From b1417b318f3b3cbfd0bf79a4cabc656825a84e5a Mon Sep 17 00:00:00 2001 From: Balajiganapathi S Date: Fri, 17 Nov 2017 21:41:15 +0530 Subject: Move string distance function to utils and format error message --- libdevcore/StringUtils.cpp | 77 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 77 insertions(+) create mode 100644 libdevcore/StringUtils.cpp (limited to 'libdevcore/StringUtils.cpp') diff --git a/libdevcore/StringUtils.cpp b/libdevcore/StringUtils.cpp new file mode 100644 index 00000000..7b2b4f5e --- /dev/null +++ b/libdevcore/StringUtils.cpp @@ -0,0 +1,77 @@ +/* + This file is part of solidity. + + solidity is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + solidity is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with solidity. If not, see . +*/ +/** @file StringUtils.h + * @author Balajiganapathi S + * @date 2017 + * + * String routines + */ + +#include "StringUtils.h" +#include +#include +#include + +using namespace std; +using namespace dev; + +namespace dev +{ + +bool stringWithinDistance(string const& _name1, string const& _name2, size_t _maxDistance) +{ + if (_name1 == _name2) + return true; + + size_t n1 = _name1.size(), n2 = _name2.size(); + vector> dp(n1 + 1, vector(n2 + 1)); + + // In this dp formulation of Damerau–Levenshtein distance we are assuming that the strings are 1-based to make base case storage easier. + // So index accesser to _name1 and _name2 have to be adjusted accordingly + for (size_t i1 = 0; i1 <= n1; ++i1) + { + for (size_t i2 = 0; i2 <= n2; ++i2) + { + if (min(i1, i2) == 0) + // Base case + dp[i1][i2] = max(i1, i2); + else + { + dp[i1][i2] = min(dp[i1 - 1][i2] + 1, dp[i1][i2 - 1] + 1); + // Deletion and insertion + if (_name1[i1 - 1] == _name2[i2 - 1]) + // Same chars, can skip + dp[i1][i2] = min(dp[i1][i2], dp[i1 - 1][i2 - 1]); + else + // Different chars so try substitution + dp[i1][i2] = min(dp[i1][i2], dp[i1 - 1][i2 - 1] + 1); + + if (i1 > 1 && i2 > 1 && _name1[i1 - 1] == _name2[i2 - 2] && _name1[i1 - 2] == _name2[i2 - 1]) + // Try transposing + dp[i1][i2] = min(dp[i1][i2], dp[i1 - 2][i2 - 2] + 1); + } + } + } + + size_t distance = dp[n1][n2]; + + // if distance is not greater than _maxDistance, and distance is strictly less than length of both names, + // they can be considered similar this is to avoid irrelevant suggestions + return distance <= _maxDistance && distance < n1 && distance < n2; +} + +} -- cgit v1.2.3 From 8a491c77ba9680afdf8c33664e905b978152b095 Mon Sep 17 00:00:00 2001 From: Balajiganapathi S Date: Tue, 21 Nov 2017 22:20:35 +0530 Subject: Restructure code for alternative identifier suggestions --- libdevcore/StringUtils.cpp | 69 +++++++++++++++++++++++++++------------------- 1 file changed, 41 insertions(+), 28 deletions(-) (limited to 'libdevcore/StringUtils.cpp') diff --git a/libdevcore/StringUtils.cpp b/libdevcore/StringUtils.cpp index 7b2b4f5e..1dbe151f 100644 --- a/libdevcore/StringUtils.cpp +++ b/libdevcore/StringUtils.cpp @@ -29,16 +29,24 @@ using namespace std; using namespace dev; -namespace dev +bool dev::stringWithinDistance(string const& _str1, string const& _str2, size_t _maxDistance) { - -bool stringWithinDistance(string const& _name1, string const& _name2, size_t _maxDistance) -{ - if (_name1 == _name2) + if (_str1 == _str2) return true; - size_t n1 = _name1.size(), n2 = _name2.size(); - vector> dp(n1 + 1, vector(n2 + 1)); + size_t n1 = _str1.size(), n2 = _str2.size(); + size_t distance = stringDistance(_str1, _str2); + + // if distance is not greater than _maxDistance, and distance is strictly less than length of both names, they can be considered similar + // this is to avoid irrelevant suggestions + return distance <= _maxDistance && distance < n1 && distance < n2; +} + +size_t dev::stringDistance(string const& _str1, string const& _str2) +{ + size_t n1 = _str1.size(), n2 = _str2.size(); + // Optimize by storing only last 2 rows and current row. So first index is considered modulo 3 + vector> dp(3, vector(n2 + 1)); // In this dp formulation of Damerau–Levenshtein distance we are assuming that the strings are 1-based to make base case storage easier. // So index accesser to _name1 and _name2 have to be adjusted accordingly @@ -46,32 +54,37 @@ bool stringWithinDistance(string const& _name1, string const& _name2, size_t _ma { for (size_t i2 = 0; i2 <= n2; ++i2) { - if (min(i1, i2) == 0) - // Base case - dp[i1][i2] = max(i1, i2); - else - { - dp[i1][i2] = min(dp[i1 - 1][i2] + 1, dp[i1][i2 - 1] + 1); - // Deletion and insertion - if (_name1[i1 - 1] == _name2[i2 - 1]) - // Same chars, can skip - dp[i1][i2] = min(dp[i1][i2], dp[i1 - 1][i2 - 1]); + if (min(i1, i2) == 0) // base case + dp[i1 % 3][i2] = max(i1, i2); else - // Different chars so try substitution - dp[i1][i2] = min(dp[i1][i2], dp[i1 - 1][i2 - 1] + 1); + { + dp[i1 % 3][i2] = min(dp[(i1-1) % 3][i2] + 1, dp[i1 % 3][i2-1] + 1); // deletion and insertion + if (_str1[i1-1] == _str2[i2-1]) // same chars, can skip + dp[i1 % 3][i2] = min(dp[i1 % 3][i2], dp[(i1-1) % 3][i2-1]); + else // different chars so try substitution + dp[i1 % 3][i2] = min(dp[i1 % 3][i2], dp[(i1-1) % 3][i2-1] + 1); - if (i1 > 1 && i2 > 1 && _name1[i1 - 1] == _name2[i2 - 2] && _name1[i1 - 2] == _name2[i2 - 1]) - // Try transposing - dp[i1][i2] = min(dp[i1][i2], dp[i1 - 2][i2 - 2] + 1); - } + if (i1 > 1 && i2 > 1 && _str1[i1-1] == _str2[i2-2] && _str1[i1-2] == _str2[i2-1]) // Try transposing + dp[i1 % 3][i2] = min(dp[i1 % 3][i2], dp[(i1-2) % 3][i2-2] + 1); + } } } - size_t distance = dp[n1][n2]; - - // if distance is not greater than _maxDistance, and distance is strictly less than length of both names, - // they can be considered similar this is to avoid irrelevant suggestions - return distance <= _maxDistance && distance < n1 && distance < n2; + return dp[n1 % 3][n2]; } +string dev::quotedAlternativesList(vector const& suggestions) { + if (suggestions.empty()) + return ""; + if (suggestions.size() == 1) + return "\"" + suggestions.front() + "\""; + + string choices = "\"" + suggestions.front() + "\""; + for (size_t i = 1; i + 1 < suggestions.size(); ++i) + choices += ", \"" + suggestions[i] + "\""; + + choices += " or \"" + suggestions.back() + "\""; + + return choices; } + -- cgit v1.2.3 From dc0a25f1cdd0fe8a8de3a8a9a8376fc77e8de213 Mon Sep 17 00:00:00 2001 From: chriseth Date: Fri, 9 Feb 2018 17:45:45 +0100 Subject: Minor changes. --- libdevcore/StringUtils.cpp | 11 +++++++---- 1 file changed, 7 insertions(+), 4 deletions(-) (limited to 'libdevcore/StringUtils.cpp') diff --git a/libdevcore/StringUtils.cpp b/libdevcore/StringUtils.cpp index 1dbe151f..3bdf71f5 100644 --- a/libdevcore/StringUtils.cpp +++ b/libdevcore/StringUtils.cpp @@ -34,17 +34,19 @@ bool dev::stringWithinDistance(string const& _str1, string const& _str2, size_t if (_str1 == _str2) return true; - size_t n1 = _str1.size(), n2 = _str2.size(); + size_t n1 = _str1.size(); + size_t n2 = _str2.size(); size_t distance = stringDistance(_str1, _str2); // if distance is not greater than _maxDistance, and distance is strictly less than length of both names, they can be considered similar // this is to avoid irrelevant suggestions - return distance <= _maxDistance && distance < n1 && distance < n2; + return distance <= _maxDistance && distance < n1 && distance < n2; } size_t dev::stringDistance(string const& _str1, string const& _str2) { - size_t n1 = _str1.size(), n2 = _str2.size(); + size_t n1 = _str1.size(); + size_t n2 = _str2.size(); // Optimize by storing only last 2 rows and current row. So first index is considered modulo 3 vector> dp(3, vector(n2 + 1)); @@ -73,7 +75,8 @@ size_t dev::stringDistance(string const& _str1, string const& _str2) return dp[n1 % 3][n2]; } -string dev::quotedAlternativesList(vector const& suggestions) { +string dev::quotedAlternativesList(vector const& suggestions) +{ if (suggestions.empty()) return ""; if (suggestions.size() == 1) -- cgit v1.2.3 From 12c3eb8880bd6c50b5fd0aad76626fcce4f663b5 Mon Sep 17 00:00:00 2001 From: chriseth Date: Fri, 9 Feb 2018 17:49:50 +0100 Subject: Suggestion to improve readability. --- libdevcore/StringUtils.cpp | 35 +++++++++++++++++++++-------------- 1 file changed, 21 insertions(+), 14 deletions(-) (limited to 'libdevcore/StringUtils.cpp') diff --git a/libdevcore/StringUtils.cpp b/libdevcore/StringUtils.cpp index 3bdf71f5..c4b1d5a9 100644 --- a/libdevcore/StringUtils.cpp +++ b/libdevcore/StringUtils.cpp @@ -53,24 +53,31 @@ size_t dev::stringDistance(string const& _str1, string const& _str2) // In this dp formulation of Damerau–Levenshtein distance we are assuming that the strings are 1-based to make base case storage easier. // So index accesser to _name1 and _name2 have to be adjusted accordingly for (size_t i1 = 0; i1 <= n1; ++i1) - { for (size_t i2 = 0; i2 <= n2; ++i2) { - if (min(i1, i2) == 0) // base case - dp[i1 % 3][i2] = max(i1, i2); + size_t x = 0; + if (min(i1, i2) == 0) // base case + x = max(i1, i2); + else + { + size_t left = dp[(i1-1) % 3][i2]; + size_t up = dp[i1 % 3][i2-1]; + size_t upleft = dp[(i1 - 1) % 3][i2-1]; + // deletion and insertion + x = min(left + 1, up + 1); + if (_str1[i1-1] == _str2[i2-1]) + // same chars, can skip + x = min(x, upleft); else - { - dp[i1 % 3][i2] = min(dp[(i1-1) % 3][i2] + 1, dp[i1 % 3][i2-1] + 1); // deletion and insertion - if (_str1[i1-1] == _str2[i2-1]) // same chars, can skip - dp[i1 % 3][i2] = min(dp[i1 % 3][i2], dp[(i1-1) % 3][i2-1]); - else // different chars so try substitution - dp[i1 % 3][i2] = min(dp[i1 % 3][i2], dp[(i1-1) % 3][i2-1] + 1); - - if (i1 > 1 && i2 > 1 && _str1[i1-1] == _str2[i2-2] && _str1[i1-2] == _str2[i2-1]) // Try transposing - dp[i1 % 3][i2] = min(dp[i1 % 3][i2], dp[(i1-2) % 3][i2-2] + 1); - } + // different chars so try substitution + x = min(x, upleft + 1); + + // transposing + if (i1 > 1 && i2 > 1 && _str1[i1 - 1] == _str2[i2 - 2] && _str1[i1 - 2] == _str2[i2 - 1]) + x = min(x, dp[(i1 - 2) % 3][i2 - 2] + 1); + } + dp[i1 % 3][i2] = x; } - } return dp[n1 % 3][n2]; } -- cgit v1.2.3 From 5747985e6a272edd512d53b2da438577fe461bb6 Mon Sep 17 00:00:00 2001 From: chriseth Date: Fri, 9 Feb 2018 17:53:30 +0100 Subject: Use one-dimensional vector. --- libdevcore/StringUtils.cpp | 15 ++++++++------- 1 file changed, 8 insertions(+), 7 deletions(-) (limited to 'libdevcore/StringUtils.cpp') diff --git a/libdevcore/StringUtils.cpp b/libdevcore/StringUtils.cpp index c4b1d5a9..2ff86bd5 100644 --- a/libdevcore/StringUtils.cpp +++ b/libdevcore/StringUtils.cpp @@ -48,7 +48,8 @@ size_t dev::stringDistance(string const& _str1, string const& _str2) size_t n1 = _str1.size(); size_t n2 = _str2.size(); // Optimize by storing only last 2 rows and current row. So first index is considered modulo 3 - vector> dp(3, vector(n2 + 1)); + // This is a two-dimensional array of size 3 x (n2 + 1). + vector dp(3 * (n2 + 1)); // In this dp formulation of Damerau–Levenshtein distance we are assuming that the strings are 1-based to make base case storage easier. // So index accesser to _name1 and _name2 have to be adjusted accordingly @@ -60,9 +61,9 @@ size_t dev::stringDistance(string const& _str1, string const& _str2) x = max(i1, i2); else { - size_t left = dp[(i1-1) % 3][i2]; - size_t up = dp[i1 % 3][i2-1]; - size_t upleft = dp[(i1 - 1) % 3][i2-1]; + size_t left = dp[(i1 - 1) % 3 + i2 * 3]; + size_t up = dp[(i1 % 3) + (i2 - 1) * 3]; + size_t upleft = dp[((i1 - 1) % 3) + (i2 - 1) * 3]; // deletion and insertion x = min(left + 1, up + 1); if (_str1[i1-1] == _str2[i2-1]) @@ -74,12 +75,12 @@ size_t dev::stringDistance(string const& _str1, string const& _str2) // transposing if (i1 > 1 && i2 > 1 && _str1[i1 - 1] == _str2[i2 - 2] && _str1[i1 - 2] == _str2[i2 - 1]) - x = min(x, dp[(i1 - 2) % 3][i2 - 2] + 1); + x = min(x, dp[((i1 - 2) % 3) + (i2 - 2) * 3] + 1); } - dp[i1 % 3][i2] = x; + dp[(i1 % 3) + i2 * 3] = x; } - return dp[n1 % 3][n2]; + return dp[(n1 % 3) + n2 * 3]; } string dev::quotedAlternativesList(vector const& suggestions) -- cgit v1.2.3