Vecalign

repository·main·Indexed 41 days ago

https://github.com/thompsonb/vecalign

A tool for sentence alignment that leverages sentence embeddings and FastDTW to find correspondences between source and target text documents in linear time and space. Version 2.0.0 supports 1-many, many-1, and many-many alignments and is compatible with multilingual sentence embedders like LASER.

Tokens
4.5K
Snippets
12
Records
15
Agent score
52%

What's inside Vecalign

  1. How Vecalign performs sentence alignment

    main

    Vecalign is an accurate and fast sentence alignment algorithm designed for very long documents.

    Core Mechanism

    • Similarity Metric: It uses the similarity of multilingual sentence embeddings to judge sentence similarity.
    • Algorithm: It uses an approximation to Dynamic Programming based on Fast Dynamic Time Warping. This approach is linear in both time and space complexity relative to the number of sentences being aligned.
    • Language Support: When used with LASER, it supports approximately 200 languages without requiring machine translation or a lexicon.
  2. Prepare embeddings for custom documents

    main

    Vecalign requires embeddings for both individual sentences and concatenations of consecutive sentences to support 1-many, many-1, and many-many alignments.

    Step 1: Generate Overlap Files

    Use vecalign.overlap to create text files containing all necessary sentence combinations. The -n flag specifies the window size for concatenations.

    python -m vecalign.overlap -i <input_files> -o <output_overlap_file> -n <window_size>

    Step 2: Generate Embeddings

    Embed the resulting overlap files using a multilingual sentence embedder. Vecalign expects embeddings as a binary file containing float32 values.

    While Vecalign is compatible with various methods, LASER is recommended. If using LASER, ensure the $LASER environment variable is set.

    Note: LASER will not overwrite existing embedding files; you may need to delete them before re-running.

    # 1. Create overlap files (e.g., window size 10)
    python -m vecalign.overlap -i bleualign_data/dev.fr bleualign_data/test*.fr -o bleualign_data/overlaps.fr -n 10
    python -m vecalign.overlap -i bleualign_data/dev.de bleualign_data/test*.de -o bleualign_data/overlaps.de -n 10
    
    # 2. Embed using LASER (example for French and German)
    $LASER/tasks/embed/embed.sh bleualign_data/overlaps.fr bleualign_data/overlaps.fr.emb [fra]
    $LASER/tasks/embed/embed.sh bleualign_data/overlaps.de bleualign_data/overlaps.de.emb [deu]
  3. Install Vecalign using pixi or uv

    main

    Vecalign includes a Cython extension (dp_core) that requires a C compiler and Python development headers (e.g., Python.h).

    pixi can build an isolated environment with the necessary C compiler and development headers.

    pixi install
    pixi shell

    Option 2: Using uv

    If you already have a C compiler (e.g., gcc/clang) and python3-dev installed, you can use uv to create a virtual environment:

    uv venv
    source .venv/bin/activate
    uv pip install -e .

    After installation, you can use the vecalign executable or invoke the module directly via python -m vecalign.vecalign.

    # Using pixi
    pixi install
    pixi shell
    
    # Using uv
    uv venv
    source .venv/bin/activate
    uv pip install -e .
  4. Run Vecalign sentence alignment

    main

    To perform sentence alignment, use the vecalign command. You must provide the source and target documents, along with their corresponding embedding files.

    Output Format

    Alignments are written to stdout in the following format: [source_index]:[target_index]:cost

    • The first two entries are the source and target sentence indexes.
    • The third entry is the sentence alignment cost (includes normalization, but not the penalty for containing more than one sentence).
    • Cost is set to zero for insertions/deletions.

    Scoring against Gold Alignments

    To score your results against a gold standard, use the --gold (or -g) flag. The --src (-s), --tgt (-t), and --gold (-g) flags can accept multiple arguments (e.g., using wildcards) to align and score multiple files at once. Results are concatenated in stdout.

    Run vecalign -h for the full list of options.

    # Example alignment using provided embeddings
    vecalign --alignment_max_size 8 --src bleualign_data/dev.de --tgt bleualign_data/dev.fr \
       --src_embed bleualign_data/overlaps.de bleualign_data/overlaps.de.emb  \
       --tgt_embed bleualign_data/overlaps.fr bleualign_data/overlaps.fr.emb
    
    # Example scoring against gold reference
    vecalign --alignment_max_size 8 --src bleualign_data/test*.de --tgt bleualign_data/test*.fr \
       --gold bleualign_data/test*.defr  \
       --src_embed bleualign_data/overlaps.de bleualign_data/overlaps.de.emb  \
       --tgt_embed bleualign_data/overlaps.fr bleualign_data/overlaps.fr.emb > /dev/null
  5. Understand Strict vs. Lax alignment matching

    main

    Vecalign implements two types of matching logic to evaluate alignment quality:

    1. Strict Match: A test alignment (test_src, test_target) is considered a true positive if it is exactly identical to a gold alignment (gold_src, gold_tgt).
    2. Lax Match: A test alignment is considered a lax true positive if it is not a strict match, but there is partial overlap. Specifically, if the source indices in the test alignment have some overlap with the gold source indices, and the target indices in the test alignment also have some overlap with the corresponding gold target indices.

    This distinction allows for evaluating how well an alignment model performs when it might capture parts of a sentence alignment correctly even if the exact boundaries differ.

  6. Use the vecalign function

    main

    The core alignment logic is exposed via the vecalign function. It performs alignment on embedding vectors using dynamic programming and FastDTW-like logic.

    Parameters:

    • vecs0: Source embeddings.
    • vecs1: Target embeddings.
    • final_alignment_types: The types of alignments to consider (e.g., 1:1, 1:M).
    • del_percentile_frac: Fraction of the cost matrix distribution used for deletion penalty.
    • width_over2: Search buffer width.
    • max_size_full_dp: Threshold for running full $N^2$ dynamic programming.
    • costs_sample_size: Sample size for cost distribution estimation.
    • num_samps_for_norm: Number of samples for embedding normalization.
    from .dp_utils import vecalign
    
    stack = vecalign(
        vecs0=src_embeddings,
        vecs1=tgt_embeddings,
        final_alignment_types=alignment_types,
        del_percentile_frac=0.2,
        width_over2=width_over2,
        max_size_full_dp=300,
        costs_sample_size=20000,
        num_samps_for_norm=100
    )
    # stack[0] contains 'final_alignments' and 'alignment_scores'
  7. Calculate overlapping sentences with go()

    main

    The go function processes multiple input text files to identify and extract overlapping sentences based on a specified overlap threshold. It reads lines from each input file, uses yield_overlaps to find overlapping segments, collects them into a unique set, and writes the sorted results to an output file.

    Parameters:

    • output_file (str): Path to the file where the resulting overlapping sentences will be saved.
    • input_files (list[str]): A list of paths to the input text files.
    • num_overlaps (int): The maximum number of allowed overlaps per segment.
    from vecalign.overlap import go
    
    go(
        output_file='output.txt',
        input_files=['file1.txt', 'file2.txt'],
        num_overlaps=4
    )
  8. Log alignment scores to stderr with log_final_scores()

    main

    The log_final_scores(res) function takes a dictionary produced by score_multiple() and prints a formatted table to sys.stderr. This is useful for quick visual inspection of alignment performance metrics.

    from vecalign.score import log_final_scores
    
    res = {
        'recall_strict': 0.850,
        'recall_lax': 0.900,
        'precision_strict': 0.800,
        'precision_lax': 0.850,
        'f1_strict': 0.824,
        'f1_lax': 0.874
    }
    
    log_final_scores(res)
  9. Compute alignment scores with score_multiple()

    main

    Use score_multiple() to calculate precision, recall, and F1 scores (both strict and lax) across multiple pairs of alignment files.

    Input Formats:

    • gold_list: A list of alignment sets (the ground truth).
    • test_list: A list of alignment sets (the predicted alignments).
    • Each alignment set should be a list of tuples, where each tuple contains two collections of indices (e.g., [( (src_idx1, src_idx2), (tgt_idx1,) ), ... ]).

    Output Format: A dictionary containing the following keys:

    • precision_strict: Precision based on exact matches.
    • precision_lax: Precision based on partial overlaps.
    • recall_strict: Recall based on exact matches.
    • recall_lax: Recall based on partial overlaps.
    • f1_strict: F1 score for strict matching.
    • f1_lax: F1 score for lax matching.

    If a denominator is zero, the score defaults to the value_for_div_by_0 parameter (default is 0.0).

    from vecalign.score import score_multiple
    
    # Example alignment data
    gold_alignments = [((0, 1), (0,)), ((2,), (1, 2))]
    test_alignments = [((0,), (0,)), ((2,), (1,))] 
    
    results = score_multiple(gold_list=[gold_alignments], test_list=[test_alignments])
    print(results)
    # Output: {'recall_strict': ..., 'recall_lax': ..., 'precision_strict': ..., 'precision_lax': ..., 'f1_strict': ..., 'f1_lax': ...}
  10. Calculate normalized PERT PDF with pert_pdf_normalized()

    main

    The pert_pdf_normalized function calculates a normalized Probability Density Function (PDF) for a PERT distribution, which is a Beta distribution reparameterized by low, peak, high, and g.

    Parameters:

    • xx (numpy.ndarray): The values at which to evaluate the PDF.
    • peak (float): The mode of the distribution.
    • g (float, optional): The shape parameter. Defaults to PERT_G (20).
    • low (float, optional): The lower bound of the support. Defaults to -0.001.
    • high (float, optional): The upper bound of the support. Defaults to 1.001.

    Returns:

    • yy (numpy.ndarray): The normalized PDF values corresponding to xx.
    import numpy as np
    
    # Example usage
    x_vals = np.linspace(0, 1, 10)
    y_vals = pert_pdf_normalized(x_vals, peak=0.5, g=20)
  11. Build document embeddings with build_doc_embedding()

    main

    The build_doc_embedding function implements the method described in EMNLP 2020 paper to transform a sequence of sentence embeddings into a single document-level vector.

    It works by:

    1. Scaling sentence vectors by their inverse frequency (1/sent_counts).
    2. Spacing sentences across a temporal axis.
    3. Applying PERT distribution weights to each sentence across NUM_TIME_SLOTS.
    4. Creating chunk vectors and flattening them into a single normalized document vector.

    Parameters:

    • sent_vecs (numpy.ndarray): An array of shape (n_sentences, embedding_dimension). These should ideally be sentence embeddings (e.g., from LaBSE or LASER) projected into a lower-dimensional space.
    • sent_counts (numpy.ndarray): An array of shape (n_sentences,) representing how many times each sentence has been seen in the corpus. Higher counts result in lower weights.

    Returns:

    • doc_vec (numpy.ndarray): A normalized document vector of shape (embedding_dimension * NUM_TIME_SLOTS,).
    import numpy as np
    
    # Example setup
    sent_emb_size = 32
    n_sents = 7
    sent_vecs = np.random.random((n_sents, sent_emb_size)) - 0.5
    sent_counts = np.random.randint(low=1, high=50, size=n_sents)
    
    # Generate embedding
    doc_emb = build_doc_embedding(sent_vecs, sent_counts)
    
    print('Document Embedding Size:', doc_emb.shape) # Expected: (32 * 16,)
  12. Vecalign CLI Reference

    main

    The following command-line arguments are available for the vecalign CLI:

    FlagLong NameTypeDefaultDescription
    -s--srcstr+RequiredPreprocessed source file(s) to align
    -t--tgtstr+RequiredPreprocessed target file(s) to align
    -g--gold_alignmentstr+NoneGold alignment file(s) to score against
    --src_embed--src_embedstr 2RequiredSource embeddings. Requires: [text file, binary embeddings file]
    --tgt_embed--tgt_embedstr 2RequiredTarget embeddings. Requires: [text file, binary embeddings file]
    -a--alignment_max_sizeint4Max size N-M where N+M <= value
    --one_to_many--one_to_manyint?NoneEnables 1:M alignment. If flag present without arg, defaults to 50. Overrides -a
    -d--del_percentile_fracfloat0.2Deletion penalty percentile (0 to 1)
    -v--verboseflagFalseSets logging to DEBUG instead of WARN
    --max_size_full_dp--max_size_full_dpint300Max size N for full $N^2$ dynamic programming
    --costs_sample_size--costs_sample_sizeint20000Sample size to estimate cost distribution
    --num_samps_for_norm--num_samps_for_normint100Samples used for normalizing embeddings
    --search_buffer_size--search_buffer_sizeint5Width of search buffer (one side)
    --debug_save_stack--debug_save_stackstrNonePath to write pickle file for debugging
    --print_aligned_text--print_aligned_textflagFalsePrint aligned text alongside alignments