سبيلر

سبيلر

مشكلة بحاجة إلى حل

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

تجريبي

رمز التوزيع

بالنسبة لهذه المشكلة، ستقوم بتوسيع وظيفة الشيفرة المقدمة لك من قبل موظفي CS50.

$

wget https://cdn.cs50.net/2026/x/psets/5/speller.zip

unzip speller.zip

rm speller.zip

cd speller

speller/ $

dictionaries/  dictionary.c  dictionary.h  keys/  Makefile  speller.c  speller50  texts/

الخلفية

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

التحدي الذي أمامك هو تنفيذ أسرع مدقق إملائي ممكن! ومع ذلك، فإننا نتحدث عن "الأسرع" عن "ساعة الحائط" الفعلية، وليس الوقت المقارب.

في speller.c، لقد قمنا بتجميع برنامج مصمم للتدقيق الإملائي للملف بعد تحميل قاموس الكلمات من القرص إلى الذاكرة. وفي الوقت نفسه، يتم تنفيذ هذا القاموس في ملف يسمى dictionary.c. (يمكن تنفيذه فقط في speller.c، ولكن عندما تصبح البرامج أكثر تعقيدًا، غالبًا ما يكون من المناسب تقسيمها إلى ملفات متعددة.) وفي الوقت نفسه، لا يتم تعريف النماذج الأولية للوظائف الموجودة فيها dictionary.c نفسها ولكن في dictionary.h بدلاً من ذلك. بهذه الطريقة، على حد سواء speller.c و dictionary.c يمكن #include الملف. لسوء الحظ، لم نتمكن من تنفيذ جزء التحميل. أو جزء الفحص. كلاهما (وأكثر قليلاً) نتركهما لك! ولكن أولا، جولة.

الفهم

dictionary.h

افتح dictionary.h، وسترى بعض الصياغة الجديدة، بما في ذلك بضعة أسطر تشير إلى DICTIONARY_H. لا داعي للقلق بشأن هذه الأشياء، ولكن إذا كنت فضوليًا، فإن هذه السطور تضمن ذلك على الرغم من ذلك dictionary.c و speller.c (الذي ستراه بعد قليل) #include هذا الملف، clang سوف يقوم بتجميعه مرة واحدة فقط.

لاحظ بعد ذلك كيف نحن #include ملف يسمى stdbool.h. هذا هو الملف الذي تم تعريف bool نفسه. لم تكن بحاجة إليها من قبل، منذ أن اعتادت مكتبة CS50 على ذلك #include هذا لك.

لاحظ أيضًا استخدامنا لـ #define، "توجيه المعالج المسبق" الذي يحدد "ثابت" يسمى LENGTH بقيمة 45. إنه ثابت بمعنى أنه لا يمكنك (عن طريق الخطأ) تغييره في الشيفرة الخاصة بك. في الحقيقة، clang سوف يحل محل أي إشارات لـ LENGTH في الشيفرة الخاصة بك، حرفيًا، 45. بمعنى آخر، إنه ليس متغيرًا، بل مجرد خدعة بحث واستبدال.

أخيرًا، لاحظ النماذج الأولية لخمس وظائف: check, hash, load, sizeو unload. لاحظ كيف أن ثلاثة من هؤلاء يأخذون المؤشر كوسيطة، لكل *:

bool check(const char *word);
unsigned int hash(const char *word);
bool load(const char *dictionary);

تذكر ذلك يمكن char * هو ما اعتدنا أن نطلق عليه string. لذا فإن هذه النماذج الثلاثة هي في الأساس مجرد:

bool check(const string word);
unsigned int hash(const string word);
bool load(const string dictionary);

و const، في هذه الأثناء، يقول فقط أن هذه السلاسل، عند تمريرها كوسائط، يجب أن تظل ثابتة؛ لن تتمكن من تغييرها، عن طريق الخطأ أو غير ذلك!

dictionary.c

