+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + **زبان‌های مجاز: `Java, C#, C++`** ---------- *در خانه‌ی مشهور شماره ۲۲۱ بیکر استریت، جاناتان کولمز، یک برنامه‌نویس با استعداد و دستیار وفادارش دکتر واتسون، به دنبال حل یک معمای جدید هستند. یک روز وقتی که جاناتان به دفترچه‌ی پوشه‌دار خود مراجعه می‌کند، با اسنادی مرموز و عجیب مواجه می‌شود.* این اسناد به زبان انگلیسی نوشته شده‌اند و به نظر می‌رسد برای نظریه‌پردازی درباره‌ی یک پرونده‌ی مخفی تهیه شده‌اند. جاناتان و دکتر واتسون، با تصمیم به حل این معما، به ساختن ابزاری سریع و قدرتمند می‌پردازند که به آن‌ها کمک می‌کند تا اطلاعات مورد نیاز خود را از متون مرموز استخراج کرده و معمایی که پیش رویشان قرار دارد را حل نمایند. # گام اول: پیش‌پردازش اسناد اولین گام، پیش‌پردازش متون اسناد است. این پیاده‌سازی باید شامل موارد زیر باشد: <details class="purple"> <summary> **تبدیل متن به حروف کوچک** </summary> ---------- برای جلوگیری از مشکلات مربوط به حساسیت به بزرگی و کوچکی حروف، همه حروف موجود در متن باید به حروف کوچک تبدیل شوند. برای مثال متن سند پیش از پردازش: ``` Please HELP! Halis said. ``` پس از این پردازش به متن زیر تبدیل خواهد شد: ``` please help! halis said. ``` </details> <details class="purple"> <summary> **پاکسازی متن** </summary> ---------- هرگونه کاراکتر غیر از حروف انگلیسی و اعداد که برای جستجوی متنی اهمیتی ندارند، باید حذف شوند. برای مثال متن سند پیش از پردازش: ``` please help! halis said. ``` پس از این پردازش به متن زیر تبدیل خواهد شد: ``` please help halis said ``` </details> <details class="purple"> <summary> **حذف کلمات توقفی** </summary> ---------- کلمات توقفی شامل موارد زیر هستند که در جستجوها نادیده گرفته می‌شوند و باید از متن حذف شوند: ``` "a", "an", "and", "are", "as", "at", "be", "but", "by", "for", "if", "in", "into", "is", "it", "no", "not", "of", "on", "or", "such", "that", "the", "their", "then", "there", "these", "they", "this", "to", "was", "will", "with" ``` برای مثال متن پیش از پردازش: ``` halis is a programmer ``` پس از این پردازش به متن زیر تبدیل خواهد شد: ``` halis programmer ``` </details> <details class="purple"> <summary> **حذف فاصله‌های اضافی** </summary> ---------- نیاز است هرگونه فاصله اضافی بین کلمات حذف شود. برای مثال متن پیش از پردازش: ``` please help halis said ``` پس از این پردازش به متن زیر تبدیل خواهد شد: ``` please help halis said ``` </details> # گام دوم: طراحی Inverted Index ساختار داده Inverted Index، ساختاری است که امکان نگهداری اطلاعات برای جستجوی سریع متنی را فراهم می‌کند. در ادامه با این ساختار داده بیشتر آشنا می‌شوید. <details class="blue"> <summary> **ایجاد لیست کلمات** </summary> ---------- در این مرحله، باید تمامی کلمات موجود در هر سند را شناسایی کرده و لیستی از این کلمات ایجاد کنیم. این لیست، پایه‌ای برای ساخت Inverted Index است. برای مثال در سند زیر: ``` "please help halis said" ``` لیست کلمات به این شکل خواهد بود: ``` ["please", "help", "halis", "said"] ``` </details> <details class="blue"> <summary> **ایجاد Inverted Index** </summary> ---------- در این مرحله، یک دیکشنری ایجاد می‌شود که کلیدهای آن کلمات موجود در لیست کلمات هستند و مقادیر آن‌ها لیستی از شماره اسنادی است که هر کلمه در آن‌ها ظاهر شده است. برای مثال دو سند پیش‌پردازش شده زیر را در نظر بگیرید: ``` Document 1: "please help halis said" Document 2: "halis writes code" ``` بنابراین Inverted Index به این شکل خواهد بود: ``` { "please": [1], "help": [1], "halis": [1, 2], "said": [1], "writes": [2], "code": [2] } ``` همانطور که می‌بینید، کلمه `halis` هم در سند 1 و هم در سند 2 وجود دارد؛ در حالی که کلمه `please` تنها در سند 1 و کلمه `code` تنها در سند 2 وجود دارند. <details class="red"> <summary> **نکته مهم: Inverted Index از روی اسناد پیش‌پردازش شده ایجاد می‌شود.** </summary> </details> </details> <details class="blue"> <summary> **بازیابی اسناد** </summary> ---------- اکنون می‌توانیم به کمک ساختار داده ایجاد شده، اسناد دلخواه را بازیابی کنیم. برای مثال Inverted Index زیر را درنظر بگیرید: ``` { "sherlock": [1], "halis": [1, 3, 4], "watson": [1, 2], "moriarty": [2, 3, 4] } ``` می‌خواهیم بدانیم کلمات `halis` و `watson` هم‌زمان در چه اسنادی آمده‌است. برای این منظور، کافی است اشتراک شماره اسناد برای این دو کلمه را بررسی کنیم: ``` intersect([1, 3, 4], [1, 2]) = [1] ``` همانطور که می‌بینید، می‌توان نتیجه گرفت کلمات `halis` و `watson` هم‌زمان در سند 1 آمده اند. </details> # گام سوم: جستجوی متنی در این گام، کوئری‌هایی طراحی می‌شوند که به کمک آن‌ها می‌توان جستجوی متنی پیشرفته انجام داد و شماره اسناد مربوطه را بازیابی کرد. ساختار این کوئری‌ها با فرمت `JSON` است که در ادامه معرفی خواهند شد. ## کوئری‌های فرزند <details class="green"> <summary> **کوئری `match`** </summary> با استفاده از این کوئری، اسنادی که شامل یک عبارت مشخص هستند، بازیابی می‌شوند. ``` { "match": "john watson" } ``` در مثال بالا، اسنادی که شامل عبارت `john watson` هستند بازیابی می‌شوند؛ یعنی این دو کلمه پشت سر هم در متن پیش پردازش شده سند وجود داشته باشد. </details> <details class="green"> <summary> **کوئری `all`** </summary> با استفاده از این کوئری، اسنادی که شامل تمام عبارات هستند، بازیابی می‌شوند. ``` { "all": ["john watson", "moriarty"] } ``` در مثال بالا، اسنادی که شامل هر دو عبارت `moriarty` و `john watson` هستند بازیابی می‌شوند. </details> <details class="green"> <summary> **کوئری `any`** </summary> با استفاده از این کوئری، اسنادی که شامل حداقل یکی از عبارات هستند، بازیابی می‌شوند. ``` { "any": ["john watson", "moriarty"] } ``` در مثال بالا، اسنادی که شامل حداقل یکی از عبارت‌های `moriarty` یا `john watson` باشند بازیابی می‌شوند. </details> <details class="yellow"> <summary> **توجه: منظور از عبارت، یک یا چند کلمه با حروف کوچک است که با فاصله از هم جدا شده‌اند.** </summary> </details> ## کوئری‌های والد <details class="green"> <summary> **کوئری `and`** </summary> با استفاده از این کوئری، اسنادی بازیابی می‌شوند که با تمام از کوئری‌های فرزند به طور همزمان مطابقت دارند. ``` { "and": [ { "match": "rainy" }, { "match": "sherlock" }, { "match": "death" } ] } ``` در مثال بالا، اسنادی بازیابی می‌شوند که شامل هر سه کلمه‌ی `rainy` ، `sherlock` و `death` باشند. یک نمونه کوئری دیگر شامل `and`: ``` { "and": [ { "match": "rainy night" }, { "and": [ { "all": ["sherlock holmes", "dr john watson", "moriarty"] }, { "any": ["death"] } ] } ] } ``` </details> <details class="green"> <summary> **کوئری `or`** </summary> با استفاده از این کوئری، اسنادی بازیابی می‌شوند که با حداقل یکی از کوئری‌های فرزند مطابقت داشته باشد. ``` { "or": [ { "match": "rainy night" }, { "all": ["sherlock holmes", "dr john watson", "moriarty"] }, { "any": ["death", "blood"] } ] } ``` در مثال بالا، اسنادی بازیابی می‌شوند که یا شامل عبارت `rainy night` باشند، یا اینکه همه عبارات `sherlock holmes`، `dr john watson` و `moriarty` در آن اسناد آمده باشد، و یا اینکه حداقل یکی از کلمات `death` یا `boold` در آن اسناد آمده باشد. </details> <details class="green"> <summary> **کوئری `not`** </summary> با استفاده از این کوئری، تمام اسنادی که با کوئری فرزند مطابقت نداشته باشند بازیابی می‌شوند. ``` { "not": { "and": [ { "match": "knife" }, { "match": "gun" } ] } } ``` در مثال بالا، اسنادی بازیابی می‌شوند که هر دو عبارت `knife` و `gun` همزمان در آن اسناد نیامده باشد. </details> ## نکات تکمیلی (مهم) <details class="red"> <summary> **نکته اول** </summary> کوئری‌های والد، خود نیز می‌توانند فرزند کوئری والد دیگری باشند. ``` { "and": [ { "or": [...] }, { "and": [...] }, { "not": {...} } ] } ``` </details> <details class="red"> <summary> **نکته دوم** </summary> در ریشه کوئری، ممکن است متغیر `size` بیاید که نشان دهنده حداکثر تعداد اسنادی است که باید بازیابی شوند. درصورتی که اندازه مشخص نشده بود، همه نتایج بازیابی می‌شوند. ``` { "and": [...], "size": 10 } ``` </details> # جمع‌بندی هدف این است که ابزاری ساخته شود تا متون اسناد را پیش پردازش کرده، سپس ساختار داده Inverted Index ایجاد شود. در نهایت به کمک این ساختار داده جهت افزایش سرعت جستجو، کوئری‌هایی با هدف بازیابی اسناد مختلف، پردازش شوند. <details class="yellow"> <summary> **توجه: لازم است اصول برنامه نویسی شیءگرا، کد تمیز و اصول SOLID تا حد ممکن در نظر گرفته شود.** </summary> </details> <details class="yellow"> <summary> **توجه: امکان پیاده‌سازی بخشی از سوال و کسب نمره آن بخش از سوال وجود دارد.** </summary> </details> <details class="yellow"> <summary> **توجه: تنها یک فایل شامل کدهای نوشته شده آپلود کنید.** </summary> </details> # ورودی ورودی شامل $n + q + 2$ خط است. در خط اول، $n$ تعداد سندها، داده می‌شود. در $n$ خط بعدی، در هر خط متن سند $i$ام داده می‌شود. سپس، عدد $q$ (تعداد کوئری‌ها) آمده است. در $q$ خط بعدی، در هر خط یک کوئری با فرمت `JSONPath` می‌آید. $$1 \le n \le 150$$ $$1 \le q \le 1500$$ <details class="yellow"> <summary> **راهنمایی: برای تبدیل کوئری از فرمت JSONPath به فرمت JSON، می‌توانید از این کدها استفاده نمایید.**</summary> <details class="orange"> <summary> **کد Java** </summary> ```Java import java.util.*; class JsonObjectCreator { private void setValue(Map<String, Object> json, String path, String value) { String[] keys = path.split("\\."); for (int i = 0; i < keys.length; i++) { String key = keys[i]; if (key.contains("[") && key.contains("]")) { String keyPart = key.substring(0, key.indexOf('[')); int index = Integer.parseInt(key.substring(key.indexOf('[') + 1, key.indexOf(']'))); if (!json.containsKey(keyPart)) { json.put(keyPart, new ArrayList<>()); } List<Object> list = (List<Object>) json.get(keyPart); while (list.size() <= index) { list.add(new HashMap<>()); } if (i == keys.length - 1) { list.set(index, value); } else { json = (Map<String, Object>) list.get(index); } } else { if (i == keys.length - 1) { json.put(key, value); } else { if (!json.containsKey(key)) { json.put(key, new HashMap<>()); } json = (Map<String, Object>) json.get(key); } } } } public Map<String, Object> createFromPath(String jsonPath) { Map<String, Object> json = new HashMap<>(); String[] paths = jsonPath.split(","); for (String path : paths) { String[] parts = path.split("="); String keyPath = parts[0].trim(); String value = parts[1].trim(); setValue(json, keyPath, value); } return json; } } ``` </details> <details class="orange"> <summary> **کد C#** </summary> ```CSharp public class JsonObjectCreator { private void SetValue(Dictionary<string, object> json, string path, string value) { var keys = path.Split('.'); for (var i = 0; i < keys.Length; i++) { var key = keys[i]; if (key.Contains('[') && key.Contains(']')) { var keyPart = key.Substring(0, key.IndexOf('[')); var index = int.Parse(key.Substring(key.IndexOf('[') + 1, key.IndexOf(']') - key.IndexOf('[') - 1)); if (!json.ContainsKey(keyPart)) { json[keyPart] = new List<object>(); } var list = (List<object>)json[keyPart]; while (list.Count <= index) { list.Add(new Dictionary<string, object>()); } if (i == keys.Length - 1) { list[index] = value; } else { json = (Dictionary<string, object>)list[index]; } } else { if (i == keys.Length - 1) { json[key] = value; } else { if (!json.ContainsKey(key)) { json[key] = new Dictionary<string, object>(); } json = (Dictionary<string, object>)json[key]; } } } } public Dictionary<string, object> CreateFromPath(string jsonPath) { var json = new Dictionary<string, object>(); var paths = jsonPath.Split(','); foreach (var path in paths) { var parts = path.Split('='); var keyPath = parts[0]; var value = parts[1]; SetValue(json, keyPath, value); } return json; } } ``` </details> <details class="orange"> <summary> **کد C++** </summary> ```CPP #include <iostream> #include <unordered_map> #include <vector> #include <string> #include <sstream> #include <any> using namespace std; class JsonObjectCreator { private: void SetValue(unordered_map<string, any> &json, const string &path, const string &value) { vector<string> keys; stringstream ss(path); string key; while (getline(ss, key, '.')) { keys.push_back(key); } unordered_map<string, any> *currentJson = &json; for (size_t i = 0; i < keys.size(); i++) { const string &key = keys[i]; if (key.find('[') != string::npos && key.find(']') != string::npos) { string keyPart = key.substr(0, key.find('[')); int index = stoi(key.substr(key.find('[') + 1, key.find(']') - key.find('[') - 1)); if (currentJson->find(keyPart) == currentJson->end()) { (*currentJson)[keyPart] = vector<any>(); } vector<any> &list = any_cast<vector<any> &>((*currentJson)[keyPart]); while (list.size() <= index) { list.push_back(unordered_map<string, any>()); } if (i == keys.size() - 1) { list[index] = value; } else { currentJson = &any_cast<unordered_map<string, any> &>(list[index]); } } else { if (i == keys.size() - 1) { (*currentJson)[key] = value; } else { if (currentJson->find(key) == currentJson->end()) { (*currentJson)[key] = unordered_map<string, any>(); } currentJson = &any_cast<unordered_map<string, any> &>((*currentJson)[key]); } } } } public: unordered_map<string, any> CreateFromPath(const string &jsonPath) { unordered_map<string, any> json; vector<string> paths; stringstream ss(jsonPath); string path; while (getline(ss, path, ',')) { paths.push_back(path); } for (const auto &path: paths) { vector<string> parts; stringstream pathSS(path); string part; while (getline(pathSS, part, '=')) { parts.push_back(part); } string keyPath = parts[0]; string value = parts[1]; SetValue(json, keyPath, value); } return json; } }; ``` </details> </details> # خروجی در خروجی به ازای هر کوئری، شماره اسنادی که بازیابی می‌شوند را به ترتیب شماره اسناد از کوچک به بزرگ با فاصله در یک خط چاپ کنید. در صورتی که هیچ سندی در نتیجه اجرای کوئری پیدا نشد، عبارت `NO RESULT` را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 The solution is simple. Another mystery solved. The mystery deepened with every clue. 3 match=mystery any[0]=mystery,any[1]=solution all[0]=mystery,all[1]=clue ``` ## خروجی نمونه ۱ ``` 2 3 1 2 3 3 ``` <details class="yellow"> <summary> **توضیحات نمونه ۱** </summary> ---------- پس از مرحله پیش‌پردازش، اسناد به صورت زیر خواهند بود: ``` Document 1: solution simple Document 2: another mystery solved Document 3: mystery deepened every clue ``` همچنین کوئری‌ها پس از تبدیل به شکل زیر خواهند بود: ``` {"match": "mystery"} {"any": ["mystery", "solution"]} {"all": ["mystery", "clue"]} ``` + در کوئری اول، به دنبال اسنادی هستیم که عبارت `mystery` در آن‌ها وجود دارد. این عبارت تنها در اسناد 2 و 3 آمده است. + در کوئری دوم، اسنادی را می‌خواهیم بازیابی کنیم که حداقل یکی از عبارات `mystery` یا `solution` در آن اسناد آمده است. عبارت `mystery` در سند 2 و 3 و عبارت `solution` در سند 1 آمده است. + در کوئری سوم، دنبال اسنادی می‌گردیم که هر دو عبارت `mystery` و `clue` در آن اسناد آمده باشد. سند 3 هردوی این عبارات را دارا است. </details> ## ورودی نمونه ۲ ``` 8 Watson: "Holmes, are you sure?" Holmes: "Quite certain, Watson." Holmes: "Observe, Watson, and learn." Watson: "I'm always learning, Holmes." Watson: "Holmes, you’re brilliant!" Holmes: "I have my moments." Holmes: "The truth is stranger than fiction." Watson: "And you prove it daily." 5 or[0].match=watson,or[1].match=holmes or[0].match=watson,or[1].match=holmes,size=6 and[0].any[0]=watson,and[0].any[1]=holmes,and[1].match=learn and[0].all[0]=watson,and[0].all[1]=holmes,and[1].match=learning not.match=watson ``` ## خروجی نمونه ۲ ``` 1 2 3 4 5 6 7 8 1 2 3 4 5 6 3 4 6 7 ``` <details class="yellow"> <summary> **توضیحات نمونه ۲** </summary> ---------- پس از مرحله پیش‌پردازش، اسناد به صورت زیر خواهند بود: ``` Document 1: watson holmes you sure Document 2: holmes quite certain watson Document 3: holmes observe watson learn Document 4: watson im always learning holmes Document 5: watson holmes youre brilliant Document 6: holmes i have my moments Document 7: holmes truth stranger than fiction Document 8: watson you prove daily ``` همچنین کوئری‌ها پس از تبدیل به شکل زیر خواهند بود: ``` {"or": [{"match": "watson"}, {"match": "holmes"}]} {"or": [{"match": "watson"}, {"match": "holmes"}], "size": 6} {"and": [{"any": ["watson", "holmes"]}, {"match": "learn"}]} {"and": [{"all": ["watson", "holmes"]}, {"match": "learning"}]} {"not": {"match": "watson"}} ``` + در کوئری اول، اسنادی را می‌خواهیم بازیابی کنیم که حداقل یکی از عبارات `watson` یا `holmes` در آن اسناد آمده است. عبارت `watson` در همه اسناد به جز اسناد 6 و 7 آمده است. از طرفی عبارت `holmes` در سند 6 و 7 هم دیده می‌شود. بنابراین همه اسناد بازیابی می‌شوند. + کوئری دوم همانند کوئری اول است با این تفاوت که `size` برابر 6 است. بنابراین تنها 6 سند اول بازیابی می‌شوند. + در کوئری سوم، دنبال اسنادی می‌گردیم که حتما عبارت `learn` در آن اسناد وجود داشته باشد، به علاوه اینکه حداقل یکی از عبارات `watson` یا `holmes` هم وجود داشته باشد. عبارت `watson` و `holmes` در کنار عبارت `learn` تنها در سند 3 آمده‌اند. </details> ## ورودی نمونه ۳ ``` 3 Crime is common, logic is rare. The little things are infinitely the most important. The world is full of obvious things which nobody by any chance ever observes. 5 match=little things match=common logic rare match=common rare any[0]=little things,any[1]=obvious things,any[2]=common logic all[0]=things ``` ## خروجی نمونه ۳ ``` 2 1 NO RESULT 1 2 3 2 3 ``` <details class="yellow"> <summary> **توضیحات نمونه ۳** </summary> ---------- پس از مرحله پیش‌پردازش، اسناد به صورت زیر خواهند بود: ``` Document 1: crime common logic rare Document 2: little things infinitely most important Document 3: world full obvious things which nobody any chance ever observes ``` همچنین کوئری‌ها پس از تبدیل به شکل زیر خواهند بود: ``` {"match": "little things"} {"match": "common logic rare"} {"match": "common rare"} {"any": ["little things", "obvious things", "common logic"]} {"all": ["things"]} ``` + در کوئری اول، به دنبال اسنادی هستیم که عبارت `little things` در آن‌ها وجود دارد. کلمات `little` و `things` تنها در سند 2 پشت سر هم دیده می‌شوند. + کوئری دوم نیز مشابه کوئری اول است، با این تفاوت که به دنبال 3 کلمه پشت سر هم هستیم. + در کوئری سوم، عبارت `common rare` در هیچ سندی دیده نمی‌شود. </details> ## ورودی نمونه ۴ ``` 10 You see, but you do not observe. Crime is common, logic is rare. There is nothing more deceptive than an obvious fact. The world is full of obvious things which nobody by any chance ever observes. Data, data, data! I can't make bricks without clay. It's a capital mistake to theorize before one has data. I am lost without my Boswell. Eliminate all other factors, and the one which remains must be the truth. The truth is what I pursue. London, at its best, is a labyrinth of intrigue and danger. 1 or[0].all[0]=london,or[0].all[1]=intrigue,or[0].all[2]=thing,or[1].any[0]=psychopath,or[1].any[1]=labyrinth,or[1].any[2]=data,or[1].any[3]=common logic rare,or[2].match=observe,or[3].and[0].match=obvious,or[3].and[1].or[0].not.any[0]=deceptive,or[3].and[1].or[0].not.any[1]=truth,size=3 ``` ## خروجی نمونه ۴ ``` 1 2 4 ```

حل سؤال در بانک سؤالات