کدگذاری جفت بایت

**کدگذاری جفت بایتی** (به اختصار ) که با **digram coding** نیز شناخته می‌شود الگوریتمی است که نخستین بار در سال ۱۹۹۴ توسط فیلیپ گیج توصیف شد و برای کدگذاری رشته‌های متنی به منظور فشرده‌سازی و تبدیل آنها به رشته‌های کوتاه‌تر از طریق ایجاد و استفاده از یک جدول ترجمه به کار می‌رود. نسخه‌ای از این الگوریتم با کمی تغییرات، در توکن‌سازهای مدل‌های زبانی بزرگ مورد استفاده قرار می‌گیرد.

نسخه اصلی این الگوریتم بر فشرده‌سازی تمرکز داشت. این روش، زوج بایت‌های با بیشترین تکرار را با یک بایت جدید که در مجموعه داده اولیه وجود ندارد جایگزین می‌کند. برای بازسازی مجموعه داده اولیه، داشتن یک جدول مراجعه و جستجو از جایگزینی‌ها ضروری است. نسخه اصلاح‌شده این الگوریتم «توکن»‌هایی (واحدهای شناسایی) را می‌سازد که می‌توانند مقادیر متفاوتی از متن منبع را پوشش دهند، که شامل نویسه‌های منفرد (از جمله تک‌رقم یا نشانه‌های نگارشی تکی) یا حتی کلمات کامل (حتی واژه‌های مرکب طولانی) می‌شود.
## الگوریتم اصلی
الگوریتم اصلی BPE با جایگزین کردن مداوم متداول‌ترین توالی‌های پیوسته از کاراکترها در متن اصلی، با بایت‌های «جایگزین» استفاده‌نشده (در متن اولیه) عمل می‌کند. این تکرار زمانی پایان می‌یابد که دیگر توالی‌ای یافت نشود و متن هدف عملاً فشرده می‌ماند. از طریق وارون کردن این فرایند می‌توان متن را از حالت فشرده خارج کرد. به این صورت که با استفاده از یک جدول مراجعه و جستجو، اصطلاحات جایگزین شناخته‌شده به توالی اصلی مربوطه بازگردانده شوند. در مقاله اصلی، این جدول همراه با متن فشرده‌شده کدگذاری و ذخیره می‌شود.
### مثال
فرض کنید داده‌ای که باید کدگذاری شود به صورت زیر باشد

 aaabdaaabac

زوج بایت «aa» بیشترین تکرار را دارد و بنابراین با بایتی که در داده اصلی وجود ندارد، مانند «Z» جایگزین می‌شود. اکنون داده و جدول جایگزینی به صورت زیر است:
 ZabdZabac
 Z=aa
سپس این فرایند با زوج بایت «ab» تکرار می‌شود و آن را با «Y» جایگزین می‌کند:
 ZYdZYac
 Y=ab
 Z=aa
تنها زوج بایتی که باقی مانده فقط یک بار تکرار شده، و در این مرحله ممکن است الگوریتم متوقف شود. یا این که فرایند می‌تواند بازگشتی شده و ادامه یابد و «ZY» را با «X» جایگزین کند:
 XdXac
 X=ZY
 Y=ab
 Z=aa
در این مرحله دیگر هیچ زوج بایتی که بیش از یک بار رخ دهد، وجود ندارد و بنابراین داده بیشتر از این با کدگذاری زوج-بایتی فشرده نمی‌شود.

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

## الگوریتم تصحیح‌شده
الگوریتم اصلی BPE برای استفاده در مدل زبانی، به‌ویژه در مدل‌های زبانی بزرگِ مبتنی بر شبکه‌های عصبی، تغییر یافته است. نسخه تغییر یافته به دنبال فشرده‌سازی حداکثری متن نیست، بلکه متن ساده را به «توکن»هایی تبدیل می‌کند که در حقیقت اعداد طبیعی هستند. همه توکن‌های منحصربه‌فردی که در یک پیکره متنی یافت می‌شوند در دایره واژگان توکن فهرست می‌شوند. اندازه این واژگان در مورد جی‌پی‌تی ۳.۵ و جی‌پی‌تی ۴ برابر با ۱۰۰۲۵۶ است.

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

این رویکرد BPE تغییر یافته در سال‌های اخیر از زبان گفتاری به زبان اشاره نیز گسترش یافته است. 

### مثال
فرض کنید در حال کدگذاری همان مثال قبلی «aaabdaaabac» هستیم، با یک اندازه واژگان معادل عدد ۶. با این وضعیت، متن اصلی با استفاده از دایره واژگان «a=0, b=1, d=2, c=3» به صورت «0, 0, 0, 1, 2, 0, 0, 0, 1, 0, 3» کدگذاری می‌شود. سپس فرایند همانند قبل ادامه می‌یابد و همراه با دایره واژگان «a=0, b=1, d=2, c=3, aa=4, ab=5»، متن قبلی به «4, 5, 2, 4, 5, 0, 3» کدگذاری می‌شود.

تا اینجا اساس کار همان فرایند پیشین است. با این حال، اگر اندازه واژگان ۵ تعیین شده بود، فرایند در دایره واژگان «a=0, b=1, d=2, c=3, aa=4» متوقف می‌شد، و مثال به صورت «4, 0, 1, 2, 4, 0, 1, 0, 3» کدگذاری می‌شد. 

از سوی دیگر، اگر اندازه واژگان ۸ تعیین می‌شد، در نهایت کدگذاری «7, 6, 0, 3» به دست می‌آمد، با که با استفاده از دایره واژگانی «a=0, b=1, d=2, c=3, aa=4, ab=5, aaab=6, aaabd=7» اتفاق می‌افتاد. این روش لزوماً بهینه‌ترین حالت فشرده‌سازی نیست، اما هدف BPE تغییر یافته، فشرده‌سازی حداکثری مجموعه داده‌ها نیست، بلکه می‌خواهد آن را به شکلی مناسب برای آموزش مدل‌های زبانی کدگذاری کند.

### BPE در سطح بایت
در مثال بالا، خروجی BPE یک دایره واژگان است که می‌تواند برای کدگذاری هر متنی که با حروف «abcd» نوشته شده، مورد استفاده قرار گیرد. اما قادر نخواهد بود متنی را که شامل حروف دیگری است، مانند «no»، کدگذاری کند. حتی اگر هر ۲۶ حرف الفبا در واژگان حضور داشته باشند، از آنجا که در دنیا زبان‌های متعدد با خط‌های گوناگون وجود دارد، به ناچار برخی نویسه‌ها قابل کدگذاری توسط چنین واژگانی نخواهند بود.

یکی از راهکارها این است که هر نویسه غیرقابل کدگذاری را با یک نویسه ویژه به نام UNK («ناشناخته») جایگزین کنیم.

روش «BPE در سطح بایت» راهکاری متفاوت است. در این روش ابتدا متن به قالب متنی یوتی‌اف-۸ تبدیل شده و سپس به شکل یک جریان از بایت‌ها پردازش می‌شود. به این ترتیب هر متنی که در UTF-8 کدگذاری شده باشد می‌تواند توسط BPE کدگذاری شود. این روش در مدل‌های شبه برت مانند RoBERTa، BART و DeBERTa، و نیز در مدل‌های شبیه به جی‌پی‌تی نظیر جی‌پی‌تی ۲ استفاده شده است.

## یادداشت‌ها

## جستارهای وابسته

* ری-پر
* الگوریتم سکویتر
## منابع
 
رده:الگوریتم‌های فشرده‌سازی بی‌اتلاف 
رده:فشرده‌سازی داده‌ها