natural language toolkit agreement metrics c 20012023 nltk project lauri hallila laurihallilagmail com url https www nltk org for license information see license txt counts paice s performance statistics for evaluating stemming algorithms what is required a dictionary of words grouped by their real lemmas a dictionary of words grouped by stems from a stemming algorithm when these are given understemming index ui overstemming index oi stemming weight sw and errorrate relative to truncation errt are counted references chris d paice 1994 an evaluation method for stemming algorithms in proceedings of sigir 4250 get original set of words used for analysis param lemmas a dictionary where keys are lemmas and values are sets or lists of words corresponding to that lemma type lemmas dictstr liststr return set of words that exist as values in the dictionary rtype setstr group words by stems defined by truncating them at given length param words set of words used for analysis param cutlength words are stemmed by cutting at this length type words setstr or liststr type cutlength int return dictionary where keys are stems and values are sets of words corresponding to that stem rtype dictstr setstr reference https en wikipedia orgwikilinelineintersection count intersection between two line segments defined by coordinate pairs param l1 tuple of two coordinate pairs defining the first line segment param l2 tuple of two coordinate pairs defining the second line segment type l1 tuplefloat float type l2 tuplefloat float return coordinates of the intersection rtype tuplefloat float when lines are parallel they must be on the yaxis we can ignore xaxis because we stop counting the truncation line when we get there there are no other options as ui xaxis grows and oi yaxis diminishes when we go along the truncation line get derivative of the line from 0 0 to given coordinates param coordinates a coordinate pair type coordinates tuplefloat float return derivative inf if x is zero rtype float count understemmed and overstemmed pairs for lemma stem pair with common words param lemmawords set or list of words corresponding to certain lemma param stems a dictionary where keys are stems and values are sets or lists of words corresponding to that stem type lemmawords setstr or liststr type stems dictstr setstr return amount of understemmed and overstemmed pairs contributed by words existing in both lemmawords and stems rtype tuplefloat float unachieved merge total wrongly merged total calculate actual and maximum possible amounts of understemmed and overstemmed word pairs param lemmas a dictionary where keys are lemmas and values are sets or lists of words corresponding to that lemma param stems a dictionary where keys are stems and values are sets or lists of words corresponding to that stem type lemmas dictstr liststr type stems dictstr setstr return global unachieved merge total gumt global desired merge total gdmt global wrongly merged total gwmt and global desired nonmerge total gdnt rtype tuplefloat float float float desired merge total desired nonmerge total for each lemma stem pair with common words count how many pairs are understemmed and overstemmed add to total undesired and wronglymerged totals each object is counted twice so divide by two count understemming index ui overstemming index oi and stemming weight sw param gumt gdmt gwmt gdnt global unachieved merge total gumt global desired merge total gdmt global wrongly merged total gwmt and global desired nonmerge total gdnt type gumt gdmt gwmt gdnt float return understemming index ui overstemming index oi and stemming weight sw rtype tuplefloat float float calculate understemming index ui overstemming index oi and stemming weight sw if gdmt max merge total is 0 define ui as 0 if gdnt max nonmerge total is 0 define oi as 0 oi and ui are 0 define sw as not a number ui is 0 define sw as infinity class for storing lemmas stems and evaluation metrics def initself lemmas stems self lemmas lemmas self stems stems self coords self gumt self gdmt self gwmt self gdnt none none none none self ui self oi self sw none none none self errt none self update def strself text global unachieved merge total gumt sn self gumt text appendglobal desired merge total gdmt sn self gdmt text appendglobal wronglymerged total gwmt sn self gwmt text appendglobal desired nonmerge total gdnt sn self gdnt text appendunderstemming index gumt gdmt sn self ui text appendoverstemming index gwmt gdnt sn self oi text appendstemming weight oi ui sn self sw text appenderrorrate relative to truncation errt srn self errt coordinates joins s item for item in self coords text appendtruncation line s coordinates return jointext def gettruncationindexesself words cutlength truncated truncatewords cutlength gumt gdmt gwmt gdnt calculateself lemmas truncated ui oi indexesgumt gdmt gwmt gdnt 2 return ui oi def gettruncationcoordinatesself cutlength0 words getwordsfromdictionaryself lemmas maxlength maxlenword for word in words truncate words from different points until 0 0 ui oi segment crosses the truncation line coords while cutlength maxlength get ui oi pair of current truncation point pair self gettruncationindexeswords cutlength store only new coordinates so we ll have an actual line segment when counting the intersection point if pair not in coords coords appendpair if pair 0 0 0 0 stop counting if truncation line goes through origo length from origo to truncation line is 0 return coords if lencoords 2 and pair0 0 0 derivative1 getderivativecoords2 derivative2 getderivativecoords1 derivative of the truncation line is a decreasing value when it passes stemming weight we ve found the segment of truncation line intersecting with 0 0 ui oi segment if derivative1 self sw derivative2 return coords cutlength 1 return coords def errtself count ui oi pairs for truncation points until we find the segment where ui oi crosses the truncation line self coords self gettruncationcoordinates if 0 0 0 0 in self coords truncation line goes through origo so errt cannot be counted if self ui self oi 0 0 0 0 return floatinf else return floatnan if self ui self oi 0 0 0 0 ui oi is origo define errt as 0 0 return 0 0 count the intersection point note that self ui self oi cannot be 0 0 0 0 and self coords has different coordinates so we have actual line segments instead of a line segment and a point intersection countintersection 0 0 self ui self oi self coords2 count op length of the line from origo to ui oi op sqrtself ui2 self oi2 count ot length of the line from origo to truncation line that goes through ui oi ot sqrtintersection0 2 intersection1 2 op ot tells how well the stemming algorithm works compared to just truncating words return op ot def updateself demonstration of the module some words with their real lemmas lemmas kneel kneel knelt range range ranged ring ring rang rung same words with stems from a stemming algorithm stems kneel kneel knelt knelt rang rang range ranged ring ring rung rung printwords grouped by their lemmas for lemma in sortedlemmas print formatlemma joinlemmaslemma print printsame words grouped by a stemming algorithm for stem in sortedstems print formatstem joinstemsstem print p paicelemmas stems printp print let s change results from a stemming algorithm stems kneel kneel knelt knelt rang rang range range ranged ring ring rung rung printcounting stats after changing stemming results for stem in sortedstems print formatstem joinstemsstem print p stems stems p update printp if name main demo natural language toolkit agreement metrics c 2001 2023 nltk project lauri hallila laurihallila gmail com url https www nltk org for license information see license txt counts paice s performance statistics for evaluating stemming algorithms what is required a dictionary of words grouped by their real lemmas a dictionary of words grouped by stems from a stemming algorithm when these are given understemming index ui overstemming index oi stemming weight sw and error rate relative to truncation errt are counted references chris d paice 1994 an evaluation method for stemming algorithms in proceedings of sigir 42 50 get original set of words used for analysis param lemmas a dictionary where keys are lemmas and values are sets or lists of words corresponding to that lemma type lemmas dict str list str return set of words that exist as values in the dictionary rtype set str group words by stems defined by truncating them at given length param words set of words used for analysis param cutlength words are stemmed by cutting at this length type words set str or list str type cutlength int return dictionary where keys are stems and values are sets of words corresponding to that stem rtype dict str set str reference https en wikipedia org wiki line line_intersection count intersection between two line segments defined by coordinate pairs param l1 tuple of two coordinate pairs defining the first line segment param l2 tuple of two coordinate pairs defining the second line segment type l1 tuple float float type l2 tuple float float return coordinates of the intersection rtype tuple float float lines are parallel when lines are parallel they must be on the y axis we can ignore x axis because we stop counting the truncation line when we get there there are no other options as ui x axis grows and oi y axis diminishes when we go along the truncation line get derivative of the line from 0 0 to given coordinates param coordinates a coordinate pair type coordinates tuple float float return derivative inf if x is zero rtype float count understemmed and overstemmed pairs for lemma stem pair with common words param lemmawords set or list of words corresponding to certain lemma param stems a dictionary where keys are stems and values are sets or lists of words corresponding to that stem type lemmawords set str or list str type stems dict str set str return amount of understemmed and overstemmed pairs contributed by words existing in both lemmawords and stems rtype tuple float float unachieved merge total wrongly merged total calculate actual and maximum possible amounts of understemmed and overstemmed word pairs param lemmas a dictionary where keys are lemmas and values are sets or lists of words corresponding to that lemma param stems a dictionary where keys are stems and values are sets or lists of words corresponding to that stem type lemmas dict str list str type stems dict str set str return global unachieved merge total gumt global desired merge total gdmt global wrongly merged total gwmt and global desired non merge total gdnt rtype tuple float float float float desired merge total desired non merge total for each lemma stem pair with common words count how many pairs are understemmed and overstemmed add to total undesired and wrongly merged totals each object is counted twice so divide by two count understemming index ui overstemming index oi and stemming weight sw param gumt gdmt gwmt gdnt global unachieved merge total gumt global desired merge total gdmt global wrongly merged total gwmt and global desired non merge total gdnt type gumt gdmt gwmt gdnt float return understemming index ui overstemming index oi and stemming weight sw rtype tuple float float float calculate understemming index ui overstemming index oi and stemming weight sw if gdmt max merge total is 0 define ui as 0 if gdnt max non merge total is 0 define oi as 0 oi and ui are 0 define sw as not a number ui is 0 define sw as infinity class for storing lemmas stems and evaluation metrics param lemmas a dictionary where keys are lemmas and values are sets or lists of words corresponding to that lemma param stems a dictionary where keys are stems and values are sets or lists of words corresponding to that stem type lemmas dict str list str type stems dict str set str count ui oi when stemming is done by truncating words at cutlength param words words used for the analysis param cutlength words are stemmed by cutting them at this length type words set str or list str type cutlength int return understemming and overstemming indexes rtype tuple int int count ui oi pairs for truncation points until we find the segment where ui oi crosses the truncation line param cutlength optional parameter to start counting from ui oi coordinates gotten by stemming at this length useful for speeding up the calculations when you know the approximate location of the intersection type cutlength int return list of coordinate pairs that define the truncation line rtype list tuple float float truncate words from different points until 0 0 ui oi segment crosses the truncation line get ui oi pair of current truncation point store only new coordinates so we ll have an actual line segment when counting the intersection point stop counting if truncation line goes through origo length from origo to truncation line is 0 derivative of the truncation line is a decreasing value when it passes stemming weight we ve found the segment of truncation line intersecting with 0 0 ui oi segment count error rate relative to truncation errt return errt length of the line from origo to ui oi divided by the length of the line from origo to the point defined by the same line when extended until the truncation line rtype float count ui oi pairs for truncation points until we find the segment where ui oi crosses the truncation line truncation line goes through origo so errt cannot be counted ui oi is origo define errt as 0 0 count the intersection point note that self ui self oi cannot be 0 0 0 0 and self coords has different coordinates so we have actual line segments instead of a line segment and a point count op length of the line from origo to ui oi count ot length of the line from origo to truncation line that goes through ui oi op ot tells how well the stemming algorithm works compared to just truncating words update statistics after lemmas and stems have been set demonstration of the module some words with their real lemmas same words with stems from a stemming algorithm let s change results from a stemming algorithm
from math import sqrt


