natural language toolkit utility functions c 20012023 nltk project steven bird stevenbird1gmail com eric kafe kafe ericgmail com acyclic closures url https www nltk org for license information see license txt short usage message builtins sometimes don t support introspection 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 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 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 default70 type width int indexing 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 breadthfirst search traverse the nodes of a tree in breadthfirst order no 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 graph drawing yield the edges of a graph in breadthfirst order discarding eventual cycles the first argument should be the start node children should be a function taking as argument a graph node and returning an iterator of the node s children from nltk util import edgeclosure printlistedgeclosure a lambda node a b c b c c b node a b a c b c c b param edges the set or list of edges of a directed graph return dotstring a representation of edges as a string in the dot graph language which can be converted to an image by the dot program from the graphviz package or nltk parse dependencygraph dot2imgdotstring param shapes dictionary of strings that trigger a specified shape param attr dictionary with global graph attributes import nltk from nltk util import edges2dot printedges2dot a b a c b c c b digraph g a b a c b c c b blankline build a minimum spanning tree mst of an unweighted graph by traversing the nodes of a tree in breadthfirst order discarding eventual cycles return a representation of this mst as a string in the dot graph language which can be converted to an image by the dot program from the graphviz package or nltk parse dependencygraph dot2imgdotstring 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 import nltk wnnltk corpus wordnet from nltk util import unweightedminimumspanningdigraph as umsd printumsdwn synset bound a 01 lambda s s alsosees digraph g synset bound a 01 synset unfree a 02 synset unfree a 02 synset confined a 02 synset unfree a 02 synset dependent a 01 synset unfree a 02 synset restricted a 01 synset restricted a 01 synset classified a 02 blankline breadthfirst depthfirst searches with cycle detection traverse the nodes of a tree in breadthfirst order discarding eventual 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 traverse the nodes of a tree in depthfirst order discarding eventual cycles within any branch adding cutmark when specified if cycles were truncated 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 catches all cycles import nltk from nltk util import acyclicdepthfirst as acyclictree wnnltk corpus wordnet from pprint import pprint pprintacyclictreewn synset dog n 01 lambda s s hypernyms cutmark synset dog n 01 synset canine n 02 synset carnivore n 01 synset placental n 01 synset mammal n 01 synset vertebrate n 01 synset chordate n 01 synset animal n 01 synset organism n 01 synset livingthing n 01 synset whole n 02 synset object n 01 synset physicalentity n 01 synset entity n 01 synset domesticanimal n 01 cyclesynset animal n 01 3 recurse with a common traversed set for all children traverse the nodes of a tree in depthfirst order discarding eventual cycles within the same branch but keep duplicate paths in different branches add cutmark when defined if cycles were truncated 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 catches only only cycles within the same branch but keeping cycles from different branches import nltk from nltk util import acyclicbranchesdepthfirst as tree wnnltk corpus wordnet from pprint import pprint pprinttreewn synset certified a 01 lambda s s alsosees cutmark depth4 synset certified a 01 synset ized a 01 synset lawful a 01 synset legal a 01 cyclesynset lawful a 01 0 synset legitimate a 01 synset straight a 06 synset honest a 01 cyclesynset lawful a 01 0 synset legitimate a 01 cyclesynset ized a 01 1 synset legal a 01 synset lawful a 01 cyclesynset legitimate a 01 0 synset valid a 01 cyclesynset legitimate a 01 0 synset reasonable a 01 synset official a 01 cyclesynset ized a 01 1 synset documented a 01 recurse with a different traversed set for each child convert acyclic dictionary dic where the keys are nodes and the values are lists of children to output tree suitable for pprint starting at root node with subtrees as nested lists return node acyclicdic2treechild dic for child in dicnode def unweightedminimumspanningdicttree childreniter traversed set empty set of traversed nodes queue dequetree initialize queue agenda tree set of all nodes ever queued mstdic empty mst dictionary while queue node queue popleft node is not yet in the mst dictionary mstdicnode so add it with an empty list of children if node not in traversed avoid cycles traversed addnode for child in childrennode if child not in agenda queue nodes only once mstdicnode appendchild add child to the mst queue appendchild add child to queue agenda addchild return mstdic def unweightedminimumspanningtreetree childreniter return acyclicdic2treetree unweightedminimumspanningdicttree children guess character encoding adapted from io py in the docutils extension module https docutils sourceforge io http www pyzine comissue008sectionarticlesarticleencodings html def guessencodingdata successfulencoding none we make utf8 the first encoding encodings utf8 next we add anything we can learn from the locale try encodings appendlocale nllanginfolocale codeset except attributeerror pass try encodings appendlocale getlocale1 except attributeerror indexerror pass try encodings appendlocale getdefaultlocale1 except attributeerror indexerror pass we try latin1 last encodings appendlatin1 for enc in encodings some of the locale calls may have returned none if not enc continue try decoded strdata enc successfulencoding enc except unicodeerror lookuperror pass else break if not successfulencoding raise unicodeerror unable to decode input data tried the following encodings s joinreprenc for enc in encodings if enc else return decoded successfulencoding remove repeated elements from a list deterministcally def uniquelistxs seen set not seen addx here acts to make the code shorter without using if statements seen addx always returns none return x for x in xs if x not in seen and not seen addx invert a dictionary def invertdictd inverteddict defaultdictlist for key in d if hasattrdkey iter for term in dkey inverteddictterm appendkey else inverteddictdkey key return inverteddict utilities for directed graphs transitive closure and inversion the graph is represented as a dictionary of sets def transitiveclosuregraph reflexivefalse if reflexive baseset lambda k k else baseset lambda k set the graph ui in the article agendagraph k graphk copy for k in graph the graph mi in the article closuregraph k basesetk for k in graph for i in graph agenda agendagraphi closure closuregraphi while agenda j agenda pop closure addj closure closuregraph setdefaultj basesetj agenda agendagraph getj basesetj agenda closure return closuregraph def invertgraphgraph inverted for key in graph for value in graphkey inverted setdefaultvalue set addkey return inverted html cleaning def cleanhtmlhtml raise notimplementederror to remove html markup use beautifulsoup s gettext function def cleanurlurl raise notimplementederror to remove html markup use beautifulsoup s gettext function flatten lists def flattenargs x for l in args if not isinstancel list tuple l l for item in l if isinstanceitem list tuple x extendflattenitem else x appenditem return x ngram iteration def padsequence sequence n padleftfalse padrightfalse leftpadsymbolnone rightpadsymbolnone sequence itersequence if padleft sequence chainleftpadsymbol n 1 sequence if padright sequence chainsequence rightpadsymbol n 1 return sequence add a flag to pad the sequence so we get peripheral ngrams def ngramssequence n kwargs sequence padsequencesequence 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 teesequence n for i subiterable in enumerateiterables for each window for in rangei iterate through every order of ngrams nextsubiterable none generate the ngrams within the window return zipiterables unpack and flattens the iterables def bigramssequence kwargs yield from ngramssequence 2 kwargs def trigramssequence kwargs yield from ngramssequence 3 kwargs def everygrams sequence minlen1 maxlen1 padleftfalse padrightfalse kwargs get maxlen for padding if maxlen 1 try maxlen lensequence except typeerror sequence listsequence maxlen lensequence pad if indicated using maxlen sequence padsequencesequence maxlen padleft padright kwargs sliding window to store grams history listislicesequence maxlen yield ngrams from sequence while history for ngramlen in rangeminlen lenhistory 1 yield tuplehistory ngramlen append element to history if sequence has more items try history appendnextsequence except stopiteration pass del history0 def skipgramssequence n k kwargs pads the sequence as desired by kwargs if padleft in kwargs or padright in kwargs sequence padsequencesequence n kwargs note when iterating through the ngrams the padright here is not the kwargs padding it s for the algorithm to detect the sentinel object on the right pad to stop inner loop sentinel object for ngram in ngramssequence n k padrighttrue rightpadsymbolsentinel head ngram 1 tail ngram1 for skiptail in combinationstail n 1 if skiptail1 is sentinel continue yield head skiptail binary search in a file inherited from pywordnet by oliver steele def binarysearchfilefile key cachenone cachedepth1 key key keylen lenkey start 0 currentdepth 0 if hasattrfile name end os statfile name stsize 1 else file seek0 2 end file tell 1 file seek0 if cache is none cache while start end laststate start end middle start end 2 if cache getmiddle offset line cachemiddle else line while true file seekmax0 middle 1 if middle 0 file discardline offset file tell line file readline if line break at eof try to find start of the last line middle start middle 2 if middle end 1 return none if currentdepth cachedepth cachemiddle offset line if offset end assert end middle 1 infinite loop end middle 1 elif line keylen key return line elif line key assert end middle 1 infinite loop end middle 1 elif line key start offset lenline 1 currentdepth 1 thisstate start end if laststate thisstate detects the condition where we re searching past the end of the file which is otherwise difficult to detect return none return none proxy configuration def setproxyproxy usernone password if proxy is none try and find the system proxy settings try proxy getproxieshttp except keyerror as e raise valueerrorcould not detect default proxy settings from e set up the proxy handler proxyhandler proxyhandlerhttps proxy http proxy opener buildopenerproxyhandler if user is not none set up basic proxy authentication if provided passwordmanager httppasswordmgrwithdefaultrealm passwordmanager addpasswordrealmnone uriproxy useruser passwdpassword opener addhandlerproxybasicauthhandlerpasswordmanager opener addhandlerproxydigestauthhandlerpasswordmanager override the existing url opener installopeneropener elementtree pretty printing from https www effbot orgzoneelementlib htm def elementtreeindentelem level0 i n level if lenelem if not elem text or not elem text strip elem text i for elem in elem elementtreeindentelem level 1 if not elem tail or not elem tail strip elem tail i else if level and not elem tail or not elem tail strip elem tail i mathematical approximations def choosen k if 0 k n ntok ktok 1 1 for t in range1 mink n k 1 ntok n ktok t n 1 return ntok ktok else return 0 iteration utilities def pairwiseiterable parallelization natural language toolkit utility functions c 2001 2023 nltk project steven bird stevenbird1 gmail com eric kafe kafe eric gmail com acyclic closures url https www nltk org for license information see license txt short usage message in case it s lazy this will load it builtins sometimes don t support introspection 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 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 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 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 breadth first search traverse the nodes of a tree in breadth first order no 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 graph drawing yield the edges of a graph in breadth first order discarding eventual cycles the first argument should be the start node children should be a function taking as argument a graph node and returning an iterator of the node s children from nltk util import edge_closure print list edge_closure a lambda node a b c b c c b node a b a c b c c b param edges the set or list of edges of a directed graph return dot_string a representation of edges as a string in the dot graph language which can be converted to an image by the dot program from the graphviz package or nltk parse dependencygraph dot2img dot_string param shapes dictionary of strings that trigger a specified shape param attr dictionary with global graph attributes import nltk from nltk util import edges2dot print edges2dot a b a c b c c b digraph g a b a c b c c b blankline build a minimum spanning tree mst of an unweighted graph by traversing the nodes of a tree in breadth first order discarding eventual cycles return a representation of this mst as a string in the dot graph language which can be converted to an image by the dot program from the graphviz package or nltk parse dependencygraph dot2img dot_string 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 import nltk wn nltk corpus wordnet from nltk util import unweighted_minimum_spanning_digraph as umsd print umsd wn synset bound a 01 lambda s s also_sees digraph g synset bound a 01 synset unfree a 02 synset unfree a 02 synset confined a 02 synset unfree a 02 synset dependent a 01 synset unfree a 02 synset restricted a 01 synset restricted a 01 synset classified a 02 blankline breadth first depth first searches with cycle detection traverse the nodes of a tree in breadth first order discarding eventual 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 traverse the nodes of a tree in depth first order discarding eventual cycles within any branch adding cut_mark when specified if cycles were truncated 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 catches all cycles import nltk from nltk util import acyclic_depth_first as acyclic_tree wn nltk corpus wordnet from pprint import pprint pprint acyclic_tree wn synset dog n 01 lambda s s hypernyms cut_mark synset dog n 01 synset canine n 02 synset carnivore n 01 synset placental n 01 synset mammal n 01 synset vertebrate n 01 synset chordate n 01 synset animal n 01 synset organism n 01 synset living_thing n 01 synset whole n 02 synset object n 01 synset physical_entity n 01 synset entity n 01 synset domestic_animal n 01 cycle synset animal n 01 3 recurse with a common traversed set for all children traverse the nodes of a tree in depth first order discarding eventual cycles within the same branch but keep duplicate paths in different branches add cut_mark when defined if cycles were truncated 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 catches only only cycles within the same branch but keeping cycles from different branches import nltk from nltk util import acyclic_branches_depth_first as tree wn nltk corpus wordnet from pprint import pprint pprint tree wn synset certified a 01 lambda s s also_sees cut_mark depth 4 synset certified a 01 synset ized a 01 synset lawful a 01 synset legal a 01 cycle synset lawful a 01 0 synset legitimate a 01 synset straight a 06 synset honest a 01 cycle synset lawful a 01 0 synset legitimate a 01 cycle synset ized a 01 1 synset legal a 01 synset lawful a 01 cycle synset legitimate a 01 0 synset valid a 01 cycle synset legitimate a 01 0 synset reasonable a 01 synset official a 01 cycle synset ized a 01 1 synset documented a 01 recurse with a different traversed set for each child convert acyclic dictionary dic where the keys are nodes and the values are lists of children to output tree suitable for pprint starting at root node with subtrees as nested lists output a dictionary representing a minimum spanning tree mst of an unweighted graph by traversing the nodes of a tree in breadth first order discarding eventual 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 import nltk from nltk corpus import wordnet as wn from nltk util import unweighted_minimum_spanning_dict as umsd from pprint import pprint pprint umsd wn synset bound a 01 lambda s s also_sees synset bound a 01 synset unfree a 02 synset classified a 02 synset confined a 02 synset dependent a 01 synset restricted a 01 synset classified a 02 synset unfree a 02 synset confined a 02 synset dependent a 01 synset restricted a 01 empty set of traversed nodes initialize queue set of all nodes ever queued empty mst dictionary node is not yet in the mst dictionary so add it with an empty list of children avoid cycles queue nodes only once add child to the mst add child to queue output a minimum spanning tree mst of an unweighted graph by traversing the nodes of a tree in breadth first order discarding eventual 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 import nltk from nltk util import unweighted_minimum_spanning_tree as mst wn nltk corpus wordnet from pprint import pprint pprint mst wn synset bound a 01 lambda s s also_sees synset bound a 01 synset unfree a 02 synset confined a 02 synset dependent a 01 synset restricted a 01 synset classified a 02 guess character encoding adapted from io py in the docutils extension module https docutils sourceforge io 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 we make utf 8 the first encoding next we add anything we can learn from the locale we try latin 1 last some of the locale calls may have returned none remove repeated elements from a list deterministcally not seen add x here acts to make the code shorter without using if statements seen add x always returns none invert a dictionary 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 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 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 ngram iteration returns a padded sequence of items before ngram extraction list pad_sequence 1 2 3 4 5 2 pad_left true pad_right true left_pad_symbol s right_pad_symbol s s 1 2 3 4 5 s list pad_sequence 1 2 3 4 5 2 pad_left true left_pad_symbol s s 1 2 3 4 5 list pad_sequence 1 2 3 4 5 2 pad_right true right_pad_symbol s 1 2 3 4 5 s param sequence the source data to be padded 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 left_pad_symbol the symbol to use for left padding default is none type left_pad_symbol any param right_pad_symbol the symbol to use for right padding default is none type right_pad_symbol any rtype sequence or iter add a flag to pad the sequence so we get peripheral ngrams return the ngrams generated from a sequence of items as an iterator for example from nltk util import ngrams list ngrams 1 2 3 4 5 3 1 2 3 2 3 4 3 4 5 wrap with list for a list version of this function set pad_left or pad_right to true in order to get additional ngrams list ngrams 1 2 3 4 5 2 pad_right true 1 2 2 3 3 4 4 5 5 none list ngrams 1 2 3 4 5 2 pad_right true right_pad_symbol s 1 2 2 3 3 4 4 5 5 s list ngrams 1 2 3 4 5 2 pad_left true left_pad_symbol s s 1 1 2 2 3 3 4 4 5 list ngrams 1 2 3 4 5 2 pad_left true pad_right true left_pad_symbol s right_pad_symbol s s 1 1 2 2 3 3 4 4 5 5 s 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 left_pad_symbol the symbol to use for left padding default is none type left_pad_symbol any param right_pad_symbol the symbol to use for right padding default is none type right_pad_symbol any rtype sequence or iter creates the sliding window of n no of items iterables is a tuple of iterables where each iterable is a window of n items for each window iterate through every order of ngrams generate the ngrams within the window unpack and flattens the iterables return the bigrams generated from a sequence of items as an iterator for example from nltk util import bigrams list bigrams 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 trigrams list trigrams 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 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 a b b b c c 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 pad if indicated using max_len sliding window to store grams yield ngrams from sequence append element to history if sequence has more items returns all possible skipgrams generated from a sequence of items as an iterator skipgrams are ngrams that allows tokens to be skipped refer to http homepages inf ed ac uk ballison pdf lrec_skipgrams pdf sent insurgents killed in ongoing fighting split list skipgrams sent 2 2 insurgents killed insurgents in insurgents ongoing killed in killed ongoing killed fighting in ongoing in fighting ongoing fighting list skipgrams sent 3 2 insurgents killed in insurgents killed ongoing insurgents killed fighting insurgents in ongoing insurgents in fighting insurgents ongoing fighting killed in ongoing killed in fighting killed ongoing fighting in ongoing fighting param sequence the source data to be converted into trigrams type sequence sequence or iter param n the degree of the ngrams type n int param k the skip distance type k int rtype iter tuple pads the sequence as desired by kwargs note when iterating through the ngrams the pad_right here is not the kwargs padding it s for the algorithm to detect the sentinel object on the right pad to stop inner loop 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 at eof try to find start of the last line detects the condition where we re searching past the end of the file which is otherwise difficult to detect 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 try and find the system proxy settings set up the proxy handler set up basic proxy authentication if provided override the existing url opener elementtree pretty printing from https www effbot org zone element lib htm recursive function to indent an elementtree _elementinterface used for pretty printing run indent on elem and then output in the normal way param elem element to be indented will be modified type elem elementtree _elementinterface param level level of indentation for this element type level nonnegative integer rtype elementtree _elementinterface return contents of elem indented to reflect its structure mathematical approximations this function is a fast way to calculate binomial coefficients commonly known as nck i e the number of combinations of n things taken k at a time https en wikipedia org wiki binomial_coefficient this is the scipy special comb with long integer computation but this approximation is faster see https github com nltk nltk issues 1181 choose 4 2 6 choose 6 2 15 param n the number of things type n int param r the number of times a thing is taken type r int iteration utilities s s0 s1 s1 s2 s2 s3 parallelization
import inspect
import locale
import os
import pydoc
import re
import textwrap
import warnings
from collections import defaultdict, deque
from itertools import chain, combinations, islice, tee
from pprint import pprint
from urllib.request import (
    HTTPPasswordMgrWithDefaultRealm,
    ProxyBasicAuthHandler,
    ProxyDigestAuthHandler,
    ProxyHandler,
    build_opener,
    getproxies,
    install_opener,
)

