Coverage for nltk.util : 67%
Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
|
# Natural Language Toolkit: Utility functions # # Copyright (C) 2001-2012 NLTK Project # Author: Steven Bird <sb@csse.unimelb.edu.au> # URL: <http://www.nltk.org/> # For license information, see LICENSE.TXT
###################################################################### # Short usage message ######################################################################
obj = obj.__class__
(defaults is None or len(args)>len(defaults))): args, varargs, varkw, defaults) initial_indent=' - ', subsequent_indent=' '*(len(name)+5)))
########################################################################## # IDLE ##########################################################################
""" Return True if this function is run within idle. Tkinter programs that are run in idle should never call ``Tk.mainloop``; so this function should be used to gate all calls to ``Tk.mainloop``.
:warning: This function works by checking ``sys.stdin``. If the user has modified ``sys.stdin``, then it may return incorrect results. :rtype: bool """ import sys, types return (isinstance(sys.stdin, types.InstanceType) and sys.stdin.__class__.__name__ == 'PyShell')
########################################################################## # PRETTY PRINTING ##########################################################################
""" Pretty print a sequence of data items
:param data: the data stream to print :type data: sequence or iter :param start: the start position :type start: int :param end: the end position :type end: int """ pprint(list(islice(data, start, end)))
""" Pretty print a string, breaking lines on whitespace
:param s: the string to print, consisting of words and spaces :type s: str :param width: the display width :type width: int """
""" Pretty print a list of text tokens, breaking lines on whitespace
:param tokens: the tokens to print :type tokens: list :param separator: the string to use to separate tokens :type separator: str :param width: the display width (default=70) :type width: int """
########################################################################## # Indexing ##########################################################################
defaultdict.__init__(self, list) for key, value in pairs: self[key].append(value)
###################################################################### ## Regexp display (thanks to David Mertz) ######################################################################
""" Return a string with markers surrounding the matched substrings. Search str for substrings matching ``regexp`` and wrap the matches with braces. This is convenient for learning about regular expressions.
:param regexp: The regular expression. :type regexp: str :param string: The string being matched. :type string: str :param left: The left delimiter (printed before the matched substring) :type left: str :param right: The right delimiter (printed after the matched substring) :type right: str :rtype: str """
########################################################################## # READ FROM FILE OR STRING ##########################################################################
# recipe from David Mertz if hasattr(f, 'read'): return f.read() elif isinstance(f, string_types): return open(f).read() else: raise ValueError("Must be called with a filename or file-like object")
########################################################################## # Breadth-First Search ##########################################################################
"""Traverse the nodes of a tree in breadth-first order. (No need to check for cycles.) The first argument should be the tree root; children should be a function taking as argument a tree node and returning an iterator of the node's children. """
########################################################################## # Guess Character Encoding ##########################################################################
# adapted from io.py in the docutils extension module (http://docutils.sourceforge.net) # http://www.pyzine.com/Issue008/Section_Articles/article_Encodings.html
""" Given a byte string, attempt to decode it. Tries the standard 'UTF8' and 'latin-1' encodings, Plus several gathered from locale information.
The calling program *must* first call::
locale.setlocale(locale.LC_ALL, '')
If successful it returns ``(decoded_unicode, successful_encoding)``. If unsuccessful it raises a ``UnicodeError``. """ successful_encoding = None # we make 'utf-8' the first encoding encodings = ['utf-8'] # # next we add anything we can learn from the locale try: encodings.append(locale.nl_langinfo(locale.CODESET)) except AttributeError: pass try: encodings.append(locale.getlocale()[1]) except (AttributeError, IndexError): pass try: encodings.append(locale.getdefaultlocale()[1]) except (AttributeError, IndexError): pass # # we try 'latin-1' last encodings.append('latin-1') for enc in encodings: # some of the locale calls # may have returned None if not enc: continue try: decoded = text_type(data, enc) successful_encoding = enc
except (UnicodeError, LookupError): pass else: break if not successful_encoding: raise UnicodeError( 'Unable to decode input data. Tried the following encodings: %s.' % ', '.join([repr(enc) for enc in encodings if enc])) else: return (decoded, successful_encoding)
########################################################################## # Invert a dictionary ##########################################################################
else:
########################################################################## # Utilities for directed graphs: transitive closure, and inversion # The graph is represented as a dictionary of sets ##########################################################################
""" Calculate the transitive closure of a directed graph, optionally the reflexive transitive closure.
The algorithm is a slight modification of the "Marking Algorithm" of Ioannidis & Ramakrishnan (1998) "Efficient Transitive Closure Algorithms".
:param graph: the initial graph, represented as a dictionary of sets :type graph: dict(set) :param reflexive: if set, also make the closure reflexive :type reflexive: bool :rtype: dict(set) """ else: base_set = lambda k: set() # The graph U_i in the article: # The graph M_i in the article:
""" Inverts a directed graph.
:param graph: the graph, represented as a dictionary of sets :type graph: dict(set) :return: the inverted graph :rtype: dict(set) """
########################################################################## # HTML Cleaning ##########################################################################
""" Remove HTML markup from the given string.
:param html: the HTML string to be cleaned :type html: str :rtype: str """
# First we remove inline JavaScript/CSS: # Then we remove html comments. This has to be done before removing regular # tags since comments can contain '>' characters. # Next we can remove the remaining tags: # Finally, we deal with whitespace
html = compat.urlopen(url).read() return clean_html(html)
########################################################################## # FLATTEN LISTS ##########################################################################
""" Flatten a list.
>>> from nltk.util import flatten >>> flatten(1, 2, ['b', 'a' , ['c', 'd']], 3) [1, 2, 'b', 'a', 'c', 'd', 3]
:param args: items and lists to be combined into a single list :rtype: list """
else:
########################################################################## # Ngram iteration ##########################################################################
# add a flag to pad the sequence so we get peripheral ngrams?
""" Return a sequence of ngrams from a sequence of items. For example:
>>> from nltk.util import ngrams >>> ngrams([1,2,3,4,5], 3) [(1, 2, 3), (2, 3, 4), (3, 4, 5)]
Use ingram for an iterator version of this function. Set pad_left or pad_right to true in order to get additional ngrams:
>>> ngrams([1,2,3,4,5], 2, pad_right=True) [(1, 2), (2, 3), (3, 4), (4, 5), (5, None)]
:param sequence: the source data to be converted into ngrams :type sequence: sequence or iter :param n: the degree of the ngrams :type n: 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 :param pad_symbol: the symbol to use for padding (default is None) :type pad_symbol: any :rtype: list(tuple) """
sequence = chain((pad_symbol,) * (n-1), sequence)
""" Return a sequence of bigrams from a sequence of items. For example:
>>> from nltk.util import bigrams >>> bigrams([1,2,3,4,5]) [(1, 2), (2, 3), (3, 4), (4, 5)]
Use ibigrams for an iterator version of this function.
:param sequence: the source data to be converted into bigrams :type sequence: sequence or iter :rtype: list(tuple) """
""" Return a sequence of trigrams from a sequence of items. For example:
>>> from nltk.util import trigrams >>> trigrams([1,2,3,4,5]) [(1, 2, 3), (2, 3, 4), (3, 4, 5)]
Use itrigrams for an iterator version of this function.
:param sequence: the source data to be converted into trigrams :type sequence: sequence or iter :rtype: list(tuple) """
""" Return the ngrams generated from a sequence of items, as an iterator. For example:
>>> from nltk.util import ingrams >>> list(ingrams([1,2,3,4,5], 3)) [(1, 2, 3), (2, 3, 4), (3, 4, 5)]
Use ngrams for a list version of this function. Set pad_left or pad_right to true in order to get additional ngrams:
>>> list(ingrams([1,2,3,4,5], 2, pad_right=True)) [(1, 2), (2, 3), (3, 4), (4, 5), (5, None)]
:param sequence: the source data to be converted into ngrams :type sequence: sequence or iter :param n: the degree of the ngrams :type n: 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 :param pad_symbol: the symbol to use for padding (default is None) :type pad_symbol: any :rtype: iter(tuple) """
sequence = chain((pad_symbol,) * (n-1), sequence)
""" Return the bigrams generated from a sequence of items, as an iterator. For example:
>>> from nltk.util import ibigrams >>> list(ibigrams([1,2,3,4,5])) [(1, 2), (2, 3), (3, 4), (4, 5)]
Use bigrams for a list version of this function.
:param sequence: the source data to be converted into bigrams :type sequence: sequence or iter :rtype: iter(tuple) """
""" Return the trigrams generated from a sequence of items, as an iterator. For example:
>>> from nltk.util import itrigrams >>> list(itrigrams([1,2,3,4,5])) [(1, 2, 3), (2, 3, 4), (3, 4, 5)]
Use trigrams for a list version of this function.
:param sequence: the source data to be converted into trigrams :type sequence: sequence or iter :rtype: iter(tuple) """
########################################################################## # Ordered Dictionary ##########################################################################
else:
dict.__delitem__(self, key) self._keys.remove(key)
except KeyError: return self.__missing__(key)
return (key for key in self.keys())
if not self._default_factory and key not in self._keys: raise KeyError() else: return self._default_factory()
dict.clear(self) self._keys.clear()
d = dict.copy(self) d._keys = self._keys return d
# returns iterator under python 3 and list under python 2 return zip(self.keys(), self.values())
assert isinstance(keys, list) assert len(data) == len(keys) return keys else: isinstance(data, OrderedDict) or \ isinstance(data, list) elif isinstance(data, list): return [key for (key, value) in data] else:
if self._keys: key = self._keys.pop() value = self[key] del self[key] return (key, value) else: raise KeyError()
dict.setdefault(self, key, failobj) if key not in self._keys: self._keys.append(key)
dict.update(self, data) for key in self.keys(data): if key not in self._keys: self._keys.append(key)
# 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. """ raise NotImplementedError('should be implemented by subclass')
""" 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. """ raise NotImplementedError('should be implemented by subclass')
""" Return the *i* th token in the corpus file underlying this corpus view. Negative indices and spans are both supported. """ else: # Handle negative indices # Use iterate_from to extract it. raise IndexError('index out of range')
"""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 sum(1 for elt in self if elt==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 = 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')
"""Return true if this list contains ``value``.""" return bool(self.count(value))
"""Return a list concatenating self with other.""" return LazyConcatenation([self, other])
"""Return a list concatenating other with self.""" return LazyConcatenation([other, self])
"""Return a list concatenating self with itself ``count`` times.""" return LazyConcatenation([self] * count)
"""Return a list concatenating self with itself ``count`` times.""" return LazyConcatenation([self] * 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. """ else: return '[%s]' % ', '.join(pieces)
""" Return a number indicating how ``self`` relates to other.
- If ``other`` is not a corpus view or a list, return -1. - Otherwise, return ``cmp(list(self), list(other))``.
Note: corpus views do not compare equal to tuples containing equal elements. Otherwise, transitivity would be violated, since tuples do not compare equal to lists. """ if not isinstance(other, (AbstractLazySequence, list)): return -1 return cmp(list(self), list(other))
""" :raise ValueError: Corpus view objects are unhashable. """ raise ValueError('%s objects are unhashable' % self.__class__.__name__)
""" 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. else:
max(0, len(self)-start))
""" 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. """
else:
# Construct an iterator over the sublists. else:
'offests not monotonic increasing!') else: 'inconsistent list value (num elts)')
""" 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.util import LazyMap >>> function = str >>> sequence = [1,2,3] >>> map(function, sequence) ['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) """ raise TypeError('LazyMap requires at least two args')
else: self._cache = None
# 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. for lst in lists) == len(lists)
# Special case: one lazy sublist for value in self._lists[0].iterate_from(index): yield self._func(value) return
# Special case: one non-lazy sublist
# Special case: n lazy sublists 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
# general case else: 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
if isinstance(index, slice): sliced_lists = [lst[index] for lst in self._lists] return LazyMap(self._func, *sliced_lists) else: # Handle negative indices if index < 0: index += len(self) if index < 0: raise IndexError('index out of range') # Check the cache if self._cache is not None and index in self._cache: return self._cache[index] # Calculate the value try: val = next(self.iterate_from(index)) except StopIteration: raise IndexError('index out of range') # Update the cache if self._cache is not None: if len(self._cache) > self._cache_size: self._cache.popitem() # discard random entry self._cache[index] = val # Return the value return val
""" 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.util import LazyZip >>> sequence1, sequence2 = [1, 2, 3], ['a', 'b', 'c'] >>> zip(sequence1, sequence2) [(1, 'a'), (2, 'b'), (3, 'c')] >>> list(LazyZip(sequence1, sequence2)) [(1, 'a'), (2, 'b'), (3, 'c')] >>> sequences = [sequence1, sequence2, [6,7,8,9]] >>> 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 ontaining 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.util 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 """
###################################################################### # Binary Search in a File ######################################################################
# inherited from pywordnet, by Oliver Steele """ Return the line from the file with first word key. Searches through a sorted file using the binary search algorithm.
:type file: file :param file: the file to be searched through. :type key: str :param key: the identifier we are searching for. """
else: file.seek(0, 2) end = file.tell() - 1 file.seek(0)
offset, line = cache[middle]
else: # at EOF; try to find start of the last line middle = (start + middle)/2 if middle == end -1: return None cache[middle] = (offset, line)
# Detects the condition where we're searching past the end # of the file, which is otherwise difficult to detect return None
###################################################################### # Proxy configuration ######################################################################
""" Set the HTTP proxy for Python to download through.
If ``proxy`` is None then tries to set proxy from environment or system settings.
:param proxy: The HTTP proxy server to use. For example: 'http://proxy.example.com:3128/' :param user: The username to authenticate with. Use None to disable authentication. :param password: The password to authenticate with. """ from nltk import compat
if proxy is None: # Try and find the system proxy settings try: proxy = compat.getproxies()['http'] except KeyError: raise ValueError('Could not detect default proxy settings')
# Set up the proxy handler proxy_handler = compat.ProxyHandler({'http': proxy}) opener = compat.build_opener(proxy_handler)
if user is not None: # Set up basic proxy authentication if provided password_manager = compat.HTTPPasswordMgrWithDefaultRealm() password_manager.add_password(realm=None, uri=proxy, user=user, passwd=password) opener.add_handler(compat.ProxyBasicAuthHandler(password_manager)) opener.add_handler(compat.ProxyDigestAuthHandler(password_manager))
# Overide the existing url opener compat.install_opener(opener) |