تحتاج الذاكرة وسيلة فعالة لتخزين طن من سلاسل (كان:قبعة Trie التنفيذ في جافا)

Question

أنا أعمل مع مجموعة كبيرة (5-20 مليون دولار) من سلسلة مفاتيح (متوسط طول 10 حرف) التي لا تحتاج إلى تخزين في الذاكرة بنية البيانات التي تدعم العملية التالية في وقت ثابت أو شبه ثابت الزمن:

// Returns true if the input is present in the container, false otherwise
public boolean contains(String input)

جافا Hashmap يبرهن على أن تكون أكثر من مرضية بقدر إنتاجية المعنية ولكن تأخذ الكثير من الذاكرة.أنا أبحث عن حل كفاءة الذاكرة و لا يزال يدعم سرعة الكريم (مقارنة مع أو تقريبا جيدة كما تجزئة).

أنا لا أهتم إدراج/حذف مرات.في التطبيق سوف تكون المنفذ الوحيد الملاحق (فقط في وقت بدء التشغيل) و بعد ذلك فقط يمكن الاستعلام عن هيكل البيانات باستخدام contains طريقة حياة التطبيق.

قرأت تلك القبعة-Trie بنية البيانات هو الأقرب للحصول على احتياجات بلدي.وأنا أتساءل عما إذا كان هناك مكتبة يحتوي على التنفيذ.

اقتراحات أخرى مع مؤشرات إلى تطبيقات موضع ترحيب.

شكرا لك.

Answer 1

Trie يبدو مثل فكرة جيدة جدا عن القيود الخاصة بك.

و "التفكير خارج الصندوق" البديلة:

إذا كنت يمكن أن تحمل بعض احتمال الرد على "الحاضر" عن سلسلة غائب

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

من أجل k=1, ازهر مرشح مثل جدول تجزئة دون مفاتيح:كل "دلو" هو ببساطة منطقية أن يقول إذا كان واحد على الأقل الإدخال مع نفس التجزئة كان حاضرا.لو 1% ايجابيات كاذبة غير مقبول ، جدول التجزئة الخاصة بك يمكن أن تكون صغيرة مثل 100 * 20 مليون بت أو ما يقرب من 200 MiB.1 في 1000 ايجابيات كاذبة ، 2GiB.

باستخدام عدة وظائف التجزئة بدلا من واحدة يمكن تحسين معدل الإيجابية الكاذبة لنفس المبلغ من البتات.

Answer 2

جوجل يجلب بلوق وظيفة على قبعة يحاول في جافا.ولكن أنا لا أرى كيف أن هذا سوف يحل المشكلة مباشرة:هيكل هو ضحل trie على البادئات المفاتيح ، مع أوراق يجري hashtables عقد اللواحق جميع مفاتيح مع البادئة.حتى في المجموع ، لديك الكثير من hashtables تخزين جميع المفاتيح التي هي في واحد الحالي الخاص بك كبيرة hashtable (ربما إنقاذ بضعة بايت لكل المفتاح العام بسبب شائعة البادئات).وفي كلتا الحالتين تحتاج مساحة أكبر كفاءة hashtable من جافا الافتراضية ، أو في وجوه النفقات العامة سوف تصل لك مجرد بشدة.فلماذا لا تبدأ مع متخصص hashtable فئة سلسلة المفاتيح فقط, إذا كنت تأخذ هذا الطريق ، والقلق بشأن trie جزء فقط إذا كان لا يزال يبدو من المفيد إذن ؟

Answer 3

الفضاء الكفاءة O(log(n)) بحث رمز بسيط ، حاول البحث الثنائية على مجموعة من الشخصيات.20 مليون مفاتيح متوسط طول 10 يجعل من 200 مليون الشخصيات:400MB إذا كنت بحاجة إلى 2 بايت/فحم;200MB إذا كان يمكنك الحصول بعيدا مع 1.على رأس هذه تحتاج إلى حد ما تمثل الحدود بين المفاتيح في الصفيف.إذا كان يمكنك حجز حرف فاصل ، هذا هو طريقة واحدة ، وإلا كنت قد تستخدم بالتوازي مجموعة من الباحث إزاحة.

أبسط البديل استخدام مجموعة من السلاسل في الفضاء تكلفة من في وجوه النفقات العامة.يجب أن لا تزال تغلب hashtable في الفضاء الكفاءة ، على الرغم من عدم لافت.

Answer 4

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