جرب

في علوم الكمبيوتر ، أ ثلاثي ( / ˈtraɪ / , / ˈtriː /^{شجرة البحث}⁽^Trie )، والمعروفة أيضًا باسمالشجرة الرقميةأو^شجرة البادئات،هي بنية بيانات متخصصةتُستخدملتخزين واسترجاع السلاسل النصية من قاموس أو مجموعة. على عكسشجرة البحث الثنائيةموقعكل عقدةداخل الشجرة مفتاحها المرتبط، وتُحدد الروابط بين العقد بواسطةأحرفبدلاً من المفتاح بأكمله.

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

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

التاريخ، أصل الكلمة، والنطق

وُصفت فكرة شجرة البحث (Trie) لتمثيل مجموعة من السلاسل النصية بشكل تجريدي لأول مرة من قِبل أكسل ثيو في عام 1912. ^{[ 2 ]}^{[ 3 ]} ووُصفت أشجار البحث لأول مرة في سياق حاسوبي من قِبل رينيه دي لا بريانديز في عام 1959. ^{[ 4 ]}^{[ 3 ]}^{[ 5 ]}^{: 336}

وُصفت الفكرة بشكل مستقل عام 1960 من قِبل إدوارد فريدكين ، ^{[ 6 ]} الذي صاغ مصطلح "تري" (trie ) ، ونطقه / ˈtriː / (بمعنى "شجرة")، نسبةً إلى المقطع الأوسط من كلمة " ريتريفال " (retrieval ) . ^{[ 7 ]}^{[ 8 ]} مع ذلك، ينطقها مؤلفون آخرون / ˈtraɪ / (بمعنى "تراي") ، في محاولة لتمييزها لفظيًا عن كلمة "تري" (tree). ^{[ 7 ]}^{[ 8 ]}^{[ 3 ]}

ملخص

تُعدّ أشجار البحث (Tries) نوعًا من هياكل بيانات البحث المفهرسة بالسلاسل النصية، وتُستخدم لتخزين قائمة قاموسية من الكلمات التي يمكن البحث فيها بطريقة تسمح بإنشاء قوائم إكمال فعّالة . ^{[ 9 ]}^{[ 10 ]}^{: 1} شجرة البحث البادئة هي هيكل بيانات شجري مُرتب يُستخدم في تمثيل مجموعة من السلاسل النصية على مجموعة أبجدية محدودة، مما يسمح بتخزين الكلمات ذات البادئات المشتركة بكفاءة. ^{[ 1 ]}

تُعدّ أشجار البحث (Trie) فعّالة في خوارزميات البحث عن السلاسل النصية ، مثل التنبؤ بالنصوص ، ومطابقة السلاسل النصية التقريبية ، والتدقيق الإملائي ، مقارنةً بأشجار البحث الثنائية. ^{[ 11 ]}^{[ 8 ]}^{[ 12 ]}^{: 358} ويمكن اعتبار شجرة البحث (Trie) آلةً حتميةً محدودةً على شكل شجرة . ^{[ 13 ]}

العمليات

تدعم أشجار البحث (Tries) عمليات متنوعة: الإضافة، والحذف، والبحث عن مفتاح نصي. تتكون أشجار البحث من عُقد تحتوي على روابط، تشير إما إلى عُقد فرعية أخرى أو إلى قيمة فارغة (null ). وكما هو الحال في أي شجرة، تشير عقدة واحدة فقط، تُسمى العقدة الأب ، إلى كل عقدة باستثناء العقدة الجذرية . تحتوي كل عقدة على عدد من الروابط يساوي عدد الأحرف في الأبجدية المستخدمة (مع أن أشجار البحث تميل إلى احتواء عدد كبير من الروابط الفارغة). في بعض الحالات، تكون الأبجدية المستخدمة هي نفسها أبجدية ترميز الأحرف ، مما ينتج عنه، على سبيل المثال، حجم 128 في حالة ASCII . ^{[ 14 ]}^{: 732}

تؤكد الروابط الفارغة داخل أبناء العقدة على الخصائص التالية: ^{[ 14 ]}^{: 734}^{[ 5 ]}^{: 336}

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

فيما يلي نوع البنية الأساسية للعقد في شجرة البحث: ${\text{Node}}$ قد يحتوي على خيار ${\text{القيمة}}$ ، وهو مرتبط بالمفتاح الذي يتوافق مع العقدة.

عقدة هيكليةبنية نهاية العقدة الفرعية [ حجم الأبجدية ] القيمة نوع البيانات

البحث

يُسترشد البحث عن قيمة في شجرة البحث (Trie) بالأحرف الموجودة في مفتاح سلسلة البحث، حيث تحتوي كل عقدة في الشجرة على رابط لكل حرف مُحتمل في السلسلة المُعطاة. وبالتالي، فإن تتبع السلسلة داخل الشجرة يُؤدي إلى القيمة المُرتبطة بمفتاح السلسلة المُعطى. ويُشير الرابط الفارغ أثناء البحث إلى عدم وجود المفتاح. ^{[ 14 ]}^{: 732-733}

