"""
Web Crawler and Indexer - Unit 7
CS 3308: Information Retrieval
This web crawler implements:
- Depth-first search (DFS) traversal of web pages
- URL frontier with 500-page limit
- HTML tag removal using BeautifulSoup
- Porter Stemmer integration
- Stop word filtering
- TF-IDF calculation
- Database storage compatible with Unit 5 search engine
Author: Student
Date: 2026
"""
import sys
import os
import re
import sqlite3
import math
import time
from collections import defaultdict
# Check for required libraries
try:
import requests
from bs4 import BeautifulSoup
from [Link] import urljoin, urlparse
except ImportError:
print("Error: Required libraries not found.")
print("Please install: pip install requests beautifulsoup4")
[Link](1)
#
=======================================================================
======
# STOP WORDS LIST
#
=======================================================================
======
STOP_WORDS = {
'the', 'of', 'and', 'to', 'in', 'you', 'it', 'with', 'that', 'or',
'was', 'he', 'is', 'for', 'this', 'his', 'as', 'not', 'at', 'by',
'all', 'they', 'but', 'be', 'on', 'from', 'had', 'her', 'work',
'are',
'any', 'she', 'if', 'said', 'so', 'which', 'have', 'do', 'we',
'no',
'my', 'were', 'them', 'their', 'him', 'one', 'will', 'me', 'there',
'who', 'up', 'other', 'an', 'its', 'when', 'what', 'can', 'may',
'into',
'out', 'must', 'your', 'then', 'would', 'could', 'more', 'now',
'has',
'like', 'down', 'where', 'been', 'through', 'did', 'away', 'these',
'such', 'set', 'back', 'some', 'than', 'way', 'made', 'our',
'after',
'well', 'should', 'get', 'even', 'am', 'go', 'saw', 'just', 'put',
'while', 'ever', 'off', 'here', 'also'
}
#
=======================================================================
======
# PORTER STEMMER CLASS
#
=======================================================================
======
class PorterStemmer:
def __init__(self):
self.b = ""
self.k = 0
self.k0 = 0
self.j = 0
def cons(self, i):
if self.b[i] == 'a' or self.b[i] == 'e' or self.b[i] == 'i' or
self.b[i] == 'o' or self.b[i] == 'u':
return 0
if self.b[i] == 'y':
if i == self.k0:
return 1
else:
return (not [Link](i - 1))
return 1
def m(self):
n = 0
i = self.k0
while 1:
if i > self.j:
return n
if not [Link](i):
break
i = i + 1
i = i + 1
while 1:
while 1:
if i > self.j:
return n
if [Link](i):
break
i = i + 1
i = i + 1
n = n + 1
while 1:
if i > self.j:
return n
if not [Link](i):
break
i = i + 1
i = i + 1
def vowelinstem(self):
for i in range(self.k0, self.j + 1):
if not [Link](i):
return 1
return 0
def doublec(self, j):
if j < (self.k0 + 1):
return 0
if (self.b[j] != self.b[j-1]):
return 0
return [Link](j)
def cvc(self, i):
if i < (self.k0 + 2) or not [Link](i) or [Link](i-1) or
not [Link](i-2):
return 0
ch = self.b[i]
if ch == 'w' or ch == 'x' or ch == 'y':
return 0
return 1
def ends(self, s):
length = len(s)
if s[length - 1] != self.b[self.k]:
return 0
if length > (self.k - self.k0 + 1):
return 0
if self.b[self.k-length+1:self.k+1] != s:
return 0
self.j = self.k - length
return 1
def setto(self, s):
length = len(s)
self.b = self.b[:self.j+1] + s + self.b[self.j+length+1:]
self.k = self.j + length
def r(self, s):
if self.m() > 0:
[Link](s)
def step1ab(self):
if self.b[self.k] == 's':
if [Link]("sses"):
self.k = self.k - 2
elif [Link]("ies"):
[Link]("i")
elif self.b[self.k - 1] != 's':
self.k = self.k - 1
if [Link]("eed"):
if self.m() > 0:
self.k = self.k - 1
elif ([Link]("ed") or [Link]("ing")) and
[Link]():
self.k = self.j
if [Link]("at"):
[Link]("ate")
elif [Link]("bl"):
[Link]("ble")
elif [Link]("iz"):
[Link]("ize")
elif [Link](self.k):
self.k = self.k - 1
ch = self.b[self.k]
if ch == 'l' or ch == 's' or ch == 'z':
self.k = self.k + 1
elif (self.m() == 1 and [Link](self.k)):
[Link]("e")
def step1c(self):
if ([Link]("y") and [Link]()):
self.b = self.b[:self.k] + 'i' + self.b[self.k+1:]
def step2(self):
if self.b[self.k - 1] == 'a':
if [Link]("ational"):
self.r("ate")
elif [Link]("tional"):
self.r("tion")
elif self.b[self.k - 1] == 'c':
if [Link]("enci"):
self.r("ence")
elif [Link]("anci"):
self.r("ance")
elif self.b[self.k - 1] == 'e':
if [Link]("izer"):
self.r("ize")
elif self.b[self.k - 1] == 'l':
if [Link]("bli"):
self.r("ble")
elif [Link]("alli"):
self.r("al")
elif [Link]("entli"):
self.r("ent")
elif [Link]("eli"):
self.r("e")
elif [Link]("ousli"):
self.r("ous")
elif self.b[self.k - 1] == 'o':
if [Link]("ization"):
self.r("ize")
elif [Link]("ation"):
self.r("ate")
elif [Link]("ator"):
self.r("ate")
elif self.b[self.k - 1] == 's':
if [Link]("alism"):
self.r("al")
elif [Link]("iveness"):
self.r("ive")
elif [Link]("fulness"):
self.r("ful")
elif [Link]("ousness"):
self.r("ous")
elif self.b[self.k - 1] == 't':
if [Link]("aliti"):
self.r("al")
elif [Link]("iviti"):
self.r("ive")
elif [Link]("biliti"):
self.r("ble")
elif self.b[self.k - 1] == 'g':
if [Link]("logi"):
self.r("log")
def step3(self):
if self.b[self.k] == 'e':
if [Link]("icate"):
self.r("ic")
elif [Link]("ative"):
self.r("")
elif [Link]("alize"):
self.r("al")
elif self.b[self.k] == 'i':
if [Link]("iciti"):
self.r("ic")
elif self.b[self.k] == 'l':
if [Link]("ical"):
self.r("ic")
elif [Link]("ful"):
self.r("")
elif self.b[self.k] == 's':
if [Link]("ness"):
self.r("")
def step4(self):
if self.b[self.k - 1] == 'a':
if [Link]("al"):
pass
else:
return
elif self.b[self.k - 1] == 'c':
if [Link]("ance"):
pass
elif [Link]("ence"):
pass
else:
return
elif self.b[self.k - 1] == 'e':
if [Link]("er"):
pass
else:
return
elif self.b[self.k - 1] == 'i':
if [Link]("ic"):
pass
else:
return
elif self.b[self.k - 1] == 'l':
if [Link]("able"):
pass
elif [Link]("ible"):
pass
else:
return
elif self.b[self.k - 1] == 'n':
if [Link]("ant"):
pass
elif [Link]("ement"):
pass
elif [Link]("ment"):
pass
elif [Link]("ent"):
pass
else:
return
elif self.b[self.k - 1] == 'o':
if [Link]("ion") and (self.b[self.j] == 's' or
self.b[self.j] == 't'):
pass
elif [Link]("ou"):
pass
else:
return
elif self.b[self.k - 1] == 's':
if [Link]("ism"):
pass
else:
return
elif self.b[self.k - 1] == 't':
if [Link]("ate"):
pass
elif [Link]("iti"):
pass
else:
return
elif self.b[self.k - 1] == 'u':
if [Link]("ous"):
pass
else:
return
elif self.b[self.k - 1] == 'v':
if [Link]("ive"):
pass
else:
return
elif self.b[self.k - 1] == 'z':
if [Link]("ize"):
pass
else:
return
else:
return
if self.m() > 1:
self.k = self.j
def step5(self):
self.j = self.k
if self.b[self.k] == 'e':
a = self.m()
if a > 1 or (a == 1 and not [Link](self.k-1)):
self.k = self.k - 1
if self.b[self.k] == 'l' and [Link](self.k) and self.m()
> 1:
self.k = self.k -1
def stem(self, p, i, j):
self.b = p
self.k = j
self.k0 = i
if self.k <= self.k0 + 1:
return self.b
self.step1ab()
self.step1c()
self.step2()
self.step3()
self.step4()
self.step5()
return self.b[self.k0:self.k+1]
#
=======================================================================
======
# WEB CRAWLER CLASS
#
=======================================================================
======
class WebCrawler:
def __init__(self, start_url, db_path="[Link]",
max_pages=500):
self.start_url = start_url
self.db_path = db_path
self.max_pages = max_pages
# Crawling state
[Link] = set()
self.to_crawl = [start_url]
self.url_frontier_count = 1
# Statistics
[Link] = 0
[Link] = 0
[Link] = 0
self.stopwords_count = 0
# Data structures
[Link] = {}
[Link] = PorterStemmer()
[Link] = [Link](r'\W+')
# Database connection
[Link] = None
[Link] = None
def setup_database(self):
"""Initialize SQLite database with required tables"""
[Link] = [Link](self.db_path)
[Link].isolation_level = None
[Link] = [Link]()
# Document Dictionary Table
[Link]("DROP TABLE IF EXISTS DocumentDictionary")
[Link]("DROP INDEX IF EXISTS idxDocumentDictionary")
[Link]("CREATE TABLE IF NOT EXISTS DocumentDictionary
(DocumentName TEXT, DocId INTEGER)")
[Link]("CREATE INDEX IF NOT EXISTS
idxDocumentDictionary ON DocumentDictionary (DocId)")
# Term Dictionary Table
[Link]("DROP TABLE IF EXISTS TermDictionary")
[Link]("DROP INDEX IF EXISTS idxTermDictionary")
[Link]("CREATE TABLE IF NOT EXISTS TermDictionary
(Term TEXT, TermId INTEGER)")
[Link]("CREATE INDEX IF NOT EXISTS idxTermDictionary
ON TermDictionary (TermId)")
# Postings Table
[Link]("DROP TABLE IF EXISTS Posting")
[Link]("DROP INDEX IF EXISTS idxPosting1")
[Link]("DROP INDEX IF EXISTS idxPosting2")
[Link]("CREATE TABLE IF NOT EXISTS Posting (TermId
INTEGER, DocId INTEGER, tfidf REAL, docfreq INTEGER, termfreq
INTEGER)")
[Link]("CREATE INDEX IF NOT EXISTS idxPosting1 ON
Posting (TermId)")
[Link]("CREATE INDEX IF NOT EXISTS idxPosting2 ON
Posting (DocId)")
def fetch_page(self, url):
"""Fetch a web page and return its content"""
try:
headers = {'User-Agent': 'Mozilla/5.0 (Educational Web
Crawler)'}
response = [Link](url, headers=headers, timeout=10)
response.raise_for_status()
return [Link]
except Exception as e:
print(f"Error fetching {url}: {str(e)}")
return None
def extract_text(self, html_content):
"""Extract text from HTML using BeautifulSoup"""
try:
soup = BeautifulSoup(html_content, '[Link]')
# Remove script and style elements
for script in soup(["script", "style"]):
[Link]()
# Get text from paragraphs, headings, and other text
elements
text_elements = soup.find_all(['p', 'h1', 'h2', 'h3', 'h4',
'h5', 'h6', 'li', 'div', 'span'])
text = ' '.join([elem.get_text() for elem in
text_elements])
# Clean up whitespace
text = ' '.join([Link]())
return text
except Exception as e:
print(f"Error extracting text: {str(e)}")
return ""
def extract_links(self, html_content, base_url):
"""Extract all links from HTML content"""
try:
soup = BeautifulSoup(html_content, '[Link]')
links = []
for link in soup.find_all('a', href=True):
href = link['href']
# Convert relative URLs to absolute
absolute_url = urljoin(base_url, href)
# Only include HTTP/HTTPS links
if absolute_url.startswith(('[Link] '[Link]
[Link](absolute_url)
return links
except Exception as e:
print(f"Error extracting links: {str(e)}")
return []
def is_valid_url(self, url):
"""Check if URL should be crawled"""
# Skip common file types
skip_extensions = ['.pdf', '.png', '.jpg', '.jpeg', '.gif',
'.css', '.js',
'.zip', '.exe', '.mp3', '.mp4', '.doc',
'.docx', '.xml']
for ext in skip_extensions:
if [Link]().endswith(ext):
return False
return True
def parse_tokens(self, text):
"""Parse tokens from text and add to index"""
# Replace tabs with spaces
text = [Link]('\t', ' ')
text = [Link]()
# Split into tokens
tokens = [Link](text)
for token in tokens:
token = [Link]('\n', '')
token = [Link]().strip()
# Increment total token count
[Link] += 1
# Apply filtering rules
if len(token) < 3: # Minimum length 3
continue
if token in STOP_WORDS:
self.stopwords_count += 1
continue
# Check if numeric
if [Link]():
continue
# Check if starts with punctuation
if token and token[0] in '!"#$%&\'()*+,-./:;<=>?
@[\\]^_`{|}~':
continue
# Apply Porter stemming
stemmed = [Link](token, 0, len(token) - 1)
# Add to index
if stemmed not in [Link]:
[Link] += 1
[Link][stemmed] = Term()
[Link][stemmed].termid = [Link]
[Link][stemmed].docids = {}
[Link][stemmed].docs = 0
# Update document frequency
if [Link] not in [Link][stemmed].docids:
[Link][stemmed].docs += 1
[Link][stemmed].docids[[Link]] = 0
# Update term frequency
[Link][stemmed].docids[[Link]] += 1
[Link][stemmed].termfreq += 1
def write_index(self):
"""Write the inverted index to database"""
print("\nWriting index to database...")
# Insert terms into TermDictionary
for term in [Link]():
if term:
[Link]('INSERT INTO TermDictionary VALUES (?,
?)',
(term, [Link][term].termid))
# Calculate TF-IDF and insert postings
N = [Link]
for term in [Link]():
if term:
df = [Link][term].docs
idf = math.log10(N / df) if df > 0 else 0
for docid in [Link][term].[Link]():
tf = [Link][term].docids[docid]
tfidf = tf * idf
if tfidf > 0:
[Link]('INSERT INTO Posting VALUES
(?, ?, ?, ?, ?)',
([Link][term].termid,
docid, tfidf, df, tf))
def crawl(self):
"""Main crawling loop using depth-first search"""
print(f"Starting crawl from: {self.start_url}")
print(f"URL frontier limit: {self.max_pages} pages")
print("-" * 70)
self.setup_database()
start_time = [Link]()
while self.to_crawl and len([Link]) < self.max_pages:
# Pop URL from queue (depth-first)
current_url = self.to_crawl.pop(0)
# Skip if already crawled
if current_url in [Link]:
continue
# Skip invalid URLs
if not self.is_valid_url(current_url):
[Link](current_url)
continue
print(f"Crawling [{len([Link]) +
1}/{self.max_pages}]: {current_url[:70]}")
# Fetch page
html_content = self.fetch_page(current_url)
if not html_content:
[Link](current_url)
continue
# Extract and index text
text = self.extract_text(html_content)
if text:
[Link] += 1
[Link]("INSERT INTO DocumentDictionary VALUES
(?, ?)",
(current_url, [Link]))
self.parse_tokens(text)
# Extract links if under frontier limit
if self.url_frontier_count < self.max_pages:
links = self.extract_links(html_content, current_url)
for link in links:
if link not in [Link] and link not in
self.to_crawl:
if self.url_frontier_count < self.max_pages:
self.to_crawl.append(link)
self.url_frontier_count += 1
# Mark as crawled
[Link](current_url)
# Write index to database
self.write_index()
# Commit and close
[Link]()
[Link]()
end_time = [Link]()
elapsed = end_time - start_time
# Print statistics
print("\n" + "=" * 70)
print("CRAWLING STATISTICS")
print("=" * 70)
print(f"Website crawled: {self.start_url}")
print(f"Documents processed: {[Link]}")
print(f"Total tokens parsed: {[Link]}")
print(f"Unique terms in index: {[Link]}")
print(f"Stop words filtered: {self.stopwords_count}")
print(f"Time elapsed: {elapsed:.2f} seconds ({elapsed/60:.2f}
minutes)")
print("=" * 70)
print(f"\nDatabase saved to: {self.db_path}")
#
=======================================================================
======
# TERM CLASS
#
=======================================================================
======
class Term:
def __init__(self):
[Link] = 0
[Link] = 0
[Link] = 0
[Link] = {}
#
=======================================================================
======
# MAIN PROGRAM
#
=======================================================================
======
def main():
print("=" * 70)
print("WEB CRAWLER - CS 3308 Information Retrieval")
print("=" * 70)
print("\nThis crawler will:")
print("- Crawl up to 500 web pages using depth-first search")
print("- Extract text using BeautifulSoup (removes HTML tags)")
print("- Apply Porter stemming to all terms")
print("- Filter stop words, numbers, and short terms")
print("- Calculate TF-IDF weights")
print("- Store results in SQLite database")
print("=" * 70)
# Get starting URL from user
start_url = input("\nEnter URL to crawl (must be in the form
[Link] ").strip()
# Validate URL
if not start_url.startswith(('[Link] '[Link]
print("Error: URL must start with http:// or [Link]
return
# Create and run crawler
crawler = WebCrawler(start_url, max_pages=500)
[Link]()
if __name__ == "__main__":
main()