شجرة بتية مع خريطة بتية

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

محاولات ومحاولات بتية

شجرة البحث ( Trie ) هي نوع من أنواع أشجار البحث، حيث - على عكس شجرة B مثلاً - لا تُخزَّن المفاتيح في العقد، بل في مسار الوصول إلى الأوراق. يُوزَّع المفتاح عبر بنية الشجرة. في شجرة البحث "الكلاسيكية"، تُمثِّل كل عقدة مع فروعها الفرعية رمزًا واحدًا من الأبجدية في موضع واحد (حرف واحد) من المفتاح.

في أشجار البت ، يتم التعامل مع المفاتيح على أنها سلسلة بتات لبعض التمثيل الثنائي ، وتمثل كل عقدة مع فروعها الفرعية قيمة سلسلة فرعية من سلسلة البتات هذه لتشكيل شجرة ثنائية (تحتوي السلسلة الفرعية على بت واحد فقط) أو شجرة n-ary (تحتوي السلسلة الفرعية على بتات متعددة).

لإعطاء مثال يوضح الفرق بين أشجار البحث "الكلاسيكية" وأشجار البحث الثنائية: بالنسبة للأرقام كمفاتيح، يمكن أن تتكون الأبجدية لشجرة البحث من الرموز '0' .. '9' لتمثيل أرقام العدد في النظام العشري، وسيكون للعقد ما يصل إلى 10 أبناء محتملين.

توجد عدة طرق مباشرة لتنفيذ شجرة البحث هذه كهيكل بيانات مادي. على سبيل المثال:

يمكن تمثيل العقدة بمصفوفة من مؤشرات الأبناء لكل رمز من رموز الأبجدية $\Sigma$ – مصفوفة من 10 مؤشرات لكل عقدة في مثال العدد العشري. وهذا يعطي $O(|M|)$ وقت البحث مع $|M|$ يمثل طول المفتاح. لكن هذا ليس فعالاً من حيث المساحة، حيث تحتفظ كل عقدة بمساحة لجميع الرموز الفرعية الممكنة حتى لو لم يكن هناك مفتاح يحقق هذا المسار.
تحتوي العقدة على شجرة ثنائية من أزواج (الرمز، مؤشر الابن)، مرتبة حسب الرمز. يتميز هذا بكفاءة أفضل في استخدام المساحة، لكن وقت البحث الآن هو $O(|M|\cdot \log |\Sigma |)$ . يتميز شجرة البحث المثالية بوقت وصول مستقل عن عدد المفاتيح المخزنة.

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

شجرة بتية مع خريطة بتية

قدّم باجويل ^{[ 1 ]} حلاً فعالاً من حيث الوقت والمساحة لشجرة التراي يُسمى شجرة المصفوفة المُرتبطة (AMT). وتعتمد شجرة التراي المُرتبطة بمصفوفة التجزئة (HAMT) على AMT. يستخدم تمثيل عقدة التراي المُدمج خريطة بتية لتمييز كل فرع صالح - أي شجرة تراي بتية مع خريطة بتية . تستخدم AMT ثماني خرائط بتية 32 بت لكل عقدة لتمثيل شجرة تراي 256-ary قادرة على تمثيل تسلسل 8 بت لكل عقدة. مع وحدات المعالجة المركزية 64 بت ( الحوسبة 64 بت )، يتمثل أحد الاختلافات في وجود شجرة تراي 64-ary مع خريطة بتية واحدة فقط 64 بت لكل عقدة قادرة على تمثيل تسلسل 6 بت ^{[ 2 ]} .

لتحديد فهرس مؤشر الابن لعقدة ما لقيمة معينة مكونة من 6 بتات، يجب حساب عدد مؤشرات الأبناء السابقة. وقد تبين أن هذه العملية يمكن تنفيذها بكفاءة عالية.

اجتياز العقدة

