Chunking: Shallow Parsing for Phrase Identification in NLP

from nltk import word_tokenize, pos_tag
from nltk.chunk import ne_chunk

# Example sentence
sentence = "The quick brown fox jumps over the lazy dog."
tokens = word_tokenize(sentence)
tagged = pos_tag(tokens)

# NLTK's chunker produces a tree
chunked = ne_chunk(tagged)

def tree_to_chunks(tree):
    """Extract chunks from NLTK tree as (chunk_type, words) pairs."""
    chunks = []
    for subtree in tree:
        if hasattr(subtree, "label"):
            # This is a chunk
            chunk_type = subtree.label()
            words = [word for word, tag in subtree.leaves()]
            chunks.append((chunk_type, " ".join(words)))
    return chunks


# Also try a sentence with named entities
ne_sentence = "Barack Obama visited New York City yesterday."
ne_tokens = word_tokenize(ne_sentence)
ne_tagged = pos_tag(ne_tokens)
ne_chunked = ne_chunk(ne_tagged)
ne_chunks = tree_to_chunks(ne_chunked)

# Examples of noun phrases with varying complexity
np_examples = [
    ("the cat", "simple: determiner + noun"),
    ("a big red ball", "adjectives: det + adj + adj + noun"),
    ("President Obama", "proper: title + name"),
    ("three blind mice", "numeral: number + adj + noun"),
    ("the New York Stock Exchange", "complex: nested proper noun"),
]

# POS patterns that form noun phrases
np_patterns = [
    "DT NN",  # the cat
    "DT JJ NN",  # the black cat
    "DT JJ JJ NN",  # the big black cat
    "NNP NNP",  # Barack Obama
    "CD NN",  # three cats
    "PRP$ NN",  # my cat
    "JJ NN",  # black cat
    "NN NN",  # computer screen
]

# Examples of verb phrases
vp_examples = [
    ("runs", "simple present"),
    ("is running", "progressive"),
    ("has been running", "perfect progressive"),
    ("will have been running", "future perfect progressive"),
    ("can swim", "modal + base"),
    ("should have called", "modal + perfect"),
]

# POS patterns for verb phrases
vp_patterns = [
    "VBZ",  # runs
    "VBG",  # running
    "VBD",  # ran
    "MD VB",  # can run
    "VBZ VBG",  # is running
    "VBZ VBN",  # is eaten
    "MD VB VBN",  # will be eaten
]

# Examples of prepositional phrases
pp_examples = [
    ("in the house", "location"),
    ("with great care", "manner"),
    ("after the meeting", "time"),
    ("under the old oak tree", "complex location"),
    ("for my best friend", "beneficiary"),
]

other_chunks = {
    "ADJP": ("Adjective phrase", "very happy, quite tired"),
    "ADVP": ("Adverb phrase", "very quickly, rather slowly"),
    "SBAR": ("Subordinate clause", "that he left, if it rains"),
    "PRT": ("Particle", "give up, turn on"),
    "CONJP": ("Conjunction phrase", "as well as, rather than"),
}

# Example sentence with IOB chunk tags
sentence = "The quick brown fox jumps over the lazy dog"
tokens = sentence.split()

# IOB tags for chunks
iob_tags = [
    "B-NP",  # The
    "I-NP",  # quick
    "I-NP",  # brown
    "I-NP",  # fox
    "B-VP",  # jumps
    "B-PP",  # over
    "B-NP",  # the
    "I-NP",  # lazy
    "I-NP",  # dog
]

def chunks_to_iob(tokens, chunks):
    """
    Convert chunk spans to IOB tags.

    Args:
        tokens: List of tokens
        chunks: List of (start_idx, end_idx, chunk_type) tuples

    Returns:
        List of IOB tags, one per token
    """
    tags = ["O"] * len(tokens)

    for start, end, chunk_type in sorted(chunks, key=lambda x: x[0]):
        if start < 0 or end > len(tokens) or start >= end:
            continue

        tags[start] = f"B-{chunk_type}"
        for i in range(start + 1, end):
            tags[i] = f"I-{chunk_type}"

    return tags


