Full-Text Indexing and Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Common English Stop Words (partial list):
 
Articles:        a, an, the
Pronouns:        I, you, he, she, it, we, they, me, him, her, us, them
                 my, your, his, her, its, our, their
                 this, that, these, those, who, what, which
Prepositions:    in, on, at, to, for, with, by, from, of, about
                 into, through, during, before, after, above, below
                 between, under, again, further, then, once
Conjunctions:    and, or, but, if, because, as, while, although
Auxiliary verbs: is, am, are, was, were, be, been, being
                 have, has, had, do, does, did, will, would
                 shall, should, can, could, may, might, must
Adverbs:         very, just, only, also, still, already, even
                 here, there, when, where, why, how
Other:           not, no, nor, too, so, than, such, own, same
 
Total: Typically 100-300 words depending on list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Zipf's Law: frequency ∝ 1/rank
 
Example from typical English corpus:
 
Rank | Word    | Frequency | % of Total | Cumulative %
-----|---------|-----------|------------|-------------
1    | the     | 7.0%      | 7.0%       | 7.0%
2    | be      | 4.0%      | 4.0%       | 11.0%
3    | to      | 2.5%      | 2.5%       | 13.5%
4    | of      | 2.5%      | 2.5%       | 16.0%
5    | and     | 2.3%      | 2.3%       | 18.3%
6    | a       | 2.0%      | 2.0%       | 20.3%
7    | in      | 1.8%      | 1.8%       | 22.1%
8    | that    | 1.2%      | 1.2%       | 23.3%
9    | have    | 1.0%      | 1.0%       | 24.3%
10   | I       | 1.0%      | 1.0%       | 25.3%
 
Top 10 words = 25% of all word occurrences!
Top 100 words = 50% of all word occurrences!
Top 1000 words = 75% of all word occurrences!
 
Long tail: 100,000+ unique words share remaining 25%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Indexing 1 Million Documents (average 500 words each):
 
Without stop word removal:
  Total tokens indexed: 500,000,000
  Unique terms: ~1,000,000
  Index size: ~8 GB
  
  Posting list for "the": ~980,000 entries (appears in 98% of docs)
  Posting list for "database": ~50,000 entries
 
With stop word removal (100 stop words removed):
  Tokens removed: ~125,000,000 (25% of corpus)
  Total tokens indexed: 375,000,000
  Unique terms: ~999,900 (only 100 terms removed, but huge posting lists gone!)
  Index size: ~5 GB
  
  37.5% reduction in index size!
  No more million-entry posting lists for "the", "and", etc.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Query: "the database performance problem"
 
Without stop word removal:
  Step 1: Fetch posting list for "the" → 980,000 doc IDs
  Step 2: Fetch posting list for "database" → 50,000 doc IDs
  Step 3: Fetch posting list for "performance" → 30,000 doc IDs
  Step 4: Fetch posting list for "problem" → 40,000 doc IDs
  Step 5: Intersect all four lists
  
  Bottleneck: Must process 980,000 entries for "the"
  Even with skip pointers, "the" dominates processing time
 
With stop word removal (query becomes "database performance problem"):
  Step 1: Fetch posting list for "database" → 50,000 doc IDs
  Step 2: Fetch posting list for "performance" → 30,000 doc IDs
  Step 3: Fetch posting list for "problem" → 40,000 doc IDs
  Step 4: Intersect three lists
  
  No million-entry list to process
  ~20x faster query execution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

def build_custom_stop_list(documents, threshold=0.8, min_count=1000):
    """
    Build corpus-specific stop word list.
    
    Stop word criteria:
    1. Appears in more than threshold% of documents
    2. Appears at least min_count times total
    """
    from collections import Counter
    
    doc_count = len(documents)
    term_doc_counts = Counter()  # How many docs contain each term
    term_total_counts = Counter()  # Total occurrences
    
    for doc in documents:
        tokens = tokenize(doc)
        term_total_counts.update(tokens)
        term_doc_counts.update(set(tokens))  # Unique per doc
    
    stop_words = set()
    for term, doc_freq in term_doc_counts.items():
        doc_ratio = doc_freq / doc_count
        total_count = term_total_counts[term]
        
        if doc_ratio >= threshold and total_count >= min_count:
            stop_words.add(term)
            print(f"Stop word: '{term}' in {doc_ratio:.1%} of docs, {total_count} occurrences")
    
    return stop_words
 
# Example output:
# Stop word: 'the' in 98.2% of docs, 15234567 occurrences
# Stop word: 'is' in 89.5% of docs, 4567890 occurrences
# Stop word: 'a' in 92.1% of docs, 8901234 occurrences
# ...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Query: "to be or not to be"
 
With stop word removal:
  Query terms after filtering: [... nothing! All removed!]
  Result: No results, or match everything
  
  If phrase expanded: [be, be] → meaningless
  Complete loss of query intent
 
Without stop word removal:
  Query: Match exact phrase "to be or not to be"
  Result: Shakespeare's Hamlet, quotes, literary analysis
  
  The phrase IS the content!
 
Other examples where stops define meaning:
  "the who" (band) vs "who" (question word)
  "the office" (TV show) vs "office" (workplace)
  "let it be" (Beatles song) vs "let be" (maybe different meaning?)
  "not" (critical negation word)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Stop words that carry meaning:
 
"not" — Critical for sentiment and meaning
  "not good" vs "good" → opposite meanings!
  "not working" vs "working" → opposite states
  
"no" — Negation
  "no results" vs "results" → very different queries
  
"only" — Restriction  
  "only database" → exclusive requirement
  
