1
00:00:00,000 --> 00:00:07,700

2
00:00:07,700 --> 00:00:10,890
>> كيفن شميد: في بعض الأحيان، عند بناء
البرنامج، قد ترغب في الاستفادة من

3
00:00:10,890 --> 00:00:13,190
هيكل البيانات المعروفة باسم القاموس.

4
00:00:13,190 --> 00:00:17,960
A خرائط القاموس مفاتيح، والتي هي
عادة السلاسل، إلى القيم ورجات،

5
00:00:17,960 --> 00:00:21,900
حرف، مؤشر إلى بعض وجوه،
كل ما نريد.

6
00:00:21,900 --> 00:00:26,510
انها مجرد مثل القواميس العادية
تلك الخريطة الكلمات من خلال التعاريف.

7
00:00:26,510 --> 00:00:29,440
>> توفر لنا قواميس مع
القدرة على تخزين المعلومات

8
00:00:29,440 --> 00:00:32,750
المرتبطة شيئا
والبحث عنه في وقت لاحق.

9
00:00:32,750 --> 00:00:36,620
لذلك كيف يمكننا تنفيذ في الواقع
القاموس في، ويقول، رمز C ما في وسعنا

10
00:00:36,620 --> 00:00:38,460
استخدام في أحد برامجنا؟

11
00:00:38,460 --> 00:00:41,790
حسنا، هناك الكثير من الطرق التي
يمكننا أن تنفيذ القاموس.

12
00:00:41,790 --> 00:00:45,930
>> لأحد، ونحن يمكن استخدام صفيف أننا
حيوي إعادة الحجم أو أننا يمكن أن تستخدم

13
00:00:45,930 --> 00:00:49,150
قائمة مرتبطة، جدول التجزئة
أو شجرة ثنائية.

14
00:00:49,150 --> 00:00:52,250
ولكن أيا كان علينا أن نختار، يجب علينا
أن تضع في اعتبارها كفاءة و

15
00:00:52,250 --> 00:00:54,300
أداء التنفيذ.

16
00:00:54,300 --> 00:00:57,930
علينا أن نفكر في الخوارزمية المستخدمة
لإدراج والبحث عن العناصر في

17
00:00:57,930 --> 00:00:59,120
هيكل البيانات المتوفرة لدينا.

18
00:00:59,120 --> 00:01:03,060
>> الآن، دعونا نفترض أننا
تريد استخدام سلاسل كمفاتيح.

19
00:01:03,060 --> 00:01:07,290
دعونا نتحدث عن إمكانية واحدة،
ودعا هيكل البيانات على TRIE.

20
00:01:07,290 --> 00:01:11,210
حتى هنا تمثيل مرئي
من TRIE.

21
00:01:11,210 --> 00:01:14,590
>> كما يوحي صورة أو TRIE
هو بنية البيانات شجرة مع

22
00:01:14,590 --> 00:01:16,050
العقد مرتبطة معا.

23
00:01:16,050 --> 00:01:19,420
ونحن نرى أن من الواضح أن هناك الجذرية
عقدة مع بعض الروابط تمتد إلى

24
00:01:19,420 --> 00:01:20,500
العقد الأخرى.

25
00:01:20,500 --> 00:01:23,040
ولكن ماذا تتكون كل عقدة؟

26
00:01:23,040 --> 00:01:26,700
لو افترضنا أننا تخزين مفاتيح
مع الأحرف الأبجدية فقط، و

27
00:01:26,700 --> 00:01:30,150
نحن لا يهتمون الرسملة،
وهنا تعريف العقدة التي

28
00:01:30,150 --> 00:01:31,100
لن يكون كافيا.

29
00:01:31,100 --> 00:01:34,130
>> كائن نوعه هو البنية
عقدة من جزأين

30
00:01:34,130 --> 00:01:35,740
دعا البيانات والأطفال.

31
00:01:35,740 --> 00:01:39,200
لقد ترك جزء البيانات كتعليق
لتحل محلها مكون

32
00:01:39,200 --> 00:01:43,190
الإعلان عند عقدة هو البنية
أدرجت في برنامج C.

