data1.csv
text,sentiment
The headphones comes in three colors and two sizes.,neutral
The service could be better but overall the laptop is fantastic.,positive
"Honestly the gym exceeded my expectations, plot was terrific.",positive
"Very satisfied, the camera has an amazing packaging.",positive
"Absolutely disappointing sound quality, would not recommend.",negative
"I really loved the movie, it was phenomenal.",positive
The service of this customer support is wonderful.,positive
"This gym is not bad at all, actually stellar.",positive
"Extremely unhappy, the laptop has a tedious design.",negative
The smartwatch is really refreshing and I would buy it again.,positive
"I really hated the airline, it was annoying.",negative
The smartwatch looks nice but the acting is terrible.,negative
"Absolutely useless service, would not recommend.",negative
"Not disappointed at all, the performance is lovely.",positive






# pip install pandas matplotlib scikit-learn
# =============================================================================
# NLP EXPERIMENT 1 : RULE-BASED SENTIMENT ANALYSIS
# AIM : Classify text as POSITIVE, NEGATIVE or NEUTRAL.
#
# THEORY
#  - Sentiment Analysis (opinion mining): NLP task that finds the emotion or
#    opinion in text (e.g. product reviews, tweets, feedback).
#  - Rule-based (lexicon-based) approach: no training needed. A DICTIONARY gives
#    each word a polarity (good = +1, bad = -1) and simple RULES adjust it:
#        * Negation    : "not good"  -> polarity flipped
#        * Intensifier : "very good" -> score amplified
#    Sum of word scores:  > 0 positive | < 0 negative | = 0 neutral.
#    Pros: simple, fast, explainable.  Cons: no sarcasm/context, limited by dictionary.
#  - Pre-processing: raw text is noisy, so we lowercase, remove URLs/punctuation,
#    expand contractions, tokenize and remove stop-words (but KEEP "not", "very").
#  - Evaluation: Accuracy = correct predictions / total predictions, plus a
#    confusion matrix.
#  - ML comparison (optional): a model LEARNS from labelled data (80% train,
#    20% test) using TF-IDF features + Logistic Regression.
#
# STEPS: 1 Data import | 2 Pre-processing | 3 Sentiment logic | 4 Accuracy | 5 Visualization
# =============================================================================
import re
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.feature_extraction.text import ENGLISH_STOP_WORDS, TfidfVectorizer
from sklearn.linear_model import LogisticRegression
from sklearn.metrics import accuracy_score, classification_report, confusion_matrix
from sklearn.model_selection import train_test_split
from sklearn.pipeline import make_pipeline

CSV_PATH, TEXT_COL, LABEL_COL = "data1.csv", "text", "sentiment"   # edit for lab dataset
LABELS = ["negative", "neutral", "positive"]

# ---------------------------- STEP 1 : DATA IMPORT ---------------------------
df = pd.read_csv(CSV_PATH).dropna(subset=[TEXT_COL])
print("Rows:", len(df), "| Columns:", list(df.columns))
print(df.head(), "\n")

# --------------------------- STEP 2 : PRE-PROCESSING -------------------------
NEGATIONS = {"not", "no", "never", "nothing", "nobody", "hardly", "without", "cannot"}
INTENSIFIERS = {"very": 1.5, "extremely": 1.8, "really": 1.4, "so": 1.3,
                "absolutely": 1.8, "highly": 1.5, "super": 1.5, "incredibly": 1.8}
STOP = ENGLISH_STOP_WORDS - NEGATIONS - set(INTENSIFIERS)   # keep rule words

def preprocess(text):
    text = str(text).lower()                                 # lowercase
    text = re.sub(r"http\S+|[@#]\w+", " ", text)             # remove URLs, @, #
    text = re.sub(r"n't", " not", text.replace("’", "'"))    # isn't -> is not
    tokens = re.findall(r"[a-z]+", text)                     # tokenize (letters only)
    return [t for t in tokens if t not in STOP]              # remove stop-words

df["tokens"] = df[TEXT_COL].apply(preprocess)
print("Example:", df[TEXT_COL][0], "->", df["tokens"][0], "\n")

# --------------------- STEP 3 : RULE-BASED SENTIMENT LOGIC -------------------
POSITIVE = set("""good great excellent amazing awesome fantastic wonderful perfect love loved best
    happy nice beautiful lovely brilliant superb outstanding impressive delicious friendly helpful
    fast smooth reliable enjoy enjoyed enjoyable pleasant recommend recommended glad satisfied
    terrific delightful flawless gorgeous fun cool easy comfortable worth""".split())
NEGATIVE = set("""bad terrible awful horrible worst hate hated poor sad angry annoying annoyed
    disappointed disappointing disappointment boring slow rude broken waste ugly useless dull
    dreadful pathetic disgusting disaster problem buggy damaged late cold mediocre frustrating
    confusing unhappy letdown regret""".split())

def sentiment_score(tokens):
    total = 0.0
    for i, w in enumerate(tokens):
        score = 1 if w in POSITIVE else -1 if w in NEGATIVE else 0   # RULE 1: dictionary
        if score == 0:
            continue
        if i > 0 and tokens[i - 1] in INTENSIFIERS:                  # RULE 2: intensifier
            score *= INTENSIFIERS[tokens[i - 1]]
        if any(t in NEGATIONS for t in tokens[max(0, i - 2):i]):     # RULE 3: negation
            score *= -0.75
        total += score
    return total

def classify(score):
    return "positive" if score > 0 else "negative" if score < 0 else "neutral"

df["score"] = df["tokens"].apply(sentiment_score)
df["predicted"] = df["score"].apply(classify)
print(df[[TEXT_COL, "score", "predicted"]].head(), "\n")

# --------------------------- STEP 4 : ACCURACY TESTING -----------------------
df["actual"] = df[LABEL_COL].astype(str).str.lower().str.strip().replace(
    {"pos": "positive", "neg": "negative", "neu": "neutral",
     "1": "positive", "4": "positive", "0": "negative", "2": "neutral"})   # edit if needed

acc = accuracy_score(df["actual"], df["predicted"])
print(f"Rule-based accuracy: {acc * 100:.2f}%\n")
print(classification_report(df["actual"], df["predicted"], labels=LABELS, zero_division=0))
cm = confusion_matrix(df["actual"], df["predicted"], labels=LABELS)

# Optional ML model: train on 80% of the data, test on unseen 20%
df["clean"] = df["tokens"].apply(" ".join)
X_tr, X_te, y_tr, y_te = train_test_split(df["clean"], df["actual"], test_size=0.2,
                                          random_state=42, stratify=df["actual"])
model = make_pipeline(TfidfVectorizer(ngram_range=(1, 2)), LogisticRegression(max_iter=1000))
model.fit(X_tr, y_tr)                                          # training
ml_acc = accuracy_score(y_te, model.predict(X_te))             # testing
rb_acc = accuracy_score(y_te, df.loc[X_te.index, "predicted"]) # rule-based, same rows
print(f"Same test set -> Rule-based: {rb_acc * 100:.2f}% | Logistic Regression: {ml_acc * 100:.2f}%\n")

# --------------------------- STEP 5 : VISUALIZATION --------------------------
fig, ax = plt.subplots(1, 3, figsize=(16, 4.5))

counts = pd.DataFrame({"Actual": df["actual"].value_counts(),
                       "Predicted": df["predicted"].value_counts()}).reindex(LABELS).fillna(0)
counts.plot(kind="bar", ax=ax[0], rot=0, title="Actual vs Predicted Sentiment")

ax[1].imshow(cm, cmap="Blues")                                  # confusion matrix
ax[1].set_xticks(range(3)); ax[1].set_xticklabels(LABELS)
ax[1].set_yticks(range(3)); ax[1].set_yticklabels(LABELS)
ax[1].set_xlabel("Predicted"); ax[1].set_ylabel("Actual")
ax[1].set_title(f"Confusion Matrix ({acc * 100:.1f}%)")
for i in range(3):
    for j in range(3):
        ax[1].text(j, i, cm[i, j], ha="center", va="center")

ax[2].bar(["Rule-based", "Logistic Reg."], [rb_acc * 100, ml_acc * 100], color=["#e67e22", "#3498db"])
ax[2].set_ylim(0, 110); ax[2].set_title("Accuracy Comparison (%)")

plt.tight_layout()
plt.show()




# pip install pandas matplotlib scikit-learn nltk
# =============================================================================
# NLP EXPERIMENT 2 : TEXT PRE-PROCESSING USING NLTK
# AIM : Implement tokenization, filtering, stop-word removal, stemming and
#       lemmatization on a text dataset using Python and the NLTK library.
#
# THEORY
#  - Text Pre-processing: cleaning raw text and converting it into a standard
#    form that a computer can analyse. Raw text is noisy (punctuation, upper/
#    lower case, URLs, filler words, word variations). It matters because
#    cleaner input -> smaller vocabulary, less noise, faster processing and
#    usually better accuracy in NLP tasks (sentiment analysis, search, chatbots).
#
#  - Tokenization: splitting text into small units (tokens) - words or sentences.
#      "I love NLP!"  ->  ['I', 'love', 'NLP', '!']
#
#  - Filtering: removing tokens that carry no useful meaning - punctuation,
#    numbers, URLs, special characters, very short tokens - and lower-casing.
#      ['I', 'love', 'NLP', '!']  ->  ['i', 'love', 'nlp']
#
#  - Stop-word Removal: dropping very common words (the, is, on, and) that add
#    little meaning.   "the cat is on the mat"  ->  ['cat', 'mat']
#    (We keep "not"/"no" because they change the sentiment of a sentence.)
#
#  - Stemming: chopping word endings with fixed rules to get a root (stem).
#    Fast, but the stem may not be a real word.
#      running -> run | studies -> studi | studying -> studi
#
#  - Lemmatization: converting a word to its dictionary form (lemma) using
#    vocabulary and grammar. Slower but always gives a real word.
#      studies -> study | wolves -> wolf | running (verb) -> run | better (adj) -> good
#
# STEPS: 1 Data import | 2 Pre-processing pipeline | 3 Example output
#        4 Accuracy testing | 5 Visualization
# =============================================================================
import pandas as pd
import matplotlib.pyplot as plt
import nltk
from collections import Counter
from nltk.tokenize import word_tokenize
from nltk.corpus import stopwords
from nltk.stem import PorterStemmer, WordNetLemmatizer
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.linear_model import LogisticRegression
from sklearn.metrics import accuracy_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import make_pipeline

for pkg in ["punkt", "punkt_tab", "stopwords", "wordnet", "omw-1.4"]:   # NLTK data (one time)
    nltk.download(pkg, quiet=True)

CSV_PATH, TEXT_COL, LABEL_COL = "data1.csv", "text", "sentiment"      # edit for lab dataset

# ---------------------------- STEP 1 : DATA IMPORT ---------------------------
df = pd.read_csv(CSV_PATH).dropna(subset=[TEXT_COL])
print("Rows:", len(df), "| Columns:", list(df.columns))
print(df.head(), "\n")

# ----------------------- STEP 2 : PRE-PROCESSING PIPELINE --------------------
stop_words = set(stopwords.words("english")) - {"not", "no", "nor"}   # keep negations
stemmer = PorterStemmer()
lemmatizer = WordNetLemmatizer()

