natural language toolkit ngram association measures c 20012023 nltk project joel nothman jnothmanstudent usyd edu au url https www nltk org for license information see license txt provides scoring functions for a number of association measures through a generic abstract implementation in ngramassocmeasures and nspecific bigramassocmeasures and trigramassocmeasures indices to marginals arguments marginals index for the ngram count unigrams 2 marginals index for the number of words in the data class ngramassocmeasuresmetaclassabcmeta n 0 staticmethod abstractmethod def contingencymarginals calculates values of contingency table marginals from its values raise notimplementederror the contingency table is not available in the general ngram case classmethod def expectedvaluescls cont for each contingency table cell yield the expected value scores ngrams by their frequency return marginalsngram marginalstotal classmethod def studenttcls marginals return marginalsngram productmarginalsunigrams marginalstotal cls n 1 marginalsngram small 0 5 classmethod def chisqcls marginals cont cls contingencymarginals exps cls expectedvaluescont return sumobs exp 2 exp small for obs exp in zipcont exps staticmethod def milikemarginals kwargs return marginalsngram kwargs getpower 3 product marginalsunigrams classmethod def pmicls marginals return log2marginalsngram marginalstotal cls n 1 log2 productmarginalsunigrams classmethod def likelihoodratiocls marginals scores ngrams using the poissonstirling measure exp productmarginalsunigrams marginalstotal cls n 1 return marginalsngram log2marginalsngram exp 1 classmethod def jaccardcls marginals a collection of bigram association measures each association measure is provided as a function with three arguments bigramscorefnnii nix nxi nxx the arguments constitute the marginals of a contingency table counting the occurrences of particular events in a corpus the letter i in the suffix refers to the appearance of the word in question while x indicates the appearance of any word thus for example nii counts w1 w2 i e the bigram being scored nix counts w1 nxi counts w2 nxx counts i e any bigram this may be shown with respect to a contingency table w1 w1 w2 nii noi nxi w2 nio noo nix total nxx calculates values of a bigram contingency table from marginal values nix nxi nixxituple noi nxi nii nio nix nii return nii noi nio nxx nii noi nio staticmethod def marginalsnii noi nio noo calculates expected values for a contingency table nxx sumcont for each contingency table cell for i in range4 yield conti conti 1 conti conti 2 nxx classmethod def phisqcls marginals nii nio noi noo cls contingencymarginals return nii noo nio noi 2 nii nio nii noi nio noo noi noo classmethod def chisqcls nii nixxituple nxx nix nxi nixxituple return nxx cls phisqnii nix nxi nxx classmethod def fishercls marginals nii nio noi noo cls contingencymarginals odds pvalue fisherexactnii nio noi noo alternativeless return pvalue staticmethod def dicenii nixxituple nxx a collection of trigram association measures each association measure is provided as a function with four arguments trigramscorefnniii niix nixi nxii nixx nxix nxxi nxxx the arguments constitute the marginals of a contingency table counting the occurrences of particular events in a corpus the letter i in the suffix refers to the appearance of the word in question while x indicates the appearance of any word thus for example niii counts w1 w2 w3 i e the trigram being scored nixx counts w1 nxxx counts i e any trigram calculates values of a trigram contingency table or cube from marginal values trigramassocmeasures contingency1 1 1 1 1 73 1 2000 1 0 0 0 0 72 0 1927 calculates values of contingency table marginals from its values trigramassocmeasures marginals1 0 0 0 0 72 0 1927 1 1 1 1 1 73 1 2000 a collection of quadgram association measures each association measure is provided as a function with five arguments trigramscorefnniiii niiix niixi nixii nxiii niixx nixix nixxi nxixi nxxii nxiix nixxx nxixx nxxix nxxxi nall the arguments constitute the marginals of a contingency table counting the occurrences of particular events in a corpus the letter i in the suffix refers to the appearance of the word in question while x indicates the appearance of any word thus for example niiii counts w1 w2 w3 w4 i e the quadgram being scored nixxi counts w1 w4 nxxxx counts i e any quadgram calculates values of a quadgram contingency table from marginal values calculates values of contingency table marginals from its values quadgramassocmeasures marginals1 0 2 46 552 825 2577 34967 1 0 2 48 7250 9031 28585 356653 1 2 553 3 1 7804 6 3132 1378 49 2 38970 17660 100 38970 440540 wraps ngramassocmeasures classes such that the arguments of association measures are contingency table values rather than marginals constructs a contingencymeasures given a ngramassocmeasures class self class name contingency measures class name for k in dirmeasures if k startswith continue v getattrmeasures k if not k startswith v self makecontingencyfnmeasures v setattrself k v staticmethod def makecontingencyfnmeasures oldfn def rescontingency return oldfnmeasures marginalscontingency res doc oldfn doc res name oldfn name return res natural language toolkit ngram association measures c 2001 2023 nltk project joel nothman jnothman student usyd edu au url https www nltk org for license information see license txt provides scoring functions for a number of association measures through a generic abstract implementation in ngramassocmeasures and n specific bigramassocmeasures and trigramassocmeasures indices to marginals arguments marginals index for the ngram count marginals index for a tuple of each unigram count marginals index for the number of words in the data an abstract class defining a collection of generic association measures each public method returns a score taking the following arguments score_fn count_of_ngram count_of_n 1gram_1 count_of_n 1gram_j count_of_n 2gram_1 count_of_n 2gram_k count_of_1gram_1 count_of_1gram_n count_of_total_words see bigramassocmeasures and trigramassocmeasures inheriting classes should define a property _n and a method _contingency which calculates contingency values from marginals in order for all association measures defined here to be usable calculates values of a contingency table from marginal values calculates values of contingency table marginals from its values calculates expected values for a contingency table for each contingency table cell yield the expected value scores ngrams by their frequency scores ngrams using student s t test with independence hypothesis for unigrams as in manning and schutze 5 3 1 scores ngrams using pearson s chi square as in manning and schutze 5 3 3 scores ngrams using a variant of mutual information the keyword argument power sets an exponent default 3 for the numerator no logarithm of the result is calculated scores ngrams by pointwise mutual information as in manning and schutze 5 4 scores ngrams using likelihood ratios as in manning and schutze 5 3 4 scores ngrams using the poisson stirling measure scores ngrams using the jaccard index a collection of bigram association measures each association measure is provided as a function with three arguments bigram_score_fn n_ii n_ix n_xi n_xx the arguments constitute the marginals of a contingency table counting the occurrences of particular events in a corpus the letter i in the suffix refers to the appearance of the word in question while x indicates the appearance of any word thus for example n_ii counts w1 w2 i e the bigram being scored n_ix counts w1 n_xi counts w2 n_xx counts i e any bigram this may be shown with respect to a contingency table w1 w1 w2 n_ii n_oi n_xi w2 n_io n_oo n_ix total n_xx calculates values of a bigram contingency table from marginal values calculates values of contingency table marginals from its values calculates expected values for a contingency table for each contingency table cell scores bigrams using phi square the square of the pearson correlation coefficient scores bigrams using chi square i e phi sq multiplied by the number of bigrams as in manning and schutze 5 3 3 scores bigrams using fisher s exact test pedersen 1996 less sensitive to small counts than pmi or chi sq but also more expensive to compute requires scipy scores bigrams using dice s coefficient a collection of trigram association measures each association measure is provided as a function with four arguments trigram_score_fn n_iii n_iix n_ixi n_xii n_ixx n_xix n_xxi n_xxx the arguments constitute the marginals of a contingency table counting the occurrences of particular events in a corpus the letter i in the suffix refers to the appearance of the word in question while x indicates the appearance of any word thus for example n_iii counts w1 w2 w3 i e the trigram being scored n_ixx counts w1 n_xxx counts i e any trigram calculates values of a trigram contingency table or cube from marginal values trigramassocmeasures _contingency 1 1 1 1 1 73 1 2000 1 0 0 0 0 72 0 1927 calculates values of contingency table marginals from its values trigramassocmeasures _marginals 1 0 0 0 0 72 0 1927 1 1 1 1 1 73 1 2000 a collection of quadgram association measures each association measure is provided as a function with five arguments trigram_score_fn n_iiii n_iiix n_iixi n_ixii n_xiii n_iixx n_ixix n_ixxi n_xixi n_xxii n_xiix n_ixxx n_xixx n_xxix n_xxxi n_all the arguments constitute the marginals of a contingency table counting the occurrences of particular events in a corpus the letter i in the suffix refers to the appearance of the word in question while x indicates the appearance of any word thus for example n_iiii counts w1 w2 w3 w4 i e the quadgram being scored n_ixxi counts w1 w4 n_xxxx counts i e any quadgram calculates values of a quadgram contingency table from marginal values calculates values of contingency table marginals from its values quadgramassocmeasures _marginals 1 0 2 46 552 825 2577 34967 1 0 2 48 7250 9031 28585 356653 1 2 553 3 1 7804 6 3132 1378 49 2 38970 17660 100 38970 440540 wraps ngramassocmeasures classes such that the arguments of association measures are contingency table values rather than marginals constructs a contingencymeasures given a ngramassocmeasures class from an association measure function produces a new function which accepts contingency table values as its arguments
import math as _math
from abc import ABCMeta, abstractmethod
from functools import reduce

