💬 NLP

Incremental BPE Tokenization

تقدم هذه الورقة خوارزمية ترميز (BPE) تزايدية جديدة تحقق تعقيداً زمنياً في أسوأ الحالات يبلغ $\mathcal{O}(n \log^2 t)$ ، مما يتيح معالجة تدفقية فعالة بسرعة تصل إلى 3 أضعاف المكتبات الحالية مثل tokenizers من Hugging Face وtiktoken.

المؤلفون الأصليون: Shenghu Jiang, Ruihao Gong

نُشر 2026-06-01

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Shenghu Jiang, Ruihao Gong

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك تقرأ كتاباً طويلاً، ولكن بدلاً من قراءة الكلمات كلمة بكلمة، أنت تقرأها "بايت ببايت" (وهي أصغر وحدات البناء الرقمية للنص). هدفك هو تجميع هذه "البايتات" في كتل ذات معنى تسمى "الرموز" (tokens)، لكي يتمكن الكمبيوتر من فهمها. تُسمى هذه العملية "الترميز" (tokenization)، وأكثر الطرق شيوعاً للقيام بها هي "ترميز زوج البايتات" (Byte Pair Encoding - BPE).

فكر في عملية (BPE) كأنها لعبة "ليجو" (Lego). تبدأ بقطع فردية (بايتات). وتقول قواعد اللعبة: "إذا رأيت قطعتين محددتين بجانب بعضهما البعض كثيراً، فقم بدمجهما معاً لصنع قطعة أكبر ومخصصة". تستمر في دمج الأزواج معاً، حتى تحصل على مزيج من القطع الصغيرة والهياكل الأكبر المخصصة.

المشكلة: عنق الزجاجة المتمثل في "الانتظار والترقب"

حالياً، معظم البرامج الحاسوبية التي تلعب لعبة الليجو هذه تعمل بشكل "غير متصل" (offline). فهي تتطلب الصفحة الكاملة من النص قبل أن تبدأ في دمج القطع معاً.

التشبيه: تخيل أنك تبني جداراً من الليجو، ولكن عليك الانتظار حتى تأتي شاحنة التوصيل بكل قطع الجدار قبل أن تتمكن حتى من دمج أول قطعتين معاً. لا يمكنك البدء في البناء حتى تصل الشحنة بأكملها.
النتيجة: في الذكاء الاصطناعي الحديث (مثل روبوتات الدردشة)، يتسبب هذا في حدوث تأخير. يجب على الكمبيوتر انتظار وصول الجملة بأكملها قبل أن يبدأ في معالجة الكلمة الأولى. الأمر يشبه خط تجميع في مصنع يتوقف في كل مرة تصل فيها قطعة جديدة، منتظراً وصول الدفعة بأكملها قبل المضي قدماً.

الحل: البنّاء "التزايدي"

يقترح مؤلفو هذه الورقة طريقة أذكى للعب لعبة الليجو. يسمونها "ترميز BPE التزايدي" (Incremental BPE Tokenization).

بدلاً من انتظار الشاحنة بأكملها، يقوم خوارزمهم بدمج القطع معاً بمجرد وصول كل "بايت" جديد.

التشبيه: تخيل بناءً ماهراً يمكنه النظر إلى قطعة واحدة جديدة، ومعرفة كيف تتناسب فوراً مع القطع السابقة، ودمجها في مكانها على الفور. هو لا يحتاج لرؤية الجدار بأكمله ليعرف كيف يبدو القسم الحالي.
كيف يعمل: تقدم الورقة بنية رياضية ذكية (تسمى "غابة التوالي" Successor Forest و"شجرة التوالي اللاحق" Suffix-Successor Tree) تعمل بمثابة خريطة لجميع تركيبات الليجو الممكنة. عندما يأتي "بايت" جديد، يستخدم الخوارزم هذه الخريطة ليعرف فوراً أفضل طريقة لتجميعه مع الماضي، دون الحاجة لإعادة مسح النص بأكمله.

الميزات والفوائد الرئيسية

1. السرعة والاستقرار (ضمان "عدم الانهيار")

