Debian Codegraph @

data/0.12-dev/gen_pms/cleanup.cpp

raw
1 #include <iostream>
2 #include <string>
3 #include <vector>
4 #include <fstream>
5 #include <strstream>
6 #include <algorithm>
7 using namespace std;
8
9 #include "setutils.h"
10
11 #define DEBUG_SUBSETS 0
12 #define DEBUG_SMALLMERGE 0
13
14
15 // SMALLMERGE_RATIO: the golden ratio used for smallmerge algorithm.
16 const double SMALLMERGE_RATIO = .5;
17
18 // PITHY_FILTER: remove all meanings with less than this many synonyms listed.
19 const unsigned int PITHY_FILTER = 10;
20
21
22 template<class T>
23 void printvec(const vector<T>& v, const char* label)
24 {
25 cout << label << " = { ";
26 copy(v.begin(), v.end(), ostream_iterator<T>(cout, ", "));
27 cout << "}\n";
28 }
29
30
31 void cleanup(vector< vector<string> >& classes, vector< vector<string> >& output)
32 {
33 output.reserve(50);
34
35 // First, destroy any classes that only have two words. There
36 // tend to be extremely obscure.
37 for(int i = 0;i < classes.size();++i)
38 {
39 if (classes[i].size() == 2)
40 classes[i].clear();
41
42 sort(classes[i].begin(), classes[i].end());
43 }
44
45 for(int i = 0;i < classes.size();++i)
46 {
47 if (classes[i].empty())
48 continue;
49
50 for(int j = i+1;j < classes.size();++j)
51 {
52 if (classes[j].empty())
53 continue;
54
55 vector<string> left, right, common;
56 set_comparison(left, right, common, classes[i], classes[j]);
57
58
59 // Now we will delete proper subsets. There shouldn't
60 // be many of these.
61 if (left.empty())
62 {
63 #if DEBUG_SUBSETS
64 cout << i << " is a subset of " << j << endl;
65 printvec(classes[i], " lhs");
66 printvec(classes[j], " rhs");
67 #endif // DEBUG_SUBSETS
68 classes[i].clear();
69 break;
70 }
71 else if (right.empty())
72 {
73 #if DEBUG_SUBSETS
74 cout << j << " is a subset of " << i << endl;
75 printvec(classes[i], " lhs");
76 printvec(classes[j], " rhs");
77 #endif
78 classes[j].clear();
79 }
80
81
82 // Now we will attempt to merge small sets into large sets.
83 // There should (hopefully) be many of these merges.
84 //
85 // We will make the convention that merges will be placed
86 // into classes[i]. In other words, we want classes[i] to
87 // become our large set, and clear out classes[j].
88 double lratio = double(common.size()) / double(common.size() + left.size());
89 if (lratio >= SMALLMERGE_RATIO)
90 {
91 #if DEBUG_SMALLMERGE
92 cout << "smallmerge: " << i << " into " << j << " (ratio=" << lratio << ")" << endl;
93 printvec(classes[i], " lhs");
94 printvec(classes[j], " rhs");
95 #endif
96
97 for(int k = 0;k < classes[j].size();++k)
98 {
99 const string& word = (classes[j])[k];
100 if (!binary_search(classes[i].begin(), classes[i].end(), word))
101 {
102 classes[i].push_back(word);
103 sort(classes[i].begin(), classes[i].end());
104 }
105 }
106
107 classes[j].clear();
108
109 --i;
110 break;
111
112 #if DEBUG_SMALLMERGE
113 cout << "Post merge setup: " << endl;
114 printvec(classes[i], " lhs");
115 printvec(classes[j], " rhs");
116 #endif
117 }
118
119 double rratio = double(common.size()) / double(common.size() + right.size());
120 if (rratio >= SMALLMERGE_RATIO)
121 {
122 #if DEBUG_SMALLMERGE
123 cout << "smallmerge: " << j << " into " << i << " (ratio=" << rratio << ")" << endl;
124 printvec(classes[i], " lhs");
125 printvec(classes[j], " rhs");
126 #endif
127
128 for(int k = 0;k < classes[j].size();++k)
129 {
130 const string& word = (classes[j])[k];
131 if (!binary_search(classes[i].begin(), classes[i].end(), word))
132 {
133 classes[i].push_back(word);
134 sort(classes[i].begin(), classes[i].end());
135 }
136 }
137
138 classes[j].clear();
139
140 --i;
141 break;
142
143 #if DEBUG_SMALLMERGE
144 cout << "Post merge setup: " << endl;
145 printvec(classes[i], " lhs");
146 printvec(classes[j], " rhs");
147 #endif
148 }
149 }
150 }
151
152
153 for(int i = 0;i < classes.size();++i)
154 {
155 if (classes[i].size() > PITHY_FILTER)
156 {
157 // copy(classes[i].begin(), classes[i].end(),
158 // ostream_iterator<string>(cout, " "));
159 // cout << endl;
160 output.push_back(classes[i]);
161 }
162 }
163 }
164