def iob_to_chunks(tokens, tags):
    """
    Extract chunk spans from IOB tags.

    Returns:
        List of (start_idx, end_idx, chunk_type, text) tuples
    """
    chunks = []
    current_chunk = None  # (start_idx, chunk_type)

    for i, (token, tag) in enumerate(zip(tokens, tags)):
        if tag.startswith("B-"):
            # Close any open chunk
            if current_chunk is not None:
                start, ctype = current_chunk
                chunks.append((start, i, ctype))

            # Start new chunk
            chunk_type = tag[2:]
            current_chunk = (i, chunk_type)

        elif tag.startswith("I-"):
            chunk_type = tag[2:]

            # Handle orphan I tag
            if current_chunk is None:
                current_chunk = (i, chunk_type)
            elif current_chunk[1] != chunk_type:
                # Type mismatch: close old, start new
                start, ctype = current_chunk
                chunks.append((start, i, ctype))
                current_chunk = (i, chunk_type)

        else:  # O tag
            if current_chunk is not None:
                start, ctype = current_chunk
                chunks.append((start, i, ctype))
                current_chunk = None

    # Handle chunk at end
    if current_chunk is not None:
        start, ctype = current_chunk
        chunks.append((start, len(tokens), ctype))

    # Add text to each chunk
    result = []
    for start, end, ctype in chunks:
        text = " ".join(tokens[start:end])
        result.append((start, end, ctype, text))

    return result


# Test the converters
test_tokens = "The quick brown fox jumps over the lazy dog".split()
test_chunks = [
    (0, 4, "NP"),  # The quick brown fox
    (4, 5, "VP"),  # jumps
    (5, 6, "PP"),  # over
    (6, 9, "NP"),  # the lazy dog
]

test_iob = chunks_to_iob(test_tokens, test_chunks)
recovered_chunks = iob_to_chunks(test_tokens, test_iob)

# Illustrate the difference
example = "I saw the man with the telescope"

# Chunking output: flat, non-recursive
chunk_analysis = {
    "chunks": [
        ("I", "NP"),
        ("saw", "VP"),
        ("the man", "NP"),
        ("with", "PP"),
        ("the telescope", "NP"),
    ],
    "structure": "flat sequence of chunks",
}

# Full parsing output: hierarchical tree
parse_analysis = {
    "interpretation_1": "VP[saw NP[the man] PP[with NP[the telescope]]]",
    "interpretation_2": "VP[saw NP[the man PP[with NP[the telescope]]]]",
    "structure": "nested tree with attachment decisions",
}

from nltk import RegexpParser

# Define a grammar for noun phrase chunking
# Patterns use POS tags, not words
# NP: optional determiner/possessive, adjectives, nouns
# VP: optional modal, verbs
# PP: just the preposition
np_grammar = r"""
    NP: {<DT|PRP\$>?<JJ>*<NN.*>+}
    VP: {<MD>?<VB.*>+}
    PP: {<IN>}
"""

# Create the chunker
chunker = RegexpParser(np_grammar)

# Test sentences
test_sentences = [
    "The quick brown fox jumps over the lazy dog.",
    "A beautiful sunset illuminated the entire valley.",
    "My old computer finally crashed yesterday.",
]

regex_results = []
for sent in test_sentences:
    tokens = word_tokenize(sent)
    tagged = pos_tag(tokens)
    tree = chunker.parse(tagged)
    chunks = tree_to_chunks(tree)
    regex_results.append((sent, tagged, chunks))

# Explanation of the NP pattern
np_pattern_parts = {
    "<DT|PRP$>?": "Optional determiner (the, a) or possessive pronoun (my, your)",
    "<JJ>*": "Zero or more adjectives",
    "<NN.*>+": "One or more nouns (NN, NNS, NNP, NNPS)",
}

# More complex grammar with additional patterns
# NP patterns: basic NP, proper noun sequences, pronouns, number + nouns
# VP: verb phrases
# PP: preposition + NP (recursive-ish)
# ADVP: adverb phrases
extended_grammar = r"""
    NP: {<DT|PRP\$>?<JJ>*<NN.*>+}
        {<NNP>+}
        {<PRP>}
        {<CD><NN.*>+}
    VP: {<MD>?<VB.*>+}
    PP: {<IN><NP>}
    ADVP: {<RB.*>+}
"""

# Grammar with chinking
# Pattern explanation:
# - {<.*>+} chunks everything into NP
# - }<VB.*|IN|CC|\.>{ removes (chinks) verbs, prepositions, conjunctions, periods
chink_grammar = r"""
    NP: {<.*>+}
        }<VB.*|IN|CC|\.>{
"""

chink_chunker = RegexpParser(chink_grammar)

chink_test = "The cat and the dog sat on the mat."
chink_tokens = word_tokenize(chink_test)
chink_tagged = pos_tag(chink_tokens)
chink_tree = chink_chunker.parse(chink_tagged)
chink_chunks = tree_to_chunks(chink_tree)

# Cases where regex chunking struggles
problematic_cases = [
    {
        "sentence": "The man I saw yesterday left.",
        "issue": "Relative clause interrupts NP",
    },
    {
        "sentence": "Very very quickly running water.",
        "issue": "Ambiguous modifier scope",
    },
    {
        "sentence": "The old man the boats.",
        "issue": "Garden path: 'man' is a verb here",
    },
]

