Phrase Queries | Print Version

We want to be able to answer queries such as "stanford university" – as a phrase

بدنا السيستم يكون قادر يجاوب على جمل كاملة زي "stanford university" كـ عبارة وحدة (Phrase).

NO MATCH ❌

"I went to university at Stanford"

الكلمات مبعثرة ومش ورا بعض.

MATCH ✅

"The stanford university research..."

الكلمات ورا بعض تماماً.

Concept: One of the few "advanced search" ideas that works

هذه الميزة من "البحث المتقدم" هي الأكثر فهماً واستخداماً من قبل الناس؛ لأنها منطقية جداً.

The Problem:

لتحقيق هذا، ما عاد يكفي نخزن بس <term : docs> (الكلمة ورقم الملف)؛ نحتاج "معلومات مكانية" أكثر.

Attempt 1: Biword indexes

Index every consecutive pair of terms in the text as a phrase

أول محاولة للحل: نفهرس "كل كلمتين ورا بعض" (Consecutive pair) كأنهم وحدة واحدة مستقلة.

"Text: "Friends, Romans, Countrymen"

friends romans + romans countrymen

Two-word phrase processing is now immediate!

البحث عن أي عبارة من كلمتين صار فوري؛ السيستم بيتعامل معها ككلمة واحدة وبيسحب ملفاتها فوراً.

Longer phrase queries

Can be processed by breaking them into biwords

طيب لو الجملة طويلة (أكثر من كلمتين)؟ بنقسمها لأزواج ونطبق قاعدة الـ AND.

"stanford university palo alto" ➔

(stanford university) AND (university palo) AND (palo alto)

⚠️ False Positives (مشكلة النتائج الخاطئة)

السيستم ممكن يعطيك ملف فيه كل "الأزواج" بس مش بالترتيب واللي بدك اياه!

Example of a "Wrong" Document:

"The student at stanford university spoke about university palo problems during his visit to palo alto."

هذا الملف حقق شرط الـ AND (فيه كل الأزواج)، بس الجملة الأصلية "stanford university palo alto" مش موجودة كـ قطعة واحدة!

Other Critical Issues

Index Blowup

حجم القاموس يتضخم بشكل هائل لأن كل زوج كلمات جديد في اللغة يحتاج مكاناً مستقلاً. 💥

Infeasible for Longer Phrases

من المستحيل عملياً تخزين 3 كلمات أو أكثر؛ لأن عدد الاحتمالات يصبح فلكياً. 🚫

Solution 2: Positional indexes

Store the position(s) of each term in the postings. الحل الأذكى: لكل كلمة، بنخزن مواقع ظهورها (Positions) داخل الملف.

:Structure

                    <term, num_docs;

                      doc1: pos1, pos2, ...;

                      doc2: pos1, ...;

                    >

⚙️ Example & Strategy

                <be: 993427;

                ID 1: 7, 18, 33, 72, 86, 231

                ID 2: 3, 149

                ID 4: 17, 191, 291...

                >

"to be or not to be"

لازم ندور على كلمات ورا بعض بالترتيب!

Proximity Strategy

نهتم بـ "مدى قرب الكلمات" (Proximity).

The Challenge

نبحث عن علاقة مكانية مش بس وجود.

Workflow: Processing a Phrase Query

Extract Posting Lists 1

بنسحب القوائم لكل كلمة (to, be, or, not) بشكل مستقل من الفهرس الموقعي.

Positional Intersection Merge 2

نبحث عن الملفات المشتركة، وبداخل كل ملف، نفحص شرط التجاور: pos2 = pos1 + 1.

...EXECUTING POSITIONAL MERGE
                        <
[ MATCH FOUND ] Document ID: 2
                    
                        to: [17]   be: [18]   (18 = 17 + 1) ✅
                    
[ SEARCHING ] Document ID: 4
                    
to positions: [8, 16, 190]
be positions: [17, 191]

                        Matches: (16, 17) & (190, 191) ✅✅

Recursive Full-Phrase Match 3

بنكرر نفس العملية لكل كلمات الجملة (to be ➔ be or ➔ or not) لضمان اتصال السلسلة كاملة.

💡 ملاحظة: نفس هذه الطريقة تُستخدم لبحث "التقارب" (Proximity) ولكن بمسافات أكبر من 1.

Example: Positional Index Construction

The Corpus (3 Documents):

:DOC 1

"machine learning is powerful"

:DOC 2

"deep learning powers machine intelligence"

:DOC 3

"machine intelligence and learning"