def tokenize(text):                      # 1. Tokenization (+ expand n't -> not)
    text = str(text).replace("won't", "will not").replace("can't", "can not").replace("n't", " not")
    return word_tokenize(text)

def filter_tokens(tokens):               # 2. Filtering: lower-case, keep alphabetic words only
    return [t.lower() for t in tokens if t.isalpha() and len(t) > 1]

def remove_stopwords(tokens):            # 3. Stop-word removal
    return [t for t in tokens if t not in stop_words]

def stem(tokens):                        # 4. Stemming
    return [stemmer.stem(t) for t in tokens]

def lemmatize(tokens):                   # 5. Lemmatization (as noun first, then as verb)
    return [lemmatizer.lemmatize(lemmatizer.lemmatize(t), pos="v") for t in tokens]

df["tokens"] = df[TEXT_COL].apply(tokenize)
df["filtered"] = df["tokens"].apply(filter_tokens)
df["no_stop"] = df["filtered"].apply(remove_stopwords)
df["stemmed"] = df["no_stop"].apply(stem)
df["lemmatized"] = df["no_stop"].apply(lemmatize)

# ---------------------------- STEP 3 : EXAMPLE OUTPUT ------------------------
row = df.iloc[1]
print("Original      :", row[TEXT_COL])
print("Tokenization  :", row["tokens"])
print("Filtering     :", row["filtered"])
print("Stop-words out:", row["no_stop"])
print("Stemming      :", row["stemmed"])
print("Lemmatization :", row["lemmatized"], "\n")

print("Stemming vs Lemmatization:")
print(pd.DataFrame({"word": row["no_stop"], "stem": row["stemmed"], "lemma": row["lemmatized"]}), "\n")

# --------------------------- STEP 4 : ACCURACY TESTING -----------------------
# Train the same classifier on text from each stage and compare accuracy.
stages = {"Raw text": df[TEXT_COL].astype(str),
          "Tokenized + Filtered": df["filtered"].apply(" ".join),
          "Stop-words removed": df["no_stop"].apply(" ".join),
          "Stemmed": df["stemmed"].apply(" ".join),
          "Lemmatized": df["lemmatized"].apply(" ".join)}

def evaluate(texts):
    X_tr, X_te, y_tr, y_te = train_test_split(texts, df[LABEL_COL], test_size=0.2,
                                              random_state=42, stratify=df[LABEL_COL])
    model = make_pipeline(TfidfVectorizer(lowercase=False), LogisticRegression(max_iter=1000))
    model.fit(X_tr, y_tr)
    return accuracy_score(y_te, model.predict(X_te))

accuracy = {name: evaluate(texts) for name, texts in stages.items()}
vocab = {name: len({w for t in texts for w in t.split()}) for name, texts in stages.items()}

print(f"{'Stage':<22}{'Vocabulary':>12}{'Accuracy':>12}")
for name in stages:
    print(f"{name:<22}{vocab[name]:>12}{accuracy[name] * 100:>11.2f}%")

# --------------------------- STEP 5 : VISUALIZATION --------------------------
fig, ax = plt.subplots(1, 3, figsize=(17, 4.5))
names = list(stages)

ax[0].bar(names, list(vocab.values()), color="#3498db")
ax[0].set_title("Vocabulary Size After Each Step")

ax[1].bar(names, [a * 100 for a in accuracy.values()], color="#2ecc71")
ax[1].set_ylim(0, 110)
ax[1].set_title("Classifier Accuracy (%) After Each Step")

top = Counter(w for t in df["lemmatized"] for w in t).most_common(10)
ax[2].barh([w for w, _ in top][::-1], [c for _, c in top][::-1], color="#e67e22")
ax[2].set_title("Top 10 Words (after lemmatization)")

for a in ax[:2]:
    a.tick_params(axis="x", rotation=25)
plt.tight_layout()
plt.show()




# pip install pandas matplotlib scikit-learn
# =============================================================================
# NLP EXPERIMENT 3 : SMOOTHING TECHNIQUES ON N-GRAMS
#                    (Laplace, Lidstone and Good-Turing)
# AIM : Implement smoothing techniques on an n-gram language model and compare
#       them using perplexity.
#
# THEORY
#  1) What is an N-gram?
#     A contiguous sequence of n words from a text.
#        n=1 unigram, n=2 bigram, n=3 trigram.
#        "I love NLP"  ->  bigrams: (I, love), (love, NLP)
#     An N-gram LANGUAGE MODEL predicts a word from the previous n-1 words
#     (Markov assumption). For a bigram model (maximum likelihood estimate):
#           P(w_i | w_i-1) = C(w_i-1, w_i) / C(w_i-1)
#     C(...) = how many times the word / word pair occurs in the training data.
#
#  2) Why are N-grams used?
#     Simple, fast, need no labelled data, and capture local word order
#     ("New York" vs "York New"). They are the base of language modelling.
#
#  3) Applications in NLP
#     Next-word prediction / auto-complete, speech recognition, machine
#     translation, spelling correction, text generation, OCR, plagiarism
#     detection, and features for text classification.
#
#  4) Major problem : Data Sparsity / Zero Probability
#     No training corpus contains every possible word sequence. A bigram that
#     never appeared in training gets C = 0 -> P = 0. Since a sentence's
#     probability is the PRODUCT of its bigram probabilities, ONE unseen
#     bigram makes the whole sentence probability 0 (perplexity = infinity).
#     So n-grams perform very badly on unseen word sequences.
#
#  5) Smoothing : take a little probability from seen n-grams and give it to
#     unseen ones, so that nothing has zero probability.
#     (V = vocabulary size, C(h) = count of the previous word / history)
#
#     a) LAPLACE (Add-One) smoothing - add 1 to every bigram count:
#           P(w | h) = ( C(h, w) + 1 ) / ( C(h) + V )
#        Useful because it is the simplest fix and guarantees P > 0.
#        Drawback: with a big vocabulary it gives TOO MUCH mass to unseen pairs.
#
#     b) LIDSTONE (Add-k) smoothing - add a small k (0 < k <= 1) instead of 1:
#           P(w | h) = ( C(h, w) + k ) / ( C(h) + k * V )
#        k = 1 is exactly Laplace. A smaller k (e.g. 0.1) is gentler on seen
#        data. k is tuned on a development (validation) set.
#
#     c) GOOD-TURING smoothing - estimate unseen events from events seen once.
#        N_c = number of distinct bigrams that occur exactly c times.
#           adjusted count  c* = (c + 1) * N_(c+1) / N_c
#           P(w | h) = c* / C(h)                      for seen bigrams
#           total probability of ALL unseen bigrams ~ N_1 / N  (N = total bigrams)
#        (For large c, N_(c+1) is often 0, so we keep c* = c when c > 5.)
#
#  6) Applications of smoothing
#     Speech recognition, machine translation, spell checkers and predictive
#     keyboards all need sensible probabilities for word pairs not seen in
#     training. Good-Turing is the idea behind Katz back-off; modern models
#     use Kneser-Ney smoothing.
#
#  7) Evaluation : PERPLEXITY (accuracy measure of a language model)
#        PPL = exp( -(1/N) * sum( log P(w_i | w_i-1) ) )      lower = better
#
# STEPS: 1 Data import | 2 Pre-processing | 3 Main logic (models) |
#        4 Accuracy testing (perplexity) | 5 Visualization
# =============================================================================
import re, math
from collections import Counter, defaultdict
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split

CSV_PATH, TEXT_COL = "data1.csv", "text"          # edit for lab dataset

# ---------------------------- STEP 1 : DATA IMPORT ---------------------------
df = pd.read_csv(CSV_PATH).dropna(subset=[TEXT_COL])
print("Rows:", len(df), "| Columns:", list(df.columns))
print(df.head(), "\n")

# --------------------------- STEP 2 : PRE-PROCESSING -------------------------
def tokenize(text):                                    # lowercase + words only
    return re.findall(r"[a-z]+", str(text).lower().replace("n't", " not"))

sentences = [tokenize(t) for t in df[TEXT_COL]]
sentences = [s for s in sentences if s]

# Split: 70% train | 15% dev (to tune k) | 15% test
train, rest = train_test_split(sentences, test_size=0.3, random_state=42)
dev, test = train_test_split(rest, test_size=0.5, random_state=42)

vocab = {w for s in train for w in s} | {"</s>", "<UNK>"}     # words the model can predict
V = len(vocab)

def add_markers(sents):          # unseen words -> <UNK>, add start/end markers
    return [["<s>"] + [w if w in vocab else "<UNK>" for w in s] + ["</s>"] for s in sents]

train, dev, test = add_markers(train), add_markers(dev), add_markers(test)
print("Example:", train[0])
print(f"Train: {len(train)} | Dev: {len(dev)} | Test: {len(test)} sentences | Vocabulary V = {V}\n")

# ----------------------- STEP 3 : MAIN LOGIC (BIGRAM MODELS) -----------------
bigrams = Counter((s[i], s[i + 1]) for s in train for i in range(len(s) - 1))   # C(h, w)
history = Counter()                                                              # C(h)
seen_after = defaultdict(int)                      # number of different words seen after h
for (h, w), c in bigrams.items():
    history[h] += c
    seen_after[h] += 1

N = sum(bigrams.values())                          # total bigrams
Nc = Counter(bigrams.values())                     # N_c : bigrams occurring exactly c times
print("Frequency of frequencies:", {c: Nc[c] for c in range(1, 6)})
print(f"Good-Turing: probability of ALL unseen bigrams ~ N1/N = {Nc[1] / N:.4f}\n")

def p_mle(h, w):                                   # no smoothing
    return bigrams[(h, w)] / history[h] if history[h] else 0.0

def p_lidstone(h, w, k):                           # add-k   (Laplace when k = 1)
    return (bigrams[(h, w)] + k) / (history[h] + k * V)

def p_laplace(h, w):                               # add-one
    return p_lidstone(h, w, 1)

def adjusted(c, limit=5):                          # Good-Turing adjusted count c*
    return (c + 1) * Nc[c + 1] / Nc[c] if c <= limit and Nc[c + 1] > 0 else c

# probability mass Good-Turing keeps for unseen words after each history h
leftover = defaultdict(float)
for (h, w), c in bigrams.items():
    leftover[h] += adjusted(c) / history[h]
leftover = {h: max(1 - m, 1e-4) for h, m in leftover.items()}

def p_good_turing(h, w):
    if not history[h]:
        return 1 / V
    c = bigrams[(h, w)]
    if c > 0:
        return adjusted(c) / history[h]                           # seen: c* / C(h)
    return leftover[h] / max(V - seen_after[h], 1)                # unseen: share leftover mass

# Tune k for Lidstone on the DEV set
def perplexity(sents, prob):
    log_sum, n = 0.0, 0
    for s in sents:
        for h, w in zip(s, s[1:]):
            p = prob(h, w)
            if p == 0:
                return float("inf")                # zero probability -> infinite perplexity
            log_sum += math.log(p)
            n += 1
    return math.exp(-log_sum / n)