تُنفذ الشفرة الزائفة التالية إجراء البحث عن مفتاح سلسلة نصية مُعطى في شجرة بحث جذرية x . ^[¹⁵^]^:¹³⁵

Trie-Find(x, key) for 0 ≤ i < key.length do if x.Children[key[i]] = nil then return nil end if x := x.Children[key[i]] كرر إرجاع قيمة x

في الشفرة الزائفة أعلاه، يُمثل x مؤشر العقدة الجذرية للشجرة، بينما يُمثل key سلسلة نصية. وتستغرق عملية البحث $O(m)$ الوقت، أين $m$ يمثل حجم مفتاح المعامل النصي . أما في شجرة البحث الثنائية المتوازنة ، فيستغرق الأمر $O(m\log n)$ في أسوأ الأحوال، يجب مقارنة المفتاح مع الوقت. $O(\log n)$ مفاتيح أخرى وكل مقارنة تأخذ $O(m)$ الوقت، في أسوأ الأحوال. ^{[ 12 ]}^{: 358}

تشغل شجرة البحث مساحة أقل، مقارنةً بشجرة البحث الثنائية، في حالة وجود عدد كبير من السلاسل النصية القصيرة، لأن العقد تشترك في تسلسلات فرعية أولية مشتركة وتخزن المفاتيح ضمنيًا. ^{[ 12 ]}^{: 358}

الإدخال

يتم إدخال العناصر في شجرة البحث باستخدام مجموعات الأحرف كمؤشرات لمصفوفة العناصر الفرعية حتى الوصول إلى آخر حرف من مفتاح السلسلة. ^{[ 14 ]}^{: 733-734.} كل عقدة في شجرة البحث تُقابل استدعاءً واحدًا لروتين فرز الجذر ، حيث يعكس هيكل شجرة البحث نمط تنفيذ فرز الجذر من أعلى إلى أسفل. ^{[ 15 ]}^{: 135}

خوارزمية إدخال الشجرة (x، المفتاح، القيمة) لـ 0 ≤ i < طول المفتاح ، إذا كان x.Children[key[i]] = nil ثم x.Children[key[i]] := Create-New-Node() نهاية الشرط x := x.Children[key[i]] كرر قيمة x := القيمة

إذا وُجدت روابط فارغة قبل الوصول إلى الحرف الأخير من مفتاح السلسلة، فسيتم إنشاء عُقد جديدة. ^{[ 14 ]}^{: 745} تُسند قيمة الإدخال إلى قيمة آخر عُقدة تم اجتيازها، وهي العُقدة التي تُطابق المفتاح.

الحذف

تتضمن عملية حذف زوج مفتاح-قيمة من شجرة البحث إيجاد العقدة المقابلة للمفتاح، وتعيين قيمتها إلى قيمة فارغة (null)، ثم إزالة العقد التي ليس لها أبناء بشكل متكرر . ^{[ 14 ]}^{: 740}

دالة حذف الشجرة (x، المفتاح) إذا كان x = nil ، فأرجع nil، وإلا إذا كان المفتاح = "" x.Value := nil آخر x.Children[key[0]] := Trie-Delete(x.Children[key[0]], key[1:]) إذا كانت قيمة x لا تساوي nil، فأرجع x. كرر ذلك من أجل 0 ≤ i < طول x.Children، إذا كانت قيمة x.Children[i] لا تساوي nil، فأرجع x. كرر ذلك ، أرجع nil .

تبدأ العملية بفحص المفتاح ؛ يشير وجود سلسلة نصية فارغة إلى الوصول إلى العقدة المقابلة للمفتاح (الأصلي)، وفي هذه الحالة تُعيّن قيمتها إلى قيمة فارغة (null). إذا كانت قيمة العقدة فارغة (null) وليس لها أبناء، تُزال من الشجرة بإرجاع قيمة فارغة (null)؛ وإلا، تُحتفظ بالعقدة بإرجاعها هي نفسها.

استبدال هياكل البيانات الأخرى

بديل لجداول التجزئة

يمكن استخدام شجرة البحث (Trie) كبديل لجدول التجزئة (Hash Table) ، حيث تتمتع بالمزايا التالية: ^{[ 12 ]}^{: 358}

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

ومع ذلك، فإن الأشجار أقل كفاءة من جدول التجزئة عندما يتم الوصول إلى البيانات مباشرة على جهاز تخزين ثانوي مثل محرك الأقراص الصلبة الذي يتمتع بوقت وصول عشوائي أعلى من الذاكرة الرئيسية . ^{[ 6 ]}

استراتيجيات التنفيذ

