ما هي أفضل طريقة لضغط قائمة من السلاسل المتشابهة ولكن غير المتطابقة؟

Question

لنفترض أن لدي عددًا من السلاسل المتشابهة تمامًا ولكنها ليست متطابقة تمامًا.

ويمكن أن تختلف أكثر أو أقل، ولكن يمكن رؤية التشابه بالعين المجردة.

جميع الأطوال متساوية، كل منها 256 بايت.إجمالي عدد السلاسل أقل من 2^16.

ما هي أفضل طريقة ضغط لمثل هذه الحالة؟

تحديث (تنسيق البيانات):

لا يمكنني مشاركة البيانات ولكن يمكنني وصفها بشكل قريب جدًا من الواقع:

تخيل التدوين (مثل لغة LOGO) وهو تسلسل الأوامر لبعض الأجهزة للتحرك والرسم على المستوى.مثل:

U12 - move up 12 steps
D64 - move down 64 steps
C78 - change drawing color to 78
P1  - pen down (start drawing)

وما إلى ذلك وهلم جرا.

مفردات هذه اللغة بأكملها لا تتجاوز حجم الأبجدية الإنجليزية.

ثم تصف السلسلة الصورة بأكملها:"U12C6P1L74D74R74U74P0 ....".

تخيل الآن فصلًا مكونًا من عشرة آلاف طفل طُلب منهم رسم صورة محددة للغاية بمساعدة هذه اللغة:مثل علم بلادهمسوف نحصل على 10K من السلاسل التي كلها مختلفة ومتشابهة في نفس الوقت.

مهمتنا هي ضغط مجموعة السلاسل بأكملها بشكل جيد قدر الإمكان.

شكوكي هنا هي أن هناك طريقة لاستغلال هذا التشابه والطول المشترك للسلاسل، في حين أن هوفمان على سبيل المثال.لن استخدامه صراحة.

Answer 1

هل يمكن أن تخبرنا ما هي البيانات؟ربما مثل تسلسل الحمض النووي؟يحب

أجكتجتجكجاجاجاجكجتجج...

جكتجتجكجاجكجاجاكجتجج...

كجكتجتجاجاجنجاكجتجج...

نجتجتجكجاجاجاجكجتجج...

جكتجتجكجاجتجاجاكجتجج...

... ...

؟ربما أو لا.على أية حال، هنا مستويان أو طريقتان للتفكير:

1. ترميز هوفمان:المرجع.ويكيبيديا بنفسك

2. علم الخيط :المرجع. http://books.google.com.hk/books/about/Jewels_of_stringology.html?id=9NdohJXtIyYC

أعتقد أنه من السهل حل مشكلتك ولكن من الصعب اختيار الطريقة الأفضل.يمكنك تصميم عدة طرق للمقارنة باستخدام http://en.wikipedia.org/wiki/Data_compression والمزيد من الأدوات.

Answer 2

نظرًا لأن لديك عرضًا ثابتًا يبلغ 256 بايت وقوة 2، فسأحاول إجراء تحويل عجلة الحفر أو خوارزمية الانتقال إلى الأمام بهذا الحجم أو ربما ضعف هذا الحجم.ثم يمكنك تجربة كود هوفمان.ربما يمكنك تجربة منحنى هيلبرت على 256 بايت ثم bwt وmft؟

Answer 3

"العدد الإجمالي للسلاسل أقل من 2^16." هذا رقم صغير محدود ، مما يجعل عملك سهلاً للغاية:لماذا لا تحتفظ بجدول بحث (جدول التجزئة) لجميع السلاسل التي سبق رؤيتها.يمكنك بعد ذلك تحويل كل سطر من 256 بايت إلى فهرس ثنائي البايت في جدول البحث هذا.

لديك بعد ذلك سلسلة من الأعداد الصحيحة ذات 16 بت.ستحتوي هذه الأعداد الصحيحة على أنماط مثل "بعد سقوط القلم، هناك احتمال بنسبة 90% أن الأمر التالي هو البدء في الرسم".إذا كانت البيانات تحتوي على أنماط مثل هذه، فإن PPM هو اختيارك.يتمتع 7-zip بتنفيذ PPM عالي الجودة.يمكنك اختياره باستخدام واجهة المستخدم الرسومية أو سطر cmd.