We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
Adding Good turing and Add -n Smoothing
Apart from the existing 2 smoothing algorithms already present, I think the add -n smoothing and the Good turing smoothing can be added

--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `nltk/lm/api.py`
Content:
```
1 # -*- coding: utf-8 -*-
2 # Natural Language Toolkit: Language Models
3 #
4 # Copyright (C) 2001-2018 NLTK Project
5 # Authors: Ilia Kurenkov <ilia.kurenkov@gmail.com>
6 # URL: <http://nltk.org/>
7 # For license information, see LICENSE.TXT
8 """Language Model Interface."""
9 from __future__ import division, unicode_literals
10 
11 import random
12 from abc import ABCMeta, abstractmethod
13 from bisect import bisect
14 
15 from six import add_metaclass
16 
17 from nltk.lm.counter import NgramCounter
18 from nltk.lm.util import log_base2
19 from nltk.lm.vocabulary import Vocabulary
20 
21 try:
22     from itertools import accumulate
23 except ImportError:
24     import operator
25 
26     def accumulate(iterable, func=operator.add):
27         """Return running totals"""
28         # accumulate([1,2,3,4,5]) --> 1 3 6 10 15
29         # accumulate([1,2,3,4,5], operator.mul) --> 1 2 6 24 120
30         it = iter(iterable)
31         try:
32             total = next(it)
33         except StopIteration:
34             return
35         yield total
36         for element in it:
37             total = func(total, element)
38             yield total
39 
40 
41 @add_metaclass(ABCMeta)
42 class Smoothing(object):
43     """Ngram Smoothing Interface
44 
45     Implements Chen & Goodman 1995's idea that all smoothing algorithms have
46     certain features in common. This should ideally allow smoothing algoritms to
47     work both with Backoff and Interpolation.
48     """
49 
50     def __init__(self, vocabulary, counter):
51         self.vocab = vocabulary
52         self.counts = counter
53 
54     @abstractmethod
55     def unigram_score(self, word):
56         raise NotImplementedError()
57 
58     @abstractmethod
59     def alpha_gamma(self, word, context):
60         raise NotImplementedError()
61 
62 
63 def _mean(items):
64     """Return average (aka mean) for sequence of items."""
65     return sum(items) / len(items)
66 
67 
68 def _random_generator(seed_or_generator):
69     if isinstance(seed_or_generator, random.Random):
70         return seed_or_generator
71     return random.Random(seed_or_generator)
72 
73 
74 def _weighted_choice(population, weights, random_seed=None):
75     """Like random.choice, but with weights.
76 
77     Heavily inspired by python 3.6 `random.choices`.
78     """
79     if not population:
80         raise ValueError("Can't choose from empty population")
81     if len(population) != len(weights):
82         raise ValueError("The number of weights does not match the population")
83     cum_weights = list(accumulate(weights))
84     total = cum_weights[-1]
85     threshold = _random_generator(random_seed).random()
86     return population[bisect(cum_weights, total * threshold)]
87 
88 
89 @add_metaclass(ABCMeta)
90 class LanguageModel(object):
91     """ABC for Language Models.
92 
93     Cannot be directly instantiated itself.
94 
95     """
96 
97     def __init__(self, order, vocabulary=None, counter=None):
98         """Creates new LanguageModel.
99 
100         :param vocabulary: If provided, this vocabulary will be used instead
101         of creating a new one when training.
102         :type vocabulary: `nltk.lm.Vocabulary` or None
103         :param counter: If provided, use this object to count ngrams.
104         :type vocabulary: `nltk.lm.NgramCounter` or None
105         :param ngrams_fn: If given, defines how sentences in training text are turned to ngram
106                           sequences.
107         :type ngrams_fn: function or None
108         :param pad_fn: If given, defines how senteces in training text are padded.
109         :type pad_fn: function or None
110 
111         """
112         self.order = order
113         self.vocab = Vocabulary() if vocabulary is None else vocabulary
114         self.counts = NgramCounter() if counter is None else counter
115 
116     def fit(self, text, vocabulary_text=None):
117         """Trains the model on a text.
118 
119         :param text: Training text as a sequence of sentences.
120 
121         """
122         if not self.vocab:
123             if vocabulary_text is None:
124                 raise ValueError(
125                     "Cannot fit without a vocabulary or text to " "create it from."
126                 )
127             self.vocab.update(vocabulary_text)
128         self.counts.update(self.vocab.lookup(sent) for sent in text)
129 
130     def score(self, word, context=None):
131         """Masks out of vocab (OOV) words and computes their model score.
132 
133         For model-specific logic of calculating scores, see the `unmasked_score`
134         method.
135         """
136         return self.unmasked_score(
137             self.vocab.lookup(word), self.vocab.lookup(context) if context else None
138         )
139 
140     @abstractmethod
141     def unmasked_score(self, word, context=None):
142         """Score a word given some optional context.
143 
144         Concrete models are expected to provide an implementation.
145         Note that this method does not mask its arguments with the OOV label.
146         Use the `score` method for that.
147 
148         :param str word: Word for which we want the score
149         :param tuple(str) context: Context the word is in.
150         If `None`, compute unigram score.
151         :param context: tuple(str) or None
152         :rtype: float
153 
154         """
155         raise NotImplementedError()
156 
157     def logscore(self, word, context=None):
158         """Evaluate the log score of this word in this context.
159 
160         The arguments are the same as for `score` and `unmasked_score`.
161 
162         """
163         return log_base2(self.score(word, context))
164 
165     def context_counts(self, context):
166         """Helper method for retrieving counts for a given context.
167 
168         Assumes context has been checked and oov words in it masked.
169         :type context: tuple(str) or None
170 
171         """
172         return (
173             self.counts[len(context) + 1][context] if context else self.counts.unigrams
174         )
175 
176     def entropy(self, text_ngrams):
177         """Calculate cross-entropy of model for given evaluation text.
178 
179         :param Iterable(tuple(str)) text_ngrams: A sequence of ngram tuples.
180         :rtype: float
181 
182         """
183         return -1 * _mean(
184             [self.logscore(ngram[-1], ngram[:-1]) for ngram in text_ngrams]
185         )
186 
187     def perplexity(self, text_ngrams):
188         """Calculates the perplexity of the given text.
189 
190         This is simply 2 ** cross-entropy for the text, so the arguments are the same.
191 
192         """
193         return pow(2.0, self.entropy(text_ngrams))
194 
195     def generate(self, num_words=1, text_seed=None, random_seed=None):
196         """Generate words from the model.
197 
198         :param int num_words: How many words to generate. By default 1.
199         :param text_seed: Generation can be conditioned on preceding context.
200         :param random_seed: If provided, makes the random sampling part of
201         generation reproducible.
202         :return: One (str) word or a list of words generated from model.
203 
204         Examples:
205 
206         >>> from nltk.lm import MLE
207         >>> lm = MLE(2)
208         >>> lm.fit([[("a", "b"), ("b", "c")]], vocabulary_text=['a', 'b', 'c'])
209         >>> lm.fit([[("a",), ("b",), ("c",)]])
210         >>> lm.generate(random_seed=3)
211         'a'
212         >>> lm.generate(text_seed=['a'])
213         'b'
214 
215         """
216         text_seed = [] if text_seed is None else list(text_seed)
217         # base recursion case
218         if num_words == 1:
219             context = (
220                 text_seed[-self.order + 1 :]
221                 if len(text_seed) >= self.order
222                 else text_seed
223             )
224             samples = self.context_counts(self.vocab.lookup(context))
225             while context and not samples:
226                 context = context[1:] if len(context) > 1 else []
227                 samples = self.context_counts(self.vocab.lookup(context))
228             # sorting achieves two things:
229             # - reproducible randomness when sampling
230             # - turning Mapping into Sequence which _weighted_choice expects
231             samples = sorted(samples)
232             return _weighted_choice(
233                 samples, tuple(self.score(w, context) for w in samples), random_seed
234             )
235         # build up text one word at a time
236         generated = []
237         for _ in range(num_words):
238             generated.append(
239                 self.generate(
240                     num_words=1,
241                     text_seed=text_seed + generated,
242                     random_seed=random_seed,
243                 )
244             )
245         return generated
246
```