يمكن تمثيل أشجار البحث (Trie) بعدة طرق، تتوافق مع مفاضلات مختلفة بين استخدام الذاكرة وسرعة العمليات. ^{[ 5 ]}^{: 341} يستهلك استخدام متجه من المؤشرات لتمثيل شجرة البحث مساحة هائلة؛ ومع ذلك، يمكن تقليل مساحة الذاكرة على حساب وقت التشغيل إذا تم استخدام قائمة مرتبطة أحادية لكل متجه عقدة، حيث أن معظم عناصر المتجه تحتوي على ${\text{nil}}$ [ ³^]^:⁴⁹⁵

قد تُقلل تقنيات مثل اختزال الأبجدية من متطلبات المساحة الكبيرة عن طريق إعادة تفسير السلسلة الأصلية كسلسلة أطول باستخدام أبجدية أصغر. على سبيل المثال، يمكن اعتبار سلسلة من $n بايت كسلسلة من$ $2^n$ وحدة، كل منها مكونة من 4 بتات . يُمكن لهذا أن يُقلل من استخدام الذاكرة بمقدار ثمانية أضعاف؛ ولكن عمليات البحث تتطلب زيارة ضعف عدد العُقد في أسوأ الحالات. ^{[ 5 ]}^{: 347-352.} تتضمن تقنية أخرى تخزين متجه من 256 مؤشر ASCII كخريطة بتات من 256 بت تُمثل أبجدية ASCII، مما يُقلل حجم العُقد الفردية بشكل كبير. ^{[ 16 ]}

محاولات بتية

تُستخدم أشجار البحث الثنائية لمعالجة متطلبات المساحة الهائلة لعقد شجرة البحث في تطبيقات متجه المؤشر البسيطة. يُمثَّل كل حرف في مجموعة مفاتيح السلسلة بواسطة بتات فردية، تُستخدم لاجتياز شجرة البحث على مفتاح السلسلة. تستخدم تطبيقات هذا النوع من أشجار البحث تعليمات وحدة المعالجة المركزية المتجهة للعثور على أول بت مُفعَّل في مُدخل مفتاح ثابت الطول (مثل الدالة المضمنة في GCC ). وبناءً على ذلك، يُستخدم البت المُفعَّل لفهرسة العنصر الأول، أو العقدة الفرعية، في شجرة البحث الثنائية ذات 32 أو 64 مدخلاً. ثم يستمر البحث باختبار كل بت لاحق في المفتاح. ^[¹⁷^]__builtin_clz()

هذا الإجراء محلي في ذاكرة التخزين المؤقت وقابل للتوازي بدرجة عالية نظرًا لاستقلاليته عن السجلات ، وبالتالي فهو فعال على وحدات المعالجة المركزية التي تنفذ العمليات خارج الترتيب . ^{[ 17 ]}

تجارب مضغوطة

شجرة الجذر ، والمعروفة أيضًا باسم شجرة التراي المضغوطة ، هي نسخة مُحسَّنة من شجرة التراي من حيث المساحة، حيث يتم دمج أي عقدة لها ابن واحد فقط مع عقدتها الأصلية؛ ويؤدي حذف فروع العقد ذات الابن الواحد إلى تحسين المقاييس من حيث المساحة والوقت. ^{[ 18 ]}^{[ 19 ]}^{: 452.} ويكون هذا الأسلوب أكثر فعالية عندما تظل شجرة التراي ثابتة، وتكون مجموعة المفاتيح المخزنة متفرقة للغاية ضمن مساحة تمثيلها. ^{[ 20 ]}^{: 3-16}

هناك طريقة أخرى للتعامل مع الأشجار الثابتة وهي "تعبئة" الشجرة عن طريق تخزين مجموعات منفصلة من الأبناء في نفس موقع الذاكرة، بشكل متداخل. ^{[ 8 ]}

أشجار باتريشيا

تمثيل شجرة باتريشيا لمجموعة السلاسل {in, integer, interval, string, structure} .

أشجار باتريشيا هي تطبيق خاص لشجرة البحث الثنائية المضغوطة، تستخدم الترميز الثنائي لمفاتيح السلسلة في تمثيلها. ^{[ 21 ]}^{[ 15 ]}^{: 140} تحتوي كل عقدة في شجرة باتريشيا على فهرس، يُعرف باسم "رقم التخطي"، يخزن فهرس تفرع العقدة لتجنب الأشجار الفرعية الفارغة أثناء الاجتياز. ^{[ 15 ]}^{: 140-141} يستهلك التطبيق البسيط لشجرة البحث مساحة تخزين هائلة بسبب العدد الكبير من العقد الورقية الناتج عن التوزيع المتفرق للمفاتيح؛ يمكن أن تكون أشجار باتريشيا فعالة في مثل هذه الحالات. ^{[ 15 ]}^{: 142}^{[ 22 ]}^{: 3}

يُظهر الشكل على اليمين تمثيلًا لشجرة باتريشيا. يُمثل كل فهرس مجاور للعقد "رقم التخطي" - وهو فهرس البت الذي يُحدد به التفرع. ^{[ 22 ]}^{: 3.} يُقابل رقم التخطي 1 عند العقدة 0 الموضع 1 في ترميز ASCII الثنائي حيث اختلف البت الأيسر في مجموعة المفاتيح $X.$ ^{[ 22 ]}^{: 3-4.} يُعد رقم التخطي بالغ الأهمية للبحث عن العقد وإدراجها وحذفها في شجرة باتريشيا، وتُجرى عملية إخفاء بت خلال كل تكرار. ^{[ 15 ]}^{: 143}

