सभी चुनौतियाँ
मध्यम 0 हल किए गए 0% स्वीकृति

बाइट पेयर एन्कोडिंग (BPE) मर्ज

GPT टोकनाइज़र की तरह सबवर्ड मर्ज सीखें: पड़ोसी प्रतीकों की सबसे आम जोड़ी को बार-बार मिलाएँ।

आप क्या सीखेंगे

  • पास-पास के प्रतीकों के जोड़े गिनना
  • सबसे आम जोड़ी को बार-बार मिलाना
  • समझना कि GPT जैसे टोकनाइज़र कैसे बनते हैं

समस्या

GPT जैसे टोकनाइज़र बाइट पेयर एन्कोडिंग का उपयोग करते हैं: अलग-अलग अक्षरों से शुरू करें और पड़ोसियों की सबसे आम जोड़ी को बार-बार एक नए प्रतीक में मिलाएँ।

  1. words के हर शब्द को अक्षरों में बाँटें। दोहराए गए शब्द कई बार गिने जाते हैं।
  2. सभी शब्दों में पड़ोसी प्रतीकों की हर जोड़ी गिनें।
  3. सबसे आम जोड़ी चुनें। बराबरी होने पर (पहला प्रतीक, दूसरा प्रतीक) को स्ट्रिंग की तरह तुलना करके सबसे छोटी जोड़ी चुनें।
  4. उस जोड़ी की हर उपस्थिति को, बाएँ से दाएँ, मिले हुए प्रतीक से बदलें और मिले हुए प्रतीक को दर्ज करें।
  5. यह num_merges बार दोहराएँ, या पहले रुक जाएँ अगर किसी शब्द में दो प्रतीक न बचें।

bpe_merges(words, num_merges) लागू करें।

इनपुट

words: ट्रेनिंग शब्द (छोटे अक्षर)।

num_merges: कितने मर्ज सीखने हैं।

आउटपुट

मिले हुए प्रतीकों को उसी क्रम में लौटाएँ जिसमें वे सीखे गए।

सीमाएँ

1 ≤ शब्दों की संख्या ≤ 1,000, 1 ≤ हर शब्द की लंबाई ≤ 30

0 ≤ num_merges ≤ 200

उदाहरण

उदाहरण 1
इनपुट:
words = ["low", "lower", "lowest"]
num_merges = 2

अपेक्षित आउटपुट:
expected = ["lo", "low"]
इनपुट:
std::vector<std::string> words = {"low", "lower", "lowest"};
long long num_merges = 2;

अपेक्षित आउटपुट:
std::vector<std::string> expected = {"lo", "low"};
इनपुट:
string[] words = new string[] {"low", "lower", "lowest"};
long num_merges = 2;

अपेक्षित आउटपुट:
string[] expected = new string[] {"lo", "low"};

व्याख्या

जोड़ियाँ: "l o" और "o w" दोनों 3-3 बार आती हैं; बराबरी में "l o" जीतती है ("l" < "o"), जिससे "lo" बनता है। फिर "lo w" 3 बार आती है और "low" बनता है। परिणाम: ["lo", "low"]।

उदाहरण 2
इनपुट:
words = ["aaa"]
num_merges = 3

अपेक्षित आउटपुट:
expected = ["aa", "aaa"]
इनपुट:
std::vector<std::string> words = {"aaa"};
long long num_merges = 3;

अपेक्षित आउटपुट:
std::vector<std::string> expected = {"aa", "aaa"};
इनपुट:
string[] words = new string[] {"aaa"};
long num_merges = 3;

अपेक्षित आउटपुट:
string[] expected = new string[] {"aa", "aaa"};

व्याख्या

"aaa" में जोड़ी "a a" दो बार है। बाएँ से दाएँ मिलाने पर "aa" + "a" मिलता है। फिर "aa a" मिलकर "aaa" बनता है और शब्द में एक ही प्रतीक बचता है, इसलिए तीसरे मर्ज के लिए कुछ नहीं बचता। परिणाम: ["aa", "aaa"]।

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

हर word के लिए current symbol sequence track करें और repeated words के across neighboring pairs को बार-बार count करें.

संकेत 2

Pair counting के साथ deterministic tie-breaking use करें, pair को दो strings की तरह compare करके, और फिर हर word को left to right update करें.

संकेत 3

ऐसे words पर ध्यान दें जो one symbol तक shrink हो जाते हैं; जब कहीं भी कोई adjacent pair नहीं बचता, तो merges बाकी होने पर भी stop करें.

अपेक्षित जटिलता

समय O(num_merges * total_symbols), अतिरिक्त स्थान O(total_symbols)

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।