33
00:01:43,190 --> 00:01:47,040
الجزء البيانات من عقدة قد تكون
قيمة منطقية تشير إلى ما إذا كان أو

34
00:01:47,040 --> 00:01:51,160
لا يمثل عقدة الانتهاء
مفتاح القاموس أو قد يكون

35
00:01:51,160 --> 00:01:54,240
سلسلة يمثلون تعريف
من كلمة في القاموس.

36
00:01:54,240 --> 00:01:58,870
>> سنستخدم وجه مبتسم للإشارة
عندما تكون البيانات موجودة في العقدة.

37
00:01:58,870 --> 00:02:02,310
هناك 26 عناصر في منطقتنا
مجموعة الأطفال، مؤشر واحد

38
00:02:02,310 --> 00:02:03,690
لكل حرف أبجدي.

39
00:02:03,690 --> 00:02:06,570
سنرى أهمية
هذا في وقت قريب.

40
00:02:06,570 --> 00:02:10,759
>> دعونا الحصول على نظرة فاحصة من عقدة الجذر
في الرسم التخطيطي لدينا، والتي لا يوجد لديه البيانات

41
00:02:10,759 --> 00:02:14,740
المرتبطة به، كما يدل على ذلك
غياب وجه مبتسم في

42
00:02:14,740 --> 00:02:16,110
جزء البيانات.

43
00:02:16,110 --> 00:02:19,910
الأسهم تمتد من أجزاء من
الأطفال مجموعة تمثل غير عقدة

44
00:02:19,910 --> 00:02:21,640
مؤشرات إلى العقد الأخرى.

45
00:02:21,640 --> 00:02:25,500
على سبيل المثال، تمتد من السهم
العنصر الثاني للأطفال

46
00:02:25,500 --> 00:02:28,400
يمثل حرف B
في مفتاح القاموس.

47
00:02:28,400 --> 00:02:31,920
وفي الرسم البياني أكبر
نحن تسميته مع B.

48
00:02:31,920 --> 00:02:35,810
>> لاحظ أنه في الرسم البياني أكبر، ونحن عندما
رسم مؤشر إلى عقدة أخرى، فإنه

49
00:02:35,810 --> 00:02:39,100
لا يهم أين رأس السهم
وتجتمع تلك العقدة الأخرى.

50
00:02:39,100 --> 00:02:43,850
يحتوي القاموس لدينا عينة TRIE
كلمتين، التي والتكبير.

51
00:02:43,850 --> 00:02:47,040
دعونا المشي من خلال مثال لل
أبحث احتياطية من البيانات للحصول على مفتاح.

52
00:02:47,040 --> 00:02:50,800
>> لنفترض أننا نريد للبحث عن
القيمة المقابلة للحمام مفتاح.

53
00:02:50,800 --> 00:02:53,610
سنبدأ نظرة لدينا ما يصل
في عقدة الجذر.

54
00:02:53,610 --> 00:02:57,870
ثم سوف نأخذ الحرف الأول من لدينا
مفتاح، B، والعثور على المقابلة

55
00:02:57,870 --> 00:03:00,020
بقعة في أطفالنا صفيف.

56
00:03:00,020 --> 00:03:04,490
لاحظ أن هناك بالضبط 26 البقع
في مجموعة، واحدة لكل حرف من

57
00:03:04,490 --> 00:03:05,330
الأبجدية.

58
00:03:05,330 --> 00:03:08,800
وسيكون لدينا تمثل البقع
الحروف الأبجدية بالترتيب.

59
00:03:08,800 --> 00:03:13,960
>> سوف نبحث في الفهرس الثاني ثم،
مؤشر واحد، لB. وبصفة عامة، إذا كنا

60
00:03:13,960 --> 00:03:17,990
لدينا بعض أبجدية حرف C نحن
يمكن تحديد بقعة المقابلة

61
00:03:17,990 --> 00:03:21,520
في مجموعة الأطفال الذين يستخدمون
عملية حسابية مثل هذا.

62
00:03:21,520 --> 00:03:25,140
نحن يمكن أن تستخدم للأطفال أكبر
مجموعة إذا أردنا أن نقدم نظرة تتكون من