ks = [0.001, 0.005, 0.01, 0.05, 0.1, 0.3, 0.5, 1]
dev_ppl = [perplexity(dev, lambda h, w, k=k: p_lidstone(h, w, k)) for k in ks]
best_k = ks[dev_ppl.index(min(dev_ppl))]
print(f"Best k for Lidstone on dev set: {best_k}\n")

# Demo: one bigram from the test set that was NEVER seen in training
h, w = next((h, w) for s in test for h, w in zip(s, s[1:]) if bigrams[(h, w)] == 0 and history[h])
print(f"Unseen bigram ('{h}', '{w}') probability:")
print(f"  No smoothing : {p_mle(h, w):.6f}\n  Laplace      : {p_laplace(h, w):.6f}")
print(f"  Lidstone     : {p_lidstone(h, w, best_k):.6f}\n  Good-Turing  : {p_good_turing(h, w):.6f}\n")

# --------------------------- STEP 4 : ACCURACY TESTING -----------------------
models = {"No smoothing": p_mle, "Laplace (k=1)": p_laplace,
          f"Lidstone (k={best_k})": lambda h, w: p_lidstone(h, w, best_k),
          "Good-Turing": p_good_turing}

test_pairs = [(a, b) for s in test for a, b in zip(s, s[1:])]
unseen = sum(bigrams[p] == 0 for p in test_pairs)
print(f"Test bigrams: {len(test_pairs)} | Unseen in training: {unseen} ({unseen / len(test_pairs) * 100:.1f}%)\n")

test_ppl = {name: perplexity(test, prob) for name, prob in models.items()}
print(f"{'Model':<22}{'Test Perplexity':>16}")
for name, ppl in test_ppl.items():
    print(f"{name:<22}{ppl:>16.2f}")

# --------------------------- STEP 5 : VISUALIZATION --------------------------
fig, ax = plt.subplots(1, 3, figsize=(17, 4.8))

names = [n for n, p in test_ppl.items() if p != float("inf")]       # inf cannot be drawn
ax[0].bar(names, [test_ppl[n] for n in names], color=["#3498db", "#2ecc71", "#e67e22"])
ax[0].set_title("Test Perplexity (lower = better)\nNo smoothing = infinity")
ax[0].tick_params(axis="x", rotation=15)

ax[1].plot(ks, dev_ppl, marker="o")
ax[1].set_xscale("log")
ax[1].set_xlabel("k (Lidstone)"); ax[1].set_ylabel("Dev perplexity")
ax[1].set_title("Effect of k  (k = 1 is Laplace)")

common = history.most_common(1)[0][0]                                # most frequent history word
mass = {n: sum(p(common, x) for x in vocab if bigrams[(common, x)] == 0) for n, p in models.items()}
ax[2].bar(list(mass), list(mass.values()), color=["#95a5a6", "#2ecc71", "#e67e22", "#9b59b6"])
ax[2].set_title(f"Probability given to UNSEEN words after '{common}'")
ax[2].tick_params(axis="x", rotation=15)

plt.tight_layout()
plt.show()



# pip install pandas matplotlib nltk
# =============================================================================
# NLP EXPERIMENT 4 : TOP-DOWN, BOTTOM-UP AND CYK PARSING USING CFG
# AIM : Understand and apply different parsing techniques for syntactic
#       analysis using a Context-Free Grammar (CFG).
#
# THEORY
#  1) What is Parsing?
#     Parsing (syntactic analysis) is the process of analysing a sentence and
#     finding out whether it can be generated by a given grammar and, if so,
#     what its grammatical structure (parse tree) is.
#        "the service is good"  ->  (S (NP the service) (VP is (ADJP good)))
#     Applications: grammar checking, machine translation, question answering,
#     information extraction, chatbots, speech understanding.
#
#  2) What is a Context-Free Grammar (CFG)?
#     A CFG is a set of rewrite rules G = (N, T, P, S):
#        N = non-terminals (phrase types: S, NP, VP ...)
#        T = terminals     (the actual symbols: words or word categories)
#        P = production rules   A -> B C     ("A can be rewritten as B C")
#        S = start symbol (S = sentence)
#     "Context-free" = the left side is always ONE non-terminal, so a rule can
#     be applied wherever that non-terminal appears, whatever surrounds it.
#        S  -> NP VP        NP -> DET NOUN        VP -> VERB NP
#
#  3) TOP-DOWN parsing (goal-driven, e.g. recursive descent)
#     Start from the start symbol S and keep applying rules to EXPAND it,
#     trying to match the input words from left to right. If a choice fails,
#     BACKTRACK and try another rule.
#     + Never builds structures that cannot lead to S.
#     - Wastes time on rules that do not match the input; goes into an
#       infinite loop on LEFT-RECURSIVE rules (NP -> NP PP).
#
#  4) BOTTOM-UP parsing (data-driven, e.g. shift-reduce / bottom-up chart)
#     Start from the input words, assign them categories, and REDUCE any group
#     of symbols that matches the right side of a rule to its left side
#     (DET NOUN -> NP), repeating until only S is left.
#     + Always consistent with the actual input words.
#     - Builds many small structures that never become part of a sentence.
#
#  5) Chomsky Normal Form (CNF)
#     A CFG is in CNF if EVERY rule has one of only two shapes:
#        A -> B C      (exactly two non-terminals)
#        A -> a        (exactly one terminal)
#     Any CFG can be converted to CNF:
#        (i)   remove unit rules   A -> B
#        (ii)  replace terminals inside longer rules by new non-terminals
#        (iii) break long rules:   A -> B C D   becomes   A -> B X , X -> C D
#
#  6) CYK (Cocke-Younger-Kasami) parsing
#     A BOTTOM-UP DYNAMIC-PROGRAMMING algorithm that REQUIRES the grammar in CNF.
#     It fills a triangular table where cell [i, j] stores every non-terminal
#     that can generate the words from position i to j:
#        - length 1 : look up the word's rule      A -> a
#        - length>1 : split span at k; if B is in [i,k] and C is in [k+1,j]
#                     and a rule A -> B C exists, put A in [i,j]
#     The sentence is accepted if S is in the top cell [0, n-1].
#     Time complexity O(n^3 * |G|) - it never backtracks and handles ambiguity.
#
#  HOW THIS CODE WORKS: each review is POS-tagged (NLTK universal tagset:
#  NOUN, VERB, ADJ, ADV, DET ...) and the CFG is written over these word
#  categories, so one small grammar can parse many different sentences.
#
# STEPS: 1 Data import | 2 Pre-processing | 3 Main logic (3 parsers)
#        4 Accuracy testing | 5 Visualization
# =============================================================================
import time
import nltk
import pandas as pd
import matplotlib.pyplot as plt
from nltk.tokenize import word_tokenize

for pkg in ["punkt", "punkt_tab", "averaged_perceptron_tagger",
            "averaged_perceptron_tagger_eng", "universal_tagset"]:      # one-time downloads
    nltk.download(pkg, quiet=True)

CSV_PATH, TEXT_COL = "data1.csv", "text"        # edit for lab dataset
SAMPLE_SIZE = 200                              # number of sentences to parse (keeps it fast)
MAX_LEN = 12                                   # top-down backtracking is exponential, so skip very long sentences

# ---------------------------- STEP 1 : DATA IMPORT ---------------------------
df = pd.read_csv(CSV_PATH).dropna(subset=[TEXT_COL]).head(SAMPLE_SIZE).reset_index(drop=True)
print("Sentences to parse:", len(df))
print(df.head(), "\n")

# --------------------------- STEP 2 : PRE-PROCESSING -------------------------
def to_tags(text):
    text = str(text).replace("won't", "will not").replace("can't", "can not").replace("n't", " not")
    words = [w for w in word_tokenize(text) if w.isalpha()]               # tokenize + filter
    return [tag for _, tag in nltk.pos_tag(words, tagset="universal")]    # word categories

df["tags"] = df[TEXT_COL].apply(to_tags)
df["length"] = df["tags"].apply(len)
df = df[df["length"].between(1, MAX_LEN)].reset_index(drop=True)   # keep sentences of 1..MAX_LEN words
print("Example:", df[TEXT_COL][1], "->", df["tags"][1], "\n")

# ------------------------------ STEP 3 : MAIN LOGIC --------------------------
# CFG over word categories. Lines like  Noun -> 'NOUN'  link a category to the
# POS tag found in the data (quoted = terminal). No left recursion, so that the
# top-down parser can run on it.
grammar = nltk.CFG.fromstring("""
S    -> CL | CL Conj S | CL S
CL   -> NP VP | VP | NP | Adv CL | Adj CL
NP   -> Det NOM | NOM | Pron | Num NOM | Det NOM PP | NOM PP | Pron NP
NOM  -> Noun | Noun NOM | Adj NOM
VP   -> Verb | Verb NP | Verb ADJP | Verb PP | Verb Adv | Verb NP PP
VP   -> Verb VP | Prt VP | Adv VP | Verb Prt VP | Verb NP Adv
ADJP -> Adj | Adv ADJP | Adj Conj ADJP | Adj PP
PP   -> Adp NP
Det  -> 'DET'
Noun -> 'NOUN'
Verb -> 'VERB'
Adj  -> 'ADJ'
Adv  -> 'ADV'
Pron -> 'PRON'
Num  -> 'NUM'
Conj -> 'CONJ'
Prt  -> 'PRT'
Adp  -> 'ADP'
""")

# --- Parser 1 : TOP-DOWN (recursive descent) ---------------------------------
try:
    top_down = nltk.RecursiveDescentParser(grammar, max_time=60)   # newer NLTK: 60 s limit per sentence
except TypeError:
    top_down = nltk.RecursiveDescentParser(grammar)                # older NLTK has no time limit

# --- Parser 2 : BOTTOM-UP (bottom-up chart parser) ---------------------------
bottom_up = nltk.BottomUpChartParser(grammar)

def parse_with(parser, tags):
    """Return the first parse tree, or None if the grammar cannot parse the sentence."""
    try:
        return next(parser.parse(tags), None)
    except ValueError:                      # a tag that is not in the grammar
        return None

# --- Parser 3 : CYK (needs CNF) ----------------------------------------------
cnf = grammar.chomsky_normal_form()         # convert CFG -> Chomsky Normal Form
print("Grammar in CNF:", cnf.is_chomsky_normal_form(), "| rules:", len(cnf.productions()))
for p in cnf.productions()[:5]:
    print("   ", p)
print()

lexical, binary = {}, {}                    # A -> a   and   A -> B C
for p in cnf.productions():
    if p.is_lexical():
        lexical.setdefault(p.rhs()[0], set()).add(p.lhs())
    else:
        binary.setdefault(p.rhs(), set()).add(p.lhs())

def cyk(tags):
    n = len(tags)
    table = [[set() for _ in range(n)] for _ in range(n)]       # table[i][j] = span i..j
    for i, t in enumerate(tags):                                # length 1 spans
        table[i][i] = set(lexical.get(t, ()))
    for length in range(2, n + 1):                              # longer spans
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):                               # split point
                for B in table[i][k]:
                    for C in table[k + 1][j]:
                        table[i][j] |= binary.get((B, C), set())
    return grammar.start() in table[0][n - 1], table