def get_words_from_dictionary(lemmas):
    
    words = set()
    for lemma in lemmas:
        words.update(set(lemmas[lemma]))
    return words


def _truncate(words, cutlength):
    
    stems = {}
    for word in words:
        stem = word[:cutlength]
        try:
            stems[stem].update([word])
        except KeyError:
            stems[stem] = {word}
    return stems



def _count_intersection(l1, l2):
    
    x1, y1 = l1[0]
    x2, y2 = l1[1]
    x3, y3 = l2[0]
    x4, y4 = l2[1]

    denominator = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)

    if denominator == 0.0:  
        if x1 == x2 == x3 == x4 == 0.0:
            
            
            
            
            
            return (0.0, y4)

    x = (
        (x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)
    ) / denominator
    y = (
        (x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)
    ) / denominator
    return (x, y)


def _get_derivative(coordinates):
    
    try:
        return coordinates[1] / coordinates[0]
    except ZeroDivisionError:
        return float("inf")


def _calculate_cut(lemmawords, stems):
    
    umt, wmt = 0.0, 0.0
    for stem in stems:
        cut = set(lemmawords) & set(stems[stem])
        if cut:
            cutcount = len(cut)
            stemcount = len(stems[stem])
            
            umt += cutcount * (len(lemmawords) - cutcount)
            
            wmt += cutcount * (stemcount - cutcount)
    return (umt, wmt)