التطبيقات

تُستخدم هياكل بيانات التراي بشكل شائع في النصوص التنبؤية أو قواميس الإكمال التلقائي ، وخوارزميات المطابقة التقريبية . ^{[ 11 ]} تُمكّن التراي من إجراء عمليات بحث أسرع، وتشغل مساحة أقل، خاصةً عندما تحتوي المجموعة على عدد كبير من السلاسل القصيرة، ولذلك تُستخدم في التدقيق الإملائي ، وتطبيقات التوصيل، وخوارزميات مطابقة أطول بادئة . ^{[ 8 ]}^{[ 12 ]}^{: 358.} مع ذلك، إذا كان تخزين كلمات القاموس هو كل ما هو مطلوب (أي لا حاجة لتخزين البيانات الوصفية المرتبطة بكل كلمة)، فإن آلة الحالة المحدودة الحتمية غير الدورية الدنيا (DAFSA) أو شجرة الجذر ستستخدم مساحة تخزين أقل من التراي. وذلك لأن آلات الحالة المحدودة الحتمية غير الدورية الدنيا وأشجار الجذر يمكنها ضغط الفروع المتطابقة من التراي التي تُقابل نفس اللواحق (أو أجزاء) الكلمات المختلفة المخزنة. تُستخدم قواميس السلاسل أيضًا في معالجة اللغة الطبيعية ، مثل إيجاد معجم مجموعة نصوص . ^{[ 23 ]}^{: 73}

فرز

يمكن تنفيذ الفرز المعجمي لمجموعة من مفاتيح السلاسل النصية عن طريق بناء شجرة بحثية (Trie) للمفاتيح المعطاة واجتياز الشجرة بترتيب ما قبل الترتيب ؛ ^{[ 24 ]} وهذا أيضًا شكل من أشكال فرز الجذر . ^{[ 25 ]} تُعد أشجار البحث أيضًا هياكل بيانات أساسية لخوارزمية فرز الاندفاع (burstsort )، والتي تُعرف بكونها أسرع خوارزمية لفرز السلاسل النصية حتى عام 2007، ^{[ 26 ]} وذلك بفضل استخدامها الفعال لذاكرة التخزين المؤقت لوحدة المعالجة المركزية . ^{[ 27 ]}

البحث في النص الكامل

يمكن استخدام نوع خاص من شجرة البحث، يُسمى شجرة اللواحق ، لفهرسة جميع اللواحق في النص لإجراء عمليات بحث سريعة في النص الكامل. ^{[ 28 ]}

محركات البحث على الإنترنت

يُستخدم نوعٌ مُتخصص من شجرة البحث، يُسمى شجرة البحث المضغوطة، في محركات البحث على الإنترنت لتخزين الفهارس - وهي مجموعة من جميع الكلمات القابلة للبحث. ^{[ 29 ]} ترتبط كل عقدة طرفية بقائمة عناوين URL - تُسمى قائمة التكرارات - للصفحات التي تُطابق الكلمة المفتاحية. تُخزن شجرة البحث في الذاكرة الرئيسية، بينما تُحفظ التكرارات في وحدة تخزين خارجية، غالبًا في مجموعات كبيرة ، أو يُشير فهرس الذاكرة إلى مستندات مُخزنة في موقع خارجي. ^{[ 30 ]}

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

تُستخدم أشجار البحث (Trie) في المعلوماتية الحيوية ، ولا سيما في تطبيقات برامج محاذاة التسلسل مثل BLAST ، التي تفهرس جميع السلاسل الفرعية المختلفة ذات الطول k (وتسمى k-mers ) لنص ما عن طريق تخزين مواضع ظهورها في قواعد بيانات تسلسل أشجار البحث المضغوطة. ^{[ 23 ]}^{: 75}

توجيه الإنترنت

تُستخدم نسخ مضغوطة من السلاسل النصية، مثل قواعد البيانات لإدارة قاعدة معلومات التوجيه (FIB)، في تخزين بادئات عناوين IP داخل أجهزة التوجيه والجسور للبحث القائم على البادئات لحل العمليات القائمة على الأقنعة في توجيه IP . ^{[ 23 ]}^{: 75}

انظر أيضاً

مراجع

