Hey -- Here's a patch I put together this morning that will suggest an alternate search term if the user's search returns nothing. It uses the Levenshtein distance algorithm[1] to compare a search term with the list of words indexed by qdbm, and suggests the closest match.
If there's enthusiasm for this, this could easily be extended to return top 5 or 10 or whatever, and have a widget in libtracker-gtk that acts like the Google Suggests bar in Firefox. ...and a screenshot for those you want to see it without applying the patch: http://img260.imageshack.us/my.php?image=suggestxs8.png (the "galerkin" is a GtkButton, when clicked to search with the suggestion). [1] http://en.wikipedia.org/wiki/Levenshtein_distance
Index: src/trackerd/tracker-dbus-search.c =================================================================== --- src/trackerd/tracker-dbus-search.c (revision 527) +++ src/trackerd/tracker-dbus-search.c (working copy) @@ -781,3 +781,171 @@ tracker_db_free_result (res); } + +/* int levenshtein () + * Original license: GNU Lesser Public License + * from the Dixit project, (http://dixit.sourceforge.net/) + * Author: Octavian Procopiuc <[EMAIL PROTECTED]> + * Created: July 25, 2004 + * Copied into tracker, by Edward Duffy + */ + +static int +levenshtein(char *source, char *target, int maxdist) +{ + + char n, m; + uint l; + l = strlen (source); + if (l > 50) + return -1; + n = l; + + l = strlen (target); + if (l > 50) + return -1; + m = l; + + if (maxdist == 0) + maxdist = MAX(m, n); + if (n == 0) + return MIN(m, maxdist); + if (m == 0) + return MIN(n, maxdist); + + // Store the min. value on each column, so that, if it reaches + // maxdist, we break early. + char mincolval; + + char matrix[51][51]; + + char j; + char i; + char cell; + + for (j = 0; j <= m; j++) + matrix[0][(int)j] = j; + + for (i = 1; i <= n; i++) { + + mincolval = MAX(m, i); + matrix[(int)i][0] = i; + + char s_i = source[i-1]; + + for (j = 1; j <= m; j++) { + + char t_j = target[j-1]; + + char cost = (s_i == t_j ? 0 : 1); + + char above = matrix[i-1][(int)j]; + char left = matrix[(int)i][j-1]; + char diag = matrix[i-1][j-1]; + cell = MIN(above + 1, MIN(left + 1, diag + cost)); + + // Cover transposition, in addition to deletion, + // insertion and substitution. This step is taken from: + // Berghel, Hal ; Roach, David : "An Extension of Ukkonen's + // Enhanced Dynamic Programming ASM Algorithm" + // (http://www.acm.org/~hlb/publications/asm/asm.html) + + if (i > 2 && j > 2) { + char trans = matrix[i-2][j-2] + 1; + if (source[i-2] != t_j) + trans++; + if (s_i != target[j-2]) + trans++; + if (cell > trans) + cell = trans; + } + + mincolval = MIN(mincolval, cell); + matrix[(int)i][(int)j] = cell; + } + + if (mincolval >= maxdist) + break; + + } + + if (i == n + 1) + return (int) matrix[(int)n][(int)m]; + else + return maxdist; +} + +void +tracker_dbus_method_search_suggest (DBusRec *rec) +{ + DBusError dbus_error; + DBusMessage *reply; + gchar *term, *str; + gint maxdist; + gint dist, tsiz; + gchar *winner_str; + gint winner_dist; + char *tmp; + int hits; + + dbus_error_init (&dbus_error); + if (!dbus_message_get_args (rec->message, NULL, + DBUS_TYPE_STRING, &term, + DBUS_TYPE_INT32, &maxdist, + DBUS_TYPE_INVALID)) { + tracker_set_error (rec, "DBusError: %s;%s", dbus_error.name, dbus_error.message); + dbus_error_free (&dbus_error); + return; + } + + winner_str = NULL; + + criterinit (tracker->file_indexer->word_index); + + str = criternext (tracker->file_indexer->word_index, NULL); + while (str != NULL) { + dist = levenshtein (term, str, 0); + if (dist != -1 && dist < maxdist) { + hits = 0; + if ((tmp = crget (tracker->file_indexer->word_index, str, -1, 0, -1, &tsiz)) != NULL) { + hits = tsiz / sizeof (WordDetails); + free (tmp); + } + if (hits > 0) { + if (winner_str == NULL) { + winner_str = strdup (str); + winner_dist = dist; + } + else if (dist < winner_dist) { + free (winner_str); + winner_str = strdup (str); + winner_dist = dist; + } + } + else { + tracker_log ("No hits for %s!", str); + } + } + free (str); + str = criternext (tracker->file_indexer->word_index, NULL); + } + + if (winner_str == NULL) { + winner_str = strdup (term); + } + + tracker_log ("Suggested spelling for %s is %s.", term, winner_str); + + reply = dbus_message_new_method_return (rec->message); + + dbus_message_append_args (reply, + DBUS_TYPE_STRING, &winner_str, + DBUS_TYPE_INVALID); + free (winner_str); + + dbus_connection_send (rec->connection, reply, NULL); + + dbus_message_unref (reply); + +} + Index: src/trackerd/trackerd.c =================================================================== --- src/trackerd/trackerd.c (revision 527) +++ src/trackerd/trackerd.c (working copy) @@ -1548,7 +1548,14 @@ break; + case DBUS_ACTION_SEARCH_SUGGEST: + tracker_dbus_method_search_suggest (rec); + + break; + + + case DBUS_ACTION_FILES_EXISTS: tracker_dbus_method_files_exists (rec); Index: src/trackerd/tracker-dbus.c =================================================================== --- src/trackerd/tracker-dbus.c (revision 527) +++ src/trackerd/tracker-dbus.c (working copy) @@ -291,7 +291,14 @@ + } else if (dbus_message_is_method_call (message, TRACKER_INTERFACE_SEARCH, TRACKER_METHOD_SEARCH_SUGGEST)) { + dbus_message_ref (message); + rec->action = DBUS_ACTION_SEARCH_SUGGEST; + + + + } else if (dbus_message_is_method_call (message, TRACKER_INTERFACE_FILES, TRACKER_METHOD_FILES_EXISTS)) { dbus_message_ref (message); Index: src/trackerd/tracker-dbus.h =================================================================== --- src/trackerd/tracker-dbus.h (revision 527) +++ src/trackerd/tracker-dbus.h (working copy) @@ -71,6 +71,7 @@ #define TRACKER_METHOD_SEARCH_METADATA "Metadata" #define TRACKER_METHOD_SEARCH_MATCHING_FIELDS "MatchingFields" #define TRACKER_METHOD_SEARCH_QUERY "Query" +#define TRACKER_METHOD_SEARCH_SUGGEST "Suggest" /* File Interface */ #define TRACKER_METHOD_FILES_EXISTS "Exists" @@ -136,6 +137,7 @@ DBUS_ACTION_SEARCH_METADATA, DBUS_ACTION_SEARCH_MATCHING_FIELDS, DBUS_ACTION_SEARCH_QUERY, + DBUS_ACTION_SEARCH_SUGGEST, DBUS_ACTION_FILES_EXISTS, DBUS_ACTION_FILES_CREATE, Index: src/libtracker/tracker.h =================================================================== --- src/libtracker/tracker.h (revision 527) +++ src/libtracker/tracker.h (working copy) @@ -129,6 +129,7 @@ char * tracker_search_get_snippet (TrackerClient *client, ServiceType service, const char *uri, const char *search_text, GError **error); char ** tracker_search_metadata (TrackerClient *client, ServiceType service, const char *field, const char* search_text, int offset, int max_hits, GError **error); GPtrArray * tracker_search_query (TrackerClient *client, int live_query_id, ServiceType service, char **fields, const char *search_text, const char *keywords, const char *query, int offset, int max_hits, gboolean sort_by_service, GError **error); +gchar * tracker_search_suggest (TrackerClient *client, const char *search_text, int maxdist, GError **error); void tracker_files_create (TrackerClient *client, const char *uri, gboolean is_directory, const char *mime, int size, int mtime, GError **error); Index: src/libtracker/tracker.c =================================================================== --- src/libtracker/tracker.c (revision 527) +++ src/libtracker/tracker.c (working copy) @@ -611,6 +611,15 @@ return table; } +char * +tracker_search_suggest (TrackerClient *client, const char *search_term, int maxdist, GError **error) +{ + gchar *result; + if (org_freedesktop_Tracker_Search_suggest (client->proxy_search, search_term, maxdist, &result, &*error)) { + return result; + } + return NULL; +} Index: src/libtracker/tracker-client.h =================================================================== --- src/libtracker/tracker-client.h (revision 527) +++ src/libtracker/tracker-client.h (working copy) @@ -895,6 +895,17 @@ stuff->userdata = userdata; return dbus_g_proxy_begin_call (proxy, "Query", org_freedesktop_Tracker_Search_query_async_callback, stuff, g_free, G_TYPE_INT, IN_live_query_id, G_TYPE_STRING, IN_service, G_TYPE_STRV, IN_fields, G_TYPE_STRING, IN_search_text, G_TYPE_STRING, IN_keyword, G_TYPE_STRING, IN_query_condition, G_TYPE_BOOLEAN, IN_sort_by_service, G_TYPE_INT, IN_offset, G_TYPE_INT, IN_max_hits, G_TYPE_INVALID); } + +static +#ifdef G_HAVE_INLINE +inline +#endif +gboolean +org_freedesktop_Tracker_Search_suggest (DBusGProxy *proxy, const char * IN_search_text, const gint IN_maxdist, gchar ** OUT_result, GError **error) + +{ + return dbus_g_proxy_call (proxy, "Suggest", error, G_TYPE_STRING, IN_search_text, G_TYPE_INT, IN_maxdist, G_TYPE_INVALID, G_TYPE_STRING, OUT_result, G_TYPE_INVALID); +} #endif /* defined DBUS_GLIB_CLIENT_WRAPPERS_org_freedesktop_Tracker_Search */ #ifndef DBUS_GLIB_CLIENT_WRAPPERS_org_freedesktop_Tracker_Files Index: src/tracker-search-tool/tracker-search-tool.h =================================================================== --- src/tracker-search-tool/tracker-search-tool.h (revision 527) +++ src/tracker-search-tool/tracker-search-tool.h (working copy) @@ -121,7 +121,7 @@ int type; service_info_t *current_service; GtkWidget *metatile; - GtkWidget *no_results_label; + GtkWidget *no_results; GtkWidget *initial_label; GtkWidget *count_label; GtkWidget *message_box; Index: src/tracker-search-tool/tracker-search-tool-callbacks.c =================================================================== --- src/tracker-search-tool/tracker-search-tool-callbacks.c (revision 527) +++ src/tracker-search-tool/tracker-search-tool-callbacks.c (working copy) @@ -1795,3 +1795,18 @@ } return FALSE; } + +void +suggest_search_cb (GtkWidget *widget, + gpointer data) +{ + GSearchWindow *gsearch = data; + gchar *suggest; + + suggest = g_object_get_data (G_OBJECT (widget), "suggestion"); + + gtk_entry_set_text (GTK_ENTRY (gsearch->search_entry), suggest); + gtk_button_clicked (GTK_BUTTON (gsearch->find_button)); + +} + Index: src/tracker-search-tool/tracker-search-tool.c =================================================================== --- src/tracker-search-tool/tracker-search-tool.c (revision 527) +++ src/tracker-search-tool/tracker-search-tool.c (working copy) @@ -778,11 +778,43 @@ static void add_no_files_found_message (GSearchWindow * gsearch) { - if (!gsearch->no_results_label) { + gchar *suggest, *str; + gchar *search_term = (gchar *) gtk_entry_get_text (GTK_ENTRY (gsearch->search_entry)); - gsearch->no_results_label = gtk_label_new (_("Your search returned no results.")); - gtk_widget_show (gsearch->no_results_label); - gtk_box_pack_start (GTK_BOX (gsearch->message_box), gsearch->no_results_label, TRUE, TRUE, 12); + GtkWidget *label; + GtkWidget *box1, *box2; + GtkWidget *button; + + if (!gsearch->no_results) { + + gsearch->no_results = gtk_vbox_new (FALSE, 0); + label = gtk_label_new (_("Your search returned no results.")); + gtk_box_pack_start (GTK_BOX (gsearch->no_results), label, FALSE, FALSE, 12); + + box1 = gtk_hbox_new (FALSE, 0); + box2 = gtk_hbox_new (FALSE, 0); + label = gtk_label_new (_("Did you mean")); + gtk_box_pack_start (GTK_BOX (box2), label, FALSE, TRUE, 0); + + suggest = tracker_search_suggest (tracker_client, search_term, 4, NULL); + str = g_strconcat ("<b><i><u>", suggest, "</u></i></b>?", NULL); + button = gtk_button_new (); + gtk_button_set_relief (GTK_BUTTON (button), GTK_RELIEF_NONE); + label = gtk_label_new (NULL); + gtk_label_set_markup (label, str); + g_free (str); + gtk_container_add (GTK_CONTAINER (button), label); + gtk_box_pack_start (GTK_BOX (box2), button, FALSE, TRUE, 0); + gtk_box_pack_start (GTK_BOX (box1), box2, TRUE, FALSE, 0); + gtk_box_pack_start (GTK_BOX (gsearch->no_results), box1, FALSE, FALSE, 12); + + gtk_box_pack_start (GTK_BOX (gsearch->message_box), gsearch->no_results, TRUE, TRUE, 12); + + gtk_widget_show_all (gsearch->no_results); + + g_object_set_data (G_OBJECT (button), "suggestion", suggest); + g_signal_connect (G_OBJECT (button), "clicked", + G_CALLBACK (suggest_search_cb), gsearch); } @@ -2250,9 +2282,9 @@ gsearch->initial_label = NULL; } - if (gsearch->no_results_label) { - gtk_widget_destroy (gsearch->no_results_label); - gsearch->no_results_label = NULL; + if (gsearch->no_results) { + gtk_widget_destroy (gsearch->no_results); + gsearch->no_results = NULL; } @@ -2624,7 +2656,7 @@ gtk_box_pack_start (GTK_BOX (vbox), gsearch->initial_label, TRUE, TRUE, 12); - gsearch->no_results_label = NULL; + gsearch->no_results = NULL; gtk_widget_show (gsearch->initial_label); Index: src/tracker-search-tool/tracker-search-tool-callbacks.h =================================================================== --- src/tracker-search-tool/tracker-search-tool-callbacks.h (revision 527) +++ src/tracker-search-tool/tracker-search-tool-callbacks.h (working copy) @@ -177,6 +177,10 @@ GdkEventWindowState * event, gpointer data); +void +suggest_search_cb (GtkWidget *widget, + gpointer data); + #ifdef __cplusplus } #endif
_______________________________________________ tracker-list mailing list [email protected] http://mail.gnome.org/mailman/listinfo/tracker-list