الادعاء: الطرق القديمة قد تصبح بطيئة أو تتعطل إذا كان النص يحتوي على أنماط غريبة (مثل مليون حرف "a" متتالية). الطريقة الجديدة تشبه سترة واقية من الرصاص؛ فهي تضمن أنها لن تصبح بطيئة أبداً، بغض النظر عن مدى غرابة النص.
النتيجة: إنها أسرع بما يصل إلى 3 مرات من المعيار الصناعي الحالي (ترميزات Hugging Face)، وتتعامل مع المدخلات "المرضية" (الغريبة) دون أن تتباطأ، على عكس tiktoken الخاص بـ OpenAI الذي يمكن أن يغرق في العمليات.

2. المخرجات المتدفقة (الطاهي "المتحمس")

ال दावा: لا تكتفي الطريقة بمعالجة المدخلات بشكل أسرع فحسب، بل تبدأ أيضاً في إخراج قطع الليجو الجاهزة فوراً.
التشبيه: تخيل طاهياً لا ينتظر نضج الوجبة بأكملها قبل تقديمها. بمجرد أن تجهز طبخة، يقوم بتنسيقها وتقديمها لك. هذا ما يسمى بـ "المخرجات المتعجلة" (Eager Output).
الفائدة: يسمح هذا للذكال الاصطناعي بالبدة في "التفكير" (توليد استجابة) بينما لا يزال "يقرأ" سؤالك، مما يجعل المحادثة تبدو أكثر واقعية وانسيابية في الوقت الفعلي.

3. بديل جاهز للاستخدام (Drop-in Replacement)

الادعاء: تم تصميم هذا الخوارزم الجديد ليكون ترقية "وصل وشغل" (plug-and-play). لست بحاجة لإعادة بناء نظام الذكاء الاصطناعي الخاص بك بالكامل؛ ما عليك سوى استبدال أداة الترميز القديمة بهذه الأداة الجديدة، وستعمل بنفس الطريقة تماماً ولكن بشكل أسرع بكثير.

الملخص

ببساطة، تقدم هذه الورقة بناءً فائق الكفاءة وفي الوقت الفعلي لقطع الليجو الخاصة بمعالجة النصوص في الذكاء الاصطناعي.

الطريقة القديمة: انتظر النص بأكمله، ثم ابنِ كل شيء دفعة واحدة. (بطيئة، وعرضة للتأخير).
الطريقة الجديدة: ابنِ القليل مع وصول كل حرف. (سريعة، مستقرة، وتسمح للذكاء الاصطناعي بالرد عليك بينما لا تزال تكتب).

لقد أثبت المؤلفون رياضياً أن هذه الطريقة سريعة، وموثوقة، وتعمل بشكل مثالي مع القواعد الحالية لكيفية فهم الذكاء الاصطناعي للنصوص، مما يوفر دفعة كبيرة في السرعة لنماذج اللغة الحديثة.

ملخص تقني: ترميز BPE التدريجي

بيان المشكلة

تعتمد مسارات النماذج اللغوية الكبيرة (LLM) الحديثة بشكل كبير على ترميز "ترميز زوج البايت" (Byte Pair Encoding - BPE). ومع ذلك، فإن معظم التطبيقات الحالية المتطورة (مثل tokenizers من Hugging Face و tiktoken من OpenAI) مصممة في الغالب كعمليات غير تدريجية (offline). فهي تتطلب مراقبة تسلسل المدخلات بالكامل أو جزء مقسم مسبقاً قبل إنتاج ترميز معياري. هذا القيد المعماري يجبر عمليات الترميز والملء المسبق للنموذج (pre-filling) على التنفيذ بشكل متسلسل بدلاً من التنفيذ المتزامن، مما يؤدي إلى إدخال زمن انتقال (latency) في سيناريوهات البث (streaming) والاستدلال طويل السياق.

علاوة على ذلك، تعتمد التطبيقات الحالية غالباً على طوابير أولوية قائمة على الكومة (heap-based priority queues) لاختيار عمليات الدمج عبر المدخلات الكاملة، مما ينتج عنه صياغات عالمية بطبيعتها ويصعب تكييفها مع التحديثات التي تتم بايت تلو الآخر. وبينما تستخدم بعض الأدوات تقسيم ما قبل المعالجة القائم على التعبيرات النمطية (regex) للحد من تكاليف الدمج، فإن هذا النهج قد يكون هشاً، مما يؤدي إلى تدهور الأداء أو استنفاد المكدس (stack exhaustion) عند التعامل مع مدخلات مرضية (pathological inputs) (مثل التكرارات الطويلة للرموز)، حيث تظهر بعض الأدوات سلوكاً بمقياس $O(n^2)$ .