# Show all three parsers on one example sentence
idx = next(i for i, t in enumerate(df["tags"]) if t and cyk(t)[0])   # first parsable sentence
tags = df["tags"][idx]
print("Sentence :", df[TEXT_COL][idx])
print("Tags     :", tags)
print("\nTop-down parse tree:")
tree = parse_with(top_down, tags)
tree.pretty_print() if tree else print("  (no parse)")
print("Bottom-up parse tree:")
tree = parse_with(bottom_up, tags)
tree.pretty_print() if tree else print("  (no parse)")
ok, table = cyk(tags)
print("CYK accepts the sentence:", ok)
print("CYK table, top cell [0, n-1] =", sorted(map(str, table[0][len(tags) - 1])), "\n")

# --------------------------- STEP 4 : ACCURACY TESTING -----------------------
# "Accuracy" of a parser = % of sentences the grammar can parse (coverage).
# All 3 parsers use the SAME grammar, so they must AGREE on every sentence.
results = {"Top-Down": [], "Bottom-Up": [], "CYK": []}
times = {k: 0.0 for k in results}

for tags in df["tags"]:
    if not tags:                                              # empty sentence
        for k in results: results[k].append(False)
        continue
    for name, fn in [("Top-Down", lambda t: parse_with(top_down, t) is not None),
                     ("Bottom-Up", lambda t: parse_with(bottom_up, t) is not None),
                     ("CYK", lambda t: cyk(t)[0])]:
        start = time.time()
        results[name].append(fn(tags))
        times[name] += time.time() - start

n = len(df)
agree = sum(results["Top-Down"][i] == results["Bottom-Up"][i] == results["CYK"][i] for i in range(n))
print(f"{'Parser':<12}{'Parsed':>8}{'Coverage':>11}{'Time (s)':>11}")
for name in results:
    parsed = sum(results[name])
    print(f"{name:<12}{parsed:>8}{parsed / n * 100:>10.1f}%{times[name]:>11.3f}")
print(f"\nAll three parsers agree on {agree}/{n} sentences ({agree / n * 100:.1f}%)")

# --------------------------- STEP 5 : VISUALIZATION --------------------------
fig, ax = plt.subplots(1, 3, figsize=(16, 4.5))
names = list(results)

parsed_pct = [sum(results[k]) / n * 100 for k in names]
ax[0].bar(names, parsed_pct, color=["#3498db", "#2ecc71", "#e67e22"])
ax[0].set_ylim(0, 100); ax[0].set_ylabel("% sentences parsed")
ax[0].set_title("Parsing Accuracy (Grammar Coverage)")

ax[1].bar(names, [times[k] for k in names], color=["#3498db", "#2ecc71", "#e67e22"])
ax[1].set_ylabel("Total time (seconds)")
ax[1].set_title("Parsing Time")

df["parsed"] = results["CYK"]
bins = range(0, int(df["length"].max()) + 2, 2)
ax[2].hist([df[df["parsed"]]["length"], df[~df["parsed"]]["length"]], bins=bins,
           label=["Parsed", "Not parsed"], color=["#2ecc71", "#e74c3c"])
ax[2].set_xlabel("Sentence length (words)"); ax[2].set_ylabel("Sentences")
ax[2].set_title("Parsed vs Not Parsed by Length"); ax[2].legend()

plt.tight_layout()
plt.show()





# pip install pandas matplotlib scikit-learn nltk
# =============================================================================
# NLP EXPERIMENT 5 : N-GRAM MODELS (UNIGRAM TO HIGHER ORDER) AND HIDDEN MARKOV MODEL
# AIM : Implement unigram, bigram, trigram and higher-order n-gram models,
#       analyse how increasing n affects performance and context, and study
#       the Hidden Markov Model (HMM).
#
# THEORY - N-GRAM MODELS
#  An n-gram is a sequence of n consecutive words. A language model gives the
#  probability of a sentence. By the CHAIN RULE:
#     P(w1 w2 ... wm) = P(w1) * P(w2|w1) * P(w3|w1 w2) * ... * P(wm|w1..wm-1)
#  The history grows without limit, so n-gram models use the MARKOV ASSUMPTION:
#  a word depends only on the previous n-1 words.
#
#  Unigram (n=1, no context):
#     P(w_i) = C(w_i) / N                              N = total words
#     P(sentence) = P(w1) * P(w2) * ... * P(wm)
#  Bigram (n=2, 1 previous word):
#     P(w_i | w_i-1) = C(w_i-1 w_i) / C(w_i-1)
#     P(sentence) = P(w1|<s>) * P(w2|w1) * ... * P(</s>|wm)
#  Trigram (n=3, 2 previous words):
#     P(w_i | w_i-2 w_i-1) = C(w_i-2 w_i-1 w_i) / C(w_i-2 w_i-1)
#  General n-gram (n-1 previous words):
#     P(w_i | w_i-n+1 ... w_i-1) = C(w_i-n+1 ... w_i) / C(w_i-n+1 ... w_i-1)
#     (<s> = sentence start, </s> = sentence end; C(...) = count in training data)
#
#  MAXIMUM LIKELIHOOD ESTIMATION (MLE)
#     MLE chooses the probabilities that make the TRAINING data as likely as
#     possible. For n-grams the answer is simply the RELATIVE FREQUENCY:
#     "how often does this word follow this history, out of all times the
#     history appeared".
#        Bigram  : if "the" occurs 1000 times and "the cat" occurs 50 times,
#                  P(cat | the) = 50 / 1000 = 0.05
#        Trigram : if "the cat" occurs 40 times and "the cat sat" 10 times,
#                  P(sat | the cat) = 10 / 40 = 0.25
#     Drawback: an n-gram never seen in training gets probability 0 (use
#     smoothing - Experiment 3).
#
#  EFFECT OF INCREASING n
#     + More context -> better predictions, lower perplexity, more fluent text.
#     - Number of possible n-grams grows like V^n, so most higher-order n-grams
#       are never seen (DATA SPARSITY), the model needs more memory and more
#       data, and it overfits. So accuracy improves for a while, then drops.
#
# THEORY - HIDDEN MARKOV MODEL (HMM)
#  An HMM models a sequence where the real states are HIDDEN and we only see
#  observations produced by them. Example (POS tagging): hidden states = tags
#  (NOUN, VERB...), observations = the words we actually see.
#  Two assumptions: (1) Markov: a state depends only on the previous state,
#  (2) output independence: a word depends only on its own state.
#  Variables of an HMM  lambda = (A, B, pi):
#     S  = {s1..sN}  set of N hidden states            (tags)
#     V  = {v1..vM}  set of M observation symbols      (words)
#     O  = o1..oT    observation sequence              (the sentence)
#     Q  = q1..qT    hidden state sequence             (tags to be found)
#     pi : initial probabilities   pi_i = P(q1 = s_i)
#     A  : transition matrix       a_ij = P(q_t+1 = s_j | q_t = s_i)
#     B  : emission matrix         b_j(o_t) = P(o_t | q_t = s_j)
#  Joint probability: P(O, Q) = pi(q1) b(q1,o1) * PRODUCT a(q_t-1,q_t) b(q_t,o_t)
#  Three classic problems:
#     Evaluation : P(O | lambda)?               -> Forward algorithm
#     Decoding   : best hidden sequence Q?      -> Viterbi algorithm (used below)
#     Learning   : estimate A, B, pi            -> counting (supervised) / Baum-Welch
#  A bigram model is a Markov chain with VISIBLE states; an HMM adds hidden ones.
#  Applications: POS tagging, speech recognition, named-entity recognition.
#
# STEPS: 1 Data import | 2 Pre-processing | 3 Main logic (n-gram + HMM)
#        4 Accuracy testing | 5 Visualization
# =============================================================================
import re, math, random
from collections import Counter, defaultdict
import nltk
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split

for pkg in ["averaged_perceptron_tagger", "averaged_perceptron_tagger_eng", "universal_tagset"]:
    nltk.download(pkg, quiet=True)                       # one-time download (POS tagger)

CSV_PATH, TEXT_COL = "data1.csv", "text"                  # edit for lab dataset
ORDERS = [1, 2, 3, 4, 5]                                 # n-gram orders to compare
K = 0.01                                                 # add-k smoothing used for perplexity
random.seed(1)

# ---------------------------- STEP 1 : DATA IMPORT ---------------------------
df = pd.read_csv(CSV_PATH).dropna(subset=[TEXT_COL])
print("Rows:", len(df), "| Columns:", list(df.columns))
print(df.head(), "\n")

# --------------------------- STEP 2 : PRE-PROCESSING -------------------------
def preprocess(text):
    """Return (lower-case words, POS tags) for one sentence."""
    raw = re.findall(r"[A-Za-z]+", str(text).replace("n't", " not"))     # tokenize, words only
    tags = [t for _, t in nltk.pos_tag(raw, tagset="universal")]          # tags = HMM hidden states
    return [w.lower() for w in raw], tags

data = [preprocess(t) for t in df[TEXT_COL]]
data = [d for d in data if d[0]]
train, test = train_test_split(data, test_size=0.2, random_state=42)      # 80% train, 20% test

vocab = {w for words, _ in train for w in words} | {"</s>", "<UNK>"}
V = len(vocab)

def pad(words, n):                       # add n-1 start markers + end marker, unseen words -> <UNK>
    return ["<s>"] * (n - 1) + [w if w in vocab else "<UNK>" for w in words] + ["</s>"]

print("Example:", train[0][0], "\n         ", train[0][1])
print(f"Train: {len(train)} | Test: {len(test)} sentences | Vocabulary: {V}\n")

# --------------------- STEP 3A : MAIN LOGIC - N-GRAM MODELS ------------------
def train_ngram(n):
    grams, ctxs = Counter(), Counter()          # C(history + word) and C(history)
    for words, _ in train:
        s = pad(words, n)
        for i in range(n - 1, len(s)):
            ctx = tuple(s[i - n + 1:i])
            grams[ctx + (s[i],)] += 1
            ctxs[ctx] += 1
    best = {}                                   # most likely next word for each history (MLE)
    for g, c in grams.items():
        if c > best.get(g[:-1], ("", 0))[1]:
            best[g[:-1]] = (g[-1], c)
    return grams, ctxs, best

models = {n: train_ngram(n) for n in ORDERS}

def p_mle(n, ctx, w):                           # Maximum Likelihood Estimate
    grams, ctxs, _ = models[n]
    return grams[ctx + (w,)] / ctxs[ctx] if ctxs[ctx] else 0.0

def p_smooth(n, ctx, w):                        # add-k smoothed (avoids zero probability)
    grams, ctxs, _ = models[n]
    return (grams[ctx + (w,)] + K) / (ctxs[ctx] + K * V)

print("MLE examples (most frequent n-gram in the training data):")
for n in (2, 3):
    grams, ctxs, _ = models[n]
    g, c = max(((g, c) for g, c in grams.items() if "<s>" not in g[:-1]), key=lambda x: x[1])
    print(f"  {'Bigram' if n == 2 else 'Trigram'}: P({g[-1]} | {' '.join(g[:-1])}) = "
          f"C({' '.join(g)}) / C({' '.join(g[:-1])}) = {c} / {ctxs[g[:-1]]} = {p_mle(n, g[:-1], g[-1]):.3f}")