1 2 معبر، مها (17 نوفمبر 2014). "بنية بيانات التراي" . مركز أبحاث الحوسبة، جامعة غلاسكو . مؤرشف من الأصل في 27 يناير 2021. تم الاطلاع عليه في 17 أبريل 2022 .
^ ثوي ، أكسل (1912). "Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen" . Skrifter Udgivne Af Videnskabs-Selskabet I Christiania . 1912 (1): 1–67 .استشهد به كنوت.
1 2 3 4 كنوت، دونالد (1997). "6.3: البحث الرقمي". فن برمجة الحاسوب، المجلد 3: الفرز والبحث ( الطبعة الثانية). أديسون-ويسلي. ص 492. ISBN 0-201-89685-0.
↑ دي لا بريانديس، رينيه (1959). البحث عن الملفات باستخدام مفاتيح متغيرة الطول (ملف PDF) . وقائع المؤتمر الغربي للحاسوب، الصفحات 295-298 . doi : 10.1145/1457838.1457895 . S2CID 10963780. مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 11 فبراير 2020. استشهد به براس وكنوث.
1 2 3 4 براس، بيتر (8 سبتمبر 2008). هياكل البيانات المتقدمة . المملكة المتحدة : مطبعة جامعة كامبريدج . doi : 10.1017/CBO9780511800191 . ISBN 978-0521880374.
1 2 إدوارد فريدكين (1960). "ذاكرة تراي" . اتصالات رابطة آلات الحوسبة . 3 (9): 490-499 . doi : 10.1145/367390.367400 . S2CID 15384533 .
1 2 بلاك، بول إي. (16-11-2009). "تراي" . قاموس الخوارزميات وهياكل البيانات . المعهد الوطني للمعايير والتكنولوجيا . مؤرشف من الأصل في 29-04-2011.
1 2 3 4 5 فرانكلين مارك ليانغ (1983). تقسيم الكلمات باستخدام الحاسوب (ملف PDF) (أطروحة دكتوراه). جامعة ستانفورد. مؤرشف (ملف PDF) من الأصل بتاريخ 11 نوفمبر 2005. تم الاطلاع عليه بتاريخ 28 مارس 2010 .
↑ "تراي" . كلية الآداب والعلوم، جامعة روتجرز . 2022. مؤرشف من الأصل في 17 أبريل 2022. تم الاسترجاع في 17 أبريل 2022 .
↑ كونلي، ريتشارد هـ.؛ موريس، ف. لوكوود (1993). "تعميم لبنية بيانات الشجرة الثلاثية" . البنى الرياضية في علوم الحاسوب . 5 (3). جامعة سيراكيوز : 381-418 . doi : 10.1017/S0960129500000803 . S2CID 18747244 .
1 2 أهو، ألفريد ف.؛ كوراسيك، مارغريت ج. (يونيو 1975). "مطابقة السلاسل بكفاءة: أداة مساعدة للبحث الببليوغرافي" . اتصالات رابطة آلات الحوسبة . 18 (6): 333-340 . doi : 10.1145/360825.360855 . S2CID 207735784 .
1 2 3 4 5 ثاريجا، ريما (13 أكتوبر 2018). "التجزئة والتصادم". هياكل البيانات باستخدام لغة C ( الطبعة الثانية). مطبعة جامعة أكسفورد . ISBN 9780198099307.
↑ داتشيوك، يان (24 يونيو 2003). مقارنة خوارزميات بناء الأوتوماتا الدنيا، غير الدورية، الحتمية، ذات الحالات المحدودة من مجموعات السلاسل . المؤتمر الدولي حول تنفيذ وتطبيق الأوتوماتا. دار نشر سبرينغر . الصفحات 255-261 . doi : 10.1007/3-540-44977-9_26 . ISBN 978-3-540-40391-3.
1 2 3 4 5 6 سيدجويك، روبرت ؛ واين، كيفن (3 أبريل 2011). الخوارزميات ( الطبعة الرابعة). أديسون-ويسلي ، جامعة برينستون . ISBN 978-0321573513.
1 2 3 4 5 6 غونيت، جي إتش؛ ييتس، آر. بايزا (يناير 1991). دليل الخوارزميات وهياكل البيانات: في باسكال وسي ( الطبعة الثانية). بوسطن ، الولايات المتحدة : أديسون-ويسلي . ISBN 978-0-201-41607-7.
↑ بيليكنز، خافيير (2014). "مخطط ضغط ذاكرة عالي الكفاءة لأنظمة كشف التسلل المُسرّعة بواسطة وحدة معالجة الرسومات". وقائع المؤتمر الدولي السابع لأمن المعلومات والشبكات - SIN '14 . غلاسكو، اسكتلندا، المملكة المتحدة: ACM. الصفحات 302:302–302:309. arXiv : 1704.02272 . doi : 10.1145/2659651.2659723 . ISBN 978-1-4503-3033-6. S2CID 12943246 .
1 2 ويلار، دان إي. (27 يناير 1983). "استعلامات النطاق في أسوأ الحالات اللوغاريتمية ممكنة في مساحة O(n)" . رسائل معالجة المعلومات . 17 (2): 81-84 . doi : 10.1016/0020-0190(83)90075-3 .
↑ سرتاج ساهني (2004). "هياكل البيانات والخوارزميات والتطبيقات في لغة C++: الأشجار" . جامعة فلوريدا . مؤرشف من الأصل في 3 يوليو 2016. تم الاطلاع عليه في 17 أبريل 2022 .
↑ ميهتا، دينش ب.؛ ساهني، سرتاج (7 مارس 2018). "محاولات". دليل هياكل البيانات وتطبيقاتها ( الطبعة الثانية). تشابمان وهول ، جامعة فلوريدا . ISBN 978-1498701853.
↑ جان داتشيوك؛ ستويان ميهوف؛ بروس دبليو. واتسون؛ ريتشارد إي. واتسون (1 مارس 2000). "البناء التدريجي لأوتوماتا الحالة المحدودة غير الدورية الدنيا" . اللغويات الحاسوبية . 26 (1). مطبعة معهد ماساتشوستس للتكنولوجيا : 3-16 . arXiv : cs/0007009 . Bibcode : 2000cs........7009D . doi : 10.1162/089120100561601 .
↑ "شجرة باتريشيا" . المعهد الوطني للمعايير والتكنولوجيا . مؤرشف من الأصل في 14 فبراير 2022. تم الاطلاع عليه في 17 أبريل 2022 .
1 2 3 كروشيمور، ماكسيم؛ ليكروك، تييري (2009). "تراي". موسوعة أنظمة قواعد البيانات . بوسطن ، الولايات المتحدة : دار نشر سبرينغر . Bibcode : 2009eds..book.....L . doi : 10.1007/978-0-387-39940-9 . ISBN 978-0-387-49616-0– عبر HAL (أرشيف مفتوح) .
1 2 3 مارتينيز-بريتو، ميغيل أ.؛ بريسابوا، نيفيس؛ كانوفاس، رودريغو؛ كلود، فرانسيسكو؛ نافارو، غونزالو (مارس 2016). " قواميس السلاسل المضغوطة العملية" . نظم المعلومات . 56. إلسيفير : 73-108 . doi : 10.1016/j.is.2015.08.008 . hdl : 10533/147675 . ISSN 0306-4379 .
↑ كاركاينن، يوها. "المحاضرة 2" (ملف PDF) . جامعة هلسنكي . الترتيب المسبق للعقد في شجرة البحث هو نفسه الترتيب المعجمي للسلاسل التي تمثلها، بافتراض أن أبناء العقدة مرتبون حسب تسميات الحواف.
↑ كاليس، رافائيل (2018). "شجرة الجذر التكيفية (التقرير رقم 14-708-887)" (ملف PDF) . جامعة زيورخ: قسم المعلوماتية، منشورات البحوث .
↑ رانجان سينها وجاستن زوبيل وديفيد رينغ (فبراير 2006). "فرز السلاسل بكفاءة عالية باستخدام النسخ" (ملف PDF) . مجلة ACM للخوارزميات التجريبية . 11 : 1-32 . doi : 10.1145/1187436.1187439 . S2CID 3184411 .
↑ ج. كاركاينن وت. رانتالا (2008). "هندسة فرز الجذر للسلاسل النصية". في أ. أمير وأ. توربين وأ. موفات (محررون). معالجة السلاسل النصية واسترجاع المعلومات، وقائع مؤتمر SPIRE . سلسلة محاضرات في علوم الحاسوب. المجلد 5280. سبرينغر. الصفحات 3-14 . doi : 10.1007/978-3-540-89097-3_3 . ISBN 978-3-540-89096-6.
↑ جيانكارلو، رافاييل (28 مايو 1992). "تعميم لشجرة اللواحق للمصفوفات المربعة، مع تطبيقات" . مجلة SIAM للحوسبة . 24 (3). جمعية الرياضيات الصناعية والتطبيقية : 520-562 . doi : 10.1137/S0097539792231982 . ISSN 0097-5397 .
↑ يانغ، لاي؛ شو، ليدا؛ شي، تشونغتشي (23 مارس 2012). "خوارزمية TRIE محسّنة للتجزئة الديناميكية للبحث المعجمي". نظم معلومات المؤسسات . 6 (4): 419-432 . Bibcode : 2012EntIS...6..419Y . doi : 10.1080/17517575.2012.665483 . S2CID 37884057 .
↑ ترانسير، فريدريك؛ ساندرز، بيتر (ديسمبر 2010). "هندسة الخوارزميات الأساسية لمحرك بحث نصي في الذاكرة" . معاملات ACM لأنظمة المعلومات . 29 (1). رابطة آلات الحوسبة : 1-37 . doi : 10.1145/1877766.1877768 . S2CID 932749 .