from nltk.collections import *
from nltk.internals import deprecated, raise_unorderable_types, slice_bounds






@deprecated("Use help(obj) instead.")
def usage(obj):
    str(obj)  

    if not isinstance(obj, type):
        obj = obj.__class__

    print(f"{obj.__name__} supports the following operations:")
    for (name, method) in sorted(pydoc.allmethods(obj).items()):
        if name.startswith("_"):
            continue
        if getattr(method, "__deprecated__", False):
            continue

        try:
            sig = str(inspect.signature(method))
        except ValueError as e:
            
            if "builtin" in str(e):
                continue
            else:
                raise

        args = sig.lstrip("(").rstrip(")").split(", ")
        meth = inspect.getattr_static(obj, name)
        if isinstance(meth, (classmethod, staticmethod)):
            name = f"cls.{name}"
        elif args and args[0] == "self":
            name = f"self.{name}"
            args.pop(0)
        print(
            textwrap.fill(
                f"{name}({', '.join(args)})",
                initial_indent="  - ",
                subsequent_indent=" " * (len(name) + 5),
            )
        )







def in_idle():
    
    import sys

    return sys.stdin.__class__.__name__ in ("PyShell", "RPCProxy")







def pr(data, start=0, end=None):
    
    pprint(list(islice(data, start, end)))


