>> كيفن شميد: في بعض الأحيان، عند بناء البرنامج، قد ترغب في الاستفادة من
هيكل البيانات المعروفة باسم القاموس.
A خرائط القاموس مفاتيح، والتي هي عادة السلاسل، إلى القيم ورجات،
حرف، مؤشر إلى بعض وجوه، كل ما نريد.
انها مجرد مثل القواميس العادية تلك الخريطة الكلمات من خلال التعاريف.
>> توفر لنا قواميس مع القدرة على تخزين المعلومات
المرتبطة شيئا والبحث عنه في وقت لاحق.
لذلك كيف يمكننا تنفيذ في الواقع القاموس في، ويقول، رمز C ما في وسعنا
استخدام في أحد برامجنا؟
حسنا، هناك الكثير من الطرق التي يمكننا أن تنفيذ القاموس.
>> لأحد، ونحن يمكن استخدام صفيف أننا حيوي إعادة الحجم أو أننا يمكن أن تستخدم
قائمة مرتبطة، جدول التجزئة أو شجرة ثنائية.
ولكن أيا كان علينا أن نختار، يجب علينا أن تضع في اعتبارها كفاءة و
أداء التنفيذ.
علينا أن نفكر في الخوارزمية المستخدمة لإدراج والبحث عن العناصر في
هيكل البيانات المتوفرة لدينا.
>> الآن، دعونا نفترض أننا تريد استخدام سلاسل كمفاتيح.
دعونا نتحدث عن إمكانية واحدة، ودعا هيكل البيانات على TRIE.
حتى هنا تمثيل مرئي من TRIE.
>> كما يوحي صورة أو TRIE هو بنية البيانات شجرة مع
العقد مرتبطة معا.
ونحن نرى أن من الواضح أن هناك الجذرية عقدة مع بعض الروابط تمتد إلى
العقد الأخرى.
ولكن ماذا تتكون كل عقدة؟
لو افترضنا أننا تخزين مفاتيح مع الأحرف الأبجدية فقط، و
نحن لا يهتمون الرسملة، وهنا تعريف العقدة التي
لن يكون كافيا.
>> كائن نوعه هو البنية عقدة من جزأين
دعا البيانات والأطفال.
لقد ترك جزء البيانات كتعليق لتحل محلها مكون
الإعلان عند عقدة هو البنية أدرجت في برنامج C.
الجزء البيانات من عقدة قد تكون قيمة منطقية تشير إلى ما إذا كان أو
لا يمثل عقدة الانتهاء مفتاح القاموس أو قد يكون
سلسلة يمثلون تعريف من كلمة في القاموس.
>> سنستخدم وجه مبتسم للإشارة عندما تكون البيانات موجودة في العقدة.
هناك 26 عناصر في منطقتنا مجموعة الأطفال، مؤشر واحد
لكل حرف أبجدي.
سنرى أهمية هذا في وقت قريب.
>> دعونا الحصول على نظرة فاحصة من عقدة الجذر في الرسم التخطيطي لدينا، والتي لا يوجد لديه البيانات
المرتبطة به، كما يدل على ذلك غياب وجه مبتسم في
جزء البيانات.
الأسهم تمتد من أجزاء من الأطفال مجموعة تمثل غير عقدة
مؤشرات إلى العقد الأخرى.
على سبيل المثال، تمتد من السهم العنصر الثاني للأطفال
يمثل حرف B في مفتاح القاموس.
وفي الرسم البياني أكبر نحن تسميته مع B.
>> لاحظ أنه في الرسم البياني أكبر، ونحن عندما رسم مؤشر إلى عقدة أخرى، فإنه
لا يهم أين رأس السهم وتجتمع تلك العقدة الأخرى.
يحتوي القاموس لدينا عينة TRIE كلمتين، التي والتكبير.
دعونا المشي من خلال مثال لل أبحث احتياطية من البيانات للحصول على مفتاح.
>> لنفترض أننا نريد للبحث عن القيمة المقابلة للحمام مفتاح.
سنبدأ نظرة لدينا ما يصل في عقدة الجذر.
ثم سوف نأخذ الحرف الأول من لدينا مفتاح، B، والعثور على المقابلة
بقعة في أطفالنا صفيف.
لاحظ أن هناك بالضبط 26 البقع في مجموعة، واحدة لكل حرف من
الأبجدية.
وسيكون لدينا تمثل البقع الحروف الأبجدية بالترتيب.
>> سوف نبحث في الفهرس الثاني ثم، مؤشر واحد، لB. وبصفة عامة، إذا كنا
لدينا بعض أبجدية حرف C نحن يمكن تحديد بقعة المقابلة
في مجموعة الأطفال الذين يستخدمون عملية حسابية مثل هذا.
نحن يمكن أن تستخدم للأطفال أكبر مجموعة إذا أردنا أن نقدم نظرة تتكون من
مفاتيح مع مجموعة واسعة من الشخصيات، مثل كامل
مجموعة أحرف ASCII.
>> في هذه الحالة، مؤشر في أطفالنا في مجموعة
مؤشر واحد ليست فارغة.
ولذا فإننا سنواصل أبحث حتى الحمام الرئيسية.
إذا كنا من أي وقت مضى واجه مؤشر فارغة في البقعة المناسبة في الأطفال
مجموعة بينما نحن اجتاز العقد، ثم علينا أن نقول إننا
لا يمكن العثور على أي شيء لهذا المفتاح.
>> الآن، سوف نأخذ الرسالة الثانية من لدينا مفتاح، A، والاستمرار التالية
المؤشرات في هذا الطريق حتى نصل تصل إلى نهاية الرئيسية لدينا.
إذا نصل إلى نهاية المفتاح دون ضرب أي المسدودة، مؤشرات فارغة،
كما هو الحال هنا، ثم نحن فقط يجب أن تحقق أكثر شيء واحد.
هو هذا المفتاح الواقع في القاموس؟
>> إذا كان الأمر كذلك، يجب أن نجد قيمة، وأيضا ل أيقونة وجه مبتسم في الرسم البياني لدينا حيث
كلمة ينتهي.
إذا كان هناك شيء آخر المخزنة مع البيانات، وبعد ذلك يمكننا إعادته.
على سبيل المثال، حديقة الحيوان الرئيسية ليست في القاموس، على الرغم من أننا يمكن أن يكون
وصلت إلى نهاية هذا المفتاح من دون أي وقت مضى ضرب مؤشر فارغة، في حين أننا
تكرار خلال TRIE.
>> إذا حاولنا أن ننظر حتى الحمام الرئيسية، و الثانية لمؤشر مجموعة عقدة الماضي،
المقابلة لحرف H، فإن وقد عقدت مؤشر فارغة.
حتى حمام ليست في القاموس.
ولذا فإن TRIE هي فريدة من نوعها في أن مفاتيح يتم أبدا تخزين صراحة في
بنية البيانات.
لذلك كيف يمكننا إدراج شيء في TRIE؟
>> دعونا ادخال المفتاح حديقة الحيوان في TRIE لدينا.
تذكر أن وجه مبتسم في عقدة يمكن أن تتوافق في التعليمات البرمجية إلى بسيطة
قيمة منطقية تشير إلى أن حديقة الحيوان هو في القاموس أو ما في وسعها
لمزيد من المعلومات تتوافق أننا ترغب في اقترانه حديقة الحيوان الرئيسية،
مثل تعريف كلمة أو أي شيء آخر.
في بعض النواحي، وعملية إدراج شيء في TRIE مشابه ل
يبحث عن شيء ما في TRIE.
>> سنبدأ مع العقدة الجذر مرة أخرى، المؤشرات التالية المقابلة ل
خطابات الرئيسية لدينا.
لحسن الحظ، كنا قادرين على متابعة مؤشرات على طول الطريق حتى وصلنا
نهاية المفتاح.
منذ حديقة الحيوان هو بادئة كلمة التكبير، وهو عضو في
القاموس، ونحن لسنا في حاجة ل تخصيص أي عقد جديد.
>> يمكننا تعديل عقدة للإشارة إلى أن مسار الشخصيات الرائدة ل
لأنها تمثل مفتاح في قاموسنا.
الآن، دعونا نحاول إدراج حمام المفتاح في TRIE.
سنبدأ في عقدة الجذر وتابع المؤشرات مرة أخرى.
ولكن في هذا الوضع، ونحن ضرب بالرصاص تنتهي قبل أن نتمكن من الحصول على
نهاية المفتاح.
الآن، سوف نحتاج إلى تخصيص بعض جديدة سوف تحتاج إلى تخصيص العقد الجديد واحد
عقدة لكل المتبقية خطاب الرئيسية لدينا.
>> في هذه الحالة، نحن بحاجة فقط تخصيص عقدة واحدة جديدة.
ثم سوف نحتاج إلى جعل مؤشر H مرجع هذه العقدة الجديدة.
مرة أخرى، لا يمكننا تعديل عقدة ل تشير إلى أن مسار الشخصيات
مما يؤدي إلى أنه يمثل المفتاح في قاموسنا.
دعونا العقل عن مقارب تعقيد الإجراءات من أجل هذه
عمليتين.
>> نلاحظ أنه في كلتا الحالتين فإن عدد من الخطوات الخوارزمية لدينا أخذت و
يتناسب مع عدد الحروف في الكلمة.
هذا صحيح.
عندما تريد البحث عن كلمة في TRIE تحتاج فقط إلى تكرار خلال
الحروف واحدا تلو الآخر حتى تقوم إما تصل إلى نهاية الكلمة أو
صلت لطريق مسدود في TRIE.
>> وعندما كنت ترغب في إدراج مفتاح الزوج قيمة في TRIE باستخدام
الإجراء ناقشنا، في أسوأ الحالات سيكون عليك أن تخصيص عقدة جديدة
لكل حرف.
ونحن سوف نفترض أن تخصيص هي عملية وقت ثابت.
حتى لو افترضنا أن طول المفتاح هو تحدها ثابت ثابت، على حد سواء
الإدراج والبحث عن ثابتة عمليات الوقت لTRIE.
>> إذا كنا لا تجعل هذا الافتراض أن يحدها طول المفتاح من قبل ثابت
ثابت، ثم الإدراج وبحث، في أسوأ الحالات، هي الخطية في
طول المفتاح.
تلاحظ أن عددا من العناصر المخزنة في TRIE لا يؤثر على نظرة متابعة
أو وقت الإدراج.
لقد أثرت فقط من قبل طول المفتاح.
>> على النقيض من ذلك، إضافة إدخالات إلى، مثلا، جدول تجزئة يميل إلى جعل
المستقبل بالبحث أبطأ.
في حين أن هذا قد يبدو جذابا في البداية، يجب علينا أن نأخذ في الاعتبار أن
تعقيد مقارب مواتية لا يعني أنه في الممارسة البيانات
هيكل هو بالضرورة لا تشوبه أية شائبة.
يجب علينا أيضا أن نعتبر أن لتخزين كلمة في TRIE نحتاج، في أسوأ
حالة، وعدد من العقد النسبي لطول الكلمة نفسها.
>> يحاول تميل إلى استخدام الكثير من الفضاء.
وهذا على النقيض من جدول تجزئة، حيث نحتاج إلى عقدة واحدة جديدة فقط
تخزين بعض الزوج قيمة المفتاح.
الآن، ومرة ​​أخرى من الناحية النظرية، مساحة كبيرة لا يبدو مثل استهلاك كبير
التعامل، وخصوصا ان الحديث أجهزة الكمبيوتر لديها غيغا بايت و
غيغابايت من الذاكرة.
ولكن اتضح أنه لا يزال أمامنا ما يدعو للقلق من استخدام الذاكرة و
المنظمة من أجل الأداء، ومنذ أجهزة الكمبيوتر الحديثة
لديها آليات في مكان تحت هود لتسريع الوصول للذاكرة.
>> ولكن هذه الآليات تعمل بشكل أفضل عندما مصنوعة العدد في الذاكرة المدمجة
المناطق أو المجالات.
والعقد من TRIE يمكن أن يقيم في أي مكان في هذا الكومة.
ولكن هذه هي المقايضات أنه يجب علينا النظر فيها.
>> تذكر أنه عند اختيار البيانات هيكل لمهمة معينة، ونحن
يجب أن نفكر ما هي أنواع عمليات بنية البيانات يحتاج إلى
الدعم ومدى الأداء كل من تلك
المسائل العمليات بالنسبة لنا.
ويمكن لهذه العمليات حتى تتجاوز مجرد
الأساسية حتى نظرة والإدراج.
لنفترض أننا نريد تنفيذ نوع من وظائف الإكمال التلقائي، والكثير
مثل محرك البحث جوجل لا.
وهذا هو، وعودة جميع مفاتيح و يحتمل أن تكون القيم التي
يكون بادئة معينة.
>> A TRIE مفيد فريد لهذه العملية.
انها واضحة لتكرار خلال وTRIE لكل حرف من
البادئة.
تماما مثل البحث عن عمل، نحن يمكن أن تتبع مؤشرات
حرف بحرف.
بعد ذلك، عندما وصلنا إلى نهاية البادئة، ونحن يمكن أن يكرر من خلال
الجزء المتبقي من هيكل البيانات لأن أي من مفاتيح أبعد
هذه النقطة لها البادئة.
>> كما انه من السهل الحصول على هذه القائمة بالترتيب الأبجدي منذ
عناصر من مجموعة الأطفال ومرتبة أبجديا.
لذلك نأمل عليك أن تنظر العطاء يحاول المحاولة.
أنا كيفن شميد، وهذا هو CS50.
>> آه، هذا هو بداية من الانخفاض.
أنا آسف.
آسف.
>> ضرب أربعة.
أنا خارج.
آسف.
آسف لجعل شخص لديه لتحرير هذا بالجنون.
>> آسف.
آسف.
>> سرور 1: أحسنت.
الذي تم القيام به بشكل جيد.