روابط خارجية

قاموس الخوارزميات وهياكل البيانات التابع للمعهد الوطني للمعايير والتكنولوجيا: شجرة البحث

[cvr14-1] 1 2 معبر، مها (17 نوفمبر 2014). "بنية بيانات التراي" . مركز أبحاث الحوسبة، جامعة غلاسكو . مؤرشف من الأصل في 27 يناير 2021. تم الاطلاع عليه في 17 أبريل 2022 .

[thue-2] ثوي ، أكسل (1912). "Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen" . Skrifter Udgivne Af Videnskabs-Selskabet I Christiania . 1912 (1): 1–67 .استشهد به كنوت.

[KnuthVol3-3] 1 2 3 4 كنوت، دونالد (1997). "6.3: البحث الرقمي". فن برمجة الحاسوب، المجلد 3: الفرز والبحث ( الطبعة الثانية). أديسون-ويسلي. ص 492. ISBN 0-201-89685-0.

[4] دي لا بريانديس، رينيه (1959). البحث عن الملفات باستخدام مفاتيح متغيرة الطول (ملف PDF) . وقائع المؤتمر الغربي للحاسوب، الصفحات 295-298 . doi : 10.1145/1457838.1457895 . S2CID 10963780. مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 11 فبراير 2020. استشهد به براس وكنوث.