63
00:03:25,140 --> 00:03:28,380
مفاتيح مع مجموعة واسعة من الشخصيات،
مثل كامل

64
00:03:28,380 --> 00:03:29,880
مجموعة أحرف ASCII.

65
00:03:29,880 --> 00:03:32,630
>> في هذه الحالة، مؤشر
في أطفالنا في مجموعة

66
00:03:32,630 --> 00:03:34,320
مؤشر واحد ليست فارغة.

67
00:03:34,320 --> 00:03:36,600
ولذا فإننا سنواصل أبحث
حتى الحمام الرئيسية.

68
00:03:36,600 --> 00:03:40,130
إذا كنا من أي وقت مضى واجه مؤشر فارغة
في البقعة المناسبة في الأطفال

69
00:03:40,130 --> 00:03:43,230
مجموعة بينما نحن اجتاز العقد،
ثم علينا أن نقول إننا

70
00:03:43,230 --> 00:03:45,630
لا يمكن العثور على أي شيء لهذا المفتاح.

71
00:03:45,630 --> 00:03:49,370
>> الآن، سوف نأخذ الرسالة الثانية من
لدينا مفتاح، A، والاستمرار التالية

72
00:03:49,370 --> 00:03:52,400
المؤشرات في هذا الطريق حتى نصل
تصل إلى نهاية الرئيسية لدينا.

73
00:03:52,400 --> 00:03:56,530
إذا نصل إلى نهاية المفتاح دون
ضرب أي المسدودة، مؤشرات فارغة،

74
00:03:56,530 --> 00:03:59,730
كما هو الحال هنا، ثم نحن فقط
يجب أن تحقق أكثر شيء واحد.

75
00:03:59,730 --> 00:04:02,110
هو هذا المفتاح الواقع
في القاموس؟

76
00:04:02,110 --> 00:04:07,660
>> إذا كان الأمر كذلك، يجب أن نجد قيمة، وأيضا ل
أيقونة وجه مبتسم في الرسم البياني لدينا حيث

77
00:04:07,660 --> 00:04:08,750
كلمة ينتهي.

78
00:04:08,750 --> 00:04:12,270
إذا كان هناك شيء آخر المخزنة مع
البيانات، وبعد ذلك يمكننا إعادته.

79
00:04:12,270 --> 00:04:16,500
على سبيل المثال، حديقة الحيوان الرئيسية ليست في
القاموس، على الرغم من أننا يمكن أن يكون

80
00:04:16,500 --> 00:04:19,810
وصلت إلى نهاية هذا المفتاح من دون أي وقت مضى
ضرب مؤشر فارغة، في حين أننا

81
00:04:19,810 --> 00:04:21,089
تكرار خلال TRIE.

82
00:04:21,089 --> 00:04:25,436
>> إذا حاولنا أن ننظر حتى الحمام الرئيسية، و
الثانية لمؤشر مجموعة عقدة الماضي،

83
00:04:25,436 --> 00:04:28,750
المقابلة لحرف H، فإن
وقد عقدت مؤشر فارغة.

84
00:04:28,750 --> 00:04:31,120
حتى حمام ليست في القاموس.

85
00:04:31,120 --> 00:04:34,800
ولذا فإن TRIE هي فريدة من نوعها في أن مفاتيح
يتم أبدا تخزين صراحة في

86
00:04:34,800 --> 00:04:36,650
بنية البيانات.

87
00:04:36,650 --> 00:04:38,810
لذلك كيف يمكننا إدراج شيء
في TRIE؟

88
00:04:38,810 --> 00:04:41,780
>> دعونا ادخال المفتاح
حديقة الحيوان في TRIE لدينا.

89
00:04:41,780 --> 00:04:46,120
تذكر أن وجه مبتسم في عقدة
يمكن أن تتوافق في التعليمات البرمجية إلى بسيطة

90
00:04:46,120 --> 00:04:50,170
قيمة منطقية تشير إلى أن حديقة الحيوان
هو في القاموس أو ما في وسعها

91
00:04:50,170 --> 00:04:53,710
لمزيد من المعلومات تتوافق أننا
ترغب في اقترانه حديقة الحيوان الرئيسية،

