(
    acronym: str, window: Span, threshold: float = 0.8,
)
return (definition, confidence)
Identify most likely definition for an acronym given a list of tokens.

    Args:
        acronym: acronym for which definition is sought
        window: a span of tokens from which definition extraction will be attempted
        threshold: minimum "confidence" in definition required for acceptance;
            valid values in [0.0, 1.0]; higher value => stricter threshold

    Returns:
        Most likely definition for given acronym ('' if none found),
        along with the confidence assigned to it

    References:
        Taghva, Kazem, and Jeff Gilbreth. "Recognizing acronyms and their definitions."
        International Journal on Document Analysis and Recognition 1.4 (1999): 191-198.
Identify most likely definition for an acronym given a list of tokens.
Identify most likely definition for an acronym given a list of tokens .
def _get_acronym_definition(
    acronym: str, window: Span, threshold: float = 0.8,
) -> Tuple[str, float]:
    """
    Identify most likely definition for an acronym given a list of tokens.

    Args:
        acronym: acronym for which definition is sought
        window: a span of tokens from which definition extraction will be attempted
        threshold: minimum "confidence" in definition required for acceptance;
            valid values in [0.0, 1.0]; higher value => stricter threshold

    Returns:
        Most likely definition for given acronym ('' if none found),
        along with the confidence assigned to it

    References:
        Taghva, Kazem, and Jeff Gilbreth. "Recognizing acronyms and their definitions."
        International Journal on Document Analysis and Recognition 1.4 (1999): 191-198.
    """

    def build_lcs_matrix(X, Y):
        m = len(X)
        n = len(Y)
        b = np.zeros((m, n), dtype=int)
        c = np.zeros((m, n), dtype=int)
        for i in range(0, m):
            for j in range(0, n):
                if X[i] == Y[j]:
                    c[i, j] = c[i - 1, j - 1] + 1
                    b[i, j] = 1
                elif c[i - 1, j] >= c[i, j - 1]:
                    c[i, j] = c[i - 1, j]
                else:
                    c[i, j] = c[i, j - 1]
        return c, b

    def parse_lcs_matrix(b, start_i, start_j, lcs_length, stack, vectors):
        m = b.shape[0]
        n = b.shape[1]
        for i in range(start_i, m):
            for j in range(start_j, n):
                if b[i, j] == 1:
                    s = (i, j)
                    stack.append(s)
                    if lcs_length == 1:
                        vec = [np.NaN] * n
                        for k, l in stack:
                            vec[l] = k
                        vectors.append(vec)
                    else:
                        parse_lcs_matrix(b, i + 1, j + 1, lcs_length - 1, stack, vectors)
                    stack = []
        return vectors

    def vector_values(v, types):
        vv = {}
        first = v.index(int(np.nanmin(v)))
        last = v.index(int(np.nanmax(v)))
        vv["size"] = (last - first) + 1
        vv["distance"] = len(v) - last
        vv["stop_count"] = 0
        vv["misses"] = 0
        for i in range(first, last + 1):
            if v[i] >= 0 and types[i] == "s":
                vv["stop_count"] += 1
            elif v[i] is None and types[i] not in ["s", "h"]:
                vv["misses"] += 1
        return vv

    def compare_vectors(A, B, types):
        vv_A = vector_values(A, types)
        vv_B = vector_values(B, types)
        # no one-letter matches, sorryboutit
        if vv_A["size"] == 1:
            return B
        elif vv_B["size"] == 1:
            return A
        if vv_A["misses"] > vv_B["misses"]:
            return B
        elif vv_A["misses"] < vv_B["misses"]:
            return A
        if vv_A["stop_count"] > vv_B["stop_count"]:
            return B
        if vv_A["stop_count"] < vv_B["stop_count"]:
            return A
        if vv_A["distance"] > vv_B["distance"]:
            return B
        elif vv_A["distance"] < vv_B["distance"]:
            return A
        if vv_A["size"] > vv_B["size"]:
            return B
        elif vv_A["size"] < vv_B["size"]:
            return A
        return A

    # get definition window's leading characters and word types
    def_leads = []
    def_types = []
    for tok in window:
        tok_text = tok.text
        if tok.is_stop:
            def_leads.append(tok_text[0])
            def_types.append("s")
        elif is_acronym(tok_text):
            def_leads.append(tok_text[0])
            def_types.append("a")
        elif "-" in tok_text and not tok_text.startswith("-"):
            tok_split = [t[0] for t in tok_text.split("-") if t]
            def_leads.extend(tok_split)
            def_types.extend("H" if i == 0 else "h" for i in range(len(tok_split)))
        else:
            def_leads.append(tok_text[0])
            def_types.append("w")
    def_leads = "".join(def_leads).lower()
    def_types = "".join(def_types)

    # extract alphanumeric characters from acronym
    acr_leads = "".join(c for c in acronym if c.isalnum())
    # handle special cases of '&' and trailing 's'
    acr_leads = acr_leads.replace("&", "a")
    if acr_leads.endswith("s"):
        # bail out if it's only a 2-letter acronym to start with, e.g. 'Is'
        if len(acr_leads) == 2:
            return ("", 0)
        acr_leads = acr_leads[:-1]
    acr_leads = acr_leads.lower()

    c, b = build_lcs_matrix(acr_leads, def_leads)

    # 4.4.1
    lcs_length = c[c.shape[0] - 1, c.shape[1] - 1]
    confidence = lcs_length / len(acronym)
    if confidence < threshold:
        return ("", confidence)

    vecs = parse_lcs_matrix(b, 0, 0, lcs_length, [], [])
    # first letter of acronym must be present
    vecs = [vec for vec in vecs if 0 in vec]
    if not vecs:
        return ("", confidence)

    best_vec = vecs[0]
    for vec in vecs[1:]:
        best_vec = compare_vectors(best_vec, vec, def_types)

    first = best_vec.index(int(np.nanmin(best_vec)))
    last = best_vec.index(int(np.nanmax(best_vec)))

    definition = window[first : last + 1].text
    if len(definition.split()) == 1:
        return ("", confidence)

    return (definition, confidence)
