SHOW:
|
|
- or go back to the newest paste.
| 1 | // Код поисковой системы из финального задания спринта №2 | |
| 2 | #include <algorithm> | |
| 3 | #include <cmath> | |
| 4 | #include <iostream> | |
| 5 | #include <map> | |
| 6 | #include <set> | |
| 7 | #include <string> | |
| 8 | #include <utility> | |
| 9 | #include <vector> | |
| 10 | #include <numeric> | |
| 11 | ||
| 12 | using namespace std; | |
| 13 | ||
| 14 | const int MAX_RESULT_DOCUMENT_COUNT = 5; | |
| 15 | constexpr double EPSILON = 1e-6; | |
| 16 | ||
| 17 | string ReadLine() {
| |
| 18 | string s; | |
| 19 | getline(cin, s); | |
| 20 | return s; | |
| 21 | } | |
| 22 | ||
| 23 | int ReadLineWithNumber() {
| |
| 24 | int result; | |
| 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 | } else {
| |
| 40 | word += c; | |
| 41 | } | |
| 42 | } | |
| 43 | if (!word.empty()) {
| |
| 44 | words.push_back(word); | |
| 45 | } | |
| 46 | ||
| 47 | return words; | |
| 48 | } | |
| 49 | ||
| 50 | template <typename StringCollection> | |
| 51 | set<string> NotEmptyStringCollection(const StringCollection& collection) {
| |
| 52 | set<string> not_empty_strings_collection; | |
| 53 | for (const auto& stringg : collection) {
| |
| 54 | if (!(stringg.empty())) {
| |
| 55 | not_empty_strings_collection.insert(stringg); | |
| 56 | } | |
| 57 | } | |
| 58 | return not_empty_strings_collection; | |
| 59 | } | |
| 60 | ||
| 61 | struct Document {
| |
| 62 | ||
| 63 | Document() = default; | |
| 64 | ||
| 65 | Document(int id_doc, double relevance_doc, int rating_doc) : id(id_doc), relevance(relevance_doc), rating(rating_doc){}
| |
| 66 | ||
| 67 | int id = 0; | |
| 68 | double relevance = 0.0; | |
| 69 | int rating = 0; | |
| 70 | }; | |
| 71 | ||
| 72 | enum class DocumentStatus {
| |
| 73 | ACTUAL, | |
| 74 | IRRELEVANT, | |
| 75 | BANNED, | |
| 76 | REMOVED, | |
| 77 | }; | |
| 78 | ||
| 79 | class SearchServer {
| |
| 80 | public: | |
| 81 | ||
| 82 | explicit SearchServer(const string& stop_words_string) : SearchServer(SplitIntoWords(stop_words_string)){}
| |
| 83 | ||
| 84 | template <typename StringCollection> | |
| 85 | explicit SearchServer(const StringCollection& stop_words) : stop_words_(NotEmptyStringCollection(stop_words)){}
| |
| 86 | ||
| 87 | void AddDocument(int document_id, const string& document, DocumentStatus status, | |
| 88 | const vector<int>& ratings) {
| |
| 89 | const vector<string> words = SplitIntoWordsNoStop(document); | |
| 90 | const double inv_word_count = 1.0 / words.size(); | |
| 91 | for (const string& word : words) {
| |
| 92 | word_to_document_freqs_[word][document_id] += inv_word_count; | |
| 93 | } | |
| 94 | documents_.emplace(document_id, DocumentData{ComputeAverageRating(ratings), status});
| |
| 95 | } | |
| 96 | ||
| 97 | template <typename Helper> | |
| 98 | vector<Document> FindTopDocuments(const string& raw_query, const Helper& helper) const {
| |
| 99 | const Query query = ParseQuery(raw_query); | |
| 100 | auto matched_documents = FindAllDocuments(query, helper); | |
| 101 | ||
| 102 | sort(matched_documents.begin(), matched_documents.end(), | |
| 103 | [](const Document& lhs, const Document& rhs) {
| |
| 104 | if (abs(lhs.relevance - rhs.relevance) < EPSILON) {
| |
| 105 | return lhs.rating > rhs.rating; | |
| 106 | } else {
| |
| 107 | return lhs.relevance > rhs.relevance; | |
| 108 | } | |
| 109 | }); | |
| 110 | if (matched_documents.size() > MAX_RESULT_DOCUMENT_COUNT) {
| |
| 111 | matched_documents.resize(MAX_RESULT_DOCUMENT_COUNT); | |
| 112 | } | |
| 113 | return matched_documents; | |
| 114 | } | |
| 115 | ||
| 116 | vector<Document> FindTopDocuments(const string& raw_query, DocumentStatus status) const {
| |
| 117 | auto result = FindTopDocuments(raw_query, [status](int id, const DocumentStatus& doc_status, int raring) {return status == doc_status;});
| |
| 118 | return result; | |
| 119 | } | |
| 120 | ||
| 121 | vector<Document> FindTopDocuments(const string& raw_query) const {
| |
| 122 | auto result = FindTopDocuments(raw_query, DocumentStatus::ACTUAL); | |
| 123 | return result; | |
| 124 | } | |
| 125 | ||
| 126 | int GetDocumentCount() const {
| |
| 127 | return documents_.size(); | |
| 128 | } | |
| 129 | ||
| 130 | tuple<vector<string>, DocumentStatus> MatchDocument(const string& raw_query, | |
| 131 | int document_id) const {
| |
| 132 | const Query query = ParseQuery(raw_query); | |
| 133 | vector<string> matched_words; | |
| 134 | for (const string& word : query.plus_words) {
| |
| 135 | if (word_to_document_freqs_.count(word) == 0) {
| |
| 136 | continue; | |
| 137 | } | |
| 138 | if (word_to_document_freqs_.at(word).count(document_id)) {
| |
| 139 | matched_words.push_back(word); | |
| 140 | } | |
| 141 | } | |
| 142 | for (const string& word : query.minus_words) {
| |
| 143 | if (word_to_document_freqs_.count(word) == 0) {
| |
| 144 | continue; | |
| 145 | } | |
| 146 | if (word_to_document_freqs_.at(word).count(document_id)) {
| |
| 147 | matched_words.clear(); | |
| 148 | break; | |
| 149 | } | |
| 150 | } | |
| 151 | return {matched_words, documents_.at(document_id).status};
| |
| 152 | } | |
| 153 | ||
| 154 | ||
| 155 | private: | |
| 156 | struct DocumentData {
| |
| 157 | int rating; | |
| 158 | DocumentStatus status; | |
| 159 | }; | |
| 160 | ||
| 161 | set<string> stop_words_; | |
| 162 | map<string, map<int, double>> word_to_document_freqs_; | |
| 163 | map<int, DocumentData> documents_; | |
| 164 | ||
| 165 | bool IsStopWord(const string& word) const {
| |
| 166 | return stop_words_.count(word) > 0; | |
| 167 | } | |
| 168 | ||
| 169 | vector<string> SplitIntoWordsNoStop(const string& text) const {
| |
| 170 | vector<string> words; | |
| 171 | for (const string& word : SplitIntoWords(text)) {
| |
| 172 | if (!IsStopWord(word)) {
| |
| 173 | words.push_back(word); | |
| 174 | } | |
| 175 | } | |
| 176 | return words; | |
| 177 | } | |
| 178 | ||
| 179 | static int ComputeAverageRating(const vector<int>& ratings) {
| |
| 180 | if (ratings.empty()) {
| |
| 181 | return 0; | |
| 182 | } | |
| 183 | /*int rating_sum = 0; | |
| 184 | for (const int rating : ratings) {
| |
| 185 | rating_sum += rating; | |
| 186 | }*/ | |
| 187 | return accumulate(ratings.begin(), ratings.end(), 0) / static_cast<int>(ratings.size()); | |
| 188 | } | |
| 189 | ||
| 190 | struct QueryWord {
| |
| 191 | string data; | |
| 192 | bool is_minus; | |
| 193 | bool is_stop; | |
| 194 | }; | |
| 195 | ||
| 196 | QueryWord ParseQueryWord(string text) const {
| |
| 197 | bool is_minus = false; | |
| 198 | // Word shouldn't be empty | |
| 199 | if (text[0] == '-') {
| |
| 200 | is_minus = true; | |
| 201 | text = text.substr(1); | |
| 202 | } | |
| 203 | return {text, is_minus, IsStopWord(text)};
| |
| 204 | } | |
| 205 | ||
| 206 | struct Query {
| |
| 207 | set<string> plus_words; | |
| 208 | set<string> minus_words; | |
| 209 | }; | |
| 210 | ||
| 211 | Query ParseQuery(const string& text) const {
| |
| 212 | Query query; | |
| 213 | for (const string& word : SplitIntoWords(text)) {
| |
| 214 | const QueryWord query_word = ParseQueryWord(word); | |
| 215 | if (!query_word.is_stop) {
| |
| 216 | if (query_word.is_minus) {
| |
| 217 | query.minus_words.insert(query_word.data); | |
| 218 | } else {
| |
| 219 | query.plus_words.insert(query_word.data); | |
| 220 | } | |
| 221 | } | |
| 222 | } | |
| 223 | return query; | |
| 224 | } | |
| 225 | ||
| 226 | // Existence required | |
| 227 | double ComputeWordInverseDocumentFreq(const string& word) const {
| |
| 228 | return log(GetDocumentCount() * 1.0 / word_to_document_freqs_.at(word).size()); | |
| 229 | } | |
| 230 | ||
| 231 | template <typename Helper> | |
| 232 | vector<Document> FindAllDocuments(const Query& query, Helper& helper) const {
| |
| 233 | map<int, double> document_to_relevance; | |
| 234 | for (const string& word : query.plus_words) {
| |
| 235 | if (word_to_document_freqs_.count(word) == 0) {
| |
| 236 | continue; | |
| 237 | } | |
| 238 | const double inverse_document_freq = ComputeWordInverseDocumentFreq(word); | |
| 239 | for (const auto [document_id, term_freq] : word_to_document_freqs_.at(word)) {
| |
| 240 | const auto& document_data = documents_.at(document_id); | |
| 241 | if (helper(document_id, document_data.status, document_data.rating)) {
| |
| 242 | document_to_relevance[document_id] += term_freq * inverse_document_freq; | |
| 243 | } | |
| 244 | } | |
| 245 | } | |
| 246 | ||
| 247 | for (const string& word : query.minus_words) {
| |
| 248 | if (word_to_document_freqs_.count(word) == 0) {
| |
| 249 | continue; | |
| 250 | } | |
| 251 | for (const auto [document_id, _] : word_to_document_freqs_.at(word)) {
| |
| 252 | document_to_relevance.erase(document_id); | |
| 253 | } | |
| 254 | } | |
| 255 | ||
| 256 | vector<Document> matched_documents; | |
| 257 | for (const auto [document_id, relevance] : document_to_relevance) {
| |
| 258 | matched_documents.push_back( | |
| 259 | {document_id, relevance, documents_.at(document_id).rating});
| |
| 260 | } | |
| 261 | return matched_documents; | |
| 262 | } | |
| 263 | }; | |
| 264 | ||
| 265 | // ==================== для примера ========================= | |
| 266 | ||
| 267 | ||
| 268 |