Guest User

Untitled

a guest
Jul 19th, 2018
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.30 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include<map>
  4. #include<algorithm>
  5. #include<iterator>
  6. #include <fstream>
  7. #include <cstdlib>
  8. #include <chrono>
  9.  
  10. using namespace std;
  11.  
  12. class Timer
  13. {
  14. // make things readable
  15. using clk = std::chrono::steady_clock;
  16.  
  17. clk::time_point b; // begin
  18. clk::time_point e; // end
  19.  
  20. public:
  21. void clear() { b = e = clk::now(); }
  22. void start() { b = clk::now(); }
  23. void stop() { e = clk::now(); }
  24.  
  25. friend std::ostream& operator<<(std::ostream& o, const Timer& timer)
  26. {
  27. return o << timer.secs();
  28. }
  29.  
  30. // return time difference in seconds
  31. double secs() const
  32. {
  33. if(e <= b)
  34. return 0.0;
  35. auto d = std::chrono::duration_cast<std::chrono::microseconds>(e - b);
  36. return d.count() / 1000000.0;
  37. }
  38. };
  39.  
  40. // len_s and len_t are the number of characters in string s and t respectively
  41. unsigned int LevenshteinDistance(string s, unsigned int len_s, string t, unsigned int len_t)
  42. {
  43. /* base case: empty strings */
  44. if (len_s == 0) return len_t;
  45. if (len_t == 0) return len_s;
  46.  
  47. /* test if last characters of the strings match */
  48. int cost = (s[len_s-1] == t[len_t-1]) ? 0 : 1;
  49.  
  50. /* return minimum of delete char from s, delete char from t, and delete char from both */
  51. return min(LevenshteinDistance(s, len_s - 1, t, len_t ) + 1,
  52. min(LevenshteinDistance(s, len_s , t, len_t - 1) + 1,
  53. LevenshteinDistance(s, len_s - 1, t, len_t - 1) + cost));
  54. }
  55.  
  56. // len_s and len_t are the number of characters in string s and t respectively
  57. unsigned int LevenshteinDistance_optmized(string s, unsigned int len_s, string t, unsigned int len_t)
  58. {
  59. /* base case: empty strings */
  60. if (len_s == 0) return len_t;
  61. if (len_t == 0) return len_s;
  62.  
  63. len_s = s.size();
  64. len_t = t.size();
  65.  
  66. unsigned int d[len_s][len_t] = {0};
  67.  
  68. for(unsigned int i = 1; i < len_s; i++) {
  69. d[i][0] = i;
  70. }
  71.  
  72. for(unsigned int j = 1; j < len_t; j++) {
  73. d[0][j] = j;
  74. }
  75.  
  76.  
  77. unsigned int subCost = 0;
  78. for(unsigned j = 1; j < len_t; j++) {
  79. for(unsigned int i = 1; i < len_s; i++) {
  80. if(s.at(i) == t.at(j))
  81. subCost = 0;
  82. else
  83. subCost = 1;
  84.  
  85. d[i][j] = min(d[i-1][j] + 1, min(d[i][j-1] + 1, d[i-1][j-1] + subCost));
  86.  
  87. }
  88. }
  89. return d[len_s-1][len_t-1];
  90.  
  91. }
  92.  
  93. static bool validateUserInput(string input) {
  94. unsigned int i = 0;
  95. while(i < input.size()) {
  96. if(!isalnum(input.at(i))) {
  97. cout << "invalid characters!" << endl;
  98. return false;
  99. }
  100. i++;
  101. }
  102.  
  103. if(input.empty())
  104. return false;
  105.  
  106. return true;
  107. }
  108.  
  109. static void loadWordListFile(const string filename, vector<string>& listofWords) {
  110. ifstream fin(filename.c_str());
  111. if(!fin) {
  112. cout << "error: can\'t open the file!" << endl;
  113. abort();
  114. }
  115.  
  116. string data;
  117. while(getline(fin, data)) {
  118. listofWords.emplace_back(data);
  119. }
  120. }
  121.  
  122. int main() {
  123.  
  124. //cout << "Lev distance: "
  125. //<< LevenshteinDistance("Kitten", 6, "sitting", 7) << endl;
  126.  
  127.  
  128.  
  129. // create a vector of random
  130. //vector<string> listofWords = {"hello", "might", "power", "wonder"};
  131. vector<string> listofWords;
  132. loadWordListFile("words.txt", listofWords);
  133.  
  134. //cout << "Select one of the following words:" << endl;
  135. //copy(listofWords.begin(), listofWords.end(), ostream_iterator<string>(cout, "\n"));
  136.  
  137. string userChoice;
  138.  
  139. cout << endl << endl <<"please type a word: " << endl;
  140. if (!std::getline(std::cin, userChoice)) {
  141. cout << "Invalid input" << endl;
  142. return -1;
  143. }
  144.  
  145. if(!validateUserInput(userChoice)) {
  146. cout << "invalid input" << endl;
  147. return -1;
  148. }
  149.  
  150.  
  151. if (find (listofWords.begin(), listofWords.end(), userChoice) != listofWords.end()) {
  152. cout << "You entered an exactly correct word" << endl;
  153. return 0;
  154. }
  155. Timer timer;
  156. vector < pair<string, unsigned int> >lvDistMap;
  157. timer.start();
  158. transform(listofWords.begin(), listofWords.end(),
  159. back_inserter(lvDistMap), [userChoice](string I) {
  160. unsigned int lvDist =
  161. LevenshteinDistance_optmized(userChoice, userChoice.size(), I, I.size());
  162. return make_pair(I, lvDist);
  163. });
  164. timer.stop();
  165. cout << "Time taken to find Levenshtein distance: " << timer << " secs" << endl;
  166. cout << "====================================" << endl;
  167. #if 0
  168. cout << "==============================" << endl;
  169. cout << "Sort and print the whole table" << endl;
  170. cout << "==============================" << endl;
  171. sort(lvDistMap.begin(), lvDistMap.end(),
  172. [](const pair<string, unsigned int>& lhs,
  173. const pair<string, unsigned int>& rhs) {
  174. return lhs.second < rhs.second;
  175. });
  176.  
  177. for(auto& I : lvDistMap) {
  178. cout << "\'" << I.first << "\' has a Levenshtein distance of: " << I.second
  179. << " relative to \'" << userChoice << "\'" << endl;
  180. }
  181.  
  182. cout << "==============================" << endl;
  183. cout << "print minimum distance only" << endl;
  184. cout << "==============================" << endl;
  185. #endif
  186.  
  187. auto result = min_element(lvDistMap.begin(), lvDistMap.end(),
  188. [](const pair<string, unsigned int>& lhs,
  189. const pair<string, unsigned int>& rhs) {
  190. return lhs.second < rhs.second;
  191. });
  192.  
  193. if(result->second <= 5)
  194. cout << "Perhaps you wanted to type \'" << result->first << "\'" << endl;
  195. else
  196. cout << "Can't find a close match" << endl;
  197.  
  198. return 0;
  199. }
Add Comment
Please, Sign In to add comment