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));
+    // TODO(dominich): Should this be history_matches.size() - first_match - i?

[Peter Kasting, 2011/08/09 20:53:00]

No, it should not.

[dominich, 2011/08/09 21:43:43]

Done.

+    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): Check that 100% confidence makes sense for exact input.

[Peter Kasting, 2011/08/09 20:53:00]

It doesn't.  This will mean the what-you-typed match is always scored as 100%,
which is definitely wrong sometimes.  For example, if we promote a match for
inline autocompletion, that match will outrank this one, which suggests it
should have higher confidence as well.  Or if the user types some characters and
then pastes, then the "ctrl" keydown during pasting will add ".com" to the end
of the current typing and this will then score that at 100%.

[dominich, 2011/08/09 21:43:43]

You're mixing up the notion of rank and confidence. While they can be mixed it's
not clear to me that they should be. The rank is a cross-provider measure while
the confidence is a per-provider measure. It also is a suggestion of what we
should do with the result.

100% confident here means that /if/ the what-you-type match is the top result
then we should definitely apply instant or prerender to it.

The issue of the pasting is an interesting one but I'm not sure how we can avoid
that and still keep the confidence here relatively high.

I will set the confidence to 0 here for the first pass of stats so it doesn't
pollute them.

   AutocompleteMatch match(this,
-      CalculateRelevance(input.type(), WHAT_YOU_TYPED, 0), false,
+      CalculateRelevance(input.type(), WHAT_YOU_TYPED, 0), 1.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) {
+  // TODO(dominich): Take into account typed count?

[Peter Kasting, 2011/08/09 20:53:00]

See comments in HCP for why typed_count is better than visit_count.

You also don't check some important clues like IsHostOnly().

[dominich, 2011/08/09 21:43:43]

It looks like CompareHistoryMatch is a good starting point for a more inclusive
measure.

I would like to get in a simple (naive) version with histograms and then try
different calculations for each provider to get the best results, ie increase
the proportion of successful prerenders.

+  // TODO(dominich): Take into account bookmarked page?
+  float numerator = match.url_info.visit_count();
+  float denominator = 0.0f;
+  for (history::HistoryMatches::const_iterator it = matches.begin();
+       it != matches.end(); ++it) {

[Peter Kasting, 2011/08/09 20:53:00]

Nit: No need for {}

[dominich, 2011/08/09 21:43:43]

See comment on HCP as to why I prefer to keep this.

+    denominator += it->url_info.visit_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;
 }