API tools faq
paste
kutuzzzov

Урок 3. Ранжирование по TF-IDF

kutuzzzov
Nov 8th, 2021 (edited)
250
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.09 KB | None | 0 0
raw download clone embed print report
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <map>
  4. #include <set>
  5. #include <string>
  6. #include <utility>
  7. #include <vector>
  8. #include <cmath>
  9.  
  10. using namespace std;
  11.  
  12. const int MAX_RESULT_DOCUMENT_COUNT = 5;
  13.  
  14. // функция считывания слов
  15. string ReadLine() {
  16. string s;
  17. getline(cin, s);
  18. return s;
  19. }
  20. // функция считывания количества слов
  21. int ReadLineWithNumber() {
  22. int result;
  23. cin >> result;
  24. ReadLine();
  25. return result;
  26. }
  27. // функция разбиения на слова и записи в вектор слов words
  28. vector<string> SplitIntoWords(const string& text) {
  29. vector<string> words;
  30. string word;
  31. for (const char c : text) {
  32. if (c == ' ') {
  33. words.push_back(word);
  34. word = "";
  35. } else {
  36. word += c;
  37. }
  38. }
  39. words.push_back(word);
  40.  
  41. return words;
  42. }
  43. // объявление структуры документов с двумя переменными: id и relevance
  44. struct Document {
  45. int id;
  46. double relevance;
  47. };
  48. // объявление структуры запроса с плюс и минус словами
  49. struct Query {
  50. vector<string> plus_words;
  51. vector<string> minus_words;
  52. };
  53.  
  54. // механизм поиска
  55. class SearchServer {
  56. public:
  57. // функция считывания стоп-слов и записи их в stop_words_
  58. void SetStopWords(const string& text) {
  59. for (const string& word : SplitIntoWords(text)) {
  60. stop_words_.insert(word);
  61. }
  62. }
  63. // функция добавления слов поискового запроса (без стоп-слов) в word_to_documents_
  64. void AddDocument(int document_id, const string& document) {
  65. vector<string> words = SplitIntoWordsNoStop(document);
  66. for (const string& word : words) {
  67.  
  68. // вычисляем TF - делим количество раз встречающегося слова на количество всех слов
  69. double tf = count(words.begin(), words.end(), word) / double(words.size());
  70. word_to_document_freqs_[word][document_id] = tf;
  71. }
  72. ++document_count_;
  73. }
  74. // функция вывода 5 наиболее релевантных результатов из всех найденных
  75. vector<Document> FindTopDocuments(const string& query) const {
  76. auto matched_documents = FindAllDocuments(query);
  77.  
  78. sort(
  79. matched_documents.begin(),
  80. matched_documents.end(),
  81. [](const Document& lhs, const Document& rhs) {
  82. return lhs.relevance > rhs.relevance;
  83. }
  84. );
  85. if (matched_documents.size() > MAX_RESULT_DOCUMENT_COUNT) {
  86. matched_documents.resize(MAX_RESULT_DOCUMENT_COUNT);
  87. }
  88. return matched_documents;
  89. }
  90.  
  91. private:
  92. // map<string, set<int>> word_to_documents_; меняем словарь «слово → документы» на «документ → TF»
  93. map<string, map<int, double>> word_to_document_freqs_;
  94. double document_count_ = 0;
  95. set<string> stop_words_;
  96.  
  97. // функция считывания слов поискового запроса и удаления из него стоп-слов (считывание плюс-слов)
  98. vector<string> SplitIntoWordsNoStop(const string& text) const {
  99. vector<string> words;
  100. for (const string& word : SplitIntoWords(text)) {
  101. if (stop_words_.count(word) == 0) {
  102. words.push_back(word);
  103. }
  104. }
  105. return words;
  106. }
  107. // обработка минус-слов запроса
  108. Query ParseQuery(const string& query) const {
  109. Query QueryWords;
  110. for (string& word : SplitIntoWords(query)) {
  111. if (word[0] == '-') {
  112. word = word.substr(1);
  113. QueryWords.minus_words.push_back(word);
  114. } else {
  115. QueryWords.plus_words.push_back(word);
  116. }
  117. }
  118. return QueryWords;
  119. }
  120. // НОВАЯ функция вывода ВСЕХ найденных результатов по релевантности по формуле TF-IDF
  121. vector<Document> FindAllDocuments(const string& query) const {
  122. Query query_words = ParseQuery(query);
  123. map<int, double> document_to_relevance;
  124.  
  125. // вычисляем IDF - делим количество документов где встречается слово на количество всех документов и берём нат.логарифм
  126. for (const string& word : query_words.plus_words) {
  127. if (word_to_document_freqs_.count(word) == 0) {
  128. continue;
  129. }
  130. double idf = log(
  131. document_count_ / word_to_document_freqs_.at(word).size());
  132.  
  133. // IDF каждого слова запроса умножается на TF этого слова в этом документе и суммируем для результата
  134. for (auto[document_id, tf]: word_to_document_freqs_.at(word)) {
  135. document_to_relevance[document_id] += idf * tf;
  136. }
  137. }
  138.  
  139. /*
  140. // старая функция вывода ВСЕХ найденных результатов по релевантности
  141. vector<Document> FindAllDocuments(const string& query) const {
  142. Query query_words = ParseQuery(query);
  143. map<int, int> document_to_relevance;
  144. for (const string& word : query_words.plus_words) {
  145. if (word_to_documents_.count(word) == 0) {
  146. continue;
  147. }
  148. for (const int document_id : word_to_documents_.at(word)) {
  149. ++document_to_relevance[document_id];
  150. }
  151. }
  152. */
  153. for (const string& word : query_words.minus_words) {
  154. if (word_to_document_freqs_.count(word) == 0) {
  155. continue;
  156. }
  157. for (auto [document_id, tf] : word_to_document_freqs_.at(word)) {
  158. document_to_relevance.erase(document_id);
  159. }
  160. }
  161. vector<Document> matched_documents;
  162. for (auto [document_id, relevance] : document_to_relevance) {
  163. matched_documents.push_back({document_id, relevance});
  164. }
  165. return matched_documents;
  166. }
  167. };
  168.  
  169. // считываем всё с ввода
  170. SearchServer CreateSearchServer() {
  171. SearchServer search_server;
  172. search_server.SetStopWords(ReadLine());
  173.  
  174. const int document_count = ReadLineWithNumber();
  175. for (int document_id = 0; document_id < document_count; ++document_id) {
  176. search_server.AddDocument(document_id, ReadLine());
  177. }
  178. return search_server;
  179. }
  180.  
  181.  
  182. int main() {
  183. const SearchServer search_server = CreateSearchServer();
  184. const string query = ReadLine();
  185.  
  186. // вывод результата поиска
  187. for (auto [document_id, relevance] : search_server.FindTopDocuments(query)) {
  188. cout << "{ document_id = " << document_id << ", relevance = " << relevance << " }" << endl;
  189. }
  190. }
Add Comment
Please, Sign In to add comment
Public Pastes
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!