Repository: nltk/nltk

Issue:
nltk.everygrams() does not work with non-reusable iterables and iterables without lengths.
`nltk.util.everygrams()` ([code](https://github.com/nltk/nltk/blob/develop/nltk/util.py#L577-L600), [docs](https://nltk.readthedocs.io/en/latest/api/nltk.html?highlight=everygrams#nltk.util.everygrams)) claims to support both sequences and iterables. However, for iterables that are not reusable or iterables without a length function, everygrams either raises an exception or behaves incorrectly. In particular:
* When calling `everygrams(obj)` without its optional `max_len` argument, it attempts to take the length of its first argument, which may not support `len(obj)` resulting in a `TypeError`.
* When calling `everygrams(obj, max_len=2)` for example, if obj is an iterable that is not reusable it will be exhausted after only the ngrams of length `1` have been found and `everygrams()` ends up returning only the ngrams of length `1`.

I am happy to make a PR for this.

## Non-Working Examples

For example, starting with the example from the documentation
```python
>>> from nltk import everygrams
>>> sent = 'a b c'.split()
>>> list(everygrams(sent))
[('a',), ('b',), ('c',), ('a', 'b'), ('b', 'c'), ('a', 'b', 'c')]
>>> list(everygrams(sent, max_len=2))
[('a',), ('b',), ('c',), ('a', 'b'), ('b', 'c')]
```

We should expect that `everygrams(iter(sent))` should have the same output as `everygrams(sent)`. Instead, it raises a `TypeError`.
```python
>>> list(everygrams(sent))
[('a',), ('b',), ('c',), ('a', 'b'), ('b', 'c'), ('a', 'b', 'c')]
>>> list(everygrams(iter(sent)))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/.../python3.8/site-packages/nltk/util.py", line 603, in everygrams
    max_len = len(sequence)
TypeError: object of type 'list_iterator' has no len()
```
Likewise, we should expect that `everygrams(iter(sent), max_len=2)` should have the same output as `everygrams(sent, max_len=2)`. This is not the case.
```python
>>> list(everygrams(sent, max_len=2))
[('a',), ('b',), ('c',), ('a', 'b'), ('b', 'c')]
>>> list(everygrams(iter(sent), max_len=2))
[('a',), ('b',), ('c',)]
```


## Possible Solutions

There are several possible solutions:
1. Do not accept iterables.
    * Since nltk is commonly used to process large amounts of text data, iterables are the most natural and practical approach to avoid loading data into memory all at once.
2. If the argument is an iterable, cache it, computing its length in the process, in case it cannot be reused.
    * This would require loading the data into memory all at once, which should be avoided.
3. Use a `history` sliding window of size `max_len` to produce the ngrams. This strategy is similar to `history` in the implementation of ngram.
    * This would be my suggested approach since it provides the most functionality. However, it would have the drawback of changing the order of the output ngrams. For example, 
      ```python
      >>> list(old_everygrams(iter(sent)))
      [('a',), ('b',), ('c',), ('a', 'b'), ('b', 'c'), ('a', 'b', 'c')]
      >>> list(new_everygrams(iter(sent)))
      [('a',), ('a', 'b'), ('a', 'b', 'c'), ('b',), ('b', 'c'), ('c',)]
      ```

I am happy to make a PR for this.

Discussion:

Patch:
diff --git a/AUTHORS.md b/AUTHORS.md
index 6a233f99b..dcf297261 100644
--- a/AUTHORS.md
+++ b/AUTHORS.md
@@ -263,6 +263,8 @@
 - Bonifacio de Oliveira <https://github.com/Bonifacio2>
 - Vassilis Palassopoulos <https://github.com/palasso>
 - Ram Rachum <https://github.com/cool-RR>
+- Denali Molitor <https://github.com/dmmolitor>
+- Jacob Moorman <https://github.com/jdmoorman>
 
 ## Others whose work we've taken and included in NLTK, but who didn't directly contribute it:
 ### Contributors to the Porter Stemmer
diff --git a/nltk/lm/__init__.py b/nltk/lm/__init__.py
index 5b87ef7f1..2baa90bca 100644
--- a/nltk/lm/__init__.py
+++ b/nltk/lm/__init__.py
@@ -73,15 +73,7 @@ While not the most efficient, it is conceptually simple.
     >>> from nltk.util import everygrams
     >>> padded_bigrams = list(pad_both_ends(text[0], n=2))
     >>> list(everygrams(padded_bigrams, max_len=2))
-    [('
',),
-     ('a',),
-     ('b',),
-     ('c',),
-     ('
',),
-     ('
', 'a'),
-     ('a', 'b'),
-     ('b', 'c'),
-     ('c', '
')]
+    [('
',), ('
', 'a'), ('a',), ('a', 'b'), ('b',), ('b', 'c'), ('c',), ('c', '
'), ('
',)]
 
 We are almost ready to start counting ngrams, just one more step left.
 During training and evaluation our model will rely on a vocabulary that
diff --git a/nltk/util.py b/nltk/util.py
index 999625aa7..3d79c67e5 100644
--- a/nltk/util.py
+++ b/nltk/util.py
@@ -471,14 +471,7 @@ def pad_sequence(
 # add a flag to pad the sequence so we get peripheral ngrams?
 
 
-def ngrams(
-    sequence,
-    n,
-    pad_left=False,
-    pad_right=False,
-    left_pad_symbol=None,
-    right_pad_symbol=None,
-):
+def ngrams(sequence, n, **kwargs):
     """
     Return the ngrams generated from a sequence of items, as an iterator.
     For example:
@@ -514,24 +507,16 @@ def ngrams(
     :type right_pad_symbol: any
     :rtype: sequence or iter
     """
-    sequence = pad_sequence(
-        sequence, n, pad_left, pad_right, left_pad_symbol, right_pad_symbol
-    )
+    sequence = pad_sequence(sequence, n, **kwargs)
+    
+    # Creates the sliding window, of n no. of items.
+    # `iterables` is a tuple of iterables where each iterable is a window of n items.
+    iterables = tee(sequence, n)
 
-    history = []
-    while n > 1:
-        # PEP 479, prevent RuntimeError from being raised when StopIteration bubbles out of generator
-        try:
-            next_item = next(sequence)
-        except StopIteration:
-            # no more data, terminate the generator
-            return
-        history.append(next_item)
-        n -= 1
-    for item in sequence:
-        history.append(item)
-        yield tuple(history)
-        del history[0]
+    for i, sub_iterable in enumerate(iterables): # For each window,
+        for _ in range(i):                       # iterate through every order of ngrams
+            next(sub_iterable, None)             # generate the ngrams within the window.
+    return zip(*iterables) # Unpack and flattens the iterables.
 
 
 def bigrams(sequence, **kwargs):
@@ -574,30 +559,64 @@ def trigrams(sequence, **kwargs):
         yield item
 
 
-def everygrams(sequence, min_len=1, max_len=-1, **kwargs):
+def everygrams(sequence, min_len=1, max_len=-1, pad_left=False, pad_right=False, **kwargs):
     """
     Returns all possible ngrams generated from a sequence of items, as an iterator.
 
         >>> sent = 'a b c'.split()
+
+    New version outputs for everygrams.
         >>> list(everygrams(sent))
+        [('a',), ('a', 'b'), ('a', 'b', 'c'), ('b',), ('b', 'c'), ('c',)]
+
+    Old version outputs for everygrams.
+        >>> sorted(everygrams(sent), key=len)
         [('a',), ('b',), ('c',), ('a', 'b'), ('b', 'c'), ('a', 'b', 'c')]
+
         >>> list(everygrams(sent, max_len=2))
-        [('a',), ('b',), ('c',), ('a', 'b'), ('b', 'c')]
+        [('a',), ('a', 'b'), ('b',), ('b', 'c'), ('c',)]
 
-    :param sequence: the source data to be converted into trigrams
+    :param sequence: the source data to be converted into ngrams. If max_len is
+        not provided, this sequence will be loaded into memory
     :type sequence: sequence or iter
     :param min_len: minimum length of the ngrams, aka. n-gram order/degree of ngram
     :type  min_len: int
     :param max_len: maximum length of the ngrams (set to length of sequence by default)
     :type  max_len: int
+    :param pad_left: whether the ngrams should be left-padded
+    :type pad_left: bool
+    :param pad_right: whether the ngrams should be right-padded
+    :type pad_right: bool
     :rtype: iter(tuple)
     """
 
+    # Get max_len for padding.
     if max_len == -1:
-        max_len = len(sequence)
-    for n in range(min_len, max_len + 1):
-        for ng in ngrams(sequence, n, **kwargs):
-            yield ng
+        try:
+            max_len = len(sequence)
+        except TypeError:
+            sequence = list(sequence)
+            max_len = len(sequence)
+
+    # Pad if indicated using max_len.
+    sequence = pad_sequence(sequence, max_len, pad_left, pad_right, **kwargs)
+
+    # Sliding window to store grams.
+    history = list(islice(sequence, max_len))
+
+    # Yield ngrams from sequence.
+    while history:
+        for ngram_len in range(min_len, len(history)+1):
+            yield tuple(history[:ngram_len])
+
+        # Append element to history if sequence has more items.
+        try:
+            history.append(next(sequence))
+        except StopIteration:
+            pass
+
+        del history[0]
+
 
 
 def skipgrams(sequence, n, k, **kwargs):


Test patch:
diff --git a/nltk/test/unit/lm/test_preprocessing.py b/nltk/test/unit/lm/test_preprocessing.py
index c29855263..76e062792 100644
--- a/nltk/test/unit/lm/test_preprocessing.py
+++ b/nltk/test/unit/lm/test_preprocessing.py
@@ -14,15 +14,15 @@ class TestPreprocessing(unittest.TestCase):
         expected_train = [
             [
                 ("
",),
-                ("a",),
-                ("b",),
-                ("c",),
-                ("
",),
                 ("
", "a"),
+                ("a",),
                 ("a", "b"),
+                ("b",),
                 ("b", "c"),
+                ("c",),
                 ("c", "
"),
-            ]
+                ("
",)
+             ]
         ]
         expected_vocab = ["
", "a", "b", "c", "
"]
         train_data, vocab_data = padded_everygram_pipeline(2, [["a", "b", "c"]])
diff --git a/nltk/test/unit/test_util.py b/nltk/test/unit/test_util.py
new file mode 100644
index 000000000..909dfecf7
--- /dev/null
+++ b/nltk/test/unit/test_util.py
@@ -0,0 +1,72 @@
+# -*- coding: utf-8 -*-
+"""
+Unit tests for nltk.util.
+"""
+
+import unittest
+from nltk.util import everygrams
+
+
+class TestEverygrams(unittest.TestCase):
+
+    def setUp(self):
+        """Form test data for tests."""
+        self.test_data = iter('a b c'.split())
+
+    def test_everygrams_without_padding(self):
+        expected_output = [
+            ('a',),
+            ('a', 'b'),
+            ('a', 'b', 'c'),
+            ('b',),
+            ('b', 'c'),
+            ('c',),
+        ]
+        output = everygrams(self.test_data)
+        self.assertCountEqual(output, expected_output)
+
+    def test_everygrams_max_len(self):
+        expected_output = [('a',), ('a', 'b'), ('b',), ('b', 'c'),('c',),]
+        output = everygrams(self.test_data, max_len=2)
+        self.assertCountEqual(output, expected_output)
+
+    def test_everygrams_min_len(self):
+        expected_output = [('a', 'b'), ('b', 'c'), ('a', 'b', 'c'),]
+        output = everygrams(self.test_data, min_len=2)
+        self.assertCountEqual(output, expected_output)
+
+    def test_everygrams_pad_right(self):
+        expected_output = [
+            ('a',),
+            ('a', 'b'),
+            ('a', 'b', 'c'),
+            ('b',),
+            ('b', 'c'),
+            ('b', 'c', None),
+            ('c',),
+            ('c', None),
+            ('c', None, None),
+            (None,),
+            (None, None),
+            (None,),
+        ]
+        output = everygrams(self.test_data, max_len=3, pad_right=True)
+        self.assertCountEqual(output, expected_output)
+
+    def test_everygrams_pad_left(self):
+        expected_output = [
+            (None,),
+            (None, None),
+            (None, None, 'a'),
+            (None,),
+            (None, 'a'),
+            (None, 'a', 'b'),
+            ('a',),
+            ('a', 'b'),
+            ('a', 'b', 'c'),
+            ('b',),
+            ('b', 'c'),
+            ('c',),
+        ]
+        output = everygrams(self.test_data, max_len=3, pad_left=True)
+        self.assertCountEqual(output, expected_output)