natural language toolkit stack decoder c 20012023 nltk project tah wei hoon hoon twgmail com url https www nltk org for license information see license txt a decoder that uses stacks to implement phrasebased translation in phrasebased translation the source sentence is segmented into phrases of one or more words and translations for those phrases are used to build the target sentence hypothesis data structures are used to keep track of the source words translated so far and the partial output a hypothesis can be expanded by selecting an untranslated phrase looking up its translation in a phrase table and appending that translation to the partial output translation is complete when a hypothesis covers all source words the search space is huge because the source sentence can be segmented in different ways the source phrases can be selected in any order and there could be multiple translations for the same source phrase in the phrase table to make decoding tractable stacks are used to limit the number of candidate hypotheses by doing histogram andor threshold pruning hypotheses with the same number of words translated are placed in the same stack in histogram pruning each stack has a size limit and the hypothesis with the lowest score is removed when the stack is full in threshold pruning hypotheses that score below a certain threshold of the best hypothesis in that stack are removed hypothesis scoring can include various factors such as phrase translation probability language model probability length of translation cost of remaining words to be translated and so on references philipp koehn 2010 statistical machine translation cambridge university press new york phrasebased stack decoder for machine translation from nltk translate import phrasetable phrasetable phrasetable phrasetable add niemand nobody log0 8 phrasetable add niemand no one log0 2 phrasetable add erwartet expects log0 8 phrasetable add erwartet expecting log0 2 phrasetable add niemand erwartet one does not expect log0 1 phrasetable add die spanische inquisition the spanish inquisition log0 8 phrasetable add log0 8 nltk model should be used here once it is implemented from collections import defaultdict languageprob defaultdictlambda 999 0 languageprob nobody log0 5 languageprob expects log0 4 languageprob the spanish inquisition log0 2 languageprob log0 1 languagemodel type object probabilitychange lambda self context phrase languageprobphrase probability lambda self phrase languageprobphrase stackdecoder stackdecoderphrasetable languagemodel stackdecoder translate niemand erwartet die spanische inquisition nobody expects the spanish inquisition param phrasetable table of translations for source language phrases and the log probabilities for those translations type phrasetable phrasetable param languagemodel target language model must define a probabilitychange method that calculates the change in log probability of a sentence if a given string is appended to it this interface is experimental and will likely be replaced with nltk model once it is implemented type languagemodel object float influences the translation length exponentially if positive shorter translations are preferred if negative longer translations are preferred if zero no penalty is applied float hypotheses that score below this factor of the best hypothesis in a stack are dropped from consideration value between 0 0 and 1 0 int maximum number of hypotheses to consider in a stack higher values increase the likelihood of a good translation but increases processing time float amount of reordering of source phrases lower values favour monotone translation suitable when word order is similar for both source and target languages value between 0 0 and 1 0 default 0 5 cache logdistortionfactor so we don t have to recompute it when scoring hypotheses param srcsentence sentence to be translated type srcsentence liststr return translated sentence rtype liststr instead of returning empty output perhaps a partial translation could be returned finds all subsequences in srcsentence that have a phrase translation in the translation table type srcsentence tuplestr return subsequences that have a phrase translation represented as a table of lists of end positions for example if result2 is 5 6 9 then there are three phrases starting from position 2 in srcsentence ending at positions 5 6 and 9 exclusive the list of ending positions are in ascending order rtype listlistint determines the approximate scores for translating every subsequence in srcsentence future scores can be used a lookahead to determine the difficulty of translating the remaining parts of a srcsentence type srcsentence tuplestr return scores of subsequences referenced by their start and end positions for example result25 is the score of the subsequence covering positions 2 3 and 4 rtype dictint dictint float warning api of languagemodel is subject to change check if a better score can be obtained by combining two child subsequences determines the approximate score for translating the untranslated words in hypothesis calculate the score of expanding hypothesis with translationoption param hypothesis hypothesis being expanded type hypothesis hypothesis param translationoption information about the proposed expansion type translationoption phrasetableentry param srcphrasespan word position span of the source phrase type srcphrasespan tupleint int the api of languagemodel is subject to change it could accept a string a list of words andor some other type extract phrases from allphrasesfrom that contains words that have not been translated by hypothesis param allphrasesfrom phrases represented by their spans in the same format as the return value of findallsrcphrases type allphrasesfrom listlistint type hypothesis hypothesis return a list of phrases represented by their spans that cover untranslated positions rtype listtupleint int subsequent elements in allphrasesfromstart will also be availableend since the elements are in ascending order partial solution to a translation records the word positions of the phrase being translated its translation raw score and the cost of the untranslated parts of the sentence when the next phrase is selected to build upon the partial solution a new hypothesis object is created with a back pointer to the previous hypothesis to find out which words have been translated so far look at the srcphrasespan in the hypothesis chain similarly the translation output can be found by traversing up the chain param rawscore likelihood of hypothesis so far higher is better does not account for untranslated words type rawscore float param srcphrasespan span of word positions covered by the source phrase in this hypothesis expansion for example 2 5 means that the phrase is from the second word up to but not including the fifth word in the source sentence type srcphrasespan tupleint param trgphrase translation of the source phrase in this hypothesis expansion type trgphrase tuplestr param previous previous hypothesis before expansion to this one type previous hypothesis param futurescore approximate score for translating the remaining words not covered by this hypothesis higher means that the remaining words are easier to translate type futurescore float overall score of hypothesis after accounting for local and global features starting from each untranslated word find the longest continuous span of untranslated positions param sentencelength length of source sentence being translated by the hypothesis type sentencelength int rtype listtupleint int each untranslated span must end in one of the translatedpositions list of positions in the source sentence of words already translated the list is not sorted rtype listint collection of hypothesis objects param beamthreshold hypotheses that score less than this factor of the best hypothesis are discarded from the stack value must be between 0 0 and 1 0 type beamthreshold float add hypothesis to the stack removes lowest scoring hypothesis if the stack is full after insertion hypotheses that score less than beamthreshold times the score of the best hypothesis are removed logscore beamthreshold logscore logbeamthreshold return hypothesis with the highest score in the stack rtype hypothesis natural language toolkit stack decoder c 2001 2023 nltk project tah wei hoon hoon tw gmail com url https www nltk org for license information see license txt a decoder that uses stacks to implement phrase based translation in phrase based translation the source sentence is segmented into phrases of one or more words and translations for those phrases are used to build the target sentence hypothesis data structures are used to keep track of the source words translated so far and the partial output a hypothesis can be expanded by selecting an untranslated phrase looking up its translation in a phrase table and appending that translation to the partial output translation is complete when a hypothesis covers all source words the search space is huge because the source sentence can be segmented in different ways the source phrases can be selected in any order and there could be multiple translations for the same source phrase in the phrase table to make decoding tractable stacks are used to limit the number of candidate hypotheses by doing histogram and or threshold pruning hypotheses with the same number of words translated are placed in the same stack in histogram pruning each stack has a size limit and the hypothesis with the lowest score is removed when the stack is full in threshold pruning hypotheses that score below a certain threshold of the best hypothesis in that stack are removed hypothesis scoring can include various factors such as phrase translation probability language model probability length of translation cost of remaining words to be translated and so on references philipp koehn 2010 statistical machine translation cambridge university press new york phrase based stack decoder for machine translation from nltk translate import phrasetable phrase_table phrasetable phrase_table add niemand nobody log 0 8 phrase_table add niemand no one log 0 2 phrase_table add erwartet expects log 0 8 phrase_table add erwartet expecting log 0 2 phrase_table add niemand erwartet one does not expect log 0 1 phrase_table add die spanische inquisition the spanish inquisition log 0 8 phrase_table add log 0 8 nltk model should be used here once it is implemented from collections import defaultdict language_prob defaultdict lambda 999 0 language_prob nobody log 0 5 language_prob expects log 0 4 language_prob the spanish inquisition log 0 2 language_prob log 0 1 language_model type object probability_change lambda self context phrase language_prob phrase probability lambda self phrase language_prob phrase stack_decoder stackdecoder phrase_table language_model stack_decoder translate niemand erwartet die spanische inquisition nobody expects the spanish inquisition param phrase_table table of translations for source language phrases and the log probabilities for those translations type phrase_table phrasetable param language_model target language model must define a probability_change method that calculates the change in log probability of a sentence if a given string is appended to it this interface is experimental and will likely be replaced with nltk model once it is implemented type language_model object float influences the translation length exponentially if positive shorter translations are preferred if negative longer translations are preferred if zero no penalty is applied float hypotheses that score below this factor of the best hypothesis in a stack are dropped from consideration value between 0 0 and 1 0 int maximum number of hypotheses to consider in a stack higher values increase the likelihood of a good translation but increases processing time float amount of reordering of source phrases lower values favour monotone translation suitable when word order is similar for both source and target languages value between 0 0 and 1 0 default 0 5 cache log distortion_factor so we don t have to recompute it when scoring hypotheses 1e 9 is almost zero param src_sentence sentence to be translated type src_sentence list str return translated sentence rtype list str prevent accidental modification instead of returning empty output perhaps a partial translation could be returned finds all subsequences in src_sentence that have a phrase translation in the translation table type src_sentence tuple str return subsequences that have a phrase translation represented as a table of lists of end positions for example if result 2 is 5 6 9 then there are three phrases starting from position 2 in src_sentence ending at positions 5 6 and 9 exclusive the list of ending positions are in ascending order rtype list list int determines the approximate scores for translating every subsequence in src_sentence future scores can be used a look ahead to determine the difficulty of translating the remaining parts of a src_sentence type src_sentence tuple str return scores of subsequences referenced by their start and end positions for example result 2 5 is the score of the subsequence covering positions 2 3 and 4 rtype dict int dict int float pick best first translation warning api of language_model is subject to change check if a better score can be obtained by combining two child subsequences determines the approximate score for translating the untranslated words in hypothesis calculate the score of expanding hypothesis with translation_option param hypothesis hypothesis being expanded type hypothesis _hypothesis param translation_option information about the proposed expansion type translation_option phrasetableentry param src_phrase_span word position span of the source phrase type src_phrase_span tuple int int the api of language_model is subject to change it could accept a string a list of words and or some other type extract phrases from all_phrases_from that contains words that have not been translated by hypothesis param all_phrases_from phrases represented by their spans in the same format as the return value of find_all_src_phrases type all_phrases_from list list int type hypothesis _hypothesis return a list of phrases represented by their spans that cover untranslated positions rtype list tuple int int subsequent elements in all_phrases_from start will also be available_end since the elements are in ascending order partial solution to a translation records the word positions of the phrase being translated its translation raw score and the cost of the untranslated parts of the sentence when the next phrase is selected to build upon the partial solution a new _hypothesis object is created with a back pointer to the previous hypothesis to find out which words have been translated so far look at the src_phrase_span in the hypothesis chain similarly the translation output can be found by traversing up the chain param raw_score likelihood of hypothesis so far higher is better does not account for untranslated words type raw_score float param src_phrase_span span of word positions covered by the source phrase in this hypothesis expansion for example 2 5 means that the phrase is from the second word up to but not including the fifth word in the source sentence type src_phrase_span tuple int param trg_phrase translation of the source phrase in this hypothesis expansion type trg_phrase tuple str param previous previous hypothesis before expansion to this one type previous _hypothesis param future_score approximate score for translating the remaining words not covered by this hypothesis higher means that the remaining words are easier to translate type future_score float overall score of hypothesis after accounting for local and global features starting from each untranslated word find the longest continuous span of untranslated positions param sentence_length length of source sentence being translated by the hypothesis type sentence_length int rtype list tuple int int add sentinel position each untranslated span must end in one of the translated_positions list of positions in the source sentence of words already translated the list is not sorted rtype list int collection of _hypothesis objects param beam_threshold hypotheses that score less than this factor of the best hypothesis are discarded from the stack value must be between 0 0 and 1 0 type beam_threshold float add hypothesis to the stack removes lowest scoring hypothesis if the stack is full after insertion hypotheses that score less than beam_threshold times the score of the best hypothesis are removed log score beam_threshold log score log beam_threshold return hypothesis with the highest score in the stack rtype _hypothesis
import warnings
from collections import defaultdict
from math import log


