keyword_cluster_finalizer.cc 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255
  1. // Copyright 2022 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. #include "components/history_clusters/core/keyword_cluster_finalizer.h"
  5. #include <queue>
  6. #include "base/containers/contains.h"
  7. #include "base/containers/flat_set.h"
  8. #include "base/strings/string_split.h"
  9. #include "base/strings/string_util.h"
  10. #include "base/strings/utf_string_conversions.h"
  11. #include "components/history/core/browser/history_types.h"
  12. #include "components/history_clusters/core/config.h"
  13. #include "components/history_clusters/core/on_device_clustering_features.h"
  14. #include "components/history_clusters/core/on_device_clustering_util.h"
  15. #include "components/optimization_guide/core/entity_metadata.h"
  16. namespace history_clusters {
  17. namespace {
  18. static constexpr float kSearchTermsScore = 100.0;
  19. static constexpr float kScoreEpsilon = 1e-8;
  20. bool IsKeywordSimilarToVisitHost(
  21. const std::vector<std::u16string>& lowercase_host_parts,
  22. const std::u16string& keyword) {
  23. std::u16string lowercase_keyword = base::ToLowerASCII(keyword);
  24. if (base::Contains(lowercase_host_parts, keyword))
  25. return true;
  26. // Now check if the whitespace-stripped keyword is part of the host.
  27. std::u16string stripped_lowercase_keyword;
  28. base::RemoveChars(lowercase_keyword, base::kWhitespaceASCIIAs16,
  29. &stripped_lowercase_keyword);
  30. return base::Contains(lowercase_host_parts, stripped_lowercase_keyword);
  31. }
  32. // Computes an keyword score per cluster visit by mulitplying its visit-wise
  33. // weight and cluster visit score, and applying a weight factor.
  34. float ComputeKeywordScorePerClusterVisit(int visit_keyword_weight,
  35. float cluster_visit_score,
  36. float weight = 1.0) {
  37. return static_cast<float>(visit_keyword_weight) * cluster_visit_score *
  38. weight;
  39. }
  40. void KeepTopKeywords(
  41. base::flat_map<std::u16string, history::ClusterKeywordData>&
  42. keyword_to_data_map,
  43. size_t max_num_keywords_per_cluster) {
  44. if (keyword_to_data_map.size() <= max_num_keywords_per_cluster) {
  45. return;
  46. }
  47. // Compare keywords first by their scores and then by types.
  48. auto cmp_keywords =
  49. [](const std::pair<std::u16string, const history::ClusterKeywordData*>&
  50. left,
  51. const std::pair<std::u16string, const history::ClusterKeywordData*>&
  52. right) {
  53. return std::fabs(left.second->score - right.second->score) >
  54. kScoreEpsilon
  55. ? left.second->score > right.second->score
  56. : left.second->type > right.second->type;
  57. };
  58. // Minimum priority queue of top keywords.
  59. std::priority_queue<
  60. std::pair<std::u16string, const history::ClusterKeywordData*>,
  61. std::vector<
  62. std::pair<std::u16string, const history::ClusterKeywordData*>>,
  63. decltype(cmp_keywords)>
  64. pq(cmp_keywords);
  65. for (const auto& keyword_data_p : keyword_to_data_map) {
  66. bool should_insert = false;
  67. if (pq.size() < max_num_keywords_per_cluster) {
  68. should_insert = true;
  69. } else {
  70. if (pq.top().second->score < keyword_data_p.second.score) {
  71. pq.pop();
  72. should_insert = true;
  73. }
  74. }
  75. if (should_insert) {
  76. pq.push(std::make_pair(keyword_data_p.first, &keyword_data_p.second));
  77. }
  78. }
  79. base::flat_set<std::u16string> keywords_set;
  80. while (!pq.empty()) {
  81. keywords_set.insert(pq.top().first);
  82. pq.pop();
  83. }
  84. auto it = keyword_to_data_map.begin();
  85. for (; it != keyword_to_data_map.end();) {
  86. if (!keywords_set.contains(it->first)) {
  87. it = keyword_to_data_map.erase(it);
  88. } else {
  89. it++;
  90. }
  91. }
  92. DCHECK_EQ(keyword_to_data_map.size(), max_num_keywords_per_cluster);
  93. }
  94. } // namespace
  95. KeywordClusterFinalizer::KeywordClusterFinalizer(
  96. const base::flat_map<std::string, optimization_guide::EntityMetadata>&
  97. entity_metadata_map)
  98. : entity_metadata_map_(entity_metadata_map) {}
  99. KeywordClusterFinalizer::~KeywordClusterFinalizer() = default;
  100. void KeywordClusterFinalizer::FinalizeCluster(history::Cluster& cluster) {
  101. base::flat_map<std::u16string, history::ClusterKeywordData>
  102. keyword_to_data_map;
  103. for (const auto& visit : cluster.visits) {
  104. if (!GetConfig().keyword_filter_on_noisy_visits && IsNoisyVisit(visit)) {
  105. // Do not put keywords if user visits the page a lot and it's not a
  106. // search-like visit.
  107. continue;
  108. }
  109. std::vector<std::u16string> lowercase_host_parts = base::SplitString(
  110. base::ToLowerASCII(
  111. base::UTF8ToUTF16(visit.annotated_visit.url_row.url().host())),
  112. u".", base::KEEP_WHITESPACE, base::SPLIT_WANT_NONEMPTY);
  113. for (const auto& entity :
  114. visit.annotated_visit.content_annotations.model_annotations.entities) {
  115. base::flat_set<std::u16string> entity_keywords;
  116. const std::u16string keyword_u16str = base::UTF8ToUTF16(entity.id);
  117. entity_keywords.insert(keyword_u16str);
  118. // Add an entity to keyword data.
  119. const float entity_score =
  120. ComputeKeywordScorePerClusterVisit(entity.weight, visit.score);
  121. auto keyword_it = keyword_to_data_map.find(keyword_u16str);
  122. if (keyword_it != keyword_to_data_map.end()) {
  123. // Accumulate entity scores from multiple visits.
  124. keyword_it->second.score += entity_score;
  125. keyword_it->second.MaybeUpdateKeywordType(
  126. history::ClusterKeywordData::kEntity);
  127. } else {
  128. keyword_to_data_map[keyword_u16str] = history::ClusterKeywordData(
  129. history::ClusterKeywordData::kEntity, entity_score,
  130. /*entity_collections=*/{});
  131. }
  132. // Add the top one entity collection to keyword data.
  133. const auto it = entity_metadata_map_.find(entity.id);
  134. if (it != entity_metadata_map_.end() && !it->second.collections.empty()) {
  135. keyword_to_data_map[keyword_u16str].entity_collections = {
  136. it->second.collections[0]};
  137. }
  138. if (GetConfig().keyword_filter_on_entity_aliases) {
  139. if (it != entity_metadata_map_.end()) {
  140. for (size_t i = 0; i < it->second.human_readable_aliases.size() &&
  141. i < GetConfig().max_entity_aliases_in_keywords;
  142. i++) {
  143. const auto alias =
  144. base::UTF8ToUTF16(it->second.human_readable_aliases[i]);
  145. entity_keywords.insert(alias);
  146. // Use the same score and collections of an entity for its aliases
  147. // as well.
  148. auto alias_it = keyword_to_data_map.find(alias);
  149. if (alias_it == keyword_to_data_map.end()) {
  150. keyword_to_data_map[alias] = history::ClusterKeywordData(
  151. history::ClusterKeywordData::kEntityAlias, entity_score, {});
  152. } else {
  153. alias_it->second.score += entity_score;
  154. alias_it->second.MaybeUpdateKeywordType(
  155. history::ClusterKeywordData::kEntityAlias);
  156. }
  157. keyword_to_data_map[alias].entity_collections =
  158. keyword_to_data_map[keyword_u16str].entity_collections;
  159. }
  160. }
  161. }
  162. if (!GetConfig().keyword_filter_on_visit_hosts) {
  163. // If we do not want any keywords associated with the visit host, make
  164. // sure that none of the keywords associated with the entity look like
  165. // they are for the visit host.
  166. bool clear_entity_keywords = false;
  167. for (const auto& entity_keyword : entity_keywords) {
  168. if (IsKeywordSimilarToVisitHost(lowercase_host_parts,
  169. entity_keyword)) {
  170. // One of the keywords is likely for the visit host, so clear out
  171. // the keywords for the whole entity.
  172. clear_entity_keywords = true;
  173. break;
  174. }
  175. }
  176. if (clear_entity_keywords) {
  177. for (const auto& keyword : entity_keywords) {
  178. keyword_to_data_map.erase(keyword);
  179. }
  180. }
  181. }
  182. }
  183. if (GetConfig().keyword_filter_on_categories) {
  184. for (const auto& category : visit.annotated_visit.content_annotations
  185. .model_annotations.categories) {
  186. std::u16string category_u16string = base::UTF8ToUTF16(category.id);
  187. if (!GetConfig().keyword_filter_on_visit_hosts &&
  188. IsKeywordSimilarToVisitHost(lowercase_host_parts,
  189. category_u16string)) {
  190. continue;
  191. }
  192. // Add a discounted keyword score for categories.
  193. const float category_score = ComputeKeywordScorePerClusterVisit(
  194. category.weight, visit.score,
  195. GetConfig().category_keyword_score_weight);
  196. auto category_it = keyword_to_data_map.find(category_u16string);
  197. if (category_it == keyword_to_data_map.end()) {
  198. keyword_to_data_map[category_u16string] = history::ClusterKeywordData(
  199. history::ClusterKeywordData::kEntityCategory, category_score,
  200. /*entity_collections=*/{});
  201. } else {
  202. // Accumulate category scores if there are multiple.
  203. category_it->second.score += category_score;
  204. category_it->second.MaybeUpdateKeywordType(
  205. history::ClusterKeywordData::kEntityCategory);
  206. }
  207. }
  208. }
  209. if (GetConfig().keyword_filter_on_search_terms &&
  210. !visit.annotated_visit.content_annotations.search_terms.empty()) {
  211. const auto& search_terms =
  212. visit.annotated_visit.content_annotations.search_terms;
  213. auto search_it = keyword_to_data_map.find(search_terms);
  214. if (search_it == keyword_to_data_map.end()) {
  215. keyword_to_data_map[search_terms] = history::ClusterKeywordData(
  216. history::ClusterKeywordData::kSearchTerms,
  217. /*score=*/kSearchTermsScore, /*entity_collections=*/{});
  218. } else {
  219. search_it->second.score += kSearchTermsScore;
  220. search_it->second.MaybeUpdateKeywordType(
  221. history::ClusterKeywordData::kSearchTerms);
  222. }
  223. }
  224. }
  225. KeepTopKeywords(keyword_to_data_map,
  226. GetConfig().max_num_keywords_per_cluster);
  227. cluster.keyword_to_data_map = std::move(keyword_to_data_map);
  228. }
  229. } // namespace history_clusters