for case in problematic_cases:
    tokens = word_tokenize(case["sentence"])
    tagged = pos_tag(tokens)
    tree = chunker.parse(tagged)
    case["tagged"] = tagged
    case["chunks"] = tree_to_chunks(tree)

from nltk.corpus import conll2000

# Load the data
train_sents = conll2000.chunked_sents(
    "train.txt", chunk_types=["NP", "VP", "PP"]
)
test_sents = conll2000.chunked_sents("test.txt", chunk_types=["NP", "VP", "PP"])

# Look at the data format
sample_sent = train_sents[0]

def tree_to_iob_triples(tree):
    """Convert NLTK tree to (word, pos, iob) triples."""
    triples = []
    for subtree in tree:
        if hasattr(subtree, "label"):
            # This is a chunk
            chunk_type = subtree.label()
            for i, (word, pos) in enumerate(subtree.leaves()):
                if i == 0:
                    iob = f"B-{chunk_type}"
                else:
                    iob = f"I-{chunk_type}"
                triples.append((word, pos, iob))
        else:
            # Single word, not in a chunk
            word, pos = subtree
            triples.append((word, pos, "O"))
    return triples


# Convert sample
sample_iob = tree_to_iob_triples(sample_sent)

def evaluate_chunker(chunker, test_trees):
    """Evaluate a chunker on test data."""
    true_positives = 0
    false_positives = 0
    false_negatives = 0

    for tree in test_trees:
        # Get gold chunks
        gold_chunks = set()
        for subtree in tree:
            if hasattr(subtree, "label"):
                words = tuple(word for word, _ in subtree.leaves())
                gold_chunks.add((subtree.label(), words))

        # Get predicted chunks
        tagged = [(word, pos) for word, pos in tree.pos()]
        pred_tree = chunker.parse(tagged)
        pred_chunks = set()
        for subtree in pred_tree:
            if hasattr(subtree, "label"):
                words = tuple(word for word, _ in subtree.leaves())
                pred_chunks.add((subtree.label(), words))

        # Count matches
        true_positives += len(gold_chunks & pred_chunks)
        false_positives += len(pred_chunks - gold_chunks)
        false_negatives += len(gold_chunks - pred_chunks)

    precision = (
        true_positives / (true_positives + false_positives)
        if (true_positives + false_positives) > 0
        else 0
    )
    recall = (
        true_positives / (true_positives + false_negatives)
        if (true_positives + false_negatives) > 0
        else 0
    )
    f1 = (
        2 * precision * recall / (precision + recall)
        if (precision + recall) > 0
        else 0
    )

    return {
        "precision": precision,
        "recall": recall,
        "f1": f1,
        "true_positives": true_positives,
        "false_positives": false_positives,
        "false_negatives": false_negatives,
    }


# Evaluate our regex chunker
regex_eval = evaluate_chunker(chunker, test_sents[:500])

def extract_np_vp_np_triples(sentence):
    """Extract subject-verb-object triples using chunking."""
    tokens = word_tokenize(sentence)
    tagged = pos_tag(tokens)
    tree = chunker.parse(tagged)

    # Collect chunks in order
    chunks = []
    for subtree in tree:
        if hasattr(subtree, "label"):
            text = " ".join(word for word, _ in subtree.leaves())
            chunks.append((subtree.label(), text))

    # Look for NP-VP-NP patterns
    triples = []
    for i in range(len(chunks) - 2):
        if (
            chunks[i][0] == "NP"
            and chunks[i + 1][0] == "VP"
            and chunks[i + 2][0] == "NP"
        ):
            subject = chunks[i][1]
            verb = chunks[i + 1][1]
            obj = chunks[i + 2][1]
            triples.append((subject, verb, obj))

    return triples


# Test extraction
extraction_examples = [
    "The cat chased the mouse.",
    "Scientists discovered a new species.",
    "The company launched its new product.",
]

extraction_results = []
for sent in extraction_examples:
    triples = extract_np_vp_np_triples(sent)
    extraction_results.append((sent, triples))

import nltk
from collections import Counter


def extract_noun_phrases(text):
    """Extract all noun phrases from text."""
    sentences = nltk.sent_tokenize(text)
    all_nps = []

    for sent in sentences:
        tokens = word_tokenize(sent)
        tagged = pos_tag(tokens)
        tree = chunker.parse(tagged)

        for subtree in tree:
            if hasattr(subtree, "label") and subtree.label() == "NP":
                np_text = " ".join(word.lower() for word, _ in subtree.leaves())
                all_nps.append(np_text)

    return all_nps


