Add confidence to AutocompleteMatch.

chrome/browser/autocomplete/history_url_provider.cc

 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "chrome/browser/autocomplete/history_url_provider.h"
 
 #include <algorithm>
 
 #include "base/basictypes.h"
 #include "base/message_loop.h"
@@ skipping 227 matching lines @@
   if (what_you_typed_match.is_history_what_you_typed_match &&
       (!backend || !params->dont_suggest_exact_input) &&
       FixupExactSuggestion(db, params->input, &what_you_typed_match,
                            &history_matches)) {
     // Got an exact match for the user's input.  Treat it as the best match
     // regardless of the input type.
     exact_suggestion = 1;
     params->matches.push_back(what_you_typed_match);
   } else if (params->prevent_inline_autocomplete ||
       history_matches.empty() ||
-      !PromoteMatchForInlineAutocomplete(params, history_matches.front())) {
+      !PromoteMatchForInlineAutocomplete(params, history_matches.front(),
+                                         history_matches)) {
     // Failed to promote any URLs for inline autocompletion.  Use the What You
     // Typed match, if we have it.
     first_match = 0;
     if (have_what_you_typed_match)
       params->matches.push_back(what_you_typed_match);
   }
 
   // This is the end of the synchronous pass.
   if (!backend)
     return;
 
   // Remove redirects and trim list to size.  We want to provide up to
   // kMaxMatches results plus the What You Typed result, if it was added to
   // |history_matches| above.
   CullRedirects(backend, &history_matches, kMaxMatches + exact_suggestion);
 
   // Convert the history matches to autocomplete matches.
   for (size_t i = first_match; i < history_matches.size(); ++i) {
     const HistoryMatch& match = history_matches[i];
     DCHECK(!have_what_you_typed_match ||
            (match.url_info.url() !=
             GURL(params->matches.front().destination_url)));
-    params->matches.push_back(HistoryMatchToACMatch(params, match, NORMAL,
-        history_matches.size() - 1 - i));
+    AutocompleteMatch ac_match =
+        HistoryMatchToACMatch(params, match, history_matches, NORMAL,
+                              history_matches.size() - 1 - i);
+    UMA_HISTOGRAM_COUNTS_100("Autocomplete.Confidence_HistoryUrl",
+                             ac_match.confidence * 100);
+    params->matches.push_back(ac_match);
   }
 }
 
 // Called on the main thread when the query is complete.
 void HistoryURLProvider::QueryComplete(
     HistoryURLProviderParams* params_gets_deleted) {
   // Ensure |params_gets_deleted| gets deleted on exit.
   scoped_ptr<HistoryURLProviderParams> params(params_gets_deleted);
 
   // If the user hasn't already started another query, clear our member pointer
@@ skipping 12 matching lines @@
     UpdateStarredStateOfMatches();
   }
 
   done_ = true;
   listener_->OnProviderUpdate(true);
 }
 
 AutocompleteMatch HistoryURLProvider::SuggestExactInput(
     const AutocompleteInput& input,
     bool trim_http) {
+  // TODO(dominich): Find a confidence measure for this.
   AutocompleteMatch match(this,
-      CalculateRelevance(input.type(), WHAT_YOU_TYPED, 0), false,
+      CalculateRelevance(input.type(), WHAT_YOU_TYPED, 0), 0.0f, false,
       AutocompleteMatch::URL_WHAT_YOU_TYPED);
+  UMA_HISTOGRAM_COUNTS_100("Autocomplete.Confidence_HistoryUrl",
+                           match.confidence * 100);
 
   const GURL& url = input.canonicalized_url();
   if (url.is_valid()) {
     match.destination_url = url;
 
     // Trim off "http://" if the user didn't type it.
     // NOTE: We use TrimHttpPrefix() here rather than StringForURLDisplay() to
     // strip the scheme as we need to know the offset so we can adjust the
     // |match_location| below.  StringForURLDisplay() and TrimHttpPrefix() have
     // slightly different behavior as well (the latter will strip even without
@@ skipping 86 matching lines @@
   // Promote as an exact match.
   match->relevance = CalculateRelevance(input.type(), type, 0);
 
   // Put it on the front of the HistoryMatches for redirect culling.
   EnsureMatchPresent(info, string16::npos, false, matches, true);
   return true;
 }
 
 bool HistoryURLProvider::PromoteMatchForInlineAutocomplete(
     HistoryURLProviderParams* params,
-    const HistoryMatch& match) {
+    const HistoryMatch& match,
+    const HistoryMatches& matches) {
   // Promote the first match if it's been typed at least n times, where n == 1
   // for "simple" (host-only) URLs and n == 2 for others.  We set a higher bar
   // for these long URLs because it's less likely that users will want to visit
   // them again.  Even though we don't increment the typed_count for pasted-in
   // URLs, if the user manually edits the URL or types some long thing in by
   // hand, we wouldn't want to immediately start autocompleting it.
   if (!match.url_info.typed_count() ||
       ((match.url_info.typed_count() == 1) &&
        !history::IsHostOnly(match.url_info.url())))
     return false;
 
   // In the case where the user has typed "foo.com" and visited (but not typed)
   // "foo/", and the input is "foo", we can reach here for "foo.com" during the
   // first pass but have the second pass suggest the exact input as a better
   // URL.  Since we need both passes to agree, and since during the first pass
   // there's no way to know about "foo/", make reaching this point prevent any
   // future pass from suggesting the exact input as a better match.
   params->dont_suggest_exact_input = true;
-  params->matches.push_back(HistoryMatchToACMatch(params, match,
+  params->matches.push_back(HistoryMatchToACMatch(params, match, matches,
                                                   INLINE_AUTOCOMPLETE, 0));
   return true;
 }
 
 HistoryURLProvider::~HistoryURLProvider() {}
 
 // static
 history::Prefixes HistoryURLProvider::GetPrefixes() {
   // We'll complete text following these prefixes.
   // NOTE: There's no requirement that these be in any particular order.
@@ skipping 20 matching lines @@
 
     case WHAT_YOU_TYPED:
       return 1200;
 
     default:
       return 900 + static_cast<int>(match_number);
   }
 }
 
 // static
+float HistoryURLProvider::CalculateConfidence(
+    const history::HistoryMatch& match,
+    const history::HistoryMatches& matches) {

[mrossetti, 2011/08/09 23:40:43]

I think this should just be the precalculated sum of scores.

+  // TODO(dominich): Take into account bookmarked page?
+  // TODO(dominich): See CompareHistoryMatch for more measures to include.
+  // Using typed count in place of visit count as:
+  // - It's a better indicator of what the user wants to open given that they
+  //   are typing in the address bar (users tend to open certain URLs by typing
+  //   and others by e.g. bookmarks, so visit_count is a good indicator of
+  //   overall interest but a bad one for specifically omnibox interest).
+  // - Since the DB query is sorted by typed_count, the results may be
+  //   effectively a random selection as far as visit_counts are concerned
+  //   (meaning many high-visit_count-URLs may be present in one query and
+  //   absent in a similar one), leading to wild swings in confidence for the
+  //   same result across distinct queries.
+  float numerator = match.url_info.typed_count();
+  float denominator = 0.0f;
+  for (history::HistoryMatches::const_iterator it = matches.begin();

[mrossetti, 2011/08/09 23:40:43]

Same thought as with the HistoryQuickProvider: why not calculate the sum once
the asynch pass has been completed rather than having to recalculate it for each
match.

[dominich, 2011/08/10 16:10:13]

Once the algorithm for the calculation settles to a stable state (the one that
gives the best prediction rate for prerender) I will optimize.

+       it != matches.end(); ++it) {
+    denominator += it->url_info.typed_count();
+  }
+  DCHECK(denominator > 0);
+  return numerator / denominator;
+}
+
+// static
 void HistoryURLProvider::PromoteOrCreateShorterSuggestion(
     history::URLDatabase* db,
     const HistoryURLProviderParams& params,
     bool have_what_you_typed_match,
     const AutocompleteMatch& what_you_typed_match,
     HistoryMatches* matches) {
   if (matches->empty())
     return;  // No matches, nothing to do.
 
   // Determine the base URL from which to search, and whether that URL could
@@ skipping 283 matching lines @@
     next = matches->erase(next);
     if (static_cast<size_t>(next - matches->begin()) < next_index)
       next_index--;
   }
   return next_index;
 }
 
 AutocompleteMatch HistoryURLProvider::HistoryMatchToACMatch(
     HistoryURLProviderParams* params,
     const HistoryMatch& history_match,
+    const HistoryMatches& history_matches,
     MatchType match_type,
     size_t match_number) {
   const history::URLRow& info = history_match.url_info;
   AutocompleteMatch match(this,
       CalculateRelevance(params->input.type(), match_type, match_number),
+      CalculateConfidence(history_match, history_matches),
       !!info.visit_count(), AutocompleteMatch::HISTORY_URL);
   match.destination_url = info.url();
   DCHECK(match.destination_url.is_valid());
   size_t inline_autocomplete_offset =
       history_match.input_location + params->input.text().length();
   std::string languages = (match_type == WHAT_YOU_TYPED) ?
       std::string() : params->languages;
   const net::FormatUrlTypes format_types = net::kFormatUrlOmitAll &
       ~((params->trim_http && !history_match.match_in_scheme) ?
           0 : net::kFormatUrlOmitHTTP);
@@ skipping 23 matching lines @@
         &match.contents_class);
   }
   match.description = info.title();
   AutocompleteMatch::ClassifyMatchInString(params->input.text(),
                                            info.title(),
                                            ACMatchClassification::NONE,
                                            &match.description_class);
 
   return match;
 }