افتح الآن dictionary.c. لاحظ كيف قمنا بتحديد ملف struct node يمثل عقدة في جدول التجزئة. وقد أعلنا عن مصفوفة مؤشرات عالمية، table، والذي سيمثل (قريبًا) جدول التجزئة الذي ستستخدمه لتتبع الكلمات في القاموس. تحتوي المصفوفة N مؤشرات العقدة، وقمنا بتعيينها N يساوي 26 في الوقت الحالي، للتوافق مع الإعداد الافتراضي وظيفة hash كما هو موضح أدناه. من المحتمل أن ترغب في زيادة هذا اعتمادًا على تنفيذك لـ hash.

بعد ذلك، لاحظ أننا قمنا بالتنفيذ load, check, sizeو unload، ولكن بالكاد يكفي لتجميع الشيفرة. لاحظ أيضًا أننا قمنا بتنفيذها hash مع نموذج خوارزمية يعتمد على الحرف الأول من الكلمة. مهمتك، في النهاية، هي إعادة تنفيذ هذه الوظائف بأكبر قدر ممكن من الذكاء حتى يعمل المدقق الإملائي كما هو معلن عنه. وبسرعة!

speller.c

حسنًا، افتح بعد ذلك speller.c وقضاء بعض الوقت في البحث عن الشيفرة والتعليقات الموجودة فيه. لن تحتاج إلى تغيير أي شيء في هذا الملف، ولا تحتاج إلى فهمه بالكامل، ولكن حاول التعرف على وظائفه بالرغم من ذلك. لاحظ كيف، عن طريق وظيفة تسمى getrusage، سنقوم "بوضع معايير مرجعية" (i.e.، توقيت تنفيذ) عمليات التنفيذ الخاصة بك check, load, sizeو unload. لاحظ أيضًا كيف نمضي قدمًا check، كلمة بكلمة، محتويات بعض الملفات التي سيتم تدقيقها إملائيًا. وفي النهاية، نقوم بالإبلاغ عن كل خطأ إملائي في هذا الملف بالإضافة إلى مجموعة من الإحصائيات.

لاحظ، بالمناسبة، أننا قمنا بتعريف استخدام speller ليكون من المفترض أن يكون

Usage: speller [dictionary] text

حيث dictionary ملفًا يحتوي على قائمة من الكلمات الصغيرة، كلمة واحدة في كل سطر، و text هو ملف يحتاج إلى التدقيق الإملائي. كما تشير الأقواس، توفير dictionary اختياري؛ إذا تم حذف هذه الحجة، سيتم استخدام speller dictionaries/large بشكل افتراضي. وبعبارة أخرى، تشغيل

./speller text

سيكون مكافئًا للتشغيل

./speller dictionaries/large text

حيث text هو الملف الذي ترغب في التدقيق الإملائي فيه. ويكفي أن نقول، الأول هو أسهل في الكتابة! (بالطبع، لن يتمكن speller من تحميل أي قواميس حتى تقوم بالتنفيذ load في dictionary.c! حتى ذلك الحين، سوف ترى Could not load.)

يوجد في القاموس الافتراضي، انتبه، 143.091 كلمة، يجب تحميلها جميعًا في الذاكرة! في الواقع، قم بإلقاء نظرة خاطفة على هذا الملف للتعرف على بنيته وحجمه. لاحظ أن كل كلمة في هذا الملف تظهر بأحرف صغيرة (حتى، من أجل البساطة، أسماء العلم والمختصرات). من الأعلى إلى الأسفل، يتم فرز الملف معجميًا، بكلمة واحدة فقط في كل سطر (ينتهي كل منها بـ \n). لا توجد كلمة أطول من 45 حرفًا، ولا تظهر أي كلمة أكثر من مرة. أثناء التطوير، قد تجد أنه من المفيد تقديمه speller مع أ dictionary خاص بك يحتوي على كلمات أقل بكثير، لئلا تجد صعوبة في تصحيح أخطاء بنية هائلة في الذاكرة. في dictionaries/small هو أحد هذه القواميس. لاستخدامه، تنفيذ

./speller dictionaries/small text