long bitMap = mem [ nodeIdx ] ; long bitPos = 1L << value ; // قيمة 6 بت if (( bitMap & bitPos ) == 0 ) return false ; // لم يتم العثور على العقدة childNodeIdx = mem [ nodeIdx + 1 + Long.bitCount ( bitMap & ( bitPos - 1 ) ) ] ;

يُحسب الإزاحة اللازمة لإيجاد الفهرس بناءً على فهرس العقدة الحالي بعدد البتات الأقل أهمية المُفعّلة في خريطة البتات قبل الموضع المستهدف، مضافًا إليها واحد لخريطة البتات نفسها. يمكن حساب عدد البتات الأقل أهمية المُفعّلة بكفاءة عالية وبتعقيد زمني ثابت باستخدام عمليات بت بسيطة وعملية CTPOP (عدّ البتات المُفعّلة) التي تُحدد عدد البتات المُفعّلة، والمتوفرة في جافا باسم Long.bitCount(). ويمكن تنفيذ CTPOP بكفاءة عالية باستخدام تقنية "التعديل على البتات" ^{[ 3 ]} ، بل إن العديد من وحدات المعالجة المركزية الحديثة تُوفر CTPOP كتعليمات مُخصصة تُعاملها المُترجمات كدالة مُضمنة .