class StackDecoder:
    

    def __init__(self, phrase_table, language_model):
        
        self.phrase_table = phrase_table
        self.language_model = language_model

        self.word_penalty = 0.0
        

        self.beam_threshold = 0.0
        

        self.stack_size = 100
        

        self.__distortion_factor = 0.5
        self.__compute_log_distortion()

    @property
    def distortion_factor(self):
        
        return self.__distortion_factor

    @distortion_factor.setter
    def distortion_factor(self, d):
        self.__distortion_factor = d
        self.__compute_log_distortion()

    def __compute_log_distortion(self):
        
        
        if self.__distortion_factor == 0.0:
            self.__log_distortion_factor = log(1e-9)  
        else:
            self.__log_distortion_factor = log(self.__distortion_factor)

    def translate(self, src_sentence):
        
        sentence = tuple(src_sentence)  
        sentence_length = len(sentence)
        stacks = [
            _Stack(self.stack_size, self.beam_threshold)
            for _ in range(0, sentence_length + 1)
        ]
        empty_hypothesis = _Hypothesis()
        stacks[0].push(empty_hypothesis)

        all_phrases = self.find_all_src_phrases(sentence)
        future_score_table = self.compute_future_scores(sentence)
        for stack in stacks:
            for hypothesis in stack:
                possible_expansions = StackDecoder.valid_phrases(
                    all_phrases, hypothesis
                )
                for src_phrase_span in possible_expansions:
                    src_phrase = sentence[src_phrase_span[0] : src_phrase_span[1]]
                    for translation_option in self.phrase_table.translations_for(
                        src_phrase
                    ):
                        raw_score = self.expansion_score(
                            hypothesis, translation_option, src_phrase_span
                        )
                        new_hypothesis = _Hypothesis(
                            raw_score=raw_score,
                            src_phrase_span=src_phrase_span,
                            trg_phrase=translation_option.trg_phrase,
                            previous=hypothesis,
                        )
                        new_hypothesis.future_score = self.future_score(
                            new_hypothesis, future_score_table, sentence_length
                        )
                        total_words = new_hypothesis.total_translated_words()
                        stacks[total_words].push(new_hypothesis)

        if not stacks[sentence_length]:
            warnings.warn(
                "Unable to translate all words. "
                "The source sentence contains words not in "
                "the phrase table"
            )
            
            
            return []

        best_hypothesis = stacks[sentence_length].best()
        return best_hypothesis.translation_so_far()

    def find_all_src_phrases(self, src_sentence):
        
        sentence_length = len(src_sentence)
        phrase_indices = [[] for _ in src_sentence]
        for start in range(0, sentence_length):
            for end in range(start + 1, sentence_length + 1):
                potential_phrase = src_sentence[start:end]
                if potential_phrase in self.phrase_table:
                    phrase_indices[start].append(end)
        return phrase_indices

    def compute_future_scores(self, src_sentence):
        
        scores = defaultdict(lambda: defaultdict(lambda: float("-inf")))
        for seq_length in range(1, len(src_sentence) + 1):
            for start in range(0, len(src_sentence) - seq_length + 1):
                end = start + seq_length
                phrase = src_sentence[start:end]
                if phrase in self.phrase_table:
                    score = self.phrase_table.translations_for(phrase)[
                        0
                    ].log_prob  
                    
                    score += self.language_model.probability(phrase)
                    scores[start][end] = score

                
                
                for mid in range(start + 1, end):
                    combined_score = scores[start][mid] + scores[mid][end]
                    if combined_score > scores[start][end]:
                        scores[start][end] = combined_score
        return scores

    def future_score(self, hypothesis, future_score_table, sentence_length):
        
        score = 0.0
        for span in hypothesis.untranslated_spans(sentence_length):
            score += future_score_table[span[0]][span[1]]
        return score

    def expansion_score(self, hypothesis, translation_option, src_phrase_span):
        
        score = hypothesis.raw_score
        score += translation_option.log_prob
        
        
        score += self.language_model.probability_change(
            hypothesis, translation_option.trg_phrase
        )
        score += self.distortion_score(hypothesis, src_phrase_span)
        score -= self.word_penalty * len(translation_option.trg_phrase)
        return score

    def distortion_score(self, hypothesis, next_src_phrase_span):
        if not hypothesis.src_phrase_span:
            return 0.0
        next_src_phrase_start = next_src_phrase_span[0]
        prev_src_phrase_end = hypothesis.src_phrase_span[1]
        distortion_distance = next_src_phrase_start - prev_src_phrase_end
        return abs(distortion_distance) * self.__log_distortion_factor

    @staticmethod
    def valid_phrases(all_phrases_from, hypothesis):
        
        untranslated_spans = hypothesis.untranslated_spans(len(all_phrases_from))
        valid_phrases = []
        for available_span in untranslated_spans:
            start = available_span[0]
            available_end = available_span[1]
            while start < available_end:
                for phrase_end in all_phrases_from[start]:
                    if phrase_end > available_end:
                        
                        
                        
                        break
                    valid_phrases.append((start, phrase_end))
                start += 1
        return valid_phrases


