+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
+ **زبان‌های مجاز: `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
```
معمای مرموز
- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
- زبان‌های مجاز:
Java, C#, C++
در خانه‌ی مشهور شماره ۲۲۱ بیکر استریت، جاناتان کولمز، یک برنامه‌نویس با استعداد و دستیار وفادارش دکتر واتسون، به دنبال حل یک معمای جدید هستند. یک روز وقتی که جاناتان به دفترچه‌ی پوشه‌دار خود مراجعه می‌کند، با اسنادی مرموز و عجیب مواجه می‌شود.
این اسناد به زبان انگلیسی نوشته شده‌اند و به نظر می‌رسد برای نظریه‌پردازی درباره‌ی یک پرونده‌ی مخفی تهیه شده‌اند. جاناتان و دکتر واتسون، با تصمیم به حل این معما، به ساختن ابزاری سریع و قدرتمند می‌پردازند که به آنها کمک می‌کند تا اطلاعات مورد نیاز خود را از متون مرموز استخراج کرده و معمایی که پیش رویشان قرار دارد را حل نمایند.
گام اول: پیش‌پردازش اسناد🔗
اولین گام، پیش‌پردازش متون اسناد است. این پیاده‌سازی باید شامل موارد زیر باشد:
تبدیل متن به حروف کوچک
برای جلوگیری از مشکلات مربوط به حساسیت به بزرگی و کوچکی حروف، همه حروف موجود در متن باید به حروف کوچک تبدیل شوند.
برای مثال متن سند پیش از پردازش:
پس از این پردازش به متن زیر تبدیل خواهد شد:
پاکسازی متن
هرگونه کاراکتر غیر از حروف انگلیسی و اعداد که برای جستجوی متنی اهمیتی ندارند، باید حذف شوند.
برای مثال متن سند پیش از پردازش:
پس از این پردازش به متن زیر تبدیل خواهد شد:
حذف کلمات توقفی
کلمات توقفی شامل موارد زیر هستند که در جستجوها نادیده گرفته می‌شوند و باید از متن حذف شوند:
برای مثال متن پیش از پردازش:
پس از این پردازش به متن زیر تبدیل خواهد شد:
حذف فاصله‌های اضافی
نیاز است هرگونه فاصله اضافی بین کلمات حذف شود.
برای مثال متن پیش از پردازش:
پس از این پردازش به متن زیر تبدیل خواهد شد:
گام دوم: طراحی Inverted Index🔗
ساختار داده Inverted Index، ساختاری است که امکان نگهداری اطلاعات برای جستجوی سریع متنی را فراهم می‌کند. در ادامه با این ساختار داده بیشتر آشنا می‌شوید.
ایجاد لیست کلمات
در این مرحله، باید تمامی کلمات موجود در هر سند را شناسایی کرده و لیستی از این کلمات ایجاد کنیم. این لیست، پایه‌ای برای ساخت Inverted Index است.
برای مثال در سند زیر:
لیست کلمات به این شکل خواهد بود:
ایجاد Inverted Index
در این مرحله، یک دیکشنری ایجاد می‌شود که کلیدهای آن کلمات موجود در لیست کلمات هستند و مقادیر آنها لیستی از شماره اسنادی است که هر کلمه در آنها ظاهر شده است.
برای مثال دو سند پیش‌پردازش شده زیر را در نظر بگیرید:
بنابراین Inverted Index به این شکل خواهد بود:
همانطور که می‌بینید، کلمه halis هم در سند 1 و هم در سند 2 وجود دارد؛ در حالی که کلمه please تنها در سند 1 و کلمه code تنها در سند 2 وجود دارند.
نکته مهم: Inverted Index از روی اسناد پیش‌پردازش شده ایجاد می‌شود.
بازیابی اسناد
اکنون می‌توانیم به کمک ساختار داده ایجاد شده، اسناد دلخواه را بازیابی کنیم.
برای مثال Inverted Index زیر را درنظر بگیرید:
می‌خواهیم بدانیم کلمات halis و watson همزمان در چه اسنادی آمده‌است. برای این منظور، کافی است اشتراک شماره اسناد برای این دو کلمه را بررسی کنیم:
همانطور که می‌بینید، می‌توان نتیجه گرفت کلمات halis و watson همزمان در سند 1 آمده اند.
گام سوم: جستجوی متنی🔗
در این گام، کوئری‌هایی طراحی می‌شوند که به کمک آنها می‌توان جستجوی متنی پیشرفته انجام داد و شماره اسناد مربوطه را بازیابی کرد. ساختار این کوئری‌ها با فرمت JSON است که در ادامه معرفی خواهند شد.
کوئری‌های فرزند🔗
کوئری match
با استفاده از این کوئری، اسنادی که شامل یک عبارت مشخص هستند، بازیابی می‌شوند.
در مثال بالا، اسنادی که شامل عبارت john watson هستند بازیابی می‌شوند؛ یعنی این دو کلمه پشت سر هم در متن پیش پردازش شده سند وجود داشته باشد.
کوئری all
با استفاده از این کوئری، اسنادی که شامل تمام عبارات هستند، بازیابی می‌شوند.
در مثال بالا، اسنادی که شامل هر دو عبارت moriarty و john watson هستند بازیابی می‌شوند.
کوئری any
با استفاده از این کوئری، اسنادی که شامل حداقل یکی از عبارات هستند، بازیابی می‌شوند.
در مثال بالا، اسنادی که شامل حداقل یکی از عبارت‌های moriarty یا john watson باشند بازیابی می‌شوند.
توجه: منظور از عبارت، یک یا چند کلمه با حروف کوچک است که با فاصله از هم جدا شده‌اند.
کوئری‌های والد🔗
کوئری and
با استفاده از این کوئری، اسنادی بازیابی می‌شوند که با تمام از کوئری‌های فرزند به طور همزمان مطابقت دارند.
در مثال بالا، اسنادی بازیابی می‌شوند که شامل هر سه کلمه‌ی rainy ، sherlock و death باشند.
یک نمونه کوئری دیگر شامل and:
کوئری or
با استفاده از این کوئری، اسنادی بازیابی می‌شوند که با حداقل یکی از کوئری‌های فرزند مطابقت داشته باشد.
در مثال بالا، اسنادی بازیابی می‌شوند که یا شامل عبارت rainy night باشند، یا اینکه همه عبارات sherlock holmes، dr john watson و moriarty در آن اسناد آمده باشد، و یا اینکه حداقل یکی از کلمات death یا boold در آن اسناد آمده باشد.
کوئری not
با استفاده از این کوئری، تمام اسنادی که با کوئری فرزند مطابقت نداشته باشند بازیابی می‌شوند.
در مثال بالا، اسنادی بازیابی می‌شوند که هر دو عبارت knife و gun همزمان در آن اسناد نیامده باشد.
نکات تکمیلی (مهم)🔗
نکته اول
کوئری‌های والد، خود نیز می‌توانند فرزند کوئری والد دیگری باشند.
نکته دوم
در ریشه کوئری، ممکن است متغیر size بیاید که نشان دهنده حداکثر تعداد اسنادی است که باید بازیابی شوند. درصورتی که اندازه مشخص نشده بود، همه نتایج بازیابی می‌شوند.
جمع‌بندی🔗
هدف این است که ابزاری ساخته شود تا متون اسناد را پیش پردازش کرده، سپس ساختار داده Inverted Index ایجاد شود. در نهایت به کمک این ساختار داده جهت افزایش سرعت جستجو، کوئری‌هایی با هدف بازیابی اسناد مختلف، پردازش شوند.
توجه: لازم است اصول برنامه نویسی شیءگرا، کد تمیز و اصول SOLID تا حد ممکن در نظر گرفته شود.
توجه: امکان پیاده‌سازی بخشی از سوال و کسب نمره آن بخش از سوال وجود دارد.
توجه: تنها یک فایل شامل کدهای نوشته شده آپلود کنید.
ورودی🔗
ورودی شامل n+q+2 خط است. در خط اول، n تعداد سندها، داده می‌شود. در n خط بعدی، در هر خط متن سند iام داده می‌شود. سپس، عدد q (تعداد کوئری‌ها) آمده است. در q خط بعدی، در هر خط یک کوئری با فرمت JSONPath می‌آید.
1≤n≤150
1≤q≤1500
راهنمایی: برای تبدیل کوئری از فرمت JSONPath به فرمت JSON، می‌توانید از این کدها استفاده نمایید.
کد Java
کد C#
کد C++
خروجی🔗
در خروجی به ازای هر کوئری، شماره اسنادی که بازیابی می‌شوند را به ترتیب شماره اسناد از کوچک به بزرگ با فاصله در یک خط چاپ کنید.
در صورتی که هیچ سندی در نتیجه اجرای کوئری پیدا نشد، عبارت NO RESULT را چاپ کنید.
مثال🔗
ورودی نمونه ۱🔗
خروجی نمونه ۱🔗
توضیحات نمونه ۱
پس از مرحله پیش‌پردازش، اسناد به صورت زیر خواهند بود:
همچنین کوئری‌ها پس از تبدیل به شکل زیر خواهند بود:
- در کوئری اول، به دنبال اسنادی هستیم که عبارت
mystery در آنها وجود دارد. این عبارت تنها در اسناد 2 و 3 آمده است.
- در کوئری دوم، اسنادی را می‌خواهیم بازیابی کنیم که حداقل یکی از عبارات
mystery یا solution در آن اسناد آمده است. عبارت mystery در سند 2 و 3 و عبارت solution در سند 1 آمده است.
- در کوئری سوم، دنبال اسنادی می‌گردیم که هر دو عبارت
mystery و clue در آن اسناد آمده باشد. سند 3 هردوی این عبارات را دارا است.
ورودی نمونه ۲🔗
خروجی نمونه ۲🔗
توضیحات نمونه ۲
پس از مرحله پیش‌پردازش، اسناد به صورت زیر خواهند بود:
همچنین کوئری‌ها پس از تبدیل به شکل زیر خواهند بود:
- در کوئری اول، اسنادی را می‌خواهیم بازیابی کنیم که حداقل یکی از عبارات
watson یا holmes در آن اسناد آمده است. عبارت watson در همه اسناد به جز اسناد 6 و 7 آمده است. از طرفی عبارت holmes در سند 6 و 7 هم دیده می‌شود. بنابراین همه اسناد بازیابی می‌شوند.
- کوئری دوم همانند کوئری اول است با این تفاوت که
size برابر 6 است. بنابراین تنها 6 سند اول بازیابی می‌شوند.
- در کوئری سوم، دنبال اسنادی می‌گردیم که حتما عبارت
learn در آن اسناد وجود داشته باشد، به علاوه اینکه حداقل یکی از عبارات watson یا holmes هم وجود داشته باشد. عبارت watson و holmes در کنار عبارت learn تنها در سند 3 آمده‌اند.
ورودی نمونه ۳🔗
خروجی نمونه ۳🔗
توضیحات نمونه ۳
پس از مرحله پیش‌پردازش، اسناد به صورت زیر خواهند بود:
همچنین کوئری‌ها پس از تبدیل به شکل زیر خواهند بود:
- در کوئری اول، به دنبال اسنادی هستیم که عبارت
little things در آنها وجود دارد. کلمات little و things تنها در سند 2 پشت سر هم دیده می‌شوند.
- کوئری دوم نیز مشابه کوئری اول است، با این تفاوت که به دنبال 3 کلمه پشت سر هم هستیم.
- در کوئری سوم، عبارت
common rare در هیچ سندی دیده نمی‌شود.
ورودی نمونه ۴🔗
خروجی نمونه ۴🔗
در این مثال، شرلوک در تلاش برای عبور از پنج ساختمان است و حداکثر مسافتی که شرلوک در یک ثانیه می‌تواند طی کند، برابر سه متر است. همانطور که در تصویر این مثال مشخص شده‌است، مقدار زمانی که نیاز است تا شرلوک تمام ساختمان‌ها را بپیماید، برابر تعداد بردار‌های قرمز در تصویر، یعنی ۱۵ ثانیه می‌شود.
اگر گراف را رسم کنیم، می‌بینیم که یک دور با رئوس ۱، ۲ و ۳ داریم و کوتاه‌ترین مسیر از رأسی که شرلوک روی آن قرار دارد (رأس ۵) به نزدیک‌ترین رأس دور (رأس ۳) مسیر زیر می‌باشد:
اگر گراف را رسم کنیم، می‌بینیم که یک دور با رئوس ۱، ۲و ۳ و یک دور با رئوس ۴، ۷ و ۸ داریم و کوتاه‌ترین مسیر از رأسی که شرلوک روی آن قرار دارد (رأس ۵) به نزدیک‌ترین رأس نزدیک‌ترین دور (رأس ۴) مسیر زیر می‌باشد: