بنية بيانات الاسترجاع

في علوم الحاسوب ، بنية بيانات الاسترجاع ، والمعروفة أيضًا باسم الدالة الثابتة ، هي نوع بيانات يشبه القاموس فعال من حيث المساحة ويتكون من مجموعة من أزواج (المفتاح، القيمة) التي تسمح بالعمليات التالية: ^{[ 1 ]}

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

ويمكن اعتبارها أيضًا دالة${\displaystyle b\colon \,{\mathcal {U}}\to \{0,1\}^{r}}$من أجل الكون${\displaystyle {\mathcal {U}}}$ومجموعة المفاتيح${\displaystyle S\subseteq {\mathcal {U}}}$حيث يجب أن تُعيد عملية الاسترجاع${\displaystyle b(x)}$لأي قيمة${\displaystyle x\in S}$وقيمة عشوائية من${\displaystyle \{0,1\}^{r}}$خلاف ذلك.

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

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

لنفترض على سبيل المثال البسيط${\displaystyle n}$تُعرض أسماء ألعاب الفيديو مع إضافة قيمة منطقية (Boolean) تُشير إلى ما إذا كانت اللعبة تحتوي على كلب يمكن مداعبته. يمكن لدالة ثابتة مُنشأة من قاعدة البيانات هذه إعادة إنتاج العلامة المرتبطة بجميع الأسماء الموجودة في المجموعة الأصلية، وعلامة أخرى اختيارية لأسماء أخرى. يمكن تصغير حجم هذه الدالة الثابتة إلى 10 ...${\displaystyle (1+\epsilon )n}$قطع صغيرة${\displaystyle \epsilon }$وهو أقل بكثير من أي تمثيل قائم على الأزواج. ^{[ 1 ]}

بالنظر إلى مجموعة من${\displaystyle n}$أزواج المفتاح والقيمة، حيث تكون كل قيمة${\displaystyle r}$البتات، وهي بنية بيانات استرجاع تستخدم${\displaystyle rv+k}$يقال إن البتات تحتوي على فائض${\displaystyle k}$ينبغي أن تتميز بنية بيانات الاسترجاع المثالية بانخفاض التكرار، مع دعمها للاسترجاع السريع. ^{[ 2 ]}

في الإطار الثابت، حيث تقتصر العمليات على الإنشاء والاسترجاع، من الممكن إنشاء حلول مع وجود فائض${\displaystyle k=o(n)}$^{[ 2 ] [ 3 ]} ومع ذلك ، اعتمادًا على نظام المعلمات، ليس من الممكن دائمًا تحقيق هذا القدر الضئيل من التكرار مع دعم الاسترجاع في وقت ثابت. ^{[ 4 ]} على سبيل المثال، إذا${\displaystyle r=\Theta (\log n)}$وبافتراض أن طول الكلمات الآلية${\displaystyle w=\Theta (\log n)}$أي حل يتضمن استعلامات استرجاع ثابتة الوقت يجب أن يتضمن تكرارًا${\displaystyle k=\Omega (n)}$[ ^{4 ]​}

تتغير نسبة التكرار الأمثل بشكل كبير إذا أخذنا في الاعتبار الإصدارات غير الثابتة للمشكلة.

• في مشكلة استرجاع القيم الديناميكية ، حيث يجب أن يدعم هيكل البيانات عملية التحديث، يكون التكرار الأمثل هو${\displaystyle k=\Theta (n)}$بغض النظر عن قيمة${\displaystyle r}$وبغض النظر عن كفاءة الوقت. ^{[ 5 ]} علاوة على ذلك، عندما${\displaystyle r=\omega (1)}$يُعتقد أن التكرار الأمثل، حتى الحدود ذات الرتبة المنخفضة، يتم تحقيقه بواسطة دالة تجزئة مثالية دنيا . ^{[ 5 ]}
• في مشكلة الاسترجاع الديناميكي ، يجب أن يدعم هيكل البيانات عمليات الإدراج والحذف على مجموعة أزواج المفاتيح والقيم، بسعة قصوى${\displaystyle n}$يعتمد ذلك على حجم المجموعة في أي لحظة معينة. بافتراض وجود مفاتيح من مجموعة كبيرة بحجم متعدد الحدود، فإن التكرار الأمثل لهذه النسخة من المشكلة هو${\displaystyle k=\Theta (n\log \log n)}$أجزاء، حتى لو${\displaystyle r=1}$^{[ 6 ] [ 7 ]} علاوة على ذلك ، إذا كان قيد السعة لـ${\displaystyle n}$إذا تمت إزالته، فسيظل من الممكن تحقيق التكرار${\displaystyle k=\Theta (n_{\text{max}}\log \log n_{\text{max}})}$، أين${\displaystyle n_{\text{max}}}$وهو أكبر حجم وصلت إليه المجموعة حتى الآن. ^{[ 8 ]}
• في مشكلة الاسترجاع التدريجي ، يجب أن يدعم هيكل البيانات عمليات الإدراج على مجموعة أزواج المفاتيح والقيم، بسعة قصوى${\displaystyle n}$يعتمد ذلك على حجم المجموعة. في هذا السياق، يكون التكرار الأمثل هو${\displaystyle k=o(n)}$البتات، كما هو الحال في الإعداد الثابت. ^{[ 7 ]}

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