def print_string(s, width=70):
    
    print("\n".join(textwrap.wrap(s, width=width)))


def tokenwrap(tokens, separator=" ", width=70):
    
    return "\n".join(textwrap.wrap(separator.join(tokens), width=width))







class Index(defaultdict):
    def __init__(self, pairs):
        defaultdict.__init__(self, list)
        for key, value in pairs:
            self[key].append(value)







def re_show(regexp, string, left="{", right="}"):
    
    print(re.compile(regexp, re.M).sub(left + r"\g<0>" + right, string.rstrip()))







def filestring(f):
    if hasattr(f, "read"):
        return f.read()
    elif isinstance(f, str):
        with open(f) as infile:
            return infile.read()
    else:
        raise ValueError("Must be called with a filename or file-like object")







def breadth_first(tree, children=iter, maxdepth=-1):
    
    queue = deque([(tree, 0)])

    while queue:
        node, depth = queue.popleft()
        yield node

        if depth != maxdepth:
            try:
                queue.extend((c, depth + 1) for c in children(node))
            except TypeError:
                pass







def edge_closure(tree, children=iter, maxdepth=-1, verbose=False):
    
    traversed = set()
    edges = set()
    queue = deque([(tree, 0)])
    while queue:
        node, depth = queue.popleft()
        traversed.add(node)
        if depth != maxdepth:
            try:
                for child in children(node):
                    if child not in traversed:
                        queue.append((child, depth + 1))
                    else:
                        if verbose:
                            warnings.warn(
                                f"Discarded redundant search for {child} at depth {depth + 1}",
                                stacklevel=2,
                            )
                    edge = (node, child)
                    if edge not in edges:
                        yield edge
                        edges.add(edge)
            except TypeError:
                pass


