thawab:search
اختلافات
عرض الاختلافات بين النسخة المختارة و النسخة الحالية من الصفحة.
جانبي المراجعة السابقةالمراجعة السابقة | |||
thawab:search [2010/10/13 13:51] – تعريف الكلمات المستبعدة عمليا alsadi | thawab:search [2015/04/23 03:21] (حالي) – تحرير خارجي 127.0.0.1 | ||
---|---|---|---|
سطر 1: | سطر 1: | ||
+ | ====== دراسة محركات البحث ====== | ||
+ | ===== نظرة عامة وفهم المصطلحات ===== | ||
+ | إن أي محرك بحث أو نظام IR أي نظام استخراج المعلومات Information Retrieval system يتكون من مراحل منفصلة هي | ||
+ | * حفظ المحتوى وفي حالتنا نحن حفظ المحتوى في ملفات SQLite منفصلة | ||
+ | * مرحلة تلقيم المحتوى للفهرسة وهي تتم مرة واحدة (ما لم يتغير المحتوى) | ||
+ | * الاستعلام وهو أن يطلب المستخدم البحث عن شيء ما ويجب أن يعيده النظام مرتب وفق تقييم rank لمدى الارتباط Relevance | ||
+ | |||
+ | يقسم النظام المحتوى إلى عدد من الوحدات الجوهرية تسمى كل منها وثيقة Document ويكون بها عدد من الحقول Fields أحدها معرف فريد (رقم أو URL ...) وفي حالنا الوثيقة الواحدة هي الفصل أو الباب في الكتاب (أو الحديث في كتب الحديث أو الراوي في كتب الرجال ...) ونميزه عبر وسم " | ||
+ | |||
+ | الحقول المختلفة في إما أن تكون حقول محللة ((انظر [[http:// | ||
+ | |||
+ | بعض الحقول يتم الاحتفاظ بها كما هي دون معالجة داخل الفهرس مثل المعرف وربما جزء ملخص من النص (أول فقرة مثلا ويسمى excerpt أو snippet) | ||
+ | وبعضها الآخر لا يتم الاحتفاظ بها مثل النص نفسه لأنه كبير جدا لكن في المقابل يمكن في هذه الحالة الاحتفاظ بما يسمى Term Vector أي متجه الحدود | ||
+ | ((انظر [[http:// | ||
+ | وهو معرّف كل كلمة وتكرارها وإزاحتها (وبالتالي ترتيبها) وحيث أن الوثائق المختلفة تستخدم نفس الكلمات يوفر الاحتفاظ بالمتجه المساحة ويقدم معلومات أكثر للفهرس. للمزيد من المعلومات انظر [[http:// | ||
+ | |||
+ | [[http:// | ||
+ | * " | ||
+ | * " | ||
+ | * " | ||
+ | |||
+ | مثلا البحث عن " | ||
+ | |||
+ | [[http:// | ||
+ | |||
+ | البحث عن عبارات مشابهة أو ما يسمى البحث الضبابي في مصطلح lucene هو البحث عن وثائق تقل فيها **مسافة التحرير** المحسوبة بخوارزمية ليفنشتاين [[http:// | ||
+ | * إضافة حرف | ||
+ | * حذف حرف | ||
+ | * تعويض حرف مكان آخر | ||
+ | |||
+ | مثلا التحرير بين | ||
+ | |||
+ | وفي lucene يمكن أن نستعلم عن الوثائق المشابهة لعبارة ونقدم رقم بين 0 و 1 مثل 0.6 وهو رقم يضرب في طول الاستعلام | ||
+ | |||
+ | ويقدم محرك lucene طريقة للجمع بين هذه الأنواع حيث يقدم المستخدم الباحث سلسلة نصية يتم إعرابها عبر [[http:// | ||
+ | [[http:// | ||
+ | |||
+ | المزيد: | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | |||
+ | ===== الكلمات المهملة stopwords ===== | ||
+ | الكلمات المهملة أو المستبعدة stopwords هي الكلمات ذات التكرار العالي وليس لها دلالة خاصة مثل حروف الجر والأدوات. وهذه يتم إهمالها في أغلب محركات البحث ومن أمثلتها كلمة from (والتي تعني من) و كلمة to (والتي تعني إلى) ولان ههذه الكلمات تتكرر كثيرا فإن اهمالها يؤدي إلى تقليل حجم فهرس البحث (وبالتالي قد ينعكس هذا على زيادة السرعة وتقليل استهلاك الذاكرة) لكن الهدف من إهمالها ليس التوفير بل هو إهمال تطابقات غير مرغوبة مثلا عند البحث عن " | ||
+ | |||
+ | في اللغة العربية أرى أنه لا يوجد حاجة لإهمال مثل هذه الكلمات مثلا لو أخذنا " | ||
+ | يمكن حساب الكلمات المستبعدة تلقائيا وذلك بأخذ عينة ممثلة من عدد كبير من الوثائق المتنوعة (وليس وثيقة واحدة) ثم إحصاء **//idf//** (أي التردد العكسي للوثائق inverse document frequency) لكل كلمة في العينة حيث تكون قيمته للكلمات المستبعدة قريبة من الصفر (يمكن أخذها أقل من قيمة معينة مثلا 0.25) ويحسب بالعلاقة: | ||
+ | |||
+ | < | ||
+ | idf=log(nD/ | ||
+ | </ | ||
+ | |||
+ | أي لوغاريتم النسبة بين عدد كل الوثائق nD على عدد الوثائق التي يظهر فيها الحد nd. مثلا إن ظهرت الكلمة " | ||
+ | |||
+ | ===== التجذيع stemming ===== | ||
+ | إن طلبنا من محرك البحث معالجة الكلمات فإنها يرسلها لدالة التجذيع وهي دالة تسقط عدة قيم إلى نفس الصورة many to one transformation | ||
+ | حيث ترسل كلمات مثل play و played و playing إلى نفس الصورة وهي في مثالنا play حيث أن البحث عن هذه يجب أن يقود لتلك. | ||
+ | ليس بالضرورة أن تكون الدالة دقيقة حيث يفترض أن ترسل عدة كلمات غالبا ما تكون متعلقة ببعضها صرفيا إلى نفس الصورة | ||
+ | |||
+ | محرك البحث lucene يحتوي على عدة محللات للتجذيع والقياسي ليس أقوى محلل للقة الإنجليزية بل هناك [[http:// | ||
+ | حيث يقوم بما يلي بعد التقطيع القياسي: | ||
+ | * StandardFilter | ||
+ | * LowerCaseFilter - تحويل كل الحروف إلى صغيرة | ||
+ | * StopFilter - إهمال الكلمات بعض الكلمات الإنجليزية | ||
+ | * SnowballFilter - التجذيع وفق طريقة Snowball | ||
+ | |||
+ | وطريقة [[http:// | ||
+ | |||
+ | لكن لم وهناك عدد من الأمثلة [[http:// | ||
+ | |||
+ | انظر [[stemming|التجذيع]] | ||
+ | |||
+ | ===== ترتيب النتائج Ranking ===== | ||
+ | |||
+ | بعد حصر التطابقات يتم تقييمها عبر عدة خوارزميات | ||
+ | انظر [[http:// | ||
+ | [[http:// | ||
+ | |||
+ | أي حاصل ضرب tf وهو التكرار النسبي للحد في الوثيقة (أي مجموع تكرار الحد في الوثيقة td على مجموع تكرار الحد في كل الوثائق tD) | ||
+ | في idf وهو مدى أهمية الحد عبر قياس لوغاريتم النسبة بين عدد كل الوثائق nD على عدد الوثائق التي يظهر فيها الحد nd | ||
+ | |||
+ | tf=sum(td)/ | ||
+ | idf=log(nD/ | ||
+ | |||
+ | هذا للحد الواحد | ||
+ | |||
+ | وهناك خوارزمية أفضل اسمها [[http:// | ||
+ | |||
+ | وهي كما تعرفها xapian تحسب بالعلاقة | ||
+ | < | ||
+ | ( (k2 . nq) (1-L)/(1+L) ) + | ||
+ | | ||
+ | </ | ||
+ | |||
+ | حيث | ||
+ | * t الحد term | ||
+ | * q تكرار الحد في الاستعلام term within query frequency, | ||
+ | * f تكرار الحد في الوثيقة term within document frequency, | ||
+ | * n عدد الوثائق التي تحتوي الحد | ||
+ | * N عدد كل الوثائق | ||
+ | * r عدد كل الوثائق التي تتعلق بالحد t | ||
+ | * R عدد كل الوثائق التي المتعلقة بالاستعلام | ||
+ | * nq عدد الحدود في في الاستعلام | ||
+ | * L طول الوثيقة النسبي (طول الوثيقة على متوسط طول الوثيقة وهو يساوي 1 للوثيقة متوسطة الطول) | ||
+ | * b و k1 و k2 و k3 ثوابت | ||
+ | * K ثابت يعتمد على L ويعطى بالعلاقة | ||
+ | |||
+ | K = k1(bL + (1-b)) | ||
+ | |||
+ | المزيد: | ||
+ | * http:// | ||
+ | * [[http:// | ||
+ | |||
+ | ===== محرك البحث Whoosh ===== | ||
+ | محرك بحث مكتوب حصريا على بايثون وبالتلي يعمل على كل المنصات التي تعمل عليها بايثون | ||
+ | |||
+ | تكمن فائدة هذا المحرك هو سرعة التطوير ويمكن الاستفادة من وضوح كود بايثون في فهم خوارزميات البحث المختلفة | ||
+ | |||
+ | حيث أنه يوفر العديد منها مثل BM25 و tf-idf | ||
+ | |||
+ | وعند تجربته لم يكن يعمل مع اللغة العربية لكن تخصيصه كان أمرا سهلا فهو يوفر العديد من صنوف التقطيع | ||
+ | |||
+ | يقول الموقع أنه أقل سرعة من lucene إلا أن ذلك غير ملموس فقد استغرق الكود المبدئي أقل من دقيقة ونصف في فهرسة عينة من الكتب (بحجم 35.2 م.ب وهي بخاري ومسلم والموطأ والسلسلة الصحيحة ومقالة PyQt4 ومقالة للتجربة) وكان حجم الفهرس مقبولا جدا حيث وصل إلى حوالي 20% من حجم النص (7.1 م.ب) ربما السبب هو كثرة الحركات في النص حيث تهملها الفهرسة | ||
+ | |||
+ | أما سرعة الاسترجاع فهي شبه آنية إليك مثال | ||
+ | < | ||
+ | | ||
+ | 44 | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | </ | ||
+ | لاحظ أن استعمال علامة الاقتباس "" | ||
+ | < | ||
+ | ./ | ||
+ | 3 | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | </ | ||
+ | |||
+ | |||
+ | مثال آخر لاحظ بدئ وبدأ وبدء | ||
+ | < | ||
+ | ./ | ||
+ | 10 | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | data/ | ||
+ | </ | ||
+ | لاحظ أنني استعملت ال التعريف ووجدها البرنامج دونها | ||
+ | < | ||
+ | ./ | ||
+ | 2 | ||
+ | data/ | ||
+ | data/ | ||
+ | </ | ||
+ | |||
+ | ===== محرك البحث xapian ===== | ||
+ | كتب على لغة سي+ وله ربط على كل اللغات الأخرى | ||
+ | به العديد من المزايا لكنه كغيره فقير بدعمه للعربية | ||
+ | |||
+ | عند تجربته احتجنا للرقعة التالية: | ||
+ | <code diff> | ||
+ | --- include/ | ||
+ | +++ include/ | ||
+ | @@ -298,6 +298,7 @@ | ||
+ | | ||
+ | | ||
+ | | ||
+ | + (1 << Xapian:: | ||
+ | | ||
+ | | ||
+ | } | ||
+ | </ | ||
+ | لحل [[http:// | ||
+ | |||
+ | كما اصطدمت بكونه يحتاج لكتابة دالة التجذيع في سي++ فقط ولا يمكن عملها في باثون مما يؤخر سرعة التطوير | ||
+ | |||
+ | إذا كنت سنضيف دالة تجذيع كبقية اللغات فالبرنامج يستخدم تقنية snowball حيث توضع ملفات بلغة برمجة خاصة في المجلد languages ويتم تعديل ملفات Makefile لتصنيف الكود الجديد | ||
+ | |||
+ | للمزيد انظر http:// | ||
+ | |||
+ | كانت سرعة الفهرسة لعينة الكتب حوالي نصف دقيقة لكن الغريب هو حجم الفهرس الكبير حيث وصل إلى 200% من حجم العينة (58.8 م.ب) ومع التجذيع اليدوي كانت النتيجة 100% (نفس حجم العينة تقريبا) | ||
+ | |||
+ | وكانت سرعة البحث آنية (أقل من 5 اجزاء من مئة من الثانية مع أنه وجد 1215 تطابقا) | ||
+ | <code bash> | ||
+ | [alsadi@pc1 thawab-python]$ ./ | ||
+ | q:[ترك الصلاه كفر] | ||
+ | Parsed query is: Xapian:: | ||
+ | 1215 results found. | ||
+ | Results 1-10: | ||
+ | 1: 100% docid=1524 [data/ | ||
+ | 2: 76% docid=1841 [data/ | ||
+ | 3: 76% docid=4975 [data/ | ||
+ | 4: 75% docid=59 [data/ | ||
+ | 5: 74% docid=1890 [data/ | ||
+ | 6: 74% docid=2966 [data/ | ||
+ | 7: 73% docid=379 [data/ | ||
+ | 8: 73% docid=431 [data/ | ||
+ | 9: 67% docid=5942 [data/ | ||
+ | 10: 67% docid=1520 [data/ | ||
+ | </ | ||
+ | وهذا مثال آخر | ||
+ | < | ||
+ | [alsadi@pc1 thawab-python]$ time ./ | ||
+ | q:[بدا الوحي] | ||
+ | Parsed query is: Xapian:: | ||
+ | 222 results found. | ||
+ | Results 1-10: | ||
+ | 1: 100% docid=7210 [data/ | ||
+ | 2: 97% docid=97 [data/ | ||
+ | 3: 89% docid=3481 [data/ | ||
+ | 4: 84% docid=1562 [data/ | ||
+ | 5: 65% docid=6108 [data/ | ||
+ | 6: 57% docid=6128 [data/ | ||
+ | 7: 53% docid=2573 [data/ | ||
+ | 8: 53% docid=1127 [data/ | ||
+ | 9: 50% docid=2768 [data/ | ||
+ | 10: 48% docid=864 [data/ | ||
+ | </ | ||
+ | |||
+ | ===== محرك البحث lucene ===== | ||
+ | عند تجربة فهرسة نفس العينة كانت سريعة جدا حيث احتاج إلى حوالي 10 ثواني (مع تجذيع بدائي مختلف مكتوب بلغة جافا وليس غروفي) | ||
+ | بحجم 17 م.ب عند عدم حفظ العاوين و 19 ميغا عند حفظ العناوين | ||
+ | |||
+ | عملية البحث تستغرق ثانية تقريبا وهو الوقت اللازم لتحميل جافا (ربما إن كانت محملة مسبقا ستكون آنية تقريبا) | ||
+ | < | ||
+ | [alsadi@pc1 thawab]$ time groovy source/ | ||
+ | HITS 1 | ||
+ | 0.4388401 | ||
+ | stored/ | ||
+ | stored/ | ||
+ | stored/ | ||
+ | real 0m1.048s | ||
+ | user 0m1.005s | ||
+ | sys 0m0.092s | ||
+ | |||
+ | [alsadi@pc1 thawab]$ groovy source/ | ||
+ | HITS 96 | ||
+ | 0.41719502 | ||
+ | stored/ | ||
+ | stored/ | ||
+ | stored/ | ||
+ | 0.21379709 | ||
+ | stored/ | ||
+ | stored/ | ||
+ | stored/ | ||
+ | 0.20339794 | ||
+ | stored/ | ||
+ | stored/ | ||
+ | stored/ | ||
+ | 0.20339794 | ||
+ | stored/ | ||
+ | stored/ | ||
+ | stored/ | ||
+ | 0.20339794 | ||
+ | stored/ | ||
+ | stored/ | ||
+ | stored/ | ||
+ | 0.19176543 | ||
+ | stored/ | ||
+ | stored/ | ||
+ | stored/ | ||
+ | 0.18760023 | ||
+ | stored/ | ||
+ | stored/ | ||
+ | stored/ | ||
+ | 0.16779475 | ||
+ | stored/ | ||
+ | stored/ | ||
+ | stored/ | ||
+ | time groovy source/ | ||
+ | HITS 3 | ||
+ | 0.80785483 | ||
+ | stored/ | ||
+ | stored/ | ||
+ | stored/ | ||
+ | 0.39978445 | ||
+ | stored/ | ||
+ | stored/ | ||
+ | stored/ | ||
+ | 0.3769204 | ||
+ | stored/ | ||
+ | stored/ | ||
+ | stored/ | ||
+ | |||
+ | groovy source/ | ||
+ | HITS 1520 | ||
+ | 0.7442378 | ||
+ | stored/ | ||
+ | stored/ | ||
+ | stored/ | ||
+ | 0.66830057 | ||
+ | stored/ | ||
+ | stored/ | ||
+ | stored/ | ||
+ | 0.4451205 | ||
+ | stored/ | ||
+ | stored/ | ||
+ | stored/ | ||
+ | 0.42100447 | ||
+ | stored/ | ||
+ | stored/ | ||
+ | stored/ | ||
+ | 0.39304644 | ||
+ | stored/ | ||
+ | stored/ | ||
+ | stored/ | ||
+ | 0.39260826 | ||
+ | stored/ | ||
+ | stored/ | ||
+ | stored/ | ||
+ | 0.36176178 | ||
+ | stored/ | ||
+ | stored/ | ||
+ | stored/ | ||
+ | 0.353653 | ||
+ | stored/ | ||
+ | stored/ | ||
+ | stored/ | ||
+ | |||
+ | </ | ||
thawab/search.txt · آخر تعديل: 2015/04/23 03:21 بواسطة 127.0.0.1