ما هي بعض بدائل قليلا المصفوفة ؟

Question

لدي استرجاع المعلومات التطبيق الذي يخلق نوعا المصفوفات على أمر من 10s من مليون بت.عدد من "مجموعة" بت في مجموعة تختلف على نطاق واسع ، من الواضح أن كل مجموعة.حاليا, أنا باستخدام مستقيم إلى الأمام قليلا array (java.util.BitSet) ، وذلك في كل من بلدي قليلا المصفوفات يأخذ عدة ميغا بايت.

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

• ما الهياكل قد تكون جيدة في كل المتطرفة ؟
• هل هناك أي في الوسط ؟

هنا هي عدد قليل من القيود أو تلميحات:

1. بت يتم تعيين مرة واحدة فقط ، في مؤشر النظام.
2. أحتاج 100% دقة شيء مثل ازهر تصفية ليست جيدة بما فيه الكفاية.
3. بعد مجموعة بنيت, أنا بحاجة إلى أن تكون قادرة على كفاءة تكرار عبر "مجموعة" بت.
4. البتات وزعت عشوائيا ، بحيث تشغيل-طول–خوارزميات التشفير غير المحتمل أن يكون أفضل بكثير من قائمة بسيطة من بعض الفهارس.
5. أنا أحاول تحسين استخدام الذاكرة ، ولكن السرعة لا يزال يحمل بعض الوزن.

شيء مفتوح المصدر جافا تنفيذ مفيد ، ولكن لم يكن ضروريا.أنا أكثر اهتماما في الأساسيات.

Answer 1

ما لم تكن بيانات عشوائية حقا و وقد متماثل 1/0 التوزيع ، فإن هذا يصبح مجرد ضياع ضغط البيانات المشكلة هي مشابهة جدا CCITT المجموعة 3 ضغط تستخدم في الأسود والأبيض (أي:ثنائي) فاكس الصور.CCITT المجموعة 3 يستخدم ترميز هوفمان المخطط.في حالة الفاكس أنها تستخدم مجموعة ثابتة من هوفمان رموز, ولكن لفترة معينة من البيانات ، يمكنك إنشاء مجموعة محددة من رموز لكل مجموعة البيانات لتحسين نسبة ضغط تحقيقها.طالما أنك تحتاج فقط للوصول إلى بت بالتتابع ، كما ينطوي هذا سوف يكون فعال جدا النهج.وصول عشوائي من شأنه أن يخلق بعض التحديات الإضافية ، ولكن ربما يمكن أن تولد شجرة البحث الثنائية مؤشر إلى مختلف تعويض النقاط في مجموعة من شأنها أن تسمح لك للحصول على مقربة من الموقع المطلوب ثم سيرا على الأقدام من هناك.

ملاحظة:Huffman المخطط لا يزال يعمل بشكل جيد حتى إذا كانت البيانات العشوائية ، طالما 1/0 التوزيع ليس تماما حتى.التي هي أقل حتى توزيع أفضل نسبة الضغط.

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

Answer 2

وأود أن تنظر بقوة باستخدام مجموعة ترميز في مكان Huffman coding.في عام مجموعة ترميز يمكن استغلال التباين على نحو أكثر فعالية من Huffman coding, ولكن هذا خاصة حتى عندما الأبجدية حجم صغير جدا.في الواقع ، عندما "الأم الأبجدية" هو ببساطة 0s 1s, الطريقة الوحيدة هوفمان يمكن الحصول على أي ضغط على الإطلاق من خلال الجمع بين تلك الرموز-التي هي بالضبط ما مجموعة ترميز سوف تفعل أكثر فعالية.

Answer 3

ربما في وقت متأخر جدا بالنسبة لك, ولكن هناك بسرعة كبيرة و كفاءة الذاكرة مكتبة متفرق قليلا المصفوفات (ضياع) وغيرها من أنواع البيانات على أساس محاولات.انظر جودي المصفوفات

Answer 4

شكرا على الإجابات.هذا ما سأحاول حيوي اختيار الأسلوب المناسب:

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

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

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

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

Answer 5

أكثر واحد ضغط الفكر:

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

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

Answer 6

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

Answer 7

سريعة combinatoric دليل على أن كنت حقا لا يمكن إنقاذ الكثير من الفضاء:

افترض أن لديك التعسفي فرعية n/2 بت تعيين إلى 1 ن مجموع بت.لديك (ن اختيار n/2) الاحتمالات.باستخدام ستيرلينغ صيغة, هذا هو ما يقرب من 2^n / الجذر التربيعي(ن) * الجذر التربيعي(2/pi).إذا كل الاحتمال هو المرجح أيضا, ثم ليس هناك طريقة لإعطاء المزيد من المرجح الخيارات أقصر التمثيل.لذلك نحن بحاجة log_2 (ن اختيار n/2) بت ، وهي عبارة عن n - (1/2)log(n) بت.

هذا ليس جيد جدا المدخرات من الذاكرة.على سبيل المثال ، إذا كنت تعمل مع ن=2^20 (1 meg), ثم يمكنك فقط حفظ 10 أجزاء.انها مجرد لا يستحق كل هذا العناء.

وبعد كل ذلك, كما يبدو من المستبعد جدا أن أي حقا معلومات مفيدة حقا عشوائية.في حال كان هناك أي هيكل أكثر إلى البيانات الخاصة بك, هناك ربما أكثر تفاؤلا الإجابة.