92
00:04:53,710 --> 00:04:56,860
مثل تعريف
كلمة أو أي شيء آخر.

93
00:04:56,860 --> 00:05:00,350
في بعض النواحي، وعملية إدراج
شيء في TRIE مشابه ل

94
00:05:00,350 --> 00:05:02,060
يبحث عن شيء ما في TRIE.

95
00:05:02,060 --> 00:05:05,720
>> سنبدأ مع العقدة الجذر مرة أخرى،
المؤشرات التالية المقابلة ل

96
00:05:05,720 --> 00:05:07,990
خطابات الرئيسية لدينا.

97
00:05:07,990 --> 00:05:11,310
لحسن الحظ، كنا قادرين على متابعة مؤشرات
على طول الطريق حتى وصلنا

98
00:05:11,310 --> 00:05:12,770
نهاية المفتاح.

99
00:05:12,770 --> 00:05:16,480
منذ حديقة الحيوان هو بادئة كلمة
التكبير، وهو عضو في

100
00:05:16,480 --> 00:05:19,440
القاموس، ونحن لسنا في حاجة ل
تخصيص أي عقد جديد.

101
00:05:19,440 --> 00:05:23,140
>> يمكننا تعديل عقدة للإشارة إلى أن
مسار الشخصيات الرائدة ل

102
00:05:23,140 --> 00:05:25,360
لأنها تمثل مفتاح في قاموسنا.

103
00:05:25,360 --> 00:05:28,630
الآن، دعونا نحاول إدراج
حمام المفتاح في TRIE.

104
00:05:28,630 --> 00:05:32,260
سنبدأ في عقدة الجذر
وتابع المؤشرات مرة أخرى.

105
00:05:32,260 --> 00:05:35,620
ولكن في هذا الوضع، ونحن ضرب بالرصاص
تنتهي قبل أن نتمكن من الحصول على

106
00:05:35,620 --> 00:05:36,940
نهاية المفتاح.

107
00:05:36,940 --> 00:05:40,980
الآن، سوف نحتاج إلى تخصيص بعض جديدة
سوف تحتاج إلى تخصيص العقد الجديد واحد

108
00:05:40,980 --> 00:05:43,660
عقدة لكل المتبقية
خطاب الرئيسية لدينا.

109
00:05:43,660 --> 00:05:46,740
>> في هذه الحالة، نحن بحاجة فقط
تخصيص عقدة واحدة جديدة.

110
00:05:46,740 --> 00:05:50,590
ثم سوف نحتاج إلى جعل مؤشر H
مرجع هذه العقدة الجديدة.

111
00:05:50,590 --> 00:05:54,070
مرة أخرى، لا يمكننا تعديل عقدة ل
تشير إلى أن مسار الشخصيات

112
00:05:54,070 --> 00:05:57,120
مما يؤدي إلى أنه يمثل
المفتاح في قاموسنا.

113
00:05:57,120 --> 00:06:00,730
دعونا العقل عن مقارب
تعقيد الإجراءات من أجل هذه

114
00:06:00,730 --> 00:06:02,110
عمليتين.

115
00:06:02,110 --> 00:06:06,420
>> نلاحظ أنه في كلتا الحالتين فإن عدد
من الخطوات الخوارزمية لدينا أخذت و

116
00:06:06,420 --> 00:06:09,470
يتناسب مع عدد
الحروف في الكلمة.

117
00:06:09,470 --> 00:06:10,220
هذا صحيح.

118
00:06:10,220 --> 00:06:13,470
عندما تريد البحث عن كلمة في
TRIE تحتاج فقط إلى تكرار خلال

119
00:06:13,470 --> 00:06:17,100
الحروف واحدا تلو الآخر حتى تقوم إما
تصل إلى نهاية الكلمة أو

120
00:06:17,100 --> 00:06:19,060
صلت لطريق مسدود في TRIE.

121
00:06:19,060 --> 00:06:22,470
>> وعندما كنت ترغب في إدراج مفتاح
الزوج قيمة في TRIE باستخدام

