লেখক:
(1) ব্র্যান্ডন টি. উইলার্ড, নরমাল কম্পিউটিং;
(2) রেমি লাউফ, সাধারণ কম্পিউটিং।
আসুন St = (s1 ... st) st ∈ V, V a শব্দভাণ্ডার এবং |V| সহ t টোকেনের একটি ক্রম উপস্থাপন করুন = N. শব্দভান্ডার, V, একটি নির্দিষ্ট বর্ণমালা [Sennrich et al., 2015] থেকে স্ট্রিং দিয়ে গঠিত এবং N প্রায়ই 104 বা তার চেয়ে বড় হয়।
আমরা নিম্নলিখিত র্যান্ডম ভেরিয়েবল হিসাবে পরবর্তী টোকেন st+1 সংজ্ঞায়িত করি:
ধরুন F ⊂ P (V), যেখানে P হল পাওয়ারসেট অপারেটর, মাল্টি-টোকেন স্ট্রিংগুলির উপসেট যা একটি বিশেষ টোকেন EOS ∈ V দিয়ে শেষ হয়৷ পাঠ্য তৈরির কাজটি হল F থেকে নমুনা আঁকা৷
এফ-এর উপাদান তৈরি করার জন্য বেশ কিছু পদ্ধতি বিবেচনা করা হয়েছে। লোভী ডিকোডিং-এর মধ্যে রয়েছে পুনরাবৃত্তিমূলকভাবে টোকেন তৈরি করা, প্রতিটি ধাপে সর্বোচ্চ সম্ভাব্যতা সহ টোকেন বেছে নেওয়া। রশ্মি অনুসন্ধানও বিতরণের মোড খুঁজে পেতে হিউরিস্টিক ব্যবহার করে পুনরাবৃত্তিমূলকভাবে টোকেন তৈরি করে। অতি সম্প্রতি, SMC স্যাম্পলিংও সিকোয়েন্স তৈরি করতে ব্যবহার করা হয়েছে [Lew et al., 2023]।
নমুনা পদ্ধতিটি অ্যালগরিদম 1 দ্বারা সাধারণভাবে বর্ণনা করা হয়েছে। প্রায়শই বহুপদ স্যাম্পলিং বলা হয়, পদ্ধতিটি EOS টোকেন পাওয়া পর্যন্ত উপরে সংজ্ঞায়িত শ্রেণীবদ্ধ বন্টন থেকে স্যাম্পলিং করে নতুন টোকেন তৈরি করে।
• অঙ্কের নমুনা,
• রেগুলার এক্সপ্রেশনের সাথে মেলে এমন স্ট্রিংগুলি [a-zA-Z],
• এবং স্ট্রিং যা একটি নির্দিষ্ট ব্যাকরণ (যেমন পাইথন, SQL, ইত্যাদি) অনুযায়ী পার্স করে
মাস্কিং সহ নমুনা পদ্ধতি হল অ্যালগরিদম 1-এর একটি সাধারণ পরিবর্ধন এবং অ্যালগরিদম 2-এ দেওয়া আছে।
লাইন 2.5-এ m-এর গণনা সম্পূর্ণভাবে V-এর সমস্ত উপাদানের উপর সঞ্চালিত হয়। α কম্পিউটিং বাদে, এই ধাপটি সহজেই সবচেয়ে ব্যয়বহুল। রেগুলার এক্সপ্রেশন-গাইডেড মাস্কিং-এর ক্ষেত্রে-এবং এর চেয়ে বেশি পরিশীলিত ক্ষেত্রে-সাপোর্ট এবং, এইভাবে, m অগত্যা পূর্বে স্যাম্পল করা টোকেনের উপর নির্ভর করবে। এই ধরণের গাইডেড জেনারেশন শেষ পর্যন্ত একটি পুনরাবৃত্তিমূলক ম্যাচিং বা পার্সিং সমস্যা এবং এটি সরাসরি স্ট্যান্ডার্ড পদ্ধতির জন্য উপযুক্ত নয় যার জন্য সম্পূর্ণ স্ট্রিং আগাম অ্যাক্সেসের প্রয়োজন। কিছু ক্ষেত্রে, আংশিক মিল বা পার্সিং প্রতিটি পুনরাবৃত্তির নমুনা ক্রম শুরু থেকে সঞ্চালিত হতে পারে, তবে এটির একটি খরচ রয়েছে যা সমগ্র শব্দভাণ্ডার জুড়ে এর প্রয়োগের O(N) খরচের পাশাপাশি রৈখিকভাবে বৃদ্ধি পায়।
এটি আমাদের এই কাজের মূল প্রশ্নগুলির দিকে নিয়ে যায়: কীভাবে আমরা নিয়মিত এক্সপ্রেশন বা CFG অনুসারে অসম্পূর্ণ স্ট্রিংগুলিকে দক্ষতার সাথে মেলাতে বা পার্স করতে পারি এবং অ্যালগরিদম 2 এর প্রতিটি পুনরাবৃত্তিতে মাস্ক m নির্ধারণ করতে পারি?
এই কাগজটি CC 4.0 লাইসেন্সের অধীনে arxiv-এ উপলব্ধ ।