بناء رقم فريد لسلسلة في جافا

Question

لدينا شرط لقراءة/كتابة أكثر من 10 ملايين سلاسل في ملف. كما أننا لا نريد التكرارات في الملف. نظرًا لأن الأوتار سيتم مسحها إلى ملف بمجرد قراءتها ، فإننا لا نحتفظ به في الذاكرة.

لا يمكننا استخدام Hashcode بسبب الاصطدامات في رمز التجزئة بسبب قد نفتقد سلسلة مكررة. نهجان آخران وجدتهما في غوغلينغ:

1. استخدم خوارزمية هضم الرسالة مثل MD5 - ولكن قد يكون حساب وتخزينه مكلفًا للغاية.

2. استخدام خوارزمية الاختبارات. [لست متأكدًا مما إذا كان هذا ينتج مفتاحًا فريدًا لسلسلة- هل يمكن لشخص ما التأكيد

هل هناك أي نهج آخر avaiable. شكرًا.

Answer 1

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

بديل آخر ، ربما مع بصمة ذاكرة أكبر ، هو تخزين السلاسل التي واجهتها بالفعل ، في أ تري (نوع خاص من الشجرة).

---

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

Answer 2

إن تخزين 10 ملايين سلاسل في الذاكرة هو في الواقع الكثير ، لذلك أفهم سبب كتابته على الفور بدلاً من التخزين في مثل أ TreeSet<String> أولا ، ولكن أين هل ترغب في تخزين 10 ملايين المفاتيح العددية الفريدة التي تريد مقارنتها؟ عندما تريد الاحتفاظ بها فريدة من نوعها و عددي (التي لديها الكثير من قاعدة/radix من الحروف) ، لا يمكنك جعل المفتاح أقصر من السلسلة نفسها بالفعل ، لذلك لن تحفظ أي ذاكرة. أو ربما في أعلى نسبة مع ضغط البيانات مثل GZIP ، ولكن هذا سيضيف الكثير من النفقات العامة فقط. MD5 غير مناسب أيضًا منذ سلسلتين مختلفتين تستطيع تسفر عن تجزئة نفس.

لا أرى حقًا حلًا أفضل لهذا الغرض من استخدام RDBMS لائق (قاعدة بيانات SQL) حيث تقوم بتعيين العمود كـ UNIQUE والتعامل مع انتهاك القيد وفقًا لذلك. تم تحسين RDBMS بشكل كبير لهذا النوع من المهام.

إذا لم تتمكن حقًا من التفكير في قاعدة بيانات ، فأنت بحاجة إلى إعادة قراءة الملف لأي إدخال موجود قبل الكتابة/التدفق. ربما ليس سريعًا جدًا ، ولكن بالتأكيد كفاءة الذاكرة.

Answer 3

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

Answer 4

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

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

البديل هو ما بعد العملية للملف بمجرد اكتماله. أمر UNIX SORT جيد جدًا في الملفات الكبيرة (كيف يمكن لأمر UNIX فرز فرز ملف كبير جدًا؟) ، لذلك أتوقع نهج سطر أوامر UNIX القياسي للعمل بشكل معقول:

    sort my-file-of-strings.txt | uniq > my-filtered-file-of-strings.txt

(لاحظ أنه يجب فرز الملفات أولاً قبل الانتقال إلى UNIQ لإزالة التكرارات).

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

Answer 5

إذا كانت الأوتار من مجموعة ثابتة من السلاسل الممكنة (N) ، فيمكنك استخدامها الحد الأدنى من التجزئة لإنشاء صفيف 0 ... N-1. الصفر في الفتحة التي تحددها وظيفة التجزئة المثالية تعني أن السلسلة لم يتم رؤيتها حتى الآن.

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

يمكنك القيام بذلك بكفاءة قدر الإمكان عن طريق رسم خرائط الذاكرة من الملف.

Answer 6

أعتقد حقًا أن الحل الأفضل هو - كما اقترح شخص آخر بالفعل - لاستخدام قاعدة بيانات.

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