abydos.distance._jaro_winkler.JaroWinkler.sim()

Complexity

Conditions

31

Size

Total Lines	155
Code Lines	70

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	61
CRAP Score	31

Importance

Changes

0

# Copyright 2014-2020 by Christopher C. Little.
    def sim(self, src: str, tar: str) -> float:
        """Return the Jaro or Jaro-Winkler similarity of two strings.

        Parameters
        ----------
        src : str
            Source string for comparison
        tar : str
            Target string for comparison

        Returns
        -------
        float
            Jaro or Jaro-Winkler similarity

        Raises
        ------
        ValueError
            Unsupported boost_threshold assignment; boost_threshold must be
            between 0 and 1.
        ValueError
            Unsupported scaling_factor assignment; scaling_factor must be
            between 0 and 0.25.'

        Examples
        --------
        >>> cmp = JaroWinkler()
        >>> round(cmp.sim('cat', 'hat'), 12)
        0.777777777778
        >>> round(cmp.sim('Niall', 'Neil'), 12)
        0.805
        >>> round(cmp.sim('aluminum', 'Catalan'), 12)
        0.60119047619
        >>> round(cmp.sim('ATCG', 'TAGC'), 12)
        0.833333333333

        >>> cmp = JaroWinkler(mode='jaro')
        >>> round(cmp.sim('cat', 'hat'), 12)
        0.777777777778
        >>> round(cmp.sim('Niall', 'Neil'), 12)
        0.783333333333
        >>> round(cmp.sim('aluminum', 'Catalan'), 12)
        0.60119047619
        >>> round(cmp.sim('ATCG', 'TAGC'), 12)
        0.833333333333


        .. versionadded:: 0.1.0
        .. versionchanged:: 0.3.6
            Encapsulated in class

        """
        if self._mode == 'winkler':
            if self._boost_threshold > 1 or self._boost_threshold < 0:
                raise ValueError(
                    'Unsupported boost_threshold assignment; '
                    + 'boost_threshold must be between 0 and 1.'
                )
            if self._scaling_factor > 0.25 or self._scaling_factor < 0:
                raise ValueError(
                    'Unsupported scaling_factor assignment; '
                    + 'scaling_factor must be between 0 and 0.25.'
                )

        if src == tar:
            return 1.0

        tokenizer = QGrams(self._qval)
        tokenizer.tokenize(src.strip())
        src_list = tokenizer.get_list()
        tokenizer.tokenize(tar.strip())
        tar_list = tokenizer.get_list()

        lens = len(src_list)
        lent = len(tar_list)

        # If either string is blank - return - added in Version 2
        if lens == 0 or lent == 0:
            return 0.0

        if lens > lent:
            search_range = lens
            minv = lent
        else:
            search_range = lent
            minv = lens

        # Zero out the flags
        src_flag = [0] * search_range
        tar_flag = [0] * search_range
        search_range = max(0, search_range // 2 - 1)

        # Looking only within the search range,
        # count and flag the matched pairs.
        num_com = 0
        yl1 = lent - 1
        for i in range(lens):
            low_lim = (i - search_range) if (i >= search_range) else 0
            hi_lim = (i + search_range) if ((i + search_range) <= yl1) else yl1
            for j in range(low_lim, hi_lim + 1):
                if (tar_flag[j] == 0) and (tar_list[j] == src_list[i]):
                    tar_flag[j] = 1
                    src_flag[i] = 1
                    num_com += 1
                    break

        # If no characters in common - return
        if num_com == 0:
            return 0.0

        # Count the number of transpositions
        k = n_trans = 0
        for i in range(lens):
            if src_flag[i] != 0:
                j = 0
                for j in range(k, lent):  # pragma: no branch
                    if tar_flag[j] != 0:
                        k = j + 1
                        break
                if src_list[i] != tar_list[j]:
                    n_trans += 1
        n_trans //= 2

        # Main weight computation for Jaro distance
        weight = (
            num_com / lens + num_com / lent + (num_com - n_trans) / num_com
        )
        weight /= 3.0

        # Continue to boost the weight if the strings are similar
        # This is the Winkler portion of Jaro-Winkler distance
        if self._mode == 'winkler' and weight > self._boost_threshold:

            # Adjust for having up to the first 4 characters in common
            j = 4 if (minv >= 4) else minv
            i = 0
            while (i < j) and (src_list[i] == tar_list[i]):
                i += 1
            weight += i * self._scaling_factor * (1.0 - weight)

            # Optionally adjust for long strings.

            # After agreeing beginning chars, at least two more must agree and
            # the agreeing characters must be > .5 of remaining characters.
            if (
                self._long_strings
                and (minv > 4)
                and (num_com > i + 1)
                and (2 * num_com >= minv + i)
            ):
                weight += (1.0 - weight) * (
                    (num_com - i - 1) / (lens + lent - i * 2 + 2)
                )

        return weight