sa2304

Relevance values test

Nov 24th, 2020
598
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define UNUSED(x) (void)(x)
  2.  
  3. //------------------------------------------------------------------------------
  4. void AssertAlmostEqualImpl(double lhs, const std::string &lhs_expr_str,
  5.                        double rhs, const std::string &rhs_expr_str,
  6.                        double precision, const std::string &file,
  7.                        const std::string &func, unsigned line,
  8.                        const std::string &hint) {
  9.   bool almost_equal = abs(lhs - rhs) < precision;
  10.   if (!almost_equal) {
  11.     cout << file << "("s << line << "): "s << func << ": "s;
  12.     cout << lhs_expr_str << " = "s << lhs
  13.          << " is not equal to "s
  14.          << rhs_expr_str << " = "s << rhs
  15.          << " with precision "s << precision;
  16.     if (!hint.empty()) {
  17.       cout << " Hint: "s << hint;
  18.     }
  19.     cout << endl;
  20.     abort();
  21.   }
  22. }
  23.  
  24.  
  25. #define ASSERT_ALMOST_EQUAL(a, b, precision) \
  26.   AssertAlmostEqualImpl((a), (#a), (b), (#b), (precision), \
  27.   __FILE__, __FUNCTION__, __LINE__, ""s)
  28.  
  29. #define ASSERT_ALMOST_EQUAL_HINT(a, b, precision, hint) \
  30.   AssertAlmostEqualImpl((a), (#a), (b), (#b), (precision), \
  31.   __FILE__, __FUNCTION__, __LINE__, (hint))
  32.  
  33. //------------------------------------------------------------------------------
  34.  
  35. std::ostream & operator<<(std::ostream & os, DocumentStatus status);
  36.  
  37. void TestMatchDocumentPlusWords();
  38. void TestMatchDocumentMinusWords();
  39. void TestMatchDocumentStopWords();
  40.  
  41. void TestAddDocument();
  42. void TestAddDocumentAverageRating();
  43. void TestAddDocumentStatus();
  44.  
  45. void TestTfIdfCalculation();
  46.  
  47. void TestFindTopDocumentsPlusWords();
  48. void TestFindTopDocumentsMinusWords();
  49. void TestFindTopDocumentsStopWords();
  50. void TestFindTopDocumentsByStatus();
  51. void TestFindTopDocumentsUsingPredicate();
  52. void TestFindTopDocumentsSort();
  53.  
  54. //------------------------------------------------------------------------------
  55.  
  56. // Функция TestSearchServer является точкой входа для запуска тестов
  57. void TestSearchServer();
  58.  
  59. #include <numeric>
  60.  
  61. //------------------------------------------------------------------------------
  62. void TestSearchServer() {
  63.   TestAddDocument();
  64.   TestAddDocumentAverageRating();
  65.   TestAddDocumentStatus();
  66.  
  67.   TestTfIdfCalculation();
  68.  
  69.   TestMatchDocumentPlusWords();
  70.   TestMatchDocumentMinusWords();
  71.   TestMatchDocumentStopWords();
  72.  
  73.   TestFindTopDocumentsPlusWords();
  74.   TestFindTopDocumentsMinusWords();
  75.   TestFindTopDocumentsStopWords();
  76.   TestFindTopDocumentsByStatus();
  77.   TestFindTopDocumentsUsingPredicate();
  78.   TestFindTopDocumentsSort();
  79.   // Не забудьте вызывать остальные тесты здесь
  80. }
  81.  
  82. //------------------------------------------------------------------------------
  83. /** Проверяет, что слова в уже проиндексированном документе можно сделать стоп-словами и исключить из поиска */
  84. void TestFindTopDocumentsStopWords() {
  85.   SearchServer server;
  86.   const int doc_id = 0;
  87.   const vector<int> ratings = { 5 };
  88.   const std::string document_text = "A quick brown fox jumps over lazy dog"s;
  89.   server.AddDocument(doc_id, document_text, DocumentStatus::ACTUAL, ratings);
  90.   const std::string query = "fox"s;
  91.  
  92.   // Убеждаемся, что документ найден по плюс-слову
  93.   {
  94.     auto search_results = server.FindTopDocuments(query);
  95.     ASSERT_EQUAL(1u, search_results.size());
  96.   }
  97.  
  98.   // Делаем слово стоп-словом, убеждаемся, что поисковик теперь его игнорирует
  99.   {
  100.     server.SetStopWords(query);
  101.     auto search_results = server.FindTopDocuments(query);
  102.     ASSERT(search_results.empty());
  103.   }
  104. }
  105.  
  106. //------------------------------------------------------------------------------
  107. void TestFindTopDocumentsMinusWords() {
  108.   SearchServer server;
  109.   const std::string document_text = "A quick brown fox jumps over lazy dog"s;
  110.   server.AddDocument(0, document_text, DocumentStatus::ACTUAL, { 5 });
  111.  
  112.   // Проверим, что документ можно найти по запросу - все три слова есть в документе
  113.   {
  114.     const std::string query = "brown fox dog"s;
  115.     auto results = server.FindTopDocuments(query);
  116.     ASSERT_EQUAL(1u, results.size());
  117.   }
  118.  
  119.   // Одно из слов сделаем минус-словом, убедимся, что теперь документ исключен из поиска
  120.   {
  121.     const std::string query = "brown fox -dog"s;
  122.     auto results = server.FindTopDocuments(query);
  123.     ASSERT(results.empty());
  124.   }
  125. }
  126.  
  127. //------------------------------------------------------------------------------
  128. std::ostream &operator<<(std::ostream &os, DocumentStatus status) {
  129.   return os << static_cast<int>(status);
  130. }
  131. //------------------------------------------------------------------------------
  132. void TestFindTopDocumentsPlusWords() {
  133.   SearchServer server;
  134.   const std::string document_text = "A quick brown fox jumps over lazy dog"s;
  135.   server.AddDocument(0, document_text, DocumentStatus::ACTUAL, { 5 });
  136.  
  137.   const std::string query = "brown dog"s;
  138.   std::vector<Document> results = server.FindTopDocuments(query);
  139.   ASSERT_EQUAL(1u, results.size());
  140.   ASSERT_EQUAL(0, results[0].id);
  141.   ASSERT_EQUAL(5, results[0].rating);
  142.   // Когда документ в индексе единственный, то IDF == 0, т.к. log(1) == 0
  143.   //  std::clog << "log(1) = " << log(1) << std::endl;
  144.   ASSERT(results[0].relevance < 0.0000001);
  145. }
  146.  
  147. //------------------------------------------------------------------------------
  148. void TestAddDocument() {
  149.   const std::string document_text = "A quick brown fox jumps over lazy dog"s;
  150.   const vector<int> doc_ratings = { 1, 2, 3, 4, 5, 5 };
  151.   const DocumentStatus status = DocumentStatus::BANNED;
  152.   SearchServer server;
  153.  
  154.   ASSERT_EQUAL(0, server.GetDocumentCount());
  155.   for (size_t i = 1; i <= 5; ++i) {
  156.     server.AddDocument(i, document_text, status, doc_ratings);
  157.     // Добавление документа увеличивает счетчик
  158.     ASSERT_EQUAL(i, server.GetDocumentCount());
  159.   }
  160. }
  161.  
  162. //------------------------------------------------------------------------------
  163. void TestAddDocumentAverageRating() {
  164.   const std::string document_text = "A quick brown fox jumps over lazy dog"s;
  165.   const vector<int> doc_ratings = { 1, 2, 3, 4, 5, 5 };
  166.   SearchServer server;
  167.   server.AddDocument(0, document_text, DocumentStatus::ACTUAL, doc_ratings);
  168.  
  169.   // Проверим, что документу присвоен рейтинг
  170.   const int avg_rating = static_cast<double>(
  171.         std::accumulate(doc_ratings.begin(),
  172.                         doc_ratings.end(), 0)) / doc_ratings.size();
  173.   const std::string query = "fox"s;
  174.   auto documents = server.FindTopDocuments(query);
  175.   ASSERT_EQUAL(documents.at(0).rating, avg_rating);
  176. }
  177.  
  178. //------------------------------------------------------------------------------
  179. /** FIXME Do we need this test? */
  180. void TestAddDocumentStatus() {
  181.   const int doc_id = 0;
  182.   const std::string document_text = "A quick brown fox jumps over lazy dog"s;
  183.   const vector<int> doc_ratings = { 1, 2, 3, 4, 5, 5 };
  184.   const DocumentStatus status = DocumentStatus::BANNED;
  185.   SearchServer server;
  186.   server.AddDocument(doc_id, document_text, status, doc_ratings);
  187.  
  188.   // Проверим, что документу присвоен статус
  189.   const std::string query = "fox"s;
  190.   // Поиск со статусом ACTUAL по умолчанию не вернет документов
  191.   {
  192.     auto search_results = server.FindTopDocuments(query);
  193.     ASSERT(search_results.empty());
  194.   }
  195.   // Поиск со статусом status должен вернуть наш документ
  196.   {
  197.     auto search_results = server.FindTopDocuments(query, status);
  198.     ASSERT_EQUAL(1u, search_results.size());
  199.   }
  200. }
  201.  
  202. //------------------------------------------------------------------------------
  203. std::map<std::string, size_t> ParseDocumentText(const std::string & text) {
  204.   std::map<std::string, size_t> stats;
  205.   for (const auto & word : SplitIntoWords(text)) {
  206.     ++stats[word];
  207.   }
  208.  
  209.   return stats;
  210. }
  211.  
  212. //------------------------------------------------------------------------------
  213. double CalcTermFrequency(const std::string & term,
  214.                          const std::map<std::string, size_t> & all_words) {
  215.   double tf = 0.0;
  216.   if (all_words.count(term)) {
  217.     auto sum = [](size_t accum, const std::pair<std::string, size_t> & item) {
  218.       const auto & [_, count] = item;
  219.           return accum + count;
  220.     };
  221.     const size_t total_words =
  222.           std::accumulate(all_words.begin(), all_words.end(), 0, sum);
  223.     const int term_count = all_words.at(term);
  224.     tf = static_cast<double>(term_count) / total_words;
  225.   }
  226.  
  227.   return tf;
  228. }
  229.  
  230. //------------------------------------------------------------------------------
  231. double CalcTermFrequency(const std::string & term, const std::string & text) {
  232.   return CalcTermFrequency(term, ParseDocumentText(text));
  233. }
  234.  
  235. //------------------------------------------------------------------------------
  236. double CalcTermInverseDocumentFrequency(const std::string & term,
  237.           const std::vector<std::string> & documents) {
  238.   auto HasTerm = [&term](const std::string & text) {
  239.     return (ParseDocumentText(text).count(term));
  240.   };
  241.   const size_t documents_with_term_count = std::count_if(documents.begin(),
  242.                                                          documents.end(), HasTerm);
  243.  
  244.   return log(static_cast<double>(documents.size()) / documents_with_term_count);
  245. }
  246.  
  247. //------------------------------------------------------------------------------
  248. /** Тест на расчет релевантности документов запросам по TF-IDF */
  249. void TestTfIdfCalculation() {
  250.   SearchServer server;
  251.   const DocumentStatus status_actual = DocumentStatus::ACTUAL;
  252.   const std::vector<int> ratings = {1,2,3,4,5};
  253.  
  254.   const std::vector<std::string> test_documents = {
  255.     "this blue ball"s,
  256.     "this red box"s,
  257.     "this yellow circle"s,
  258.   };
  259.  
  260.   const size_t documents_total = test_documents.size();
  261.   const std::map<std::string, std::map<size_t, double>> tf {
  262.     { "this"s, {
  263.         { 0, 1.0/static_cast<double>(documents_total) },
  264.         { 1, 1.0/static_cast<double>(documents_total) },
  265.         { 2, 1.0/static_cast<double>(documents_total) },
  266.       } },
  267.     { "blue"s, {
  268.         { 0, 1.0/static_cast<double>(documents_total) },
  269.       } },
  270.     { "ball"s, {
  271.         { 0, 1.0/static_cast<double>(documents_total) },
  272.       } },
  273.     { "red"s, {
  274.         { 1, 1.0/static_cast<double>(documents_total) },
  275.       } },
  276.     { "box"s, {
  277.         { 1, 1.0/static_cast<double>(documents_total) },
  278.       } },
  279.     { "yellow"s, {
  280.         { 2, 1.0/static_cast<double>(documents_total) },
  281.       } },
  282.     { "circle"s, {
  283.         { 2, 1.0/static_cast<double>(documents_total) },
  284.       } },
  285.   };
  286.  
  287.   std::map<std::string, size_t> df;
  288.   for (const auto & [term, freqs] : tf) {
  289.     df[term] = freqs.size();
  290.     std::clog << "DF('" << term << "') = " << df.at(term) << std::endl;
  291.   }
  292.  
  293.   const std::map<std::string, double> idf = {
  294.     { "this"s, log( static_cast<double>(documents_total)/df.at("this"s)) },
  295.     { "blue"s, log( static_cast<double>(documents_total)/df.at("blue"s)) },
  296.     { "ball"s, log( static_cast<double>(documents_total)/df.at("ball"s)) },
  297.     { "red"s, log( static_cast<double>(documents_total)/df.at("red"s)) },
  298.     { "box"s, log( static_cast<double>(documents_total)/df.at("box"s)) },
  299.     { "yellow"s, log( static_cast<double>(documents_total)/df.at("yellow"s)) },
  300.     { "circle"s, log( static_cast<double>(documents_total)/df.at("circle"s)) },
  301.   };
  302.   for (const auto & [word, value] : idf) {
  303.     std::clog << "'" << word << "' has IDF=" << value << std::endl;
  304.   }
  305.  
  306.   const std::vector<std::string> queries = {
  307.     "this box"s,
  308.     "this ball"s,
  309.     "this circle"s,
  310.   };
  311.  
  312.   std::map<size_t, std::map<size_t, double>> query_to_doc_relevance = {
  313.     { 0, {
  314.         { 0, 0.0 },
  315.         { 1, 1.0/static_cast<double>(documents_total) * idf.at("box"s) },
  316.         { 2, 0.0 } },
  317.       },
  318.     { 1, {
  319.         { 0, 1.0/static_cast<double>(documents_total) * idf.at("ball"s) },
  320.         { 1, 0.0 },
  321.         { 2, 0.0 },
  322.       } },
  323.     { 2, {
  324.         { 0, 0.0 },
  325.         { 1, 0.0 },
  326.         { 2, 1.0/static_cast<double>(documents_total) * idf.at("circle") }
  327.       } },
  328.     };
  329.  
  330.   // Сперва добавим все документы
  331.   for (size_t i = 0; i < test_documents.size(); ++i) {
  332.     const std::string & text = test_documents.at(i);
  333.     int doc_id = static_cast<int>(i);
  334.     std::clog << "Document [" << doc_id << "] is '" << text << "'" << std::endl;
  335.     server.AddDocument(doc_id, text, status_actual, ratings);
  336.   }
  337.  
  338.   for (size_t q = 0; q < queries.size(); ++q) {
  339.     const std::string & query = queries.at(q);
  340.     std::clog << "Query '" << query << "'" << std::endl;
  341.     auto search_results = server.FindTopDocuments(query);
  342.     for (const auto & doc : search_results) {
  343.       const double expected_relevance = query_to_doc_relevance.at(q).at(doc.id);
  344.       std::clog << "Document [" << doc.id << "], relevance = " << doc.relevance
  345.                 << ", expected = " << expected_relevance
  346.                 << std::endl;
  347.       ASSERT_ALMOST_EQUAL(doc.relevance, expected_relevance, 0.01);
  348.     }
  349.   }
  350. }
  351.  
  352. //------------------------------------------------------------------------------
  353. void TestFindTopDocumentsByStatus() {
  354.   SearchServer server;
  355.   std::string text = "this is an example"s;
  356.   const DocumentStatus status_banned = DocumentStatus::BANNED;
  357.   const std::vector<int> ratings = { 5 };
  358.   const size_t documents_count = 3;
  359.   for (size_t i = 0; i < documents_count; ++i) {
  360.     server.AddDocument(static_cast<int>(i), text, status_banned, ratings);
  361.   }
  362.  
  363.   const std::string query = "this"s;
  364.   // Убелимся, что нет документов со статусом ACTUAL
  365.   {
  366.     auto actual_documents = server.FindTopDocuments(query);
  367.     ASSERT(actual_documents.empty());
  368.   }
  369.   // Убедимся, что все документы - с нужным статусом
  370.   {
  371.     auto banned_documents = server.FindTopDocuments(query, status_banned);
  372.     ASSERT_EQUAL(documents_count, banned_documents.size());
  373.   }
  374. }
  375.  
  376. //------------------------------------------------------------------------------
  377. void TestFindTopDocumentsUsingPredicate() {
  378.   // Добавим два докумета с одинаковым текстом, но разными статусами
  379.   SearchServer server;
  380.   std::string text = "this is an example"s;
  381.   const std::vector<int> avg_ratings = { 1, 2, 3, 4, 4, 4, 7 };
  382.   // Добавим столько документов, сколько объявили рейтингов
  383.   for (size_t i = 0; i < avg_ratings.size(); ++i) {
  384.     server.AddDocument(static_cast<int>(i), text, DocumentStatus::ACTUAL,
  385.                        { avg_ratings.at(i) });
  386.   }
  387.  
  388.   // Поиск без предиката возвращает все документы
  389.   {
  390.     const size_t expected_documents_count =
  391.         std::min(avg_ratings.size(), static_cast<size_t>(MAX_RESULT_DOCUMENT_COUNT));
  392.     ASSERT_EQUAL(expected_documents_count, server.FindTopDocuments(text).size());
  393.   }
  394.  
  395.   // Найдем документ по предикату с существующим id
  396.   {
  397.     const int id = 0;
  398.     auto predicate_id = [id](int doc_id, DocumentStatus status, int rating) {
  399.       UNUSED(status);
  400.       UNUSED(rating);
  401.       return doc_id == id;
  402.     };
  403.     auto search_results = server.FindTopDocuments(text, predicate_id);
  404.     ASSERT_EQUAL(1u, search_results.size());
  405.     ASSERT_EQUAL(id, search_results.at(0).id);
  406.   }
  407.  
  408.   // Убедимся, что поиск по предикату с несуществующим id не возвращает документов
  409.   {
  410.     const int id_not_exists = avg_ratings.size();
  411.     auto predicate_id = [id_not_exists](int doc_id, DocumentStatus status, int rating) {
  412.       UNUSED(status);
  413.       UNUSED(rating);
  414.       return doc_id == id_not_exists;
  415.     };
  416.     auto search_results = server.FindTopDocuments(text, predicate_id);
  417.     ASSERT(search_results.empty());
  418.   }
  419.  
  420.   // Найдем документы с рейтингом 4 по предикату
  421.   {
  422.     auto predicate_rating4 = [](int doc_id, DocumentStatus status, int rating) {
  423.       UNUSED(doc_id);
  424.       UNUSED(status);
  425.       return rating == 4;
  426.     };
  427.     auto search_results = server.FindTopDocuments(text, predicate_rating4);
  428.     ASSERT_EQUAL(std::count( avg_ratings.begin(), avg_ratings.end(), 4 ),
  429.                  search_results.size());
  430.   }
  431. }
  432.  
  433. //------------------------------------------------------------------------------
  434. void TestFindTopDocumentsSort() {
  435.   SearchServer server;
  436.   const DocumentStatus status_actual = DocumentStatus::ACTUAL;
  437.   const std::vector<int> ratings = {1,2,3,4,5};
  438.  
  439.   // Нарочно перепутаем порядок документов, чтобы поисковик не мог случайно вернуть документы в порядке их добавления
  440.   const std::vector<std::string> test_documents = {
  441.     "this is a green crocodile"s,
  442.     "this is a a test"s,
  443.     "this is a white crocodile"s,
  444.   };
  445.   const std::string query = "this white crocodile"s;
  446.  
  447.   // Сперва добавим все документы
  448.   for (size_t i = 0; i < test_documents.size(); ++i) {
  449.     const std::string text = test_documents.at(i);
  450.     server.AddDocument(i, text, status_actual, ratings);
  451.   }
  452.  
  453.   // Документы упорядочены по убыванию релевантности
  454.   auto search_results = server.FindTopDocuments(query);
  455.   for (size_t i = 0; i < search_results.size(); ++i) {
  456.     if (0 < i) {
  457.       ASSERT(search_results.at(i).relevance <= search_results.at(i-1).relevance);
  458.     }
  459.   }
  460. }
  461.  
  462. //------------------------------------------------------------------------------
  463. /** Проверим, что MatchDocument работает по плюс-словам */
  464. void TestMatchDocumentPlusWords() {
  465.   SearchServer server;
  466.   const std::string document_text = "A quick brown fox jumps over lazy dog"s;
  467.   server.AddDocument(0, document_text, DocumentStatus::ACTUAL, { 5 });
  468.  
  469.   const std::string query = "brown dog"s;
  470.   auto [matched_words, status] = server.MatchDocument(query, 0);
  471.   const std::vector<std::string> expected_matched_words = { "brown"s, "dog"s };
  472.   ASSERT_EQUAL(DocumentStatus::ACTUAL, status);
  473.   ASSERT_EQUAL(expected_matched_words, matched_words);
  474. }
  475.  
  476. //------------------------------------------------------------------------------
  477. /** Проверим, что MatchDocument исключает документы с минус-словами */
  478. void TestMatchDocumentMinusWords() {
  479.   SearchServer server;
  480.   const std::string document_text = "A quick brown fox jumps over lazy dog"s;
  481.   server.AddDocument(0, document_text, DocumentStatus::ACTUAL, { 5 });
  482.  
  483.   // Проверим, что документ можно найти по запросу - все три слова есть в документе
  484.   {
  485.     const std::string query = "brown fox dog"s;
  486.     auto [matched_words, status] = server.MatchDocument(query, 0);
  487.     ASSERT_EQUAL(3u, matched_words.size());
  488.   }
  489.  
  490.   // Одно из слов сделаем минус-словом, убедимся, что теперь документ не подходит к запросу
  491.   {
  492.     const std::string query = "brown fox -dog"s;
  493.     auto [matched_words, status] = server.MatchDocument(query, 0);
  494.     ASSERT(matched_words.empty());
  495.   }
  496. }
  497.  
  498. //------------------------------------------------------------------------------
  499. /** Проверим, что MatchDocument игнорирует стоп-слова в запросах */
  500. void TestMatchDocumentStopWords() {
  501.   SearchServer server;
  502.   const std::string stop_words = "a the fox"s;
  503.   server.SetStopWords(stop_words);
  504.   const std::string document_text = "A quick brown fox jumps over lazy dog"s;
  505.   server.AddDocument(0, document_text, DocumentStatus::ACTUAL, { 5 });
  506.  
  507.   {
  508.     auto [matched_words, status] = server.MatchDocument("brown fox", 0);
  509.     ASSERT_EQUAL(1u, matched_words.size());
  510.     ASSERT_EQUAL("brown", matched_words.at(0));
  511.   }
  512. }
  513.  
RAW Paste Data