_log2 = lambda x: _math.log2(x)
_ln = _math.log

_product = lambda s: reduce(lambda x, y: x * y, s)

_SMALL = 1e-20

try:
    from scipy.stats import fisher_exact
except ImportError:

    def fisher_exact(*_args, **_kwargs):
        raise NotImplementedError




NGRAM = 0


UNIGRAMS = -2


TOTAL = -1



class NgramAssocMeasures(metaclass=ABCMeta):
    

    _n = 0

    @staticmethod
    @abstractmethod
    def _contingency(*marginals):
        
        raise NotImplementedError(
            "The contingency table is not available" "in the general ngram case"
        )

    @staticmethod
    @abstractmethod
    def _marginals(*contingency):
        
        raise NotImplementedError(
            "The contingency table is not available" "in the general ngram case"
        )

    @classmethod
    def _expected_values(cls, cont):
        
        n_all = sum(cont)
        bits = [1 << i for i in range(cls._n)]

        
        for i in range(len(cont)):
            
            yield (
                _product(
                    sum(cont[x] for x in range(2**cls._n) if (x & j) == (i & j))
                    for j in bits
                )
                / (n_all ** (cls._n - 1))
            )

    @staticmethod
    def raw_freq(*marginals):
        
        return marginals[NGRAM] / marginals[TOTAL]

    @classmethod
    def student_t(cls, *marginals):
        
        return (
            marginals[NGRAM]
            - _product(marginals[UNIGRAMS]) / (marginals[TOTAL] ** (cls._n - 1))
        ) / (marginals[NGRAM] + _SMALL) ** 0.5

    @classmethod
    def chi_sq(cls, *marginals):
        
        cont = cls._contingency(*marginals)
        exps = cls._expected_values(cont)
        return sum((obs - exp) ** 2 / (exp + _SMALL) for obs, exp in zip(cont, exps))

    @staticmethod
    def mi_like(*marginals, **kwargs):
        
        return marginals[NGRAM] ** kwargs.get("power", 3) / _product(
            marginals[UNIGRAMS]
        )

    @classmethod
    def pmi(cls, *marginals):
        
        return _log2(marginals[NGRAM] * marginals[TOTAL] ** (cls._n - 1)) - _log2(
            _product(marginals[UNIGRAMS])
        )

    @classmethod
    def likelihood_ratio(cls, *marginals):
        
        cont = cls._contingency(*marginals)
        return 2 * sum(
            obs * _ln(obs / (exp + _SMALL) + _SMALL)
            for obs, exp in zip(cont, cls._expected_values(cont))
        )

    @classmethod
    def poisson_stirling(cls, *marginals):
        
        exp = _product(marginals[UNIGRAMS]) / (marginals[TOTAL] ** (cls._n - 1))
        return marginals[NGRAM] * (_log2(marginals[NGRAM] / exp) - 1)

    @classmethod
    def jaccard(cls, *marginals):
        
        cont = cls._contingency(*marginals)
        return cont[0] / sum(cont[:-1])


