natural language toolkit collections c 20012023 nltk project steven bird stevenbird1gmail com url https www nltk org for license information see license txt this unused import is for python 2 7 ordered dictionary returns iterator under python 3 and list under python 2 returns iterator under python 3 lazy sequences an abstract base class for readonly sequences whose values are computed as needed lazy sequences act like tuples they can be indexed sliced and iterated over but they may not be modified the most common application of lazy sequences in nltk is for corpus view objects which provide access to the contents of a corpus without loading the entire corpus into memory by loading pieces of the corpus from disk as needed the result of modifying a mutable element of a lazy sequence is undefined in particular the modifications made to the element may or may not persist depending on whether and when the lazy sequence caches that element s value or reconstructs it from scratch subclasses are required to define two methods len and iteratefrom return the number of tokens in the corpus file underlying this corpus view return an iterator that generates the tokens in the corpus file underlying this corpus view starting at the token number start if startlenself then this iterator will generate no tokens return the i th token in the corpus file underlying this corpus view negative indices and spans are both supported handle negative indices use iteratefrom to extract it return an iterator that generates the tokens in the corpus file underlying this corpus view return self iteratefrom0 def countself value return the index of the first occurrence of value in this list that is greater than or equal to start and less than stop negative start and stop values are treated like negative slice bounds i e they count from the end of the list start stop sliceboundsself slicestart stop for i elt in enumerateisliceself start stop if elt value return i start raise valueerrorindexx x not in list def containsself value return a list concatenating self with other return lazyconcatenationself other def raddself other return a list concatenating self with itself count times return lazyconcatenationself count def rmulself count return a string representation for this corpus view that is similar to a list s representation but if it would be more than 60 characters long it is truncated raise valueerror corpus view objects are unhashable a subsequence produced by slicing a lazy sequence this slice keeps a reference to its source sequence and generates its values by looking them up in the source sequence the minimum size for which lazy slices should be created if lazysubsequence is called with a subsequence that is shorter than minsize then a tuple will be returned instead construct a new slice from a given underlying sequence the start and stop indices should be absolute indices i e they should not be negative for indexing from the back of a list or greater than the length of source if the slice is small enough just use a tuple a lazy sequence formed by concatenating a list of lists this underlying list of lists may itself be lazy lazyconcatenation maintains an index that it uses to keep track of the relationship between offsets in the concatenated lists and offsets in the sublists construct an iterator over the sublists a lazy sequence whose elements are formed by applying a given function to each element in one or more underlying lists the function is applied lazily i e when you read a value from the list lazymap will calculate that value by applying its function to the underlying lists values lazymap is essentially a lazy version of the python primitive function map in particular the following two expressions are equivalent from nltk collections import lazymap function str sequence 1 2 3 mapfunction sequence doctest skip 1 2 3 listlazymapfunction sequence 1 2 3 like the python map primitive if the source lists do not have equal size then the value none will be supplied for the missing elements lazy maps can be useful for conserving memory in cases where individual values take up a lot of space this is especially true if the underlying list s values are constructed lazily as is the case with many corpus readers a typical example of a use case for this class is performing feature detection on the tokens in a corpus since featuresets are encoded as dictionaries which can take up a lot of memory using a lazymap can significantly reduce memory usage when training and running classifiers param function the function that should be applied to elements of lists it should take as many arguments as there are lists param lists the underlying lists param cachesize determines the size of the cache used by this lazy map default5 if you just take bool of sum here alllazy will be true just in case n 1 list is an abstractlazysequence presumably this isn t what s intended special case one lazy sublist special case one nonlazy sublist special case n lazy sublists general case handle negative indices check the cache calculate the value update the cache return the value a lazy sequence whose elements are tuples each containing the ith element from each of the argument sequences the returned list is truncated in length to the length of the shortest argument sequence the tuples are constructed lazily i e when you read a value from the list lazyzip will calculate that value by forming a tuple from the ith element of each of the argument sequences lazyzip is essentially a lazy version of the python primitive function zip in particular an evaluated lazyzip is equivalent to a zip from nltk collections import lazyzip sequence1 sequence2 1 2 3 a b c zipsequence1 sequence2 doctest skip 1 a 2 b 3 c listlazyzipsequence1 sequence2 1 a 2 b 3 c sequences sequence1 sequence2 6 7 8 9 listzipsequences listlazyzipsequences true lazy zips can be useful for conserving memory in cases where the argument sequences are particularly long a typical example of a use case for this class is combining long sequences of gold standard and predicted values in a classification or tagging task in order to calculate accuracy by constructing tuples lazily and avoiding the creation of an additional long sequence memory usage can be significantly reduced param lists the underlying lists type lists listlist a lazy sequence whose elements are tuples each containing a count from zero and a value yielded by underlying sequence lazyenumerate is useful for obtaining an indexed list the tuples are constructed lazily i e when you read a value from the list lazyenumerate will calculate that value by forming a tuple from the count of the ith element and the ith element of the underlying sequence lazyenumerate is essentially a lazy version of the python primitive function enumerate in particular the following two expressions are equivalent from nltk collections import lazyenumerate sequence first second third listenumeratesequence 0 first 1 second 2 third listlazyenumeratesequence 0 first 1 second 2 third lazy enumerations can be useful for conserving memory in cases where the argument sequences are particularly long a typical example of a use case for this class is obtaining an indexed list for a long sequence of values by constructing tuples lazily and avoiding the creation of an additional long sequence memory usage can be significantly reduced param lst the underlying list type lst list wraps an iterator loading its elements on demand and making them subscriptable repr displays only the first few elements create a new iterator over this list starting at the given offset while lenself cache start v nextself it self cache appendv i start while i lenself cache yield self cachei i 1 try while true v nextself it self cache appendv yield v except stopiteration pass def addself other return a list concatenating other with self return typeselfchainother self trie implementation class triedict builds a trie object which is built around a dict if strings is provided it will add the strings which consist of a list of strings to the trie otherwise it ll construct an empty trie param strings list of strings to insert into the trie default is none type strings liststr inserts string into the trie param string string to insert into the trie type string str example from nltk collections import trie trie trieabc def expected a b c true none d e f true none trie expected true mark the string is complete natural language toolkit collections c 2001 2023 nltk project steven bird stevenbird1 gmail com url https www nltk org for license information see license txt this unused import is for python 2 7 ordered dictionary returns iterator under python 3 and list under python 2 returns iterator under python 3 lazy sequences an abstract base class for read only sequences whose values are computed as needed lazy sequences act like tuples they can be indexed sliced and iterated over but they may not be modified the most common application of lazy sequences in nltk is for corpus view objects which provide access to the contents of a corpus without loading the entire corpus into memory by loading pieces of the corpus from disk as needed the result of modifying a mutable element of a lazy sequence is undefined in particular the modifications made to the element may or may not persist depending on whether and when the lazy sequence caches that element s value or reconstructs it from scratch subclasses are required to define two methods __len__ and iterate_from return the number of tokens in the corpus file underlying this corpus view return an iterator that generates the tokens in the corpus file underlying this corpus view starting at the token number start if start len self then this iterator will generate no tokens return the i th token in the corpus file underlying this corpus view negative indices and spans are both supported handle negative indices use iterate_from to extract it return an iterator that generates the tokens in the corpus file underlying this corpus view return the number of times this list contains value return the index of the first occurrence of value in this list that is greater than or equal to start and less than stop negative start and stop values are treated like negative slice bounds i e they count from the end of the list return true if this list contains value return a list concatenating self with other return a list concatenating other with self return a list concatenating self with itself count times return a list concatenating self with itself count times return a string representation for this corpus view that is similar to a list s representation but if it would be more than 60 characters long it is truncated raise valueerror corpus view objects are unhashable a subsequence produced by slicing a lazy sequence this slice keeps a reference to its source sequence and generates its values by looking them up in the source sequence the minimum size for which lazy slices should be created if lazysubsequence is called with a subsequence that is shorter than min_size then a tuple will be returned instead construct a new slice from a given underlying sequence the start and stop indices should be absolute indices i e they should not be negative for indexing from the back of a list or greater than the length of source if the slice is small enough just use a tuple a lazy sequence formed by concatenating a list of lists this underlying list of lists may itself be lazy lazyconcatenation maintains an index that it uses to keep track of the relationship between offsets in the concatenated lists and offsets in the sublists construct an iterator over the sublists a lazy sequence whose elements are formed by applying a given function to each element in one or more underlying lists the function is applied lazily i e when you read a value from the list lazymap will calculate that value by applying its function to the underlying lists value s lazymap is essentially a lazy version of the python primitive function map in particular the following two expressions are equivalent from nltk collections import lazymap function str sequence 1 2 3 map function sequence doctest skip 1 2 3 list lazymap function sequence 1 2 3 like the python map primitive if the source lists do not have equal size then the value none will be supplied for the missing elements lazy maps can be useful for conserving memory in cases where individual values take up a lot of space this is especially true if the underlying list s values are constructed lazily as is the case with many corpus readers a typical example of a use case for this class is performing feature detection on the tokens in a corpus since featuresets are encoded as dictionaries which can take up a lot of memory using a lazymap can significantly reduce memory usage when training and running classifiers param function the function that should be applied to elements of lists it should take as many arguments as there are lists param lists the underlying lists param cache_size determines the size of the cache used by this lazy map default 5 if you just take bool of sum here _all_lazy will be true just in case n 1 list is an abstractlazysequence presumably this isn t what s intended special case one lazy sublist special case one non lazy sublist special case n lazy sublists fixme what is this except really catching stopiteration general case handle negative indices check the cache calculate the value update the cache discard random entry return the value a lazy sequence whose elements are tuples each containing the i th element from each of the argument sequences the returned list is truncated in length to the length of the shortest argument sequence the tuples are constructed lazily i e when you read a value from the list lazyzip will calculate that value by forming a tuple from the i th element of each of the argument sequences lazyzip is essentially a lazy version of the python primitive function zip in particular an evaluated lazyzip is equivalent to a zip from nltk collections import lazyzip sequence1 sequence2 1 2 3 a b c zip sequence1 sequence2 doctest skip 1 a 2 b 3 c list lazyzip sequence1 sequence2 1 a 2 b 3 c sequences sequence1 sequence2 6 7 8 9 list zip sequences list lazyzip sequences true lazy zips can be useful for conserving memory in cases where the argument sequences are particularly long a typical example of a use case for this class is combining long sequences of gold standard and predicted values in a classification or tagging task in order to calculate accuracy by constructing tuples lazily and avoiding the creation of an additional long sequence memory usage can be significantly reduced param lists the underlying lists type lists list list a lazy sequence whose elements are tuples each containing a count from zero and a value yielded by underlying sequence lazyenumerate is useful for obtaining an indexed list the tuples are constructed lazily i e when you read a value from the list lazyenumerate will calculate that value by forming a tuple from the count of the i th element and the i th element of the underlying sequence lazyenumerate is essentially a lazy version of the python primitive function enumerate in particular the following two expressions are equivalent from nltk collections import lazyenumerate sequence first second third list enumerate sequence 0 first 1 second 2 third list lazyenumerate sequence 0 first 1 second 2 third lazy enumerations can be useful for conserving memory in cases where the argument sequences are particularly long a typical example of a use case for this class is obtaining an indexed list for a long sequence of values by constructing tuples lazily and avoiding the creation of an additional long sequence memory usage can be significantly reduced param lst the underlying list type lst list wraps an iterator loading its elements on demand and making them subscriptable __repr__ displays only the first few elements create a new iterator over this list starting at the given offset return a list concatenating self with other return a list concatenating other with self trie implementation a trie implementation for strings builds a trie object which is built around a dict if strings is provided it will add the strings which consist of a list of strings to the trie otherwise it ll construct an empty trie param strings list of strings to insert into the trie default is none type strings list str inserts string into the trie param string string to insert into the trie type string str example from nltk collections import trie trie trie abc def expected a b c true none d e f true none trie expected true mark the string is complete
import bisect