حيث text هو الملف الذي ترغب في التدقيق الإملائي فيه. لا تمضي قدمًا حتى تتأكد من أنك تفهم كيف speller يعمل بنفسه!

من المحتمل أنك لم تقضي وقتًا كافيًا في البحث speller.c. ارجع إلى مربع واحد وسر بنفسك من خلاله مرة أخرى!

texts/

حتى تتمكن من اختبار تنفيذك لـ speller، لقد قدمنا لك أيضًا مجموعة كاملة من النصوص، من بينها النص من لا لا لاند، نص قانون الرعاية الميسرة، ثلاثة ملايين بايت من تولستوي، بعض المقتطفات من الأوراق الفيدرالية وشكسبير والمزيد. لكي تعرف ما يمكن توقعه، افتح كل ملف من هذه الملفات وتصفحه، وكلها موجودة في دليل يسمى texts داخل pset5 الدليل.

الآن، كما يجب أن تعرف بعد قراءتك مرة أخرى speller.c بعناية، إخراج speller، إذا تم تنفيذه باستخدام، على سبيل المثال،

./speller texts/lalaland.txt

سوف يشبه في النهاية ما يلي.

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

MISSPELLED WORDS

[...]
AHHHHHHHHHHHHHHHHHHHHHHHHHHHT
[...]
Shangri
[...]
fianc
[...]
Sebastian's
[...]

WORDS MISSPELLED:
WORDS IN DICTIONARY:
WORDS IN TEXT:
TIME IN load:
TIME IN check:
TIME IN size:
TIME IN unload:
TIME IN TOTAL:

TIME IN load يمثل عدد الثواني التي speller ينفق على تنفيذ تنفيذك لـ load. TIME IN check يمثل عدد الثواني التي speller ينفق إجماليًا على تنفيذ تنفيذك لـ check. TIME IN size يمثل عدد الثواني التي speller ينفق على تنفيذ تنفيذك لـ size. TIME IN unload يمثل عدد الثواني التي speller ينفق على تنفيذ تنفيذك لـ unload. TIME IN TOTAL هو مجموع تلك القياسات الأربعة.

لاحظ أن هذه الأوقات قد تختلف إلى حد ما عبر عمليات التنفيذ speller، اعتمادًا على ما تفعله مساحة الشيفرة الخاصة بك، حتى لو لم تقم بتغيير الشيفرة الخاصة بك.

بالمناسبة، لكي نكون واضحين، نعني بكلمة "أخطاء إملائية" ببساطة أن بعض الكلمات ليست موجودة في dictionary تم توفيره.

Makefile

وأخيرًا، تذكر ذلك make يقوم تلقائيًا بتجميع الشيفرة الخاصة بك حتى لا تضطر إلى التنفيذ clang يدويًا مع مجموعة كاملة من المفاتيح. ومع ذلك، مع نمو حجم برامجك، لن يتمكن make من الاستدلال من السياق بعد الآن على كيفية تجميع الشيفرة الخاصة بك؛ سوف تحتاج إلى البدء في القول make كيفية تجميع برنامجك، خاصة عندما يتضمن مصادر متعددة (i.e., .c) الملفات، كما في حالة هذه المشكلة. ولذا سوف نستخدم أ Makefile، ملف التكوين الذي يخبرنا make ما يجب فعله بالضبط. افتح Makefile، ومن المفترض أن تشاهد أربعة أسطر:

1. السطر الأول يحكي make لتنفيذ الأسطر اللاحقة عندما تقوم بالتنفيذ بنفسك make speller (أو فقط make).
2. السطر الثاني يحكي make كيفية التجميع speller.c إلى رمز الجهاز (i.e., speller.o).
3. السطر الثالث يحكي make كيفية التجميع dictionary.c إلى رمز الجهاز (i.e., dictionary.o).
4. السطر الرابع يحكي make للربط speller.o و dictionary.o في ملف يسمى speller.

تأكد من التجميع speller بالتنفيذ make speller (أو فقط make). تنفيذ make dictionary لن يعمل!

المواصفات

