من مترجم: استرعي انتباهكم إلى ترجمة لمقال قديم جدًا نُشر في 15 يناير 1983. على الرغم من هذا العصر المثير للإعجاب ، بدت المقالة مثيرة للاهتمام بالنسبة لي ، ومن المحتمل أنها ستكون مفيدة لشخص اليوم. بالمناسبة ، يشار إلى هذه المقالة من قبل الرجل تحديد موقع موضوع المساعدة (1) على opennet.ru: https://www.opennet.ru/man.shtml؟topic=locate .
ملخص
توضح هذه المقالة آلية بحث سريع عن الملفات في UNIX. فهو يجمع بين طريقتين لضغط البيانات مع تقنية بحث سطر جديدة ، وهو مصمم للبحث بسرعة عن الملفات العشوائية. الكود ، المدمج في أداة البحث القياسية ، يبحث في قاعدة البيانات التي تم إنشاؤها سابقًا ، ويتم تحديثها يوميًا. وهذا يميزها عن الآلية المعتادة للبحث عن التطابقات الرئيسية مع المرشحين ، والتي يتم إنشاؤها بسرعة من بنية دليل متناثرة (على القرص).قاعدة بيانات مسار الملف هي قائمة مشفرة بشكل متزايد ومفروشة حسب المعجم (تسمى أحيانًا ملف "مضغوط أمامي") ، والتي تخضع أيضًا لترميز كبير بشكل منتظم من أجل الحصول على ضغط فعال. نسبة الضغط 5 إلى 6 مقارنة بتمثيل ASCII المعتاد. يتم مسح القائمة باستخدام بحث خطي معدل ، تم تكييفه خصيصًا للتشفير التدريجي ، في حين أن الوقت النموذجي الذي تقضيه الخوارزمية أقل بنسبة 40-50٪ من البحث العادي.المقدمة
يعد العثور على الملفات في نظام الكمبيوتر أو شبكة الكمبيوتر عملية معقدة. يمكن لمستخدمي UNIX تنفيذه بطرق متنوعة ، من التلاعب بأوامر cd و ls و grep إلى الأوامر المتخصصة ، مثل تلك التي طورتها Berkeley حيث يوجد و fleese ، وحتى أمر Unix الأكثر شيوعًا.لسوء الحظ ، يقتصر الصوف (من Berkeley) على الدليل الرئيسي ، وحيث يمكن البحث فقط عن رمز النظام والوثائق الموجودة في الأماكن القياسية.بحث:find / -name "*<filename>*" -print
بالطبع ، يمكنه البحث عن ملفات عشوائية ، ولكن ببطء شديد ، لأنه يستخدم نزولًا تعاوديًا في جميع أنحاء نظام الملفات ، منتشر بلا رحمة في جميع أنحاء القرص. دفعنا نفاد الصبر إلى تطوير بحث بديل (فيما يتعلق بطريقة "البحث والعثور") عن مسارات الملفات.الحسابات الأولية
لماذا لا تقوم فقط بإنشاء قائمة ثابتة لجميع الملفات في النظام والبحث عن grep عليها؟ سيحتوي النظام النموذجي الذي يحتوي على 20000 ملف على 1000 مقطع من أسماء الملفات ، حتى إذا قمت بتقصير / usr to / u يقوم برنامج Grep على نظام PDP-11/70 غير المُحمّل بمعالجة 30-40 كتلة في الثانية ، وسيتطلب مسح نصف دقيقة. هذا غير مقبول لأمر شائع الاستخدام.ولكن إذا قدمنا تضحية صغيرة - عدم القدرة على البحث عن الملفات التي مضى عليها أقل من يوم واحد ، فلن يخلق هذا مشاكل كبيرة ، لأن الشخص الذي أنشأ مثل هذا الملف ربما يكون في متناول اليد ، أو ربما الملف غير جاهز بعد استعمال. الملفات القديمة التي تم إنشاؤها بواسطة مجموعات مستخدمين أخرى ذات اصطلاحات تسمية مختلفة للملفات هي على الأرجح مرشحات البحث.ضغط
لتسريع الوصول للتطبيقات ، يمكنك اقتراح استخدام بحث ثنائي أو جدول تجزئة ، ولكن هذه المخططات لا تعمل بشكل جيد لإجراء مقارنات جزئية ، إذا كنا مهتمين فقط بجزء من الاسم. يتم تنفيذ تقنية ضغط البيانات المطلوبة ، والمعروفة باسم الترميز التدريجي ، والتي تم استخدامها لمهمة ضغط القاموس المماثلة بسهولة [Morris / Thompson، 1974]. في هذه الحالة ، يتم حساب البادئة الأطول للاسم السابق. على سبيل المثال:/usr/src
/usr/src/cmd/aardvark.c
/usr/src/cmd/armadillo.c
/usr/tmp/zoo
تم تحويله إلى0/usr/src
8/cmd/aardvark.c
14armadillo.c
5tmp/zoo
سيكون فك التشفير بسيطًا (تم حذف الإعلانات المتغيرة)fp = fopen(COMPRESSED_FILELIST, "r");
while((count = (getc(fp) & 0177)) != EOF) {
for(p = path + count; (*p++ = getc(fp)) < 0200; )
;
ungetc(*--p, fp);
*p-- = NULL;
if(math(path, name) == YES)
puts(path);
}
حيث math هي دالة تحدد ما إذا كانت السلسلة الفرعية للاسم موجودة في سلسلة المسار .في الواقع ، نظرًا لأن القائمة المشفرة أقصر بخمس مرات تقريبًا من القائمة غير المشفرة ، وفك التشفير بسيط جدًا ، يعمل البرنامج ثلاث إلى أربع مرات أسرع من grep على الملف النصي.أسرع
هذا النهج مفيد بالفعل ، لكنه يترك مجالًا لمزيد من التحسينات. (ملاحظة: يتم استخدام هذا الرمز في أداة البحث المساعدة. ليست هناك حاجة لتحميل UNIX بأمر آخر [وصفحة دليل] عندما يمكننا تحسين برنامج مماثل موجود. لحسن الحظ ، لا يوجد اتصال مع وسيطتين ، ويمكننا ملء الفراغ بدون زخرفة :find name
لاحظ أن الرمز أعلاه لا يزال يبحث في القائمة غير المعبأة ، وإن كانت في الذاكرة ، وليس على القرص. يمكن تجنب ذلك بمقارنة سلسلة مع سلسلة فرعية في الاتجاه المعاكس. دع التسمية تشير إلى الحرف الأخير من اسم السلسلة ، واستبدل الرياضيات بـ:for(s = p, cutoff = path + count; s > cutoff; s--) {
if(*s == namend) {
for(p = namend - 1, q = s - 1; *p != NULL; p--, q--)
if(*q != *p)
break;
if(*p == NULL) {
puts(path);
break;
}
}
}
يسهل فهم ذلك من خلال النظر في ثلاث حالات. إذا كانت السلسلة الفرعية تمامًا على يمين القطع ، فستنتهي المقارنة بنجاح. إذا تداخلت ، يصبح القطع "ضعيفًا" وتستمر المقارنة. إذا كانت السلسلة الفرعية تقع تمامًا على يسار القطع ، فسيتم الكشف عن تطابق للخطوط السابقة ، مما يعني أنه لا يمكننا إجراء هذا البحث! من الناحية الفنية ، يمكن نقل القطع إلى المسار مباشرة بعد إجراء المقارنة. تم حذف هذا الشرط أعلاه.معدات من مستويين
يمكنك تجنب إبطاء البحث الناتج عن معالجة أحرف أنماط البحث . في القيام بذلك، ونحن معالجة جزء من الاسم الذي لا يحتوي على الأحرف الخاصة واستخدام وظيفة أبطأ العودية amath داخل الاكتشاف . بمعنى آخر،puts(path)
يصبحif(globchars == NO | amatch(path, name))
puts(path);
حيث يتم تعيين globchars إذا كان الاسم يحتوي على أحرف تعريف. مثال على استخدام نمط البحث لأمر man بسيط :vtroff -man 'find '*man*'"$1"'.[1-9]
مزيد من التحسينات
يزيد رمز الإنتاج الخاص بأداة البحث المساعدة من نسبة الضغط بنسبة 20-25٪ أخرى عن طريق استبدال التركيبات الأكثر شيوعًا المكونة من حرفين برموز ASCII غير القابلة للطباعة. ".c" و ".P" شائعان بشكل خاص.الخوارزميات الأخرى التي تنفذ مقايضات أخرى بين الوقت وحجم البيانات ، مثل خوارزمية هوفمان [Reghbati ، 1981] ، لا تبدو واعدة: إنها فقط تستبدل حد أداء الإدخال / الإخراج بحد الأداء.يمكن استخدام طرق البحث دون الخطية Boyer-Moore [Boyer، 1977] أو طرق النموذج الكلي [Storer / Szymanski، 1982].في الختام ، تجدر الإشارة إلى أننا قمنا بمسح 19000 اسم ملف في ثوانٍ قليلة ، باستخدام 180 مقطعًا ورمزًا C يلائم صفحتين.المراجع
Boyer ، RS خوارزمية البحث السريع في السلسلة ، Commun. ACM ، المجلد. 20، رقم 10، أكتوبر 1977.موريس، R. وتومسون، ثانيا K. بستر على رأس دبوس، مذكرة غير منشورة التقنية، مختبرات بيل موراي هيل، NY، 1974.Reghbati، HK نظرة عامة على ضغط البيانات Techinques، كمبيوتر ، المجلد. 14 ، رقم 4 أبريل 1981.Storer ، JA و Szymanski ، ضغط بيانات TG عبر استبدال النص ، J. ACM ، Vol. 29 ، رقم 4 أكتوبر 1982.