def edges2dot(edges, shapes=None, attr=None):
    
    if not shapes:
        shapes = dict()
    if not attr:
        attr = dict()

    dot_string = "digraph G {\n"

    for pair in attr.items():
        dot_string += f"{pair[0]} = {pair[1]};\n"

    for edge in edges:
        for shape in shapes.items():
            for node in range(2):
                if shape[0] in repr(edge[node]):
                    dot_string += f'"{edge[node]}" [shape = {shape[1]}];\n'
        dot_string += f'"{edge[0]}" -> "{edge[1]}";\n'

    dot_string += "}\n"
    return dot_string


def unweighted_minimum_spanning_digraph(tree, children=iter, shapes=None, attr=None):
    
    return edges2dot(
        edge_closure(
            tree, lambda node: unweighted_minimum_spanning_dict(tree, children)[node]
        ),
        shapes,
        attr,
    )







def acyclic_breadth_first(tree, children=iter, maxdepth=-1):
    
    traversed = set()
    queue = deque([(tree, 0)])
    while queue:
        node, depth = queue.popleft()
        yield node
        traversed.add(node)
        if depth != maxdepth:
            try:
                for child in children(node):
                    if child not in traversed:
                        queue.append((child, depth + 1))
                    else:
                        warnings.warn(
                            "Discarded redundant search for {} at depth {}".format(
                                child, depth + 1
                            ),
                            stacklevel=2,
                        )
            except TypeError:
                pass


