كشف التغييرات في المدخلات المرتبة بشكل عشوائي (وظيفة التجزئة؟)

Question

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

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

Answer 1

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

Answer 2

لذلك لديك مدخلات مثل

A B C D
D E F G
C B A D

وتحتاج إلى اكتشاف أن السطرين الأول والثالث متطابقان؟

Answer 3

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

Answer 4

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

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

Answer 5

إذا قمت بإضافة قيم ASCII لكل حرف، فستحصل على نفس النتيجة بغض النظر عن الترتيب.

(قد يكون هذا مبسطًا بعض الشيء، ولكنه ربما يثير فكرة بالنسبة لك.راجع لآلئ البرمجة، القسم 2.8، للحصول على قصة مثيرة للاهتمام.)

Answer 6

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

يجب تجربة طريقة التجزئة فقط إذا لم يكن من الضروري أن تفوت تغييرًا أو تكتشف تغييرًا لا يوجد فيه أي تغيير.

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

• إذا واجهت خطًا به عدد صفر (أو لا يوجد إدخال للخريطة على الإطلاق)، فقد رأيت خطًا لم تتوقعه.
• إذا أنهيت هذا مع بقاء إدخالات غير صفرية في الخريطة، فلن ترى شيئًا كنت تتوقعه.

Answer 7

حسنًا، مواصفات المشكلة محدودة بعض الشيء.

كما أفهم أنك ترغب في معرفة ما إذا كانت عدة سلاسل تحتوي على نفس العناصر بغض النظر عن الترتيب.

على سبيل المثال:

A B C
C B A

هي نفسها.

طريقة القيام بذلك هي إنشاء مجموعة من القيم ثم مقارنة المجموعات.لإنشاء مجموعة قم بما يلي:

HashSet set = new HashSet();
foreach (item : string) {
   set.add(item);
}

ثم قم فقط بمقارنة محتويات المجموعات من خلال المرور عبر إحدى المجموعات ومقارنتها مع المجموعات الأخرى.سيكون وقت التنفيذ O(N) بدلاً من O(NlogN) بالنسبة لمثال الفرز