استرجاع XOR

يمكن تصنيف المرشحات المُجزأة حسب استعلاماتها إلى مرشحات OR وAND وXOR. على سبيل المثال، مرشح بلوم هو مرشح AND لأنه يُرجع القيمة "صحيح" لاستعلام العضوية إذا تطابقت جميع المواقع المُستهدفة. تعمل مرشحات XOR فقط مع عمليات الاسترجاع الثابتة، وهي الأنسب لبناء أنظمة فعالة من حيث المساحة. ^{[ 9 ]} يتم بناؤها عن طريق حل نظام خطي يضمن أن يُرجع الاستعلام لكل مفتاح القيمة "صحيح".

بناء

بافتراض دالة تجزئة${\displaystyle h}$التي تربط كل مفتاح بمتجه بت بطول${\displaystyle m\geq \left\vert S\right\vert =n}$حيث الجميع${\displaystyle (h(x))_{x\in S}}$إذا كانت المعادلات الخطية التالية مستقلة خطيًا، فإن النظام التالي من المعادلات الخطية له حل.${\displaystyle Z\in \{0,1\}^{m\times r}}$:

${\displaystyle (h(x)\cdot Z=b(x))_{x\in S}}$

وبالتالي، تُعطى الدالة الساكنة بالصيغة التالية:${\displaystyle h}$و${\displaystyle Z}$ويهيمن على استخدام المساحة${\displaystyle Z}$وهو ما يعادل تقريبًا${\displaystyle (1+\epsilon )n}$بت لكل مفتاح لـ${\displaystyle m=(1+\epsilon )n}$، يُفترض أن دالة التجزئة صغيرة.

استرجاع لـ${\displaystyle x\in {\mathcal {U}}}$يمكن التعبير عنها كعملية XOR ثنائية للصفوف${\displaystyle Z_{i}}$لجميع البتات المحددة${\displaystyle i}$ل${\displaystyle h(x)}$علاوة على ذلك، تتطلب الاستعلامات السريعة بيانات متفرقة${\displaystyle h(x)}$وبالتالي فإن المشاكل التي يجب حلها لهذه الطريقة هي إيجاد دالة تجزئة مناسبة مع القدرة على حل نظام المعادلات الخطية بكفاءة.

استعادة الشريط

باستخدام مصفوفة عشوائية متفرقة${\displaystyle h}$يجعل ذلك عمليات الاسترجاع غير فعالة من حيث ذاكرة التخزين المؤقت لأنها تصل إلى معظم${\displaystyle Z}$بنمط عشوائي غير محلي. يعمل استرجاع الشريط على تحسين ذلك من خلال إعطاء كل${\displaystyle h(x)}$شريط متتالي من العرض${\displaystyle w={\mathcal {O}}(\log n/\epsilon )}$حيث يتم تعيين البتات بشكل عشوائي. ^{[ 9 ]}

باستخدام خصائص${\displaystyle (h(x))_{x\in S}}$المصفوفة${\displaystyle Z}$يمكن حسابها في${\displaystyle {\mathcal {O}}(n/\epsilon ^{2})}$الوقت المتوقع: تعمل خوارزمية الشريط عن طريق فرز الصفوف أولاً حسب موقعها الابتدائي (مثل فرز العد ). بعد ذلك، يمكن إنشاء نموذج REM بشكل تكراري عن طريق إجراء عمليات على الصفوف التي تلي الصف الحالي مباشرةً، مما يؤدي إلى حذف جميع القيم التي تساوي 1 في جميع الأعمدة التي تلي أول قيمة تساوي 1 في هذا الصف. لا تُنتج عمليات الصفوف أي قيم خارج الشريط، وهي غير مكلفة للغاية لأنها تتطلب فقط عملية XOR.${\displaystyle {\mathcal {O}}(\log n/\epsilon )}$أجزاء يمكن القيام بها في${\displaystyle {\mathcal {O}}(1/\epsilon )}$الوقت على ذاكرة الوصول العشوائي (RAM) . يمكن إثبات أن الكمية المتوقعة لعمليات الصف هي${\displaystyle {\mathcal {O}}(n/\epsilon )}$وأخيرًا، يتم الحصول على الحل عن طريق التعويض العكسي. ^{[ 10 ]}