natural language toolkit phrase extraction algorithm c 20012023 nltk project s liling tan fredrik hedman petra barancikova url https www nltk org for license information see license txt this function checks for alignment point consistency and extracts phrases using the chunk of consistent phrases a phrase pair e f is consistent with an alignment a if and only if i no english words in the phrase pair are aligned to words outside it e i e e i f j a f j f ii no foreign words in the phrase pair are aligned to words outside it f j f e i f j a e i e iii the phrase pair contains at least one alignment point e i e f j f s t e i f j a type fstart int param fstart starting index of the possible foreign language phrases type fend int param fend end index of the possible foreign language phrases type estart int param estart starting index of the possible source language phrases type eend int param eend end index of the possible source language phrases type srctext list param srctext the source language tokens a list of string type trgtext list param trgtext the target language tokens a list of string type srclen int param srclen the number of tokens in the source language tokens type trglen int param trglen the number of tokens in the target language tokens check if alignment points are consistent add phrase pairs incl additional unaligned f add phrase pair estart eend fs fe to set e need to 1 in range to include the endpoint include more data for later ordering phrase extraction algorithm extracts all consistent phrase pairs from a wordaligned sentence pair the idea is to loop over all possible source language e phrases and find the minimal foreign phrase f that matches each of them matching is done by identifying all alignment points for the source phrase and finding the shortest foreign phrase that includes all the foreign counterparts for the source words in short a phrase alignment has to a contain all alignment points for all covered words b contain at least one alignment point srctext michael assumes that he will stay in the house trgtext michael geht davon aus dass er im haus bleibt alignment 0 0 1 1 1 2 1 3 2 5 3 6 4 9 5 9 6 7 7 7 8 8 phrases phraseextractionsrctext trgtext alignment for i in sortedphrases printi 0 1 0 1 michael michael 0 2 0 4 michael assumes michael geht davon aus 0 2 0 5 michael assumes michael geht davon aus 0 3 0 6 michael assumes that michael geht davon aus dass 0 4 0 7 michael assumes that he michael geht davon aus dass er 0 9 0 10 michael assumes that he will stay in the house michael geht davon aus dass er im haus bleibt 1 2 1 4 assumes geht davon aus 1 2 1 5 assumes geht davon aus 1 3 1 6 assumes that geht davon aus dass 1 4 1 7 assumes that he geht davon aus dass er 1 9 1 10 assumes that he will stay in the house geht davon aus dass er im haus bleibt 2 3 4 6 that dass 2 3 5 6 that dass 2 4 4 7 that he dass er 2 4 5 7 that he dass er 2 9 4 10 that he will stay in the house dass er im haus bleibt 2 9 5 10 that he will stay in the house dass er im haus bleibt 3 4 6 7 he er 3 9 6 10 he will stay in the house er im haus bleibt 4 6 9 10 will stay bleibt 4 9 7 10 will stay in the house im haus bleibt 6 8 7 8 in the im 6 9 7 9 in the house im haus 8 9 8 9 house haus type srctext str param srctext the sentence string from the source language type trgtext str param trgtext the sentence string from the target language type alignment listtuple param alignment the word alignment outputs as list of tuples where the first elements of tuples are the source words indices and second elements are the target words indices this is also the output format of nltk translate ibm1 rtype listtuple return a list of tuples each element in a list is a phrase and each phrase is a tuple made up of i its source location ii its target location iii the source phrase and iii the target phrase the phrase list of tuples represents all the possible phrases extracted from the word alignments type maxphraselength int param maxphraselength maximal phrase length if 0 or not specified it is set to a length of the longer sentence srctext or trgtext keeps an index of which sourcetarget words that are aligned set of phrase pairs bp find the minimally matching foreign phrase f start f end lengthf 0 fstart 0 lenf 1 fend 0 lenf 1 add extract f start f end e start e end to set bp natural language toolkit phrase extraction algorithm c 2001 2023 nltk project s liling tan fredrik hedman petra barancikova url https www nltk org for license information see license txt this function checks for alignment point consistency and extracts phrases using the chunk of consistent phrases a phrase pair e f is consistent with an alignment a if and only if i no english words in the phrase pair are aligned to words outside it e i e e i f j a f j f ii no foreign words in the phrase pair are aligned to words outside it f j f e i f j a e i e iii the phrase pair contains at least one alignment point e i e f j f s t e i f j a type f_start int param f_start starting index of the possible foreign language phrases type f_end int param f_end end index of the possible foreign language phrases type e_start int param e_start starting index of the possible source language phrases type e_end int param e_end end index of the possible source language phrases type srctext list param srctext the source language tokens a list of string type trgtext list param trgtext the target language tokens a list of string type srclen int param srclen the number of tokens in the source language tokens type trglen int param trglen the number of tokens in the target language tokens 0 based indexing check if alignment points are consistent add phrase pairs incl additional unaligned f add phrase pair e_start e_end fs fe to set e need to 1 in range to include the end point include more data for later ordering phrase extraction algorithm extracts all consistent phrase pairs from a word aligned sentence pair the idea is to loop over all possible source language e phrases and find the minimal foreign phrase f that matches each of them matching is done by identifying all alignment points for the source phrase and finding the shortest foreign phrase that includes all the foreign counterparts for the source words in short a phrase alignment has to a contain all alignment points for all covered words b contain at least one alignment point srctext michael assumes that he will stay in the house trgtext michael geht davon aus dass er im haus bleibt alignment 0 0 1 1 1 2 1 3 2 5 3 6 4 9 5 9 6 7 7 7 8 8 phrases phrase_extraction srctext trgtext alignment for i in sorted phrases print i 0 1 0 1 michael michael 0 2 0 4 michael assumes michael geht davon aus 0 2 0 5 michael assumes michael geht davon aus 0 3 0 6 michael assumes that michael geht davon aus dass 0 4 0 7 michael assumes that he michael geht davon aus dass er 0 9 0 10 michael assumes that he will stay in the house michael geht davon aus dass er im haus bleibt 1 2 1 4 assumes geht davon aus 1 2 1 5 assumes geht davon aus 1 3 1 6 assumes that geht davon aus dass 1 4 1 7 assumes that he geht davon aus dass er 1 9 1 10 assumes that he will stay in the house geht davon aus dass er im haus bleibt 2 3 4 6 that dass 2 3 5 6 that dass 2 4 4 7 that he dass er 2 4 5 7 that he dass er 2 9 4 10 that he will stay in the house dass er im haus bleibt 2 9 5 10 that he will stay in the house dass er im haus bleibt 3 4 6 7 he er 3 9 6 10 he will stay in the house er im haus bleibt 4 6 9 10 will stay bleibt 4 9 7 10 will stay in the house im haus bleibt 6 8 7 8 in the im 6 9 7 9 in the house im haus 8 9 8 9 house haus type srctext str param srctext the sentence string from the source language type trgtext str param trgtext the sentence string from the target language type alignment list tuple param alignment the word alignment outputs as list of tuples where the first elements of tuples are the source words indices and second elements are the target words indices this is also the output format of nltk translate ibm1 rtype list tuple return a list of tuples each element in a list is a phrase and each phrase is a tuple made up of i its source location ii its target location iii the source phrase and iii the target phrase the phrase list of tuples represents all the possible phrases extracted from the word alignments type max_phrase_length int param max_phrase_length maximal phrase length if 0 or not specified it is set to a length of the longer sentence srctext or trgtext e f len e len f keeps an index of which source target words that are aligned set of phrase pairs bp find the minimally matching foreign phrase f start f end length f 0 f_start 0 len f 1 f_end 0 len f 1 0 based indexing add extract f start f end e start e end to set bp
def extract(
    f_start,
    f_end,
    e_start,
    e_end,
    alignment,
    f_aligned,
    srctext,
    trgtext,
    srclen,
    trglen,
    max_phrase_length,
):
    

    if f_end < 0:  
        return {}
    
    for e, f in alignment:
        if (f_start <= f <= f_end) and (e < e_start or e > e_end):
            return {}

    
    phrases = set()
    fs = f_start
    while True:
        fe = min(f_end, f_start + max_phrase_length - 1)
        while True:
            
            
            src_phrase = " ".join(srctext[e_start : e_end + 1])
            trg_phrase = " ".join(trgtext[fs : fe + 1])
            
            phrases.add(((e_start, e_end + 1), (fs, fe + 1), src_phrase, trg_phrase))
            fe += 1
            if fe in f_aligned or fe >= trglen:
                break
        fs -= 1
        if fs in f_aligned or fs < 0:
            break
    return phrases


def phrase_extraction(srctext, trgtext, alignment, max_phrase_length=0):
    

    srctext = srctext.split()  
    trgtext = trgtext.split()  
    srclen = len(srctext)  
    trglen = len(trgtext)  
    
    f_aligned = [j for _, j in alignment]
    max_phrase_length = max_phrase_length or max(srclen, trglen)

    
    bp = set()

    for e_start in range(srclen):
        max_idx = min(srclen, e_start + max_phrase_length)
        for e_end in range(e_start, max_idx):
            
            
            
            f_start, f_end = trglen - 1, -1  

            for e, f in alignment:
                if e_start <= e <= e_end:
                    f_start = min(f, f_start)
                    f_end = max(f, f_end)
            
            phrases = extract(
                f_start,
                f_end,
                e_start,
                e_end,
                alignment,
                f_aligned,
                srctext,
                trgtext,
                srclen,
                trglen,
                max_phrase_length,
            )
            if phrases:
                bp.update(phrases)
    return bp