ngram_extractor_unittest.cc 4.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155
  1. // Copyright 2016 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/url_pattern_index/ngram_extractor.h"
  5. #include <stdint.h>
  6. #include <string>
  7. #include <vector>
  8. #include "testing/gtest/include/gtest/gtest.h"
  9. namespace url_pattern_index {
  10. namespace {
  11. bool IsSeparatorTrue(char) {
  12. return true;
  13. }
  14. bool IsSeparatorFalse(char) {
  15. return false;
  16. }
  17. bool IsSpecialChar(char c) {
  18. return c == '*' || c == '^';
  19. }
  20. template <typename IntType>
  21. IntType EncodeStringToInteger(const std::string& data) {
  22. EXPECT_LE(data.size(), sizeof(IntType));
  23. IntType encoded_string = 0;
  24. for (size_t i = 0; i < data.size(); ++i) {
  25. encoded_string = (encoded_string << 8) | static_cast<IntType>(data[i]);
  26. }
  27. return encoded_string;
  28. }
  29. template <typename IntType>
  30. std::vector<IntType> EncodeStringsToIntegers(
  31. const std::vector<std::string>& ngrams) {
  32. std::vector<IntType> int_grams;
  33. for (const std::string& ngram : ngrams) {
  34. int_grams.push_back(EncodeStringToInteger<IntType>(ngram));
  35. }
  36. return int_grams;
  37. }
  38. } // namespace
  39. TEST(NGramExtractorTest, EmptyString) {
  40. const char* kString = "";
  41. auto extractor =
  42. CreateNGramExtractor<3, uint32_t, NGramCaseExtraction::kLowerCase>(
  43. kString, IsSpecialChar);
  44. EXPECT_EQ(extractor.begin(), extractor.end());
  45. }
  46. TEST(NGramExtractorTest, ShortString) {
  47. const char* kString = "abacab";
  48. auto extractor =
  49. CreateNGramExtractor<7, uint64_t, NGramCaseExtraction::kLowerCase>(
  50. kString, IsSeparatorFalse);
  51. EXPECT_EQ(extractor.begin(), extractor.end());
  52. }
  53. TEST(NGramExtractorTest, ShortPieces) {
  54. const char* kString = "1**abac*abc*abcd*00";
  55. auto extractor =
  56. CreateNGramExtractor<6, uint64_t, NGramCaseExtraction::kLowerCase>(
  57. kString, IsSpecialChar);
  58. EXPECT_EQ(extractor.begin(), extractor.end());
  59. }
  60. TEST(NGramExtractorTest, IsSeparatorAlwaysTrue) {
  61. const char* kString = "abacaba";
  62. auto extractor =
  63. CreateNGramExtractor<3, uint32_t, NGramCaseExtraction::kLowerCase>(
  64. kString, IsSeparatorTrue);
  65. EXPECT_EQ(extractor.begin(), extractor.end());
  66. }
  67. TEST(NGramExtractorTest, IsSeparatorAlwaysFalse) {
  68. const std::string kString = "abacaba123";
  69. constexpr size_t N = 3;
  70. std::vector<uint32_t> expected_ngrams = EncodeStringsToIntegers<uint32_t>(
  71. {"aba", "bac", "aca", "cab", "aba", "ba1", "a12", "123"});
  72. auto extractor =
  73. CreateNGramExtractor<N, uint32_t, NGramCaseExtraction::kLowerCase>(
  74. kString, IsSeparatorFalse);
  75. std::vector<uint32_t> actual_ngrams(extractor.begin(), extractor.end());
  76. EXPECT_EQ(expected_ngrams, actual_ngrams);
  77. }
  78. TEST(NGramExtractorTest, LowerCaseExtraction) {
  79. const std::string kString = "aBcDEFG";
  80. constexpr size_t N = 3;
  81. std::vector<uint32_t> expected_ngrams =
  82. EncodeStringsToIntegers<uint32_t>({"abc", "bcd", "cde", "def", "efg"});
  83. auto extractor =
  84. CreateNGramExtractor<N, uint32_t, NGramCaseExtraction::kLowerCase>(
  85. kString, IsSeparatorFalse);
  86. std::vector<uint32_t> actual_ngrams(extractor.begin(), extractor.end());
  87. EXPECT_EQ(expected_ngrams, actual_ngrams);
  88. }
  89. TEST(NGramExtractorTest, CaseSensitiveExtraction) {
  90. const std::string kString = "aBcDEFG";
  91. constexpr size_t N = 3;
  92. std::vector<uint32_t> expected_ngrams =
  93. EncodeStringsToIntegers<uint32_t>({"aBc", "BcD", "cDE", "DEF", "EFG"});
  94. auto extractor =
  95. CreateNGramExtractor<N, uint32_t, NGramCaseExtraction::kCaseSensitive>(
  96. kString, IsSeparatorFalse);
  97. std::vector<uint32_t> actual_ngrams(extractor.begin(), extractor.end());
  98. EXPECT_EQ(expected_ngrams, actual_ngrams);
  99. }
  100. TEST(NGramExtractorTest, NGramsArePresent) {
  101. constexpr size_t N = 6;
  102. const std::string kTestCases[] = {
  103. "abcdef", "abacaba", "*abacaba",
  104. "abacaba*", "*abacaba*", "*abacaba*abc^1005001*",
  105. };
  106. for (const std::string& string : kTestCases) {
  107. SCOPED_TRACE(testing::Message() << "String: " << string);
  108. std::vector<uint64_t> expected_ngrams;
  109. for (size_t begin = 0; begin + N <= string.size(); ++begin) {
  110. bool is_valid_ngram = true;
  111. for (size_t i = 0; i < N; ++i) {
  112. if (IsSpecialChar(string[begin + i])) {
  113. is_valid_ngram = false;
  114. break;
  115. }
  116. }
  117. if (is_valid_ngram) {
  118. expected_ngrams.push_back(
  119. EncodeStringToInteger<uint64_t>(string.substr(begin, N)));
  120. }
  121. }
  122. auto extractor =
  123. CreateNGramExtractor<N, uint64_t, NGramCaseExtraction::kLowerCase>(
  124. string, IsSpecialChar);
  125. std::vector<uint64_t> actual_ngrams(extractor.begin(), extractor.end());
  126. EXPECT_EQ(expected_ngrams, actual_ngrams);
  127. }
  128. }
  129. } // namespace url_pattern_index