Add confidence to AutocompleteMatch.

chrome/browser/autocomplete/history_contents_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_contents_provider.h"
 
 #include "base/callback.h"
 #include "base/metrics/histogram.h"
 #include "base/string_util.h"
 #include "base/utf_string_conversions.h"
 #include "chrome/browser/autocomplete/autocomplete_match.h"
 #include "chrome/browser/bookmarks/bookmark_model.h"
 #include "chrome/browser/bookmarks/bookmark_utils.h"
 #include "chrome/browser/profiles/profile.h"
 #include "chrome/common/url_constants.h"
 #include "googleurl/src/url_util.h"
 #include "net/base/net_util.h"
 
 using base::TimeTicks;
+using history::HistoryDatabase;
 
 namespace {
 
 // Number of days to search for full text results. The longer this is, the more
 // time it will take.
 const int kDaysToSearch = 30;
 
-// When processing the results from the history query, this structure points to
-// a single result. It allows the results to be sorted and processed without
-// modifying the larger and slower results structure.
-struct MatchReference {
-  MatchReference(const history::URLResult* result, int relevance)
-      : result(result),
-        relevance(relevance) {
-  }
+}  // end namespace
 
-  const history::URLResult* result;
-  int relevance;  // Score of relevance computed by CalculateRelevance.
-};
-
-// This is a > operator for MatchReference.
-bool CompareMatchRelevance(const MatchReference& a, const MatchReference& b) {
-  if (a.relevance != b.relevance)
-    return a.relevance > b.relevance;
-
-  // Want results in reverse-chronological order all else being equal.
-  return a.result->last_visit() > b.result->last_visit();
+HistoryContentsProvider::MatchReference::MatchReference(
+    const history::URLResult* result,
+    int relevance,
+    float confidence)
+    : result(result),
+      relevance(relevance),
+      confidence(confidence) {
 }
 
-}  // namespace
-
-using history::HistoryDatabase;
+// static
+bool HistoryContentsProvider::MatchReference::CompareRelevance(
+    const HistoryContentsProvider::MatchReference& lhs,
+    const HistoryContentsProvider::MatchReference& rhs) {
+  if (lhs.relevance != rhs.relevance)
+    return lhs.relevance > rhs.relevance;
+  return lhs.result->last_visit() > rhs.result->last_visit();
+}
 
 HistoryContentsProvider::HistoryContentsProvider(ACProviderListener* listener,
                                                  Profile* profile,
                                                  bool body_only)
     : HistoryProvider(listener, profile, "HistoryContents"),
       star_title_count_(0),
       star_contents_count_(0),
       title_count_(0),
       contents_count_(0),
       input_type_(AutocompleteInput::INVALID),
@@ skipping 118 matching lines @@
 
   // Make the result references and score the results.
   std::vector<MatchReference> result_refs;
   result_refs.reserve(results_.size());
 
   // Results are sorted in decreasing order so we run the loop backwards so that
   // the relevance increment favors the higher ranked results.
   for (std::vector<history::URLResult*>::const_reverse_iterator i =
        results_.rbegin(); i != results_.rend(); ++i) {
     history::URLResult* result = *i;
-    MatchReference ref(result, CalculateRelevance(*result));
+    MatchReference ref(result, CalculateRelevance(*result),
+                       CalculateConfidence(*result, results_));
     result_refs.push_back(ref);
   }
 
   // Get the top matches and add them.
   size_t max_for_provider = std::min(kMaxMatches, result_refs.size());
   std::partial_sort(result_refs.begin(), result_refs.begin() + max_for_provider,
-                    result_refs.end(), &CompareMatchRelevance);
+                    result_refs.end(), &MatchReference::CompareRelevance);
   matches_.clear();
   for (size_t i = 0; i < max_for_provider; i++) {
-    matches_.push_back(ResultToMatch(*result_refs[i].result,
-                                     result_refs[i].relevance));
+    AutocompleteMatch match(ResultToMatch(result_refs[i]));
+    UMA_HISTOGRAM_COUNTS_100("Autocomplete.Confidence_HistoryContents",
+                             match.confidence * 100);
+    matches_.push_back(match);
   }

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