[brass-5] 1 2 3 4 براس، بيتر (8 سبتمبر 2008). هياكل البيانات المتقدمة . المملكة المتحدة : مطبعة جامعة كامبريدج . doi : 10.1017/CBO9780511800191 . ISBN 978-0521880374.

[triememory-6] 1 2 إدوارد فريدكين (1960). "ذاكرة تراي" . اتصالات رابطة آلات الحوسبة . 3 (9): 490-499 . doi : 10.1145/367390.367400 . S2CID 15384533 .

[DADS-7] 1 2 بلاك، بول إي. (16-11-2009). "تراي" . قاموس الخوارزميات وهياكل البيانات . المعهد الوطني للمعايير والتكنولوجيا . مؤرشف من الأصل في 29-04-2011.

[Liang1983-8] 1 2 3 4 5 فرانكلين مارك ليانغ (1983). تقسيم الكلمات باستخدام الحاسوب (ملف PDF) (أطروحة دكتوراه). جامعة ستانفورد. مؤرشف (ملف PDF) من الأصل بتاريخ 11 نوفمبر 2005. تم الاطلاع عليه بتاريخ 28 مارس 2010 .

[9] "تراي" . كلية الآداب والعلوم، جامعة روتجرز . 2022. مؤرشف من الأصل في 17 أبريل 2022. تم الاسترجاع في 17 أبريل 2022 .

[10] كونلي، ريتشارد هـ.؛ موريس، ف. لوكوود (1993). "تعميم لبنية بيانات الشجرة الثلاثية" . البنى الرياضية في علوم الحاسوب . 5 (3). جامعة سيراكيوز : 381-418 . doi : 10.1017/S0960129500000803 . S2CID 18747244 .

[aho75-11] 1 2 أهو، ألفريد ف.؛ كوراسيك، مارغريت ج. (يونيو 1975). "مطابقة السلاسل بكفاءة: أداة مساعدة للبحث الببليوغرافي" . اتصالات رابطة آلات الحوسبة . 18 (6): 333-340 . doi : 10.1145/360825.360855 . S2CID 207735784 .

[reema18-12] 1 2 3 4 5 ثاريجا، ريما (13 أكتوبر 2018). "التجزئة والتصادم". هياكل البيانات باستخدام لغة C ( الطبعة الثانية). مطبعة جامعة أكسفورد . ISBN 9780198099307.

[13] داتشيوك، يان (24 يونيو 2003). مقارنة خوارزميات بناء الأوتوماتا الدنيا، غير الدورية، الحتمية، ذات الحالات المحدودة من مجموعات السلاسل . المؤتمر الدولي حول تنفيذ وتطبيق الأوتوماتا. دار نشر سبرينغر . الصفحات 255-261 . doi : 10.1007/3-540-44977-9_26 . ISBN 978-3-540-40391-3.

[robert11-14] 1 2 3 4 5 6 سيدجويك، روبرت ؛ واين، كيفن (3 أبريل 2011). الخوارزميات ( الطبعة الرابعة). أديسون-ويسلي ، جامعة برينستون . ISBN 978-0321573513.

[gonnet91-15] 1 2 3 4 5 6 غونيت، جي إتش؛ ييتس، آر. بايزا (يناير 1991). دليل الخوارزميات وهياكل البيانات: في باسكال وسي ( الطبعة الثانية). بوسطن ، الولايات المتحدة : أديسون-ويسلي . ISBN 978-0-201-41607-7.

[16] بيليكنز، خافيير (2014). "مخطط ضغط ذاكرة عالي الكفاءة لأنظمة كشف التسلل المُسرّعة بواسطة وحدة معالجة الرسومات". وقائع المؤتمر الدولي السابع لأمن المعلومات والشبكات - SIN '14 . غلاسكو، اسكتلندا، المملكة المتحدة: ACM. الصفحات 302:302–302:309. arXiv : 1704.02272 . doi : 10.1145/2659651.2659723 . ISBN 978-1-4503-3033-6. S2CID 12943246 .

