natural language toolkit ibm model 5 c 20012023 nltk project tah wei hoon hoon twgmail com url https www nltk org for license information see license txt translation model that keeps track of vacant positions in the target sentence to decide where to place translated words translation can be viewed as a process where each word in the source sentence is stepped through sequentially generating translated words for each source word the target sentence can be viewed as being made up of m empty slots initially which gradually fill up as generated words are placed in them models 3 and 4 use distortion probabilities to decide how to place translated words for simplicity these models ignore the history of which slots have already been occupied with translated words consider the placement of the last translated word there is only one empty slot left in the target sentence so the distortion probability should be 1 0 for that position and 0 0 everywhere else however the distortion probabilities for models 3 and 4 are set up such that all positions are under consideration ibm model 5 fixes this deficiency by accounting for occupied slots during translation it introduces the vacancy function vj the number of vacancies up to and including position j in the target sentence terminology maximum vacancy the number of valid slots that a word can be placed in this is not necessarily the same as the number of vacant slots for example if a tablet contains more than one word the head word cannot be placed at the last vacant slot because there will be no space for the other words in the tablet the number of valid slots has to take into account the length of the tablet nonhead words cannot be placed before the head word so vacancies to the left of the head word are ignored vacancy difference for a head word vj vcenter of previous cept can be positive or negative for a nonhead word vj vposition of previously placed word always positive because successive words in a tablet are assumed to appear to the right of the previous word positioning of target words fall under three cases 1 words generated by null are distributed uniformly 2 for a head word t its position is modeled by the probability vheaddv maxv wordclasstt 3 for a nonhead word t its position is modeled by the probability vnonheaddv maxv wordclasstt dv and maxv are defined differently for head and nonhead words the em algorithm used in model 5 is e step in the training data collect counts weighted by prior probabilities a count how many times a source language word is translated into a target language word b for a particular word class and maximum vacancy count how many times a head word and the previous cept s center have a particular difference in number of vacancies b for a particular word class and maximum vacancy count how many times a nonhead word and the previous target word have a particular difference in number of vacancies d count how many times a source word is aligned to phi number of target words e count how many times null is aligned to a target word m step estimate new probabilities based on the counts from the e step like model 4 there are too many possible alignments to consider thus a hill climbing approach is used to sample good candidates in addition pruning is used to weed out unlikely alignments based on model 4 scores notations i position in the source sentence valid values are 0 for null 1 2 length of source sentence j position in the target sentence valid values are 1 2 length of target sentence l number of words in the source sentence excluding null m number of words in the target sentence s a word in the source language t a word in the target language phi fertility the number of target words produced by a source word p1 probability that a target word produced by a source word is accompanied by another target word that is aligned to null p0 1 p1 maxv maximum vacancy dv vacancy difference v the definition of vhead here differs from giza section 4 7 of brown et al 1993 and koehn 2010 in the latter cases vhead is vheadvj vcenter of previous cept maxv wordclasst here we follow appendix b of brown et al 1993 and combine vj with vcenter of previous cept to obtain dv vheadvj vcenter of previous cept maxv wordclasst references philipp koehn 2010 statistical machine translation cambridge university press new york peter e brown stephen a della pietra vincent j della pietra and robert l mercer 1993 the mathematics of statistical machine translation parameter estimation computational linguistics 19 2 263311 translation model that keeps track of vacant positions in the target sentence to decide where to place translated words bitext bitext appendalignedsent klein ist das haus the house is small bitext appendalignedsent das haus war ja gro the house was big bitext appendalignedsent das buch ist ja klein the book is small bitext appendalignedsent ein haus ist klein a house is small bitext appendalignedsent das haus the house bitext appendalignedsent das buch the book bitext appendalignedsent ein buch a book bitext appendalignedsent ich fasse das buch zusammen i summarize the book bitext appendalignedsent fasse zusammen summarize srcclasses the 0 a 0 small 1 big 1 house 2 book 2 is 3 was 3 i 4 summarize 5 trgclasses das 0 ein 0 haus 1 buch 1 klein 2 gro 2 ist 3 war 3 ja 4 ich 5 fasse 6 zusammen 6 ibm5 ibmmodel5bitext 5 srcclasses trgclasses printroundibm5 headvacancytable111 3 1 0 printroundibm5 headvacancytable211 3 0 0 printroundibm5 nonheadvacancytable336 3 1 0 printroundibm5 fertilitytable2 summarize 3 1 0 printroundibm5 fertilitytable1 book 3 1 0 printroundibm5 p1 3 0 033 testsentence bitext2 testsentence words das buch ist ja klein testsentence mots the book is small testsentence alignment alignment0 0 1 1 2 2 3 none 4 3 alignments with scores below this factor are pruned during sampling train on sentencealignedcorpus and create a lexical translation model vacancy models a fertility model and a model for generating nullaligned words translation direction is from alignedsent mots to alignedsent words param sentencealignedcorpus sentencealigned parallel corpus type sentencealignedcorpus listalignedsent param iterations number of iterations to run training algorithm type iterations int param sourcewordclasses lookup table that maps a source word to its word class the latter represented by an integer id type sourcewordclasses dictstr int param targetwordclasses lookup table that maps a target word to its word class the latter represented by an integer id type targetwordclasses dictstr int param probabilitytables optional use this to pass in custom probability values if not specified probabilities will be set to a uniform distribution or some other sensible value if specified all the following entries must be present translationtable alignmenttable fertilitytable p1 headdistortiontable nonheaddistortiontable headvacancytable nonheadvacancytable see ibmmodel ibmmodel4 and ibmmodel5 for the type and purpose of these tables type probabilitytables dictstr object get probabilities from ibm model 4 set userdefined probabilities dictintintint float probabilityvacancy difference number of remaining valid positions target word class values accessed as headvacancytabledvvmaxtrgclass dictintintint float probabilityvacancy difference number of remaining valid positions target word class values accessed as nonheadvacancytabledvvmaxtrgclass set vacancy probabilities uniformly to 1 cardinality of vacancy difference values the maximum vacancy difference occurs when a word is placed in the last available position m of the target sentence and the previous word position has no vacancies the minimum is 1maxv when a word is placed in the first available position and the previous word is placed beyond the last available position thus the number of possible vacancy difference values is maxv 1maxv 1 2 maxv sample the alignment space record the most probable alignment e step a compute normalization factors to weigh counts e step b collect counts m step update probabilities with maximum likelihood estimates if any probability is less than minprob clamp it to minprob sample the most probable alignments from the entire alignment space according to model 4 note that model 4 scoring is used instead of model 5 because the latter is too expensive to compute first determine the best alignment according to ibm model 2 with this initial alignment use hill climbing to determine the best alignment according to a ibm model 4 add this alignment and its neighbors to the sample set repeat this process with other initial alignments obtained by pegging an alignment point finally prune alignments that have substantially lower model 4 scores than the best alignment param sentencepair source and target language sentence pair to generate a sample of alignments from type sentencepair alignedsent return a set of best alignments represented by their alignmentinfo and the best alignment of the set for convenience rtype setalignmentinfo alignmentinfo removes alignments from alignmentinfos that have substantially lower model 4 scores than the best alignment return pruned alignments rtype setalignmentinfo starting from the alignment in alignmentinfo look at neighboring alignments iteratively for the best one according to model 4 note that model 4 scoring is used instead of model 5 because the latter is too expensive to compute there is no guarantee that the best alignment in the alignment space will be found because the algorithm might be stuck in a local maximum param jpegged if specified the search will be constrained to alignments where jpegged remains unchanged type jpegged int return the best alignment found from hill climbing rtype alignmentinfo until there are no better alignments probability of target sentence and an alignment given the source sentence binomial distribution bm nullfertility p1 combination m nullfertility choose nullfertility case 1 nullaligned words case 2 head word case 3 nonhead words end nested functions abort computation whenever probability falls below minprob at any point since minprob can be considered as zero data object to store counts of various parameters during training includes counts for vacancies param count value to add to the vacancy counts param alignmentinfo alignment under consideration param i source word position under consideration param trgclasses target word classes param slots vacancy states of the slots in the target sentence output parameter that will be modified as new words are placed in the target sentence case 1 null aligned words case 2 head word case 3 nonhead words represents positions in a target sentence used to keep track of which slot position is occupied return mark slot at position as occupied return number of vacant slots up to and including position natural language toolkit ibm model 5 c 2001 2023 nltk project tah wei hoon hoon tw gmail com url https www nltk org for license information see license txt translation model that keeps track of vacant positions in the target sentence to decide where to place translated words translation can be viewed as a process where each word in the source sentence is stepped through sequentially generating translated words for each source word the target sentence can be viewed as being made up of m empty slots initially which gradually fill up as generated words are placed in them models 3 and 4 use distortion probabilities to decide how to place translated words for simplicity these models ignore the history of which slots have already been occupied with translated words consider the placement of the last translated word there is only one empty slot left in the target sentence so the distortion probability should be 1 0 for that position and 0 0 everywhere else however the distortion probabilities for models 3 and 4 are set up such that all positions are under consideration ibm model 5 fixes this deficiency by accounting for occupied slots during translation it introduces the vacancy function v j the number of vacancies up to and including position j in the target sentence terminology maximum vacancy the number of valid slots that a word can be placed in this is not necessarily the same as the number of vacant slots for example if a tablet contains more than one word the head word cannot be placed at the last vacant slot because there will be no space for the other words in the tablet the number of valid slots has to take into account the length of the tablet non head words cannot be placed before the head word so vacancies to the left of the head word are ignored vacancy difference for a head word v j v center of previous cept can be positive or negative for a non head word v j v position of previously placed word always positive because successive words in a tablet are assumed to appear to the right of the previous word positioning of target words fall under three cases 1 words generated by null are distributed uniformly 2 for a head word t its position is modeled by the probability v_head dv max_v word_class_t t 3 for a non head word t its position is modeled by the probability v_non_head dv max_v word_class_t t dv and max_v are defined differently for head and non head words the em algorithm used in model 5 is e step in the training data collect counts weighted by prior probabilities a count how many times a source language word is translated into a target language word b for a particular word class and maximum vacancy count how many times a head word and the previous cept s center have a particular difference in number of vacancies b for a particular word class and maximum vacancy count how many times a non head word and the previous target word have a particular difference in number of vacancies d count how many times a source word is aligned to phi number of target words e count how many times null is aligned to a target word m step estimate new probabilities based on the counts from the e step like model 4 there are too many possible alignments to consider thus a hill climbing approach is used to sample good candidates in addition pruning is used to weed out unlikely alignments based on model 4 scores notations i position in the source sentence valid values are 0 for null 1 2 length of source sentence j position in the target sentence valid values are 1 2 length of target sentence l number of words in the source sentence excluding null m number of words in the target sentence s a word in the source language t a word in the target language phi fertility the number of target words produced by a source word p1 probability that a target word produced by a source word is accompanied by another target word that is aligned to null p0 1 p1 max_v maximum vacancy dv vacancy difference δv the definition of v_head here differs from giza section 4 7 of brown et al 1993 and koehn 2010 in the latter cases v_head is v_head v j v center of previous cept max_v word_class t here we follow appendix b of brown et al 1993 and combine v j with v center of previous cept to obtain dv v_head v j v center of previous cept max_v word_class t references philipp koehn 2010 statistical machine translation cambridge university press new york peter e brown stephen a della pietra vincent j della pietra and robert l mercer 1993 the mathematics of statistical machine translation parameter estimation computational linguistics 19 2 263 311 translation model that keeps track of vacant positions in the target sentence to decide where to place translated words bitext bitext append alignedsent klein ist das haus the house is small bitext append alignedsent das haus war ja groß the house was big bitext append alignedsent das buch ist ja klein the book is small bitext append alignedsent ein haus ist klein a house is small bitext append alignedsent das haus the house bitext append alignedsent das buch the book bitext append alignedsent ein buch a book bitext append alignedsent ich fasse das buch zusammen i summarize the book bitext append alignedsent fasse zusammen summarize src_classes the 0 a 0 small 1 big 1 house 2 book 2 is 3 was 3 i 4 summarize 5 trg_classes das 0 ein 0 haus 1 buch 1 klein 2 groß 2 ist 3 war 3 ja 4 ich 5 fasse 6 zusammen 6 ibm5 ibmmodel5 bitext 5 src_classes trg_classes print round ibm5 head_vacancy_table 1 1 1 3 1 0 print round ibm5 head_vacancy_table 2 1 1 3 0 0 print round ibm5 non_head_vacancy_table 3 3 6 3 1 0 print round ibm5 fertility_table 2 summarize 3 1 0 print round ibm5 fertility_table 1 book 3 1 0 print round ibm5 p1 3 0 033 test_sentence bitext 2 test_sentence words das buch ist ja klein test_sentence mots the book is small test_sentence alignment alignment 0 0 1 1 2 2 3 none 4 3 alignments with scores below this factor are pruned during sampling train on sentence_aligned_corpus and create a lexical translation model vacancy models a fertility model and a model for generating null aligned words translation direction is from alignedsent mots to alignedsent words param sentence_aligned_corpus sentence aligned parallel corpus type sentence_aligned_corpus list alignedsent param iterations number of iterations to run training algorithm type iterations int param source_word_classes lookup table that maps a source word to its word class the latter represented by an integer id type source_word_classes dict str int param target_word_classes lookup table that maps a target word to its word class the latter represented by an integer id type target_word_classes dict str int param probability_tables optional use this to pass in custom probability values if not specified probabilities will be set to a uniform distribution or some other sensible value if specified all the following entries must be present translation_table alignment_table fertility_table p1 head_distortion_table non_head_distortion_table head_vacancy_table non_head_vacancy_table see ibmmodel ibmmodel4 and ibmmodel5 for the type and purpose of these tables type probability_tables dict str object get probabilities from ibm model 4 set user defined probabilities dict int int int float probability vacancy difference number of remaining valid positions target word class values accessed as head_vacancy_table dv v_max trg_class dict int int int float probability vacancy difference number of remaining valid positions target word class values accessed as non_head_vacancy_table dv v_max trg_class set vacancy probabilities uniformly to 1 cardinality of vacancy difference values the maximum vacancy difference occurs when a word is placed in the last available position m of the target sentence and the previous word position has no vacancies the minimum is 1 max_v when a word is placed in the first available position and the previous word is placed beyond the last available position thus the number of possible vacancy difference values is max_v 1 max_v 1 2 max_v sample the alignment space record the most probable alignment e step a compute normalization factors to weigh counts e step b collect counts m step update probabilities with maximum likelihood estimates if any probability is less than min_prob clamp it to min_prob don t retrain sample the most probable alignments from the entire alignment space according to model 4 note that model 4 scoring is used instead of model 5 because the latter is too expensive to compute first determine the best alignment according to ibm model 2 with this initial alignment use hill climbing to determine the best alignment according to a ibm model 4 add this alignment and its neighbors to the sample set repeat this process with other initial alignments obtained by pegging an alignment point finally prune alignments that have substantially lower model 4 scores than the best alignment param sentence_pair source and target language sentence pair to generate a sample of alignments from type sentence_pair alignedsent return a set of best alignments represented by their alignmentinfo and the best alignment of the set for convenience rtype set alignmentinfo alignmentinfo removes alignments from alignment_infos that have substantially lower model 4 scores than the best alignment return pruned alignments rtype set alignmentinfo starting from the alignment in alignment_info look at neighboring alignments iteratively for the best one according to model 4 note that model 4 scoring is used instead of model 5 because the latter is too expensive to compute there is no guarantee that the best alignment in the alignment space will be found because the algorithm might be stuck in a local maximum param j_pegged if specified the search will be constrained to alignments where j_pegged remains unchanged type j_pegged int return the best alignment found from hill climbing rtype alignmentinfo alias with shorter name until there are no better alignments probability of target sentence and an alignment given the source sentence binomial distribution b m null_fertility p1 combination m null_fertility choose null_fertility case 1 null aligned words case 2 head word mark position as occupied case 3 non head words mark position as occupied end nested functions abort computation whenever probability falls below min_prob at any point since min_prob can be considered as zero data object to store counts of various parameters during training includes counts for vacancies param count value to add to the vacancy counts param alignment_info alignment under consideration param i source word position under consideration param trg_classes target word classes param slots vacancy states of the slots in the target sentence output parameter that will be modified as new words are placed in the target sentence case 1 null aligned words ignore zero fertility words case 2 head word mark position as occupied case 3 non head words mark position as occupied represents positions in a target sentence used to keep track of which slot position is occupied 1 indexed return mark slot at position as occupied return number of vacant slots up to and including position exclude dummy zeroeth element
import warnings
from collections import defaultdict
from math import factorial

