ضغط لدفق فريد من البيانات

Question

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

قام Zlib بتقليص حجمه إلى حوالي 25٪ من حجمه الأصلي.هذا جميل، لكنني لا أعتقد أن الخوارزمية الخاصة به مناسبة بشكل خاص لهذه المشكلة.هل يعرف أحد مكتبة ضغط أو خوارزمية بسيطة قد تؤدي أداءً أفضل لهذا النوع من المعلومات؟

تحديث:zlib بعد تحويله إلى مصفوفة من دلتا xor يقلصه إلى حوالي 20% من الحجم الأصلي.

Answer 1

إذا أكثر من الأعداد الصحيحة هي في الواقع نفس سابقة، وعادة ما يمكن التعبير عن الفارق بين رمز باعتباره الوجه بت واحد، وهذا يبدو وكأنه عمل للXOR.

وخذ تيار المدخلات مثل:

1101
1101
1110
1110
0110

ووالمخرجات:

1101
0000
0010
0000
1000

وقليلا من رمز زائف

compressed[0] = uncompressed[0]
loop
  compressed[i] = uncompressed[i-1] ^ uncompressed[i]

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

وعندما تريد ضغط:

uncompressed[0] = compressed[0]
loop
  uncompressed[i] = uncompressed[i-1] ^ compressed[i]

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

Answer 2

هل تعتبر تشغيل طول ترميز ؟

وأو جرب هذا: بدلا من تخزين الأرقام في حد ذاتها، قمت بتخزين الاختلافات بين الأرقام. 1 1 2 2 2 3 5 يصبح 0 1 0 1 0 1 2. الآن معظم الأرقام التي لدينا لترميز صغيرة جدا. لتخزين عدد صحيح صغير، استخدم عدد صحيح 8 بت بدلا من 32 بت واحد فسوف ترميز على معظم المنصات. وهذا عامل من 4 هناك حق. إذا كنت بحاجة إلى أن تكون مستعدة لثغرات أكبر من ذلك، تعيين بت عالي من عدد صحيح 8 بت إلى القول "هذا الرقم يتطلب 8 بت المقبلة أيضا".

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

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

Answer 3

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

في قضيتك، زليب هو وسيلة ضغط البايت من الحكمة، ولكن يأتي البيانات الخاصة بك في (؟ 32-بت) صحيحة. أنت لا تحتاج إلى reimplement ZLIB نفسك، ولكنك تحتاج إلى تقرأ على كيف يعمل، حتى تتمكن من معرفة كيفية تقديمها مع البيانات انضغاط بسهولة، أو إذا كان من المناسب لأغراضك على الإطلاق.

وزليب تنفذ شكل Lempel-زيف الترميز. JPG وغيرها الكثير استخدام هوفمان الترميز لالخلفية الخاصة بهم. ترميز تشغيل طول شعبية لكثير من الاستخدامات المخصصة. الخ، الخ ...

Answer 4

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

1. قم بتقسيم كل int الخاص بك إلى 4 بايت، لذلك i₀, ، أنا₁, ، أنا₂, ، ...، أنا_ن يصبح ب_0,0, ، ب_0,1, ، ب_0,2, ، ب_0,3, ، ب_1,0, ، ب_1,1, ، ب_1,2, ، ب_1,3, ، ...، ب_ن،0, ، ب_ن،1, ، ب_ن،2, ، ب_ن،3.ثم اكتب كل ب_أنا،0س، تليها ب_أنا،1ق، ب_ط،2ق، و ب_ط،3س.إذا كانت أرقامك تختلف في معظم الأوقات بمقدار قليل أو اثنين فقط، فيجب أن تحصل على فترات طويلة لطيفة من البايتات المتكررة، والتي يجب أن يتم ضغطها بشكل جيد باستخدام شيء مثل Run-length Encoding أو zlib.هذا هو المفضل لدي من الأساليب التي أقدمها.

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

3. إذا كانت لديك وحدات بت مختلفة، فلا يزال من الممكن أن يكون لديك اختلافات كبيرة، ولكن إذا كان من المرجح أن يكون لديك اختلافات رقمية كبيرة تتوافق مع اختلاف بت واحد أو اثنين (عادةً)، فقد تكون أفضل حالًا باستخدام مخطط حيث تقوم بإنشاء ahebyte المصفوفة - استخدم أول 4 بايتات لترميز العدد الصحيح الأول، ثم لكل إدخال لاحق، استخدم 0 بايت أو أكثر للإشارة إلى البتات التي يجب قلبها - تخزين 0، 1، 2، ...، أو 31 في البايت، مع حارس (قل 32) للإشارة إلى وقت الانتهاء.قد يؤدي هذا إلى العدد الأولي من البايتات اللازمة لتمثيل عدد صحيح لشيء قريب من 2 في المتوسط، والذي تأتي معظم البايتات من مجموعة محدودة (0 - 32).قم بتشغيل هذا الدفق عبر zlib، وربما ستتفاجأ بسرور.

