Debian Codegraph @

wordcloud/tokenization.py

raw
1 from __future__ import division
2 from itertools import tee
3 from operator import itemgetter
4 from collections import defaultdict
5 from math import log
6
7
8 def l(k, n, x): # noqa: E741, E743
9 # dunning's likelihood ratio with notation from
10 # http://nlp.stanford.edu/fsnlp/promo/colloc.pdf p162
11 return log(max(x, 1e-10)) * k + log(max(1 - x, 1e-10)) * (n - k)
12
13
14 def score(count_bigram, count1, count2, n_words):
15 """Collocation score"""
16 if n_words <= count1 or n_words <= count2:
17 # only one words appears in the whole document
18 return 0
19 N = n_words
20 c12 = count_bigram
21 c1 = count1
22 c2 = count2
23 p = c2 / N
24 p1 = c12 / c1
25 p2 = (c2 - c12) / (N - c1)
26 score = (l(c12, c1, p) + l(c2 - c12, N - c1, p)
27 - l(c12, c1, p1) - l(c2 - c12, N - c1, p2))
28 return -2 * score
29
30
31 def pairwise(iterable):
32 # from itertool recipies
33 # is -> (s0,s1), (s1,s2), (s2, s3), ...
34 a, b = tee(iterable)
35 next(b, None)
36 return zip(a, b)
37
38
39 def unigrams_and_bigrams(words, stopwords, normalize_plurals=True, collocation_threshold=30):
40 # We must create the bigrams before removing the stopword tokens from the words, or else we get bigrams like
41 # "thank much" from "thank you very much".
42 # We don't allow any of the words in the bigram to be stopwords
43 bigrams = list(p for p in pairwise(words) if not any(w.lower() in stopwords for w in p))
44 unigrams = list(w for w in words if w.lower() not in stopwords)
45 n_words = len(unigrams)
46 counts_unigrams, standard_form = process_tokens(
47 unigrams, normalize_plurals=normalize_plurals)
48 counts_bigrams, standard_form_bigrams = process_tokens(
49 [" ".join(bigram) for bigram in bigrams],
50 normalize_plurals=normalize_plurals)
51 # create a copy of counts_unigram so the score computation is not changed
52 orig_counts = counts_unigrams.copy()
53
54 # Include bigrams that are also collocations
55 for bigram_string, count in counts_bigrams.items():
56 bigram = tuple(bigram_string.split(" "))
57 word1 = standard_form[bigram[0].lower()]
58 word2 = standard_form[bigram[1].lower()]
59
60 collocation_score = score(count, orig_counts[word1], orig_counts[word2], n_words)
61 if collocation_score > collocation_threshold:
62 # bigram is a collocation
63 # discount words in unigrams dict. hack because one word might
64 # appear in multiple collocations at the same time
65 # (leading to negative counts)
66 counts_unigrams[word1] -= counts_bigrams[bigram_string]
67 counts_unigrams[word2] -= counts_bigrams[bigram_string]
68 counts_unigrams[bigram_string] = counts_bigrams[bigram_string]
69 for word, count in list(counts_unigrams.items()):
70 if count <= 0:
71 del counts_unigrams[word]
72 return counts_unigrams
73
74
75 def process_tokens(words, normalize_plurals=True):
76 """Normalize cases and remove plurals.
77
78 Each word is represented by the most common case.
79 If a word appears with an "s" on the end and without an "s" on the end,
80 the version with "s" is assumed to be a plural and merged with the
81 version without "s" (except if the word ends with "ss").
82
83 Parameters
84 ----------
85 words : iterable of strings
86 Words to count.
87
88 normalize_plurals : bool, default=True
89 Whether to try and detect plurals and remove trailing "s".
90
91 Returns
92 -------
93 counts : dict from string to int
94 Counts for each unique word, with cases represented by the most common
95 case, and plurals removed.
96
97 standard_forms : dict from string to string
98 For each lower-case word the standard capitalization.
99 """
100 # words can be either a list of unigrams or bigrams
101 # d is a dict of dicts.
102 # Keys of d are word.lower(). Values are dicts
103 # counting frequency of each capitalization
104 d = defaultdict(dict)
105 for word in words:
106 word_lower = word.lower()
107 # get dict of cases for word_lower
108 case_dict = d[word_lower]
109 # increase this case
110 case_dict[word] = case_dict.get(word, 0) + 1
111 if normalize_plurals:
112 # merge plurals into the singular count (simple cases only)
113 merged_plurals = {}
114 for key in list(d.keys()):
115 if key.endswith('s') and not key.endswith("ss"):
116 key_singular = key[:-1]
117 if key_singular in d:
118 dict_plural = d[key]
119 dict_singular = d[key_singular]
120 for word, count in dict_plural.items():
121 singular = word[:-1]
122 dict_singular[singular] = (
123 dict_singular.get(singular, 0) + count)
124 merged_plurals[key] = key_singular
125 del d[key]
126 fused_cases = {}
127 standard_cases = {}
128 item1 = itemgetter(1)
129 for word_lower, case_dict in d.items():
130 # Get the most popular case.
131 first = max(case_dict.items(), key=item1)[0]
132 fused_cases[first] = sum(case_dict.values())
133 standard_cases[word_lower] = first
134 if normalize_plurals:
135 # add plurals to fused cases:
136 for plural, singular in merged_plurals.items():
137 standard_cases[plural] = standard_cases[singular.lower()]
138 return fused_cases, standard_cases