1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232
|
// Copyright (c) 2012 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 "components/omnibox/browser/bookmark_provider.h"
#include <algorithm>
#include <functional>
#include <vector>
#include "base/macros.h"
#include "base/strings/string_util.h"
#include "base/strings/utf_string_conversions.h"
#include "base/trace_event/trace_event.h"
#include "components/bookmarks/browser/bookmark_model.h"
#include "components/bookmarks/browser/titled_url_match.h"
#include "components/metrics/proto/omnibox_input_type.pb.h"
#include "components/omnibox/browser/autocomplete_provider_client.h"
#include "components/omnibox/browser/autocomplete_result.h"
#include "components/omnibox/browser/titled_url_match_utils.h"
#include "components/prefs/pref_service.h"
#include "url/url_constants.h"
using bookmarks::BookmarkNode;
using bookmarks::TitledUrlMatch;
using TitledUrlMatches = std::vector<TitledUrlMatch>;
// BookmarkProvider ------------------------------------------------------------
BookmarkProvider::BookmarkProvider(AutocompleteProviderClient* client)
: AutocompleteProvider(AutocompleteProvider::TYPE_BOOKMARK),
client_(client),
bookmark_model_(client ? client_->GetBookmarkModel() : nullptr) {}
void BookmarkProvider::Start(const AutocompleteInput& input,
bool minimal_changes) {
TRACE_EVENT0("omnibox", "BookmarkProvider::Start");
if (minimal_changes)
return;
matches_.clear();
if (input.from_omnibox_focus() || input.text().empty())
return;
DoAutocomplete(input);
}
BookmarkProvider::~BookmarkProvider() {}
void BookmarkProvider::DoAutocomplete(const AutocompleteInput& input) {
// We may not have a bookmark model for some unit tests.
if (!bookmark_model_)
return;
TitledUrlMatches matches;
// Retrieve enough bookmarks so that we have a reasonable probability of
// suggesting the one that the user desires.
const size_t kMaxBookmarkMatches = 50;
// GetBookmarksMatching returns bookmarks matching the user's
// search terms using the following rules:
// - The search text is broken up into search terms. Each term is searched
// for separately.
// - Term matches are always performed against the start of a word. 'def'
// will match against 'define' but not against 'indefinite'.
// - Terms must be at least three characters in length in order to perform
// partial word matches. Any term of lesser length will only be used as an
// exact match. 'def' will match against 'define' but 'de' will not match.
// - A search containing multiple terms will return results with those words
// occuring in any order.
// - Terms enclosed in quotes comprises a phrase that must match exactly.
// - Multiple terms enclosed in quotes will require those exact words in that
// exact order to match.
//
// Please refer to the code for TitledUrlIndex::GetResultsMatching for
// complete details of how searches are performed against the user's
// bookmarks.
bookmark_model_->GetBookmarksMatching(input.text(),
kMaxBookmarkMatches,
&matches);
if (matches.empty())
return; // There were no matches.
const base::string16 fixed_up_input(FixupUserInput(input).second);
for (const auto& bookmark_match : matches) {
// Score the TitledUrlMatch. If its score is greater than 0 then the
// AutocompleteMatch is created and added to matches_.
int relevance = CalculateBookmarkMatchRelevance(bookmark_match);
if (relevance > 0) {
matches_.push_back(TitledUrlMatchToAutocompleteMatch(
bookmark_match, AutocompleteMatchType::BOOKMARK_TITLE, relevance,
this, client_->GetSchemeClassifier(), input, fixed_up_input));
}
}
// Sort and clip the resulting matches.
size_t num_matches =
std::min(matches_.size(), AutocompleteProvider::kMaxMatches);
std::partial_sort(matches_.begin(), matches_.begin() + num_matches,
matches_.end(), AutocompleteMatch::MoreRelevant);
matches_.resize(num_matches);
}
namespace {
// for_each helper functor that calculates a match factor for each query term
// when calculating the final score.
//
// Calculate a 'factor' from 0 to the bookmark's title length for a match
// based on 1) how many characters match and 2) where the match is positioned.
class ScoringFunctor {
public:
// |title_length| is the length of the bookmark title against which this
// match will be scored.
explicit ScoringFunctor(size_t title_length)
: title_length_(static_cast<double>(title_length)),
scoring_factor_(0.0) {
}
void operator()(const query_parser::Snippet::MatchPosition& match) {
double term_length = static_cast<double>(match.second - match.first);
scoring_factor_ += term_length *
(title_length_ - match.first) / title_length_;
}
double ScoringFactor() { return scoring_factor_; }
private:
double title_length_;
double scoring_factor_;
};
} // namespace
int BookmarkProvider::CalculateBookmarkMatchRelevance(
const TitledUrlMatch& bookmark_match) const {
// Summary on how a relevance score is determined for the match:
//
// For each match within the bookmark's title or URL (or both), calculate a
// 'factor', sum up those factors, then use the sum to figure out a value
// between the base score and the maximum score.
//
// The factor for each match is the product of:
//
// 1) how many characters in the bookmark's title/URL are part of this match.
// This is capped at the length of the bookmark's title
// to prevent terms that match in both the title and the URL from
// scoring too strongly.
//
// 2) where the match occurs within the bookmark's title or URL,
// giving more points for matches that appear earlier in the string:
// ((string_length - position of match start) / string_length).
//
// Example: Given a bookmark title of 'abcde fghijklm', with a title length
// of 14, and two different search terms, 'abcde' and 'fghij', with
// start positions of 0 and 6, respectively, 'abcde' will score higher
// (with a a partial factor of (14-0)/14 = 1.000 ) than 'fghij' (with
// a partial factor of (14-6)/14 = 0.571 ). (In this example neither
// term matches in the URL.)
//
// Once all match factors have been calculated they are summed. If there
// are no URL matches, the resulting sum will never be greater than the
// length of the bookmark title because of the way the bookmark model matches
// and removes overlaps. (In particular, the bookmark model only
// matches terms to the beginning of words and it removes all overlapping
// matches, keeping only the longest. Together these mean that each
// character is included in at most one match.) If there are matches in the
// URL, the sum can be greater.
//
// This sum is then normalized by the length of the bookmark title + 10
// and capped at 1.0. The +10 is to expand the scoring range so fewer
// bookmarks will hit the 1.0 cap and hence lose all ability to distinguish
// between these high-quality bookmarks.
//
// The normalized value is multiplied against the scoring range available,
// which is the difference between the minimum possible score and the maximum
// possible score. This product is added to the minimum possible score to
// give the preliminary score.
//
// If the preliminary score is less than the maximum possible score, 1199,
// it can be boosted up to that maximum possible score if the URL referenced
// by the bookmark is also referenced by any of the user's other bookmarks.
// A count of how many times the bookmark's URL is referenced is determined
// and, for each additional reference beyond the one for the bookmark being
// scored up to a maximum of three, the score is boosted by a fixed amount
// given by |kURLCountBoost|, below.
base::string16 title(bookmark_match.node->GetTitledUrlNodeTitle());
const GURL& url(bookmark_match.node->GetTitledUrlNodeUrl());
// Pretend empty titles are identical to the URL.
if (title.empty())
title = base::ASCIIToUTF16(url.spec());
ScoringFunctor title_position_functor =
for_each(bookmark_match.title_match_positions.begin(),
bookmark_match.title_match_positions.end(),
ScoringFunctor(title.size()));
ScoringFunctor url_position_functor =
for_each(bookmark_match.url_match_positions.begin(),
bookmark_match.url_match_positions.end(),
ScoringFunctor(
bookmark_match.node->GetTitledUrlNodeUrl().spec().length()));
const double title_match_strength = title_position_functor.ScoringFactor();
const double summed_factors = title_match_strength +
url_position_functor.ScoringFactor();
const double normalized_sum =
std::min(summed_factors / (title.size() + 10), 1.0);
// Bookmarks with javascript scheme ("bookmarklets") that do not have title
// matches get a lower base and lower maximum score because returning them
// for matches in their (often very long) URL looks stupid and is often not
// intended by the user.
const bool bookmarklet_without_title_match =
url.SchemeIs(url::kJavaScriptScheme) && (title_match_strength == 0.0);
const int kBaseBookmarkScore = bookmarklet_without_title_match ? 400 : 900;
const int kMaxBookmarkScore = bookmarklet_without_title_match ? 799 : 1199;
const double kBookmarkScoreRange =
static_cast<double>(kMaxBookmarkScore - kBaseBookmarkScore);
int relevance = static_cast<int>(normalized_sum * kBookmarkScoreRange) +
kBaseBookmarkScore;
// Don't waste any time searching for additional referenced URLs if we
// already have a perfect title match.
if (relevance >= kMaxBookmarkScore)
return relevance;
// Boost the score if the bookmark's URL is referenced by other bookmarks.
const int kURLCountBoost[4] = { 0, 75, 125, 150 };
std::vector<const BookmarkNode*> nodes;
bookmark_model_->GetNodesByURL(url, &nodes);
DCHECK_GE(std::min(arraysize(kURLCountBoost), nodes.size()), 1U);
relevance +=
kURLCountBoost[std::min(arraysize(kURLCountBoost), nodes.size()) - 1];
relevance = std::min(kMaxBookmarkScore, relevance);
return relevance;
}
|