محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

در خانه‌ی مشهور شماره ۲۲۱ بیکر استریت، جاناتان کولمز، یک برنامه‌نویس با استعداد و دستیار وفادارش دکتر واتسون، به دنبال حل یک معمای جدید هستند. یک روز وقتی که جاناتان به دفترچه‌ی پوشه‌دار خود مراجعه می‌کند، با اسنادی مرموز و عجیب مواجه می‌شود.

این اسناد به زبان انگلیسی نوشته شده‌اند و به نظر می‌رسد برای نظریه‌پردازی درباره‌ی یک پرونده‌ی مخفی تهیه شده‌اند. جاناتان و دکتر واتسون، با تصمیم به حل این معما، به ساختن ابزاری سریع و قدرتمند می‌پردازند که به آن‌ها کمک می‌کند تا اطلاعات مورد نیاز خود را از متون مرموز استخراج کرده و معمایی که پیش رویشان قرار دارد را حل نمایند.

گام اول: پیش‌پردازش اسناد

اولین گام، پیش‌پردازش متون اسناد است. این پیاده‌سازی باید شامل موارد زیر باشد:

تبدیل متن به حروف کوچک

برای جلوگیری از مشکلات مربوط به حساسیت به بزرگی و کوچکی حروف، همه حروف موجود در متن باید به حروف کوچک تبدیل شوند.

برای مثال متن سند پیش از پردازش:

Please HELP! Halis said.

پس از این پردازش به متن زیر تبدیل خواهد شد:

please help! halis said.

پاکسازی متن

هرگونه کاراکتر غیر از حروف انگلیسی و اعداد که برای جستجوی متنی اهمیتی ندارند، باید حذف شوند.

برای مثال متن سند پیش از پردازش:

please help! halis said.

پس از این پردازش به متن زیر تبدیل خواهد شد:

please help halis said

حذف کلمات توقفی

کلمات توقفی شامل موارد زیر هستند که در جستجوها نادیده گرفته می‌شوند و باید از متن حذف شوند:

"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

حذف فاصله‌های اضافی

نیاز است هرگونه فاصله اضافی بین کلمات حذف شود.

برای مثال متن پیش از پردازش:

please help	halis  said

پس از این پردازش به متن زیر تبدیل خواهد شد:

please help halis said

گام دوم: طراحی Inverted Index

ساختار داده Inverted Index، ساختاری است که امکان نگهداری اطلاعات برای جستجوی سریع متنی را فراهم می‌کند. در ادامه با این ساختار داده بیشتر آشنا می‌شوید.

ایجاد لیست کلمات

در این مرحله، باید تمامی کلمات موجود در هر سند را شناسایی کرده و لیستی از این کلمات ایجاد کنیم. این لیست، پایه‌ای برای ساخت Inverted Index است.

برای مثال در سند زیر:

"please help halis said"

لیست کلمات به این شکل خواهد بود:

["please", "help", "halis", "said"]

ایجاد Inverted Index

در این مرحله، یک دیکشنری ایجاد می‌شود که کلیدهای آن کلمات موجود در لیست کلمات هستند و مقادیر آن‌ها لیستی از شماره اسنادی است که هر کلمه در آن‌ها ظاهر شده است.

برای مثال دو سند پیش‌پردازش شده زیر را در نظر بگیرید:

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 وجود دارند.

نکته مهم: Inverted Index از روی اسناد پیش‌پردازش شده ایجاد می‌شود.

بازیابی اسناد

اکنون می‌توانیم به کمک ساختار داده ایجاد شده، اسناد دلخواه را بازیابی کنیم.

برای مثال 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 آمده اند.

گام سوم: جستجوی متنی

در این گام، کوئری‌هایی طراحی می‌شوند که به کمک آن‌ها می‌توان جستجوی متنی پیشرفته انجام داد و شماره اسناد مربوطه را بازیابی کرد. ساختار این کوئری‌ها با فرمت JSON است که در ادامه معرفی خواهند شد.

کوئری‌های فرزند

کوئری match

با استفاده از این کوئری، اسنادی که شامل یک عبارت مشخص هستند، بازیابی می‌شوند.

{
    "match": "john watson"
}

در مثال بالا، اسنادی که شامل عبارت john watson هستند بازیابی می‌شوند؛ یعنی این دو کلمه پشت سر هم در متن پیش پردازش شده سند وجود داشته باشد.

کوئری all

با استفاده از این کوئری، اسنادی که شامل تمام عبارات هستند، بازیابی می‌شوند.

{
    "all": ["john watson", "moriarty"]
}

در مثال بالا، اسنادی که شامل هر دو عبارت moriarty و john watson هستند بازیابی می‌شوند.

کوئری any