class _Hypothesis:
    

    def __init__(
        self,
        raw_score=0.0,
        src_phrase_span=(),
        trg_phrase=(),
        previous=None,
        future_score=0.0,
    ):
        
        self.raw_score = raw_score
        self.src_phrase_span = src_phrase_span
        self.trg_phrase = trg_phrase
        self.previous = previous
        self.future_score = future_score

    def score(self):
        
        return self.raw_score + self.future_score

    def untranslated_spans(self, sentence_length):
        
        translated_positions = self.translated_positions()
        translated_positions.sort()
        translated_positions.append(sentence_length)  

        untranslated_spans = []
        start = 0
        
        for end in translated_positions:
            if start < end:
                untranslated_spans.append((start, end))
            start = end + 1

        return untranslated_spans

    def translated_positions(self):
        
        translated_positions = []
        current_hypothesis = self
        while current_hypothesis.previous is not None:
            translated_span = current_hypothesis.src_phrase_span
            translated_positions.extend(range(translated_span[0], translated_span[1]))
            current_hypothesis = current_hypothesis.previous
        return translated_positions

    def total_translated_words(self):
        return len(self.translated_positions())

    def translation_so_far(self):
        translation = []
        self.__build_translation(self, translation)
        return translation

    def __build_translation(self, hypothesis, output):
        if hypothesis.previous is None:
            return
        self.__build_translation(hypothesis.previous, output)
        output.extend(hypothesis.trg_phrase)


class _Stack:
    

    def __init__(self, max_size=100, beam_threshold=0.0):
        
        self.max_size = max_size
        self.items = []

        if beam_threshold == 0.0:
            self.__log_beam_threshold = float("-inf")
        else:
            self.__log_beam_threshold = log(beam_threshold)

    def push(self, hypothesis):
        
        self.items.append(hypothesis)
        self.items.sort(key=lambda h: h.score(), reverse=True)
        while len(self.items) > self.max_size:
            self.items.pop()
        self.threshold_prune()

    def threshold_prune(self):
        if not self.items:
            return
        
        threshold = self.items[0].score() + self.__log_beam_threshold
        for hypothesis in reversed(self.items):
            if hypothesis.score() < threshold:
                self.items.pop()
            else:
                break

    def best(self):
        
        if self.items:
            return self.items[0]
        return None

    def __iter__(self):
        return iter(self.items)

    def __contains__(self, hypothesis):
        return hypothesis in self.items

    def __bool__(self):
        return len(self.items) != 0

    __nonzero__ = __bool__