المنهجية

يقترح المؤلفون خوارزمية مبتكرة لـ ترميز BPE التدريجي تحافظ على نتائج ترميز BPE لكل بادئة (prefix) من النص المدخل في الوقت الفعلي. يعتمد هذا النهج على الخصائص الهيكلية لـ BPE ويقدم عدة ابتكارات خوارزمية رئيسية:

1. الأسس الهيكلية

اتساق البادئة (Prefix Consistency): بالاستفادة من خاصية أن ترميز BPE الصالح يمكن قطعه بحرية، تعمل الخوارزمية على نمذجة ترميز سلسلة متنامية كإمتداد لترميز بادئة سابقة صالحة لسلسلة أقصر، بدلاً من إعادة الحساب.
الرمز الأخير ( $\theta(s)$ ): تركز الخوارزمية على الحفاظ على "الرمز الأخير" للسلسلة الحالية $s$ . يتم تشفير الترميز الكامل ضمنياً من خلال تسلسل الرموز الأخيرة، والذي يمكن استرجاعه عبر التتبع الخلفي (backtracking).
غابة الخلفاء (Successor Forest) وشجرة خلفاء اللاحقة (Suffix-Successor Tree): يتم تطبيع المفردات (vocabulary) إلى رموز معيارية، مما يشكل بنية طوبولوجية تسمى غابة الخلفاء. لأي مدخل، يتم حصر مساحة البحث للرمز الأخير الجديد في شجرة خلفاء اللاحقة، التي تنظم جميع رموز اللاحقة المحتملة.

2. خاصية المسار الرتيب (The Monotonic Path Property)

المساهمة النظرية الجوهرية هي خاصية المسار الرتيب، والتي تثبت أنه لأي سلسلة مدخلة، فإن مجموعة رموز اللاحقة القادرة على العمل كرمز أخير تشكل مساراً واحداً مستمراً داخل شجرة خلفاء اللاحقة. هذا المسار يرتكز عند الجذر (الرمز الذري) ويمتد إلى الرمز الأخير الحقيقي $\theta(s)$ . هذه الخاصية تقلص مساحة البحث من الشجرة بأكملها إلى مسار واحد، مما يتيح التحقق بكفاءة.

3. التنفيذ الخوارزمي

تتضمن عملية التحديث التدريجي خطوتين رئيسيتين:

تحديد مساحة البحث: باستخدام آلية أهو-كوراسيك (Aho–Corasick automaton) معززة بتبليط الجذر التربيعي المستمر، تحدد الخوارزمية أطول رمز لاحق $\tau(sc)$ في زمن قدره $O(1)$ ، مما يحدد شجرة خلفاء اللاحقة المحددة.
البحث عن تمديد المسار: للعثور على أعمق عقدة صالحة على المسار الرتيب، تستخدم الخوارما تفكيك المركز (Centroid Decomposition). تقوم بالتنقل عبر شجرة بحث المركز (CST) مسبقة الحساب بارتفاع $O(\log |\tau|)$ . وفي كل خطوة، تتحقق من شرط الرمز الأخير للبادئة (التحقق من الوصول والسيادة ذات الأولوية) باستخدام فترات التخطيط الخطي لـ DFS. يسمح هذا للخوارزمية بتحديد اتجاه المسار الصالح في زمن قدره $O(\log |\tau|)$ .

4. آلية المخرجات المستعجلة (Eager Output)

لدعم البث الحقيقي، يقدم المؤلفون خوارزمية المخرجات المستعجلة. وهي تحدد "الجبهة النشطة" (Active Frontier) لشجرة الترميز — وهو نطاق البادئات التي يمكن أن تصبح مستقبلاً آباءً لرموز قادمة. من خلال الحفاظ على رسم بياني فرعي ديناميكي لهذه المرشحات، يمكن للنظام إصدار الرموز بمجرد أن تصبح حدودها ثابتة (أي عندما تتقارب جميع المسارات النشطة إلى ابن واحد من الجذر الافتراضي)، مما يتيح خط أنابيب (pipelining) كاملاً مع استدلال النموذج.

المساهمات الرئيسية