from collections import Counter, defaultdict, deque
from functools import total_ordering
from itertools import chain, islice

from nltk.internals import raise_unorderable_types, slice_bounds






class OrderedDict(dict):
    def __init__(self, data=None, **kwargs):
        self._keys = self.keys(data, kwargs.get("keys"))
        self._default_factory = kwargs.get("default_factory")
        if data is None:
            dict.__init__(self)
        else:
            dict.__init__(self, data)

    def __delitem__(self, key):
        dict.__delitem__(self, key)
        self._keys.remove(key)

    def __getitem__(self, key):
        try:
            return dict.__getitem__(self, key)
        except KeyError:
            return self.__missing__(key)

    def __iter__(self):
        return (key for key in self.keys())

    def __missing__(self, key):
        if not self._default_factory and key not in self._keys:
            raise KeyError()
        return self._default_factory()

    def __setitem__(self, key, item):
        dict.__setitem__(self, key, item)
        if key not in self._keys:
            self._keys.append(key)

    def clear(self):
        dict.clear(self)
        self._keys.clear()

    def copy(self):
        d = dict.copy(self)
        d._keys = self._keys
        return d

    def items(self):
        
        return zip(self.keys(), self.values())

    def keys(self, data=None, keys=None):
        if data:
            if keys:
                assert isinstance(keys, list)
                assert len(data) == len(keys)
                return keys
            else:
                assert (
                    isinstance(data, dict)
                    or isinstance(data, OrderedDict)
                    or isinstance(data, list)
                )
                if isinstance(data, dict) or isinstance(data, OrderedDict):
                    return data.keys()
                elif isinstance(data, list):
                    return [key for (key, value) in data]
        elif "_keys" in self.__dict__:
            return self._keys
        else:
            return []

    def popitem(self):
        if not self._keys:
            raise KeyError()

        key = self._keys.pop()
        value = self[key]
        del self[key]
        return (key, value)

    def setdefault(self, key, failobj=None):
        dict.setdefault(self, key, failobj)
        if key not in self._keys:
            self._keys.append(key)

    def update(self, data):
        dict.update(self, data)
        for key in self.keys(data):
            if key not in self._keys:
                self._keys.append(key)

    def values(self):
        
        return map(self.get, self._keys)