int CTPOP ( long x ) { // تنفيذ "مُعدَّل" لدالة عدّ السكان. x -= (( x >>> 1 ) & 0x55555555555555555L ); x = ( x & 0x3333333333333333L ) + (( x >>> 2 ) & 0x3333333333333333L ); x = ( x + ( x >>> 4 )) & 0x0f0f0f0f0f0f0f0fL ; x += ( x >>> 8 ); x += ( x >>> 16 ); x += ( x >>> 32 ); return x & 0x7f ; }

مثال على تنفيذ المجموعة

بنية البيانات المادية

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

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

يتم تضمين العقد الورقية: بدلاً من وجود مؤشر فرعي إلى عقدة ورقية، يتم تخزين الصورة النقطية للعقدة الورقية نفسها.

public class BBTrieSet {long [] mem ; long [] freeLists ; long freeIdx ;جذر طويل ؛ عدد طويل ؛// الحد الأقصى لحجم العقدة هو 1 (خريطة البت) + 64 (مؤشرات الأبناء أو قيم الأوراق) + 1 لأن المصفوفات تبدأ من الصفر. final static int FREE_LIST_SIZE = 1 + 64 + 1 ;final static int KNOWN_EMPTY_NODE = 0 ; final static int KNOWN_DELETED_NODE = 1 ; final static int HEADER_SIZE = 2 ; // KNOWN_EMPTY_NODE, KNOWN_DELETED_NODEpublic BBTrieSet ( int size ) { mem = new long [ size ] ; freeLists = new long [ FREE_LIST_SIZE ] ; freeIdx = HEADER_SIZE ; root = KNOWN_EMPTY_NODE ; count = 0 ; }private long allocate ( int size ) { long free = freeLists [ size ] ; if ( free != 0 ) { // الحجم المطلوب متوفر في قائمة free، أعد الربط وأرجع رأس freeLists [ size ] = mem [ ( int ) free ] ; return free ; } else { // هل هناك حاجة للتوسيع؟ if ( freeIdx + size > mem.length ) { // زيادة بنسبة 25 % والتأكد من كفايته int currSize = mem.length ; int newSize = currSize + Math.max ( currSize / 4 , size ) ; mem = Arrays.copyOf ( mem , newSize ) ; }long idx = freeIdx ; freeIdx += size ; return idx ; } }دالة خاصة طويلة allocateInsert ( long nodeIdx , int size , int childIdx ) { long newNodeRef = allocate ( size + 1 );int a = ( int ) newNodeRef ; int b = ( int ) nodeIdx ;// نسخ مع ترك مسافة للفرع for ( int j = 0 ; j < childIdx ; j ++ ) mem [ a ++] = mem [ b ++] ; a ++ ; // إدراج for ( int j = childIdx ; j < size ; j ++ ) mem [ a ++] = mem [ b ++] ;إلغاء التخصيص ( nodeIdx ، size )؛return newNodeRef ; } private long allocateDelete ( long nodeIdx , int size , int childIdx ) { long newNodeRef = allocate ( size - 1 );// نسخ مع إزالة العنصر الفرعي int a = ( int ) newNodeRef ; int b = ( int ) nodeIdx ; for ( int j = 0 ; j < childIdx ; j ++ ) mem [ a ++] = mem [ b ++] ; b ++ ; // تمت الإزالة for ( int j = childIdx + 1 ; j < size ; j ++ ) mem [ a ++] = mem [ b ++] ; deallocate ( nodeIdx , size );return newNodeRef ; }private void deallocate ( long idx , int size ) { if ( idx == KNOWN_EMPTY_NODE ) return ; // الاحتفاظ بالعقدة الفارغة المعروفة// أضف إلى رأس قائمة العناصر الحرة mem [ ( int ) idx ] = freeLists [ size ] ; freeLists [ size ] = idx ; }private long createLeaf ( byte [] key , int off , int len ) { long newNodeRef = allocate ( 2 ); int a = ( int ) newNodeRef ; mem [ a ++] = 1L << key [ len - 2 ] ; mem [ a ] = 1L << key [ len - 1 ] ; // القيمة len -= 3 ; while ( len >= off ) { long newParentNodeRef = allocate ( 2 ); a = ( int ) newParentNodeRef ; mem [ a ++] = 1L << key [ len-- ] ; mem [ a ] = newNodeRef ; newNodeRef = newParentNodeRef ; } return newNodeRef ; }private long insertChild ( long nodeRef , long bitMap , long bitPos , int idx , long value ) { int size = Long.bitCount ( bitMap ) ; long newNodeRef = allocateInsert ( nodeRef , size + 1 , idx + 1 ); mem [ ( int ) newNodeRef ] = bitMap | bitPos ; mem [ ( int ) newNodeRef + 1 + idx ] = value ; return newNodeRef ; } private long removeChild ( long nodeRef , long bitMap , long bitPos , int idx ) { int size = Long.bitCount ( bitMap ) ; if ( size > 1 ) { // لا يزال للعقدة أبناء آخرون / تغادر long newNodeRef = allocateDelete ( nodeRef , size + 1 , idx + 1 ) ; mem [ ( int ) newNodeRef ] = bitMap & ~ bitPos ; return newNodeRef ; } else { // العقدة فارغة الآن، قم بإزالتها deallocate ( nodeRef , size + 1 ); return KNOWN_DELETED_NODE ; } }public long size () { return count ; }}

عمليات المجموعة

يحتوي على مفتاح

تختبر دالة get ما إذا كان المفتاح جزءًا من المجموعة. يتم تسليم المفتاح على شكل مصفوفة بايتات، حيث يمثل كل بايت تسلسلًا من 6 بتات للمفتاح - لذا يتم استخدام 6 بتات فقط من أصل 8 بتات لكل بايت.

public boolean get ( byte [] key , int len ) { if ( root == KNOWN_EMPTY_NODE ) return false ;long nodeRef = root ; int off = 0 ; for (;;) { long bitMap = mem [ ( int ) nodeRef ] ; long bitPos = 1L << key [ off ++] ; // انتبه للزيادة if (( bitMap & bitPos ) == 0 ) return false ; // غير موجودlong value = mem [ ( int ) nodeRef + 1 + Long . bitCount ( bitMap & ( bitPos - 1 )) ] ;إذا كان ( off == len - 1 ) { // عند الورقة long bitPosLeaf = 1L << key [ off ] ; return (( value & bitPosLeaf ) != 0 ); } else { // مؤشر الابن nodeRef = value ; } } }

مفتاح التعيين (إضافة)

public boolean set ( byte [] key , int len ) { long nodeRef = set ( root , key , 0 , len ); if ( nodeRef != KNOWN_EMPTY_NODE ) { // يشير إلى تغيير عدد العناصر ++ ; root = nodeRef ; return true ; } else return false ; }private long set ( long nodeRef , byte [] key , int off , int len ) { long bitMap = mem [ ( int ) nodeRef ] ; long bitPos = 1L << key [ off ++] ; // انتبه للزيادة int idx = Long.bitCount ( bitMap & ( bitPos - 1 ) );إذا كان ( bitMap & bitPos ) يساوي صفرًا ، فهذا يعني أن العنصر الفرعي غير موجود بعد . إذا كان ( off == len - 1 ) ، فإن value = 1L << key [ off ] ؛ وإلا فإن value = createLeaf ( key , off , len ) ؛ ثم تُرجع insertChild ( nodeRef , bitMap , bitPos , idx , value ) . أما إذا كان ( off == len - 1 ) ، فهذا يعني أن العنصر الفرعي موجود . إذا كان ( off == len - 1 ) ، فهذا يعني أن bitPosLeaf موجود في الورقة . إذا كان ( value & bitPosLeaf ) يساوي صفرًا ، فهذا يعني أن bitMap الورقة موجود بالفعل . ثم تُرجع KNOWN_EMPTY_NODE . } else { // ليس عند العقدة الطرفية، تكرار طويل childNodeRef = value ; طويل newChildNodeRef = set ( childNodeRef , key , off , len ); إذا ( newChildNodeRef == KNOWN_EMPTY_NODE ) إرجاع KNOWN_EMPTY_NODE ; إذا ( newChildNodeRef != childNodeRef ) mem [ ( int ) nodeRef + 1 + idx ] =newChildNodeRef ; return nodeRef ; } } }

مسح (إزالة) المفتاح

public boolean clear ( byte [] key , int len ) { long nodeRef = clear ( root , key , 0 , len ); if ( nodeRef ! = KNOWN_EMPTY_NODE ) { count-- ; if ( nodeRef == KNOWN_DELETED_NODE ) root = KNOWN_EMPTY_NODE ; else root = nodeRef ; return true ; } else return false ; }public long clear ( long nodeRef , byte [] key , int off , int len ) { if ( root == KNOWN_EMPTY_NODE ) return KNOWN_EMPTY_NODE ;long bitMap = mem [ ( int ) nodeRef ] ; long bitPos = 1L << key [ off ++] ; // انتبه للزيادة ++ إذا كان (( bitMap & bitPos ) == 0 ) { // العنصر الفرعي غير موجود، المفتاح غير موجود return KNOWN_EMPTY_NODE ; } else { // العنصر الفرعي موجود int idx = Long.bitCount ( bitMap & ( bitPos - 1 )); long value = mem [ ( int ) nodeRef + 1 + idx ] ; إذا كان ( off == len - 1 ) { // عند الورقة long bitPosLeaf = 1L << key [ off ] ; إذا كان (( value & bitPosLeaf ) == 0 ) // المفتاح غير موجود return KNOWN_EMPTY_NODE ; else { // مسح البت في الورقة value = value & ~ bitPosLeaf ; إذا كانت القيمة لا تساوي صفرًا ، فسيتم الاحتفاظ بالعقدة الطرفية مع تحديث قيمة ` mem [ ( int ) nodeRef + 1 + idx ] ` إلى القيمة الحالية ، ثم يتم إرجاع `nodeRef` . وإلا ، فسيتم إرجاع `removeChild ( nodeRef , bitMap , bitPosLeaf , idx )`. أما إذا لم تكن العقدة الطرفية موجودة، فسيتم تعيين قيمة `childNodeRef` إلى `value` ، ثم يتم مسح `newChildNodeRef` باستخدام `clear ( childNodeRef , key , off , len )`. إذا كانت قيمة `newChildNodeRef` تساوي صفرًا ، فسيتم إرجاع القيمة الحالية .إذا كانت قيمة `KNOWN_EMPTY_NODE` تساوي `KNOWN_DELETED_NODE` ، فسيتم إرجاع ` KNOWN_EMPTY_NODE` . إذا كانت قيمة `newChildNodeRef` تساوي `KNOWN_DELETED_NODE` ، فسيتم إرجاع `removeChild ( nodeRef , bitMap , bitPos , idx )`. إذا كانت قيمة ` newChildNodeRef` لا تساوي `childNodeRef` ، فسيتم تعيين `mem [ ( int ) nodeRef + 1 + idx ] ` إلى ` newChildNodeRef` . ثم يتم إرجاع `nodeRef` .}

عوامل المجموعة

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

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

واجهة وزن خفيف

واجهة عامة BBTrieNode { دالة عامة طويلة getBitMap (); دالة عامة طويلة getBitMapLeaf ( long bitPos ); دالة عامة BBTrieNode getChildNode ( long bitPos ); } فئة ثابتة عامة BBTrieNodeMem تُنفذ واجهة BBTrieNode {long nodeRef ; long [] mem ;BBTrieNodeMem child ;public BBTrieNodeMem ( long nodeRef , long [] mem ) { this . nodeRef = nodeRef ; this . mem = mem ; }@Override public long getBitMap () { return mem [ ( int ) nodeRef ] ; }@Override public long getBitMapLeaf ( long bitPos ) { int idx = Long . bitCount ( getBitMap () & ( bitPos - 1 )); long value = mem [ ( int ) nodeRef + 1 + idx ] ; return value ; }@Override public BBTrieNode getChildNode ( long bitPos ) { int idx = Long.bitCount ( getBitMap ( ) & ( bitPos - 1 )); long value = mem [ ( int ) nodeRef + 1 + idx ] ; return new BBTrieNodeMem ( value , mem ) ; } }

التقاطع (و)

يُعدّ عامل التقاطع فعالاً للغاية لأنه يُجري عملية التقليم تلقائيًا حتى على التعبيرات الفرعية. لا حاجة للوصول إلى العقد الفرعية غير ذات الصلة لأن خريطة البتات وعملية AND المنطقية تسمح بتحديد النتيجة مسبقًا. على سبيل المثال، حساب $\{1,2,3\}\cap (\{2,3,4\}\cup \{5,6,7\})=\{2,3\}$ ، التعبير الفرعي $\{2,3,4\}\cup \{5,6,7\}=\{2,3,4,5,6,7\}$ لن تتحقق كنتيجة وسيطة.

public static class BBTrieAnd implements BBTrieNode { BBTrieNode nodeA ; BBTrieNode nodeB ; long bitMapA ; long bitMapB ;public BBTrieAnd ( BBTrieNode nodeA , BBTrieNode nodeB ) { this.nodeA = nodeA ; this.nodeB = nodeB ; bitMapA = nodeA.getBitMap ( ) ; bitMapB = nodeB.getBitMap ( ) ; } public long getBitMap ( ) { return bitMapA & bitMapB ; // هذا يُحسّن الأداء ( التقليم ) } public long getBitMapLeaf ( long bitPos ) { return nodeA.getBitMapLeaf ( bitPos ) & nodeB.getBitMapLeaf ( bitPos ) ; } public BBTrieNode getChildNode ( long bitPos ) { BBTrieNode childNodeA = nodeA.getChildNode ( bitPos ) ; BBTrieNode childNodeB = nodeB.getChildNode ( bitPos ) ; إرجاع BBTrieAnd ( ChildNodeA , ChildNodeB ) الجديد ; }}

الاتحاد (أوريغون)

public static class BBTrieOr implements BBTrieNode { BBTrieNode nodeA ; BBTrieNode nodeB ; long bitMapA ; long bitMapB ;public BBTrieOr ( BBTrieNode nodeA , BBTrieNode nodeB ) { this.nodeA = nodeA ; this.nodeB = nodeB ; bitMapA = nodeA.getBitMap ( ) ; bitMapB = nodeB.getBitMap ( ) ; } public long getBitMap ( ) { return bitMapA | bitMapB ; } public long getBitMapLeaf ( long bitPos ) { return nodeA.getBitMapLeaf ( bitPos ) | nodeB.getBitMapLeaf ( bitPos ) ; } public BBTrieNode getChildNode ( long bitPos ) { if ( ( bitMapA & bitPos ) ! = 0 ) { BBTrieNode childNodeA = nodeA.getChildNode ( bitPos ) ; if ( ( bitMapB & bitPos ) ! = 0 ) { BBTrieNode childNodeB = nodeB . getChildNode ( bitPos ); return new BBTrieOr ( childNodeA , childNodeB ); } else return childNodeA ; // تحسين، لا حاجة إلى عقدة OR } else { BBTrieNode childNodeB = nodeB.getChildNode ( bitPos ) ; return childNodeB ; // تحسين، لا حاجة إلى عقدة OR } }}

الفرق (ناقص)

public static class BBTrieMinus implements BBTrieNode { BBTrieNode nodeA ; BBTrieNode nodeB ; long bitMapA ; long bitMapB ; public BBTrieMinus ( BBTrieNode nodeA , BBTrieNode nodeB ) { this . nodeA = nodeA ; this . nodeB = nodeB ; bitMapA = nodeA . getBitMap (); bitMapB = nodeB . getBitMap (); } public long getBitMap () { return bitMapA ; // bitMapB غير مفيد هنا } public long getBitMapLeaf ( long bitPos ) { long childBitMapA = nodeA . getBitMapLeaf ( bitPos ); if (( bitMapB & bitPos ) == 0 ) return childBitMapA ; long childBitMapB = nodeB . getBitMapLeaf ( bitPos ); return childBitMapA & ~ childBitMapB ; } public BBTrieNode getChildNode ( long bitPos ) { BBTrieNode childNodeA = nodeA.getChildNode ( bitPos ); if ( ( bitMapB & bitPos ) == 0 ) return childNodeA ; // تحسين، لا حاجة إلى عقدة سالبة BBTrieNode childNodeB = nodeB.getChildNode ( bitPos ) ; return new BBTrieMinus ( childNodeA , childNodeB ) ; }}

نطاقات

باستخدام أسلوب العقدة الافتراضية، يمكن إنجاز استعلامات النطاق عن طريق تقاطع شجرة بحث افتراضية لتوليد النطاق (انظر أدناه) مع عامل تشغيل آخر. لذا، لتحديد أي أرقام من مجموعة، على سبيل المثال $\{10,20,30,40,50,60,61,62,63\}$ ، تقع ضمن نطاق معين، ولنقل [10..50]، بدلاً من المرور عبر المجموعة والتحقق من كل عنصر، يتم ذلك عن طريق التقييم $\{10,20,30,40,50,60,61,62,63\}\cap \{10,..,50\}$ .

public static class BBTrieIntRange implements BBTrieNode { private long bitMap ; private int a , b ; private int x , y ; private int level ; public BBTrieIntRange ( int a , int b ) { this ( a , b , 5 ); }private BBTrieIntRange ( int a , int b , int level ) { this.a = a ; this.b = b ; this.level = level ; x = ( int ) ( a >>> ( level * 6 ) ) & 0x3F ; y = ( int ) ( b >>> ( level * 6 ) ) & 0x3F ; // خدعة بتية for: for (int i = x; i <= y; i++) bitSet |= (1L << i); bitMap = 1L << y ; bitMap | = bitMap - 1 ; bitMap & = ~ ( ( 1L << x ) - 1 ) ; }public long getBitMap () { return bitMap ; } public long getBitMapLeaf ( long bitPos ) { // حل بسيط لسهولة القراءة (ليس فعالاً للغاية لأنه يتم إنشاء عنصر فرعي جديد في كل استدعاء) return getChildNode ( bitPos ) .getBitMap (); }public BBTrieIntRange getChildNode ( long bitPos ) { int bitNum = Long.numberOfTrailingZeros ( bitPos ); if ( x == y ) return new BBTrieIntRange ( a , b , level - 1 ) ; else if ( bitNum == x ) return new BBTrieIntRange ( a , ~ 0x0 , level - 1 ); else if ( bitNum == y ) return new BBTrieIntRange ( 0 , b , level - 1 ) ; else return new BBTrieIntRange ( 0 , ~ 0x0 , level - 1 ); }}

مثال على الاستخدام

يوضح المثال كيفية الاستخدام باستخدام الأعداد الصحيحة ذات 32 بت كمفاتيح.

public class BBTrieSetSample {واجهة عامة باسم Visitor { دالة عامة void visit ( بايت [] مفتاح ، عدد صحيح طول المفتاح ); } دالة عامة ثابتة void visit ( عقدة BBTrieNode عقدة ، زائر زائر ، بايت [] مفتاح ، عدد صحيح إيقاف ، عدد صحيح طول ) { طويل bitMap = عقدة . getBitMap (); إذا ( bitMap == 0 ) إرجاع ; طويل bits = bitMap ; بينما ( bits != 0 ) { طويل bitPos = bits & - bits ; bits ^= bitPos ; // الحصول على البت الأيمن ومسحه عدد صحيح bitNum = طويل . numberOfTrailingZeros ( bitPos ); مفتاح [ إيقاف ] = ( بايت ) bitNum ; إذا ( إيقاف == طول - 2 ) { طويل value = عقدة . getBitMapLeaf ( bitPos ); طويل bits2 = value ; بينما ( bits2 != 0 ) { طويل bitPos2 = bits2 & - bits2 ; bits2 ^= bitPos2 ; int bitNum2 = Long . numberOfTrailingZeros ( bitPos2 ); key [ off + 1 ] = ( byte ) bitNum2 ; visitor . visit ( key , off + 2 ); } } else { BBTrieNode childNode = node . getChildNode ( bitPos); زيارة ( childNode , visitor , key , off + 1 , len ); } } } public static int set6Int ( byte [] b , int value ) { int pos = 0 ; b [ pos ] = ( byte ) (( value >>> 30 ) & 0x3F ); b [ pos + 1 ] = ( byte ) (( value >>> 24 ) & 0x3F ); b [ pos + 2 ] = ( byte ) (( value >>> 18 ) & 0x3F ); b [ pos + 3 ] = ( byte ) (( value >>> 12 ) & 0x3F ); b [ pos + 4 ] = ( byte ) (( value >>> 6 ) & 0x3F ); b [ pos + 5 ] = ( byte ) ( value & 0x3F ); return 6 ; }public static int get6Int ( byte [] b ) { int pos = 0 ; return (( b [ pos ] & 0x3F ) << 30 ) | (( b [ pos + 1 ] & 0x3F ) << 24 ) | (( b [ pos + 2 ] & 0x3F ) << 18 ) | (( b [ pos + 3 ] & 0x3F ) << 12 ) | (( b [ pos + 4 ] & 0x3F ) << 6 ) | ( b [ pos + 5 ] & 0x3F ); }public static void main ( String [] args ) { BBTrieSet trie1 = new BBTrieSet ( 100 ); BBTrieSet trie2 = new BBTrieSet ( 100 );byte [] key = new byte [ 64 ] ; int len ; final int KEY_LEN_INT = set6Int ( key , 1 ); // 6int [] test = new int [ ] { 10 , 20 , 30 , 40 , 50 , 30 , 60 , 61 , 62 , 63 }; for ( int i = 0 ; i < test.length ; i ++ ) { len = set6Int ( key , test [ i ] ); boolean change = trie1.set ( key , len ); System.out.println ( " set : " + test [ i ] + " , " + change ) ; } System.out.println ( " trie1 size : " + trie1.size ( ) ) ;BBTrieSetOps.visit ( new BBTrieNodeMem ( trie1.root , trie1.mem ) , new BBTrieSetOps.Visitor ( ) { @Override public void visit ( byte [ ] key , int keyLen ) { System.out.println ( " الزائر : " + get6Int ( key ) + " " , " + keyLen ) ; } } , key , 0 , KEY_LEN_INT ) ;test = new int [] { 10 , 25 , 30 , 40 , 45 , 50 , 55 , 60 } ; for ( int i = 0 ; i < test.length ; i ++ ) { len = set6Int ( key , test [ i ] ); boolean containd = trie1.get ( key , len ) ; System.out.println ( " contained : " + test [ i ] + " , " + containd ) ; }test = new int [ ] { 10 , 20 , 30 , 40 , 45 , 50 , 55 , 60 , 61 , 62 , 63 }; for ( int i = 0 ; i < test.length ; i ++ ) { len = set6Int ( key , test [ i ] ) ; boolean change = trie1.clear ( key , len ); System.out.println ( " تم المسح : " + test [ i ] + " , " + change ) ; BBTrieSetOps . زيارة ( BBTrieNodeMem جديد ( trie1.root ، trie1.mem ) ، BBTrieSetOps جديد . Visitor ( ) { @Override public void visit ( byte [ ] key ، int keyLen ) { System.out.print ( get6Int ( key ) + " " ) ; } } , key ، 0 ، KEY_LEN_INT ) ; System.out.println ( ) ;System.out.println ( " حجم شجرة البحث الأولى: " + trie1.size ( ) ) ;for ( int i = 0 ; i < = 50 ; i ++ ) { len = set6Int ( key , i ); trie1.set ( key , len ); System.out.println ( " set : " + i ) ; } System.out.println ( " trie1 size : " + trie1.size ( ) ) ;for ( int i = 25 ; i < = 75 ; i ++ ) { len = set6Int ( key , i ); trie2.set ( key , len ); System.out.println ( " set : " + i ) ; } System.out.println ( " trie2 size : " + trie2.size ( ) ) ;// مثال AND BBTrieNode result = new BBTrieAnd ( new BBTrieNodeMem ( trie1 . root , trie1 . mem ), new BBTrieNodeMem ( trie2 . root , trie2 . mem ));BBTrieSetOps.visit ( result , new BBTrieSetOps.Visitor ( ) { @Override public void visit ( byte [ ] key , int keyLen ) { System.out.println ( " Visitor AND result: " + get6Int ( key ) ) ; } } , key , 0 , KEY_LEN_INT ) ;} }

مراجع

^ فيل باجويل (2000). عمليات بحث سريعة وفعالة في المساحة (PDF) (أبلغ عن). قسم علوم المعلومات، المدرسة الفيدرالية للفنون التطبيقية في لوزان .
↑ براءة اختراع أوروبية رقم 3376407 ، والتر باور، "الاستخدام الفعال لبنية بيانات الشجرة في قواعد البيانات"، نُشرت في 19 سبتمبر 2018، وصدرت في 16 سبتمبر 2020، ومُسجلة باسم شركة سينشير إيه جي.
↑ وارن الابن، هنري س. (2013). متعة المخترق ( الطبعة الثانية). أديسون ويسلي - بيرسون للتعليم، المحدودة. ISBN 978-0-321-84268-8.

[bagwell-1] فيل باجويل (2000). عمليات بحث سريعة وفعالة في المساحة (PDF) (أبلغ عن). قسم علوم المعلومات، المدرسة الفيدرالية للفنون التطبيقية في لوزان .

[bauer-2] براءة اختراع أوروبية رقم 3376407 ، والتر باور، "الاستخدام الفعال لبنية بيانات الشجرة في قواعد البيانات"، نُشرت في 19 سبتمبر 2018، وصدرت في 16 سبتمبر 2020، ومُسجلة باسم شركة سينشير إيه جي.

[Warren_2013-3] وارن الابن، هنري س. (2013). متعة المخترق ( الطبعة الثانية). أديسون ويسلي - بيرسون للتعليم، المحدودة. ISBN 978-0-321-84268-8.

[ 1 ]

[ 2 ]

[ 3 ]

اللغة	العربية (RTL)
روابط موسوعية	20 رابطاً
المصدر الأصلي	ويكيبيديا ↗