خوارزمية الضغط لترميز قوائم الكلمات

Question

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

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

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

يحرر:لتلخيص متطلبات القاموس:

• صفر ايجابيات كاذبة
• صفر السلبيات الكاذبة
• نسبة ضغط عالية جدًا
• لا حاجة لتخفيف الضغط

Answer 1

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

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

Answer 2

مرشح بلوم (http://en.wikipedia.org/wiki/Bloom_filter و http://www.coolsnap.net/kevin/?p=13) عبارة عن بنية بيانات تستخدم لتخزين كلمات القاموس بشكل مضغوط للغاية في بعض أدوات التدقيق الإملائي.ومع ذلك، هناك خطر الحصول على نتائج إيجابية كاذبة.

Answer 3

أود أن أقترح شجرة لاحقة مبطنة.ضغط جيد على قوائم الكلمات، وأوقات بحث ممتازة.

http://en.wikipedia.org/wiki/Suffix_tree

Answer 4

لتلخيص:

• صفر ايجابيات كاذبة
• صفر السلبيات الكاذبة
• نسبة ضغط عالية
• لا حاجة للمعكوس (أيلا حاجة لفك الضغط)

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

بدلاً من ذلك، تتحدث برمجة اللؤلؤ عن مجموعة مماثلة من المتطلبات (/usr/share/dict/words في 41 ك).

اتخذ هذا نهج تقلص السيقان:على سبيل المثال:تم الإرسال هو الجذر، لذلك يمكن إضافة الإصلاحات المسبقة واللاحقة:

• حاضر
• يمثل
• التمثيل
• تحريف

Answer 5

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

السابق.:أ+ن+د+s|an+d+y|و+es+roid

هو 26 حرفًا، مقارنة بـ:

إعلان مثل وأي جبال جبال الأندرويد

وهو 33.

مع الأخذ في الاعتبار نسبة الضغط البالغة 12.5% ​​للتخزين كمحتوى 7 بت، يكون إجمالي الضغط حوالي 31%.تعتمد نسبة الضغط، بطبيعة الحال، على حجم ومحتوى قائمة الكلمات الخاصة بك.

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

لنفكر في الأمر، إذا كنت تستخدم 26 حرفًا فقط بالإضافة إلى حرفين للمحددات، فيمكنك القيام بكل شيء في 5 بتات، وهو ما يمثل ضغطًا بنسبة 37.5% في حد ذاته، وبذلك يصل المثال أعلاه إلى معدل ضغط يزيد عن 50%.

Answer 6

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

Answer 7

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

Answer 8

للضغط النقي، أقصى ضغط يقدم الموقع بعض النتائج لقائمة كلمات إنجليزية حجمها 4 ميجابايت، وأفضل برنامج يضغطها إلى حوالي 400 كيلو بايت.بعض موارد الضغط الأخرى لضغط النص/الكلمات هي صفحة جائزة هوتر و ال معيار ضغط النص الكبير.

Answer 9

يذكر كنوث أ "باتريشيا تحاول" في فن برمجة الكمبيوتر المجلد.3.لم أستخدمه أبدًا في أي عمل حقيقي ولكن ربما يكون ذلك مفيدًا.

يحرر:ما هو قيد ذاكرة الوصول العشوائي الخاصة بك؟إذا كان لديك ذاكرة وصول عشوائي (RAM) أكثر بكثير من ذاكرة الوصول العشوائي (ROM)، فربما يكون ضغط البيانات في ذاكرة الوصول العشوائي (الذي يتطلب إلغاء الضغط في ذاكرة الوصول العشوائي) هو الطريقة الصحيحة.أفترض أنه إذا كان لديك كمية متوسطة ولكن ليست كبيرة من ذاكرة الوصول العشوائي (RAM)، فمن الناحية الفنية، يمكنك أيضًا تخزين أجزاء من بنية البيانات على شكل نقاط مضغوطة في الذاكرة، وذاكرة تخزين مؤقت أقل استخدامًا للاحتفاظ بالعديد منها، ثم فك ضغط الملف المناسب ديناميكيًا blob عندما لا يكون في ذاكرة التخزين المؤقت.