@total_ordering
class AbstractLazySequence:
    

    def __len__(self):
        
        raise NotImplementedError("should be implemented by subclass")

    def iterate_from(self, start):
        
        raise NotImplementedError("should be implemented by subclass")

    def __getitem__(self, i):
        
        if isinstance(i, slice):
            start, stop = slice_bounds(self, i)
            return LazySubsequence(self, start, stop)
        else:
            
            if i < 0:
                i += len(self)
            if i < 0:
                raise IndexError("index out of range")
            
            try:
                return next(self.iterate_from(i))
            except StopIteration as e:
                raise IndexError("index out of range") from e

    def __iter__(self):
        
        return self.iterate_from(0)

    def count(self, value):
        
        return sum(1 for elt in self if elt == value)

    def index(self, value, start=None, stop=None):
        
        start, stop = slice_bounds(self, slice(start, stop))
        for i, elt in enumerate(islice(self, start, stop)):
            if elt == value:
                return i + start
        raise ValueError("index(x): x not in list")

    def __contains__(self, value):
        
        return bool(self.count(value))

    def __add__(self, other):
        
        return LazyConcatenation([self, other])

    def __radd__(self, other):
        
        return LazyConcatenation([other, self])

    def __mul__(self, count):
        
        return LazyConcatenation([self] * count)

    def __rmul__(self, count):
        
        return LazyConcatenation([self] * count)

    _MAX_REPR_SIZE = 60

    def __repr__(self):
        
        pieces = []
        length = 5
        for elt in self:
            pieces.append(repr(elt))
            length += len(pieces[-1]) + 2
            if length > self._MAX_REPR_SIZE and len(pieces) > 2:
                return "[%s, ...]" % ", ".join(pieces[:-1])
        return "[%s]" % ", ".join(pieces)

    def __eq__(self, other):
        return type(self) == type(other) and list(self) == list(other)

    def __ne__(self, other):
        return not self == other

    def __lt__(self, other):
        if type(other) != type(self):
            raise_unorderable_types("<", self, other)
        return list(self) < list(other)

    def __hash__(self):
        
        raise ValueError("%s objects are unhashable" % self.__class__.__name__)