class BigramAssocMeasures(NgramAssocMeasures):
    

    _n = 2

    @staticmethod
    def _contingency(n_ii, n_ix_xi_tuple, n_xx):
        
        (n_ix, n_xi) = n_ix_xi_tuple
        n_oi = n_xi - n_ii
        n_io = n_ix - n_ii
        return (n_ii, n_oi, n_io, n_xx - n_ii - n_oi - n_io)

    @staticmethod
    def _marginals(n_ii, n_oi, n_io, n_oo):
        
        return (n_ii, (n_oi + n_ii, n_io + n_ii), n_oo + n_oi + n_io + n_ii)

    @staticmethod
    def _expected_values(cont):
        
        n_xx = sum(cont)
        
        for i in range(4):
            yield (cont[i] + cont[i ^ 1]) * (cont[i] + cont[i ^ 2]) / n_xx

    @classmethod
    def phi_sq(cls, *marginals):
        
        n_ii, n_io, n_oi, n_oo = cls._contingency(*marginals)

        return (n_ii * n_oo - n_io * n_oi) ** 2 / (
            (n_ii + n_io) * (n_ii + n_oi) * (n_io + n_oo) * (n_oi + n_oo)
        )

    @classmethod
    def chi_sq(cls, n_ii, n_ix_xi_tuple, n_xx):
        
        (n_ix, n_xi) = n_ix_xi_tuple
        return n_xx * cls.phi_sq(n_ii, (n_ix, n_xi), n_xx)

    @classmethod
    def fisher(cls, *marginals):
        

        n_ii, n_io, n_oi, n_oo = cls._contingency(*marginals)

        (odds, pvalue) = fisher_exact([[n_ii, n_io], [n_oi, n_oo]], alternative="less")
        return pvalue

    @staticmethod
    def dice(n_ii, n_ix_xi_tuple, n_xx):
        
        (n_ix, n_xi) = n_ix_xi_tuple
        return 2 * n_ii / (n_ix + n_xi)