print()

def generate(n, max_len=15):                    # sample a sentence from the MLE model
    grams = models[n][0]
    ctx, out = ("<s>",) * (n - 1), []
    for _ in range(max_len):
        options = [(g[-1], c) for g, c in grams.items() if g[:-1] == ctx]
        if not options:
            break
        w = random.choices([o[0] for o in options], [o[1] for o in options])[0]
        if w == "</s>":
            break
        out.append(w)
        ctx = (ctx + (w,))[1:]
    return " ".join(out)

print("Generated text (shows how context improves with n):")
for n in ORDERS:
    print(f"  n={n}: {generate(n)}")
print()

# ------------------------ STEP 3B : MAIN LOGIC - HMM -------------------------
# HMM for POS tagging: hidden states = tags, observations = words.
TAGS = sorted({t for _, tags in train for t in tags})                    # S : hidden states
pi, A, B = Counter(), defaultdict(Counter), defaultdict(Counter)
for words, tags in train:
    pi[tags[0]] += 1                                                     # initial state counts
    for t1, t2 in zip(tags, tags[1:]):
        A[t1][t2] += 1                                                   # transition counts
    for w, t in zip(words, tags):
        B[t][w] += 1                                                     # emission counts
A_tot = {t: sum(A[t].values()) for t in TAGS}
B_tot = {t: sum(B[t].values()) for t in TAGS}
HK, NS = 0.001, len(TAGS)                                                # small smoothing

def log_pi(t):    return math.log((pi[t] + HK) / (len(train) + HK * NS))
def log_a(p, t):  return math.log((A[p][t] + HK) / (A_tot[p] + HK * NS))
def log_b(t, w):  return math.log((B[t][w] + HK) / (B_tot[t] + HK * V))

def viterbi(words):
    """Decoding: find the most probable hidden tag sequence for the words."""
    best = [{t: log_pi(t) + log_b(t, words[0]) for t in TAGS}]
    back = []
    for w in words[1:]:
        scores, ptr = {}, {}
        for t in TAGS:
            prev = max(TAGS, key=lambda p: best[-1][p] + log_a(p, t))
            scores[t] = best[-1][prev] + log_a(prev, t) + log_b(t, w)
            ptr[t] = prev
        best.append(scores)
        back.append(ptr)
    path = [max(TAGS, key=lambda t: best[-1][t])]
    for ptr in reversed(back):
        path.append(ptr[path[-1]])
    return path[::-1]

print("HMM variables:")
print("  Hidden states S  :", TAGS)
print("  Observations V   :", V, "words")
print("  Initial pi       :", {t: round(pi[t] / len(train), 2) for t in TAGS})
A_df = pd.DataFrame([[A[p][t] / A_tot[p] if A_tot[p] else 0 for t in TAGS] for p in TAGS],
                    index=TAGS, columns=TAGS)
print("  Transition matrix A (row = from state, column = to state):")
print(A_df.round(2))
print("  Emission B - most likely words per state:")
for t in TAGS:
    print(f"    {t:<5}", [w for w, _ in B[t].most_common(4)])
words, true_tags = test[0]
print("\nViterbi decoding example:")
print("  Words    :", words)
print("  Predicted:", viterbi(words))
print("  Actual   :", true_tags, "\n")

# --------------------------- STEP 4 : ACCURACY TESTING -----------------------
# 4A : n-gram - perplexity, unseen n-grams and NEXT-WORD PREDICTION accuracy
fallback = models[1][2][()][0]                  # most common word, used if history never seen
rows = []
for n in ORDERS:
    grams, ctxs, best = models[n]
    log_sum = total = unseen = correct = 0
    for words, _ in test:
        s = pad(words, n)
        for i in range(n - 1, len(s)):
            ctx, w = tuple(s[i - n + 1:i]), s[i]
            total += 1
            unseen += grams[ctx + (w,)] == 0
            log_sum += math.log(p_smooth(n, ctx, w))
            correct += best.get(ctx, (fallback,))[0] == w
    rows.append({"n": n, "Distinct n-grams": len(grams),
                 "Unseen test n-grams %": round(unseen / total * 100, 1),
                 "Next-word accuracy %": round(correct / total * 100, 1),
                 "Perplexity": round(math.exp(-log_sum / total), 2)})
results = pd.DataFrame(rows).set_index("n")
print("N-gram results (test set):")
print(results, "\n")

# 4B : HMM - tagging accuracy of Viterbi on the test set
hits = tokens = 0
for words, tags in test:
    pred = viterbi(words)
    hits += sum(p == t for p, t in zip(pred, tags))
    tokens += len(tags)
hmm_acc = hits / tokens * 100
print(f"HMM (Viterbi) tagging accuracy: {hmm_acc:.2f}%  ({hits}/{tokens} words)\n")

# --------------------------- STEP 5 : VISUALIZATION --------------------------
fig, ax = plt.subplots(1, 3, figsize=(17, 4.8))

ax[0].plot(ORDERS, results["Perplexity"], marker="o", color="#e67e22")
ax[0].set_xticks(ORDERS); ax[0].set_xlabel("n (order of n-gram)"); ax[0].set_ylabel("Perplexity")
ax[0].set_title("Perplexity vs n (lower = better)")

ax[1].plot(ORDERS, results["Next-word accuracy %"], marker="o", label="Next-word accuracy %", color="#2ecc71")
ax[1].plot(ORDERS, results["Unseen test n-grams %"], marker="s", label="Unseen n-grams %", color="#e74c3c")
ax[1].set_xticks(ORDERS); ax[1].set_xlabel("n (order of n-gram)"); ax[1].set_ylabel("%")
ax[1].set_title("Accuracy vs Data Sparsity"); ax[1].legend()

im = ax[2].imshow(A_df.values, cmap="Blues")
ax[2].set_xticks(range(NS)); ax[2].set_xticklabels(TAGS, rotation=45)
ax[2].set_yticks(range(NS)); ax[2].set_yticklabels(TAGS)
ax[2].set_xlabel("To state"); ax[2].set_ylabel("From state")
ax[2].set_title(f"HMM Transition Matrix A\n(Viterbi tagging accuracy {hmm_acc:.1f}%)")
fig.colorbar(im, ax=ax[2], fraction=0.046)

plt.tight_layout()
plt.show()






# pip install pandas matplotlib scikit-learn nltk
# =============================================================================
# NLP EXPERIMENT 6 : PART-OF-SPEECH (POS) TAGGING
# AIM : Assign a POS tag (noun, verb, adjective ...) to every word of a sentence
#       using default, rule-based, stochastic, transformation-based and HMM taggers.
#
# THEORY
#  1) What is POS tagging?
#     Tagging is the process of automatically assigning a descriptor (a POS tag)
#     to each token in a text. It can be seen as a CLASSIFICATION task: the input
#     is a token (with its context) and the output class is its tag.
#        "The service is excellent"  ->  The/DET service/NOUN is/VERB excellent/ADJ
#     Tag sets: Penn Treebank (NN, VB, JJ, RB, DT, IN ...) or the simpler
#     UNIVERSAL tagset used here (NOUN, VERB, ADJ, ADV, DET, ADP, PRON, CONJ,
#     NUM, PRT).  The same word can have different tags ("book a ticket" -> VERB,
#     "read a book" -> NOUN), so tagging must look at the context.
#
#  2) Applications
#     Parsing (Experiment 4), information extraction and named-entity recognition,
#     machine translation, question answering, text-to-speech (record: noun vs
#     verb is pronounced differently), word-sense disambiguation, sentiment
#     analysis (adjectives carry opinion), spelling and grammar checking.
#
#  3) Converting a sentence into words and a LIST OF TUPLES
#     raw text      : "The service is excellent."
#     tokens (list) : ['The', 'service', 'is', 'excellent', '.']
#     tagged tokens : [('The', 'DET'), ('service', 'NOUN'), ('is', 'VERB'), ...]
#     Each tagged token is a (word, tag) TUPLE; a tagged sentence is a list of
#     tuples; a tagged corpus is a list of tagged sentences. Text form "word/TAG"
#     is converted with nltk.tag.str2tuple("fly/NOUN") -> ('fly', 'NOUN') and
#     back with nltk.tag.tuple2str. All NLTK taggers take a list of words
#     tagger.tag(tokens) and return a list of (word, tag) tuples.
#
#  4) DEFAULT TAGGING - the nltk.DefaultTagger class
#     DefaultTagger(tag) is the simplest tagger: it gives EVERY token the same
#     tag you pass to the constructor, e.g. nltk.DefaultTagger('NN'). The best
#     choice is the most frequent tag in the training data (found with
#     nltk.FreqDist). It is a subclass of SequentialBackoffTagger, has methods
#     tag(tokens) and tag_sents(sentences), and is used as the BASELINE and as
#     the LAST BACKOFF of other taggers (when they do not know a word, it still
#     returns something). Its accuracy is low (roughly 15-35%) because only
#     the words of that one class are tagged correctly.
#
#  5) RULE-BASED TAGGING
#     Uses hand-written linguistic rules (a small dictionary + suffix/context
#     rules), e.g.  word ends with "-ing"/"-ed" -> VERB, ends with "-ly" -> ADV,
#     digits -> NUM, "the/a/an" -> DET.  NLTK: nltk.RegexpTagger(patterns).
#     + Easy to understand, needs no training data.
#     - Rules are written manually, are never complete, and cannot easily handle
#       ambiguity.
#
#  6) STOCHASTIC (PROBABILISTIC) TAGGING - learns from a tagged training corpus
#     a) WORD-FREQUENCY approach (Unigram tagger): give each word the tag it
#        had MOST OFTEN in the training data:   tag(w) = argmax_t C(w, t).
#        Ignores context; unknown words get no tag.
#     b) TAG-SEQUENCE approach (N-gram taggers): the tag also depends on the
#        previous tag(s):  Bigram -> P(t_i | t_i-1, w_i), Trigram -> t_i-2, t_i-1.
#        Unseen contexts are handled with BACKOFF:
#        Trigram -> Bigram -> Unigram -> Rule-based -> Default.
#     c) HMM tagger (see 8).
#
#  7) TRANSFORMATION-BASED TAGGING (Brill tagger)
#     Start with an initial tagging (e.g. most frequent tag of each word), then
#     LEARN an ordered list of correction rules of the form
#        "change tag A to B when <condition>"
#     such as "change NOUN to VERB if the previous tag is PRT" ("to /run/").
#     The rule that fixes the most errors is picked first; repeat. Combines the
#     readability of rules with learning from data.
#
#  8) HMM for POS tagging
#     Hidden states = tags, observations = words. Choose the tag sequence that
#        T* = argmax  PRODUCT_i  P(w_i | t_i) * P(t_i | t_i-1)
#               emission prob.    transition prob.
#     The probabilities are counted from a tagged corpus and the best sequence
#     is found with the VITERBI algorithm (see Experiment 5).
#
# STEPS: 1 Data import | 2 Pre-processing | 3 Main logic (all taggers)
#        4 Accuracy testing | 5 Visualization
# =============================================================================
import re
from collections import Counter
import nltk
import pandas as pd
import matplotlib.pyplot as plt
from nltk.tag import hmm, brill, brill_trainer
from sklearn.model_selection import train_test_split