class LazySubsequence(AbstractLazySequence):
    

    MIN_SIZE = 100
    

    def __new__(cls, source, start, stop):
        
        
        if stop - start < cls.MIN_SIZE:
            return list(islice(source.iterate_from(start), stop - start))
        else:
            return object.__new__(cls)

    def __init__(self, source, start, stop):
        self._source = source
        self._start = start
        self._stop = stop

    def __len__(self):
        return self._stop - self._start

    def iterate_from(self, start):
        return islice(
            self._source.iterate_from(start + self._start), max(0, len(self) - start)
        )


class LazyConcatenation(AbstractLazySequence):
    

    def __init__(self, list_of_lists):
        self._list = list_of_lists
        self._offsets = [0]

    def __len__(self):
        if len(self._offsets) <= len(self._list):
            for _ in self.iterate_from(self._offsets[-1]):
                pass
        return self._offsets[-1]

    def iterate_from(self, start_index):
        if start_index < self._offsets[-1]:
            sublist_index = bisect.bisect_right(self._offsets, start_index) - 1
        else:
            sublist_index = len(self._offsets) - 1

        index = self._offsets[sublist_index]

        
        if isinstance(self._list, AbstractLazySequence):
            sublist_iter = self._list.iterate_from(sublist_index)
        else:
            sublist_iter = islice(self._list, sublist_index, None)

        for sublist in sublist_iter:
            if sublist_index == (len(self._offsets) - 1):
                assert (
                    index + len(sublist) >= self._offsets[-1]
                ), "offsets not monotonic increasing!"
                self._offsets.append(index + len(sublist))
            else:
                assert self._offsets[sublist_index + 1] == index + len(
                    sublist
                ), "inconsistent list value (num elts)"

            yield from sublist[max(0, start_index - index) :]

            index += len(sublist)
            sublist_index += 1


