util.py 25 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828
  1. # Natural Language Toolkit: Utility functions
  2. #
  3. # Copyright (C) 2001-2019 NLTK Project
  4. # Author: Steven Bird <stevenbird1@gmail.com>
  5. # URL: <http://nltk.org/>
  6. # For license information, see LICENSE.TXT
  7. from __future__ import print_function
  8. import sys
  9. import inspect
  10. import locale
  11. import re
  12. import types
  13. import textwrap
  14. import pydoc
  15. import bisect
  16. import os
  17. from itertools import islice, chain, combinations
  18. from pprint import pprint
  19. from collections import defaultdict, deque
  20. from sys import version_info
  21. from six import class_types, string_types, text_type
  22. from six.moves.urllib.request import (
  23. build_opener,
  24. install_opener,
  25. getproxies,
  26. ProxyHandler,
  27. ProxyBasicAuthHandler,
  28. ProxyDigestAuthHandler,
  29. HTTPPasswordMgrWithDefaultRealm,
  30. )
  31. from nltk.internals import slice_bounds, raise_unorderable_types
  32. from nltk.collections import *
  33. from nltk.compat import python_2_unicode_compatible
  34. ######################################################################
  35. # Short usage message
  36. ######################################################################
  37. def usage(obj, selfname='self'):
  38. str(obj) # In case it's lazy, this will load it.
  39. if not isinstance(obj, class_types):
  40. obj = obj.__class__
  41. print('%s supports the following operations:' % obj.__name__)
  42. for (name, method) in sorted(pydoc.allmethods(obj).items()):
  43. if name.startswith('_'):
  44. continue
  45. if getattr(method, '__deprecated__', False):
  46. continue
  47. if sys.version_info[0] >= 3:
  48. getargspec = inspect.getfullargspec
  49. else:
  50. getargspec = inspect.getargspec
  51. args, varargs, varkw, defaults = getargspec(method)[:4]
  52. if (
  53. args
  54. and args[0] == 'self'
  55. and (defaults is None or len(args) > len(defaults))
  56. ):
  57. args = args[1:]
  58. name = '%s.%s' % (selfname, name)
  59. argspec = inspect.formatargspec(args, varargs, varkw, defaults)
  60. print(
  61. textwrap.fill(
  62. '%s%s' % (name, argspec),
  63. initial_indent=' - ',
  64. subsequent_indent=' ' * (len(name) + 5),
  65. )
  66. )
  67. ##########################################################################
  68. # IDLE
  69. ##########################################################################
  70. def in_idle():
  71. """
  72. Return True if this function is run within idle. Tkinter
  73. programs that are run in idle should never call ``Tk.mainloop``; so
  74. this function should be used to gate all calls to ``Tk.mainloop``.
  75. :warning: This function works by checking ``sys.stdin``. If the
  76. user has modified ``sys.stdin``, then it may return incorrect
  77. results.
  78. :rtype: bool
  79. """
  80. import sys
  81. return sys.stdin.__class__.__name__ in ('PyShell', 'RPCProxy')
  82. ##########################################################################
  83. # PRETTY PRINTING
  84. ##########################################################################
  85. def pr(data, start=0, end=None):
  86. """
  87. Pretty print a sequence of data items
  88. :param data: the data stream to print
  89. :type data: sequence or iter
  90. :param start: the start position
  91. :type start: int
  92. :param end: the end position
  93. :type end: int
  94. """
  95. pprint(list(islice(data, start, end)))
  96. def print_string(s, width=70):
  97. """
  98. Pretty print a string, breaking lines on whitespace
  99. :param s: the string to print, consisting of words and spaces
  100. :type s: str
  101. :param width: the display width
  102. :type width: int
  103. """
  104. print('\n'.join(textwrap.wrap(s, width=width)))
  105. def tokenwrap(tokens, separator=" ", width=70):
  106. """
  107. Pretty print a list of text tokens, breaking lines on whitespace
  108. :param tokens: the tokens to print
  109. :type tokens: list
  110. :param separator: the string to use to separate tokens
  111. :type separator: str
  112. :param width: the display width (default=70)
  113. :type width: int
  114. """
  115. return '\n'.join(textwrap.wrap(separator.join(tokens), width=width))
  116. ##########################################################################
  117. # Python version
  118. ##########################################################################
  119. def py25():
  120. return version_info[0] == 2 and version_info[1] == 5
  121. def py26():
  122. return version_info[0] == 2 and version_info[1] == 6
  123. def py27():
  124. return version_info[0] == 2 and version_info[1] == 7
  125. ##########################################################################
  126. # Indexing
  127. ##########################################################################
  128. class Index(defaultdict):
  129. def __init__(self, pairs):
  130. defaultdict.__init__(self, list)
  131. for key, value in pairs:
  132. self[key].append(value)
  133. ######################################################################
  134. ## Regexp display (thanks to David Mertz)
  135. ######################################################################
  136. def re_show(regexp, string, left="{", right="}"):
  137. """
  138. Return a string with markers surrounding the matched substrings.
  139. Search str for substrings matching ``regexp`` and wrap the matches
  140. with braces. This is convenient for learning about regular expressions.
  141. :param regexp: The regular expression.
  142. :type regexp: str
  143. :param string: The string being matched.
  144. :type string: str
  145. :param left: The left delimiter (printed before the matched substring)
  146. :type left: str
  147. :param right: The right delimiter (printed after the matched substring)
  148. :type right: str
  149. :rtype: str
  150. """
  151. print(re.compile(regexp, re.M).sub(left + r"\g<0>" + right, string.rstrip()))
  152. ##########################################################################
  153. # READ FROM FILE OR STRING
  154. ##########################################################################
  155. # recipe from David Mertz
  156. def filestring(f):
  157. if hasattr(f, 'read'):
  158. return f.read()
  159. elif isinstance(f, string_types):
  160. with open(f, 'r') as infile:
  161. return infile.read()
  162. else:
  163. raise ValueError("Must be called with a filename or file-like object")
  164. ##########################################################################
  165. # Breadth-First Search
  166. ##########################################################################
  167. def breadth_first(tree, children=iter, maxdepth=-1):
  168. """Traverse the nodes of a tree in breadth-first order.
  169. (No need to check for cycles.)
  170. The first argument should be the tree root;
  171. children should be a function taking as argument a tree node
  172. and returning an iterator of the node's children.
  173. """
  174. queue = deque([(tree, 0)])
  175. while queue:
  176. node, depth = queue.popleft()
  177. yield node
  178. if depth != maxdepth:
  179. try:
  180. queue.extend((c, depth + 1) for c in children(node))
  181. except TypeError:
  182. pass
  183. ##########################################################################
  184. # Guess Character Encoding
  185. ##########################################################################
  186. # adapted from io.py in the docutils extension module (http://docutils.sourceforge.net)
  187. # http://www.pyzine.com/Issue008/Section_Articles/article_Encodings.html
  188. def guess_encoding(data):
  189. """
  190. Given a byte string, attempt to decode it.
  191. Tries the standard 'UTF8' and 'latin-1' encodings,
  192. Plus several gathered from locale information.
  193. The calling program *must* first call::
  194. locale.setlocale(locale.LC_ALL, '')
  195. If successful it returns ``(decoded_unicode, successful_encoding)``.
  196. If unsuccessful it raises a ``UnicodeError``.
  197. """
  198. successful_encoding = None
  199. # we make 'utf-8' the first encoding
  200. encodings = ['utf-8']
  201. #
  202. # next we add anything we can learn from the locale
  203. try:
  204. encodings.append(locale.nl_langinfo(locale.CODESET))
  205. except AttributeError:
  206. pass
  207. try:
  208. encodings.append(locale.getlocale()[1])
  209. except (AttributeError, IndexError):
  210. pass
  211. try:
  212. encodings.append(locale.getdefaultlocale()[1])
  213. except (AttributeError, IndexError):
  214. pass
  215. #
  216. # we try 'latin-1' last
  217. encodings.append('latin-1')
  218. for enc in encodings:
  219. # some of the locale calls
  220. # may have returned None
  221. if not enc:
  222. continue
  223. try:
  224. decoded = text_type(data, enc)
  225. successful_encoding = enc
  226. except (UnicodeError, LookupError):
  227. pass
  228. else:
  229. break
  230. if not successful_encoding:
  231. raise UnicodeError(
  232. 'Unable to decode input data. '
  233. 'Tried the following encodings: %s.'
  234. % ', '.join([repr(enc) for enc in encodings if enc])
  235. )
  236. else:
  237. return (decoded, successful_encoding)
  238. ##########################################################################
  239. # Remove repeated elements from a list deterministcally
  240. ##########################################################################
  241. def unique_list(xs):
  242. seen = set()
  243. # not seen.add(x) here acts to make the code shorter without using if statements, seen.add(x) always returns None.
  244. return [x for x in xs if x not in seen and not seen.add(x)]
  245. ##########################################################################
  246. # Invert a dictionary
  247. ##########################################################################
  248. def invert_dict(d):
  249. inverted_dict = defaultdict(list)
  250. for key in d:
  251. if hasattr(d[key], '__iter__'):
  252. for term in d[key]:
  253. inverted_dict[term].append(key)
  254. else:
  255. inverted_dict[d[key]] = key
  256. return inverted_dict
  257. ##########################################################################
  258. # Utilities for directed graphs: transitive closure, and inversion
  259. # The graph is represented as a dictionary of sets
  260. ##########################################################################
  261. def transitive_closure(graph, reflexive=False):
  262. """
  263. Calculate the transitive closure of a directed graph,
  264. optionally the reflexive transitive closure.
  265. The algorithm is a slight modification of the "Marking Algorithm" of
  266. Ioannidis & Ramakrishnan (1998) "Efficient Transitive Closure Algorithms".
  267. :param graph: the initial graph, represented as a dictionary of sets
  268. :type graph: dict(set)
  269. :param reflexive: if set, also make the closure reflexive
  270. :type reflexive: bool
  271. :rtype: dict(set)
  272. """
  273. if reflexive:
  274. base_set = lambda k: set([k])
  275. else:
  276. base_set = lambda k: set()
  277. # The graph U_i in the article:
  278. agenda_graph = dict((k, graph[k].copy()) for k in graph)
  279. # The graph M_i in the article:
  280. closure_graph = dict((k, base_set(k)) for k in graph)
  281. for i in graph:
  282. agenda = agenda_graph[i]
  283. closure = closure_graph[i]
  284. while agenda:
  285. j = agenda.pop()
  286. closure.add(j)
  287. closure |= closure_graph.setdefault(j, base_set(j))
  288. agenda |= agenda_graph.get(j, base_set(j))
  289. agenda -= closure
  290. return closure_graph
  291. def invert_graph(graph):
  292. """
  293. Inverts a directed graph.
  294. :param graph: the graph, represented as a dictionary of sets
  295. :type graph: dict(set)
  296. :return: the inverted graph
  297. :rtype: dict(set)
  298. """
  299. inverted = {}
  300. for key in graph:
  301. for value in graph[key]:
  302. inverted.setdefault(value, set()).add(key)
  303. return inverted
  304. ##########################################################################
  305. # HTML Cleaning
  306. ##########################################################################
  307. def clean_html(html):
  308. raise NotImplementedError(
  309. "To remove HTML markup, use BeautifulSoup's get_text() function"
  310. )
  311. def clean_url(url):
  312. raise NotImplementedError(
  313. "To remove HTML markup, use BeautifulSoup's get_text() function"
  314. )
  315. ##########################################################################
  316. # FLATTEN LISTS
  317. ##########################################################################
  318. def flatten(*args):
  319. """
  320. Flatten a list.
  321. >>> from nltk.util import flatten
  322. >>> flatten(1, 2, ['b', 'a' , ['c', 'd']], 3)
  323. [1, 2, 'b', 'a', 'c', 'd', 3]
  324. :param args: items and lists to be combined into a single list
  325. :rtype: list
  326. """
  327. x = []
  328. for l in args:
  329. if not isinstance(l, (list, tuple)):
  330. l = [l]
  331. for item in l:
  332. if isinstance(item, (list, tuple)):
  333. x.extend(flatten(item))
  334. else:
  335. x.append(item)
  336. return x
  337. ##########################################################################
  338. # Ngram iteration
  339. ##########################################################################
  340. def pad_sequence(
  341. sequence,
  342. n,
  343. pad_left=False,
  344. pad_right=False,
  345. left_pad_symbol=None,
  346. right_pad_symbol=None,
  347. ):
  348. """
  349. Returns a padded sequence of items before ngram extraction.
  350. >>> list(pad_sequence([1,2,3,4,5], 2, pad_left=True, pad_right=True, left_pad_symbol='<s>', right_pad_symbol='</s>'))
  351. ['<s>', 1, 2, 3, 4, 5, '</s>']
  352. >>> list(pad_sequence([1,2,3,4,5], 2, pad_left=True, left_pad_symbol='<s>'))
  353. ['<s>', 1, 2, 3, 4, 5]
  354. >>> list(pad_sequence([1,2,3,4,5], 2, pad_right=True, right_pad_symbol='</s>'))
  355. [1, 2, 3, 4, 5, '</s>']
  356. :param sequence: the source data to be padded
  357. :type sequence: sequence or iter
  358. :param n: the degree of the ngrams
  359. :type n: int
  360. :param pad_left: whether the ngrams should be left-padded
  361. :type pad_left: bool
  362. :param pad_right: whether the ngrams should be right-padded
  363. :type pad_right: bool
  364. :param left_pad_symbol: the symbol to use for left padding (default is None)
  365. :type left_pad_symbol: any
  366. :param right_pad_symbol: the symbol to use for right padding (default is None)
  367. :type right_pad_symbol: any
  368. :rtype: sequence or iter
  369. """
  370. sequence = iter(sequence)
  371. if pad_left:
  372. sequence = chain((left_pad_symbol,) * (n - 1), sequence)
  373. if pad_right:
  374. sequence = chain(sequence, (right_pad_symbol,) * (n - 1))
  375. return sequence
  376. # add a flag to pad the sequence so we get peripheral ngrams?
  377. def ngrams(
  378. sequence,
  379. n,
  380. pad_left=False,
  381. pad_right=False,
  382. left_pad_symbol=None,
  383. right_pad_symbol=None,
  384. ):
  385. """
  386. Return the ngrams generated from a sequence of items, as an iterator.
  387. For example:
  388. >>> from nltk.util import ngrams
  389. >>> list(ngrams([1,2,3,4,5], 3))
  390. [(1, 2, 3), (2, 3, 4), (3, 4, 5)]
  391. Wrap with list for a list version of this function. Set pad_left
  392. or pad_right to true in order to get additional ngrams:
  393. >>> list(ngrams([1,2,3,4,5], 2, pad_right=True))
  394. [(1, 2), (2, 3), (3, 4), (4, 5), (5, None)]
  395. >>> list(ngrams([1,2,3,4,5], 2, pad_right=True, right_pad_symbol='</s>'))
  396. [(1, 2), (2, 3), (3, 4), (4, 5), (5, '</s>')]
  397. >>> list(ngrams([1,2,3,4,5], 2, pad_left=True, left_pad_symbol='<s>'))
  398. [('<s>', 1), (1, 2), (2, 3), (3, 4), (4, 5)]
  399. >>> list(ngrams([1,2,3,4,5], 2, pad_left=True, pad_right=True, left_pad_symbol='<s>', right_pad_symbol='</s>'))
  400. [('<s>', 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, '</s>')]
  401. :param sequence: the source data to be converted into ngrams
  402. :type sequence: sequence or iter
  403. :param n: the degree of the ngrams
  404. :type n: int
  405. :param pad_left: whether the ngrams should be left-padded
  406. :type pad_left: bool
  407. :param pad_right: whether the ngrams should be right-padded
  408. :type pad_right: bool
  409. :param left_pad_symbol: the symbol to use for left padding (default is None)
  410. :type left_pad_symbol: any
  411. :param right_pad_symbol: the symbol to use for right padding (default is None)
  412. :type right_pad_symbol: any
  413. :rtype: sequence or iter
  414. """
  415. sequence = pad_sequence(
  416. sequence, n, pad_left, pad_right, left_pad_symbol, right_pad_symbol
  417. )
  418. history = []
  419. while n > 1:
  420. # PEP 479, prevent RuntimeError from being raised when StopIteration bubbles out of generator
  421. try:
  422. next_item = next(sequence)
  423. except StopIteration:
  424. # no more data, terminate the generator
  425. return
  426. history.append(next_item)
  427. n -= 1
  428. for item in sequence:
  429. history.append(item)
  430. yield tuple(history)
  431. del history[0]
  432. def bigrams(sequence, **kwargs):
  433. """
  434. Return the bigrams generated from a sequence of items, as an iterator.
  435. For example:
  436. >>> from nltk.util import bigrams
  437. >>> list(bigrams([1,2,3,4,5]))
  438. [(1, 2), (2, 3), (3, 4), (4, 5)]
  439. Use bigrams for a list version of this function.
  440. :param sequence: the source data to be converted into bigrams
  441. :type sequence: sequence or iter
  442. :rtype: iter(tuple)
  443. """
  444. for item in ngrams(sequence, 2, **kwargs):
  445. yield item
  446. def trigrams(sequence, **kwargs):
  447. """
  448. Return the trigrams generated from a sequence of items, as an iterator.
  449. For example:
  450. >>> from nltk.util import trigrams
  451. >>> list(trigrams([1,2,3,4,5]))
  452. [(1, 2, 3), (2, 3, 4), (3, 4, 5)]
  453. Use trigrams for a list version of this function.
  454. :param sequence: the source data to be converted into trigrams
  455. :type sequence: sequence or iter
  456. :rtype: iter(tuple)
  457. """
  458. for item in ngrams(sequence, 3, **kwargs):
  459. yield item
  460. def everygrams(sequence, min_len=1, max_len=-1, **kwargs):
  461. """
  462. Returns all possible ngrams generated from a sequence of items, as an iterator.
  463. >>> sent = 'a b c'.split()
  464. >>> list(everygrams(sent))
  465. [('a',), ('b',), ('c',), ('a', 'b'), ('b', 'c'), ('a', 'b', 'c')]
  466. >>> list(everygrams(sent, max_len=2))
  467. [('a',), ('b',), ('c',), ('a', 'b'), ('b', 'c')]
  468. :param sequence: the source data to be converted into trigrams
  469. :type sequence: sequence or iter
  470. :param min_len: minimum length of the ngrams, aka. n-gram order/degree of ngram
  471. :type min_len: int
  472. :param max_len: maximum length of the ngrams (set to length of sequence by default)
  473. :type max_len: int
  474. :rtype: iter(tuple)
  475. """
  476. if max_len == -1:
  477. max_len = len(sequence)
  478. for n in range(min_len, max_len + 1):
  479. for ng in ngrams(sequence, n, **kwargs):
  480. yield ng
  481. def skipgrams(sequence, n, k, **kwargs):
  482. """
  483. Returns all possible skipgrams generated from a sequence of items, as an iterator.
  484. Skipgrams are ngrams that allows tokens to be skipped.
  485. Refer to http://homepages.inf.ed.ac.uk/ballison/pdf/lrec_skipgrams.pdf
  486. >>> sent = "Insurgents killed in ongoing fighting".split()
  487. >>> list(skipgrams(sent, 2, 2))
  488. [('Insurgents', 'killed'), ('Insurgents', 'in'), ('Insurgents', 'ongoing'), ('killed', 'in'), ('killed', 'ongoing'), ('killed', 'fighting'), ('in', 'ongoing'), ('in', 'fighting'), ('ongoing', 'fighting')]
  489. >>> list(skipgrams(sent, 3, 2))
  490. [('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')]
  491. :param sequence: the source data to be converted into trigrams
  492. :type sequence: sequence or iter
  493. :param n: the degree of the ngrams
  494. :type n: int
  495. :param k: the skip distance
  496. :type k: int
  497. :rtype: iter(tuple)
  498. """
  499. # Pads the sequence as desired by **kwargs.
  500. if 'pad_left' in kwargs or 'pad_right' in kwargs:
  501. sequence = pad_sequence(sequence, n, **kwargs)
  502. # Note when iterating through the ngrams, the pad_right here is not
  503. # the **kwargs padding, it's for the algorithm to detect the SENTINEL
  504. # object on the right pad to stop inner loop.
  505. SENTINEL = object()
  506. for ngram in ngrams(sequence, n + k, pad_right=True, right_pad_symbol=SENTINEL):
  507. head = ngram[:1]
  508. tail = ngram[1:]
  509. for skip_tail in combinations(tail, n - 1):
  510. if skip_tail[-1] is SENTINEL:
  511. continue
  512. yield head + skip_tail
  513. ######################################################################
  514. # Binary Search in a File
  515. ######################################################################
  516. # inherited from pywordnet, by Oliver Steele
  517. def binary_search_file(file, key, cache={}, cacheDepth=-1):
  518. """
  519. Return the line from the file with first word key.
  520. Searches through a sorted file using the binary search algorithm.
  521. :type file: file
  522. :param file: the file to be searched through.
  523. :type key: str
  524. :param key: the identifier we are searching for.
  525. """
  526. key = key + ' '
  527. keylen = len(key)
  528. start = 0
  529. currentDepth = 0
  530. if hasattr(file, 'name'):
  531. end = os.stat(file.name).st_size - 1
  532. else:
  533. file.seek(0, 2)
  534. end = file.tell() - 1
  535. file.seek(0)
  536. while start < end:
  537. lastState = start, end
  538. middle = (start + end) // 2
  539. if cache.get(middle):
  540. offset, line = cache[middle]
  541. else:
  542. line = ""
  543. while True:
  544. file.seek(max(0, middle - 1))
  545. if middle > 0:
  546. file.discard_line()
  547. offset = file.tell()
  548. line = file.readline()
  549. if line != "":
  550. break
  551. # at EOF; try to find start of the last line
  552. middle = (start + middle) // 2
  553. if middle == end - 1:
  554. return None
  555. if currentDepth < cacheDepth:
  556. cache[middle] = (offset, line)
  557. if offset > end:
  558. assert end != middle - 1, "infinite loop"
  559. end = middle - 1
  560. elif line[:keylen] == key:
  561. return line
  562. elif line > key:
  563. assert end != middle - 1, "infinite loop"
  564. end = middle - 1
  565. elif line < key:
  566. start = offset + len(line) - 1
  567. currentDepth += 1
  568. thisState = start, end
  569. if lastState == thisState:
  570. # Detects the condition where we're searching past the end
  571. # of the file, which is otherwise difficult to detect
  572. return None
  573. return None
  574. ######################################################################
  575. # Proxy configuration
  576. ######################################################################
  577. def set_proxy(proxy, user=None, password=''):
  578. """
  579. Set the HTTP proxy for Python to download through.
  580. If ``proxy`` is None then tries to set proxy from environment or system
  581. settings.
  582. :param proxy: The HTTP proxy server to use. For example:
  583. 'http://proxy.example.com:3128/'
  584. :param user: The username to authenticate with. Use None to disable
  585. authentication.
  586. :param password: The password to authenticate with.
  587. """
  588. from nltk import compat
  589. if proxy is None:
  590. # Try and find the system proxy settings
  591. try:
  592. proxy = getproxies()['http']
  593. except KeyError:
  594. raise ValueError('Could not detect default proxy settings')
  595. # Set up the proxy handler
  596. proxy_handler = ProxyHandler({'https': proxy, 'http': proxy})
  597. opener = build_opener(proxy_handler)
  598. if user is not None:
  599. # Set up basic proxy authentication if provided
  600. password_manager = HTTPPasswordMgrWithDefaultRealm()
  601. password_manager.add_password(realm=None, uri=proxy, user=user, passwd=password)
  602. opener.add_handler(ProxyBasicAuthHandler(password_manager))
  603. opener.add_handler(ProxyDigestAuthHandler(password_manager))
  604. # Overide the existing url opener
  605. install_opener(opener)
  606. ######################################################################
  607. # ElementTree pretty printing from http://www.effbot.org/zone/element-lib.htm
  608. ######################################################################
  609. def elementtree_indent(elem, level=0):
  610. """
  611. Recursive function to indent an ElementTree._ElementInterface
  612. used for pretty printing. Run indent on elem and then output
  613. in the normal way.
  614. :param elem: element to be indented. will be modified.
  615. :type elem: ElementTree._ElementInterface
  616. :param level: level of indentation for this element
  617. :type level: nonnegative integer
  618. :rtype: ElementTree._ElementInterface
  619. :return: Contents of elem indented to reflect its structure
  620. """
  621. i = "\n" + level * " "
  622. if len(elem):
  623. if not elem.text or not elem.text.strip():
  624. elem.text = i + " "
  625. for elem in elem:
  626. elementtree_indent(elem, level + 1)
  627. if not elem.tail or not elem.tail.strip():
  628. elem.tail = i
  629. else:
  630. if level and (not elem.tail or not elem.tail.strip()):
  631. elem.tail = i
  632. ######################################################################
  633. # Mathematical approximations
  634. ######################################################################
  635. def choose(n, k):
  636. """
  637. This function is a fast way to calculate binomial coefficients, commonly
  638. known as nCk, i.e. the number of combinations of n things taken k at a time.
  639. (https://en.wikipedia.org/wiki/Binomial_coefficient).
  640. This is the *scipy.special.comb()* with long integer computation but this
  641. approximation is faster, see https://github.com/nltk/nltk/issues/1181
  642. >>> choose(4, 2)
  643. 6
  644. >>> choose(6, 2)
  645. 15
  646. :param n: The number of things.
  647. :type n: int
  648. :param r: The number of times a thing is taken.
  649. :type r: int
  650. """
  651. if 0 <= k <= n:
  652. ntok, ktok = 1, 1
  653. for t in range(1, min(k, n - k) + 1):
  654. ntok *= n
  655. ktok *= t
  656. n -= 1
  657. return ntok // ktok
  658. else:
  659. return 0