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 #ifndef COMPONENTS_OMNIBOX_BROWSER_SCORED_HISTORY_MATCH_H_ 6 #define COMPONENTS_OMNIBOX_BROWSER_SCORED_HISTORY_MATCH_H_ 7 8 #include <stddef.h> 9 10 #include <string> 11 #include <utility> 12 #include <vector> 13 14 #include "base/gtest_prod_util.h" 15 #include "base/strings/string16.h" 16 #include "base/strings/utf_offset_string_conversions.h" 17 #include "base/time/time.h" 18 #include "components/history/core/browser/history_types.h" 19 #include "components/omnibox/browser/history_match.h" 20 #include "components/omnibox/browser/in_memory_url_index_types.h" 21 #include "components/omnibox/browser/omnibox_field_trial.h" 22 23 class ScoredHistoryMatchTest; 24 25 // An HistoryMatch that has a score as well as metrics defining where in the 26 // history item's URL and/or page title matches have occurred. 27 struct ScoredHistoryMatch : public history::HistoryMatch { 28 // ScoreMaxRelevance maps from an intermediate-score to the maximum 29 // final-relevance score given to a URL for this intermediate score. 30 // This is used to store the score ranges of relevance buckets. 31 // Please see GetFinalRelevancyScore() for details. 32 using ScoreMaxRelevance = std::pair<double, int>; 33 34 // A sorted vector of ScoreMaxRelevance entries, used by taking a score and 35 // interpolating between consecutive buckets. See GetFinalRelevancyScore() 36 // for details. 37 using ScoreMaxRelevances = std::vector<ScoreMaxRelevance>; 38 39 // Required for STL, we don't use this directly. 40 ScoredHistoryMatch(); 41 ScoredHistoryMatch(const ScoredHistoryMatch& other); 42 ScoredHistoryMatch(ScoredHistoryMatch&& other); 43 ScoredHistoryMatch& operator=(const ScoredHistoryMatch& other); 44 ScoredHistoryMatch& operator=(ScoredHistoryMatch&& other); 45 46 // Initializes the ScoredHistoryMatch with a raw score calculated for the 47 // history item given in |row| with recent visits as indicated in |visits|. It 48 // first determines if the row qualifies by seeing if all of the terms in 49 // |terms_vector| occur in |row|. If so, calculates a raw score. This raw 50 // score is in part determined by whether the matches occur at word 51 // boundaries, the locations of which are stored in |word_starts|. For some 52 // terms, it's appropriate to look for the word boundary within the term. For 53 // instance, the term ".net" should look for a word boundary at the "n". 54 // These offsets (".net" should have an offset of 1) come from 55 // |terms_to_word_starts_offsets|. |is_url_bookmarked| indicates whether the 56 // match's URL is referenced by any bookmarks, which can also affect the raw 57 // score. |num_matching_pages| indicates how many URLs in the eligible URL 58 // database match the user's input; it can also affect the raw score. The raw 59 // score allows the matches to be ordered and can be used to influence the 60 // final score calculated by the client of this index. If the row does not 61 // qualify the raw score will be 0. 62 ScoredHistoryMatch(const history::URLRow& row, 63 const VisitInfoVector& visits, 64 const base::string16& lower_string, 65 const String16Vector& terms_vector, 66 const WordStarts& terms_to_word_starts_offsets, 67 const RowWordStarts& word_starts, 68 bool is_url_bookmarked, 69 size_t num_matching_pages, 70 base::Time now); 71 72 ~ScoredHistoryMatch(); 73 74 // Compares two matches by score. Functor supporting URLIndexPrivateData's 75 // HistoryItemsForTerms function. Looks at particular fields within 76 // with url_info to make tie-breaking a bit smarter. 77 static bool MatchScoreGreater(const ScoredHistoryMatch& m1, 78 const ScoredHistoryMatch& m2); 79 80 // Returns |term_matches| after removing all matches that are not at a 81 // word break that are in the range [|start_pos|, |end_pos|). 82 // start_pos == string::npos is treated as start_pos = length of string. 83 // (In other words, no matches will be filtered.) 84 // end_pos == string::npos is treated as end_pos = length of string. If 85 // |allow_midword_continuations| is true, matches not at a word break are not 86 // filtered if they continue where the previous match ended. 87 static TermMatches FilterTermMatchesByWordStarts( 88 const TermMatches& term_matches, 89 const WordStarts& terms_to_word_starts_offsets, 90 const WordStarts& word_starts, 91 size_t start_pos, 92 size_t end_pos, 93 bool allow_midword_continuations = false); 94 95 // An interim score taking into consideration location and completeness 96 // of the match. 97 int raw_score; 98 99 // Both these TermMatches contain the set of matches that are considered 100 // important. At this time, that means they exclude mid-word matches 101 // except in the hostname of the URL. (Technically, during early 102 // construction of ScoredHistoryMatch, they may contain all matches, but 103 // unimportant matches are eliminated by GetTopicalityScore(), called 104 // during construction.) 105 106 // Term matches within the URL. 107 TermMatches url_matches; 108 // Term matches within the page title. 109 TermMatches title_matches; 110 111 private: 112 friend class ScoredHistoryMatchTest; 113 FRIEND_TEST_ALL_PREFIXES(ScoredHistoryMatchTest, GetDocumentSpecificityScore); 114 FRIEND_TEST_ALL_PREFIXES(ScoredHistoryMatchTest, GetFinalRelevancyScore); 115 FRIEND_TEST_ALL_PREFIXES(ScoredHistoryMatchTest, GetFrequency); 116 FRIEND_TEST_ALL_PREFIXES(ScoredHistoryMatchTest, GetHQPBucketsFromString); 117 FRIEND_TEST_ALL_PREFIXES(ScoredHistoryMatchTest, ScoringBookmarks); 118 FRIEND_TEST_ALL_PREFIXES(ScoredHistoryMatchTest, ScoringScheme); 119 FRIEND_TEST_ALL_PREFIXES(ScoredHistoryMatchTest, ScoringTLD); 120 121 // Initialize ScoredHistoryMatch statics. Must be called before any other 122 // method of ScoredHistoryMatch and before creating any instances. 123 static void Init(); 124 125 // Return a topicality score based on how many matches appear in the url and 126 // the page's title and where they are (e.g., at word boundaries). Revises 127 // url_matches and title_matches in the process so they only reflect matches 128 // used for scoring. (For instance, some mid-word matches are not given 129 // credit in scoring.) Requires that |url_matches| and |title_matches| are 130 // sorted. |adjustments| must contain any adjustments used to format |url|. 131 float GetTopicalityScore(const int num_terms, 132 const GURL& url, 133 const base::OffsetAdjuster::Adjustments& adjustments, 134 const WordStarts& terms_to_word_starts_offsets, 135 const RowWordStarts& word_starts); 136 137 // Returns a recency score based on |last_visit_days_ago|, which is 138 // how many days ago the page was last visited. 139 float GetRecencyScore(int last_visit_days_ago) const; 140 141 // Examines the first |max_visits_to_score_| and returns a score (higher is 142 // better) based the rate of visits, whether the page is bookmarked, and 143 // how often those visits are typed navigations (i.e., explicitly 144 // invoked by the user). |now| is passed in to avoid unnecessarily 145 // recomputing it frequently. 146 float GetFrequency(const base::Time& now, 147 const bool bookmarked, 148 const VisitInfoVector& visits) const; 149 150 // Returns a document specificity score based on how many pages matched the 151 // user's input. 152 float GetDocumentSpecificityScore(size_t num_matching_pages) const; 153 154 // Combines the three component scores into a final score that's 155 // an appropriate value to use as a relevancy score. 156 static float GetFinalRelevancyScore(float topicality_score, 157 float frequency_score, 158 float specificity_score); 159 160 // Helper function that returns the string containing the scoring buckets 161 // (either the default ones or ones specified in an experiment). 162 static ScoreMaxRelevances GetHQPBuckets(); 163 164 // Helper function to parse the string containing the scoring buckets and 165 // return the results. For example, with |buckets_str| as 166 // "0.0:400,1.5:600,12.0:1300,20.0:1399", it returns [(0.0, 400), (1.5, 600), 167 // (12.0, 1300), (20.0, 1399)]. It returns an empty vector in the case of a 168 // malformed |buckets_str|. 169 static ScoreMaxRelevances GetHQPBucketsFromString( 170 const std::string& buckets_str); 171 172 // If true, assign raw scores to be max(whatever it normally would be, a 173 // score that's similar to the score HistoryURL provider would assign). 174 static bool also_do_hup_like_scoring_; 175 176 // Untyped visits to bookmarked pages score this, compared to 1 for 177 // untyped visits to non-bookmarked pages and |typed_value_| for typed visits. 178 static float bookmark_value_; 179 180 // Typed visits to page score this, compared to 1 for untyped visits. 181 static float typed_value_; 182 183 // The maximum number of recent visits to examine in GetFrequency(). 184 static size_t max_visits_to_score_; 185 186 // If true, we allow input terms to match in the TLD (e.g., ".com"). 187 static bool allow_tld_matches_; 188 189 // If true, we allow input terms to match in the scheme (e.g., "http://"). 190 static bool allow_scheme_matches_; 191 192 // The number of title words examined when computing topicality scores. 193 // Words beyond this number are ignored. 194 static size_t num_title_words_to_allow_; 195 196 // |topicality_threshold_| is used to control the topicality scoring. 197 // If |topicality_threshold_| > 0, then URLs with topicality-score less than 198 // the threshold are given topicality score of 0. 199 static float topicality_threshold_; 200 201 // Used for testing. A possibly null pointer to a vector. If set, 202 // overrides the static local variable |relevance_buckets| declared in 203 // GetFinalRelevancyScore(). 204 static ScoreMaxRelevances* relevance_buckets_override_; 205 206 // Used for testing. If this pointer is not null, it overrides the static 207 // local variable |default_matches_to_specificity| declared in 208 // GetDocumentSpecificityScore(). 209 static OmniboxFieldTrial::NumMatchesScores* matches_to_specificity_override_; 210 }; 211 typedef std::vector<ScoredHistoryMatch> ScoredHistoryMatches; 212 213 #endif // COMPONENTS_OMNIBOX_BROWSER_SCORED_HISTORY_MATCH_H_ 214