با استفاده از این کوئری، اسنادی که شامل حداقل یکی از عبارات هستند، بازیابی می‌شوند.

{
    "any": ["john watson", "moriarty"]
}

در مثال بالا، اسنادی که شامل حداقل یکی از عبارت‌های moriarty یا john watson باشند بازیابی می‌شوند.

توجه: منظور از عبارت، یک یا چند کلمه با حروف کوچک است که با فاصله از هم جدا شده‌اند.

کوئری‌های والد

کوئری and

با استفاده از این کوئری، اسنادی بازیابی می‌شوند که با تمام از کوئری‌های فرزند به طور همزمان مطابقت دارند.

{
    "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"]
                }
            ]
        }
    ]
}

کوئری or

با استفاده از این کوئری، اسنادی بازیابی می‌شوند که با حداقل یکی از کوئری‌های فرزند مطابقت داشته باشد.

{
    "or": [
        {
            "match": "rainy night"
        },
        {
            "all": ["sherlock holmes", "dr john watson", "moriarty"]
        },
        {
            "any": ["death", "blood"]
        }
    ]
}

در مثال بالا، اسنادی بازیابی می‌شوند که یا شامل عبارت rainy night باشند، یا اینکه همه عبارات sherlock holmes، dr john watson و moriarty در آن اسناد آمده باشد، و یا اینکه حداقل یکی از کلمات death یا boold در آن اسناد آمده باشد.

کوئری not

با استفاده از این کوئری، تمام اسنادی که با کوئری فرزند مطابقت نداشته باشند بازیابی می‌شوند.

{
    "not": {
        "and": [
            {
                "match": "knife"
            },
            {
                "match": "gun"
            }
        ]
    }
}

در مثال بالا، اسنادی بازیابی می‌شوند که هر دو عبارت knife و gun همزمان در آن اسناد نیامده باشد.

نکات تکمیلی (مهم)

نکته اول

کوئری‌های والد، خود نیز می‌توانند فرزند کوئری والد دیگری باشند.

{
    "and": [
        {
            "or": [...]
        },
        {
            "and": [...]
        },
        {
            "not": {...}
        }
    ]
}

نکته دوم

در ریشه کوئری، ممکن است متغیر size بیاید که نشان دهنده حداکثر تعداد اسنادی است که باید بازیابی شوند. درصورتی که اندازه مشخص نشده بود، همه نتایج بازیابی می‌شوند.

{
    "and": [...],
    "size": 10
}

جمع‌بندی

هدف این است که ابزاری ساخته شود تا متون اسناد را پیش پردازش کرده، سپس ساختار داده Inverted Index ایجاد شود. در نهایت به کمک این ساختار داده جهت افزایش سرعت جستجو، کوئری‌هایی با هدف بازیابی اسناد مختلف، پردازش شوند.

توجه: لازم است اصول برنامه نویسی شیءگرا، کد تمیز و اصول SOLID تا حد ممکن در نظر گرفته شود.

توجه: امکان پیاده‌سازی بخشی از سوال و کسب نمره آن بخش از سوال وجود دارد.

توجه: تنها یک فایل شامل کدهای نوشته شده آپلود کنید.

ورودی

ورودی شامل $n + q + 2$ خط است. در خط اول، $n$ تعداد سندها، داده می‌شود. در $n$ خط بعدی، در هر خط متن سند $i$ ام داده می‌شود. سپس، عدد $q$ (تعداد کوئری‌ها) آمده است. در $q$ خط بعدی، در هر خط یک کوئری با فرمت JSONPath می‌آید.

$1 \le n \le 150$ $1 \le q \le 1500$

راهنمایی: برای تبدیل کوئری از فرمت JSONPath به فرمت JSON، می‌توانید از این کدها استفاده نمایید.

کد 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;
    }
}

کد C#

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;
    }
}

کد C++

#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;
    }
};

خروجی

در خروجی به ازای هر کوئری، شماره اسنادی که بازیابی می‌شوند را به ترتیب شماره اسناد از کوچک به بزرگ با فاصله در یک خط چاپ کنید. در صورتی که هیچ سندی در نتیجه اجرای کوئری پیدا نشد، عبارت 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

توضیحات نمونه ۱

پس از مرحله پیش‌پردازش، اسناد به صورت زیر خواهند بود:

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 هردوی این عبارات را دارا است.

ورودی نمونه ۲

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

توضیحات نمونه ۲

پس از مرحله پیش‌پردازش، اسناد به صورت زیر خواهند بود:

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 آمده‌اند.

ورودی نمونه ۳

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

توضیحات نمونه ۳

پس از مرحله پیش‌پردازش، اسناد به صورت زیر خواهند بود:

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 در هیچ سندی دیده نمی‌شود.

ورودی نمونه ۴

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

ارسال پاسخ برای این سؤال