Word Alignment Techniques in Machine Translation

def dice_coefficient(e_word, f_word, parallel_corpus):
    """
    Co-occurrence based alignment
    """
    count_ef = count_co_occurrence(e_word, f_word, parallel_corpus)
    count_e = count_word(e_word, english_corpus)
    count_f = count_word(f_word, french_corpus)
    
    dice = (2.0 * count_ef) / (count_e + count_f)
    return dice

# Align sentence pair
for e_word in english_sentence:
    best_f_word = max(french_sentence, key=lambda f: dice_coefficient(e, f))
    alignment.append((e_idx, f_idx))

def ibm_model1(parallel_corpus, max_iter=10):
    """
    Train IBM Model 1 using EM
    """
    # Initialize t(f|e) uniformly
    t = defaultdict(lambda: 1.0 / vocab_size)
    
    for iteration in range(max_iter):
        # E-step: Compute expected counts
        count = defaultdict(float)
        total = defaultdict(float)
        
        for e_sent, f_sent in parallel_corpus:
            # Add NULL word
            e_sent = ['NULL'] + e_sent
            
            for f_word in f_sent:
                # Normalization factor
                Z = sum(t[(f_word, e_word)] for e_word in e_sent)
                
                for e_word in e_sent:
                    # Posterior probability
                    delta = t[(f_word, e_word)] / Z
                    
                    count[(f_word, e_word)] += delta
                    total[e_word] += delta
        
        # M-step: Update parameters
        for (f_word, e_word) in count:
            t[(f_word, e_word)] = count[(f_word, e_word)] / total[e_word]
    
    return t

# Align using trained model
def align_with_ibm1(e_sent, f_sent, t):
    alignment = []
    e_sent = ['NULL'] + e_sent
    
    for j, f_word in enumerate(f_sent):
        # Find best alignment
        best_i = max(range(len(e_sent)), 
                     key=lambda i: t[(f_word, e_sent[i])])
        
        if best_i > 0:  # Skip NULL alignments
            alignment.append((best_i - 1, j))
    
    return alignment

alignment_final = alignment_e2f ∩ alignment_f2e

alignment_final = alignment_e2f ∪ alignment_f2e

def grow_diag_final(e2f, f2e):
    """
    Start with intersection, grow diagonally, add final links
    """
    # Step 1: Initialize with intersection
    alignment = e2f ∩ f2e
    
    # Step 2: Add neighboring links
    neighbors = [(±1, 0), (0, ±1), (±1, ±1), (±1, ∓1)]
    
    while True:
        added = False
        for (i, j) in alignment.copy():
            for (di, dj) in neighbors:
                new_link = (i + di, j + dj)
                
                if (new_link in e2f or new_link in f2e) and \
                   not_aligned(new_link):
                    alignment.add(new_link)
                    added = True
        
        if not added:
            break
    
    # Step 3: Add remaining union links
    for link in (e2f ∪ f2e):
        if not_aligned(link):
            alignment.add(link)
    
    return alignment

precision = |predicted ∩ gold| / |predicted|
recall = |predicted ∩ gold| / |gold|
f1 = 2 × (precision × recall) / (precision + recall)

import re
from nltk.tokenize import word_tokenize

def preprocess_sentence(text):
    # Lowercase
    text = text.lower()
    
    # Tokenize
    tokens = word_tokenize(text)
    
    # Remove punctuation (optional)
    # tokens = [t for t in tokens if t.isalnum()]
    
    return tokens

# Input: sentence pairs
parallel_corpus = [
    (["the", "cat", "sat"], ["le", "chat", "était"]),
    (["john", "loves", "mary"], ["jean", "aime", "marie"]),
    # ... 100K+ pairs
]

import matplotlib.pyplot as plt

def visualize_alignment(e_sent, f_sent, alignment):
    """
    Plot alignment matrix
    """
    matrix = np.zeros((len(e_sent), len(f_sent)))
    for (i, j) in alignment:
        matrix[i, j] = 1
    
    plt.imshow(matrix, cmap='Blues')
    plt.xticks(range(len(f_sent)), f_sent, rotation=45)
    plt.yticks(range(len(e_sent)), e_sent)
    plt.xlabel('French')
    plt.ylabel('English')
    plt.title('Word Alignment')
    plt.show()