Documents to be indexed ➔ Tokenizer ➔ Linguistic Modules ➔ Indexer ➔ Inverted Index
هاض هو "خط الإنتاج" الأساسي لأي محرك بحث. بيبدأ بالمواد الخام وهي الـ Documents، بعدين بتمر على العمليات التالية:
-
• Tokenizer: "المشرط" اللي بقطع
الجمل لكلمات (Tokens).
Friends, Romans, countrymen. ➔ Friends, Romans,
countrymen
-
• Linguistic modules: المرحلة اللي
بتعدل شكل الكلمات لأصولها (Modified tokens).
Friends, Romans, countrymen ➔ friend, roman,
countryman
-
• Indexer: اللي برتب المعلومات في
الـ Inverted Index النهائي (الكلمة ومكان ظهورها في
المستندات).
friend ➔ 2, 4
📂 Parsing: What is a Document?
Need to step back and ask: What format? What language? What character set?
قبل ما نبدأ، لازم نسأل 3 أسئلة جوهرية عن المستند:
- • What
format? (pdf, word, excel, html?)
- • What
language? (أي لغة مكتوب فيها؟)
- • What character
set? (CP1252, UTF-8, ...)
تحديد هالمعلومات هو Classification problem (مشكلة تصنيف)؛ السيستم
لازم يحزر النوع بناءً على "بصمات" الملف.
⚠️ Complications:
Format/language
الموضوع مش دايماً سهل، فيه تعقيدات زي:
- • Multi-language
single index: الفهرس الواحد ممكن يحتوي كلمات من لغات كثيرة.
- • Mixed
content: إيميل فرنسي ومعه مرفق ألماني (German pdf attachment).
- • Quoted
content: إيميل فرنسي بقتبس فقرات من عقد إنجليزي.
عشان هيك فيه Commercial and open source libraries هي اللي بتتعامل مع
هاض العجقة وبتحل المشاكل.
⚖️ Grain size: Unit document
لازم نحدد الـ Unit document (وحدة المستند)؛ هاض الموضوع بنسميه Grain size (حجم الحبة)، وهو جداً مهم لأنه بحدد دقة النتائج.
- • A file?
(هل هو مجرد ملف؟)
- • An
email? (ممكن إيميل واحد من ضمن ملف mbox كبير).
- • Email with 5
attachments? (مستند واحد ولا كل مرفق لحال؟)
- • A group of files? (زي ملفات PPT أو
LaTeX المقسمة).
Input: "Friends, Romans and Countrymen" ➔ Output: Tokens (Friends, Romans, Countrymen)
الـ Token هو "مثيل لسلسلة من الحروف" (Instance of a sequence of
characters). كل Token بطلع من هذه المرحلة بصير Candidate (مرشح)
ليدخل في الفهرس كـ Entry، بس طبعاً بعد مراحل معالجة ثانية (Further processing).
But what are valid tokens to emit?
🤔 Issues in tokenization
هون بتبدأ المشاكل؛ طلع على هالأمثلة اللي بالسلايدات:
-
Finland's capital
هل نفصلها لـ Finland و s ؟ ولا Finlands ؟ ولا نتركها Finland's ؟
-
Hewlett-Packard
هل نعتبرها Token واحد ولا ثنين؟ هل نكسر الشحطات اللي بينهم؟
(زي state-of-the-art, co-education, lowercase vs lower-case)
-
San Francisco
مستند واحد ولا ثنين؟ (One token or two). قرارك بحدد دقة النتائج.
Numbers: 3/20/91, Mar. 12, 1991, 55 B.C., B-52, (800) 234-2333
الأرقام والتواريخ بكل أشكالها بتمثل تحدي؛ الدكتور حط أمثلة متنوعة زي التواريخ المختصرة والطويلة، وحتى
الـ PGP keys المعقدة زي 324a3df234cb23e.
-
• Often have embedded spaces:
أرقام التلفونات غالباً فيها فراغات بتلخبط الـ Tokenizer.
-
• Older IR systems:
المحركات القديمة كانت تطنش الأرقام، بس اليوم هي Very useful
(جداً مفيدة)؛ زي البحث عن "أكواد الأخطاء" (Error codes) أو الـ Stacktraces على الويب.
-
• Meta-data:
الأرقام غالباً بتتحول لـ Meta-data منفصلة، زي "تاريخ
الإنشاء" (Creation date) أو "تنسيق الملف" (Format).
🌏 Chinese and Japanese: No spaces
في الصينية واليابانية، الكلمات ملزقة ببعض وما فيه فراغات (No spaces):
莎拉波娃现在居住在美国东南部的佛罗里达。
هاض الاشي معناه إنه Not always guaranteed a unique tokenization (مش
دايماً التقطيع بكون وحيد أو مؤكد)، ممكن كلمة تنفهم بطريقتين مختلفتين تماماً.
🕌 Arabic Issues: Bi-directional & Ligatures
لغتنا العربية فيها "أفلام" خاصة فيها ذكرها الدكتور:
-
• Bi-directional (BiDi):
العربي ببدأ من اليمين لليسار، بس لما يدخل رقم (زي 1962) بقلب الترتيب من اليسار لليمين.
-
• Complex Ligatures:
الحروف عندنا بتغير شكلها وبتشبك ببعض (تشبيك الحروف)، وهاد بعمل تعقيد في معالجة شكل الكلمة.
-
• Unicode vs Stored form:
بالرغم من إن العرض على الشاشة (Surface presentation) معقد بسبب الـ Unicode، إلا إن طريقة التخزين
في السيرفرات (Stored form) بتكون Straightforward (بسيطة
ومباشرة).
Slide Example:
.استقلت الجزائر في سنة 1962 بعد 132 عاماً من الاحتلال
الفرنسي
'Algeria achieved its independence in 1962 after 132 years of French occupation.'
🚫 With a stop list, you exclude...
فكرتها إنك تحذف الكلمات الشائعة جداً من القاموس نهائياً. والسبب (Intuition):
-
• They have little semantic
content:
كلمات زي the,
a, and, to, be ما بتعطي معنى فريد للمستند.
-
• There are a lot of them:
هدول الكلمات بياخدوا مساحة خرافية؛ تقريباً ~30% of postings
لأول 30 كلمة شائعة!
📉 But the trend is away from doing this:
اليوم، التوجه هو "الابتعاد" عن حذف كلمات الوقف، والسبب هو تطور التقنيات:
⚠️ You need them for:
-
• Phrase queries:
زي "King of Denmark"، لو
حذفت الـ "of" بضيع المعنى.
-
• Various song titles:
أغاني زي "Let it be" أو
"To be or not to be".
-
• "Relational" queries:
زي "flights to London"، حرف
الـ "to" هون جوهري.
We may need to "normalize" words in indexed text as well as query words into the same form.
لازم نوحد شكل الكلمة (Normalization) سواء كانت في الملفات أو في كلمة البحث، عشان نقدر نعمل Match صح. مثال: بدنا U.S.A والـ USA يتطابقوا.
Result is terms: a term is a (normalized) word type, which is an entry in our IR system dictionary.
الـ Term هو النتيجة النهائية بعد التوحيد، وهو اللي بنخزنه فعلياً في
"قاموس" نظام الاسترجاع.
We most commonly implicitly define equivalence classes of terms by, e.g.,
-
• Deleting periods to form a term:
حذف النقاط.
U.S.A., USA ➔ USA
-
• Deleting hyphens to form a term:
حذف الشحطات.
anti-discriminatory, antidiscriminatory ➔ antidiscriminatory
🔡 Reduce all letters to lower case
-
• Exception: upper case in
mid-sentence?
زي General Motors : لما الحروف الكبيرة
تيجي بنص الجملة، هاض دليل إنها اسم علم.
-
• Policy:
الأفضل تحول كل شي لـ lowercase لأن اليوزرز غالباً بكتبوا بحثهم بالـ small بغض النظر عن القواعد
الصحيحة.
Longstanding Google example:
Query: C.A.T
result is for "cat" not Caterpillar Inc #1
هاض المثال بوجيك كيف التوحيد العنيف في جوجل خلى السيستم يغلط ويفهم إنك بتبحث عن "بسه" وإنت قاصد شركة
المعدات الشهيرة.
An alternative to equivalence classing is to do expansion
بدل ما نوحد الكلمات وقت التخزين، ممكن نعمل Expansion (توسعة) وقت
البحث. يعني السيستم ببحث عن الكلمة وكل "قرايبها" في نفس الوقت.
An example of where this may be useful:
Enter: window ➔ Search: window, windows
Enter: windows ➔ Search: Windows, windows, window
Enter: Windows ➔ Search: Windows
Potentially more powerful, but less efficient
هاد الأسلوب More powerful لأنه أدق وبفهم نية اليوزر (زي مثال ويندوز
نظام التشغيل)، بس هو Less efficient لأنه بخلي السيستم ينفذ عمليات
بحث أكثر في نفس اللحظة.
Do we handle synonyms and homonyms?
كيف السيستم بتعامل مع المترادفات؟ مثلاً بالاعتماد على Hand-constructed
equivalence classes:
car = automobile | color = colour
Two ways to implement this:
-
1. Rewrite to form equivalence-class
terms:
التوحيد وقت التخزين؛ لو الجهاز لقى automobile، بخزنها بالفهرس تحت المصطلح المشترك -car-.
-
2. Or we can expand a query:
التوحيد وقت البحث؛ لو اليوزر كتب automobile، السيستم ببحث تلقائياً عن car كمان.
Reduce inflectional/variant forms to base form
الهدف الأساسي من الـ Lemmatization هو تقليل التصريفات والأشكال
المختلفة للكلمة (Inflectional forms) وترجيعها لشكلها الأساسي.
-
am, are, is ➔ be •
-
car, cars, car's, cars' ➔ car •
(توحيد المفرد والجمع
والملكية)
Example sentence transformation:
Original: the boy's cars are different
colors
Normalized: the boy car be different color ➔
هاض المثال بوجيك كيف الجملة صارت "مفككة" لأصولها؛ الـ Lemmatizer بشتغل "صح" وبرجع الكلمة لشكلها اللي في
القاموس (Dictionary headword form) بناءً على تحليل لغوي دقيق.
Lemmatization implies doing "proper" reduction to dictionary headword form
الـ Lemmatization بتعني إنك تعمل تقليل "صحيح" (Proper reduction) للكلمة عشان ترجعها لأصلها المعجمي
(Dictionary headword).
Reduce terms to their "roots" before indexing
الـ Stemming هو تخفيف الكلمات لجذورها (Roots) قبل ما نفهرسها.
"Stemming" suggests crude affix chopping
-
• language dependent: بيعتمد
عاللغة.
-
• e.g., automate(s), automatic,
automation all reduced to automat.
كلمة Stemming بتوحي بالقص "الخشن" (Crude affix chopping) للزوائد.
for example compressed and compression are both accepted as equivalent to compress.
➔
for exampl compress and compress ar both accept as equival to compress
Commonest algorithm for stemming English
Conventions + 5 phases of reductions
Typical rules in Porter:
sses ➔ ss
ies ➔ i
ational ➔ ate
tional ➔ tion
Weight of word sensitive rules
replacement ➔ replac
cement ➔ cement
الوزن (Weight) بيفرق؛ كلمة Replacement طويلة فاختصرها، بس cement قصيرة خلاها زي ما هي.
English: very mixed results. Helps recall for some queries but harms precision on others
في الإنجليزي، النتائج Mixed (مختلطة)؛ الـ Stemming برفع الـ Recall (بخليك تلاقي ملفات أكثر) بس ممكن يضرب الـ Precision (الدقة بتقل).
E.g., operative (dentistry) ➔ oper
مثلاً لو بحثت عن كلمة operative (بمعنى عملية أسنان)،
والسيستم عملها Stemming لـ oper ، ممكن تطلعلك نتائج عن "عمليات
جراحية" عامة، وهيك الدقة بتضيع (Precision harms).
Definitely useful for Spanish, German, ...
بس في لغات ثانية زي الإسبانية أو الألمانية، الـ Stemming هو إشي Essential (ضروري جداً) ومفيد بدون نقاش بسبب تعقيد تصريفات الكلمات
عندهم.
The above methods embody transformations that are: Language-specific, and often Application-specific
كل الطرق اللي حكينا عنها (Tokenization, Normalization, Stemming) هي عمليات Language-specific (بتعتمد على اللغة)؛ يعني اللي بضبط للإنجليزي ما بضبط
للعربي. وحتى أحياناً بتكون Application-specific (بتعتمد على نوع
التطبيق أو المجال اللي بتشتغل فيه).
Both open source and commercial plug-ins are available for handling these
عشان تريح راسك، فيه Plug-ins (إضافات) جاهزة؛ منها Open source (مفتوح المصدر) ومنها Commercial (تجارية بفلوس)، بتتعامل مع هاي التعقيدات وبتعطيك الـ
Stemming والتوحيد المناسب لكل لغة.
✅ End of Text Operations
خلصنا شرح عمليات معالجة النصوص. القسم الجاي رح نحكي عن كيفية بناء الـ Inverted Index بالتفصيل.