122
00:06:22,470 --> 00:06:26,250
الإجراء ناقشنا، في أسوأ الحالات
سيكون عليك أن تخصيص عقدة جديدة

123
00:06:26,250 --> 00:06:27,550
لكل حرف.

124
00:06:27,550 --> 00:06:31,290
ونحن سوف نفترض أن تخصيص
هي عملية وقت ثابت.

125
00:06:31,290 --> 00:06:35,850
حتى لو افترضنا أن طول المفتاح هو
تحدها ثابت ثابت، على حد سواء

126
00:06:35,850 --> 00:06:39,400
الإدراج والبحث عن ثابتة
عمليات الوقت لTRIE.

127
00:06:39,400 --> 00:06:42,930
>> إذا كنا لا تجعل هذا الافتراض أن
يحدها طول المفتاح من قبل ثابت

128
00:06:42,930 --> 00:06:46,650
ثابت، ثم الإدراج وبحث،
في أسوأ الحالات، هي الخطية في

129
00:06:46,650 --> 00:06:48,240
طول المفتاح.

130
00:06:48,240 --> 00:06:51,800
تلاحظ أن عددا من العناصر المخزنة
في TRIE لا يؤثر على نظرة متابعة

131
00:06:51,800 --> 00:06:52,820
أو وقت الإدراج.

132
00:06:52,820 --> 00:06:55,360
لقد أثرت فقط من قبل
طول المفتاح.

133
00:06:55,360 --> 00:06:59,300
>> على النقيض من ذلك، إضافة إدخالات إلى، مثلا،
جدول تجزئة يميل إلى جعل

134
00:06:59,300 --> 00:07:01,250
المستقبل بالبحث أبطأ.

135
00:07:01,250 --> 00:07:04,520
في حين أن هذا قد يبدو جذابا في البداية،
يجب علينا أن نأخذ في الاعتبار أن

136
00:07:04,520 --> 00:07:08,740
تعقيد مقارب مواتية لا
يعني أنه في الممارسة البيانات

137
00:07:08,740 --> 00:07:11,410
هيكل هو بالضرورة
لا تشوبه أية شائبة.

138
00:07:11,410 --> 00:07:15,860
يجب علينا أيضا أن نعتبر أن لتخزين
كلمة في TRIE نحتاج، في أسوأ

139
00:07:15,860 --> 00:07:19,700
حالة، وعدد من العقد النسبي
لطول الكلمة نفسها.

140
00:07:19,700 --> 00:07:21,880
>> يحاول تميل إلى استخدام الكثير من الفضاء.

141
00:07:21,880 --> 00:07:25,620
وهذا على النقيض من جدول تجزئة،
حيث نحتاج إلى عقدة واحدة جديدة فقط

142
00:07:25,620 --> 00:07:27,940
تخزين بعض الزوج قيمة المفتاح.

143
00:07:27,940 --> 00:07:31,370
الآن، ومرة ​​أخرى من الناحية النظرية، مساحة كبيرة
لا يبدو مثل استهلاك كبير

144
00:07:31,370 --> 00:07:34,620
التعامل، وخصوصا ان الحديث
أجهزة الكمبيوتر لديها غيغا بايت و

145
00:07:34,620 --> 00:07:36,180
غيغابايت من الذاكرة.

146
00:07:36,180 --> 00:07:39,200
ولكن اتضح أنه لا يزال أمامنا
ما يدعو للقلق من استخدام الذاكرة و

147
00:07:39,200 --> 00:07:42,540
المنظمة من أجل
الأداء، ومنذ أجهزة الكمبيوتر الحديثة

148
00:07:42,540 --> 00:07:46,960
لديها آليات في مكان تحت
هود لتسريع الوصول للذاكرة.

149
00:07:46,960 --> 00:07:51,180
>> ولكن هذه الآليات تعمل بشكل أفضل عندما
مصنوعة العدد في الذاكرة المدمجة

150
00:07:51,180 --> 00:07:52,810
المناطق أو المجالات.

151
00:07:52,810 --> 00:07:55,910
والعقد من TRIE يمكن أن يقيم
في أي مكان في هذا الكومة.

152
00:07:55,910 --> 00:07:58,390
ولكن هذه هي المقايضات
أنه يجب علينا النظر فيها.

