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
from urllib.request import urlopen
from html.parser import HTMLParser
from urllib.parse import urljoin


class LinkParser(HTMLParser):
    def __init__(self):
        super().__init__()
        self.links = []

    def handle_starttag(self, tag, attrs):
        if tag == "a":
            for key, value in attrs:
                if key == "href" and value:
                    self.links.append(value)


url = "https://example.com"

html = urlopen(
    url,
    timeout=5
).read().decode("utf-8", errors="ignore")

parser = LinkParser()
parser.feed(html)

for link in parser.links:
    print(urljoin(url, link))

1
2
3
4
5
6
7
8
9
10
text = "Search engines process queries."

tokens = (
    text
    .lower()
    .replace(".", "")
    .split()
)

print(tokens)

1
2
3
4
5
6
7
8
9
10
11
12
13
from nltk.stem import PorterStemmer

stemmer = PorterStemmer()

words = [
    "computer",
    "computers",
    "computing",
    "compute"
]

for word in words:
    print(word, "->", stemmer.stem(word))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
documents = {
    "D1": "search engine",
    "D2": "information retrieval",
    "D3": "search information"
}

index = {}

for doc_id, text in documents.items():

    terms = text.lower().split()

    for term in terms:
        index.setdefault(term, set()).add(doc_id)


for term, doc_ids in sorted(index.items()):
    print(term, "->", sorted(doc_ids))

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
documents = {
    "D1": "search engine architecture",
    "D2": "information retrieval system",
    "D3": "search engine information retrieval"
}

query = "search engine"

terms = query.lower().split()

results = []

for doc_id, text in documents.items():

    words = text.lower().split()

    score = sum(
        words.count(term)
        for term in terms
    )

    results.append((doc_id, score))


results.sort(
    key=lambda item: item[1],
    reverse=True
)

for doc_id, score in results:
    print(doc_id, "score =", score)

1
2
3
4
5
6
7
8
graph = {
    "A": ["B", "C"],
    "B": ["C"],
    "C": ["A"]
}

for page, links in graph.items():
    print(page, "->", links)

1
2
3
4
5
6
documents = {
    "D1": "information retrieval",
    "D2": "search engine",
    "D3": "information search engine",
    "D4": "retrieval system"
}

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


def tokenize(text):
    """
    Convert text into normalized tokens.

    Steps:
    1. Lowercase
    2. Remove punctuation
    3. Split into words
    """

    text = text.lower()

    # Keep only letters and numbers
    text = re.sub(r"[^a-z0-9\s]", " ", text)

    tokens = text.split()

    return tokens

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
45
46
47
48
49
50
51
import os
from collections import defaultdict

from tokenizer import tokenize


class Indexer:

    def __init__(self):
        # term -> set(document)
        self.inverted_index = defaultdict(set)

        # document -> tokens
        self.documents = {}

    def index_documents(self, documents_path):
        """
        Read all .txt files and build inverted index.
        """

        for filename in os.listdir(documents_path):

            if not filename.endswith(".txt"):
                continue

            filepath = os.path.join(documents_path, filename)

            with open(filepath, "r", encoding="utf-8") as file:
                text = file.read()

            tokens = tokenize(text)

            self.documents[filename] = tokens

            for token in set(tokens):
                self.inverted_index[token].add(filename)

    def get_candidates(self, query_tokens):
        """
        Find documents containing at least
        one query term.
        """

        candidates = set()

        for token in query_tokens:
            candidates.update(
                self.inverted_index.get(token, set())
            )

        return candidates

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


class SearchEngine:

    def __init__(self, indexer, ranker):
        self.indexer = indexer
        self.ranker = ranker

    def search(self, query):

        query_tokens = tokenize(query)

        # Find candidate documents
        candidates = self.indexer.get_candidates(query_tokens)

        # Rank candidates
        results = self.ranker.rank(
            query_tokens,
            candidates,
            self.indexer.documents
        )

        return results

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def precision_at_k(results, relevant_documents, k=5):
    """
    Calculate Precision@K.

    results:
        [('doc1.txt', 0.8), ('doc2.txt', 0.4)]

    relevant_documents:
        {'doc1.txt', 'doc3.txt'}
    """

    top_k = results[:k]

    if not top_k:
        return 0

    relevant_count = 0

    for doc, score in top_k:

        if doc in relevant_documents:
            relevant_count += 1

    return relevant_count / len(top_k)

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
from indexer import Indexer
from ranker import Ranker
from search import SearchEngine


DOCUMENTS_PATH = "documents"

def main():

    print("================================")
    print("       MINI SEARCH ENGINE")
    print("================================")

    # -----------------------------
    # 1. Build index
    # -----------------------------

    indexer = Indexer()

    indexer.index_documents(DOCUMENTS_PATH)

    print(
        f"\nIndexed {len(indexer.documents)} documents."
    )

    print(
        f"Vocabulary size: "
        f"{len(indexer.inverted_index)}"
    )

    # -----------------------------
    # 2. Create ranker
    # -----------------------------

    ranker = Ranker(
        total_documents=len(indexer.documents)
    )

    # -----------------------------
    # 3. Create search engine
    # -----------------------------

    search_engine = SearchEngine(
        indexer,
        ranker
    )

    # -----------------------------
    # 4. User interaction
    # -----------------------------

    while True:

        query = input("\nSearch (type 'exit' to quit): ")

        if query.lower() == "exit":
            break

        results = search_engine.search(query)

        print("\nResults:")

        if not results:
            print("No documents found.")
            continue

        for i, (doc, score) in enumerate(results, 1):

            print(
                f"{i}. {doc} "
                f"(score={score:.4f})"
            )


if __name__ == "__main__":
    main()