التعقيد الخوارزمي: تعالج الخوارزمية المقترحة كل بايت من المدخلات بتعقيد زمني أسوأ حالة صارم قدره $O(\log_2 t)$ ، حيث $t$ هو أقصى طول للرمز. ينتج عن ذلك تعقيد إجمالي قدره $O(n \log_2 t)$ لمدخل بطول $n$ .
القدرة على البث: تعمل الطريقة كبديل جاهز لمراحل BPE القياسية، مما يتيح ترميزاً جزئياً فعالاً في سيناريوهات البث دون تغيير صحة مراحل المعالجة المسبقة المحيطة.
المخرجات المستعجلة: يتيح تقديم آلية المخرجات المستعجلة بثاً وتدفقاً (pipelining) حقيقياً مع استدلال النموذج، من خلال إصدار الرموز فور تحديد الحدود.
المتانة: على عكس الأدوات الحالية التي قد تتدهور إلى $O(n^2)$ في المدخلات المرضية، تحافظ هذه الطريقة على ضمانات أداء مستقرة.
دعم البادئة الكاملة: تدعم الخوارزمية بشكل طبيعي السيناريوهات التي تتطلب الوصول إلى ترميزات جميع البادئات (مثل مهام "الملء في المنتصف" أو علاج الرموز) دون الحاجة إلى قطع تجريبي أو إعادة حساب.

النتائج

قام المؤلفون بتنفيذ الخوارزمية بلغة Rust واختبروا أداءها مقابل tokenizers من Hugging Face و tiktoken من OpenAI.

الإنتاجية (Throughput): تحقق الطريقة التدريجية تسريعاً في النهاية إلى النهاية يصل إلى $\sim 3\times$ مقارنة بترميزات Hugging Face، خاصة في السيناريوهات التي تفتقر إلى التقسيم المسبق القائم على التعبيرات النمطية (مثل CodeLlama).
زمن الانتقال في المدخلات المرضية: في المدخلات ذات التكرارات المكثفة، تظهر tiktoken تراجعاً في الإنتاجية يتوافق مع تعقيد $O(n^2)$ . في المقابل، تحافظ الطريقة المقترحة على إنتاجية مستقرة، مما يظهر انخفاضات كبيرة في زمن الانتقال في مثل هذه الحالات المرضية.
عبء المخرجات المستعجلة: تفرض آلية المخرجات المستعجلة عبئاً قدره حوالي 10% في الإنتاجية من النهاية إلى النهاية مقارنة بالنسخة التدريجية غير المستعجلة، وهو تكلفة يشير المؤلفون إلى إمكانية استيعالها (amortized) في الأنظمة التي يتم فيها دمج الترميز مع الإدخال/الإخراج أو الاستدلال.

الأهمية والادعاءات

تثبت الورقة أن ترميز BPE يمكن تنفيذه بشكل تدريجي مع ضمانات صارمة لأسوأ حالة مع الحفاظ على التوافق الدلالي التام مع BPE القياسي.

يدعي المؤلفون أن عملهم يسد الفجوة بين الصيغ النظرية (التي تقترح استقرار البادئة) والهندسة العملية (التي اعتمدت على المعالجة العالمية غير التدريجية). ومن خلال توفير خوارزمية بتعقيد $O(n \log_2 t)$ ، يتيح العمل:

تقليل زمن الانتقال: من خلال السماح بدم عملية الترميز بالكامل مع استدلال النموذج، مما يزيل الاختناق المتسلسل في الاستدلال التدريجي.
متانة النظام: من خلال التخفيف من خطر هجمات التعقيد الخوارزمي (مثل حرمان الخدمة عبر مدخلات مصممة خصيصاً) التي تستغل ثغرات $O(n^2)$ في المرمّزات الحالية.
تحسين خط الأنابيب: من خلال جعل مراحل التقسيم المسبق (المصممة فقط للحد من تكاليف BPE العالمية) غير ضرورية خوارزمياً، مما يسمح بتصميمات أكثر نظافة وكفاءة لخطوط الأنابيب.

يخلص المؤلفون إلى أن نهجهم يمهد الطريق لخطوط أنابيب نماذج لغوية كبيرة أكثر استجابة، ومتانة، وكفاءة في استهلاك الطاقة من خلال ترجمة الضمانات الخوارزمية الصارمة إلى فوائد عملية في زمن الانتقال.