class TrigramAssocMeasures(NgramAssocMeasures):
    

    _n = 3

    @staticmethod
    def _contingency(n_iii, n_iix_tuple, n_ixx_tuple, n_xxx):
        
        (n_iix, n_ixi, n_xii) = n_iix_tuple
        (n_ixx, n_xix, n_xxi) = n_ixx_tuple
        n_oii = n_xii - n_iii
        n_ioi = n_ixi - n_iii
        n_iio = n_iix - n_iii
        n_ooi = n_xxi - n_iii - n_oii - n_ioi
        n_oio = n_xix - n_iii - n_oii - n_iio
        n_ioo = n_ixx - n_iii - n_ioi - n_iio
        n_ooo = n_xxx - n_iii - n_oii - n_ioi - n_iio - n_ooi - n_oio - n_ioo

        return (n_iii, n_oii, n_ioi, n_ooi, n_iio, n_oio, n_ioo, n_ooo)

    @staticmethod
    def _marginals(*contingency):
        
        n_iii, n_oii, n_ioi, n_ooi, n_iio, n_oio, n_ioo, n_ooo = contingency
        return (
            n_iii,
            (n_iii + n_iio, n_iii + n_ioi, n_iii + n_oii),
            (
                n_iii + n_ioi + n_iio + n_ioo,
                n_iii + n_oii + n_iio + n_oio,
                n_iii + n_oii + n_ioi + n_ooi,
            ),
            sum(contingency),
        )