def acyclic_depth_first(tree, children=iter, depth=-1, cut_mark=None, traversed=None):
    
    if traversed is None:
        traversed = {tree}
    out_tree = [tree]
    if depth != 0:
        try:
            for child in children(tree):
                if child not in traversed:
                    
                    traversed.add(child)
                    out_tree += [
                        acyclic_depth_first(
                            child, children, depth - 1, cut_mark, traversed
                        )
                    ]
                else:
                    warnings.warn(
                        "Discarded redundant search for {} at depth {}".format(
                            child, depth - 1
                        ),
                        stacklevel=3,
                    )
                    if cut_mark:
                        out_tree += [f"Cycle({child},{depth - 1},{cut_mark})"]
        except TypeError:
            pass
    elif cut_mark:
        out_tree += [cut_mark]
    return out_tree


def acyclic_branches_depth_first(
    tree, children=iter, depth=-1, cut_mark=None, traversed=None
):
    
    if traversed is None:
        traversed = {tree}
    out_tree = [tree]
    if depth != 0:
        try:
            for child in children(tree):
                if child not in traversed:
                    
                    out_tree += [
                        acyclic_branches_depth_first(
                            child,
                            children,
                            depth - 1,
                            cut_mark,
                            traversed.union({child}),
                        )
                    ]
                else:
                    warnings.warn(
                        "Discarded redundant search for {} at depth {}".format(
                            child, depth - 1
                        ),
                        stacklevel=3,
                    )
                    if cut_mark:
                        out_tree += [f"Cycle({child},{depth - 1},{cut_mark})"]
        except TypeError:
            pass
    elif cut_mark:
        out_tree += [cut_mark]
    return out_tree