[willar83-17] 1 2 ويلار، دان إي. (27 يناير 1983). "استعلامات النطاق في أسوأ الحالات اللوغاريتمية ممكنة في مساحة O(n)" . رسائل معالجة المعلومات . 17 (2): 81-84 . doi : 10.1016/0020-0190(83)90075-3 .

[18] سرتاج ساهني (2004). "هياكل البيانات والخوارزميات والتطبيقات في لغة C++: الأشجار" . جامعة فلوريدا . مؤرشف من الأصل في 3 يوليو 2016. تم الاطلاع عليه في 17 أبريل 2022 .

[19] ميهتا، دينش ب.؛ ساهني، سرتاج (7 مارس 2018). "محاولات". دليل هياكل البيانات وتطبيقاتها ( الطبعة الثانية). تشابمان وهول ، جامعة فلوريدا . ISBN 978-1498701853.

[20] جان داتشيوك؛ ستويان ميهوف؛ بروس دبليو. واتسون؛ ريتشارد إي. واتسون (1 مارس 2000). "البناء التدريجي لأوتوماتا الحالة المحدودة غير الدورية الدنيا" . اللغويات الحاسوبية . 26 (1). مطبعة معهد ماساتشوستس للتكنولوجيا : 3-16 . arXiv : cs/0007009 . Bibcode : 2000cs........7009D . doi : 10.1162/089120100561601 .

[21] "شجرة باتريشيا" . المعهد الوطني للمعايير والتكنولوجيا . مؤرشف من الأصل في 14 فبراير 2022. تم الاطلاع عليه في 17 أبريل 2022 .

[maxime09-22] 1 2 3 كروشيمور، ماكسيم؛ ليكروك، تييري (2009). "تراي". موسوعة أنظمة قواعد البيانات . بوسطن ، الولايات المتحدة : دار نشر سبرينغر . Bibcode : 2009eds..book.....L . doi : 10.1007/978-0-387-39940-9 . ISBN 978-0-387-49616-0– عبر HAL (أرشيف مفتوح) .

[prieto16-23] 1 2 3 مارتينيز-بريتو، ميغيل أ.؛ بريسابوا، نيفيس؛ كانوفاس، رودريغو؛ كلود، فرانسيسكو؛ نافارو، غونزالو (مارس 2016). " قواميس السلاسل المضغوطة العملية" . نظم المعلومات . 56. إلسيفير : 73-108 . doi : 10.1016/j.is.2015.08.008 . hdl : 10533/147675 . ISSN 0306-4379 .

[24] كاركاينن، يوها. "المحاضرة 2" (ملف PDF) . جامعة هلسنكي . الترتيب المسبق للعقد في شجرة البحث هو نفسه الترتيب المعجمي للسلاسل التي تمثلها، بافتراض أن أبناء العقدة مرتبون حسب تسميات الحواف.

[25] كاليس، رافائيل (2018). "شجرة الجذر التكيفية (التقرير رقم 14-708-887)" (ملف PDF) . جامعة زيورخ: قسم المعلوماتية، منشورات البحوث .

[cachestringsort-26] رانجان سينها وجاستن زوبيل وديفيد رينغ (فبراير 2006). "فرز السلاسل بكفاءة عالية باستخدام النسخ" (ملف PDF) . مجلة ACM للخوارزميات التجريبية . 11 : 1-32 . doi : 10.1145/1187436.1187439 . S2CID 3184411 .

[stringradix-27] ج. كاركاينن وت. رانتالا (2008). "هندسة فرز الجذر للسلاسل النصية". في أ. أمير وأ. توربين وأ. موفات (محررون). معالجة السلاسل النصية واسترجاع المعلومات، وقائع مؤتمر SPIRE . سلسلة محاضرات في علوم الحاسوب. المجلد 5280. سبرينغر. الصفحات 3-14 . doi : 10.1007/978-3-540-89097-3_3 . ISBN 978-3-540-89096-6.

[28] جيانكارلو، رافاييل (28 مايو 1992). "تعميم لشجرة اللواحق للمصفوفات المربعة، مع تطبيقات" . مجلة SIAM للحوسبة . 24 (3). جمعية الرياضيات الصناعية والتطبيقية : 520-562 . doi : 10.1137/S0097539792231982 . ISSN 0097-5397 .

[Xu12-29] يانغ، لاي؛ شو، ليدا؛ شي، تشونغتشي (23 مارس 2012). "خوارزمية TRIE محسّنة للتجزئة الديناميكية للبحث المعجمي". نظم معلومات المؤسسات . 6 (4): 419-432 . Bibcode : 2012EntIS...6..419Y . doi : 10.1080/17517575.2012.665483 . S2CID 37884057 .

[30] ترانسير، فريدريك؛ ساندرز، بيتر (ديسمبر 2010). "هندسة الخوارزميات الأساسية لمحرك بحث نصي في الذاكرة" . معاملات ACM لأنظمة المعلومات . 29 (1). رابطة آلات الحوسبة : 1-37 . doi : 10.1145/1877766.1877768 . S2CID 932749 .

شجرة البحث

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[

[ 16 ]

[

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

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