"very", "too" — Intensity
  "too slow" vs "slow" → severity differs
  
Removing these changes query semantics!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Query-Time Stop Word Strategies:
 
Strategy 1: Remove stops only if other terms exist
  Query: "the database" → search for "database" (drop "the")
  Query: "the the" → search for "the the" (keep, no content terms)
  
Strategy 2: Use stops for phrase matching, ignore for ranking
  Query: "the quick brown fox"
  
  Step 1 - Ranking: Score by "quick", "brown", "fox" (ignore "the")
  Step 2 - Phrase validation: Verify "the" appears in correct position
  
Strategy 3: Lower stop word weight rather than remove
  Query: "the database is slow"
  Weights: the(0.01), database(1.0), is(0.01), slow(0.8)
  
  Stops contribute near-zero to score but aren't removed

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Position-Only Stop Word Indexing:
 
Regular terms: Store full posting list (docID, freq, positions)
Stop words: Store positions only (for phrase matching)
 
Index structure:
 
"database" → [(doc1, 3, [5,12,45]), (doc2, 1, [8]), ...]
            Full postings for ranking
 
"the" → [doc1:[0,3,7,19,32,...], doc2:[1,5,9,...], ...]
       No frequency (always high)
       No score contribution
       Positions only for phrase matching
 
"is" → [doc1:[4,15], doc2:[6,12], ...]
      Same: positions only
 
Benefits:
- Can still match phrases with stop words
- No score pollution from stops
- Smaller index than full stop word postings
- Larger index than complete removal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

def classify_query_terms(query_terms, collection_stats):
    """
    Dynamically determine which terms to treat as stops.
    No static stop word list!
    """
    classified_terms = []
    
    for term in query_terms:
        df = collection_stats.get_document_frequency(term)
        collection_df_ratio = df / collection_stats.total_docs
        
        if collection_df_ratio > 0.90:
            # Appears in >90% of docs: Treat as stop
            role = 'stop'
        elif collection_df_ratio > 0.50:
            # Appears in 50-90%: Low weight term
            role = 'low_weight'  
        else:
            # Appears in <50%: Full weight term
            role = 'content'
            
        classified_terms.append({
            'term': term,
            'role': role,
            'df': df,
            'idf': math.log(collection_stats.total_docs / (df + 1))
        })
    
    return classified_terms
 
# Example:
# "the database performance problem"
# → [
#     {'term': 'the', 'role': 'stop', 'df': 980000, 'idf': 0.02},
#     {'term': 'database', 'role': 'content', 'df': 50000, 'idf': 2.99},
#     {'term': 'performance', 'role': 'content', 'df': 30000, 'idf': 3.51},
#     {'term': 'problem', 'role': 'low_weight', 'df': 400000, 'idf': 0.92}
#   ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Languages with Different Stop Word Properties:
 
Chinese/Japanese:
- No articles (the, a, an)
- No spaces between words
- Requires tokenization (word segmentation) first
- Particles may function as stops (Japanese: は, が, を)
- Character-based search may not need stops
 
German:
- Compound words: "Datenbankoptimierung" = "database optimization"
- Must decompose compounds before stop word analysis
- Case endings create more variations
 
Agglutinative Languages (Turkish, Finnish):
- Words formed by adding many suffixes
- "evlerinizden" = "from your houses" (one word!)
- Morphological analysis needed before stop word removal
 
Arabic/Hebrew:
- Articles attach to words: ال (al-) = "the"
- Must strip prefixes before analysis
- Different stop word lists needed

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

-- PostgreSQL uses text search configurations with stop words
 
-- View current stop words for English
SELECT * FROM ts_debug('english', 'The quick brown fox');
 
-- lexeme | The quick brown fox is jumping
-- --------+--------------------------------
-- Output shows which tokens are filtered
 
-- Custom dictionary without stop words
CREATE TEXT SEARCH DICTIONARY english_nostop (
    TEMPLATE = snowball,
    Language = english,
    StopWords = ''  -- Empty = no stop word removal
);
 
-- Use custom config
CREATE TEXT SEARCH CONFIGURATION english_nostop_config (COPY = english);
ALTER TEXT SEARCH CONFIGURATION english_nostop_config
    ALTER MAPPING FOR asciiword WITH english_nostop;
 
-- Compare results
SELECT to_tsvector('english', 'The quick brown fox');
-- Result: 'brown':3 'fox':4 'quick':2  (the removed)
 
SELECT to_tsvector('english_nostop_config', 'The quick brown fox');  
-- Result: 'the':1 'brown':3 'fox':4 'quick':2  (the kept)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

// Elasticsearch analyzer configuration with stop words
 
PUT /my_index
{
  "settings": {
    "analysis": {
      "filter": {
        "custom_stop": {
          "type": "stop",
          "stopwords": ["_english_"],  // Use default English
          "ignore_case": true
        },
        "minimal_stop": {
          "type": "stop", 
          "stopwords": ["the", "a", "an", "is", "are"]  // Minimal list
        }
      },
      "analyzer": {
        "custom_analyzer": {
          "type": "custom",
          "tokenizer": "standard",
          "filter": ["lowercase", "custom_stop"]
        },
        "no_stop_analyzer": {
          "type": "custom",
          "tokenizer": "standard",
          "filter": ["lowercase"]  // No stop filter = keep everything
        }
      }
    }
  },
  "mappings": {
    "properties": {
      "title": {
        "type": "text",
        "analyzer": "custom_analyzer"
      },
      "body": {
        "type": "text",
        "analyzer": "no_stop_analyzer"
      }
    }
  }
}