| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | |
| 2 // Use of this source code is governed by a BSD-style license that can be | |
| 3 // found in the LICENSE file. | |
| 4 | |
| 5 #include "chrome/browser/history/scored_history_match.h" | |
| 6 | |
| 7 #include <algorithm> | |
| 8 #include <functional> | |
| 9 #include <iterator> | |
| 10 #include <numeric> | |
| 11 #include <set> | |
| 12 | |
| 13 #include <math.h> | |
| 14 | |
| 15 #include "base/logging.h" | |
| 16 #include "base/metrics/histogram.h" | |
| 17 #include "base/strings/string_util.h" | |
| 18 #include "base/strings/utf_string_conversions.h" | |
| 19 #include "chrome/browser/autocomplete/history_url_provider.h" | |
| 20 #include "components/bookmarks/browser/bookmark_utils.h" | |
| 21 #include "components/history/core/browser/history_client.h" | |
| 22 #include "components/omnibox/omnibox_field_trial.h" | |
| 23 #include "components/omnibox/url_prefix.h" | |
| 24 #include "content/public/browser/browser_thread.h" | |
| 25 | |
| 26 namespace history { | |
| 27 | |
| 28 // ScoredHistoryMatch ---------------------------------------------------------- | |
| 29 | |
| 30 // static | |
| 31 const size_t ScoredHistoryMatch::kMaxVisitsToScore = 10; | |
| 32 const int ScoredHistoryMatch::kDaysToPrecomputeRecencyScoresFor = 366; | |
| 33 const int ScoredHistoryMatch::kMaxRawTermScore = 30; | |
| 34 float* ScoredHistoryMatch::raw_term_score_to_topicality_score_ = NULL; | |
| 35 float* ScoredHistoryMatch::days_ago_to_recency_score_ = NULL; | |
| 36 bool ScoredHistoryMatch::initialized_ = false; | |
| 37 int ScoredHistoryMatch::bookmark_value_ = 1; | |
| 38 bool ScoredHistoryMatch::allow_tld_matches_ = false; | |
| 39 bool ScoredHistoryMatch::allow_scheme_matches_ = false; | |
| 40 bool ScoredHistoryMatch::also_do_hup_like_scoring_ = false; | |
| 41 int ScoredHistoryMatch::max_assigned_score_for_non_inlineable_matches_ = -1; | |
| 42 | |
| 43 ScoredHistoryMatch::ScoredHistoryMatch() | |
| 44 : raw_score_(0), | |
| 45 can_inline_(false) { | |
| 46 Init(); | |
| 47 } | |
| 48 | |
| 49 ScoredHistoryMatch::ScoredHistoryMatch( | |
| 50 const URLRow& row, | |
| 51 const VisitInfoVector& visits, | |
| 52 const std::string& languages, | |
| 53 const base::string16& lower_string, | |
| 54 const String16Vector& terms, | |
| 55 const WordStarts& terms_to_word_starts_offsets, | |
| 56 const RowWordStarts& word_starts, | |
| 57 const base::Time now, | |
| 58 HistoryClient* history_client) | |
| 59 : HistoryMatch(row, 0, false, false), | |
| 60 raw_score_(0), | |
| 61 can_inline_(false) { | |
| 62 Init(); | |
| 63 | |
| 64 GURL gurl = row.url(); | |
| 65 if (!gurl.is_valid()) | |
| 66 return; | |
| 67 | |
| 68 // Figure out where each search term appears in the URL and/or page title | |
| 69 // so that we can score as well as provide autocomplete highlighting. | |
| 70 base::OffsetAdjuster::Adjustments adjustments; | |
| 71 base::string16 url = | |
| 72 bookmarks::CleanUpUrlForMatching(gurl, languages, &adjustments); | |
| 73 base::string16 title = bookmarks::CleanUpTitleForMatching(row.title()); | |
| 74 int term_num = 0; | |
| 75 for (String16Vector::const_iterator iter = terms.begin(); iter != terms.end(); | |
| 76 ++iter, ++term_num) { | |
| 77 base::string16 term = *iter; | |
| 78 TermMatches url_term_matches = MatchTermInString(term, url, term_num); | |
| 79 TermMatches title_term_matches = MatchTermInString(term, title, term_num); | |
| 80 if (url_term_matches.empty() && title_term_matches.empty()) | |
| 81 return; // A term was not found in either URL or title - reject. | |
| 82 url_matches_.insert(url_matches_.end(), url_term_matches.begin(), | |
| 83 url_term_matches.end()); | |
| 84 title_matches_.insert(title_matches_.end(), title_term_matches.begin(), | |
| 85 title_term_matches.end()); | |
| 86 } | |
| 87 | |
| 88 // Sort matches by offset and eliminate any which overlap. | |
| 89 // TODO(mpearson): Investigate whether this has any meaningful | |
| 90 // effect on scoring. (It's necessary at some point: removing | |
| 91 // overlaps and sorting is needed to decide what to highlight in the | |
| 92 // suggestion string. But this sort and de-overlap doesn't have to | |
| 93 // be done before scoring.) | |
| 94 url_matches_ = SortAndDeoverlapMatches(url_matches_); | |
| 95 title_matches_ = SortAndDeoverlapMatches(title_matches_); | |
| 96 | |
| 97 // We can inline autocomplete a match if: | |
| 98 // 1) there is only one search term | |
| 99 // 2) AND the match begins immediately after one of the prefixes in | |
| 100 // URLPrefix such as http://www and https:// (note that one of these | |
| 101 // is the empty prefix, for cases where the user has typed the scheme) | |
| 102 // 3) AND the search string does not end in whitespace (making it look to | |
| 103 // the IMUI as though there is a single search term when actually there | |
| 104 // is a second, empty term). | |
| 105 // |best_inlineable_prefix| stores the inlineable prefix computed in | |
| 106 // clause (2) or NULL if no such prefix exists. (The URL is not inlineable.) | |
| 107 // Note that using the best prefix here means that when multiple | |
| 108 // prefixes match, we'll choose to inline following the longest one. | |
| 109 // For a URL like "http://www.washingtonmutual.com", this means | |
| 110 // typing "w" will inline "ashington..." instead of "ww.washington...". | |
| 111 const URLPrefix* best_inlineable_prefix = | |
| 112 (!url_matches_.empty() && (terms.size() == 1)) ? | |
| 113 URLPrefix::BestURLPrefix(base::UTF8ToUTF16(gurl.spec()), terms[0]) : | |
| 114 NULL; | |
| 115 can_inline_ = (best_inlineable_prefix != NULL) && | |
| 116 !IsWhitespace(*(lower_string.rbegin())); | |
| 117 if (can_inline_) { | |
| 118 // Initialize innermost_match. | |
| 119 // The idea here is that matches that occur in the scheme or | |
| 120 // "www." are worse than matches which don't. For the URLs | |
| 121 // "http://www.google.com" and "http://wellsfargo.com", we want | |
| 122 // the omnibox input "w" to cause the latter URL to rank higher | |
| 123 // than the former. Note that this is not the same as checking | |
| 124 // whether one match's inlinable prefix has more components than | |
| 125 // the other match's, since in this example, both matches would | |
| 126 // have an inlinable prefix of "http://", which is one component. | |
| 127 // | |
| 128 // Instead, we look for the overall best (i.e., most components) | |
| 129 // prefix of the current URL, and then check whether the inlinable | |
| 130 // prefix has that many components. If it does, this is an | |
| 131 // "innermost" match, and should be boosted. In the example | |
| 132 // above, the best prefixes for the two URLs have two and one | |
| 133 // components respectively, while the inlinable prefixes each | |
| 134 // have one component; this means the first match is not innermost | |
| 135 // and the second match is innermost, resulting in us boosting the | |
| 136 // second match. | |
| 137 // | |
| 138 // Now, the code that implements this. | |
| 139 // The deepest prefix for this URL regardless of where the match is. | |
| 140 const URLPrefix* best_prefix = URLPrefix::BestURLPrefix( | |
| 141 base::UTF8ToUTF16(gurl.spec()), base::string16()); | |
| 142 DCHECK(best_prefix != NULL); | |
| 143 const int num_components_in_best_prefix = best_prefix->num_components; | |
| 144 // If the URL is inlineable, we must have a match. Note the prefix that | |
| 145 // makes it inlineable may be empty. | |
| 146 DCHECK(best_inlineable_prefix != NULL); | |
| 147 const int num_components_in_best_inlineable_prefix = | |
| 148 best_inlineable_prefix->num_components; | |
| 149 innermost_match = (num_components_in_best_inlineable_prefix == | |
| 150 num_components_in_best_prefix); | |
| 151 } | |
| 152 | |
| 153 const float topicality_score = GetTopicalityScore( | |
| 154 terms.size(), url, terms_to_word_starts_offsets, word_starts); | |
| 155 const float frequency_score = GetFrequency( | |
| 156 now, (history_client && history_client->IsBookmarked(gurl)), visits); | |
| 157 raw_score_ = GetFinalRelevancyScore(topicality_score, frequency_score); | |
| 158 raw_score_ = | |
| 159 (raw_score_ <= kint32max) ? static_cast<int>(raw_score_) : kint32max; | |
| 160 | |
| 161 if (also_do_hup_like_scoring_ && can_inline_) { | |
| 162 // HistoryURL-provider-like scoring gives any match that is | |
| 163 // capable of being inlined a certain minimum score. Some of these | |
| 164 // are given a higher score that lets them be shown in inline. | |
| 165 // This test here derives from the test in | |
| 166 // HistoryURLProvider::PromoteMatchForInlineAutocomplete(). | |
| 167 const bool promote_to_inline = (row.typed_count() > 1) || | |
| 168 (IsHostOnly() && (row.typed_count() == 1)); | |
| 169 int hup_like_score = promote_to_inline ? | |
| 170 HistoryURLProvider::kScoreForBestInlineableResult : | |
| 171 HistoryURLProvider::kBaseScoreForNonInlineableResult; | |
| 172 | |
| 173 // Also, if the user types the hostname of a host with a typed | |
| 174 // visit, then everything from that host get given inlineable scores | |
| 175 // (because the URL-that-you-typed will go first and everything | |
| 176 // else will be assigned one minus the previous score, as coded | |
| 177 // at the end of HistoryURLProvider::DoAutocomplete(). | |
| 178 if (base::UTF8ToUTF16(gurl.host()) == terms[0]) | |
| 179 hup_like_score = HistoryURLProvider::kScoreForBestInlineableResult; | |
| 180 | |
| 181 // HistoryURLProvider has the function PromoteOrCreateShorterSuggestion() | |
| 182 // that's meant to promote prefixes of the best match (if they've | |
| 183 // been visited enough related to the best match) or | |
| 184 // create/promote host-only suggestions (even if they've never | |
| 185 // been typed). The code is complicated and we don't try to | |
| 186 // duplicate the logic here. Instead, we handle a simple case: in | |
| 187 // low-typed-count ranges, give host-only matches (i.e., | |
| 188 // http://www.foo.com/ vs. http://www.foo.com/bar.html) a boost so | |
| 189 // that the host-only match outscores all the other matches that | |
| 190 // would normally have the same base score. This behavior is not | |
| 191 // identical to what happens in HistoryURLProvider even in these | |
| 192 // low typed count ranges--sometimes it will create/promote when | |
| 193 // this test does not (indeed, we cannot create matches like HUP | |
| 194 // can) and vice versa--but the underlying philosophy is similar. | |
| 195 if (!promote_to_inline && IsHostOnly()) | |
| 196 hup_like_score++; | |
| 197 | |
| 198 // All the other logic to goes into hup-like-scoring happens in | |
| 199 // the tie-breaker case of MatchScoreGreater(). | |
| 200 | |
| 201 // Incorporate hup_like_score into raw_score. | |
| 202 raw_score_ = std::max(raw_score_, hup_like_score); | |
| 203 } | |
| 204 | |
| 205 // If this match is not inlineable and there's a cap on the maximum | |
| 206 // score that can be given to non-inlineable matches, apply the cap. | |
| 207 if (!can_inline_ && (max_assigned_score_for_non_inlineable_matches_ != -1)) { | |
| 208 raw_score_ = std::min(max_assigned_score_for_non_inlineable_matches_, | |
| 209 raw_score_); | |
| 210 } | |
| 211 | |
| 212 // Now that we're done processing this entry, correct the offsets of the | |
| 213 // matches in |url_matches_| so they point to offsets in the original URL | |
| 214 // spec, not the cleaned-up URL string that we used for matching. | |
| 215 std::vector<size_t> offsets = OffsetsFromTermMatches(url_matches_); | |
| 216 base::OffsetAdjuster::UnadjustOffsets(adjustments, &offsets); | |
| 217 url_matches_ = ReplaceOffsetsInTermMatches(url_matches_, offsets); | |
| 218 } | |
| 219 | |
| 220 ScoredHistoryMatch::~ScoredHistoryMatch() {} | |
| 221 | |
| 222 // Comparison function for sorting ScoredMatches by their scores with | |
| 223 // intelligent tie-breaking. | |
| 224 bool ScoredHistoryMatch::MatchScoreGreater(const ScoredHistoryMatch& m1, | |
| 225 const ScoredHistoryMatch& m2) { | |
| 226 if (m1.raw_score_ != m2.raw_score_) | |
| 227 return m1.raw_score_ > m2.raw_score_; | |
| 228 | |
| 229 // This tie-breaking logic is inspired by / largely copied from the | |
| 230 // ordering logic in history_url_provider.cc CompareHistoryMatch(). | |
| 231 | |
| 232 // A URL that has been typed at all is better than one that has never been | |
| 233 // typed. (Note "!"s on each side.) | |
| 234 if (!m1.url_info.typed_count() != !m2.url_info.typed_count()) | |
| 235 return m1.url_info.typed_count() > m2.url_info.typed_count(); | |
| 236 | |
| 237 // Innermost matches (matches after any scheme or "www.") are better than | |
| 238 // non-innermost matches. | |
| 239 if (m1.innermost_match != m2.innermost_match) | |
| 240 return m1.innermost_match; | |
| 241 | |
| 242 // URLs that have been typed more often are better. | |
| 243 if (m1.url_info.typed_count() != m2.url_info.typed_count()) | |
| 244 return m1.url_info.typed_count() > m2.url_info.typed_count(); | |
| 245 | |
| 246 // For URLs that have each been typed once, a host (alone) is better | |
| 247 // than a page inside. | |
| 248 if (m1.url_info.typed_count() == 1) { | |
| 249 if (m1.IsHostOnly() != m2.IsHostOnly()) | |
| 250 return m1.IsHostOnly(); | |
| 251 } | |
| 252 | |
| 253 // URLs that have been visited more often are better. | |
| 254 if (m1.url_info.visit_count() != m2.url_info.visit_count()) | |
| 255 return m1.url_info.visit_count() > m2.url_info.visit_count(); | |
| 256 | |
| 257 // URLs that have been visited more recently are better. | |
| 258 return m1.url_info.last_visit() > m2.url_info.last_visit(); | |
| 259 } | |
| 260 | |
| 261 // static | |
| 262 TermMatches ScoredHistoryMatch::FilterTermMatchesByWordStarts( | |
| 263 const TermMatches& term_matches, | |
| 264 const WordStarts& terms_to_word_starts_offsets, | |
| 265 const WordStarts& word_starts, | |
| 266 size_t start_pos, | |
| 267 size_t end_pos) { | |
| 268 // Return early if no filtering is needed. | |
| 269 if (start_pos == std::string::npos) | |
| 270 return term_matches; | |
| 271 TermMatches filtered_matches; | |
| 272 WordStarts::const_iterator next_word_starts = word_starts.begin(); | |
| 273 WordStarts::const_iterator end_word_starts = word_starts.end(); | |
| 274 for (TermMatches::const_iterator iter = term_matches.begin(); | |
| 275 iter != term_matches.end(); ++iter) { | |
| 276 const size_t term_offset = terms_to_word_starts_offsets[iter->term_num]; | |
| 277 // Advance next_word_starts until it's >= the position of the term we're | |
| 278 // considering (adjusted for where the word begins within the term). | |
| 279 while ((next_word_starts != end_word_starts) && | |
| 280 (*next_word_starts < (iter->offset + term_offset))) | |
| 281 ++next_word_starts; | |
| 282 // Add the match if it's before the position we start filtering at or | |
| 283 // after the position we stop filtering at (assuming we have a position | |
| 284 // to stop filtering at) or if it's at a word boundary. | |
| 285 if ((iter->offset < start_pos) || | |
| 286 ((end_pos != std::string::npos) && (iter->offset >= end_pos)) || | |
| 287 ((next_word_starts != end_word_starts) && | |
| 288 (*next_word_starts == iter->offset + term_offset))) | |
| 289 filtered_matches.push_back(*iter); | |
| 290 } | |
| 291 return filtered_matches; | |
| 292 } | |
| 293 | |
| 294 float ScoredHistoryMatch::GetTopicalityScore( | |
| 295 const int num_terms, | |
| 296 const base::string16& url, | |
| 297 const WordStarts& terms_to_word_starts_offsets, | |
| 298 const RowWordStarts& word_starts) { | |
| 299 // Because the below thread is not thread safe, we check that we're | |
| 300 // only calling it from one thread: the UI thread. Specifically, | |
| 301 // we check "if we've heard of the UI thread then we'd better | |
| 302 // be on it." The first part is necessary so unit tests pass. (Many | |
| 303 // unit tests don't set up the threading naming system; hence | |
| 304 // CurrentlyOn(UI thread) will fail.) | |
| 305 DCHECK(!content::BrowserThread::IsThreadInitialized( | |
| 306 content::BrowserThread::UI) || | |
| 307 content::BrowserThread::CurrentlyOn(content::BrowserThread::UI)); | |
| 308 if (raw_term_score_to_topicality_score_ == NULL) { | |
| 309 raw_term_score_to_topicality_score_ = new float[kMaxRawTermScore]; | |
| 310 FillInTermScoreToTopicalityScoreArray(); | |
| 311 } | |
| 312 // A vector that accumulates per-term scores. The strongest match--a | |
| 313 // match in the hostname at a word boundary--is worth 10 points. | |
| 314 // Everything else is less. In general, a match that's not at a word | |
| 315 // boundary is worth about 1/4th or 1/5th of a match at the word boundary | |
| 316 // in the same part of the URL/title. | |
| 317 DCHECK_GT(num_terms, 0); | |
| 318 std::vector<int> term_scores(num_terms, 0); | |
| 319 WordStarts::const_iterator next_word_starts = | |
| 320 word_starts.url_word_starts_.begin(); | |
| 321 WordStarts::const_iterator end_word_starts = | |
| 322 word_starts.url_word_starts_.end(); | |
| 323 const size_t question_mark_pos = url.find('?'); | |
| 324 const size_t colon_pos = url.find(':'); | |
| 325 // The + 3 skips the // that probably appears in the protocol | |
| 326 // after the colon. If the protocol doesn't have two slashes after | |
| 327 // the colon, that's okay--all this ends up doing is starting our | |
| 328 // search for the next / a few characters into the hostname. The | |
| 329 // only times this can cause problems is if we have a protocol without | |
| 330 // a // after the colon and the hostname is only one or two characters. | |
| 331 // This isn't worth worrying about. | |
| 332 const size_t end_of_hostname_pos = (colon_pos != std::string::npos) ? | |
| 333 url.find('/', colon_pos + 3) : url.find('/'); | |
| 334 size_t last_part_of_hostname_pos = | |
| 335 (end_of_hostname_pos != std::string::npos) ? | |
| 336 url.rfind('.', end_of_hostname_pos) : url.rfind('.'); | |
| 337 // Loop through all URL matches and score them appropriately. | |
| 338 // First, filter all matches not at a word boundary and in the path (or | |
| 339 // later). | |
| 340 url_matches_ = FilterTermMatchesByWordStarts( | |
| 341 url_matches_, terms_to_word_starts_offsets, word_starts.url_word_starts_, | |
| 342 end_of_hostname_pos, | |
| 343 std::string::npos); | |
| 344 if (colon_pos != std::string::npos) { | |
| 345 // Also filter matches not at a word boundary and in the scheme. | |
| 346 url_matches_ = FilterTermMatchesByWordStarts( | |
| 347 url_matches_, terms_to_word_starts_offsets, | |
| 348 word_starts.url_word_starts_, 0, colon_pos); | |
| 349 } | |
| 350 for (TermMatches::const_iterator iter = url_matches_.begin(); | |
| 351 iter != url_matches_.end(); ++iter) { | |
| 352 const size_t term_offset = terms_to_word_starts_offsets[iter->term_num]; | |
| 353 // Advance next_word_starts until it's >= the position of the term we're | |
| 354 // considering (adjusted for where the word begins within the term). | |
| 355 while ((next_word_starts != end_word_starts) && | |
| 356 (*next_word_starts < (iter->offset + term_offset))) { | |
| 357 ++next_word_starts; | |
| 358 } | |
| 359 const bool at_word_boundary = (next_word_starts != end_word_starts) && | |
| 360 (*next_word_starts == iter->offset + term_offset); | |
| 361 if ((question_mark_pos != std::string::npos) && | |
| 362 (iter->offset > question_mark_pos)) { | |
| 363 // The match is in a CGI ?... fragment. | |
| 364 DCHECK(at_word_boundary); | |
| 365 term_scores[iter->term_num] += 5; | |
| 366 } else if ((end_of_hostname_pos != std::string::npos) && | |
| 367 (iter->offset > end_of_hostname_pos)) { | |
| 368 // The match is in the path. | |
| 369 DCHECK(at_word_boundary); | |
| 370 term_scores[iter->term_num] += 8; | |
| 371 } else if ((colon_pos == std::string::npos) || | |
| 372 (iter->offset > colon_pos)) { | |
| 373 // The match is in the hostname. | |
| 374 if ((last_part_of_hostname_pos == std::string::npos) || | |
| 375 (iter->offset < last_part_of_hostname_pos)) { | |
| 376 // Either there are no dots in the hostname or this match isn't | |
| 377 // the last dotted component. | |
| 378 term_scores[iter->term_num] += at_word_boundary ? 10 : 2; | |
| 379 } else { | |
| 380 // The match is in the last part of a dotted hostname (usually this | |
| 381 // is the top-level domain .com, .net, etc.). | |
| 382 if (allow_tld_matches_) | |
| 383 term_scores[iter->term_num] += at_word_boundary ? 10 : 0; | |
| 384 } | |
| 385 } else { | |
| 386 // The match is in the protocol (a.k.a. scheme). | |
| 387 // Matches not at a word boundary should have been filtered already. | |
| 388 DCHECK(at_word_boundary); | |
| 389 match_in_scheme = true; | |
| 390 if (allow_scheme_matches_) | |
| 391 term_scores[iter->term_num] += 10; | |
| 392 } | |
| 393 } | |
| 394 // Now do the analogous loop over all matches in the title. | |
| 395 next_word_starts = word_starts.title_word_starts_.begin(); | |
| 396 end_word_starts = word_starts.title_word_starts_.end(); | |
| 397 int word_num = 0; | |
| 398 title_matches_ = FilterTermMatchesByWordStarts( | |
| 399 title_matches_, terms_to_word_starts_offsets, | |
| 400 word_starts.title_word_starts_, 0, std::string::npos); | |
| 401 for (TermMatches::const_iterator iter = title_matches_.begin(); | |
| 402 iter != title_matches_.end(); ++iter) { | |
| 403 const size_t term_offset = terms_to_word_starts_offsets[iter->term_num]; | |
| 404 // Advance next_word_starts until it's >= the position of the term we're | |
| 405 // considering (adjusted for where the word begins within the term). | |
| 406 while ((next_word_starts != end_word_starts) && | |
| 407 (*next_word_starts < (iter->offset + term_offset))) { | |
| 408 ++next_word_starts; | |
| 409 ++word_num; | |
| 410 } | |
| 411 if (word_num >= 10) break; // only count the first ten words | |
| 412 DCHECK(next_word_starts != end_word_starts); | |
| 413 DCHECK_EQ(*next_word_starts, iter->offset + term_offset) | |
| 414 << "not at word boundary"; | |
| 415 term_scores[iter->term_num] += 8; | |
| 416 } | |
| 417 // TODO(mpearson): Restore logic for penalizing out-of-order matches. | |
| 418 // (Perhaps discount them by 0.8?) | |
| 419 // TODO(mpearson): Consider: if the earliest match occurs late in the string, | |
| 420 // should we discount it? | |
| 421 // TODO(mpearson): Consider: do we want to score based on how much of the | |
| 422 // input string the input covers? (I'm leaning toward no.) | |
| 423 | |
| 424 // Compute the topicality_score as the sum of transformed term_scores. | |
| 425 float topicality_score = 0; | |
| 426 for (size_t i = 0; i < term_scores.size(); ++i) { | |
| 427 // Drop this URL if it seems like a term didn't appear or, more precisely, | |
| 428 // didn't appear in a part of the URL or title that we trust enough | |
| 429 // to give it credit for. For instance, terms that appear in the middle | |
| 430 // of a CGI parameter get no credit. Almost all the matches dropped | |
| 431 // due to this test would look stupid if shown to the user. | |
| 432 if (term_scores[i] == 0) | |
| 433 return 0; | |
| 434 topicality_score += raw_term_score_to_topicality_score_[ | |
| 435 (term_scores[i] >= kMaxRawTermScore) ? (kMaxRawTermScore - 1) : | |
| 436 term_scores[i]]; | |
| 437 } | |
| 438 // TODO(mpearson): If there are multiple terms, consider taking the | |
| 439 // geometric mean of per-term scores rather than the arithmetic mean. | |
| 440 | |
| 441 return topicality_score / num_terms; | |
| 442 } | |
| 443 | |
| 444 // static | |
| 445 void ScoredHistoryMatch::FillInTermScoreToTopicalityScoreArray() { | |
| 446 for (int term_score = 0; term_score < kMaxRawTermScore; ++term_score) { | |
| 447 float topicality_score; | |
| 448 if (term_score < 10) { | |
| 449 // If the term scores less than 10 points (no full-credit hit, or | |
| 450 // no combination of hits that score that well), then the topicality | |
| 451 // score is linear in the term score. | |
| 452 topicality_score = 0.1 * term_score; | |
| 453 } else { | |
| 454 // For term scores of at least ten points, pass them through a log | |
| 455 // function so a score of 10 points gets a 1.0 (to meet up exactly | |
| 456 // with the linear component) and increases logarithmically until | |
| 457 // maxing out at 30 points, with computes to a score around 2.1. | |
| 458 topicality_score = (1.0 + 2.25 * log10(0.1 * term_score)); | |
| 459 } | |
| 460 raw_term_score_to_topicality_score_[term_score] = topicality_score; | |
| 461 } | |
| 462 } | |
| 463 | |
| 464 // static | |
| 465 float ScoredHistoryMatch::GetRecencyScore(int last_visit_days_ago) { | |
| 466 // Because the below thread is not thread safe, we check that we're | |
| 467 // only calling it from one thread: the UI thread. Specifically, | |
| 468 // we check "if we've heard of the UI thread then we'd better | |
| 469 // be on it." The first part is necessary so unit tests pass. (Many | |
| 470 // unit tests don't set up the threading naming system; hence | |
| 471 // CurrentlyOn(UI thread) will fail.) | |
| 472 DCHECK(!content::BrowserThread::IsThreadInitialized( | |
| 473 content::BrowserThread::UI) || | |
| 474 content::BrowserThread::CurrentlyOn(content::BrowserThread::UI)); | |
| 475 if (days_ago_to_recency_score_ == NULL) { | |
| 476 days_ago_to_recency_score_ = new float[kDaysToPrecomputeRecencyScoresFor]; | |
| 477 FillInDaysAgoToRecencyScoreArray(); | |
| 478 } | |
| 479 // Lookup the score in days_ago_to_recency_score, treating | |
| 480 // everything older than what we've precomputed as the oldest thing | |
| 481 // we've precomputed. The std::max is to protect against corruption | |
| 482 // in the database (in case last_visit_days_ago is negative). | |
| 483 return days_ago_to_recency_score_[ | |
| 484 std::max( | |
| 485 std::min(last_visit_days_ago, kDaysToPrecomputeRecencyScoresFor - 1), | |
| 486 0)]; | |
| 487 } | |
| 488 | |
| 489 void ScoredHistoryMatch::FillInDaysAgoToRecencyScoreArray() { | |
| 490 for (int days_ago = 0; days_ago < kDaysToPrecomputeRecencyScoresFor; | |
| 491 days_ago++) { | |
| 492 int unnormalized_recency_score; | |
| 493 if (days_ago <= 4) { | |
| 494 unnormalized_recency_score = 100; | |
| 495 } else if (days_ago <= 14) { | |
| 496 // Linearly extrapolate between 4 and 14 days so 14 days has a score | |
| 497 // of 70. | |
| 498 unnormalized_recency_score = 70 + (14 - days_ago) * (100 - 70) / (14 - 4); | |
| 499 } else if (days_ago <= 31) { | |
| 500 // Linearly extrapolate between 14 and 31 days so 31 days has a score | |
| 501 // of 50. | |
| 502 unnormalized_recency_score = 50 + (31 - days_ago) * (70 - 50) / (31 - 14); | |
| 503 } else if (days_ago <= 90) { | |
| 504 // Linearly extrapolate between 30 and 90 days so 90 days has a score | |
| 505 // of 30. | |
| 506 unnormalized_recency_score = 30 + (90 - days_ago) * (50 - 30) / (90 - 30); | |
| 507 } else { | |
| 508 // Linearly extrapolate between 90 and 365 days so 365 days has a score | |
| 509 // of 10. | |
| 510 unnormalized_recency_score = | |
| 511 10 + (365 - days_ago) * (20 - 10) / (365 - 90); | |
| 512 } | |
| 513 days_ago_to_recency_score_[days_ago] = unnormalized_recency_score / 100.0; | |
| 514 if (days_ago > 0) { | |
| 515 DCHECK_LE(days_ago_to_recency_score_[days_ago], | |
| 516 days_ago_to_recency_score_[days_ago - 1]); | |
| 517 } | |
| 518 } | |
| 519 } | |
| 520 | |
| 521 // static | |
| 522 float ScoredHistoryMatch::GetFrequency(const base::Time& now, | |
| 523 const bool bookmarked, | |
| 524 const VisitInfoVector& visits) { | |
| 525 // Compute the weighted average |value_of_transition| over the last at | |
| 526 // most kMaxVisitsToScore visits, where each visit is weighted using | |
| 527 // GetRecencyScore() based on how many days ago it happened. Use | |
| 528 // kMaxVisitsToScore as the denominator for the average regardless of | |
| 529 // how many visits there were in order to penalize a match that has | |
| 530 // fewer visits than kMaxVisitsToScore. | |
| 531 float summed_visit_points = 0; | |
| 532 for (size_t i = 0; i < std::min(visits.size(), kMaxVisitsToScore); ++i) { | |
| 533 int value_of_transition = | |
| 534 (visits[i].second == ui::PAGE_TRANSITION_TYPED) ? 20 : 1; | |
| 535 if (bookmarked) | |
| 536 value_of_transition = std::max(value_of_transition, bookmark_value_); | |
| 537 const float bucket_weight = | |
| 538 GetRecencyScore((now - visits[i].first).InDays()); | |
| 539 summed_visit_points += (value_of_transition * bucket_weight); | |
| 540 } | |
| 541 return visits.size() * summed_visit_points / kMaxVisitsToScore; | |
| 542 } | |
| 543 | |
| 544 // static | |
| 545 float ScoredHistoryMatch::GetFinalRelevancyScore(float topicality_score, | |
| 546 float frequency_score) { | |
| 547 if (topicality_score == 0) | |
| 548 return 0; | |
| 549 // Here's how to interpret intermediate_score: Suppose the omnibox | |
| 550 // has one input term. Suppose we have a URL for which the omnibox | |
| 551 // input term has a single URL hostname hit at a word boundary. (This | |
| 552 // implies topicality_score = 1.0.). Then the intermediate_score for | |
| 553 // this URL will depend entirely on the frequency_score with | |
| 554 // this interpretation: | |
| 555 // - a single typed visit more than three months ago, no other visits -> 0.2 | |
| 556 // - a visit every three days, no typed visits -> 0.706 | |
| 557 // - a visit every day, no typed visits -> 0.916 | |
| 558 // - a single typed visit yesterday, no other visits -> 2.0 | |
| 559 // - a typed visit once a week -> 11.77 | |
| 560 // - a typed visit every three days -> 14.12 | |
| 561 // - at least ten typed visits today -> 20.0 (maximum score) | |
| 562 const float intermediate_score = topicality_score * frequency_score; | |
| 563 // The below code maps intermediate_score to the range [0, 1399]. | |
| 564 // The score maxes out at 1400 (i.e., cannot beat a good inline result). | |
| 565 if (intermediate_score <= 1) { | |
| 566 // Linearly extrapolate between 0 and 1.5 so 0 has a score of 400 | |
| 567 // and 1.5 has a score of 600. | |
| 568 const float slope = (600 - 400) / (1.5f - 0.0f); | |
| 569 return 400 + slope * intermediate_score; | |
| 570 } | |
| 571 if (intermediate_score <= 12.0) { | |
| 572 // Linearly extrapolate up to 12 so 12 has a score of 1300. | |
| 573 const float slope = (1300 - 600) / (12.0f - 1.5f); | |
| 574 return 600 + slope * (intermediate_score - 1.5); | |
| 575 } | |
| 576 // Linearly extrapolate so a score of 20 (or more) has a score of 1399. | |
| 577 // (Scores above 20 are possible for URLs that have multiple term hits | |
| 578 // in the URL and/or title and that are visited practically all | |
| 579 // the time using typed visits. We don't attempt to distinguish | |
| 580 // between these very good results.) | |
| 581 const float slope = (1399 - 1300) / (20.0f - 12.0f); | |
| 582 return std::min(1399.0, 1300 + slope * (intermediate_score - 12.0)); | |
| 583 } | |
| 584 | |
| 585 void ScoredHistoryMatch::Init() { | |
| 586 if (initialized_) | |
| 587 return; | |
| 588 also_do_hup_like_scoring_ = false; | |
| 589 // When doing HUP-like scoring, don't allow a non-inlineable match | |
| 590 // to beat the score of good inlineable matches. This is a problem | |
| 591 // because if a non-inlineable match ends up with the highest score | |
| 592 // from HistoryQuick provider, all HistoryQuick matches get demoted | |
| 593 // to non-inlineable scores (scores less than 1200). Without | |
| 594 // HUP-like-scoring, these results would actually come from the HUP | |
| 595 // and not be demoted, thus outscoring the demoted HQP results. | |
| 596 // When the HQP provides these, we need to clamp the non-inlineable | |
| 597 // results to preserve this behavior. | |
| 598 if (also_do_hup_like_scoring_) { | |
| 599 max_assigned_score_for_non_inlineable_matches_ = | |
| 600 HistoryURLProvider::kScoreForBestInlineableResult - 1; | |
| 601 } | |
| 602 bookmark_value_ = OmniboxFieldTrial::HQPBookmarkValue(); | |
| 603 allow_tld_matches_ = OmniboxFieldTrial::HQPAllowMatchInTLDValue(); | |
| 604 allow_scheme_matches_ = OmniboxFieldTrial::HQPAllowMatchInSchemeValue(); | |
| 605 initialized_ = true; | |
| 606 } | |
| 607 | |
| 608 } // namespace history | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 896983003:
Componentize ScoredHistoryMatch (Closed)
Base URL: https://chromium.googlesource.com/chromium/src.git@master