حسنًا، التحدي الذي يواجهك الآن هو التنفيذ بالترتيب، load, hash, size, checkو unload بأكبر قدر ممكن من الكفاءة باستخدام جدول التجزئة بهذه الطريقة تم تصغير TIME IN load, TIME IN check, TIME IN sizeو TIME IN unload كلها. من المؤكد أنه ليس من الواضح ما الذي يعنيه التقليل من شأنك، بقدر ما ستختلف هذه المعايير بالتأكيد مع إطعامك speller قيم مختلفة لـ dictionary و ل text. ولكن هنا يكمن التحدي، إن لم يكن المتعة، في هذه المشكلة. هذه المشكلة هي فرصتك للتصميم. على الرغم من أننا ندعوك لتقليل المساحة، إلا أن عدوك النهائي هو الوقت. ولكن قبل أن تغوص في التفاصيل، بعض المواصفات منا.

• لا يجوز لك التغيير speller.c أو Makefile.
• يجوز لك التغيير dictionary.c (وفي الواقع، يجب إكمال عمليات تنفيذ load, hash, size, checkو unload)، ولكن لا يجوز لك تغيير الإعلانات (i.e.، النماذج الأولية) الخاصة بـ load, hash, size, check، أو unload. ومع ذلك، يمكنك إضافة وظائف جديدة ومتغيرات (محلية أو عامة) إلى dictionary.c.
• يمكنك تغيير قيمة N في dictionary.c، حتى يحتوي جدول التجزئة الخاص بك على المزيد من المجموعات.
• يجوز لك التغيير dictionary.h، ولكن لا يجوز لك تغيير إعلانات load, hash, size, check، أو unload.
• يجب ألا يكون تنفيذك للدالة check حساسًا لحالة الأحرف. وبعبارة أخرى، إذا foo موجود في القاموس إذن check يجب أن يُرجع صحيحًا نظرًا لأي كتابة بالأحرف الكبيرة؛ لا شيء من يجب اعتبار foo, foO, fOo, fOO, fOO, Foo, FoO, FOoو FOO به خطأ إملائي.
• بغض النظر عن الكتابة بالأحرف الكبيرة، فإن تنفيذك لـ check يجب أن يعود فقط true للكلمات الموجودة بالفعل dictionary. احذر من الكلمات الشائعة ذات الترميز الصعب (e.g., the)، لئلا نمرر التنفيذ الخاص بك أ dictionary بدون نفس الكلمات. علاوة على ذلك، فإن الممتلكات الوحيدة المسموح بها هي تلك الموجودة بالفعل dictionary. وبعبارة أخرى، حتى لو foo موجود dictionary, check false معطى foo's إذا foo's ليس موجودًا أيضًا dictionary.
• قد تفترض أن أي dictionary التي تم تمريرها إلى برنامجك سيتم تنظيمها تمامًا مثل برنامجنا، ومرتبة أبجديًا من الأعلى إلى الأسفل بكلمة واحدة في كل سطر، تنتهي كل منها بـ \n. يمكنك أن تفترض ذلك أيضًا dictionary سيحتوي على كلمة واحدة على الأقل، ولن تكون هناك كلمة أطول منها LENGTH (ثابت محدد في dictionary.h) ، بحيث لن تظهر أي كلمة أكثر من مرة، وأن كل كلمة ستحتوي فقط على أحرف أبجدية صغيرة وربما فواصل عليا، وألا تبدأ أي كلمة بفاصلة عليا.
• ربما تفترض ذلك check سيتم تمرير فقط الكلمات التي تحتوي على أحرف أبجدية (كبيرة أو صغيرة) وربما الفواصل العليا.
• قد يستغرق المدقق الإملائي الخاص بك فقط text واختياريًا، dictionary كمدخل. على الرغم من أنك قد تميل (خاصة إذا كنت من بين الأشخاص الأكثر راحة) إلى "المعالجة المسبقة" لقاموسنا الافتراضي من أجل استخلاص "وظيفة تجزئة مثالية" له، إلا أنه لا يجوز لك حفظ مخرجات أي معالجة مسبقة من هذا القبيل على القرص من أجل تحميله مرة أخرى إلى الذاكرة في عمليات التشغيل اللاحقة للمدقق الإملائي الخاص بك من أجل الحصول على ميزة.
• يجب ألا يتسبب المدقق الإملائي في تسريب أي ذاكرة. تأكد من التحقق من وجود تسربات مع valgrind.
• يجب أن تكون وظيفة التجزئة التي تكتبها خاصة بك في النهاية، وليست وظيفة تبحث عنها عبر الإنترنت.