def _calculate(lemmas, stems):
    

    n = sum(len(lemmas[word]) for word in lemmas)

    gdmt, gdnt, gumt, gwmt = (0.0, 0.0, 0.0, 0.0)

    for lemma in lemmas:
        lemmacount = len(lemmas[lemma])

        
        gdmt += lemmacount * (lemmacount - 1)

        
        gdnt += lemmacount * (n - lemmacount)

        
        
        umt, wmt = _calculate_cut(lemmas[lemma], stems)

        
        gumt += umt
        gwmt += wmt

    
    return (gumt / 2, gdmt / 2, gwmt / 2, gdnt / 2)


def _indexes(gumt, gdmt, gwmt, gdnt):
    
    
    
    try:
        ui = gumt / gdmt
    except ZeroDivisionError:
        
        ui = 0.0
    try:
        oi = gwmt / gdnt
    except ZeroDivisionError:
        
        oi = 0.0
    try:
        sw = oi / ui
    except ZeroDivisionError:
        if oi == 0.0:
            
            sw = float("nan")
        else:
            
            sw = float("inf")
    return (ui, oi, sw)


class Paice:
    

    def __init__(self, lemmas, stems):
        
        self.lemmas = lemmas
        self.stems = stems
        self.coords = []
        self.gumt, self.gdmt, self.gwmt, self.gdnt = (None, None, None, None)
        self.ui, self.oi, self.sw = (None, None, None)
        self.errt = None
        self.update()

    def __str__(self):
        text = ["Global Unachieved Merge Total (GUMT): %s\n" % self.gumt]
        text.append("Global Desired Merge Total (GDMT): %s\n" % self.gdmt)
        text.append("Global Wrongly-Merged Total (GWMT): %s\n" % self.gwmt)
        text.append("Global Desired Non-merge Total (GDNT): %s\n" % self.gdnt)
        text.append("Understemming Index (GUMT / GDMT): %s\n" % self.ui)
        text.append("Overstemming Index (GWMT / GDNT): %s\n" % self.oi)
        text.append("Stemming Weight (OI / UI): %s\n" % self.sw)
        text.append("Error-Rate Relative to Truncation (ERRT): %s\r\n" % self.errt)
        coordinates = " ".join(["(%s, %s)" % item for item in self.coords])
        text.append("Truncation line: %s" % coordinates)
        return "".join(text)

    def _get_truncation_indexes(self, words, cutlength):
        

        truncated = _truncate(words, cutlength)
        gumt, gdmt, gwmt, gdnt = _calculate(self.lemmas, truncated)
        ui, oi = _indexes(gumt, gdmt, gwmt, gdnt)[:2]
        return (ui, oi)

    def _get_truncation_coordinates(self, cutlength=0):
        
        words = get_words_from_dictionary(self.lemmas)
        maxlength = max(len(word) for word in words)

        
        coords = []
        while cutlength <= maxlength:
            
            pair = self._get_truncation_indexes(words, cutlength)

            
            
            if pair not in coords:
                coords.append(pair)
            if pair == (0.0, 0.0):
                
                
                return coords
            if len(coords) >= 2 and pair[0] > 0.0:
                derivative1 = _get_derivative(coords[-2])
                derivative2 = _get_derivative(coords[-1])
                
                
                
                if derivative1 >= self.sw >= derivative2:
                    return coords
            cutlength += 1
        return coords

    def _errt(self):
        
        
        self.coords = self._get_truncation_coordinates()
        if (0.0, 0.0) in self.coords:
            
            if (self.ui, self.oi) != (0.0, 0.0):
                return float("inf")
            else:
                return float("nan")
        if (self.ui, self.oi) == (0.0, 0.0):
            
            return 0.0
        
        
        
        intersection = _count_intersection(
            ((0, 0), (self.ui, self.oi)), self.coords[-2:]
        )
        
        op = sqrt(self.ui**2 + self.oi**2)
        
        ot = sqrt(intersection[0] ** 2 + intersection[1] ** 2)
        
        return op / ot

    def update(self):
        
        self.gumt, self.gdmt, self.gwmt, self.gdnt = _calculate(self.lemmas, self.stems)
        self.ui, self.oi, self.sw = _indexes(self.gumt, self.gdmt, self.gwmt, self.gdnt)
        self.errt = self._errt()


def demo():
    
    
    lemmas = {
        "kneel": ["kneel", "knelt"],
        "range": ["range", "ranged"],
        "ring": ["ring", "rang", "rung"],
    }
    
    stems = {
        "kneel": ["kneel"],
        "knelt": ["knelt"],
        "rang": ["rang", "range", "ranged"],
        "ring": ["ring"],
        "rung": ["rung"],
    }
    print("Words grouped by their lemmas:")
    for lemma in sorted(lemmas):
        print("{} => {}".format(lemma, " ".join(lemmas[lemma])))
    print()
    print("Same words grouped by a stemming algorithm:")
    for stem in sorted(stems):
        print("{} => {}".format(stem, " ".join(stems[stem])))
    print()
    p = Paice(lemmas, stems)
    print(p)
    print()
    
    stems = {
        "kneel": ["kneel"],
        "knelt": ["knelt"],
        "rang": ["rang"],
        "range": ["range", "ranged"],
        "ring": ["ring"],
        "rung": ["rung"],
    }
    print("Counting stats after changing stemming results:")
    for stem in sorted(stems):
        print("{} => {}".format(stem, " ".join(stems[stem])))
    print()
    p.stems = stems
    p.update()
    print(p)


if __name__ == "__main__":
    demo()