The Resulting Index (Step 1):

تخزين رقم الملف ومواقع الظهور (0-indexed).

machine: {1: [0], 2: [3], 3: [0]}

learning: {1: [1], 2: [1], 3: [3]}

Step 2: Intersection Algorithm

Query: "machine learning"

الهدف: نلاقي الملفات اللي فيها كلمة learning وكلمة machine مباشرة ورا بعض.

The Mathematical Rule:

For each docID:

Is position(learning) == position(machine) + 1 ?

The Data to Check:

"machine" ➔ {1: [0], 2: [3], 3: [0]}
"learning" ➔ {1: [1], 2: [1], 3: [3]}

Execution & Results

DOCID	MACHINE [POS]	LEARNING [POS]	RULE CHECK	MATCH?
1	[0]	[1]	1 == 0 + 1	✅ YES
2	[3]	[1]	1 != 3 + 1	❌ NO
3	[0]	[3]	3 != 0 + 1	❌ NO

الخلاصة: فقط الملف رقم 1 يحتوي على العبارة المطلوبة بالترتيب الصحيح.

Proximity queries

LIMIT! /3 STATUTE /3 FEDERAL /2 TORT

مثال لاستعلام متقدم يستخدم بحث "التقارب" (Proximity).

Meaning of /k:

📏

الرمز /k يعني "ضمن مجال k من الكلمات".
مثلاً A /3 B يعني أن B يجب أن تظهر في غضون 3 كلمات قبل أو بعد A.

Positional Indexes are MUST:

هنا تظهر القوة الحقيقية للـ Positional Indexes؛ مستحيل نقدر نعمل هالحكي بالـ Biword index لأنه لا يعرف المسافات، فقط التلاصق.

Why it Grows: Impact of Document Length

Need an entry for EACH occurrence

في الفهرس العادي، بنسجل `docID` مرة وحدة للملف. بس في الموقعي، لازم نسجل كل مكان ظهرت فيه الكلمة جوا هاض الملف.

TERM FREQ: 0.1% EXAMPLE

Doc Size	Normal	Positional
1,000	1	1
100,000	1	100

WEB PAGE

terms (Short) 1,000~

BOOKS / FILINGS

terms (Massive) +100,000

"The longer the document, the larger the gap between normal and positional indexes"

The Storage Trade-offs

Significant Expansion

الفهرس الموقعي بياخد مساحة تخزين ضخمة جداً؛ لأنه بيخزن كل "موضع" (رقم مكان) بتظهر فيه الكلمة.

* Even though indices can be compressed, the growth remains "Substantial".

Industry Standard

بالرغم من التكلفة العالية للمساحة، بضل هو المعيار الأساسي؛ لأنه بدونه مستحيل نعمل جمل بحث (Phrase queries) دقيقة.

💡 الخلاصة: احنا بنضحي بـ "المساحة" عشان نكسب "القوة والدقة". أغلب محركات البحث اليوم بتستخدم الـ Positional Index كجزء أساسي في ترتيب النتائج (Ranking).

Positional Index: Rules of Thumb

2x to 4x Size Expansion

الفهرس الموقعي عادة بكون حجمه من ضعفين لـ 4 أضعاف حجم الفهرس العادي (Non-positional).

📦

35% to 50% of Total Corpus

مقارنة بحجم البيانات الأصلية ككل، الفهرس بياخد مساحة ضخمة بتوصل لـ نصف حجم البيانات الأصلية!

Context: English-like Languages

هذه النسب هي "المتوقع" في اللغات الشبيهة بالإنجليزية؛ قد تختلف في لغات أخرى حسب طبيعة تركيب الكلمات.

🌐

⚠️ تذكر: الفهرس العادي كان بياخد بس 10% من المساحة. هاد التضخم هو "الثمن" اللي بنقصه عشان نحصل على بحث ذكي ودقيق!

Combination Schemes (The Hybrid Solution)

يمكن دمج الحلين معاً (Biword + Positional) لتحقيق أفضل توازن بين السرعة والحجم.

Fast Track (Biword) ⚡

نستخدم الـ Biword للعبارات المشهورة جداً (مثل "Michael Jackson") والكلمات الشائعة (مثل "The Who") لتجنب الـ Merge المكلف.

Precision Track (Positional) 🎯

نستخدم الـ Positional Index لبقية العبارات النادرة لضمان الدقة وتوفير المساحة.

"Best of both worlds: Speed for common phrases, flexibility for everything else"

Phrase Queries & Positional Indexes