from nltk.translate import AlignedSent, Alignment, IBMModel, IBMModel4
from nltk.translate.ibm_model import Counts, longest_target_sentence_length


class IBMModel5(IBMModel):
    

    MIN_SCORE_FACTOR = 0.2
    

    def __init__(
        self,
        sentence_aligned_corpus,
        iterations,
        source_word_classes,
        target_word_classes,
        probability_tables=None,
    ):
        
        super().__init__(sentence_aligned_corpus)
        self.reset_probabilities()
        self.src_classes = source_word_classes
        self.trg_classes = target_word_classes

        if probability_tables is None:
            
            ibm4 = IBMModel4(
                sentence_aligned_corpus,
                iterations,
                source_word_classes,
                target_word_classes,
            )
            self.translation_table = ibm4.translation_table
            self.alignment_table = ibm4.alignment_table
            self.fertility_table = ibm4.fertility_table
            self.p1 = ibm4.p1
            self.head_distortion_table = ibm4.head_distortion_table
            self.non_head_distortion_table = ibm4.non_head_distortion_table
            self.set_uniform_probabilities(sentence_aligned_corpus)
        else:
            
            self.translation_table = probability_tables["translation_table"]
            self.alignment_table = probability_tables["alignment_table"]
            self.fertility_table = probability_tables["fertility_table"]
            self.p1 = probability_tables["p1"]
            self.head_distortion_table = probability_tables["head_distortion_table"]
            self.non_head_distortion_table = probability_tables[
                "non_head_distortion_table"
            ]
            self.head_vacancy_table = probability_tables["head_vacancy_table"]
            self.non_head_vacancy_table = probability_tables["non_head_vacancy_table"]

        for n in range(0, iterations):
            self.train(sentence_aligned_corpus)

    def reset_probabilities(self):
        super().reset_probabilities()
        self.head_vacancy_table = defaultdict(
            lambda: defaultdict(lambda: defaultdict(lambda: self.MIN_PROB))
        )
        

        self.non_head_vacancy_table = defaultdict(
            lambda: defaultdict(lambda: defaultdict(lambda: self.MIN_PROB))
        )
        

    def set_uniform_probabilities(self, sentence_aligned_corpus):
        
        max_m = longest_target_sentence_length(sentence_aligned_corpus)

        
        
        
        
        
        
        
        
        if max_m > 0 and (1 / (2 * max_m)) < IBMModel.MIN_PROB:
            warnings.warn(
                "A target sentence is too long ("
                + str(max_m)
                + " words). Results may be less accurate."
            )

        for max_v in range(1, max_m + 1):
            for dv in range(1, max_m + 1):
                initial_prob = 1 / (2 * max_v)
                self.head_vacancy_table[dv][max_v] = defaultdict(lambda: initial_prob)
                self.head_vacancy_table[-(dv - 1)][max_v] = defaultdict(
                    lambda: initial_prob
                )
                self.non_head_vacancy_table[dv][max_v] = defaultdict(
                    lambda: initial_prob
                )
                self.non_head_vacancy_table[-(dv - 1)][max_v] = defaultdict(
                    lambda: initial_prob
                )

    def train(self, parallel_corpus):
        counts = Model5Counts()
        for aligned_sentence in parallel_corpus:
            l = len(aligned_sentence.mots)
            m = len(aligned_sentence.words)

            
            sampled_alignments, best_alignment = self.sample(aligned_sentence)
            
            aligned_sentence.alignment = Alignment(
                best_alignment.zero_indexed_alignment()
            )

            
            total_count = self.prob_of_alignments(sampled_alignments)

            
            for alignment_info in sampled_alignments:
                count = self.prob_t_a_given_s(alignment_info)
                normalized_count = count / total_count

                for j in range(1, m + 1):
                    counts.update_lexical_translation(
                        normalized_count, alignment_info, j
                    )

                slots = Slots(m)
                for i in range(1, l + 1):
                    counts.update_vacancy(
                        normalized_count, alignment_info, i, self.trg_classes, slots
                    )

                counts.update_null_generation(normalized_count, alignment_info)
                counts.update_fertility(normalized_count, alignment_info)

        
        
        existing_alignment_table = self.alignment_table
        self.reset_probabilities()
        self.alignment_table = existing_alignment_table  

        self.maximize_lexical_translation_probabilities(counts)
        self.maximize_vacancy_probabilities(counts)
        self.maximize_fertility_probabilities(counts)
        self.maximize_null_generation_probabilities(counts)

    def sample(self, sentence_pair):
        
        sampled_alignments, best_alignment = super().sample(sentence_pair)
        return self.prune(sampled_alignments), best_alignment

    def prune(self, alignment_infos):
        
        alignments = []
        best_score = 0

        for alignment_info in alignment_infos:
            score = IBMModel4.model4_prob_t_a_given_s(alignment_info, self)
            best_score = max(score, best_score)
            alignments.append((alignment_info, score))

        threshold = IBMModel5.MIN_SCORE_FACTOR * best_score
        alignments = [a[0] for a in alignments if a[1] > threshold]
        return set(alignments)

    def hillclimb(self, alignment_info, j_pegged=None):
        
        alignment = alignment_info  
        max_probability = IBMModel4.model4_prob_t_a_given_s(alignment, self)

        while True:
            old_alignment = alignment
            for neighbor_alignment in self.neighboring(alignment, j_pegged):
                neighbor_probability = IBMModel4.model4_prob_t_a_given_s(
                    neighbor_alignment, self
                )

                if neighbor_probability > max_probability:
                    alignment = neighbor_alignment
                    max_probability = neighbor_probability

            if alignment == old_alignment:
                
                break

        alignment.score = max_probability
        return alignment

    def prob_t_a_given_s(self, alignment_info):
        
        probability = 1.0
        MIN_PROB = IBMModel.MIN_PROB
        slots = Slots(len(alignment_info.trg_sentence) - 1)

        def null_generation_term():
            
            value = 1.0
            p1 = self.p1
            p0 = 1 - p1
            null_fertility = alignment_info.fertility_of_i(0)
            m = len(alignment_info.trg_sentence) - 1
            value *= pow(p1, null_fertility) * pow(p0, m - 2 * null_fertility)
            if value < MIN_PROB:
                return MIN_PROB

            
            for i in range(1, null_fertility + 1):
                value *= (m - null_fertility - i + 1) / i
            return value

        def fertility_term():
            value = 1.0
            src_sentence = alignment_info.src_sentence
            for i in range(1, len(src_sentence)):
                fertility = alignment_info.fertility_of_i(i)
                value *= (
                    factorial(fertility)
                    * self.fertility_table[fertility][src_sentence[i]]
                )
                if value < MIN_PROB:
                    return MIN_PROB
            return value

        def lexical_translation_term(j):
            t = alignment_info.trg_sentence[j]
            i = alignment_info.alignment[j]
            s = alignment_info.src_sentence[i]
            return self.translation_table[t][s]

        def vacancy_term(i):
            value = 1.0
            tablet = alignment_info.cepts[i]
            tablet_length = len(tablet)
            total_vacancies = slots.vacancies_at(len(slots))

            
            if tablet_length == 0:
                return value

            
            j = tablet[0]
            previous_cept = alignment_info.previous_cept(j)
            previous_center = alignment_info.center_of_cept(previous_cept)
            dv = slots.vacancies_at(j) - slots.vacancies_at(previous_center)
            max_v = total_vacancies - tablet_length + 1
            trg_class = self.trg_classes[alignment_info.trg_sentence[j]]
            value *= self.head_vacancy_table[dv][max_v][trg_class]
            slots.occupy(j)  
            total_vacancies -= 1
            if value < MIN_PROB:
                return MIN_PROB

            
            for k in range(1, tablet_length):
                previous_position = tablet[k - 1]
                previous_vacancies = slots.vacancies_at(previous_position)
                j = tablet[k]
                dv = slots.vacancies_at(j) - previous_vacancies
                max_v = total_vacancies - tablet_length + k + 1 - previous_vacancies
                trg_class = self.trg_classes[alignment_info.trg_sentence[j]]
                value *= self.non_head_vacancy_table[dv][max_v][trg_class]
                slots.occupy(j)  
                total_vacancies -= 1
                if value < MIN_PROB:
                    return MIN_PROB

            return value

        

        
        
        probability *= null_generation_term()
        if probability < MIN_PROB:
            return MIN_PROB

        probability *= fertility_term()
        if probability < MIN_PROB:
            return MIN_PROB

        for j in range(1, len(alignment_info.trg_sentence)):
            probability *= lexical_translation_term(j)
            if probability < MIN_PROB:
                return MIN_PROB

        for i in range(1, len(alignment_info.src_sentence)):
            probability *= vacancy_term(i)
            if probability < MIN_PROB:
                return MIN_PROB

        return probability

    def maximize_vacancy_probabilities(self, counts):
        MIN_PROB = IBMModel.MIN_PROB
        head_vacancy_table = self.head_vacancy_table
        for dv, max_vs in counts.head_vacancy.items():
            for max_v, trg_classes in max_vs.items():
                for t_cls in trg_classes:
                    estimate = (
                        counts.head_vacancy[dv][max_v][t_cls]
                        / counts.head_vacancy_for_any_dv[max_v][t_cls]
                    )
                    head_vacancy_table[dv][max_v][t_cls] = max(estimate, MIN_PROB)

        non_head_vacancy_table = self.non_head_vacancy_table
        for dv, max_vs in counts.non_head_vacancy.items():
            for max_v, trg_classes in max_vs.items():
                for t_cls in trg_classes:
                    estimate = (
                        counts.non_head_vacancy[dv][max_v][t_cls]
                        / counts.non_head_vacancy_for_any_dv[max_v][t_cls]
                    )
                    non_head_vacancy_table[dv][max_v][t_cls] = max(estimate, MIN_PROB)


