التجزئة الوقت المستمر لأسلوت؟

Question

سؤال آخر حول ذلك نشأ المرافق في بعض اللغات إلى سلاسل التجزئة لمنحهم بحثا سريعا في طاولة. مثالين من هذه هي القاموس <> في .NET و {} هيكل التخزين في بيثون. لغات أخرى تؤيد بالتأكيد مثل هذه الآلية. C ++ لها خريطتها، LISP لديه ما يعادله، كما تفعل معظم اللغات الحديثة الأخرى.

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

أنا على دراية خوارزمية Rabin-Karp التي تستخدم وظيفة التجزئة لعملتها، لكن هذه الخوارزمية لا تملي وظيفة تجزئة محددة لاستخدامها، والذي اقترح المؤلفون هو O (م)، حيث م هو طول سلسلة الفحص.

أرى بعض الصفحات الأخرى مثل هذا (http://www.cse.yorku.ca/~oz/hash.html.) التي تعرض بعض خوارزميات التجزئة، ولكن يبدو أن كل منهم يشتكن على كامل طول السلسلة للوصول إلى قيمته.

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

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

أنا أدرك أن أشجار اللاحقة / صفائف و aho-corasick يمكن أن تجلب البحث إلى THETA (م) من أجل مزيد من النفقات في الذاكرة، ولكن ما أسأل على وجه التحديد أنه موجود طريقة تجزئة ثابتة لأسلوت أطوال تعسفية كما كان ادعى من قبل العضو الآخر.

شكرًا.

Answer 1

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

النظر في سلسلة سلسلة يستخدم دائما حرف MIN (N، 20) لحساب التجزئة القياسية. من الواضح أن هذا ينمو كما o (1) بحجم السلسلة. هل سيعمل بشكل موثوق؟ ذلك يعتمد على نطاقك ...

Answer 2

لا تضطر وظيفة التجزئة إلى (ولا أستطيع) إرجاع قيمة فريدة لكل سلسلة.

يمكنك استخدام الأحرف العشرة الأولى لتهيئة مولد أرقام عشوائي ثم استخدام ذلك لسحب 100 حرف عشوائي من السلسلة، والتشش. سيكون هذا وقت ثابت.

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

Answer 3

لا يمكنك بسهولة تحقيق خوارزمية التجزئة في الوقت الثابت للسلاسل دون المخاطرة بالحالات الشديدة من تصادمات التجزئة.

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

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

Answer 4

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

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

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

Answer 5

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

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

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

Answer 6

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

Answer 7

قد تكون مهتما بالنتيجة الرياضية التالية التي توصلت إليها في العام الماضي.

النظر في مشكلة التجزئة العدد اللانهائي من المفاتيح - مثل مجموعة جميع سلاسل أي طول إلى مجموعة الأرقام في {1،2، ...، B}. خلاصة عشوائية عائدات من قبل أول اختيار عشوائي وظيفة تجزئة H في عائلة من وظائف H.

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

اختر أي وظيفة التجزئة H: هناك قيمة تجزئة واحدة على الأقل Y بحيث يتم تعيين مجموعة A = {s: h (s) = y} لا حصر لها، وهذا هو، لديك العديد من سلاسل كثيرة بلا حدود. اختر أي وظيفة تجزئة أخرى H 'و HESH المفاتيح في المجموعة A. هناك قيمة تجزئة واحدة على الأقل Y' مثل أن مجموعة A '= {s موجودة في: h' (s) = y '} غير محدود، وهذا هو، هناك العديد من السلاسل بلا حدود تصادم على وظائف التجزئة. يمكنك تكرار هذه الوسيطة أي عدد من المرات. كررها H مرات. ثم لديك مجموعة لا حصر لها من السلاسل حيث تصطدم جميع الأوتار جميع وظائف Hash الخاصة بك. CQFD.

قراءة متعمقة: تجزئة معقولة من سلاسل متغيرة الطول أمر مستحيلhttp://lemire.me/blog/archives/2009/10/02/sible-hashing-of-fariable-liver-s-is-is-impossible/