API tools faq
paste
Advertisement
RobertDeMilo

Ранжирование по TF-IDF (медленно)

RobertDeMilo
Oct 20th, 2023 (edited)
128
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.41 KB | None | 0 0
raw download clone embed print report
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <set>
  4. #include <string>
  5. #include <utility>
  6. #include <vector>
  7. #include <map>
  8. #include <cmath>
  9.  
  10. using namespace std;
  11.  
  12. const int MAX_RESULT_DOCUMENT_COUNT = 5;
  13.  
  14. //Для хранения запроса удобно создать структуру Query с двумя множествами слов : плюс - и минус - словами.
  15. //Возвращать эту структуру по строке запроса нужно в новом приватном методе — ParseQuery.
  16.  
  17. string ReadLine() {
  18.     string s;
  19.     getline(cin, s);
  20.     return s;
  21. }
  22.  
  23. int ReadLineWithNumber() {
  24.     int result = 0;
  25.     cin >> result;
  26.     ReadLine();
  27.     return result;
  28. }
  29.  
  30. vector<string> SplitIntoWords(const string& text) {
  31.     vector<string> words;
  32.     string word;
  33.     for (const char c : text) {
  34.         if (c == ' ') {
  35.             if (!word.empty()) {
  36.                 words.push_back(word);
  37.                 word.clear();
  38.             }
  39.         }
  40.         else {
  41.             word += c;
  42.         }
  43.     }
  44.     if (!word.empty()) {
  45.         words.push_back(word);
  46.     }
  47.  
  48.     return words;
  49. }
  50.  
  51. struct Document {
  52.     int id;
  53.     double relevance;
  54. };
  55.  
  56. class SearchServer {
  57. public:
  58.     void SetStopWords(const string& text) {
  59.         for (const string& word : SplitIntoWords(text)) {
  60.             stop_words_.insert(word);
  61.         }
  62.     }
  63.    
  64.     void AddDocument(int document_id, const string& document) {
  65.  
  66.        
  67.         //map<string, map<int, double>> word_to_document_freqs_;
  68.         //При добавлении документа нужно вычислить TF каждого входящего слова. Это нужно делать в методе AddDocument
  69.        
  70.        
  71.        /* for (const string& word : SplitIntoWordsNoStop(document))
  72.         {
  73.             word_to_document_freqs_[word][document_id] += 1.0 / SplitIntoWordsNoStop(document).size();
  74.         }
  75.         ++document_count_;*/
  76.  
  77.         ++document_count_;
  78.         const vector<string> words = SplitIntoWordsNoStop(document);
  79.         const double inv_word_count = 1.0 / words.size();
  80.         for (const string& word : words) {
  81.             word_to_document_freqs_[word][document_id] += inv_word_count;
  82.         }
  83.     }
  84.  
  85.     vector<Document> FindTopDocuments(const string& raw_query) const {
  86.  
  87.         const Query query_words = ParseQuery(raw_query);
  88.  
  89.         auto matched_documents = FindAllDocuments(query_words);
  90.  
  91.         sort(matched_documents.begin(), matched_documents.end(),
  92.             [](const Document& lhs, const Document& rhs) {
  93.                 return lhs.relevance > rhs.relevance;
  94.             });
  95.         if (matched_documents.size() > MAX_RESULT_DOCUMENT_COUNT) {
  96.             matched_documents.resize(MAX_RESULT_DOCUMENT_COUNT);
  97.         }
  98.         return matched_documents;
  99.     }
  100.  
  101. private:
  102.     // больше не понадобится
  103.     /*struct DocumentContent {
  104.         int id = 0;
  105.         vector<string> words;
  106.     };
  107.     vector<DocumentContent> documents_;*/
  108.  
  109.     // Ключи этого контейнера — слова из добавленных документов,
  110.     // а значения — id документов, в которых это слово встречается.
  111.     //map<string, set<int>> documents_;
  112.  
  113.     double document_count_ = 0;
  114.  
  115.     // Теперь недостаточно для каждого слова хранить список документов, в которых оно встречается.
  116.     // Вместе с каждым документом нужно хранить TF соответствующего слова в этом документе.
  117.     // Эту проблему можно решить, если заменить словарь «слово → документы» на более сложную структуру,
  118.     // которая сопоставляет каждому слову словарь «документ → TF».
  119.  
  120.     map<string, map<int, double>> word_to_document_freqs_;
  121.  
  122.     struct Query
  123.     {
  124.         set<string> plus_words;
  125.         set<string> minus_words;
  126.     };
  127.  
  128.     set<string> stop_words_;
  129.  
  130.     bool IsStopWord(const string& word) const {
  131.         return stop_words_.count(word) > 0;
  132.     }
  133.  
  134.     vector<string> SplitIntoWordsNoStop(const string& text) const {
  135.         vector<string> words;
  136.         for (const string& word : SplitIntoWords(text)) {
  137.             if (!IsStopWord(word)) {
  138.                 words.push_back(word);
  139.             }
  140.         }
  141.         return words;
  142.     }
  143.  
  144.     /*set<string> ParseQuery(const string& text) const*/
  145.     Query ParseQuery(const string& text) const
  146.     {
  147.         /*set<string> query_words;*/
  148.         Query query;
  149.  
  150.         for (const string& word : SplitIntoWordsNoStop(text)) {
  151.  
  152.             if (word[0] == '-')
  153.             {
  154.                 query.minus_words.insert(word.substr(1));
  155.             }
  156.  
  157.             else
  158.             {
  159.                 query.plus_words.insert(word);
  160.             }
  161.         }
  162.         return query;
  163.     }
  164.  
  165.     //В методе FindAllDocuments сначала вычислите релевантность документов, в которые входят плюс - слова запроса.
  166.     //Для этого используйте map<int, int>,  где ключ — id документа, а значение — количество плюс-слов,
  167.     // которые в этом документе встречаются.Затем исключите из получившегося map те документы,
  168.     //в которых встретилось хотя бы одно минус - слово.
  169.  
  170.     //Оставшиеся элементы map скопируйте в результирующий vector<Document>.
  171.  
  172.     /*vector<Document> FindAllDocuments(const set<string>& query_words) const*/
  173.     vector<Document> FindAllDocuments(const Query& query_words) const
  174.     {
  175.  
  176.         vector<Document> matched_documents;
  177.  
  178.         map<int, double> id_relevance;
  179.  
  180.         for (const string& word : query_words.plus_words)
  181.         {
  182.             //map<string, map<int, double>> word_to_document_freqs_;
  183.             if (word_to_document_freqs_.count(word) != 0)
  184.             {
  185.                 for (const auto& [id, TF] : word_to_document_freqs_.at(word))
  186.                 {
  187.                    
  188.                         id_relevance[id] += TF * log(document_count_ / (word_to_document_freqs_.at(word).size()));
  189.                 }
  190.             }
  191.         }
  192.        
  193.         //vector <int> id_with_minus_words;
  194.         ////бежим по минус - словам
  195.         //for (const string& word : query_words.minus_words)
  196.         //{
  197.         //    if (word_to_document_freqs_.count(word) != 0)
  198.         //    {
  199.         //        for (const auto& [id, TF] : word_to_document_freqs_.at(word)) // метод константный поэтому at
  200.         //        {
  201.         //            id_with_minus_words.push_back(id);
  202.         //        }
  203.         //    }
  204.         //}
  205.  
  206.         ////удаляем id с минус - словами
  207.         //for (const auto& id : id_with_minus_words)
  208.         //{
  209.         //    id_relevance.erase(id);
  210.         //}
  211.  
  212.  
  213.          for (const string& word : query_words.minus_words)
  214.         {
  215.             if (word_to_document_freqs_.count(word) != 0)
  216.             {
  217.                 for (const auto [document_id, freq] : word_to_document_freqs_.at(word))
  218.                 {
  219.                     id_relevance.erase(document_id);
  220.                 }
  221.             }
  222.  
  223.         }
  224.  
  225.  
  226.         for (const auto& [id, rel] : id_relevance)
  227.         {
  228.             matched_documents.push_back({ id,rel });
  229.         }
  230.  
  231.         return matched_documents;
  232.     }
  233. };
  234.  
  235. SearchServer CreateSearchServer() {
  236.     SearchServer search_server;
  237.     search_server.SetStopWords(ReadLine());
  238.  
  239.     const int document_count = ReadLineWithNumber();
  240.     for (int document_id = 0; document_id < document_count; ++document_id) {
  241.         search_server.AddDocument(document_id, ReadLine());
  242.     }
  243.  
  244.     return search_server;
  245. }
  246.  
  247. int main() {
  248.     const SearchServer search_server = CreateSearchServer();
  249.  
  250.     const string query = ReadLine();
  251.     for (const auto& [document_id, relevance] : search_server.FindTopDocuments(query)) {
  252.         cout << "{ document_id = "s << document_id << ", "
  253.             << "relevance = "s << relevance << " }"s << endl;
  254.     }
  255. }
  256.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!