def acyclic_dic2tree(node, dic):
    
    return [node] + [acyclic_dic2tree(child, dic) for child in dic[node]]


def unweighted_minimum_spanning_dict(tree, children=iter):
    
    traversed = set()  
    queue = deque([tree])  
    agenda = {tree}  
    mstdic = {}  
    while queue:
        node = queue.popleft()  
        mstdic[node] = []  
        if node not in traversed:  
            traversed.add(node)
            for child in children(node):
                if child not in agenda:  
                    mstdic[node].append(child)  
                    queue.append(child)  
                    agenda.add(child)
    return mstdic


def unweighted_minimum_spanning_tree(tree, children=iter):
    
    return acyclic_dic2tree(tree, unweighted_minimum_spanning_dict(tree, children))










def guess_encoding(data):
    
    successful_encoding = None
    
    encodings = ["utf-8"]
    
    
    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
    
    
    encodings.append("latin-1")
    for enc in encodings:
        
        
        if not enc:
            continue
        try:
            decoded = str(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)







def unique_list(xs):
    seen = set()
    
    return [x for x in xs if x not in seen and not seen.add(x)]







def invert_dict(d):
    inverted_dict = defaultdict(list)
    for key in d:
        if hasattr(d[key], "__iter__"):
            for term in d[key]:
                inverted_dict[term].append(key)
        else:
            inverted_dict[d[key]] = key
    return inverted_dict








