مطابقة الأنماط المضغوطة

في علوم الحاسوب ، تُعرف مطابقة الأنماط المضغوطة ( CPM ) بأنها عملية البحث عن أنماط في البيانات المضغوطة مع فك ضغط بسيط أو بدون فك ضغط على الإطلاق. يُعد البحث في سلسلة نصية مضغوطة أسرع من البحث في سلسلة نصية غير مضغوطة، كما أنه يتطلب مساحة تخزين أقل.

إذا كان الملف المضغوط يستخدم ترميزًا متغير العرض، فقد يُشكل ذلك مشكلة: على سبيل المثال، لنفترض أن "100" هو رمز الحرف "أ" ، و"110100" هو رمز الحرف " ب" . إذا كنا نبحث عن ظهور الحرف "أ" في النص، فقد نحصل على نتيجة تتضمن ظهورًا ضمن رمز الحرف " ب" : نسمي هذه الحالة "تطابقًا خاطئًا ". لذا، علينا التحقق مما إذا كان الظهور المكتشف محاذيًا فعليًا لحدود رمز الحرف. مع ذلك، يمكننا دائمًا فك ترميز النص بالكامل ثم تطبيق خوارزمية مطابقة السلاسل النصية التقليدية ، لكن هذا يتطلب عادةً مساحة ووقتًا أكبر، وغالبًا ما يكون غير ممكن، على سبيل المثال إذا كان الملف المضغوط مُستضافًا على الإنترنت. تُسمى هذه المشكلة، المتمثلة في التحقق من صحة أو خطأ التطابق الذي تُرجعه خوارزمية مطابقة الأنماط المضغوطة، بالإضافة إلى استحالة فك ترميز النص بالكامل، بمشكلة المطابقة المضغوطة . ^{[ 1 ]}

توجد العديد من الاستراتيجيات لإيجاد حدود الكلمات المشفرة وتجنب فك ضغط النص بالكامل، على سبيل المثال:

• قائمة بمؤشرات البت الأول من كل كلمة رمزية، حيث يمكننا تطبيق البحث الثنائي؛
• قائمة بمؤشرات البت الأول من كل كلمة رمزية مع الترميز التفاضلي، حتى نتمكن من استخدام مساحة أقل داخل الملف؛
• قناع البت ، حيث يشير البت 1 إلى بت البداية لكل كلمة رمزية؛
• التقسيم إلى كتل، من أجل تخفيف الضغط الجزئي والموجه.

تم تقديم خوارزميات توفر وقت تشغيل ينمو لوغاريتميًا مع زيادة طول السلسلة والنمط. ^{[ 2 ]}

• شموئيل ت. كلاين ودانا شابيرا مطابقة الأنماط في النصوص المشفرة بواسطة هوفمان (2003)
• ماريك كاربينسكي، فويتشيك ريتر وأيومي شينوهارا. خوارزمية فعالة لمطابقة الأنماط للسلاسل ذات الأوصاف القصيرة. المجلة الإسكندنافية للحوسبة 4(2): ص 172-168 (1997).

• "مطابقة الأنماط المضغوطة بتقنية LZW شبه المثالية". 1999: 316-325 . CiteSeerX 10.1.1.44.5521 . {{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=
• خوارزمية مطابقة الأنماط المضغوطة القائمة على القاموس (ملف PDF) ، مؤرشفة من النسخة الأصلية (ملف PDF) بتاريخ 13 مارس 2003
• "إطار عمل موحد لمطابقة الأنماط المضغوطة". 1999: 89-96 . CiteSeerX 10.1.1.50.1745 . {{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=
• "تسريع مطابقة أنماط السلاسل النصية عن طريق ضغط النصوص: فجر عصر جديد" (ملف PDF) . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 8 أغسطس 2007. تم الاطلاع عليه بتاريخ 22 مارس 2009 .{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=
• "نهج الإزاحة والمطابقة النمطية في النصوص المضغوطة بتقنية LZW". 1999: 1-13 . CiteSeerX 10.1.1.15.4609 . {{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=
• "خوارزمية LZW" (ملف PDF) .{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=