natural language toolkit galechurch aligner c 20012023 nltk project torsten marek marekifi uzh ch contributor cassidy laidlaw liling tan url https www nltk org for license information see license txt a port of the galechurch aligner gale church 1993 a program for aligning sentences in bilingual corpora https aclweb organthologyj931004 pdf complementary error function z absx t 1 1 0 5 z r t math exp z z 1 26551223 t 1 00002368 t 0 37409196 t 0 09678418 t 0 18628806 t 0 27886807 t 1 13520398 t 1 48851587 t 0 82215223 t 0 17087277 if x 0 0 return r else return 2 0 r def normcdfx these are the languageindependent probabilities and parameters given in gale church for the computation l1 is always the language with less characters traverse the alignment cost from the tracebacks and retrieves appropriate sentence pairs param backlinks a dictionary where the key is the alignment points and value is the cost referencing the languageindependent priors type backlinks dict param sourcesentslens a list of target sentences lengths type sourcesentslens listint param targetsentslens a list of target sentences lengths type targetsentslens listint returns the log probability of the two sentences csourcesentsi ctargetsentsj being aligned with a specific calignment param i the offset of the source sentence param j the offset of the target sentence param sourcesents the list of source sentence lengths param targetsents the list of target sentence lengths param alignment the alignment type a tuple of two integers param params the sentence alignment parameters returns the log probability of a specific alignment between the two sentences given the parameters actually the paper says ls params variancecharacters this is based on the c reference implementation with ls in the denominator insertions are impossible return the sentence alignment of two text blocks usually paragraphs alignblocks5 5 5 7 7 7 0 0 1 1 2 2 alignblocks10 5 5 12 20 0 0 1 1 2 1 alignblocks12 20 10 5 5 0 0 1 1 1 2 alignblocks10 2 10 10 2 10 12 3 20 3 12 0 0 1 1 2 2 3 2 4 3 5 4 param sourcesentslens the list of source sentence lengths param targetsentslens the list of target sentence lengths param params the sentence alignment parameters return the sentence alignments a list of index pairs there are always three rows in the history with the last of them being filled creates the sentence alignment of two texts texts can consist of several blocks block boundaries cannot be crossed by sentence alignment links each block consists of a list that contains the lengths in characters of the sentences in this block param sourceblocks the list of blocks in the source text param targetblocks the list of blocks in the target text param params the sentence alignment parameters returns a list of sentence alignment lists file io functions may belong in a corpus reader splits an iterator cit at values of csplitvalue each instance of csplitvalue is swallowed the iterator produces subiterators which need to be consumed fully before the next subiterator can be used parses a stream of tokens and splits it into sentences using csoftdelimiter tokens and blocks using charddelimiter tokens for use with the laligntexts function natural language toolkit gale church aligner c 2001 2023 nltk project torsten marek marek ifi uzh ch contributor cassidy laidlaw liling tan url https www nltk org for license information see license txt a port of the gale church aligner gale church 1993 a program for aligning sentences in bilingual corpora https aclweb org anthology j93 1004 pdf complementary error function return the area under the normal distribution from m x these are the language independent probabilities and parameters given in gale church for the computation l_1 is always the language with less characters traverse the alignment cost from the tracebacks and retrieves appropriate sentence pairs param backlinks a dictionary where the key is the alignment points and value is the cost referencing the languageindependent priors type backlinks dict param source_sents_lens a list of target sentences lengths type source_sents_lens list int param target_sents_lens a list of target sentences lengths type target_sents_lens list int returns the log probability of the two sentences c source_sents i c target_sents j being aligned with a specific c alignment param i the offset of the source sentence param j the offset of the target sentence param source_sents the list of source sentence lengths param target_sents the list of target sentence lengths param alignment the alignment type a tuple of two integers param params the sentence alignment parameters returns the log probability of a specific alignment between the two sentences given the parameters actually the paper says l_s params variance_characters this is based on the c reference implementation with l_s in the denominator insertions are impossible return the sentence alignment of two text blocks usually paragraphs align_blocks 5 5 5 7 7 7 0 0 1 1 2 2 align_blocks 10 5 5 12 20 0 0 1 1 2 1 align_blocks 12 20 10 5 5 0 0 1 1 1 2 align_blocks 10 2 10 10 2 10 12 3 20 3 12 0 0 1 1 2 2 3 2 4 3 5 4 param source_sents_lens the list of source sentence lengths param target_sents_lens the list of target sentence lengths param params the sentence alignment parameters return the sentence alignments a list of index pairs there are always three rows in the history with the last of them being filled creates the sentence alignment of two texts texts can consist of several blocks block boundaries cannot be crossed by sentence alignment links each block consists of a list that contains the lengths in characters of the sentences in this block param source_blocks the list of blocks in the source text param target_blocks the list of blocks in the target text param params the sentence alignment parameters returns a list of sentence alignment lists file i o functions may belong in a corpus reader splits an iterator c it at values of c split_value each instance of c split_value is swallowed the iterator produces subiterators which need to be consumed fully before the next subiterator can be used parses a stream of tokens and splits it into sentences using c soft_delimiter tokens and blocks using c hard_delimiter tokens for use with the l align_texts function
import math

