Extracting page shingle hashes for similarity detection.

chrome/renderer/safe_browsing/phishing_term_feature_extractor.cc

Index: chrome/renderer/safe_browsing/phishing_term_feature_extractor.cc
diff --git a/chrome/renderer/safe_browsing/phishing_term_feature_extractor.cc b/chrome/renderer/safe_browsing/phishing_term_feature_extractor.cc
index 89994dfd04cf4488d4f4a87689cff92bc8760bb8..1e93ea0b94a046820d95f5956f614d802ea1f502 100644
--- a/chrome/renderer/safe_browsing/phishing_term_feature_extractor.cc
+++ b/chrome/renderer/safe_browsing/phishing_term_feature_extractor.cc
@@ -45,6 +45,14 @@ struct PhishingTermFeatureExtractor::ExtractionState {
   // Stores up to max_words_per_term_ previous words separated by spaces.
   std::string previous_words;
 
+  // Stores the current shingle after a new word is processed and added in.
+  std::string current_shingle;
+
+  // Stores the sizes of the words in current_shingle. Note: the size includes
+  // the space after each word. In other words, the sum of all sizes in this
+  // list is equal to the length of current_shingle.
+  std::list<size_t> shingle_word_sizes;
+
   // Stores the sizes of the words in previous_words.  Note: the size includes
   // the space after each word.  In other words, the sum of all sizes in this
   // list is equal to the length of previous_words.
@@ -95,11 +103,15 @@ PhishingTermFeatureExtractor::PhishingTermFeatureExtractor(
     const base::hash_set<uint32>* page_word_hashes,
     size_t max_words_per_term,
     uint32 murmurhash3_seed,
+    size_t max_shingles_per_page,
+    size_t shingle_size,
     FeatureExtractorClock* clock)
     : page_term_hashes_(page_term_hashes),
       page_word_hashes_(page_word_hashes),
       max_words_per_term_(max_words_per_term),
       murmurhash3_seed_(murmurhash3_seed),
+      max_shingles_per_page_(max_shingles_per_page),
+      shingle_size_(shingle_size),
       negative_word_cache_(kMaxNegativeWordCacheSize),
       clock_(clock),
       weak_factory_(this) {
@@ -115,6 +127,7 @@ PhishingTermFeatureExtractor::~PhishingTermFeatureExtractor() {
 void PhishingTermFeatureExtractor::ExtractFeatures(
     const base::string16* page_text,
     FeatureMap* features,
+    std::set<uint32>* shingle_hashes,
     const DoneCallback& done_callback) {
   // The RenderView should have called CancelPendingExtraction() before
   // starting a new extraction, so DCHECK this.
@@ -125,6 +138,7 @@ void PhishingTermFeatureExtractor::ExtractFeatures(
 
   page_text_ = page_text;
   features_ = features;
+  shingle_hashes_ = shingle_hashes,
   done_callback_ = done_callback;
 
   state_.reset(new ExtractionState(*page_text_, clock_->Now()));
@@ -210,6 +224,23 @@ void PhishingTermFeatureExtractor::ExtractFeaturesWithTimeout() {
 
 void PhishingTermFeatureExtractor::HandleWord(
     const base::StringPiece16& word) {
+  // First, extract shingle hashes. We check the size of shingle_hashes_ first
+  // to skip as soon as we reach |max_shingles_per_page_|.
+  std::string word_lower;
+  if (shingle_hashes_->size() < max_shingles_per_page_) {

[noelutz, 2014/05/06 21:40:18]

I think we want to keep the min 200 shingles so that code isn't quite right. 
You should always add the new shingle and then remove the largest one if we have
more than max_shingles_per_page_ shingles in the set.

[zysxqn, 2014/05/07 19:29:19]

I know on the server side experiment we use min 200 hashes. But for the sake of
computing similarity I don't see any problem with keeping first 200 hashes, as
long as the extracting logic is the same among all pages. Am I miss anything?

[zysxqn, 2014/05/09 21:34:24]

Done.

[mattm, 2014/05/09 23:28:10]

Have you tested if doing it for the whole text has any notable performance
impact? (Not just the hashing, but the extra lowercasing and utf conversions
which are called expensive below.)

[noelutz, 2014/05/10 01:01:20]

+1 on performance testing.  Could you add a histogram measuring how much time we
spend doing that?

+    word_lower = base::UTF16ToUTF8(base::i18n::ToLower(word));
+    state_->current_shingle.append(word_lower + " ");
+    state_->shingle_word_sizes.push_back(word_lower.size() + 1);
+    if (state_->shingle_word_sizes.size() == shingle_size_) {
+      shingle_hashes_->insert(
+          MurmurHash3String(state_->current_shingle, murmurhash3_seed_));
+      state_->current_shingle.erase(0, state_->shingle_word_sizes.front());
+      state_->shingle_word_sizes.pop_front();
+    }
+  }
+
+  // Next, extract page terms.
+  //
   // Quickest out if we have seen this word before and know that it's not
   // part of any term. This avoids the lowercasing and UTF conversion, both of
   // which are relatively expensive.
@@ -221,7 +252,9 @@ void PhishingTermFeatureExtractor::HandleWord(
     return;
   }
 
-  std::string word_lower = base::UTF16ToUTF8(base::i18n::ToLower(word));
+  if (word_lower.empty()) {
+    word_lower = base::UTF16ToUTF8(base::i18n::ToLower(word));
+  }
   uint32 word_hash = MurmurHash3String(word_lower, murmurhash3_seed_);
 
   // Quick out if the word is not part of any term, which is the common case.
@@ -302,6 +335,7 @@ void PhishingTermFeatureExtractor::RunCallback(bool success) {
 void PhishingTermFeatureExtractor::Clear() {
   page_text_ = NULL;
   features_ = NULL;
+  shingle_hashes_ = NULL;
   done_callback_.Reset();
   state_.reset(NULL);
   negative_word_cache_.Clear();