153
00:07:58,390 --> 00:08:01,440
>> تذكر أنه عند اختيار البيانات
هيكل لمهمة معينة، ونحن

154
00:08:01,440 --> 00:08:04,420
يجب أن نفكر ما هي أنواع
عمليات بنية البيانات يحتاج إلى

155
00:08:04,420 --> 00:08:07,140
الدعم ومدى الأداء
كل من تلك

156
00:08:07,140 --> 00:08:09,080
المسائل العمليات بالنسبة لنا.

157
00:08:09,080 --> 00:08:11,300
ويمكن لهذه العمليات حتى
تتجاوز مجرد

158
00:08:11,300 --> 00:08:13,430
الأساسية حتى نظرة والإدراج.

159
00:08:13,430 --> 00:08:17,010
لنفترض أننا نريد تنفيذ نوع
من وظائف الإكمال التلقائي، والكثير

160
00:08:17,010 --> 00:08:18,890
مثل محرك البحث جوجل لا.

161
00:08:18,890 --> 00:08:22,210
وهذا هو، وعودة جميع مفاتيح و
يحتمل أن تكون القيم التي

162
00:08:22,210 --> 00:08:24,130
يكون بادئة معينة.

163
00:08:24,130 --> 00:08:27,050
>> A TRIE مفيد فريد
لهذه العملية.

164
00:08:27,050 --> 00:08:29,890
انها واضحة لتكرار خلال
وTRIE لكل حرف من

165
00:08:29,890 --> 00:08:30,950
البادئة.

166
00:08:30,950 --> 00:08:33,559
تماما مثل البحث عن عمل،
نحن يمكن أن تتبع مؤشرات

167
00:08:33,559 --> 00:08:35,400
حرف بحرف.

168
00:08:35,400 --> 00:08:38,659
بعد ذلك، عندما وصلنا إلى نهاية
البادئة، ونحن يمكن أن يكرر من خلال

169
00:08:38,659 --> 00:08:42,049
الجزء المتبقي من هيكل البيانات
لأن أي من مفاتيح أبعد

170
00:08:42,049 --> 00:08:43,980
هذه النقطة لها البادئة.

171
00:08:43,980 --> 00:08:47,670
>> كما انه من السهل الحصول على هذه القائمة
بالترتيب الأبجدي منذ

172
00:08:47,670 --> 00:08:50,970
عناصر من مجموعة الأطفال
ومرتبة أبجديا.

173
00:08:50,970 --> 00:08:54,420
لذلك نأمل عليك أن تنظر
العطاء يحاول المحاولة.

174
00:08:54,420 --> 00:08:56,085
أنا كيفن شميد، وهذا هو CS50.

175
00:08:56,085 --> 00:08:58,745

176
00:08:58,745 --> 00:09:00,790
>> آه، هذا هو بداية
من الانخفاض.

177
00:09:00,790 --> 00:09:01,350
أنا آسف.

178
00:09:01,350 --> 00:09:01,870
آسف.

179
00:09:01,870 --> 00:09:02,480
آسف.

180
00:09:02,480 --> 00:09:03,130
آسف.

181
00:09:03,130 --> 00:09:03,950
>> ضرب أربعة.

182
00:09:03,950 --> 00:09:04,360
أنا خارج.

183
00:09:04,360 --> 00:09:05,280
آسف.

184
00:09:05,280 --> 00:09:06,500
آسف.

185
00:09:06,500 --> 00:09:07,490
آسف.

186
00:09:07,490 --> 00:09:12,352
آسف لجعل شخص
لديه لتحرير هذا بالجنون.

187
00:09:12,352 --> 00:09:13,280
>> آسف.

188
00:09:13,280 --> 00:09:13,880
آسف.

189
00:09:13,880 --> 00:09:15,080
آسف.

190
00:09:15,080 --> 00:09:15,680
آسف.

191
00:09:15,680 --> 00:09:16,280
>> سرور 1: أحسنت.

192
00:09:16,280 --> 00:09:17,530
الذي تم القيام به بشكل جيد.

193
00:09:17,530 --> 00:09:18,430