class QuadgramAssocMeasures(NgramAssocMeasures):
    

    _n = 4

    @staticmethod
    def _contingency(n_iiii, n_iiix_tuple, n_iixx_tuple, n_ixxx_tuple, n_xxxx):
        
        (n_iiix, n_iixi, n_ixii, n_xiii) = n_iiix_tuple
        (n_iixx, n_ixix, n_ixxi, n_xixi, n_xxii, n_xiix) = n_iixx_tuple
        (n_ixxx, n_xixx, n_xxix, n_xxxi) = n_ixxx_tuple
        n_oiii = n_xiii - n_iiii
        n_ioii = n_ixii - n_iiii
        n_iioi = n_iixi - n_iiii
        n_ooii = n_xxii - n_iiii - n_oiii - n_ioii
        n_oioi = n_xixi - n_iiii - n_oiii - n_iioi
        n_iooi = n_ixxi - n_iiii - n_ioii - n_iioi
        n_oooi = n_xxxi - n_iiii - n_oiii - n_ioii - n_iioi - n_ooii - n_iooi - n_oioi
        n_iiio = n_iiix - n_iiii
        n_oiio = n_xiix - n_iiii - n_oiii - n_iiio
        n_ioio = n_ixix - n_iiii - n_ioii - n_iiio
        n_ooio = n_xxix - n_iiii - n_oiii - n_ioii - n_iiio - n_ooii - n_ioio - n_oiio
        n_iioo = n_iixx - n_iiii - n_iioi - n_iiio
        n_oioo = n_xixx - n_iiii - n_oiii - n_iioi - n_iiio - n_oioi - n_oiio - n_iioo
        n_iooo = n_ixxx - n_iiii - n_ioii - n_iioi - n_iiio - n_iooi - n_iioo - n_ioio
        n_oooo = (
            n_xxxx
            - n_iiii
            - n_oiii
            - n_ioii
            - n_iioi
            - n_ooii
            - n_oioi
            - n_iooi
            - n_oooi
            - n_iiio
            - n_oiio
            - n_ioio
            - n_ooio
            - n_iioo
            - n_oioo
            - n_iooo
        )

        return (
            n_iiii,
            n_oiii,
            n_ioii,
            n_ooii,
            n_iioi,
            n_oioi,
            n_iooi,
            n_oooi,
            n_iiio,
            n_oiio,
            n_ioio,
            n_ooio,
            n_iioo,
            n_oioo,
            n_iooo,
            n_oooo,
        )

    @staticmethod
    def _marginals(*contingency):
        
        (
            n_iiii,
            n_oiii,
            n_ioii,
            n_ooii,
            n_iioi,
            n_oioi,
            n_iooi,
            n_oooi,
            n_iiio,
            n_oiio,
            n_ioio,
            n_ooio,
            n_iioo,
            n_oioo,
            n_iooo,
            n_oooo,
        ) = contingency

        n_iiix = n_iiii + n_iiio
        n_iixi = n_iiii + n_iioi
        n_ixii = n_iiii + n_ioii
        n_xiii = n_iiii + n_oiii

        n_iixx = n_iiii + n_iioi + n_iiio + n_iioo
        n_ixix = n_iiii + n_ioii + n_iiio + n_ioio
        n_ixxi = n_iiii + n_ioii + n_iioi + n_iooi
        n_xixi = n_iiii + n_oiii + n_iioi + n_oioi
        n_xxii = n_iiii + n_oiii + n_ioii + n_ooii
        n_xiix = n_iiii + n_oiii + n_iiio + n_oiio

        n_ixxx = n_iiii + n_ioii + n_iioi + n_iiio + n_iooi + n_iioo + n_ioio + n_iooo
        n_xixx = n_iiii + n_oiii + n_iioi + n_iiio + n_oioi + n_oiio + n_iioo + n_oioo
        n_xxix = n_iiii + n_oiii + n_ioii + n_iiio + n_ooii + n_ioio + n_oiio + n_ooio
        n_xxxi = n_iiii + n_oiii + n_ioii + n_iioi + n_ooii + n_iooi + n_oioi + n_oooi

        n_all = sum(contingency)

        return (
            n_iiii,
            (n_iiix, n_iixi, n_ixii, n_xiii),
            (n_iixx, n_ixix, n_ixxi, n_xixi, n_xxii, n_xiix),
            (n_ixxx, n_xixx, n_xxix, n_xxxi),
            n_all,
        )


class ContingencyMeasures:
    

    def __init__(self, measures):
        
        self.__class__.__name__ = "Contingency" + measures.__class__.__name__
        for k in dir(measures):
            if k.startswith("__"):
                continue
            v = getattr(measures, k)
            if not k.startswith("_"):
                v = self._make_contingency_fn(measures, v)
            setattr(self, k, v)

    @staticmethod
    def _make_contingency_fn(measures, old_fn):
        

        def res(*contingency):
            return old_fn(*measures._marginals(*contingency))

        res.__doc__ = old_fn.__doc__
        res.__name__ = old_fn.__name__
        return res