for pkg in ["averaged_perceptron_tagger", "averaged_perceptron_tagger_eng", "universal_tagset"]:
    nltk.download(pkg, quiet=True)

CSV_PATH, TEXT_COL = "data1.csv", "text"        # edit for lab dataset
USE_TREEBANK = False                            # True = use NLTK's hand-tagged Penn Treebank sample

# ---------------------------- STEP 1 : DATA IMPORT ---------------------------
if USE_TREEBANK:
    nltk.download("treebank", quiet=True)
    from nltk.corpus import treebank
    tagged = [[(w.lower(), t) for w, t in s] for s in treebank.tagged_sents(tagset="universal")]
    print("Loaded", len(tagged), "tagged sentences from the Treebank corpus\n")
else:
    df = pd.read_csv(CSV_PATH).dropna(subset=[TEXT_COL])
    print("Rows:", len(df), "| Columns:", list(df.columns))
    print(df.head(), "\n")

# --------------------------- STEP 2 : PRE-PROCESSING -------------------------
# sentence (string) -> tokens (list of words) -> tagged tokens (list of tuples)
if not USE_TREEBANK:
    def to_tagged(text):
        tokens = re.findall(r"[A-Za-z]+", str(text).replace("n't", " not"))   # tokenize
        pairs = nltk.pos_tag(tokens, tagset="universal")                      # [(word, tag), ...]
        return [(w.lower(), t) for w, t in pairs]
    tagged = [to_tagged(t) for t in df[TEXT_COL]]
    tagged = [s for s in tagged if s]      # NOTE: reference tags come from NLTK's pre-trained tagger

print("Sentence as tokens        :", [w for w, _ in tagged[0]])
print("Sentence as list of tuples:", tagged[0])
print("Tuple <-> string          :", nltk.tag.tuple2str(tagged[0][1]), "->", nltk.tag.str2tuple("fly/NOUN"), "\n")

train, test = train_test_split(tagged, test_size=0.2, random_state=42)    # 80% train, 20% test
print(f"Train: {len(train)} | Test: {len(test)} sentences\n")

# --------------------------- STEP 3 : MAIN LOGIC (TAGGERS) -------------------
# 3.1 Default tagger : the most frequent tag in the training data for every word
tag_counts = nltk.FreqDist(t for s in train for _, t in s)
most_common_tag = tag_counts.max()
print("Tag frequencies:", dict(tag_counts.most_common()))
print("Most frequent tag (used by DefaultTagger):", most_common_tag, "\n")
default_tagger = nltk.DefaultTagger(most_common_tag)

# 3.2 Rule-based tagger : hand-written closed-class word lists + suffix rules
rules = [
    (r"^(the|a|an|this|that|these|those|all|every|each|any)$", "DET"),
    (r"^(i|you|he|she|it|we|they|my|your|his|her|its|our|their|what|nothing)$", "PRON"),
    (r"^(is|are|was|were|be|been|am|has|have|had|do|does|did|would|could|will|can|should)$", "VERB"),
    (r"^(and|but|or|nor)$", "CONJ"),
    (r"^(in|on|at|of|for|with|by|from|about|after|before|into)$", "ADP"),
    (r"^(not|never|very|really|just|also|too|so|extremely|absolutely)$", "ADV"),
    (r"^to$", "PRT"),
    (r"^(one|two|three|four|five|six|seven|eight|nine|ten)$", "NUM"),
    (r".*ing$", "VERB"), (r".*ed$", "VERB"),            # suffix rules
    (r".*ly$", "ADV"),
    (r".*(ful|ous|ive|able|ible|al|ic|less)$", "ADJ"),
    (r".*", "NOUN"),                                     # anything else -> NOUN
]
rule_tagger = nltk.RegexpTagger(rules)

# 3.3 Stochastic taggers (learn from the tagged training data)
unigram = nltk.UnigramTagger(train)                      # word-frequency approach
bigram = nltk.BigramTagger(train)                        # tag depends on previous tag
trigram = nltk.TrigramTagger(train)
combined = nltk.TrigramTagger(train, backoff=nltk.BigramTagger(
    train, backoff=nltk.UnigramTagger(train, backoff=rule_tagger)))   # backoff chain

# 3.4 Transformation-based (Brill) tagger : learns correction rules
initial = nltk.UnigramTagger(train, backoff=rule_tagger)
trainer = brill_trainer.BrillTaggerTrainer(initial, brill.fntbl37(), trace=0)
brill_tagger = trainer.train(train, max_rules=20)
print("First learned Brill rules (change tag A -> B when condition):")
for r in brill_tagger.rules()[:5]:
    print("   ", r)
print()

# 3.5 HMM tagger : transition + emission probabilities, decoded with Viterbi
hmm_tagger = hmm.HiddenMarkovModelTrainer().train_supervised(
    train, estimator=lambda fd, bins: nltk.LidstoneProbDist(fd, 0.1, bins))

taggers = {"Default": default_tagger, "Rule-based": rule_tagger, "Unigram": unigram,
           "Bigram": bigram, "Trigram": trigram, "Combined (backoff)": combined,
           "Brill (transformation)": brill_tagger, "HMM": hmm_tagger}

# Same sentence tagged by every tagger
words = [w for w, _ in test[0]]
demo = pd.DataFrame({"word": words, "reference": [t for _, t in test[0]]})
for name, tg in taggers.items():
    demo[name] = [t for _, t in tg.tag(words)]
print("One test sentence tagged by every tagger:")
print(demo.to_string(index=False), "\n")

# --------------------------- STEP 4 : ACCURACY TESTING -----------------------
def predict(tagger, sents):
    return [[t for _, t in tagger.tag([w for w, _ in s])] for s in sents]

gold = [t for s in test for _, t in s]
accuracy, preds = {}, {}
for name, tg in taggers.items():
    preds[name] = [t for sent in predict(tg, test) for t in sent]
    accuracy[name] = sum(p == g for p, g in zip(preds[name], gold)) / len(gold) * 100

print(f"{'Tagger':<26}{'Accuracy':>10}")
for name, acc in accuracy.items():
    print(f"{name:<26}{acc:>9.2f}%")
best = max(accuracy, key=accuracy.get)
print(f"\nBest tagger: {best} ({accuracy[best]:.2f}%)")

# Accuracy per tag for the best tagger
tag_total, tag_hit = Counter(gold), Counter(g for p, g in zip(preds[best], gold) if p == g)
per_tag = {t: tag_hit[t] / tag_total[t] * 100 for t in tag_total}

# --------------------------- STEP 5 : VISUALIZATION --------------------------
fig, ax = plt.subplots(1, 3, figsize=(18, 5))

ax[0].barh(list(accuracy), list(accuracy.values()), color="#3498db")
ax[0].invert_yaxis(); ax[0].set_xlim(0, 105); ax[0].set_xlabel("Accuracy (%)")
ax[0].set_title("Accuracy of Each Tagger")
for i, v in enumerate(accuracy.values()):
    ax[0].text(v + 1, i, f"{v:.1f}", va="center")

ax[1].bar(*zip(*tag_counts.most_common()), color="#e67e22")
ax[1].set_title("Tag Distribution in Training Data"); ax[1].tick_params(axis="x", rotation=45)

ax[2].bar(per_tag.keys(), per_tag.values(), color="#2ecc71")
ax[2].set_ylim(0, 105); ax[2].set_ylabel("Accuracy (%)")
ax[2].set_title(f"Accuracy per Tag ({best})"); ax[2].tick_params(axis="x", rotation=45)

plt.tight_layout()
plt.show()





# pip install pandas numpy matplotlib scikit-learn
# =============================================================================
# NLP EXPERIMENT 7 : TEXT CHUNKING
#   Fixed-size, Sliding-window, and Dynamic (sentence-based / conversation-based)
# AIM : Study and implement different chunking techniques and compare how well
#       each one keeps the text meaningful.
#
# THEORY
#  1) What is chunking?
#     Chunking is splitting a long text into smaller pieces (chunks) that can be
#     processed one by one. (In classical NLP "chunking" also means shallow
#     parsing, e.g. noun-phrase chunks; here it means TEXT SEGMENTATION.)
#
#  2) Why is it needed?
#     - Language models and embedding models have a limited input length
#       (context window), so long documents must be cut into pieces.
#     - Small focused chunks give more accurate search / retrieval (RAG,
#       chatbots, semantic search) than one huge document.
#     - Smaller inputs are faster and cheaper to process and store.
#     - A good chunk keeps a COMPLETE idea; a bad cut splits a sentence and
#       loses meaning.
#
#  3) Types of chunking
#     a) FIXED-SIZE chunking : cut every N characters / words / tokens.
#        + Very simple and fast, uniform size.
#        - Ignores meaning: it can cut a sentence or a word group in half.
#     b) SLIDING-WINDOW chunking : fixed-size chunks that OVERLAP. A window of
#        size N moves forward by a step of (N - overlap).
#           window = 50 words, overlap = 15 -> chunks start at 0, 35, 70 ...
#        + Information at a boundary appears in two chunks, so context is kept.
#        - More chunks and duplicated text (more storage and compute).
#     c) DYNAMIC chunking : chunk size is NOT fixed; boundaries follow the
#        structure of the text.
#        - SENTENCE-based : split into sentences, then pack whole sentences into
#          a chunk until a size limit is reached. Never cuts a sentence.
#        - CONVERSATION-based : the unit is a conversation TURN (a message).
#          Turns are grouped together; a NEW chunk starts when the topic
#          changes (low TF-IDF similarity between the new turn and the current
#          chunk) AND the chunk already has a minimum size, or when the size
#          limit is reached. A question and its answer stay together.
#        + Meaningful, complete chunks.   - Uneven sizes, slightly more complex.
#     (Other types: paragraph-based, recursive, semantic and document-structure
#      chunking.)
#
#  4) Applications
#     Retrieval-Augmented Generation (RAG) and chatbots, search engines and
#     vector databases, long-document question answering, summarisation of long
#     text, chat-history memory management, transcripts of calls / meetings.
#
#  5) Evaluation used here (no labels needed)
#     - Number of chunks, average chunk size
#     - Sentence completeness % : sentences that fit COMPLETELY inside at least
#       one chunk (higher = less information broken)
#     - Clean-boundary chunks % : chunks that start AND end at a sentence border
#     - Redundancy : total words in all chunks / words in the document
#       (1.0 = no duplication, more than 1.0 = overlap)
#
# STEPS: 1 Data import | 2 Pre-processing | 3 Main logic (chunkers)
#        4 Accuracy testing | 5 Visualization
# =============================================================================
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.metrics.pairwise import cosine_similarity

CSV_PATH, TEXT_COL = "data1.csv", "text"      # edit for lab dataset
CHUNK_SIZE = 50                              # words per chunk (fixed / sliding / max for dynamic)
OVERLAP = 15                                 # words shared by neighbouring sliding-window chunks
SIM_THRESHOLD = 0.10                         # conversation chunking: min similarity to stay in chunk
MIN_WORDS = 20                               # conversation chunking: do not split before this size