Answer 5

هل جربت BZIP2 لهذا؟ http://bzip.org/

وانها عملت دائما أفضل من زليب بالنسبة لي.

Answer 6

نظرًا لأن اهتمامك هو تقليل عملية الإدخال/الإخراج للقرص، فستحتاج إلى ضغط كل مصفوفة أعداد صحيحة بشكل مستقل، دون الإشارة إلى مصفوفات أعداد صحيحة أخرى.

أحد الأساليب الشائعة للسيناريو الخاص بك هو تخزين الاختلافات، حيث يمكن ترميز عدد صغير من الاختلافات باستخدام كلمات مشفرة قصيرة.يبدو أنك بحاجة إلى ابتكار نظام ترميز خاص بك للاختلافات، نظرًا لأنها اختلافات متعددة البت، وربما تستخدم بايت 8 بت كنقطة بداية:

• 1 بت للإشارة إلى أن عددًا صحيحًا جديدًا كاملاً يتبعه، أو أن هذا البايت يشفر اختلافًا عن العدد الصحيح الأخير،
• 1 بت للإشارة إلى أن هناك المزيد من البايتات التالية، وتسجيل المزيد من اختلافات البت الفردية لنفس العدد الصحيح.
• 6 بتات لتسجيل رقم البت للتبديل من العدد الصحيح السابق.

إذا كان هناك أكثر من 4 بتات مختلفة، فقم بتخزين العدد الصحيح.

قد لا يكون هذا المخطط مناسبًا إذا كان لديك أيضًا الكثير من الرموز المختلفة تمامًا، نظرًا لأن كل منها سيأخذ 5 بايت الآن بدلاً من 4.

Answer 7

"Zlib يقللها بعامل حوالي 4x." يعني أن ملف 100 ألف الآن يأخذ الآن سلبي 300 ألف؛هذا مثير للإعجاب بكل تعريف :-).أفترض أنك تقصد أنه يقلصه بنسبة 75%، أي إلى 1/4 حجمه الأصلي.

أحد احتمالات الضغط الأمثل هو كما يلي (يفترض عددًا صحيحًا 32 بت وتغيير 3 بتات على الأكثر من عنصر إلى عنصر).

• إخراج العدد الصحيح الأول (32 بت).
• قم بإخراج عدد تغييرات البت (n=0-3، 2 بت).
• محددات بتات الإخراج (0-31، 5 بتات لكل منها).

أسوأ حالة لهذا الضغط هي تغيير 3 بت في كل عدد صحيح (2+5+5+5 بت) والذي سيميل إلى 17/32 من الحجم الأصلي (ضغط 46.875%).

أقول "يميل نحو" نظرًا لأن العدد الصحيح الأول دائمًا هو 32 بت، ولكن بالنسبة لأي مجموعة ذات حجم مناسب، فإن هذا العدد الصحيح الأول سيكون ضئيلًا.

أفضل حالة هي ملف يحتوي على أعداد صحيحة متطابقة (لا توجد تغييرات في البتات لكل عدد صحيح، فقط 2 بتات صفرية) - سيميل هذا إلى 2/32 من الحجم الأصلي (ضغط بنسبة 93.75%).

حيث يكون متوسط ​​اختلاف 2 بت لكل عدد صحيح متتالي (كما تقول هي حالتك الشائعة)، ستحصل على 2+5+5 بت لكل عدد صحيح والذي يميل إلى ضغط 12/32 أو 62.5%.

نقطة التعادل الخاصة بك (إذا أعطى zlib ضغطًا بنسبة 75٪) هي 8 بت لكل عدد صحيح والذي سيكون

• تغييرات البت المفرد (2+5 = 7 بت):80% من التحولات.
• تغييرات ثنائية البت (2+5+5 = 12 بت):20% من التحولات.

هذا يعني أن متوسطك يجب أن يكون 1.2 بت لكل عدد صحيح لجعل هذا الأمر جديرًا بالاهتمام.

شيء واحد أود أن أقترح النظر فيه هو 7zip - فهو يتمتع بترخيص ليبرالي جدًا ويمكنك ربطه بالكود الخاص بك (أعتقد أن المصدر متاح أيضًا).

لقد لاحظت (بالنسبة لأشيائي على أي حال) أنه يؤدي كثيراً أفضل من WinZip على نظام التشغيل Windows لذلك قد يتفوق أيضًا على zlib.