try:
    from norm import logsf as norm_logsf
    from scipy.stats import norm
except ImportError:

    def erfcc(x):
        
        z = abs(x)
        t = 1 / (1 + 0.5 * z)
        r = t * math.exp(
            -z * z
            - 1.26551223
            + t
            * (
                1.00002368
                + t
                * (
                    0.37409196
                    + t
                    * (
                        0.09678418
                        + t
                        * (
                            -0.18628806
                            + t
                            * (
                                0.27886807
                                + t
                                * (
                                    -1.13520398
                                    + t
                                    * (1.48851587 + t * (-0.82215223 + t * 0.17087277))
                                )
                            )
                        )
                    )
                )
            )
        )
        if x >= 0.0:
            return r
        else:
            return 2.0 - r

    def norm_cdf(x):
        
        return 1 - 0.5 * erfcc(x / math.sqrt(2))

    def norm_logsf(x):
        try:
            return math.log(1 - norm_cdf(x))
        except ValueError:
            return float("-inf")


LOG2 = math.log(2)


class LanguageIndependent:
    
    

    
    PRIORS = {
        (1, 0): 0.0099,
        (0, 1): 0.0099,
        (1, 1): 0.89,
        (2, 1): 0.089,
        (1, 2): 0.089,
        (2, 2): 0.011,
    }

    AVERAGE_CHARACTERS = 1
    VARIANCE_CHARACTERS = 6.8


def trace(backlinks, source_sents_lens, target_sents_lens):
    
    links = []
    position = (len(source_sents_lens), len(target_sents_lens))
    while position != (0, 0) and all(p >= 0 for p in position):
        try:
            s, t = backlinks[position]
        except TypeError:
            position = (position[0] - 1, position[1] - 1)
            continue
        for i in range(s):
            for j in range(t):
                links.append((position[0] - i - 1, position[1] - j - 1))
        position = (position[0] - s, position[1] - t)

    return links[::-1]


def align_log_prob(i, j, source_sents, target_sents, alignment, params):
    
    l_s = sum(source_sents[i - offset - 1] for offset in range(alignment[0]))
    l_t = sum(target_sents[j - offset - 1] for offset in range(alignment[1]))
    try:
        
        
        m = (l_s + l_t / params.AVERAGE_CHARACTERS) / 2
        delta = (l_s * params.AVERAGE_CHARACTERS - l_t) / math.sqrt(
            m * params.VARIANCE_CHARACTERS
        )
    except ZeroDivisionError:
        return float("-inf")

    return -(LOG2 + norm_logsf(abs(delta)) + math.log(params.PRIORS[alignment]))


def align_blocks(source_sents_lens, target_sents_lens, params=LanguageIndependent):
    

    alignment_types = list(params.PRIORS.keys())

    
    D = [[]]

    backlinks = {}

    for i in range(len(source_sents_lens) + 1):
        for j in range(len(target_sents_lens) + 1):
            min_dist = float("inf")
            min_align = None
            for a in alignment_types:
                prev_i = -1 - a[0]
                prev_j = j - a[1]
                if prev_i < -len(D) or prev_j < 0:
                    continue
                p = D[prev_i][prev_j] + align_log_prob(
                    i, j, source_sents_lens, target_sents_lens, a, params
                )
                if p < min_dist:
                    min_dist = p
                    min_align = a

            if min_dist == float("inf"):
                min_dist = 0

            backlinks[(i, j)] = min_align
            D[-1].append(min_dist)

        if len(D) > 2:
            D.pop(0)
        D.append([])

    return trace(backlinks, source_sents_lens, target_sents_lens)


def align_texts(source_blocks, target_blocks, params=LanguageIndependent):
    
    if len(source_blocks) != len(target_blocks):
        raise ValueError(
            "Source and target texts do not have the same number of blocks."
        )

    return [
        align_blocks(source_block, target_block, params)
        for source_block, target_block in zip(source_blocks, target_blocks)
    ]





def split_at(it, split_value):
    

    def _chunk_iterator(first):
        v = first
        while v != split_value:
            yield v
            v = it.next()

    while True:
        yield _chunk_iterator(it.next())


def parse_token_stream(stream, soft_delimiter, hard_delimiter):
    
    return [
        [
            sum(len(token) for token in sentence_it)
            for sentence_it in split_at(block_it, soft_delimiter)
        ]
        for block_it in split_at(stream, hard_delimiter)
    ]