def _get_acronym_definition ( acronym : str , window : Span , threshold : float = 0.8 , ) -> Tuple [ str , float ] : def build_lcs_matrix ( X , Y ) : m = len ( X ) n = len ( Y ) b = np . zeros ( ( m , n ) , dtype = int ) c = np . zeros ( ( m , n ) , dtype = int ) for i in range ( 0 , m ) : for j in range ( 0 , n ) : if X [ i ] == Y [ j ] : c [ i , j ] = c [ i - 1 , j - 1 ] + 1 b [ i , j ] = 1 elif c [ i - 1 , j ] >= c [ i , j - 1 ] : c [ i , j ] = c [ i - 1 , j ] else : c [ i , j ] = c [ i , j - 1 ] return c , b def parse_lcs_matrix ( b , start_i , start_j , lcs_length , stack , vectors ) : m = b . shape [ 0 ] n = b . shape [ 1 ] for i in range ( start_i , m ) : for j in range ( start_j , n ) : if b [ i , j ] == 1 : s = ( i , j ) stack . append ( s ) if lcs_length == 1 : vec = [ np . NaN ] * n for k , l in stack : vec [ l ] = k vectors . append ( vec ) else : parse_lcs_matrix ( b , i + 1 , j + 1 , lcs_length - 1 , stack , vectors ) stack = [ ] return vectors def vector_values ( v , types ) : vv = { } first = v . index ( int ( np . nanmin ( v ) ) ) last = v . index ( int ( np . nanmax ( v ) ) ) vv [ "size" ] = ( last - first ) + 1 vv [ "distance" ] = len ( v ) - last vv [ "stop_count" ] = 0 vv [ "misses" ] = 0 for i in range ( first , last + 1 ) : if v [ i ] >= 0 and types [ i ] == "s" : vv [ "stop_count" ] += 1 elif v [ i ] is None and types [ i ] not in [ "s" , "h" ] : vv [ "misses" ] += 1 return vv def compare_vectors ( A , B , types ) : vv_A = vector_values ( A , types ) vv_B = vector_values ( B , types ) # no one-letter matches, sorryboutit if vv_A [ "size" ] == 1 : return B elif vv_B [ "size" ] == 1 : return A if vv_A [ "misses" ] > vv_B [ "misses" ] : return B elif vv_A [ "misses" ] < vv_B [ "misses" ] : return A if vv_A [ "stop_count" ] > vv_B [ "stop_count" ] : return B if vv_A [ "stop_count" ] < vv_B [ "stop_count" ] : return A if vv_A [ "distance" ] > vv_B [ "distance" ] : return B elif vv_A [ "distance" ] < vv_B [ "distance" ] : return A if vv_A [ "size" ] > vv_B [ "size" ] : return B elif vv_A [ "size" ] < vv_B [ "size" ] : return A return A # get definition window's leading characters and word types def_leads = [ ] def_types = [ ] for tok in window : tok_text = tok . text if tok . is_stop : def_leads . append ( tok_text [ 0 ] ) def_types . append ( "s" ) elif is_acronym ( tok_text ) : def_leads . append ( tok_text [ 0 ] ) def_types . append ( "a" ) elif "-" in tok_text and not tok_text . startswith ( "-" ) : tok_split = [ t [ 0 ] for t in tok_text . split ( "-" ) if t ] def_leads . extend ( tok_split ) def_types . extend ( "H" if i == 0 else "h" for i in range ( len ( tok_split ) ) ) else : def_leads . append ( tok_text [ 0 ] ) def_types . append ( "w" ) def_leads = "" . join ( def_leads ) . lower ( ) def_types = "" . join ( def_types ) # extract alphanumeric characters from acronym acr_leads = "" . join ( c for c in acronym if c . isalnum ( ) ) # handle special cases of '&' and trailing 's' acr_leads = acr_leads . replace ( "&" , "a" ) if acr_leads . endswith ( "s" ) : # bail out if it's only a 2-letter acronym to start with, e.g. 'Is' if len ( acr_leads ) == 2 : return ( "" , 0 ) acr_leads = acr_leads [ : - 1 ] acr_leads = acr_leads . lower ( ) c , b = build_lcs_matrix ( acr_leads , def_leads ) # 4.4.1 lcs_length = c [ c . shape [ 0 ] - 1 , c . shape [ 1 ] - 1 ] confidence = lcs_length / len ( acronym ) if confidence < threshold : return ( "" , confidence ) vecs = parse_lcs_matrix ( b , 0 , 0 , lcs_length , [ ] , [ ] ) # first letter of acronym must be present vecs = [ vec for vec in vecs if 0 in vec ] if not vecs : return ( "" , confidence ) best_vec = vecs [ 0 ] for vec in vecs [ 1 : ] : best_vec = compare_vectors ( best_vec , vec , def_types ) first = best_vec . index ( int ( np . nanmin ( best_vec ) ) ) last = best_vec . index ( int ( np . nanmax ( best_vec ) ) ) definition = window [ first : last + 1 ] . text if len ( definition . split ( ) ) == 1 : return ( "" , confidence ) return ( definition , confidence )