Path: `nltk/lm/smoothing.py`
Content:
```
1 # -*- coding: utf-8 -*-
2 # Natural Language Toolkit: Language Model Unit Tests
3 #
4 # Copyright (C) 2001-2018 NLTK Project
5 # Author: Ilia Kurenkov <ilia.kurenkov@gmail.com>
6 # URL: <http://nltk.org/>
7 # For license information, see LICENSE.TXT
8 """Smoothing algorithms for language modeling.
9 
10 According to Chen & Goodman 1995 these should work with both Backoff and
11 Interpolation.
12 """
13 
14 from nltk.lm.api import Smoothing
15 
16 
17 def _count_non_zero_vals(dictionary):
18     return sum(1.0 for c in dictionary.values() if c > 0)
19 
20 
21 class WittenBell(Smoothing):
22     """Witten-Bell smoothing."""
23 
24     def alpha_gamma(self, word, context):
25         gamma = self.gamma(context)
26         return (1.0 - gamma) * self.alpha(word, context), gamma
27 
28     def unigram_score(self, word):
29         return self.counts.unigrams.freq(word)
30 
31     def alpha(self, word, context):
32         return self.counts[context].freq(word)
33 
34     def gamma(self, context):
35         n_plus = _count_non_zero_vals(self.counts[context])
36         return n_plus / (n_plus + self.counts[len(context) + 1].N())
37 
38 
39 class KneserNey(Smoothing):
40     """Kneser-Ney Smoothing."""
41 
42     def __init__(self, vocabulary, counter, discount=0.1, **kwargs):
43         super(KneserNey, self).__init__(vocabulary, counter, *kwargs)
44         self.discount = discount
45 
46     def unigram_score(self, word):
47         return 1.0 / len(self.vocab)
48 
49     def alpha_gamma(self, word, context):
50         prefix_counts = self.counts[context]
51         return self.alpha(word, prefix_counts), self.gamma(prefix_counts)
52 
53     def alpha(self, word, prefix_counts):
54         return max(prefix_counts[word] - self.discount, 0.0) / prefix_counts.N()
55 
56     def gamma(self, prefix_counts):
57         return self.discount * _count_non_zero_vals(prefix_counts) / prefix_counts.N()
58
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/nltk/lm/api.py b/nltk/lm/api.py
--- a/nltk/lm/api.py
+++ b/nltk/lm/api.py
@@ -45,6 +45,8 @@
     Implements Chen & Goodman 1995's idea that all smoothing algorithms have
     certain features in common. This should ideally allow smoothing algoritms to
     work both with Backoff and Interpolation.
+
+    counter represents the number of counts for ngrams
     """
 
     def __init__(self, vocabulary, counter):
diff --git a/nltk/lm/smoothing.py b/nltk/lm/smoothing.py
--- a/nltk/lm/smoothing.py
+++ b/nltk/lm/smoothing.py
@@ -21,6 +21,10 @@
 class WittenBell(Smoothing):
     """Witten-Bell smoothing."""
 
+    def __init__(self, vocabulary, counter, discount=0.1, **kwargs):
+        super(WittenBell, self).__init__(vocabulary, counter, *kwargs)
+        self.counts = counter
+
     def alpha_gamma(self, word, context):
         gamma = self.gamma(context)
         return (1.0 - gamma) * self.alpha(word, context), gamma
@@ -42,9 +46,10 @@
     def __init__(self, vocabulary, counter, discount=0.1, **kwargs):
         super(KneserNey, self).__init__(vocabulary, counter, *kwargs)
         self.discount = discount
+        self.vocabulary = vocabulary
 
     def unigram_score(self, word):
-        return 1.0 / len(self.vocab)
+        return 1.0 / len(self.vocabulary)
 
     def alpha_gamma(self, word, context):
         prefix_counts = self.counts[context]
@@ -55,3 +60,19 @@
 
     def gamma(self, prefix_counts):
         return self.discount * _count_non_zero_vals(prefix_counts) / prefix_counts.N()
+
+
+class GoodTuring(Smoothing):
+    """Good-Turing Smoothing"""
+    def __init__(self, vocabulary, counter, **kwargs):
+        super(GoodTuring, self).__init__(vocabulary, counter, *kwargs)
+        self.counts = counter
+        self.vocabulary = vocabulary
+
+    def unigram_score(self, word):
+        word_count = self.counts[word]
+        count_plus_1 = 0.
+        for everyContext in self.counts.keys():
+            if len(everyContext.split()) == word_count+1:
+                count_plus_1 += 1
+        return count_plus_1 / len(self.vocabulary)

{"golden_diff": "diff --git a/nltk/lm/api.py b/nltk/lm/api.py\n--- a/nltk/lm/api.py\n+++ b/nltk/lm/api.py\n@@ -45,6 +45,8 @@\n     Implements Chen & Goodman 1995's idea that all smoothing algorithms have\n     certain features in common. This should ideally allow smoothing algoritms to\n     work both with Backoff and Interpolation.\n+\n+    counter represents the number of counts for ngrams\n     \"\"\"\n \n     def __init__(self, vocabulary, counter):\ndiff --git a/nltk/lm/smoothing.py b/nltk/lm/smoothing.py\n--- a/nltk/lm/smoothing.py\n+++ b/nltk/lm/smoothing.py\n@@ -21,6 +21,10 @@\n class WittenBell(Smoothing):\n     \"\"\"Witten-Bell smoothing.\"\"\"\n \n+    def __init__(self, vocabulary, counter, discount=0.1, **kwargs):\n+        super(WittenBell, self).__init__(vocabulary, counter, *kwargs)\n+        self.counts = counter\n+\n     def alpha_gamma(self, word, context):\n         gamma = self.gamma(context)\n         return (1.0 - gamma) * self.alpha(word, context), gamma\n@@ -42,9 +46,10 @@\n     def __init__(self, vocabulary, counter, discount=0.1, **kwargs):\n         super(KneserNey, self).__init__(vocabulary, counter, *kwargs)\n         self.discount = discount\n+        self.vocabulary = vocabulary\n \n     def unigram_score(self, word):\n-        return 1.0 / len(self.vocab)\n+        return 1.0 / len(self.vocabulary)\n \n     def alpha_gamma(self, word, context):\n         prefix_counts = self.counts[context]\n@@ -55,3 +60,19 @@\n \n     def gamma(self, prefix_counts):\n         return self.discount * _count_non_zero_vals(prefix_counts) / prefix_counts.N()\n+\n+\n+class GoodTuring(Smoothing):\n+    \"\"\"Good-Turing Smoothing\"\"\"\n+    def __init__(self, vocabulary, counter, **kwargs):\n+        super(GoodTuring, self).__init__(vocabulary, counter, *kwargs)\n+        self.counts = counter\n+        self.vocabulary = vocabulary\n+\n+    def unigram_score(self, word):\n+        word_count = self.counts[word]\n+        count_plus_1 = 0.\n+        for everyContext in self.counts.keys():\n+            if len(everyContext.split()) == word_count+1:\n+                count_plus_1 += 1\n+        return count_plus_1 / len(self.vocabulary)\n", "issue": "Adding Good turing and Add -n Smoothing\nApart from the existing 2 smoothing algorithms already present, I think the add -n smoothing and the Good turing smoothing can be added\n", "before_files": [{"content": "# -*- coding: utf-8 -*-\n# Natural Language Toolkit: Language Models\n#\n# Copyright (C) 2001-2018 NLTK Project\n# Authors: Ilia Kurenkov <ilia.kurenkov@gmail.com>\n# URL: <http://nltk.org/>\n# For license information, see LICENSE.TXT\n\"\"\"Language Model Interface.\"\"\"\nfrom __future__ import division, unicode_literals\n\nimport random\nfrom abc import ABCMeta, abstractmethod\nfrom bisect import bisect\n\nfrom six import add_metaclass\n\nfrom nltk.lm.counter import NgramCounter\nfrom nltk.lm.util import log_base2\nfrom nltk.lm.vocabulary import Vocabulary\n\ntry:\n    from itertools import accumulate\nexcept ImportError:\n    import operator\n\n    def accumulate(iterable, func=operator.add):\n        \"\"\"Return running totals\"\"\"\n        # accumulate([1,2,3,4,5]) --> 1 3 6 10 15\n        # accumulate([1,2,3,4,5], operator.mul) --> 1 2 6 24 120\n        it = iter(iterable)\n        try:\n            total = next(it)\n        except StopIteration:\n            return\n        yield total\n        for element in it:\n            total = func(total, element)\n            yield total\n\n\n@add_metaclass(ABCMeta)\nclass Smoothing(object):\n    \"\"\"Ngram Smoothing Interface\n\n    Implements Chen & Goodman 1995's idea that all smoothing algorithms have\n    certain features in common. This should ideally allow smoothing algoritms to\n    work both with Backoff and Interpolation.\n    \"\"\"\n\n    def __init__(self, vocabulary, counter):\n        self.vocab = vocabulary\n        self.counts = counter\n\n    @abstractmethod\n    def unigram_score(self, word):\n        raise NotImplementedError()\n\n    @abstractmethod\n    def alpha_gamma(self, word, context):\n        raise NotImplementedError()\n\n\ndef _mean(items):\n    \"\"\"Return average (aka mean) for sequence of items.\"\"\"\n    return sum(items) / len(items)\n\n\ndef _random_generator(seed_or_generator):\n    if isinstance(seed_or_generator, random.Random):\n        return seed_or_generator\n    return random.Random(seed_or_generator)\n\n\ndef _weighted_choice(population, weights, random_seed=None):\n    \"\"\"Like random.choice, but with weights.\n\n    Heavily inspired by python 3.6 `random.choices`.\n    \"\"\"\n    if not population:\n        raise ValueError(\"Can't choose from empty population\")\n    if len(population) != len(weights):\n        raise ValueError(\"The number of weights does not match the population\")\n    cum_weights = list(accumulate(weights))\n    total = cum_weights[-1]\n    threshold = _random_generator(random_seed).random()\n    return population[bisect(cum_weights, total * threshold)]\n\n\n@add_metaclass(ABCMeta)\nclass LanguageModel(object):\n    \"\"\"ABC for Language Models.\n\n    Cannot be directly instantiated itself.\n\n    \"\"\"\n\n    def __init__(self, order, vocabulary=None, counter=None):\n        \"\"\"Creates new LanguageModel.\n\n        :param vocabulary: If provided, this vocabulary will be used instead\n        of creating a new one when training.\n        :type vocabulary: `nltk.lm.Vocabulary` or None\n        :param counter: If provided, use this object to count ngrams.\n        :type vocabulary: `nltk.lm.NgramCounter` or None\n        :param ngrams_fn: If given, defines how sentences in training text are turned to ngram\n                          sequences.\n        :type ngrams_fn: function or None\n        :param pad_fn: If given, defines how senteces in training text are padded.\n        :type pad_fn: function or None\n\n        \"\"\"\n        self.order = order\n        self.vocab = Vocabulary() if vocabulary is None else vocabulary\n        self.counts = NgramCounter() if counter is None else counter\n\n    def fit(self, text, vocabulary_text=None):\n        \"\"\"Trains the model on a text.\n\n        :param text: Training text as a sequence of sentences.\n\n        \"\"\"\n        if not self.vocab:\n            if vocabulary_text is None:\n                raise ValueError(\n                    \"Cannot fit without a vocabulary or text to \" \"create it from.\"\n                )\n            self.vocab.update(vocabulary_text)\n        self.counts.update(self.vocab.lookup(sent) for sent in text)\n\n    def score(self, word, context=None):\n        \"\"\"Masks out of vocab (OOV) words and computes their model score.\n\n        For model-specific logic of calculating scores, see the `unmasked_score`\n        method.\n        \"\"\"\n        return self.unmasked_score(\n            self.vocab.lookup(word), self.vocab.lookup(context) if context else None\n        )\n\n    @abstractmethod\n    def unmasked_score(self, word, context=None):\n        \"\"\"Score a word given some optional context.\n\n        Concrete models are expected to provide an implementation.\n        Note that this method does not mask its arguments with the OOV label.\n        Use the `score` method for that.\n\n        :param str word: Word for which we want the score\n        :param tuple(str) context: Context the word is in.\n        If `None`, compute unigram score.\n        :param context: tuple(str) or None\n        :rtype: float\n\n        \"\"\"\n        raise NotImplementedError()\n\n    def logscore(self, word, context=None):\n        \"\"\"Evaluate the log score of this word in this context.\n\n        The arguments are the same as for `score` and `unmasked_score`.\n\n        \"\"\"\n        return log_base2(self.score(word, context))\n\n    def context_counts(self, context):\n        \"\"\"Helper method for retrieving counts for a given context.\n\n        Assumes context has been checked and oov words in it masked.\n        :type context: tuple(str) or None\n\n        \"\"\"\n        return (\n            self.counts[len(context) + 1][context] if context else self.counts.unigrams\n        )\n\n    def entropy(self, text_ngrams):\n        \"\"\"Calculate cross-entropy of model for given evaluation text.\n\n        :param Iterable(tuple(str)) text_ngrams: A sequence of ngram tuples.\n        :rtype: float\n\n        \"\"\"\n        return -1 * _mean(\n            [self.logscore(ngram[-1], ngram[:-1]) for ngram in text_ngrams]\n        )\n\n    def perplexity(self, text_ngrams):\n        \"\"\"Calculates the perplexity of the given text.\n\n        This is simply 2 ** cross-entropy for the text, so the arguments are the same.\n\n        \"\"\"\n        return pow(2.0, self.entropy(text_ngrams))\n\n    def generate(self, num_words=1, text_seed=None, random_seed=None):\n        \"\"\"Generate words from the model.\n\n        :param int num_words: How many words to generate. By default 1.\n        :param text_seed: Generation can be conditioned on preceding context.\n        :param random_seed: If provided, makes the random sampling part of\n        generation reproducible.\n        :return: One (str) word or a list of words generated from model.\n\n        Examples:\n\n        >>> from nltk.lm import MLE\n        >>> lm = MLE(2)\n        >>> lm.fit([[(\"a\", \"b\"), (\"b\", \"c\")]], vocabulary_text=['a', 'b', 'c'])\n        >>> lm.fit([[(\"a\",), (\"b\",), (\"c\",)]])\n        >>> lm.generate(random_seed=3)\n        'a'\n        >>> lm.generate(text_seed=['a'])\n        'b'\n\n        \"\"\"\n        text_seed = [] if text_seed is None else list(text_seed)\n        # base recursion case\n        if num_words == 1:\n            context = (\n                text_seed[-self.order + 1 :]\n                if len(text_seed) >= self.order\n                else text_seed\n            )\n            samples = self.context_counts(self.vocab.lookup(context))\n            while context and not samples:\n                context = context[1:] if len(context) > 1 else []\n                samples = self.context_counts(self.vocab.lookup(context))\n            # sorting achieves two things:\n            # - reproducible randomness when sampling\n            # - turning Mapping into Sequence which _weighted_choice expects\n            samples = sorted(samples)\n            return _weighted_choice(\n                samples, tuple(self.score(w, context) for w in samples), random_seed\n            )\n        # build up text one word at a time\n        generated = []\n        for _ in range(num_words):\n            generated.append(\n                self.generate(\n                    num_words=1,\n                    text_seed=text_seed + generated,\n                    random_seed=random_seed,\n                )\n            )\n        return generated\n", "path": "nltk/lm/api.py"}, {"content": "# -*- coding: utf-8 -*-\n# Natural Language Toolkit: Language Model Unit Tests\n#\n# Copyright (C) 2001-2018 NLTK Project\n# Author: Ilia Kurenkov <ilia.kurenkov@gmail.com>\n# URL: <http://nltk.org/>\n# For license information, see LICENSE.TXT\n\"\"\"Smoothing algorithms for language modeling.\n\nAccording to Chen & Goodman 1995 these should work with both Backoff and\nInterpolation.\n\"\"\"\n\nfrom nltk.lm.api import Smoothing\n\n\ndef _count_non_zero_vals(dictionary):\n    return sum(1.0 for c in dictionary.values() if c > 0)\n\n\nclass WittenBell(Smoothing):\n    \"\"\"Witten-Bell smoothing.\"\"\"\n\n    def alpha_gamma(self, word, context):\n        gamma = self.gamma(context)\n        return (1.0 - gamma) * self.alpha(word, context), gamma\n\n    def unigram_score(self, word):\n        return self.counts.unigrams.freq(word)\n\n    def alpha(self, word, context):\n        return self.counts[context].freq(word)\n\n    def gamma(self, context):\n        n_plus = _count_non_zero_vals(self.counts[context])\n        return n_plus / (n_plus + self.counts[len(context) + 1].N())\n\n\nclass KneserNey(Smoothing):\n    \"\"\"Kneser-Ney Smoothing.\"\"\"\n\n    def __init__(self, vocabulary, counter, discount=0.1, **kwargs):\n        super(KneserNey, self).__init__(vocabulary, counter, *kwargs)\n        self.discount = discount\n\n    def unigram_score(self, word):\n        return 1.0 / len(self.vocab)\n\n    def alpha_gamma(self, word, context):\n        prefix_counts = self.counts[context]\n        return self.alpha(word, prefix_counts), self.gamma(prefix_counts)\n\n    def alpha(self, word, prefix_counts):\n        return max(prefix_counts[word] - self.discount, 0.0) / prefix_counts.N()\n\n    def gamma(self, prefix_counts):\n        return self.discount * _count_non_zero_vals(prefix_counts) / prefix_counts.N()\n", "path": "nltk/lm/smoothing.py"}], "after_files": [{"content": "# -*- coding: utf-8 -*-\n# Natural Language Toolkit: Language Models\n#\n# Copyright (C) 2001-2018 NLTK Project\n# Authors: Ilia Kurenkov <ilia.kurenkov@gmail.com>\n# URL: <http://nltk.org/>\n# For license information, see LICENSE.TXT\n\"\"\"Language Model Interface.\"\"\"\nfrom __future__ import division, unicode_literals\n\nimport random\nfrom abc import ABCMeta, abstractmethod\nfrom bisect import bisect\n\nfrom six import add_metaclass\n\nfrom nltk.lm.counter import NgramCounter\nfrom nltk.lm.util import log_base2\nfrom nltk.lm.vocabulary import Vocabulary\n\ntry:\n    from itertools import accumulate\nexcept ImportError:\n    import operator\n\n    def accumulate(iterable, func=operator.add):\n        \"\"\"Return running totals\"\"\"\n        # accumulate([1,2,3,4,5]) --> 1 3 6 10 15\n        # accumulate([1,2,3,4,5], operator.mul) --> 1 2 6 24 120\n        it = iter(iterable)\n        try:\n            total = next(it)\n        except StopIteration:\n            return\n        yield total\n        for element in it:\n            total = func(total, element)\n            yield total\n\n\n@add_metaclass(ABCMeta)\nclass Smoothing(object):\n    \"\"\"Ngram Smoothing Interface\n\n    Implements Chen & Goodman 1995's idea that all smoothing algorithms have\n    certain features in common. This should ideally allow smoothing algoritms to\n    work both with Backoff and Interpolation.\n\n    counter represents the number of counts for ngrams\n    \"\"\"\n\n    def __init__(self, vocabulary, counter):\n        self.vocab = vocabulary\n        self.counts = counter\n\n    @abstractmethod\n    def unigram_score(self, word):\n        raise NotImplementedError()\n\n    @abstractmethod\n    def alpha_gamma(self, word, context):\n        raise NotImplementedError()\n\n\ndef _mean(items):\n    \"\"\"Return average (aka mean) for sequence of items.\"\"\"\n    return sum(items) / len(items)\n\n\ndef _random_generator(seed_or_generator):\n    if isinstance(seed_or_generator, random.Random):\n        return seed_or_generator\n    return random.Random(seed_or_generator)\n\n\ndef _weighted_choice(population, weights, random_seed=None):\n    \"\"\"Like random.choice, but with weights.\n\n    Heavily inspired by python 3.6 `random.choices`.\n    \"\"\"\n    if not population:\n        raise ValueError(\"Can't choose from empty population\")\n    if len(population) != len(weights):\n        raise ValueError(\"The number of weights does not match the population\")\n    cum_weights = list(accumulate(weights))\n    total = cum_weights[-1]\n    threshold = _random_generator(random_seed).random()\n    return population[bisect(cum_weights, total * threshold)]\n\n\n@add_metaclass(ABCMeta)\nclass LanguageModel(object):\n    \"\"\"ABC for Language Models.\n\n    Cannot be directly instantiated itself.\n\n    \"\"\"\n\n    def __init__(self, order, vocabulary=None, counter=None):\n        \"\"\"Creates new LanguageModel.\n\n        :param vocabulary: If provided, this vocabulary will be used instead\n        of creating a new one when training.\n        :type vocabulary: `nltk.lm.Vocabulary` or None\n        :param counter: If provided, use this object to count ngrams.\n        :type vocabulary: `nltk.lm.NgramCounter` or None\n        :param ngrams_fn: If given, defines how sentences in training text are turned to ngram\n                          sequences.\n        :type ngrams_fn: function or None\n        :param pad_fn: If given, defines how senteces in training text are padded.\n        :type pad_fn: function or None\n\n        \"\"\"\n        self.order = order\n        self.vocab = Vocabulary() if vocabulary is None else vocabulary\n        self.counts = NgramCounter() if counter is None else counter\n\n    def fit(self, text, vocabulary_text=None):\n        \"\"\"Trains the model on a text.\n\n        :param text: Training text as a sequence of sentences.\n\n        \"\"\"\n        if not self.vocab:\n            if vocabulary_text is None:\n                raise ValueError(\n                    \"Cannot fit without a vocabulary or text to \" \"create it from.\"\n                )\n            self.vocab.update(vocabulary_text)\n        self.counts.update(self.vocab.lookup(sent) for sent in text)\n\n    def score(self, word, context=None):\n        \"\"\"Masks out of vocab (OOV) words and computes their model score.\n\n        For model-specific logic of calculating scores, see the `unmasked_score`\n        method.\n        \"\"\"\n        return self.unmasked_score(\n            self.vocab.lookup(word), self.vocab.lookup(context) if context else None\n        )\n\n    @abstractmethod\n    def unmasked_score(self, word, context=None):\n        \"\"\"Score a word given some optional context.\n\n        Concrete models are expected to provide an implementation.\n        Note that this method does not mask its arguments with the OOV label.\n        Use the `score` method for that.\n\n        :param str word: Word for which we want the score\n        :param tuple(str) context: Context the word is in.\n        If `None`, compute unigram score.\n        :param context: tuple(str) or None\n        :rtype: float\n\n        \"\"\"\n        raise NotImplementedError()\n\n    def logscore(self, word, context=None):\n        \"\"\"Evaluate the log score of this word in this context.\n\n        The arguments are the same as for `score` and `unmasked_score`.\n\n        \"\"\"\n        return log_base2(self.score(word, context))\n\n    def context_counts(self, context):\n        \"\"\"Helper method for retrieving counts for a given context.\n\n        Assumes context has been checked and oov words in it masked.\n        :type context: tuple(str) or None\n\n        \"\"\"\n        return (\n            self.counts[len(context) + 1][context] if context else self.counts.unigrams\n        )\n\n    def entropy(self, text_ngrams):\n        \"\"\"Calculate cross-entropy of model for given evaluation text.\n\n        :param Iterable(tuple(str)) text_ngrams: A sequence of ngram tuples.\n        :rtype: float\n\n        \"\"\"\n        return -1 * _mean(\n            [self.logscore(ngram[-1], ngram[:-1]) for ngram in text_ngrams]\n        )\n\n    def perplexity(self, text_ngrams):\n        \"\"\"Calculates the perplexity of the given text.\n\n        This is simply 2 ** cross-entropy for the text, so the arguments are the same.\n\n        \"\"\"\n        return pow(2.0, self.entropy(text_ngrams))\n\n    def generate(self, num_words=1, text_seed=None, random_seed=None):\n        \"\"\"Generate words from the model.\n\n        :param int num_words: How many words to generate. By default 1.\n        :param text_seed: Generation can be conditioned on preceding context.\n        :param random_seed: If provided, makes the random sampling part of\n        generation reproducible.\n        :return: One (str) word or a list of words generated from model.\n\n        Examples:\n\n        >>> from nltk.lm import MLE\n        >>> lm = MLE(2)\n        >>> lm.fit([[(\"a\", \"b\"), (\"b\", \"c\")]], vocabulary_text=['a', 'b', 'c'])\n        >>> lm.fit([[(\"a\",), (\"b\",), (\"c\",)]])\n        >>> lm.generate(random_seed=3)\n        'a'\n        >>> lm.generate(text_seed=['a'])\n        'b'\n\n        \"\"\"\n        text_seed = [] if text_seed is None else list(text_seed)\n        # base recursion case\n        if num_words == 1:\n            context = (\n                text_seed[-self.order + 1 :]\n                if len(text_seed) >= self.order\n                else text_seed\n            )\n            samples = self.context_counts(self.vocab.lookup(context))\n            while context and not samples:\n                context = context[1:] if len(context) > 1 else []\n                samples = self.context_counts(self.vocab.lookup(context))\n            # sorting achieves two things:\n            # - reproducible randomness when sampling\n            # - turning Mapping into Sequence which _weighted_choice expects\n            samples = sorted(samples)\n            return _weighted_choice(\n                samples, tuple(self.score(w, context) for w in samples), random_seed\n            )\n        # build up text one word at a time\n        generated = []\n        for _ in range(num_words):\n            generated.append(\n                self.generate(\n                    num_words=1,\n                    text_seed=text_seed + generated,\n                    random_seed=random_seed,\n                )\n            )\n        return generated\n", "path": "nltk/lm/api.py"}, {"content": "# -*- coding: utf-8 -*-\n# Natural Language Toolkit: Language Model Unit Tests\n#\n# Copyright (C) 2001-2018 NLTK Project\n# Author: Ilia Kurenkov <ilia.kurenkov@gmail.com>\n# URL: <http://nltk.org/>\n# For license information, see LICENSE.TXT\n\"\"\"Smoothing algorithms for language modeling.\n\nAccording to Chen & Goodman 1995 these should work with both Backoff and\nInterpolation.\n\"\"\"\n\nfrom nltk.lm.api import Smoothing\n\n\ndef _count_non_zero_vals(dictionary):\n    return sum(1.0 for c in dictionary.values() if c > 0)\n\n\nclass WittenBell(Smoothing):\n    \"\"\"Witten-Bell smoothing.\"\"\"\n\n    def __init__(self, vocabulary, counter, discount=0.1, **kwargs):\n        super(WittenBell, self).__init__(vocabulary, counter, *kwargs)\n        self.counts = counter\n\n    def alpha_gamma(self, word, context):\n        gamma = self.gamma(context)\n        return (1.0 - gamma) * self.alpha(word, context), gamma\n\n    def unigram_score(self, word):\n        return self.counts.unigrams.freq(word)\n\n    def alpha(self, word, context):\n        return self.counts[context].freq(word)\n\n    def gamma(self, context):\n        n_plus = _count_non_zero_vals(self.counts[context])\n        return n_plus / (n_plus + self.counts[len(context) + 1].N())\n\n\nclass KneserNey(Smoothing):\n    \"\"\"Kneser-Ney Smoothing.\"\"\"\n\n    def __init__(self, vocabulary, counter, discount=0.1, **kwargs):\n        super(KneserNey, self).__init__(vocabulary, counter, *kwargs)\n        self.discount = discount\n        self.vocabulary = vocabulary\n\n    def unigram_score(self, word):\n        return 1.0 / len(self.vocabulary)\n\n    def alpha_gamma(self, word, context):\n        prefix_counts = self.counts[context]\n        return self.alpha(word, prefix_counts), self.gamma(prefix_counts)\n\n    def alpha(self, word, prefix_counts):\n        return max(prefix_counts[word] - self.discount, 0.0) / prefix_counts.N()\n\n    def gamma(self, prefix_counts):\n        return self.discount * _count_non_zero_vals(prefix_counts) / prefix_counts.N()\n\n\nclass GoodTuring(Smoothing):\n    \"\"\"Good-Turing Smoothing\"\"\"\n    def __init__(self, vocabulary, counter, **kwargs):\n        super(GoodTuring, self).__init__(vocabulary, counter, *kwargs)\n        self.counts = counter\n        self.vocabulary = vocabulary\n\n    def unigram_score(self, word):\n        word_count = self.counts[word]\n        count_plus_1 = 0.\n        for everyContext in self.counts.keys():\n            if len(everyContext.split()) == word_count+1:\n                count_plus_1 += 1\n        return count_plus_1 / len(self.vocabulary)\n", "path": "nltk/lm/smoothing.py"}]}