| 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 |