# ---------------------------- STEP 1 : DATA IMPORT ---------------------------
df = pd.read_csv(CSV_PATH).dropna(subset=[TEXT_COL]).reset_index(drop=True)
print("Rows:", len(df), "| Columns:", list(df.columns))
print(df.head(), "\n")

# --------------------------- STEP 2 : PRE-PROCESSING -------------------------
# Treat the whole file as ONE long document:
#   - each row is one TURN (message) of a conversation
#   - every word gets a position, so a chunk is just a (start, end) span of words
turn_texts = [str(t).strip() for t in df[TEXT_COL]]
words, turn_spans, sent_spans = [], [], []
for text in turn_texts:
    tokens = text.split()                            # tokenize on whitespace
    start = len(words)
    words += tokens
    turn_spans.append((start, len(words)))
    s = start
    for i in range(start, len(words)):               # sentence ends at . ! ? or end of turn
        if words[i][-1] in ".!?" or i == len(words) - 1:
            sent_spans.append((s, i + 1))
            s = i + 1

N = len(words)
sent_starts = {s for s, _ in sent_spans}
sent_ends = {e for _, e in sent_spans}
print(f"Document: {N} words | {len(sent_spans)} sentences | {len(turn_spans)} turns\n")

def text_of(span):
    return " ".join(words[span[0]:span[1]])

# ------------------------------ STEP 3 : MAIN LOGIC --------------------------
def fixed_chunks(size):
    """Every chunk has exactly `size` words (the last one may be shorter)."""
    return [(i, min(i + size, N)) for i in range(0, N, size)]

def sliding_chunks(size, overlap):
    """Window of `size` words moving forward by (size - overlap) words."""
    step, spans, i = size - overlap, [], 0
    while True:
        spans.append((i, min(i + size, N)))
        if i + size >= N:
            break
        i += step
    return spans

def sentence_chunks(max_words):
    """Dynamic: pack WHOLE sentences until the next one would exceed max_words."""
    spans, start, end = [], sent_spans[0][0], sent_spans[0][0]
    for s, e in sent_spans:
        if e - start > max_words and end > start:
            spans.append((start, end))
            start = s
        end = e
    spans.append((start, end))
    return spans

tfidf = TfidfVectorizer(stop_words="english").fit_transform(turn_texts)   # turn vectors

def conversation_chunks(max_words, threshold, min_words):
    """Dynamic: group turns; start a new chunk on a topic change or size limit."""
    spans, first = [], 0
    for i in range(1, len(turn_spans)):
        centroid = np.asarray(tfidf[first:i].mean(axis=0))                # current chunk "topic"
        similarity = cosine_similarity(centroid, tfidf[i])[0, 0]
        size_now = turn_spans[i - 1][1] - turn_spans[first][0]
        topic_change = similarity < threshold and size_now >= min_words
        too_big = turn_spans[i][1] - turn_spans[first][0] > max_words
        if topic_change or too_big:
            spans.append((turn_spans[first][0], turn_spans[i - 1][1]))
            first = i
    spans.append((turn_spans[first][0], turn_spans[-1][1]))
    return spans

chunkers = {"Fixed-size": fixed_chunks(CHUNK_SIZE),
            "Sliding window": sliding_chunks(CHUNK_SIZE, OVERLAP),
            "Sentence-based": sentence_chunks(CHUNK_SIZE),
            "Conversation-based": conversation_chunks(CHUNK_SIZE, SIM_THRESHOLD, MIN_WORDS)}

for name, spans in chunkers.items():
    print(f"--- {name}: first 2 chunks ---")
    for sp in spans[:2]:
        print(f"  [{sp[1] - sp[0]} words] {text_of(sp)[:150]}...")
    print()

# --------------------------- STEP 4 : ACCURACY TESTING -----------------------
rows = []
for name, spans in chunkers.items():
    sizes = [e - s for s, e in spans]
    complete = sum(any(cs <= s and e <= ce for cs, ce in spans) for s, e in sent_spans)
    clean = sum(s in sent_starts and e in sent_ends for s, e in spans)
    rows.append({"Method": name, "Chunks": len(spans),
                 "Avg size (words)": round(np.mean(sizes), 1),
                 "Min": min(sizes), "Max": max(sizes),
                 "Sentence completeness %": round(complete / len(sent_spans) * 100, 1),
                 "Clean-boundary chunks %": round(clean / len(spans) * 100, 1),
                 "Redundancy": round(sum(sizes) / N, 2)})
results = pd.DataFrame(rows).set_index("Method")
print(results.to_string(), "\n")

# --------------------------- STEP 5 : VISUALIZATION --------------------------
names = list(chunkers)
colors = ["#3498db", "#e67e22", "#2ecc71", "#9b59b6"]
fig, ax = plt.subplots(1, 3, figsize=(18, 5))

ax[0].boxplot([[e - s for s, e in chunkers[n]] for n in names])
ax[0].set_xticklabels(names, rotation=20)
ax[0].set_ylabel("Chunk size (words)"); ax[0].set_title("Chunk Size Distribution")

x = np.arange(len(names))
ax[1].bar(x - 0.2, results["Sentence completeness %"], width=0.4, label="Sentence completeness %", color="#2ecc71")
ax[1].bar(x + 0.2, results["Clean-boundary chunks %"], width=0.4, label="Clean-boundary chunks %", color="#e74c3c")
ax[1].set_xticks(x); ax[1].set_xticklabels(names, rotation=20)
ax[1].set_ylim(0, 110); ax[1].set_title("How Well Is Meaning Preserved?"); ax[1].legend(loc="lower right")

bars = ax[2].bar(names, results["Redundancy"], color=colors)
for b, c in zip(bars, results["Chunks"]):
    ax[2].text(b.get_x() + b.get_width() / 2, b.get_height() + 0.01, f"{c} chunks", ha="center")
ax[2].set_ylim(0, results["Redundancy"].max() + 0.2)
ax[2].set_ylabel("Redundancy (1.0 = no overlap)"); ax[2].set_title("Redundancy and Number of Chunks")
ax[2].tick_params(axis="x", rotation=20)

plt.tight_layout()
plt.show()





ner_data.csv
text,sentiment,entities
I received an email from Airtel about the upcoming event.,neutral,Airtel:ORGANIZATION
"Our trip to Dubai was horrible, the hotel was dirty and the staff was rude.",negative,Dubai:GPE
Rohit Sharma praised the excellent service at Apple in Delhi.,positive,Apple:ORGANIZATION;Rohit Sharma:PERSON;Delhi:GPE
"Really unhappy with Toyota, the delivery was late and the quality is poor.",negative,Toyota:ORGANIZATION
I received an email from Swiggy about the upcoming event.,neutral,Swiggy:ORGANIZATION
"Apple has excellent customer service, I am very happy.",positive,Apple:ORGANIZATION
"Goa is a beautiful city, I love it.",positive,Goa:GPE
"Dell never disappoints, such a wonderful experience!",positive,Dell:ORGANIZATION
"Really unhappy with Airtel, the delivery was late and the quality is poor.",negative,Airtel:ORGANIZATION
Infosys opened a new office last month.,neutral,Infosys:ORGANIZATION
"Microsoft and Toyota both have terrible service, I am disappointed.",negative,Microsoft:ORGANIZATION;Toyota:ORGANIZATION
"Our trip to Mumbai was horrible, the hotel was dirty and the staff was rude.",negative,Mumbai:GPE





# pip install pandas matplotlib nltk
# =============================================================================
# NLP EXPERIMENT 8 : PARSING WITH CFG + NAMED ENTITY RECOGNITION FOR SENTIMENT
# AIM : Parse sentences using a Context-Free Grammar, identify and classify the
#       named entities mentioned in the text, and find the sentiment about each.
#
# THEORY
#  1) Parsing
#     Parsing = analysing a sentence to find its grammatical structure (a tree).
#
#  2) Context-Free Grammar (CFG)
#     A set of rewrite rules  A -> B C  (left side = ONE non-terminal) plus a
#     start symbol S and terminals (words or word categories). Example:
#        S  -> NP VP          NP -> PN | Det Noun        VP -> Verb NP
#        PN -> 'Apple'        Det -> 'the'  Noun -> 'phone'  Verb -> 'launched'
#
#  3) Parsing using a CFG
#     Given a sentence and a grammar, find the rules that generate the sentence.
#        "Apple launched the phone"
#        (S (NP (PN Apple)) (VP (Verb launched) (NP (Det the) (Noun phone))))
#     Algorithms: top-down, bottom-up, CYK (Experiment 4); here NLTK's chart parser.
#     If the grammar allows several trees the sentence is AMBIGUOUS.
#     Link with NER: a node PN (proper-noun phrase) in the tree is a CANDIDATE
#     named entity:  Elon/PROPN Musk/PROPN visited/VERB Mumbai/PROPN
#                    -> PN(Elon Musk), PN(Mumbai)
#
#  4) Named Entity Recognition (NER)
#     NER finds names of real-world things in text (IDENTIFICATION) and assigns
#     each one a category (CLASSIFICATION):
#        "Sundar Pichai said Google will open an office in Mumbai on Monday."
#         [Sundar Pichai] PERSON   [Google] ORGANIZATION   [Mumbai] GPE (place)
#         [Monday] DATE
#     Common types: PERSON, ORGANIZATION, GPE/LOCATION, DATE, MONEY, PRODUCT.
#     Approaches: (a) rule-based / gazetteer (dictionary lookup) - precise but
#     only knows listed names; (b) statistical models (NLTK ne_chunk, CRF);
#     (c) deep learning (BERT, spaCy). Difficulties: ambiguity (Apple = fruit
#     or company), new names, capitalisation.
#     Used here: CFG finds the entity, then a gazetteer + NLTK ne_chunk gives
#     its type. (If the grammar cannot parse a sentence, runs of proper nouns
#     are used instead.)
#
#  5) Named-entity RELATIONSHIPS (relation extraction)
#     Relations connect two entities through a verb, giving triples
#     (entity1, relation, entity2):
#        "Satya Nadella joined Microsoft"  ->  (Satya Nadella, joined, Microsoft)
#     Simple pattern used here:  ENTITY1 ... VERB ... ENTITY2.
#
#  6) Entity-level sentiment
#     Sentiment of the sentence (rule-based: sentiment words + negation, as in
#     Experiment 1) is attached to every entity mentioned, so we can say WHICH
#     company / person / place people feel positive or negative about.
#
# STEPS: 1 Data import | 2 Pre-processing | 3 Main logic | 4 Accuracy | 5 Visualization
# =============================================================================
import itertools
from collections import Counter, defaultdict
import nltk
import pandas as pd
import matplotlib.pyplot as plt

for pkg in ["punkt", "punkt_tab", "averaged_perceptron_tagger", "averaged_perceptron_tagger_eng",
            "maxent_ne_chunker", "maxent_ne_chunker_tab", "words"]:
    nltk.download(pkg, quiet=True)                       # one-time downloads

CSV_PATH, TEXT_COL, LABEL_COL, GOLD_COL = "ner_data.csv", "text", "sentiment", "entities"

