« back to all changes in this revision
Viewing changes to service/distance.c
- browse files at revision 133.3.1
- compare with another revision
- download diff
- download tarball
- view history from revision 133.3.1
- Committer: Ted Gould
- Date: 2011-12-12 00:55:33 UTC
- mfrom: (0.1.43 trunk)
- mto: (1.1.29 upstream) (133.1.2 TDD.hud) (2.22.17 merge-hud.ubuntu) (227.128.1 docs-and-stuff)
- mto: This revision was merged to the branch mainline in revision 138.
- Revision ID: ted@gould.cx-20111212005533-pnu2co12oa7chou8
Merging the HUD into indicator-appmenu
- files added:
- data
- docs
- po
- service
- tests
- tests/bad-app-info
- tests/good-app-info
- files modified:
- .bzrignore
added
removed
service/distance.c
1
/*
2
Functions to calculate the distance between two strings.
3
4
Copyright 2011 Canonical Ltd.
5
6
Authors:
7
Ted Gould <ted@canonical.com>
8
9
This program is free software: you can redistribute it and/or modify it
10
under the terms of the GNU General Public License version 3, as published
11
by the Free Software Foundation.
12
13
This program is distributed in the hope that it will be useful, but
14
WITHOUT ANY WARRANTY; without even the implied warranties of
15
MERCHANTABILITY, SATISFACTORY QUALITY, or FITNESS FOR A PARTICULAR
16
PURPOSE. See the GNU General Public License for more details.
17
18
You should have received a copy of the GNU General Public License along
19
with this program. If not, see <http://www.gnu.org/licenses/>.
20
*/
21
22
#include <glib.h>
23
#include <glib/gprintf.h>
24
#include <glib-object.h>
25
#include <glib/gi18n.h>
26
27
#include "distance.h"
28
29
#define ADD_PENALTY 10
30
#define PRE_ADD_PENALTY 1
31
#define DROP_PENALTY 10
32
#define END_DROP_PENALTY 10
33
#define TRANSPOSE_PENALTY 10
34
#define DELETE_PENALTY 10
35
#define SWAP_PENALTY 10
36
37
static gboolean
38
ignore_character (gchar inchar)
39
{
40
static gchar * ignore = NULL;
41
if (ignore == NULL) {
42
/* TRANSLATORS: These are chacaters that should not be considered
43
mistakes in the comparison functions. Typically they are gramatical
44
characters that can be found in menus. */
45
ignore = _(" _->");
46
}
47
48
int i;
49
for (i = 0; i < 4; i++) {
50
if (ignore[i] == inchar) {
51
return TRUE;
52
}
53
}
54
return FALSE;
55
}
56
57
static guint
58
swap_cost (gchar a, gchar b)
59
{
60
if (a == b)
61
return 0;
62
if (ignore_character(a) || ignore_character(b))
63
return 0;
64
if (g_unichar_toupper(a) == g_unichar_toupper(b))
65
return SWAP_PENALTY / 10; /* Some penalty, but close */
66
return SWAP_PENALTY;
67
}
68
69
#define MATRIX_VAL(needle_loc, haystack_loc) (penalty_matrix[(needle_loc + 1) + (haystack_loc + 1) * (len_needle + 1)])
70
71
static void
72
dumpmatrix (const gchar * needle, guint len_needle, const gchar * haystack, guint len_haystack, guint * penalty_matrix)
73
{
74
#ifndef DUMP_MATRIX
75
return;
76
#endif
77
gint i, j;
78
79
g_printf("\n");
80
/* Character Column */
81
g_printf(" ");
82
/* Base val column */
83
g_printf(" ");
84
for (i = 0; i < len_needle; i++) {
85
g_printf("%c ", needle[i]);
86
}
87
g_printf("\n");
88
89
/* Character Column */
90
g_printf(" ");
91
for (i = -1; i < (gint)len_needle; i++) {
92
g_printf("%u ", MATRIX_VAL(i, -1));
93
}
94
g_printf("\n");
95
96
for (j = 0; j < len_haystack; j++) {
97
g_printf("%c ", haystack[j]);
98
for (i = -1; i < (gint)len_needle; i++) {
99
g_printf("%u ", MATRIX_VAL(i, j));
100
}
101
g_printf("\n");
102
}
103
g_printf("\n");
104
105
return;
106
}
107
108
static guint
109
calculate_token_distance (const gchar * needle, const gchar * haystack)
110
{
111
// g_debug("Comparing token '%s' to token '%s'", needle, haystack);
112
113
guint len_needle = 0;
114
guint len_haystack = 0;
115
116
if (needle != NULL) {
117
len_needle = g_utf8_strlen(needle, -1);
118
}
119
120
if (haystack != NULL) {
121
len_haystack = g_utf8_strlen(haystack, -1);
122
}
123
124
/* Handle the cases of very short or NULL strings quickly */
125
if (len_needle == 0) {
126
return DROP_PENALTY * len_haystack;
127
}
128
129
if (len_haystack == 0) {
130
return ADD_PENALTY * len_needle;
131
}
132
133
/* Allocate the matrix of penalties */
134
guint * penalty_matrix = g_malloc0(sizeof(guint) * (len_needle + 1) * (len_haystack + 1));
135
int i;
136
137
/* Take the first row and first column and make them additional letter penalties */
138
for (i = 0; i < len_needle + 1; i++) {
139
MATRIX_VAL(i - 1, -1) = i * ADD_PENALTY;
140
}
141
142
for (i = 0; i < len_haystack + 1; i++) {
143
if (i < len_haystack - len_needle) {
144
MATRIX_VAL(-1, i - 1) = i * PRE_ADD_PENALTY;
145
} else {
146
MATRIX_VAL(-1, i - 1) = (len_haystack - len_needle) * PRE_ADD_PENALTY + (i - (len_haystack - len_needle)) * DROP_PENALTY;
147
}
148
}
149
150
/* Now go through the matrix building up the penalties */
151
int ineedle, ihaystack;
152
for (ineedle = 0; ineedle < len_needle; ineedle++) {
153
for (ihaystack = 0; ihaystack < len_haystack; ihaystack++) {
154
char needle_let = needle[ineedle];
155
char haystack_let = haystack[ihaystack];
156
157
guint subst_pen = MATRIX_VAL(ineedle - 1, ihaystack - 1) + swap_cost(needle_let, haystack_let);
158
guint drop_pen = MATRIX_VAL(ineedle - 1, ihaystack);
159
if (ineedle < ihaystack) {
160
drop_pen += DROP_PENALTY;
161
} else {
162
drop_pen += END_DROP_PENALTY;
163
}
164
165
guint add_pen = MATRIX_VAL(ineedle, ihaystack - 1);
166
if (len_haystack - len_needle - ineedle > 0) {
167
add_pen += PRE_ADD_PENALTY;
168
} else {
169
add_pen += ADD_PENALTY;
170
}
171
guint transpose_pen = drop_pen + 1; /* ensures won't be chosen */
172
173
if (ineedle > 0 && ihaystack > 0 && needle_let == haystack[ihaystack - 1] && haystack_let == needle[ineedle - 1]) {
174
transpose_pen = MATRIX_VAL(ineedle - 2, ihaystack - 2) + TRANSPOSE_PENALTY;
175
}
176
177
MATRIX_VAL(ineedle, ihaystack) = MIN(MIN(subst_pen, drop_pen), MIN(add_pen, transpose_pen));
178
}
179
}
180
181
dumpmatrix(needle, len_needle, haystack, len_haystack, penalty_matrix);
182
183
guint retval = penalty_matrix[(len_needle + 1) * (len_haystack + 1) - 1];
184
g_free(penalty_matrix);
185
186
return retval;
187
}
188
189
/* Looks through the array of paths and tries to find a minimum path
190
looking up from the needle specified. This way we can look through
191
all the possible paths */
192
guint
193
minimize_distance_recurse (guint needle, guint num_needles, guint haystack, guint num_haystacks, guint * distances, guint * matches)
194
{
195
gint i;
196
197
/* Put where we are in the array so that we don't forget */
198
matches[needle] = haystack;
199
200
/* First check to see if we've already used this entry */
201
for (i = needle - 1; i >= 0; i--) {
202
if (matches[i] == haystack) {
203
return G_MAXUINT;
204
}
205
}
206
207
/* If we're the last needle, we can return our distance */
208
if (needle + 1 >= num_needles) {
209
return distances[(needle * num_haystacks) + haystack];
210
}
211
212
guint * local_match = g_new0(guint, num_needles);
213
for (i = 0; i < num_needles && i < needle + 1; i++) {
214
local_match[i] = matches[i];
215
}
216
217
/* Now look where we can get the minimum with the other needles */
218
guint min = G_MAXUINT;
219
for (i = 0; i < num_haystacks; i++) {
220
guint local = minimize_distance_recurse(needle + 1, num_needles, i, num_haystacks, distances, local_match);
221
222
if (local < min) {
223
min = local;
224
225
int j;
226
for (j = needle + 1; j < num_needles; j++) {
227
matches[j] = local_match[j];
228
}
229
}
230
}
231
232
g_free(local_match);
233
234
/* Return the min of everyone else plus our distance */
235
if (min < G_MAXUINT) {
236
min += distances[(needle * num_haystacks) + haystack];
237
}
238
239
return min;
240
}
241
242
/* Figuring out the lowest path through the distance array
243
where we don't use the same haystack tokens */
244
guint
245
minimize_distance (guint num_needles, guint num_haystacks, guint * distances, guint * matches)
246
{
247
guint final_distance = G_MAXUINT;
248
guint * local_matches = g_new0(guint, num_needles);
249
250
guint haystack_token;
251
for (haystack_token = 0; haystack_token < num_haystacks; haystack_token++) {
252
guint distance = minimize_distance_recurse(0, num_needles, haystack_token, num_haystacks, distances, local_matches);
253
254
if (distance < final_distance) {
255
final_distance = distance;
256
257
guint match_cnt;
258
for (match_cnt = 0; match_cnt < num_needles; match_cnt++) {
259
matches[match_cnt] = local_matches[match_cnt];
260
}
261
}
262
}
263
264
g_free(local_matches);
265
266
return final_distance;
267
}
268
269
/* Dups a specific token in the array of strv arrays */
270
gchar *
271
find_token (guint token_number, GStrv * haystacks, guint num_haystacks)
272
{
273
guint haystack;
274
275
for (haystack = 0; haystack < num_haystacks; haystack++) {
276
guint strvlen = g_strv_length(haystacks[haystack]);
277
278
if (token_number < strvlen) {
279
return g_strdup(haystacks[haystack][token_number]);
280
}
281
282
token_number -= strvlen;
283
}
284
285
return NULL;
286
}
287
288
#define SEPARATORS " .->"
289
290
guint
291
calculate_distance (const gchar * needle, GStrv haystacks, GStrv * matches)
292
{
293
g_return_val_if_fail(needle != NULL || haystacks != NULL, G_MAXUINT);
294
guint final_distance = G_MAXUINT;
295
296
if (needle == NULL) {
297
return DROP_PENALTY * g_utf8_strlen(haystacks[0], 1024);
298
}
299
if (haystacks == NULL) {
300
return ADD_PENALTY * g_utf8_strlen(needle, 1024);
301
}
302
303
/* Tokenize all the haystack strings */
304
gint i;
305
guint num_haystacks = g_strv_length(haystacks);
306
guint num_haystack_tokens = 0;
307
GStrv * haystacks_array = g_new0(GStrv, num_haystacks);
308
for (i = 0; i < num_haystacks; i++) {
309
haystacks_array[i] = g_strsplit_set(haystacks[i], SEPARATORS, 0);
310
num_haystack_tokens += g_strv_length(haystacks_array[i]);
311
}
312
313
/* Tokenize our needles the same way */
314
GStrv needle_tokens = g_strsplit_set(needle, SEPARATORS, 0);
315
guint num_needle_tokens = g_strv_length(needle_tokens);
316
317
/* If we can't even find a set that works, let's just cut
318
our losses here */
319
if (num_needle_tokens > num_haystack_tokens) {
320
goto cleanup_tokens;
321
}
322
323
/* We need a place to store all the distances */
324
guint * distances = g_new0(guint, num_haystack_tokens * num_needle_tokens);
325
326
/* Calculate all the distance combinations */
327
gint needle_token;
328
for (needle_token = 0; needle_tokens[needle_token] != NULL; needle_token++) {
329
gchar * ineedle = needle_tokens[needle_token];
330
331
guint haystacks_cnt;
332
guint haystack_token_cnt = 0;
333
for (haystacks_cnt = 0; haystacks_cnt < num_haystacks; haystacks_cnt++) {
334
guint haystack_cnt;
335
for (haystack_cnt = 0; haystacks_array[haystacks_cnt][haystack_cnt] != NULL; haystack_cnt++) {
336
gchar * ihaystack = haystacks_array[haystacks_cnt][haystack_cnt];
337
guint distance = calculate_token_distance(ineedle, ihaystack);
338
339
distances[(needle_token * num_haystack_tokens) + haystack_token_cnt] = distance;
340
haystack_token_cnt++;
341
}
342
}
343
}
344
345
/* Now, try to find a path through the array that results in the
346
lowest total value */
347
guint * final_matches = g_new0(guint, num_needle_tokens);
348
349
final_distance = minimize_distance(num_needle_tokens, num_haystack_tokens, distances, final_matches);
350
351
/* Set up an array for matches so that we can enter
352
the items as we go */
353
if (matches != NULL) {
354
GStrv match_array = NULL;
355
match_array = g_new0(gchar *, num_needle_tokens + 1);
356
match_array[num_needle_tokens] = NULL;
357
358
/* Copy the strings that we care about */
359
int i;
360
for (i = 0; i < num_needle_tokens; i++) {
361
match_array[i] = find_token(final_matches[i], haystacks_array, num_haystacks);
362
}
363
364
*matches = match_array;
365
}
366
367
g_free(final_matches);
368
g_free(distances);
369
370
cleanup_tokens:
371
g_strfreev(needle_tokens);
372
for (i = 0; i < num_haystacks; i++) {
373
g_strfreev(haystacks_array[i]);
374
}
375
g_free(haystacks_array);
376
377
if (final_distance != G_MAXUINT) {
378
return final_distance / num_needle_tokens;
379
} else {
380
return G_MAXUINT;
381
}
382
}
Loggerhead is a web-based interface for Breezy
Version: 2.0.1