class Model5Counts(Counts):
    

    def __init__(self):
        super().__init__()
        self.head_vacancy = defaultdict(
            lambda: defaultdict(lambda: defaultdict(lambda: 0.0))
        )
        self.head_vacancy_for_any_dv = defaultdict(lambda: defaultdict(lambda: 0.0))
        self.non_head_vacancy = defaultdict(
            lambda: defaultdict(lambda: defaultdict(lambda: 0.0))
        )
        self.non_head_vacancy_for_any_dv = defaultdict(lambda: defaultdict(lambda: 0.0))

    def update_vacancy(self, count, alignment_info, i, trg_classes, slots):
        
        tablet = alignment_info.cepts[i]
        tablet_length = len(tablet)
        total_vacancies = slots.vacancies_at(len(slots))

        
        if tablet_length == 0:
            return  

        
        j = tablet[0]
        previous_cept = alignment_info.previous_cept(j)
        previous_center = alignment_info.center_of_cept(previous_cept)
        dv = slots.vacancies_at(j) - slots.vacancies_at(previous_center)
        max_v = total_vacancies - tablet_length + 1
        trg_class = trg_classes[alignment_info.trg_sentence[j]]
        self.head_vacancy[dv][max_v][trg_class] += count
        self.head_vacancy_for_any_dv[max_v][trg_class] += count
        slots.occupy(j)  
        total_vacancies -= 1

        
        for k in range(1, tablet_length):
            previous_position = tablet[k - 1]
            previous_vacancies = slots.vacancies_at(previous_position)
            j = tablet[k]
            dv = slots.vacancies_at(j) - previous_vacancies
            max_v = total_vacancies - tablet_length + k + 1 - previous_vacancies
            trg_class = trg_classes[alignment_info.trg_sentence[j]]
            self.non_head_vacancy[dv][max_v][trg_class] += count
            self.non_head_vacancy_for_any_dv[max_v][trg_class] += count
            slots.occupy(j)  
            total_vacancies -= 1


class Slots:
    

    def __init__(self, target_sentence_length):
        self._slots = [False] * (target_sentence_length + 1)  

    def occupy(self, position):
        
        self._slots[position] = True

    def vacancies_at(self, position):
        
        vacancies = 0
        for k in range(1, position + 1):
            if not self._slots[k]:
                vacancies += 1
        return vacancies

    def __len__(self):
        return len(self._slots) - 1