Perhaps calculate sum of scores here.

 }
 
 // TODO(mrossetti): Remove MatchInTitle once body_only_ becomes permanent.
 bool HistoryContentsProvider::MatchInTitle(const history::URLResult& result) {
   return !body_only_ && !result.title_match_positions().empty();
 }
 
 AutocompleteMatch HistoryContentsProvider::ResultToMatch(
-    const history::URLResult& result,
-    int score) {
-  AutocompleteMatch match(this, score, true, MatchInTitle(result) ?
-      AutocompleteMatch::HISTORY_TITLE : AutocompleteMatch::HISTORY_BODY);
+    const MatchReference& match_reference) {
+  const history::URLResult& result = *match_reference.result;
+  AutocompleteMatch match(this, match_reference.relevance,
+      match_reference.confidence, true, MatchInTitle(result) ?
+          AutocompleteMatch::HISTORY_TITLE : AutocompleteMatch::HISTORY_BODY);
   match.contents = StringForURLDisplay(result.url(), true, trim_http_);
   match.fill_into_edit =
       AutocompleteInput::FormattedStringWithEquivalentMeaning(result.url(),
                                                               match.contents);
   match.destination_url = result.url();
   match.contents_class.push_back(
       ACMatchClassification(0, ACMatchClassification::URL));
   match.description = result.title();
   match.starred =
       (profile_->GetBookmarkModel() &&
@@ skipping 31 matching lines @@
 int HistoryContentsProvider::CalculateRelevance(
     const history::URLResult& result) {
   const bool in_title = MatchInTitle(result);
   if (!profile_->GetBookmarkModel() ||
       !profile_->GetBookmarkModel()->IsBookmarked(result.url()))
     return in_title ? (700 + title_count_++) : (500 + contents_count_++);
   return in_title ?
       (1000 + star_title_count_++) : (550 + star_contents_count_++);
 }
 
+float HistoryContentsProvider::CalculateConfidence(
+    const history::URLResult& result,
+    const history::QueryResults& results) const {
+  // Calculate a score of [0, 0.9] based on typed count.
+  // Using typed count in place of visit count as:
+  // - It's a better indicator of what the user wants to open given that they

[Peter Kasting, 2011/08/09 21:52:38]

Nit: To save copy+pasting, you might want to just say "see comments on
HistoryURLProvider::CalculateConfidence() for why we use typed_count rather than
visit_count here."

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

I have kept these separate because the details may change. I did consider moving
this calculation to the base HistoryProvider class as a default implementation
but the derived classes use slightly different types. Perhaps this is something
that could be cleaned up later.

+  //   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 = result.typed_count();
+  float denominator = 0.0f;
+  for (std::vector<history::URLResult*>::const_iterator it = results.begin();
+       it != results.end(); ++it) {
+    denominator += (*it)->typed_count();
+  }
+  // It should only be equal to 0 if the result is not in the results vector.
+  DCHECK(denominator > 0);
+  float score = 0.9f * (numerator / denominator);
+
+  // Add 0.1 if the URL is bookmarked to get a final range of [0, 1].
+  if (profile_->GetBookmarkModel() &&
+      profile_->GetBookmarkModel()->IsBookmarked(result.url())) {
+    score += 0.1f;
+  }
+
+  return score;
+}
+
 void HistoryContentsProvider::QueryBookmarks(const AutocompleteInput& input) {
   BookmarkModel* bookmark_model = profile_->GetBookmarkModel();
   if (!bookmark_model)
     return;
 
   DCHECK(results_.empty());
 
   TimeTicks start_time = TimeTicks::Now();
   std::vector<bookmark_utils::TitleMatch> matches;
   bookmark_model->GetBookmarksWithTitlesMatching(input.text(),
                                                  kMaxMatches, &matches);
   for (size_t i = 0; i < matches.size(); ++i)
     AddBookmarkTitleMatchToResults(matches[i]);
   UMA_HISTOGRAM_TIMES("Omnibox.QueryBookmarksTime",
                       TimeTicks::Now() - start_time);
 }
 
 void HistoryContentsProvider::AddBookmarkTitleMatchToResults(
     const bookmark_utils::TitleMatch& match) {
   history::URLResult url_result(match.node->url(), match.match_positions);
   url_result.set_title(match.node->GetTitle());
   results_.AppendURLBySwapping(&url_result);
 }