def transitive_closure(graph, reflexive=False):
    
    if reflexive:
        base_set = lambda k: {k}
    else:
        base_set = lambda k: set()
    
    agenda_graph = {k: graph[k].copy() for k in graph}
    
    closure_graph = {k: base_set(k) for k in graph}
    for i in graph:
        agenda = agenda_graph[i]
        closure = closure_graph[i]
        while agenda:
            j = agenda.pop()
            closure.add(j)
            closure |= closure_graph.setdefault(j, base_set(j))
            agenda |= agenda_graph.get(j, base_set(j))
            agenda -= closure
    return closure_graph


def invert_graph(graph):
    
    inverted = {}
    for key in graph:
        for value in graph[key]:
            inverted.setdefault(value, set()).add(key)
    return inverted







def clean_html(html):
    raise NotImplementedError(
        "To remove HTML markup, use BeautifulSoup's get_text() function"
    )


def clean_url(url):
    raise NotImplementedError(
        "To remove HTML markup, use BeautifulSoup's get_text() function"
    )







def flatten(*args):
    

    x = []
    for l in args:
        if not isinstance(l, (list, tuple)):
            l = [l]
        for item in l:
            if isinstance(item, (list, tuple)):
                x.extend(flatten(item))
            else:
                x.append(item)
    return x







def pad_sequence(
    sequence,
    n,
    pad_left=False,
    pad_right=False,
    left_pad_symbol=None,
    right_pad_symbol=None,
):
    
    sequence = iter(sequence)
    if pad_left:
        sequence = chain((left_pad_symbol,) * (n - 1), sequence)
    if pad_right:
        sequence = chain(sequence, (right_pad_symbol,) * (n - 1))
    return sequence





def ngrams(sequence, n, **kwargs):
    
    sequence = pad_sequence(sequence, n, **kwargs)

    
    
    iterables = tee(sequence, n)

    for i, sub_iterable in enumerate(iterables):  
        for _ in range(i):  
            next(sub_iterable, None)  
    return zip(*iterables)  


def bigrams(sequence, **kwargs):
    

    yield from ngrams(sequence, 2, **kwargs)


def trigrams(sequence, **kwargs):
    

    yield from ngrams(sequence, 3, **kwargs)