# Example text
sample_text = """
Machine learning is transforming natural language processing. 
Deep neural networks have achieved remarkable results on many NLP tasks.
Transformer models like BERT and GPT have set new benchmarks.
These language models learn rich representations from large text corpora.
"""

nps = extract_noun_phrases(sample_text)
np_counts = Counter(nps)

def find_answer_candidates(question, context):
    """Find potential answer spans in context based on question type."""
    # Determine question type
    q_lower = question.lower()
    if q_lower.startswith("who"):
        target_chunk = "NP"  # Look for noun phrases (people)
    elif q_lower.startswith("where"):
        target_chunk = "PP"  # Look for prepositional phrases (locations)
    elif q_lower.startswith("what"):
        target_chunk = "NP"  # Look for noun phrases (things)
    else:
        target_chunk = "NP"  # Default

    # Extract chunks from context
    tokens = word_tokenize(context)
    tagged = pos_tag(tokens)
    tree = chunker.parse(tagged)

    candidates = []
    for subtree in tree:
        if hasattr(subtree, "label") and subtree.label() == target_chunk:
            text = " ".join(word for word, _ in subtree.leaves())
            candidates.append(text)

    return candidates


# Example
qa_question = "Who wrote the novel?"
qa_context = "The famous author Ernest Hemingway wrote the novel in 1929."
qa_candidates = find_answer_candidates(qa_question, qa_context)

import nltk
from nltk.chunk import ChunkParserI
from nltk.tag import UnigramTagger


class UnigramChunker(ChunkParserI):
    """A simple chunker that uses a unigram tagger on (POS, IOB) pairs."""

    def __init__(self, train_sents):
        # Convert trees to (word, pos, iob) sequences
        train_data = []
        for tree in train_sents:
            iob_triples = tree_to_iob_triples(tree)
            # Create (pos, iob) pairs for training
            pos_iob_pairs = [(pos, iob) for word, pos, iob in iob_triples]
            train_data.append(pos_iob_pairs)

        # Train a unigram tagger to predict IOB from POS
        self.tagger = UnigramTagger(train_data)

    def parse(self, tagged_sent):
        """Parse a POS-tagged sentence into a chunk tree."""
        # Get POS tags
        pos_tags = [pos for word, pos in tagged_sent]

        # Predict IOB tags
        iob_tags = [self.tagger.tag([pos])[0][1] or "O" for pos in pos_tags]

        # Build IOB tagged sentence
        iob_tagged = [
            (word, pos, iob) for (word, pos), iob in zip(tagged_sent, iob_tags)
        ]

        # Convert to tree
        return nltk.chunk.conlltags2tree(iob_tagged)


# Train the chunker
unigram_chunker = UnigramChunker(train_sents)

# Evaluate
unigram_eval = evaluate_chunker(unigram_chunker, test_sents[:500])

from nltk.tag import BigramTagger


class BigramChunker(ChunkParserI):
    """A chunker using bigram context."""

    def __init__(self, train_sents):
        train_data = []
        for tree in train_sents:
            iob_triples = tree_to_iob_triples(tree)
            pos_iob_pairs = [(pos, iob) for word, pos, iob in iob_triples]
            train_data.append(pos_iob_pairs)

        # Use bigram tagger with unigram backoff
        unigram = UnigramTagger(train_data)
        self.tagger = BigramTagger(train_data, backoff=unigram)

    def parse(self, tagged_sent):
        pos_tags = [pos for word, pos in tagged_sent]
        iob_tags = self.tagger.tag(pos_tags)
        iob_tags = [iob if iob else "O" for pos, iob in iob_tags]
        iob_tagged = [
            (word, pos, iob) for (word, pos), iob in zip(tagged_sent, iob_tags)
        ]
        return nltk.chunk.conlltags2tree(iob_tagged)


# Train and evaluate
bigram_chunker = BigramChunker(train_sents)
bigram_eval = evaluate_chunker(bigram_chunker, test_sents[:500])

import spacy

try:
    nlp = spacy.load("en_core_web_sm")
except OSError:
    import subprocess

    subprocess.run(
        ["python", "-m", "spacy", "download", "en_core_web_sm"],
        capture_output=True,
    )
    nlp = spacy.load("en_core_web_sm")

# Example sentences
spacy_examples = [
    "The quick brown fox jumps over the lazy dog.",
    "A major breakthrough in artificial intelligence was announced yesterday.",
    "The President of the United States addressed the nation.",
]

spacy_results = []
for sent in spacy_examples:
    doc = nlp(sent)
    chunks = [
        (chunk.text, chunk.root.text, chunk.root.dep_)
        for chunk in doc.noun_chunks
    ]
    spacy_results.append((sent, chunks))