Caffe2 - C++ API
A deep learning, cross platform ML framework
string_utils.cc
1 #include "caffe2/utils/string_utils.h"
2 
3 #include <algorithm>
4 #include <sstream>
5 #include <vector>
6 
7 namespace caffe2 {
8 
9 std::vector<std::string> split(char separator, const std::string& string) {
10  std::vector<std::string> pieces;
11  std::stringstream ss(string);
12  std::string item;
13  while (getline(ss, item, separator)) {
14  pieces.push_back(std::move(item));
15  }
16  return pieces;
17 }
18 
19 std::string trim(const std::string& str) {
20  size_t left = str.find_first_not_of(' ');
21  if (left == std::string::npos) {
22  return str;
23  }
24  size_t right = str.find_last_not_of(' ');
25  return str.substr(left, (right - left + 1));
26 }
27 
28 size_t editDistance(
29  const std::string& s1, const std::string& s2, size_t max_distance)
30  {
31  std::vector<size_t> current(s1.length() + 1);
32  std::vector<size_t> previous(s1.length() + 1);
33  std::vector<size_t> previous1(s1.length() + 1);
34 
35  return editDistanceHelper(
36  s1.c_str(),
37  s1.length(),
38  s2.c_str(),
39  s2.length(),
40  current,
41  previous,
42  previous1,
43  max_distance
44  );
45  }
46  #define NEXT_UNSAFE(s, i, c) { \
47  (c)=(uint8_t)(s)[(i)++]; \
48  }
49 
50 int32_t editDistanceHelper(const char* s1,
51  size_t s1_len,
52  const char* s2,
53  size_t s2_len,
54  std::vector<size_t> &current,
55  std::vector<size_t> &previous,
56  std::vector<size_t> &previous1,
57  size_t max_distance) {
58  if (max_distance) {
59  if (std::max(s1_len, s2_len) - std::min(s1_len, s2_len) > max_distance) {
60  return max_distance+1;
61  }
62  }
63 
64  for (size_t j = 0; j <= s1_len; ++j) {
65  current[j] = j;
66  }
67 
68  int32_t str2_offset = 0;
69  char prev2 = 0;
70  for (size_t i = 1; i <= s2_len; ++i) {
71  swap(previous1, previous);
72  swap(current, previous);
73  current[0] = i;
74 
75  char c2 = s2[str2_offset];
76  char prev1 = 0;
77  int32_t str1_offset = 0;
78 
79  NEXT_UNSAFE(s2, str2_offset, c2);
80 
81  size_t current_min = s1_len;
82  for (size_t j = 1; j <= s1_len; ++j) {
83  size_t insertion = previous[j] + 1;
84  size_t deletion = current[j - 1] + 1;
85  size_t substitution = previous[j - 1];
86  size_t transposition = insertion;
87  char c1 = s1[str1_offset];
88 
89  NEXT_UNSAFE(s1, str1_offset, c1);
90 
91  if (c1 != c2) {
92  substitution += 1;
93  }
94 
95 
96  if (prev1 == c2 && prev2 == c1 && j > 1 && i > 1) {
97  transposition = previous1[j - 2] + 1;
98  }
99  prev1 = c1;
100 
101  current[j] = std::min(std::min(insertion, deletion),
102  std::min(substitution, transposition));
103  current_min = std::min(current_min, current[j]);
104  }
105 
106 
107  if (max_distance != 0 && current_min > max_distance) {
108  return max_distance+1;
109  }
110 
111  prev2 = c2;
112  }
113 
114  return current[s1_len];
115  }
116 } // namespace caffe2
A global dictionary that holds information about what Caffe2 modules have been loaded in the current ...
Definition: blob.h:13