def everygrams(
    sequence, min_len=1, max_len=-1, pad_left=False, pad_right=False, **kwargs
):
    

    
    if max_len == -1:
        try:
            max_len = len(sequence)
        except TypeError:
            sequence = list(sequence)
            max_len = len(sequence)

    
    sequence = pad_sequence(sequence, max_len, pad_left, pad_right, **kwargs)

    
    history = list(islice(sequence, max_len))

    
    while history:
        for ngram_len in range(min_len, len(history) + 1):
            yield tuple(history[:ngram_len])

        
        try:
            history.append(next(sequence))
        except StopIteration:
            pass

        del history[0]


def skipgrams(sequence, n, k, **kwargs):
    

    
    if "pad_left" in kwargs or "pad_right" in kwargs:
        sequence = pad_sequence(sequence, n, **kwargs)

    
    
    
    SENTINEL = object()
    for ngram in ngrams(sequence, n + k, pad_right=True, right_pad_symbol=SENTINEL):
        head = ngram[:1]
        tail = ngram[1:]
        for skip_tail in combinations(tail, n - 1):
            if skip_tail[-1] is SENTINEL:
                continue
            yield head + skip_tail







def binary_search_file(file, key, cache=None, cacheDepth=-1):
    

    key = key + " "
    keylen = len(key)
    start = 0
    currentDepth = 0

    if hasattr(file, "name"):
        end = os.stat(file.name).st_size - 1
    else:
        file.seek(0, 2)
        end = file.tell() - 1
        file.seek(0)

    if cache is None:
        cache = {}

    while start < end:
        lastState = start, end
        middle = (start + end) // 2

        if cache.get(middle):
            offset, line = cache[middle]

        else:
            line = ""
            while True:
                file.seek(max(0, middle - 1))
                if middle > 0:
                    file.discard_line()
                offset = file.tell()
                line = file.readline()
                if line != "":
                    break
                
                middle = (start + middle) // 2
                if middle == end - 1:
                    return None
            if currentDepth < cacheDepth:
                cache[middle] = (offset, line)

        if offset > end:
            assert end != middle - 1, "infinite loop"
            end = middle - 1
        elif line[:keylen] == key:
            return line
        elif line > key:
            assert end != middle - 1, "infinite loop"
            end = middle - 1
        elif line < key:
            start = offset + len(line) - 1

        currentDepth += 1
        thisState = start, end

        if lastState == thisState:
            
            
            return None

    return None







def set_proxy(proxy, user=None, password=""):
    
    if proxy is None:
        
        try:
            proxy = getproxies()["http"]
        except KeyError as e:
            raise ValueError("Could not detect default proxy settings") from e

    
    proxy_handler = ProxyHandler({"https": proxy, "http": proxy})
    opener = build_opener(proxy_handler)

    if user is not None:
        
        password_manager = HTTPPasswordMgrWithDefaultRealm()
        password_manager.add_password(realm=None, uri=proxy, user=user, passwd=password)
        opener.add_handler(ProxyBasicAuthHandler(password_manager))
        opener.add_handler(ProxyDigestAuthHandler(password_manager))

    
    install_opener(opener)







def elementtree_indent(elem, level=0):
    

    i = "\n" + level * "  "
    if len(elem):
        if not elem.text or not elem.text.strip():
            elem.text = i + "  "
        for elem in elem:
            elementtree_indent(elem, level + 1)
        if not elem.tail or not elem.tail.strip():
            elem.tail = i
    else:
        if level and (not elem.tail or not elem.tail.strip()):
            elem.tail = i







def choose(n, k):
    
    if 0 <= k <= n:
        ntok, ktok = 1, 1
        for t in range(1, min(k, n - k) + 1):
            ntok *= n
            ktok *= t
            n -= 1
        return ntok // ktok
    else:
        return 0







def pairwise(iterable):
    
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)







def parallelize_preprocess(func, iterator, processes, progress_bar=False):
    from joblib import Parallel, delayed
    from tqdm import tqdm

    iterator = tqdm(iterator) if progress_bar else iterator
    if processes <= 1:
        return map(func, iterator)
    return Parallel(n_jobs=processes)(delayed(func)(line) for line in iterator)