حساسية مقاييس التكرارية تجاه عكس السلاسل

ندرس التأثير الذي يمكن أن يحدثه عكس السلاسل على عدة مقاييس للتكرارية. أولاً، نعرض عائلة غير منتهية من السلاسل حيث يمكن أن يزيد عدد الجولات، r، في ترميز طول الجولات لتحويل بورو-ويلر (BWT) بشكل إضافي بمقدار Θ (n) عند عكس السلسلة. هذا يحسن بشكل كبير حد الأدنى المعروف Ω (log n) لحساسية r الإضافية وهو ضيق بشكل تقاربي. نعمم نتاجنا لنسخ أخرى من BWT، بما في ذلك النسخة مع رمز نهاية السلسلة المضاف وBWT الإحادي. نوضح أن نتيجة مماثلة تنطبق على الحجم z لتمثيل Lempel-Ziv 77 (LZ) للنص، وكذلك لبعض نسخها، بما في ذلك تمثيل LZ غير المتداخل وتمثيل LZ-end. علاوة على ذلك، نصف عائلة من السلاسل التي تقترب فيها النسبة z (wR) /z (w) من 3 من الأسفل بينما |w| → ∞. كما نعرض حد أدنى ضيق بمقدار Θ (n) لحساسية الحجم v لأصغر تمثيل قاموس تجاه عكس السلاسل. أخيرًا، نوضح أن الحساسية الضربية لـ v تجاه عكس السلسلة هي Θ (log n)، وهذا الحد الأدنى أيضًا ضيق. بشكل عام، تكشف نتائجنا عن قيود مقاييس التكرارية المستخدمة على نطاق واسع في الممارسة العملية، ضد عكس السلاسل - وهو تحويل بسيط وطبيعي للبيانات.