حسنًا، هل أنت مستعد للذهاب؟ يجب على

• التنفيذ load.
• التنفيذ hash.
• التنفيذ size.
• التنفيذ check.
• التنفيذ unload.

تلميحات

bool load(const char *dictionary)
{
    // Open the dictionary file

    // Read each word in the file

        // Add each word to the hash table

    // Close the dictionary file
}

bool load(const char *dictionary)
{
    // Open the dictionary file
    FILE *source = fopen(dictionary, "r");

    // Read each word in the file

        // Add each word to the hash table

    // Close the dictionary file
}

bool load(const char *dictionary)
{
    // Open the dictionary file
    FILE *source = fopen(dictionary, "r");

    // Read each word in the file

        // Add each word to the hash table

    // Close the dictionary file
    fclose(source);
}

valgrind ./speller texts/cat.txt

help50 valgrind ./speller texts/cat.txt

الإرشادات التفصيلية

كيفية الاختبار

كيف تتحقق مما إذا كان برنامجك يكتب الكلمات الصحيحة التي بها أخطاء إملائية؟ حسنًا، أنتم مدعوون للرجوع إلى "مفاتيح الإجابة" الموجودة داخل الملف دليل keys الموجود بداخل ملفك speller الدليل. على سبيل المثال، داخل keys/lalaland.txt هي كل الكلمات التي يستخدمها برنامجك ينبغي أعتقد أنها تحتوي على أخطاء إملائية.

لذلك يمكنك تشغيل برنامجك على بعض النصوص في نافذة واحدة، كما هو الحال في ما يلي.

./speller texts/lalaland.txt

ويمكنك بعد ذلك تشغيل حل فريق العمل على نفس النص في نافذة أخرى، كما هو الحال أدناه.

./speller50 texts/lalaland.txt

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

./speller texts/lalaland.txt > student.txt
./speller50 texts/lalaland.txt > staff.txt

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

diff -y student.txt staff.txt

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

diff -y student.txt keys/lalaland.txt

إذا كانت مخرجات برنامجك تتطابق مع مخرجات فريق العمل، diff سيخرج عمودين يجب أن يكونا متطابقين باستثناء أوقات التشغيل في الأسفل. ومع ذلك، إذا اختلفت الأعمدة، فسترى أ > أو | حيث يختلفان. على سبيل المثال، إذا كنت ترى

MISSPELLED WORDS                                                MISSPELLED WORDS

TECHNO                                                          TECHNO
L                                                               L
                                                              > Thelonious
Prius                                                           Prius
                                                              > MIA
L                                                               L

هذا يعني أن برنامجك (الذي يوجد مخرجاته على اليسار) لا يعتقد ذلك Thelonious أو MIA به خطأ إملائي، على الرغم من وجود خطأ إملائي في إخراج فريق العمل (على اليمين)، كما يوحي ذلك غياب، على سبيل المثال، Thelonious في العمود الأيسر ووجود Thelonious في العمود الأيمن.

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

./speller dictionaries/small texts/cat.txt 

صحة

check50 cs50/problems/2026/x/speller

النمط

style50 dictionary.c

الحل الخاص بفريق العمل

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

./speller50 texts/lalaland.txt

كيفية الإرسال

في جهازك الطرفي، قم بتنفيذ ما يلي لإرسال عملك، والإجابة على المطالبات التي تظهر أيضًا.

submit50 cs50/problems/2026/x/speller