# ---------------------------- STEP 1 : DATA IMPORT ---------------------------
df = pd.read_csv(CSV_PATH).dropna(subset=[TEXT_COL]).reset_index(drop=True)
print("Rows:", len(df), "| Columns:", list(df.columns))
print(df.head(), "\n")
has_gold = GOLD_COL in df.columns                         # true entities (for accuracy testing)
gold = [set(tuple(e.rsplit(":", 1)) for e in str(g).split(";") if ":" in e) if has_gold else set()
        for g in df.get(GOLD_COL, [""] * len(df))]

# --------------------------- STEP 2 : PRE-PROCESSING -------------------------
# Keep capital letters (they help to find names), drop punctuation, then POS-tag.
df["tokens"] = df[TEXT_COL].apply(lambda t: [w for w in nltk.word_tokenize(str(t)) if w.isalnum()])
df["tagged"] = df["tokens"].apply(nltk.pos_tag)
print("Example:", df["tagged"][0], "\n")

# ------------------------------ STEP 3 : MAIN LOGIC --------------------------
# 3A. Parsing with a CFG over word categories (Penn tags -> simple categories)
PREFIX = [("NNP", "PROPN"), ("NN", "NOUN"), ("VB", "VERB"), ("MD", "VERB"), ("JJ", "ADJ"),
          ("RB", "ADV"), ("DT", "DET"), ("PRP", "PRON"), ("WP", "PRON"), ("IN", "ADP"),
          ("CC", "CONJ"), ("CD", "NUM"), ("TO", "PRT")]

def category(tag):
    return next((c for p, c in PREFIX if tag.startswith(p)), "ADV")      # other words ~ adverbs

grammar = nltk.CFG.fromstring("""
S    -> CL | CL Conj S | CL S
CL   -> NP VP | VP | NP | Adv CL
NP   -> Det NOM | NOM | Pron | Num NOM | PN | Det PN | NP PP
NOM  -> Noun | Noun NOM | Adj NOM | PN NOM
PN   -> Propn | Propn Propn | Propn Propn Propn
VP   -> Verb | Verb NP | Verb ADJP | Verb PP | Verb Adv | Verb VP | Adv VP | Prt VP | Verb NP PP | Verb NP Adv
ADJP -> Adj | Adv ADJP | Adj Conj ADJP | Adj PP
PP   -> Adp NP
Det -> 'DET'
Noun -> 'NOUN'
Propn -> 'PROPN'
Verb -> 'VERB'
Adj -> 'ADJ'
Adv -> 'ADV'
Pron -> 'PRON'
Num -> 'NUM'
Conj -> 'CONJ'
Prt -> 'PRT'
Adp -> 'ADP'
""")
parser = nltk.ChartParser(grammar)

def pn_count(tree):
    return sum(1 for _ in tree.subtrees(lambda t: t.label() == "PN"))

def propn_runs(tagged):
    """Fallback: runs of consecutive proper nouns (used when the grammar cannot parse)."""
    ents, run = [], []
    for w, t in tagged:
        if t.startswith("NNP"):
            run.append(w)
        elif run:
            ents.append(" ".join(run)); run = []
    return ents + [" ".join(run)] if run else ents

def parse_sentence(tagged):
    """Return (parse tree with words as leaves, list of PN phrases); tree is None if no parse."""
    cats = [category(t) for _, t in tagged]
    try:
        trees = list(itertools.islice(parser.parse(cats), 10))
    except ValueError:
        trees = []
    if not trees:
        return None, propn_runs(tagged)
    tree = min(trees, key=pn_count)                  # prefer the tree with the LONGEST name phrases
    for i, pos in enumerate(tree.treepositions("leaves")):
        tree[pos] = tagged[i][0]                     # put the real words back
    return tree, [" ".join(s.leaves()) for s in tree.subtrees(lambda t: t.label() == "PN")]

parsed = df["tagged"].apply(parse_sentence)
df["cfg_entities"] = parsed.apply(lambda x: x[1])
df["parsed"] = parsed.apply(lambda x: x[0] is not None)

idx = next(i for i in range(len(df)) if df["parsed"][i] and len(df["cfg_entities"][i]) >= 2)
print("Example sentence:", df[TEXT_COL][idx])
print("Parse tree (CFG):")
parsed[idx][0].pretty_print()
print("Entity candidates from the tree (PN nodes):", df["cfg_entities"][idx], "\n")

# 3B. Classification of entity type: gazetteer first, NLTK ne_chunk as fallback
GAZETTEER = {**{n: "ORGANIZATION" for n in ["apple", "samsung", "amazon", "google", "microsoft", "tesla",
                                            "netflix", "nike", "starbucks", "sony", "uber"]},
             **{n: "PERSON" for n in ["elon musk", "virat kohli", "taylor swift", "shah rukh khan",
                                      "tom hanks", "lionel messi"]},
             **{n: "GPE" for n in ["mumbai", "delhi", "paris", "london", "new york", "tokyo", "goa",
                                   "dubai", "rome"]},
             **{n: "DATE" for n in ["monday", "tuesday", "wednesday", "thursday", "friday"]}}
NE_MAP = {"GSP": "GPE", "LOCATION": "GPE", "FACILITY": "ORGANIZATION"}

def ne_chunk_entities(tagged):
    """Statistical NER with NLTK: list of (entity text, type). Merges neighbouring chunks."""
    ents, last_was_entity = [], False
    for node in nltk.ne_chunk(tagged):
        if hasattr(node, "label"):
            text, label = " ".join(w for w, _ in node.leaves()), NE_MAP.get(node.label(), node.label())
            if last_was_entity and ents[-1][1] == label:
                ents[-1] = (ents[-1][0] + " " + text, label)
            else:
                ents.append((text, label))
            last_was_entity = True
        else:
            last_was_entity = False
    return ents

df["ne_entities"] = df["tagged"].apply(ne_chunk_entities)

def classify_entities(cfg_ents, ne_ents):
    word_type = {w: label for text, label in ne_ents for w in text.split()}
    return [(e, GAZETTEER.get(e.lower(), word_type.get(e.split()[0], "UNKNOWN"))) for e in cfg_ents]

df["entities_final"] = [classify_entities(c, n) for c, n in zip(df["cfg_entities"], df["ne_entities"])]
print("Final entities (CFG + gazetteer + ne_chunk):", df["entities_final"][idx], "\n")

# 3C. Rule-based sentiment of each sentence (sentiment words + negation)
POSITIVE = set("""excellent happy impressed fast great wonderful love loved recommended amazing brilliant admire
    inspiring fantastic delicious friendly beautiful praised delighted good""".split())
NEGATIVE = set("""terrible disappointed disappointing disappoints unhappy late poor awful hate waste failing rude
    tired horrible dirty angry upset complained""".split())
NEGATIONS = {"not", "never", "no"}

def sentiment(tokens):
    words, total = [w.lower() for w in tokens], 0
    for i, w in enumerate(words):
        score = 1 if w in POSITIVE else -1 if w in NEGATIVE else 0
        if score and any(t in NEGATIONS for t in words[max(0, i - 2):i]):
            score = -score                                   # negation flips the polarity
        total += score
    return "positive" if total > 0 else "negative" if total < 0 else "neutral"

df["pred_sentiment"] = df["tokens"].apply(sentiment)

# Entity-level sentiment: every entity gets the sentiment of its sentence
entity_sent = defaultdict(Counter)
for ents, s in zip(df["entities_final"], df["pred_sentiment"]):
    for e, _ in ents:
        entity_sent[e][s] += 1
print("Sentiment per entity (top 8):")
for e, c in sorted(entity_sent.items(), key=lambda x: -sum(x[1].values()))[:8]:
    print(f"  {e:<16} positive={c['positive']:<3} negative={c['negative']:<3} neutral={c['neutral']}")
print()

# 3D. Simple relation extraction:  ENTITY1 ... VERB ... ENTITY2
def relations(tagged, entities):
    words, found, spans = [w for w, _ in tagged], [], []
    for e, _ in entities:
        parts = e.split()
        for i in range(len(words) - len(parts) + 1):
            if words[i:i + len(parts)] == parts:
                spans.append((i, i + len(parts), e))
    spans.sort()
    for (s1, e1, a), (s2, e2, b) in zip(spans, spans[1:]):
        verbs = [w for w, t in tagged[e1:s2] if t.startswith("VB")]
        if verbs:
            found.append((a, verbs[0], b))
    return found

df["relations"] = [relations(t, e) for t, e in zip(df["tagged"], df["entities_final"])]
print("Example relations (entity1, verb, entity2):")
for r in [r for rel in df["relations"] for r in rel][:5]:
    print("  ", r)
print()

# --------------------------- STEP 4 : ACCURACY TESTING -----------------------
def evaluate(pred_col):
    tp = fp = fn = type_ok = 0
    for pred, g in zip(df[pred_col], gold):
        pt, gt, gtype = {t for t, _ in pred}, {t for t, _ in g}, dict(g)
        tp, fp, fn = tp + len(pt & gt), fp + len(pt - gt), fn + len(gt - pt)
        type_ok += sum(typ == gtype[t] for t, typ in pred if t in gtype)
    p, r = tp / max(tp + fp, 1), tp / max(tp + fn, 1)
    return {"Precision": p, "Recall": r, "F1": 2 * p * r / max(p + r, 1e-9), "Type accuracy": type_ok / max(tp, 1)}

if has_gold:
    ner = pd.DataFrame({"NLTK ne_chunk": evaluate("ne_entities"),
                        "CFG + gazetteer + ne_chunk": evaluate("entities_final")}).T
    print("NER results (entities matched against the true entities):")
    print((ner * 100).round(1).to_string(), "\n")

parse_cov = df["parsed"].mean() * 100
sent_acc = (df["pred_sentiment"] == df[LABEL_COL]).mean() * 100
print(f"CFG parse coverage : {parse_cov:.1f}% of sentences parsed")
print(f"Sentiment accuracy : {sent_acc:.1f}%\n")

# --------------------------- STEP 5 : VISUALIZATION --------------------------
fig, ax = plt.subplots(1, 3, figsize=(18, 5))

if has_gold:
    (ner * 100).T.plot(kind="bar", ax=ax[0], rot=0)
    ax[0].set_ylim(0, 110); ax[0].set_ylabel("%"); ax[0].set_title("NER Accuracy by Method")
    ax[0].legend(fontsize=8, loc="lower right")

types = Counter(t for ents in df["entities_final"] for _, t in ents)
ax[1].bar(types.keys(), types.values(), color=["#3498db", "#e67e22", "#2ecc71", "#95a5a6"][:len(types)])
ax[1].set_title("Entity Types Found"); ax[1].set_ylabel("Mentions")

top = sorted(entity_sent.items(), key=lambda x: -sum(x[1].values()))[:10]
names = [e for e, _ in top]
bottom = [0] * len(top)
for label, color in [("positive", "#2ecc71"), ("neutral", "#95a5a6"), ("negative", "#e74c3c")]:
    vals = [c[label] for _, c in top]
    ax[2].barh(names, vals, left=bottom, label=label, color=color)
    bottom = [b + v for b, v in zip(bottom, vals)]
ax[2].invert_yaxis(); ax[2].legend(); ax[2].set_xlabel("Mentions")
ax[2].set_title("Sentiment per Entity (top 10)")

plt.tight_layout()
plt.show()

