سؤال مصاحبه

یک merge که باعث اشتراک نماد بین دو تطابق می‌شود

A merge that lets two matches share a symbol

  • سطح ۲: میانی
  • کدخوانی
  • ۸ دقیقه

این تابع، کلمه‌ای را پس از انتخاب یک merge در الگوریتم BPE بازنویسی می‌کند. روی کلمه‌ی (7, 7, 7) با جفت (7, 7) خروجی (300, 300, 7) را برمی‌گرداند. باگ را پیدا کنید و خروجی درست را بنویسید.

def apply_merge(symbols, pair, new_id):
    out = []
    i = 0
    while i < len(symbols):
        if i + 1 < len(symbols) and symbols[i] == pair[0] and symbols[i + 1] == pair[1]:
            out.append(new_id)
            i += 1
        else:
            out.append(symbols[i])
            i += 1
    return tuple(out)

اول خودتان جواب بدهید، بعد پاسخ را باز کنید.

پاسخ کوتاه

پس از پیدا شدن تطابق، پیمایش به‌جای 2 موقعیت، فقط 1 موقعیت جلو می‌رود؛ بنابراین، نماد دومِ تطابق دوباره خوانده می‌شود: یا نقطهٔ شروع تطابق بعدی قرار می‌گیرد یا در خروجی کپی می‌شود. تطابق‌ها نباید نماد مشترک داشته باشند. خروجی درست (300, 7) است: دو تا 7 اول به یک شناسه (id) جدید تبدیل می‌شوند و 7 سوم باقی می‌ماند.

پاسخ کامل

عملکرد باگ

وقتی پس از هر تطابق گام پیمایش 1 باشد، پیمایشْ جفت را در موقعیت‌های 0 و 1 می‌بیند، شناسه‌ی جدید را ثبت می‌کند و سپس به سراغ موقعیت‌های 1 و 2 می‌رود که آن‌ها هم با جفت تطابق دارند. کلمه صاحب نمادی می‌شود که قبلاً هرگز نداشته است؛ بنابراین پیکره متنی (Corpus) ادغام‌شده خراب می‌شود و هر گام بعدی، جفت‌ها را روی کلمات آسیب‌دیده می‌شمارد. کدگذاری در زمان استنتاج (inference) هم از همین تابع استفاده می‌کند، در نتیجه هر متنی با نماد تکراری به بایت‌هایی متفاوت با ورودی اصلی رمزگشایی (decode) می‌شود.

اصلاح باگ

        if i + 1 < len(symbols) and symbols[i] == pair[0] and symbols[i + 1] == pair[1]:
            out.append(new_id)
            i += 2

پیمایش را از چپ به راست انجام دهید و بعد از نماد دومِ تطابق به مسیر ادامه دهید. حلقه‌ی merge در فصل توکنایزرها دقیقاً همین کار را می‌کند و در وظیفه (Task) تمرینی هم یک جهش‌یافته (mutant) برای گام تک‌تایی وجود دارد که روی [a, a, a] شکست می‌خورد.

اهمیت قاعده‌ی چپ‌به‌راست

جایگزینی بدون همپوشانی (Overlap) از سمت چپ یک قرارداد است و حلقه‌ی آموزش و کدگذار باید هر دو از آن پیروی کنند. اگر آموزش از چپ merge کند و کدگذار از راست، همان کلمه در آموزش و در استنتاج شناسه‌های متفاوتی می‌گیرد. جدول ادغام (merge table) تنها زمانی درست کار می‌کند که هر دو طرف آن را دقیقاً به یک شکل اعمال کنند.

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

سؤال‌های تکمیلی مصاحبه‌گر
  • سطح 2: همین باگ چه بلایی بر سر شمارش جفت‌ها در گام بعدی آموزش می‌آورد؟ انتظار می‌رود: جفت‌هایی را می‌شمارد که در پیکره متنی واقعی وجود ندارند، بنابراین mergeهای بعدی بر اساس اعداد اشتباه انتخاب می‌شوند.
  • سطح 2: ورودی‌ای مثال بزنید که باگ روی آن خروجی درست تولید کند. انتظار می‌رود: فقط کلمه‌ای که هیچ تطابقی با جفت داده‌شده ندارد، مثل (7, 8, 7) با جفت (7, 7)؛ هر تطابقی یک کپی اضافی از نماد دومش به جا می‌گذارد.
  • سطح 3: یک آزمون بازگشت‌پذیری (Round-trip) چطور این باگ را کشف می‌کند؟ انتظار می‌رود: رشته‌ای با بایت تکراری را کدگذاری، شناسه‌ها را رمزگشایی، و بایت‌ها را مقایسه کنید؛ نماد ادغام‌شده‌ی اضافی به بایت‌های بیشتری نسبت به ورودی اولیه باز می‌شود.
جواب‌های اشتباهی که مصاحبه‌گرها زیاد می‌شنوند
  • «جایگزینی جفت با متدهای رشته‌ای روی نمادهای به‌هم‌پیوسته.» شناسه‌ها عدد صحیح هستند نه کاراکتر، و چسباندن آن‌ها مرز بین شناسه‌ها را پنهان می‌کند.
  • «تطابق را به‌جای چپ، از راست انجام دهیم.» هر کدام از این جهت‌ها به‌تنهایی کار می‌کنند، اما آموزش و استنتاج باید از یک جهت یکسان استفاده کنند؛ قرارداد رایج، چپ به راست است.
  • «برای سرعت بیشتر، به‌جای تاپل یک لیست برگردانیم.» کلمات، کلیدهای دیکشنری هستند و حتماً باید هش‌پذیر (hashable) بمانند.

کجای دوره آموزش داده می‌شود

درس توکنایزرها حلقه‌ی merge را با گام 2موقعیتی می‌نویسد، درس پیاده‌سازی BPE از صفر قرارداد ادغام (Merge Contract) مشترک را شرح می‌دهد و تمرین BPE حالت همپوشانی را می‌سنجد.