class LazyMap(AbstractLazySequence):
    

    def __init__(self, function, *lists, **config):
        
        if not lists:
            raise TypeError("LazyMap requires at least two args")

        self._lists = lists
        self._func = function
        self._cache_size = config.get("cache_size", 5)
        self._cache = {} if self._cache_size > 0 else None

        
        
        
        self._all_lazy = sum(
            isinstance(lst, AbstractLazySequence) for lst in lists
        ) == len(lists)

    def iterate_from(self, index):
        
        if len(self._lists) == 1 and self._all_lazy:
            for value in self._lists[0].iterate_from(index):
                yield self._func(value)
            return

        
        elif len(self._lists) == 1:
            while True:
                try:
                    yield self._func(self._lists[0][index])
                except IndexError:
                    return
                index += 1

        
        elif self._all_lazy:
            iterators = [lst.iterate_from(index) for lst in self._lists]
            while True:
                elements = []
                for iterator in iterators:
                    try:
                        elements.append(next(iterator))
                    except:  
                        elements.append(None)
                if elements == [None] * len(self._lists):
                    return
                yield self._func(*elements)
                index += 1

        
        else:
            while True:
                try:
                    elements = [lst[index] for lst in self._lists]
                except IndexError:
                    elements = [None] * len(self._lists)
                    for i, lst in enumerate(self._lists):
                        try:
                            elements[i] = lst[index]
                        except IndexError:
                            pass
                    if elements == [None] * len(self._lists):
                        return
                yield self._func(*elements)
                index += 1

    def __getitem__(self, index):
        if isinstance(index, slice):
            sliced_lists = [lst[index] for lst in self._lists]
            return LazyMap(self._func, *sliced_lists)
        else:
            
            if index < 0:
                index += len(self)
            if index < 0:
                raise IndexError("index out of range")
            
            if self._cache is not None and index in self._cache:
                return self._cache[index]
            
            try:
                val = next(self.iterate_from(index))
            except StopIteration as e:
                raise IndexError("index out of range") from e
            
            if self._cache is not None:
                if len(self._cache) > self._cache_size:
                    self._cache.popitem()  
                self._cache[index] = val
            
            return val

    def __len__(self):
        return max(len(lst) for lst in self._lists)


class LazyZip(LazyMap):
    

    def __init__(self, *lists):
        
        LazyMap.__init__(self, lambda *elts: elts, *lists)

    def iterate_from(self, index):
        iterator = LazyMap.iterate_from(self, index)
        while index < len(self):
            yield next(iterator)
            index += 1
        return

    def __len__(self):
        return min(len(lst) for lst in self._lists)


class LazyEnumerate(LazyZip):
    

    def __init__(self, lst):
        
        LazyZip.__init__(self, range(len(lst)), lst)


class LazyIteratorList(AbstractLazySequence):
    

    def __init__(self, it, known_len=None):
        self._it = it
        self._len = known_len
        self._cache = []

    def __len__(self):
        if self._len:
            return self._len
        for _ in self.iterate_from(len(self._cache)):
            pass
        self._len = len(self._cache)
        return self._len

    def iterate_from(self, start):
        
        while len(self._cache) < start:
            v = next(self._it)
            self._cache.append(v)
        i = start
        while i < len(self._cache):
            yield self._cache[i]
            i += 1
        try:
            while True:
                v = next(self._it)
                self._cache.append(v)
                yield v
        except StopIteration:
            pass

    def __add__(self, other):
        
        return type(self)(chain(self, other))

    def __radd__(self, other):
        
        return type(self)(chain(other, self))





class Trie(dict):
    

    LEAF = True

    def __init__(self, strings=None):
        
        super().__init__()
        if strings:
            for string in strings:
                self.insert(string)

    def insert(self, string):
        
        if len(string):
            self[string[0]].insert(string[1:])
        else:
            
            self[Trie.LEAF] = None

    def __missing__(self, key):
        self[key] = Trie()
        return self[key]