abydos.distance.lcsstr() - Code Metrics - Inspection of "fixed threshold checking" - chrislit/abydos - Measure and Improve Code Quality continuously with Scrutinizer

Test Failed
Push — master ( 52414d...a2edde )

by Chris
created 2018-09-25 00:40 UTC
abydos.distance.lcsstr() A

↳ Parent: abydos.distance
Complexity

Conditions
Size

Total Lines	42
Code Lines	12
Duplication

Lines	0
Ratio	0 %
Importance

Changes
Metric	Value
cc	5
eloc	12
nop	2
dl	0
loc	42
rs	9.3333
c	0
b	0
f	0
# -*- coding: utf-8 -*-

# Copyright 2014-2018 by Christopher C. Little.
# This file is part of Abydos.
#
# Abydos is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# Abydos is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with Abydos. If not, see <http://www.gnu.org/licenses/>.

"""abydos.distance.

The distance module implements string edit distance functions including:

    - Levenshtein distance
    - Optimal String Alignment distance
    - Levenshtein-Damerau distance
    - Hamming distance
    - Tversky index
    - Sørensen–Dice coefficient & distance
    - Jaccard similarity coefficient & distance
    - overlap similarity & distance
    - Tanimoto coefficient & distance
    - Minkowski distance & similarity
    - Manhattan distance & similarity
    - Euclidean distance & similarity
    - Chebyshev distance & similarity
    - cosine similarity & distance
    - Jaro distance
    - Jaro-Winkler distance (incl. the strcmp95 algorithm variant)
    - Longest common substring
    - Ratcliff-Obershelp similarity & distance
    - Match Rating Algorithm similarity
    - Normalized Compression Distance (NCD) & similarity
    - Monge-Elkan similarity & distance
    - Matrix similarity
    - Needleman-Wunsch score
    - Smither-Waterman score
    - Gotoh score
    - Length similarity
    - Prefix, Suffix, and Identity similarity & distance
    - Modified Language-Independent Product Name Search (MLIPNS) similarity &
      distance
    - Bag distance
    - Editex distance
    - Eudex distances
    - Sift4 distance
    - Baystat distance & similarity
    - Typo distance
    - Indel distance

Functions beginning with the prefixes 'sim' and 'dist' are guaranteed to be
in the range [0, 1], and sim_X = 1 - dist_X since the two are complements.
If a sim_X function is supplied identical src & tar arguments, it is guaranteed
to return 1; the corresponding dist_X function is guaranteed to return 0.
"""

from __future__ import division, unicode_literals

from codecs import encode
from collections import Counter, Iterable, defaultdict
from math import log, sqrt
from sys import maxsize, modules
from types import GeneratorType
from unicodedata import normalize

from numpy import float32 as np_float32
from numpy import int as np_int
from numpy import zeros as np_zeros

from six import text_type
from six.moves import range

from .compression import ac_encode, ac_train, rle_encode
from .fingerprint import synoname_toolcode, _synoname_special_table
from .phonetic import eudex, mra
from .qgram import QGrams

try:
    import lzma
except ImportError:  # pragma: no cover
    # If the system lacks the lzma library, that's fine, but lzma comrpession
    # similarity won't be supported.
    pass


def levenshtein(src, tar, mode='lev', cost=(1, 1, 1, 1)):
    """Return the Levenshtein distance between two strings.

    This is the standard edit distance measure. Cf.
    :cite:`Levenshtein:1965,Levenshtein:1966`.

    Two additional variants: optimal string alignment (aka restricted
    Damerau-Levenshtein distance) :cite:`Boytsov:2011` and the
    Damerau-Levenshtein :cite:`Damerau:1964` distance are also supported.

    The ordinary Levenshtein & Optimal String Alignment distance both
    employ the Wagner-Fischer dynamic programming algorithm
    :cite:`Wagner:1974`.

    Levenshtein edit distance ordinarily has unit insertion, deletion, and
    substitution costs.

    :param str src, tar: two strings to be compared
    :param str mode: specifies a mode for computing the Levenshtein distance:

        - 'lev' (default) computes the ordinary Levenshtein distance,
          in which edits may include inserts, deletes, and substitutions
        - 'osa' computes the Optimal String Alignment distance, in which
          edits may include inserts, deletes, substitutions, and
          transpositions but substrings may only be edited once
        - 'dam' computes the Damerau-Levenshtein distance, in which
          edits may include inserts, deletes, substitutions, and
          transpositions and substrings may undergo repeated edits

    :param tuple cost: a 4-tuple representing the cost of the four possible
        edits: inserts, deletes, substitutions, and transpositions,
        respectively (by default: (1, 1, 1, 1))
    :returns: the Levenshtein distance between src & tar
    :rtype: int (may return a float if cost has float values)

    >>> levenshtein('cat', 'hat')
    1
    >>> levenshtein('Niall', 'Neil')
    3
    >>> levenshtein('aluminum', 'Catalan')
    7
    >>> levenshtein('ATCG', 'TAGC')
    3

    >>> levenshtein('ATCG', 'TAGC', mode='osa')
    2
    >>> levenshtein('ACTG', 'TAGC', mode='osa')
    4

    >>> levenshtein('ATCG', 'TAGC', mode='dam')
    2
    >>> levenshtein('ACTG', 'TAGC', mode='dam')
    3
    """
    ins_cost, del_cost, sub_cost, trans_cost = cost

    if src == tar:
        return 0
    if not src:
        return len(tar) * ins_cost
    if not tar:
        return len(src) * del_cost

    if 'dam' in mode:
        return damerau_levenshtein(src, tar, cost)

    # pylint: disable=no-member
    d_mat = np_zeros((len(src)+1, len(tar)+1), dtype=np_int)
    # pylint: enable=no-member
    for i in range(len(src)+1):
        d_mat[i, 0] = i * del_cost
    for j in range(len(tar)+1):
        d_mat[0, j] = j * ins_cost

    for i in range(len(src)):
        for j in range(len(tar)):
            d_mat[i+1, j+1] = min(
                d_mat[i+1, j] + ins_cost,  # ins
                d_mat[i, j+1] + del_cost,  # del
                d_mat[i, j] + (sub_cost if src[i] != tar[j] else 0)  # sub/==
            )

            if mode == 'osa':
                if ((i+1 > 1 and j+1 > 1 and src[i] == tar[j-1] and
                     src[i-1] == tar[j])):
                    # transposition
                    d_mat[i+1, j+1] = min(d_mat[i+1, j+1],
                                          d_mat[i-1, j-1] + trans_cost)

    return d_mat[len(src), len(tar)]


def dist_levenshtein(src, tar, mode='lev', cost=(1, 1, 1, 1)):
    """Return the normalized Levenshtein distance between two strings.

    The Levenshtein distance is normalized by dividing the Levenshtein distance
    (calculated by any of the three supported methods) by the greater of
    the number of characters in src times the cost of a delete and
    the number of characters in tar times the cost of an insert.
    For the case in which all operations have :math:`cost = 1`, this is
    equivalent to the greater of the length of the two strings src & tar.

    :param str src, tar: two strings to be compared
    :param str mode: specifies a mode for computing the Levenshtein distance:

        - 'lev' (default) computes the ordinary Levenshtein distance,
          in which edits may include inserts, deletes, and substitutions
        - 'osa' computes the Optimal String Alignment distance, in which
          edits may include inserts, deletes, substitutions, and
          transpositions but substrings may only be edited once
        - 'dam' computes the Damerau-Levenshtein distance, in which
          edits may include inserts, deletes, substitutions, and
          transpositions and substrings may undergo repeated edits

    :param tuple cost: a 4-tuple representing the cost of the four possible
        edits: inserts, deletes, substitutions, and transpositions,
        respectively (by default: (1, 1, 1, 1))
    :returns: normalized Levenshtein distance
    :rtype: float

    >>> round(dist_levenshtein('cat', 'hat'), 12)
    0.333333333333
    >>> round(dist_levenshtein('Niall', 'Neil'), 12)
    0.6
    >>> dist_levenshtein('aluminum', 'Catalan')
    0.875
    >>> dist_levenshtein('ATCG', 'TAGC')
    0.75
    """
    if src == tar:
        return 0
    ins_cost, del_cost = cost[:2]
    return (levenshtein(src, tar, mode, cost) /
            (max(len(src)*del_cost, len(tar)*ins_cost)))


def sim_levenshtein(src, tar, mode='lev', cost=(1, 1, 1, 1)):
    """Return the Levenshtein similarity of two strings.

    Normalized Levenshtein similarity is the complement of normalized
    Levenshtein distance:
    :math:`sim_{Levenshtein} = 1 - dist_{Levenshtein}`.

    :param str src, tar: two strings to be compared
    :param str mode: specifies a mode for computing the Levenshtein distance:

            - 'lev' (default) computes the ordinary Levenshtein distance,
              in which edits may include inserts, deletes, and substitutions
            - 'osa' computes the Optimal String Alignment distance, in which
              edits may include inserts, deletes, substitutions, and
              transpositions but substrings may only be edited once
            - 'dam' computes the Damerau-Levenshtein distance, in which
              edits may include inserts, deletes, substitutions, and
              transpositions and substrings may undergo repeated edits

    :param tuple cost: a 4-tuple representing the cost of the four possible
        edits:
        inserts, deletes, substitutions, and transpositions, respectively
        (by default: (1, 1, 1, 1))
    :returns: normalized Levenshtein similarity
    :rtype: float

    >>> round(sim_levenshtein('cat', 'hat'), 12)
    0.666666666667
    >>> round(sim_levenshtein('Niall', 'Neil'), 12)
    0.4
    >>> sim_levenshtein('aluminum', 'Catalan')
    0.125
    >>> sim_levenshtein('ATCG', 'TAGC')
    0.25
    """
    return 1 - dist_levenshtein(src, tar, mode, cost)


def damerau_levenshtein(src, tar, cost=(1, 1, 1, 1)):
    """Return the Damerau-Levenshtein distance between two strings.

    This computes the Damerau-Levenshtein distance :cite:`Damerau:1964`.
    Damerau-Levenshtein code is based on Java code by Kevin L. Stern
    :cite:`Stern:2014`, under the MIT license:
    https://github.com/KevinStern/software-and-algorithms/blob/master/src/main/java/blogspot/software_and_algorithms/stern_library/string/DamerauLevenshteinAlgorithm.java

    :param str src, tar: two strings to be compared
    :param tuple cost: a 4-tuple representing the cost of the four possible
        edits:
        inserts, deletes, substitutions, and transpositions, respectively
        (by default: (1, 1, 1, 1))
    :returns: the Damerau-Levenshtein distance between src & tar
    :rtype: int (may return a float if cost has float values)

    >>> damerau_levenshtein('cat', 'hat')
    1
    >>> damerau_levenshtein('Niall', 'Neil')
    3
    >>> damerau_levenshtein('aluminum', 'Catalan')
    7
    >>> damerau_levenshtein('ATCG', 'TAGC')
    2
    """
    ins_cost, del_cost, sub_cost, trans_cost = cost

    if src == tar:
        return 0
    if not src:
        return len(tar) * ins_cost
    if not tar:
        return len(src) * del_cost

    if 2*trans_cost < ins_cost + del_cost:
        raise ValueError('Unsupported cost assignment; the cost of two ' +
                         'transpositions must not be less than the cost of ' +
                         'an insert plus a delete.')

    # pylint: disable=no-member
    d_mat = (np_zeros((len(src))*(len(tar)), dtype=np_int).
             reshape((len(src), len(tar))))
    # pylint: enable=no-member

    if src[0] != tar[0]:
        d_mat[0, 0] = min(sub_cost, ins_cost + del_cost)

    src_index_by_character = {}
    src_index_by_character[src[0]] = 0
    for i in range(1, len(src)):
        del_distance = d_mat[i-1, 0] + del_cost
        ins_distance = (i+1) * del_cost + ins_cost
        match_distance = (i * del_cost +
                          (0 if src[i] == tar[0] else sub_cost))
        d_mat[i, 0] = min(del_distance, ins_distance, match_distance)

    for j in range(1, len(tar)):
        del_distance = (j+1) * ins_cost + del_cost
        ins_distance = d_mat[0, j-1] + ins_cost
        match_distance = (j * ins_cost +
                          (0 if src[0] == tar[j] else sub_cost))
        d_mat[0, j] = min(del_distance, ins_distance, match_distance)

    for i in range(1, len(src)):
        max_src_letter_match_index = (0 if src[i] == tar[0] else -1)
        for j in range(1, len(tar)):
            candidate_swap_index = (-1 if tar[j] not in
                                    src_index_by_character else
                                    src_index_by_character[tar[j]])
            j_swap = max_src_letter_match_index
            del_distance = d_mat[i-1, j] + del_cost
            ins_distance = d_mat[i, j-1] + ins_cost
            match_distance = d_mat[i-1, j-1]
            if src[i] != tar[j]:
                match_distance += sub_cost
            else:
                max_src_letter_match_index = j

            if candidate_swap_index != -1 and j_swap != -1:
                i_swap = candidate_swap_index

                if i_swap == 0 and j_swap == 0:
                    pre_swap_cost = 0
                else:
                    pre_swap_cost = d_mat[max(0, i_swap-1), max(0, j_swap-1)]
                swap_distance = (pre_swap_cost + (i - i_swap - 1) *
                                 del_cost + (j - j_swap - 1) * ins_cost +
                                 trans_cost)
            else:
                swap_distance = maxsize

            d_mat[i, j] = min(del_distance, ins_distance,
                              match_distance, swap_distance)
        src_index_by_character[src[i]] = i

    return d_mat[len(src)-1, len(tar)-1]


def dist_damerau(src, tar, cost=(1, 1, 1, 1)):
    """Return the Damerau-Levenshtein similarity of two strings.

    Damerau-Levenshtein distance normalized to the interval [0, 1].

    The Damerau-Levenshtein distance is normalized by dividing the
    Damerau-Levenshtein distance by the greater of
    the number of characters in src times the cost of a delete and
    the number of characters in tar times the cost of an insert.
    For the case in which all operations have :math:`cost = 1`, this is
    equivalent to the greater of the length of the two strings src & tar.

    The arguments are identical to those of the levenshtein() function.

    :param str src, tar: two strings to be compared
    :param tuple cost: a 4-tuple representing the cost of the four possible
        edits:
        inserts, deletes, substitutions, and transpositions, respectively
        (by default: (1, 1, 1, 1))
    :returns: normalized Damerau-Levenshtein distance
    :rtype: float

    >>> round(dist_damerau('cat', 'hat'), 12)
    0.333333333333
    >>> round(dist_damerau('Niall', 'Neil'), 12)
    0.6
    >>> dist_damerau('aluminum', 'Catalan')
    0.875
    >>> dist_damerau('ATCG', 'TAGC')
    0.5
    """
    if src == tar:
        return 0
    ins_cost, del_cost = cost[:2]
    return (damerau_levenshtein(src, tar, cost) /
            (max(len(src)*del_cost, len(tar)*ins_cost)))


def sim_damerau(src, tar, cost=(1, 1, 1, 1)):
    """Return the Damerau-Levenshtein similarity of two strings.

    Normalized Damerau-Levenshtein similarity the complement of normalized
    Damerau-Levenshtein distance:
    :math:`sim_{Damerau} = 1 - dist_{Damerau}`.

    The arguments are identical to those of the levenshtein() function.

    :param str src, tar: two strings to be compared
    :param tuple cost: a 4-tuple representing the cost of the four possible
        edits:
        inserts, deletes, substitutions, and transpositions, respectively
        (by default: (1, 1, 1, 1))
    :returns: normalized Damerau-Levenshtein similarity
    :rtype: float

    >>> round(sim_damerau('cat', 'hat'), 12)
    0.666666666667
    >>> round(sim_damerau('Niall', 'Neil'), 12)
    0.4
    >>> sim_damerau('aluminum', 'Catalan')
    0.125
    >>> sim_damerau('ATCG', 'TAGC')
    0.5
    """
    return 1 - dist_damerau(src, tar, cost)


def hamming(src, tar, difflens=True):
    """Return the Hamming distance between two strings.

    Hamming distance :cite:`Hamming:1950` equals the number of character
    positions at which two strings differ. For strings of unequal lengths,
    it is not normally defined. By default, this implementation calculates the
    Hamming distance of the first n characters where n is the lesser of the two
    strings' lengths and adds to this the difference in string lengths.

    :param str src, tar: two strings to be compared
    :param bool allow_different_lengths:
        If True (default), this returns the Hamming distance for those
        characters that have a matching character in both strings plus the
        difference in the strings' lengths. This is equivalent to extending
        the shorter string with obligatorily non-matching characters.
        If False, an exception is raised in the case of strings of unequal
        lengths.
    :returns: the Hamming distance between src & tar
    :rtype: int

    >>> hamming('cat', 'hat')
    1
    >>> hamming('Niall', 'Neil')
    3
    >>> hamming('aluminum', 'Catalan')
    8
    >>> hamming('ATCG', 'TAGC')
    4
    """
    if not difflens and len(src) != len(tar):
        raise ValueError('Undefined for sequences of unequal length; set ' +
                         'difflens to True for Hamming distance between ' +
                         'strings of unequal lengths.')

    hdist = 0
    if difflens:
        hdist += abs(len(src)-len(tar))
    hdist += sum(c1 != c2 for c1, c2 in zip(src, tar))

    return hdist


def dist_hamming(src, tar, difflens=True):
    """Return the normalized Hamming distance between two strings.

    Hamming distance normalized to the interval [0, 1].

    The Hamming distance is normalized by dividing it
    by the greater of the number of characters in src & tar (unless difflens is
    set to False, in which case an exception is raised).

    The arguments are identical to those of the hamming() function.

    :param str src, tar: two strings to be compared
    :param bool allow_different_lengths:
        If True (default), this returns the Hamming distance for those
        characters that have a matching character in both strings plus the
        difference in the strings' lengths. This is equivalent to extending
        the shorter string with obligatorily non-matching characters.
        If False, an exception is raised in the case of strings of unequal
        lengths.
    :returns: normalized Hamming distance
    :rtype: float

    >>> round(dist_hamming('cat', 'hat'), 12)
    0.333333333333
    >>> dist_hamming('Niall', 'Neil')
    0.6
    >>> dist_hamming('aluminum', 'Catalan')
    1.0
    >>> dist_hamming('ATCG', 'TAGC')
    1.0
    """
    if src == tar:
        return 0
    return hamming(src, tar, difflens) / max(len(src), len(tar))


def sim_hamming(src, tar, difflens=True):
    """Return the normalized Hamming similarity of two strings.

    Hamming similarity normalized to the interval [0, 1].

    Hamming similarity is the complement of normalized Hamming distance:
    :math:`sim_{Hamming} = 1 - dist{Hamming}`.

    Provided that difflens==True, the Hamming similarity is identical to the
    Language-Independent Product Name Search (LIPNS) similarity score. For
    further information, see the sim_mlipns documentation.

    The arguments are identical to those of the hamming() function.

    :param str src, tar: two strings to be compared
    :param bool allow_different_lengths:
        If True (default), this returns the Hamming distance for those
        characters that have a matching character in both strings plus the
        difference in the strings' lengths. This is equivalent to extending
        the shorter string with obligatorily non-matching characters.
        If False, an exception is raised in the case of strings of unequal
        lengths.
    :returns: normalized Hamming similarity
    :rtype: float

    >>> round(sim_hamming('cat', 'hat'), 12)
    0.666666666667
    >>> sim_hamming('Niall', 'Neil')
    0.4
    >>> sim_hamming('aluminum', 'Catalan')
    0.0
    >>> sim_hamming('ATCG', 'TAGC')
    0.0
    """
    return 1 - dist_hamming(src, tar, difflens)


def _get_qgrams(src, tar, qval=None, skip=0):
    """Return the Q-Grams in src & tar.

    :param str src, tar: two strings to be compared
        (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :param int skip: the number of characters to skip (only works when
        src and tar are strings
    :return: Q-Grams
    """
    if isinstance(src, Counter) and isinstance(tar, Counter):
        return src, tar
    if qval and qval > 0:
        return (QGrams(src, qval, '$#', skip),
                QGrams(tar, qval, '$#', skip))
    return Counter(src.strip().split()), Counter(tar.strip().split())


def sim_tversky(src, tar, qval=2, alpha=1, beta=1, bias=None):
    r"""Return the Tversky index of two strings.

    The Tversky index :cite:`Tversky:1977` is defined as:
    For two sets X and Y:
    :math:`sim_{Tversky}(X, Y) = \\frac{|X \\cap Y|}
    {|X \\cap Y| + \\alpha|X - Y| + \\beta|Y - X|}`.

    :math:`\\alpha = \\beta = 1` is equivalent to the Jaccard & Tanimoto
    similarity coefficients.

    :math:`\\alpha = \\beta = 0.5` is equivalent to the Sørensen-Dice
    similarity coefficient :cite:`Dice:1945,Sorensen:1948`.

    Unequal α and β will tend to emphasize one or the other set's
    contributions:

        - :math:`\\alpha > \\beta` emphasizes the contributions of X over Y
        - :math:`\\alpha < \\beta` emphasizes the contributions of Y over X)

    Parameter values' relation to 1 emphasizes different types of
    contributions:

        - :math:`\\alpha and \\beta > 1` emphsize unique contributions over the
          intersection
        - :math:`\\alpha and \\beta < 1` emphsize the intersection over unique
          contributions

    The symmetric variant is defined in :cite:`Jiminez:2013`. This is activated
    by specifying a bias parameter.

    :param str src, tar: two strings to be compared
        (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :param float alpha, beta: two Tversky index parameters as indicated in the
        description below
    :returns: Tversky similarity
    :rtype: float

    >>> sim_tversky('cat', 'hat')
    0.3333333333333333
    >>> sim_tversky('Niall', 'Neil')
    0.2222222222222222
    >>> sim_tversky('aluminum', 'Catalan')
    0.0625
    >>> sim_tversky('ATCG', 'TAGC')
    0.0
    """
    if alpha < 0 or beta < 0:
        raise ValueError('Unsupported weight assignment; alpha and beta ' +
                         'must be greater than or equal to 0.')

    if src == tar:
        return 1.0
    elif not src or not tar:
        return 0.0

    q_src, q_tar = _get_qgrams(src, tar, qval)
    q_src_mag = sum(q_src.values())
    q_tar_mag = sum(q_tar.values())
    q_intersection_mag = sum((q_src & q_tar).values())

    if not q_src or not q_tar:
        return 0.0

    if bias is None:
        return q_intersection_mag / (q_intersection_mag + alpha *
                                     (q_src_mag - q_intersection_mag) +
                                     beta * (q_tar_mag - q_intersection_mag))

    a_val = min(q_src_mag - q_intersection_mag,
                q_tar_mag - q_intersection_mag)
    b_val = max(q_src_mag - q_intersection_mag,
                q_tar_mag - q_intersection_mag)
    c_val = q_intersection_mag + bias
    return c_val / (beta * (alpha * a_val + (1 - alpha) * b_val) + c_val)


def dist_tversky(src, tar, qval=2, alpha=1, beta=1, bias=None):
    """Return the Tverssky distance between two strings.

    Tversky distance is the complement of the Tvesrsky index (similarity):
    :math:`dist_{Tversky} = 1-sim_{Tversky}`.

    :param str src, tar: two strings to be compared
        (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :param float alpha, beta: two Tversky index parameters as indicated in the
        description below
    :returns: Tversky distance
    :rtype: float

    >>> dist_tversky('cat', 'hat')
    0.6666666666666667
    >>> dist_tversky('Niall', 'Neil')
    0.7777777777777778
    >>> dist_tversky('aluminum', 'Catalan')
    0.9375
    >>> dist_tversky('ATCG', 'TAGC')
    1.0
    """
    return 1 - sim_tversky(src, tar, qval, alpha, beta, bias)


def sim_dice(src, tar, qval=2):
    r"""Return the Sørensen–Dice coefficient of two strings.

    For two sets X and Y, the Sørensen–Dice coefficient
    :cite:`Dice:1945,Sorensen:1948` is
    :math:`sim_{dice}(X, Y) = \\frac{2 \\cdot |X \\cap Y|}{|X| + |Y|}`.

    This is identical to the Tanimoto similarity coefficient
    :cite:`Tanimoto:1958` and the Tversky index :cite:`Tversky:1977` for
    :math:`\\alpha = \\beta = 0.5`.

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :returns: Sørensen–Dice similarity
    :rtype: float

    >>> sim_dice('cat', 'hat')
    0.5
    >>> sim_dice('Niall', 'Neil')
    0.36363636363636365
    >>> sim_dice('aluminum', 'Catalan')
    0.11764705882352941
    >>> sim_dice('ATCG', 'TAGC')
    0.0
    """
    return sim_tversky(src, tar, qval, 0.5, 0.5)


def dist_dice(src, tar, qval=2):
    """Return the Sørensen–Dice distance between two strings.

    Sørensen–Dice distance is the complemenjt of the Sørensen–Dice coefficient:
    :math:`dist_{dice} = 1 - sim_{dice}`.

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :returns: Sørensen–Dice distance
    :rtype: float

    >>> dist_dice('cat', 'hat')
    0.5
    >>> dist_dice('Niall', 'Neil')
    0.6363636363636364
    >>> dist_dice('aluminum', 'Catalan')
    0.8823529411764706
    >>> dist_dice('ATCG', 'TAGC')
    1.0
    """
    return 1 - sim_dice(src, tar, qval)


def sim_jaccard(src, tar, qval=2):
    r"""Return the Jaccard similarity of two strings.

    For two sets X and Y, the Jaccard similarity coefficient
    :cite:`Jaccard:1901` is :math:`sim_{jaccard}(X, Y) =
    \\frac{|X \\cap Y|}{|X \\cup Y|}`.

    This is identical to the Tanimoto similarity coefficient
    :cite:`Tanimoto:1958`
    and the Tversky index :cite:`Tversky:1977` for
    :math:`\\alpha = \\beta = 1`.

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :returns: Jaccard similarity
    :rtype: float

    >>> sim_jaccard('cat', 'hat')
    0.3333333333333333
    >>> sim_jaccard('Niall', 'Neil')
    0.2222222222222222
    >>> sim_jaccard('aluminum', 'Catalan')
    0.0625
    >>> sim_jaccard('ATCG', 'TAGC')
    0.0
    """
    return sim_tversky(src, tar, qval, 1, 1)


def dist_jaccard(src, tar, qval=2):
    """Return the Jaccard distance between two strings.

    Jaccard distance is the complement of the Jaccard similarity coefficient:
    :math:`dist_{Jaccard} = 1 - sim_{Jaccard}`.

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :returns: Jaccard distance
    :rtype: float

    >>> dist_jaccard('cat', 'hat')
    0.6666666666666667
    >>> dist_jaccard('Niall', 'Neil')
    0.7777777777777778
    >>> dist_jaccard('aluminum', 'Catalan')
    0.9375
    >>> dist_jaccard('ATCG', 'TAGC')
    1.0
    """
    return 1 - sim_jaccard(src, tar, qval)


def sim_overlap(src, tar, qval=2):
    r"""Return the overlap coefficient of two strings.

    For two sets X and Y, the overlap coefficient
    :cite:`Szymkiewicz:1934,Simpson:1949`, also called the
    Szymkiewicz-Simpson coefficient, is
    :math:`sim_{overlap}(X, Y) = \\frac{|X \\cap Y|}{min(|X|, |Y|)}`.

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :returns: overlap similarity
    :rtype: float

    >>> sim_overlap('cat', 'hat')
    0.5
    >>> sim_overlap('Niall', 'Neil')
    0.4
    >>> sim_overlap('aluminum', 'Catalan')
    0.125
    >>> sim_overlap('ATCG', 'TAGC')
    0.0
    """
    if src == tar:
        return 1.0
    elif not src or not tar:
        return 0.0

    q_src, q_tar = _get_qgrams(src, tar, qval)
    q_src_mag = sum(q_src.values())
    q_tar_mag = sum(q_tar.values())
    q_intersection_mag = sum((q_src & q_tar).values())

    return q_intersection_mag / min(q_src_mag, q_tar_mag)


def dist_overlap(src, tar, qval=2):
    """Return the overlap distance between two strings.

    Overlap distance is the complement of the overlap coefficient:
    :math:`sim_{overlap} = 1 - dist_{overlap}`.

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :returns: overlap distance
    :rtype: float

    >>> dist_overlap('cat', 'hat')
    0.5
    >>> dist_overlap('Niall', 'Neil')
    0.6
    >>> dist_overlap('aluminum', 'Catalan')
    0.875
    >>> dist_overlap('ATCG', 'TAGC')
    1.0
    """
    return 1 - sim_overlap(src, tar, qval)


def sim_tanimoto(src, tar, qval=2):
    r"""Return the Tanimoto similarity of two strings.

    For two sets X and Y, the Tanimoto similarity coefficient
    :cite:`Tanimoto:1958` is
    :math:`sim_{Tanimoto}(X, Y) = \\frac{|X \\cap Y|}{|X \\cup Y|}`.

    This is identical to the Jaccard similarity coefficient
    :cite:`Jaccard:1901` and the Tversky index :cite:`Tversky:1977` for
    :math:`\\alpha = \\beta = 1`.

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :returns: Tanimoto similarity
    :rtype: float

    >>> sim_tanimoto('cat', 'hat')
    0.3333333333333333
    >>> sim_tanimoto('Niall', 'Neil')
    0.2222222222222222
    >>> sim_tanimoto('aluminum', 'Catalan')
    0.0625
    >>> sim_tanimoto('ATCG', 'TAGC')
    0.0
    """
    return sim_jaccard(src, tar, qval)


def tanimoto(src, tar, qval=2):
    """Return the Tanimoto distance between two strings.

    Tanimoto distance is :math:`-log_{2}sim_{Tanimoto}`.

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :returns: Tanimoto distance
    :rtype: float

    >>> tanimoto('cat', 'hat')
    -1.5849625007211563
    >>> tanimoto('Niall', 'Neil')
    -2.1699250014423126
    >>> tanimoto('aluminum', 'Catalan')
    -4.0
    >>> tanimoto('ATCG', 'TAGC')
    -inf
    """
    coeff = sim_jaccard(src, tar, qval)
    if coeff != 0:
        return log(coeff, 2)

    return float('-inf')


def minkowski(src, tar, qval=2, pval=1, normalize=False):
    """Return the Minkowski distance (:math:`L^p-norm`) of two strings.

    The Minkowsky distance :cite:`Minkowski:1910` is a distance metric in
    :math:`L^p-space`.

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :param pval: the :math:`p`-value of the :math:`L^p`-space.
    :param normalize: normalizes to [0, 1] if True
    :returns: the Minkowski distance
    :rtype: float
    """
    q_src, q_tar = _get_qgrams(src, tar, qval)
    diffs = ((q_src - q_tar) + (q_tar - q_src)).values()

    normalizer = 1
    if normalize:
        totals = (q_src + q_tar).values()
        if pval == 0:
            normalizer = len(totals)
        else:
            normalizer = sum(_**pval for _ in totals)**(1 / pval)

    if pval == float('inf'):
        # Chebyshev distance
        return max(diffs)/normalizer
    if pval == 0:
        # This is the l_0 "norm" as developed by David Donoho
        return len(diffs)
    return sum(_**pval for _ in diffs)**(1 / pval)/normalizer


def dist_minkowski(src, tar, qval=2, pval=1):
    """Return Minkowski distance of two strings, normalized to [0, 1].

    The normalized Minkowsky distance :cite:`Minkowski:1910` is a distance
    metric in :math:`L^p-space`, normalized to [0, 1].

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :param pval: the :math:`p`-value of the :math:`L^p`-space.
    :returns: the normalized Minkowski distance
    :rtype: float
    """
    return minkowski(src, tar, qval, pval, True)


def sim_minkowski(src, tar, qval=2, pval=1):
    """Return Minkowski similarity of two strings, normalized to [0, 1].

    Minkowski similarity is the complement of Minkowski distance:
    :math:`sim_{Minkowski} = 1 - dist_{Minkowski}`.

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :param pval: the :math:`p`-value of the :math:`L^p`-space.
    :returns: the normalized Minkowski similarity
    :rtype: float
    """
    return 1-minkowski(src, tar, qval, pval, True)


def manhattan(src, tar, qval=2, normalize=False):
    """Return the Manhattan distance between two strings.

    Manhattan distance is the city-block or taxi-cab distance, equivalent
    to Minkowski distance in :math:`L^1`-space.

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :param pval: the :math:`p`-value of the :math:`L^p`-space.
    :param normalize: normalizes to [0, 1] if True
    :returns: the Manhattan distance
    :rtype: float
    """
    return minkowski(src, tar, qval, 1, normalize)


def dist_manhattan(src, tar, qval=2):
    """Return the Manhattan distance between two strings, normalized to [0, 1].

    The normalized Manhattan distance is a distance
    metric in :math:`L^1-space`, normalized to [0, 1].

    This is identical to Canberra distance.

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :param pval: the :math:`p`-value of the :math:`L^p`-space.
    :returns: the normalized Manhattan distance
    :rtype: float
    """
    return manhattan(src, tar, qval, 1, True)


def sim_manhattan(src, tar, qval=2):
    """Return the Manhattan similarity of two strings, normalized to [0, 1].

    Manhattan similarity is the complement of Manhattan distance:
    :math:`sim_{Manhattan} = 1 - dist_{Manhattan}`.

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :param pval: the :math:`p`-value of the :math:`L^p`-space.
    :returns: the normalized Manhattan similarity
    :rtype: float
    """
    return 1-manhattan(src, tar, qval, 1, True)


def euclidean(src, tar, qval=2, normalize=False):
    """Return the Euclidean distance between two strings.

    Euclidean distance is the straigh-line or as-the-crow-flies distance,
    equivalent to Minkowski distance in :math:`L^2`-space.

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :param pval: the :math:`p`-value of the :math:`L^p`-space.
    :param normalize: normalizes to [0, 1] if True
    :returns: the Euclidean distance
    :rtype: float
    """
    return minkowski(src, tar, qval, 2, normalize)


def dist_euclidean(src, tar, qval=2):
    """Return the Euclidean distance between two strings, normalized to [0, 1].

    The normalized Euclidean distance is a distance
    metric in :math:`L^2-space`, normalized to [0, 1].

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :param pval: the :math:`p`-value of the :math:`L^p`-space.
    :returns: the normalized Euclidean distance
    :rtype: float
    """
    return euclidean(src, tar, qval, True)


def sim_euclidean(src, tar, qval=2):
    """Return the Euclidean similarity of two strings, normalized to [0, 1].

    Euclidean similarity is the complement of Euclidean distance:
    :math:`sim_{Euclidean} = 1 - dist_{Euclidean}`.

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :param pval: the :math:`p`-value of the :math:`L^p`-space.
    :returns: the normalized Euclidean similarity
    :rtype: float
    """
    return 1-euclidean(src, tar, qval, True)


def chebyshev(src, tar, qval=2, normalize=False):
    r"""Return the Chebyshev distance between two strings.

    Euclidean distance is the chessboard distance,
    equivalent to Minkowski distance in :math:`L^\infty`-space.

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :param pval: the :math:`p`-value of the :math:`L^p`-space.
    :param normalize: normalizes to [0, 1] if True
    :returns: the Chebyshev distance
    :rtype: float
    """
    return minkowski(src, tar, qval, float('inf'), normalize)


def dist_chebyshev(src, tar, qval=2):
    """Return the Chebyshev distance between two strings, normalized to [0, 1].

    The normalized Chebyshev distance :cite:`Minkowski:1910` is a distance
    metric in :math:`L^p-space`, normalized to [0, 1].

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :param pval: the :math:`p`-value of the :math:`L^p`-space.
    :returns: the normalized Chebyshev distance
    :rtype: float
    """
    return chebyshev(src, tar, qval, True)


def sim_chebyshev(src, tar, qval=2):
    """Return the Chebyshev similarity of two strings, normalized to [0, 1].

    Chebyshev similarity is the complement of Chebyshev distance:
    :math:`sim_{Chebyshev} = 1 - dist_{Chebyshev}`.

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :param pval: the :math:`p`-value of the :math:`L^p`-space.
    :returns: the normalized Chebyshev similarity
    :rtype: float
    """
    return 1 - chebyshev(src, tar, qval, True)


def sim_cosine(src, tar, qval=2):
    r"""Return the cosine similarity of two strings.

    For two sets X and Y, the cosine similarity, Otsuka-Ochiai coefficient, or
    Ochiai coefficient :cite:`Otsuka:1936,Ochiai:1957` is:
    :math:`sim_{cosine}(X, Y) = \\frac{|X \\cap Y|}{\\sqrt{|X| \\cdot |Y|}}`.

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :returns: cosine similarity
    :rtype: float

    >>> sim_cosine('cat', 'hat')
    0.5
    >>> sim_cosine('Niall', 'Neil')
    0.3651483716701107
    >>> sim_cosine('aluminum', 'Catalan')
    0.11785113019775793
    >>> sim_cosine('ATCG', 'TAGC')
    0.0
    """
    if src == tar:
        return 1.0
    if not src or not tar:
        return 0.0

    q_src, q_tar = _get_qgrams(src, tar, qval)
    q_src_mag = sum(q_src.values())
    q_tar_mag = sum(q_tar.values())
    q_intersection_mag = sum((q_src & q_tar).values())

    return q_intersection_mag / sqrt(q_src_mag * q_tar_mag)


def dist_cosine(src, tar, qval=2):
    """Return the cosine distance between two strings.

    Cosine distance is the complement of cosine similarity:
    :math:`dist_{cosine} = 1 - sim_{cosine}`.

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :returns: cosine distance
    :rtype: float

    >>> dist_cosine('cat', 'hat')
    0.5
    >>> dist_cosine('Niall', 'Neil')
    0.6348516283298893
    >>> dist_cosine('aluminum', 'Catalan')
    0.882148869802242
    >>> dist_cosine('ATCG', 'TAGC')
    1.0
    """
    return 1 - sim_cosine(src, tar, qval)


def sim_strcmp95(src, tar, long_strings=False):
    """Return the strcmp95 similarity of two strings.

    This is a Python translation of the C code for strcmp95:
    http://web.archive.org/web/20110629121242/http://www.census.gov/geo/msb/stand/strcmp.c
    :cite:`Winkler:1994`.
    The above file is a US Government publication and, accordingly,
    in the public domain.

    This is based on the Jaro-Winkler distance, but also attempts to correct
    for some common typos and frequently confused characters. It is also
    limited to uppercase ASCII characters, so it is appropriate to American
    names, but not much else.

    :param str src, tar: two strings to be compared
    :param bool long_strings: set to True to "Increase the probability of a
        match when the number of matched characters is large.  This option
        allows for a little more tolerance when the strings are large. It is
        not an appropriate test when comparing fixed length fields such as
        phone and social security numbers."
    :returns: strcmp95 similarity
    :rtype: float

    >>> sim_strcmp95('cat', 'hat')
    0.7777777777777777
    >>> sim_strcmp95('Niall', 'Neil')
    0.8454999999999999
    >>> sim_strcmp95('aluminum', 'Catalan')
    0.6547619047619048
    >>> sim_strcmp95('ATCG', 'TAGC')
    0.8333333333333334
    """
    def _inrange(char):
        """Return True if char is in the range (0, 91)."""
        return ord(char) > 0 and ord(char) < 91

    ying = src.strip().upper()
    yang = tar.strip().upper()

    if ying == yang:
        return 1.0
    # If either string is blank - return - added in Version 2
    if not ying or not yang:
        return 0.0

    adjwt = defaultdict(int)
    sp_mx = (
        ('A', 'E'), ('A', 'I'), ('A', 'O'), ('A', 'U'), ('B', 'V'), ('E', 'I'),
        ('E', 'O'), ('E', 'U'), ('I', 'O'), ('I', 'U'), ('O', 'U'), ('I', 'Y'),
        ('E', 'Y'), ('C', 'G'), ('E', 'F'), ('W', 'U'), ('W', 'V'), ('X', 'K'),
        ('S', 'Z'), ('X', 'S'), ('Q', 'C'), ('U', 'V'), ('M', 'N'), ('L', 'I'),
        ('Q', 'O'), ('P', 'R'), ('I', 'J'), ('2', 'Z'), ('5', 'S'), ('8', 'B'),
        ('1', 'I'), ('1', 'L'), ('0', 'O'), ('0', 'Q'), ('C', 'K'), ('G', 'J')
    )

    # Initialize the adjwt array on the first call to the function only.
    # The adjwt array is used to give partial credit for characters that
    # may be errors due to known phonetic or character recognition errors.
    # A typical example is to match the letter "O" with the number "0"
    for i in sp_mx:
        adjwt[(i[0], i[1])] = 3
        adjwt[(i[1], i[0])] = 3

    if len(ying) > len(yang):
        search_range = len(ying)
        minv = len(yang)
    else:
        search_range = len(yang)
        minv = len(ying)

    # Blank out the flags
    ying_flag = [0] * search_range
    yang_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 = len(yang) - 1
    for i in range(len(ying)):
        lowlim = (i - search_range) if (i >= search_range) else 0
        hilim = (i + search_range) if ((i + search_range) <= yl1) else yl1
        for j in range(lowlim, hilim+1):
            if (yang_flag[j] == 0) and (yang[j] == ying[i]):
                yang_flag[j] = 1
                ying_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(len(ying)):
        if ying_flag[i] != 0:
            for j in range(k, len(yang)):
                if yang_flag[j] != 0:
                    k = j + 1
                    break
            if ying[i] != yang[j]:

                n_trans += 1
    n_trans = n_trans // 2

    # Adjust for similarities in unmatched characters
    n_simi = 0
    if minv > num_com:
        for i in range(len(ying)):
            if ying_flag[i] == 0 and _inrange(ying[i]):
                for j in range(len(yang)):
                    if yang_flag[j] == 0 and _inrange(yang[j]):
                        if (ying[i], yang[j]) in adjwt:
                            n_simi += adjwt[(ying[i], yang[j])]
                            yang_flag[j] = 2
                            break
    num_sim = n_simi/10.0 + num_com

    # Main weight computation
    weight = num_sim / len(ying) + num_sim / len(yang) + \
        (num_com - n_trans) / num_com
    weight = weight / 3.0

    # Continue to boost the weight if the strings are similar
    if weight > 0.7:

        # Adjust for having up to the first 4 characters in common
        j = 4 if (minv >= 4) else minv
        i = 0
        while (i < j) and (ying[i] == yang[i]) and (not ying[i].isdigit()):
            i += 1
        if i:
            weight += i * 0.1 * (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 (((long_strings) and (minv > 4) and (num_com > i+1) and
             (2*num_com >= minv+i))):
            if not ying[0].isdigit():
                weight += (1.0-weight) * ((num_com-i-1) /
                                          (len(ying)+len(yang)-i*2+2))

    return weight


def dist_strcmp95(src, tar, long_strings=False):
    """Return the strcmp95 distance between two strings.

    strcmp95 distance is the complement of strcmp95 similarity:
    :math:`dist_{strcmp95} = 1 - sim_{strcmp95}`.

    :param str src, tar: two strings to be compared
    :param bool long_strings: set to True to "Increase the probability of a
        match when the number of matched characters is large.  This option
        allows for a little more tolerance when the strings are large. It is
        not an appropriate test when comparing fixed length fields such as
        phone and social security numbers."
    :returns: strcmp95 distance
    :rtype: float

    >>> round(dist_strcmp95('cat', 'hat'), 12)
    0.222222222222
    >>> round(dist_strcmp95('Niall', 'Neil'), 12)
    0.1545
    >>> round(dist_strcmp95('aluminum', 'Catalan'), 12)
    0.345238095238
    >>> round(dist_strcmp95('ATCG', 'TAGC'), 12)
    0.166666666667
    """
    return 1 - sim_strcmp95(src, tar, long_strings)


def sim_jaro_winkler(src, tar, qval=1, mode='winkler', long_strings=False,
                     boost_threshold=0.7, scaling_factor=0.1):
    """Return the Jaro or Jaro-Winkler similarity of two strings.

    Jaro(-Winkler) distance is a string edit distance initially proposed by
    Jaro and extended by Winkler :cite:`Jaro:1989,Winkler:1990`.

    This is Python based on the C code for strcmp95:
    http://web.archive.org/web/20110629121242/http://www.census.gov/geo/msb/stand/strcmp.c
    :cite:`Winkler:1994`. The above file is a US Government publication and,
    accordingly, in the public domain.

    :param str src, tar: two strings to be compared
    :param int qval: the length of each q-gram (defaults to 1: character-wise
        matching)
    :param str mode: indicates which variant of this distance metric to
        compute:

            - 'winkler' -- computes the Jaro-Winkler distance (default) which
              increases the score for matches near the start of the word
            - 'jaro' -- computes the Jaro distance

    The following arguments apply only when mode is 'winkler':

    :param bool long_strings: set to True to "Increase the probability of a
        match when the number of matched characters is large.  This option
        allows for a little more tolerance when the strings are large.  It is
        not an appropriate test when comparing fixed length fields such as
        phone and social security numbers."
    :param float boost_threshold: a value between 0 and 1, below which the
        Winkler boost is not applied (defaults to 0.7)
    :param float scaling_factor: a value between 0 and 0.25, indicating by how
        much to boost scores for matching prefixes (defaults to 0.1)

    :returns: Jaro or Jaro-Winkler similarity
    :rtype: float

    >>> round(sim_jaro_winkler('cat', 'hat'), 12)
    0.777777777778
    >>> round(sim_jaro_winkler('Niall', 'Neil'), 12)
    0.805
    >>> round(sim_jaro_winkler('aluminum', 'Catalan'), 12)
    0.60119047619
    >>> round(sim_jaro_winkler('ATCG', 'TAGC'), 12)
    0.833333333333

    >>> round(sim_jaro_winkler('cat', 'hat', mode='jaro'), 12)
    0.777777777778
    >>> round(sim_jaro_winkler('Niall', 'Neil', mode='jaro'), 12)
    0.783333333333
    >>> round(sim_jaro_winkler('aluminum', 'Catalan', mode='jaro'), 12)
    0.60119047619
    >>> round(sim_jaro_winkler('ATCG', 'TAGC', mode='jaro'), 12)
    0.833333333333
    """
    if mode == 'winkler':
        if boost_threshold > 1 or boost_threshold < 0:
            raise ValueError('Unsupported boost_threshold assignment; ' +
                             'boost_threshold must be between 0 and 1.')
        if scaling_factor > 0.25 or scaling_factor < 0:
            raise ValueError('Unsupported scaling_factor assignment; ' +
                             'scaling_factor must be between 0 and 0.25.')

    if src == tar:
        return 1.0

    src = QGrams(src.strip(), qval).ordered_list
    tar = QGrams(tar.strip(), qval).ordered_list

    lens = len(src)
    lent = len(tar)

    # 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):
        lowlim = (i - search_range) if (i >= search_range) else 0
        hilim = (i + search_range) if ((i + search_range) <= yl1) else yl1
        for j in range(lowlim, hilim+1):
            if (tar_flag[j] == 0) and (tar[j] == src[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:
            for j in range(k, lent):
                if tar_flag[j] != 0:
                    k = j + 1
                    break
            if src[i] != tar[j]:

                n_trans += 1
    n_trans = n_trans // 2

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

    # Continue to boost the weight if the strings are similar
    # This is the Winkler portion of Jaro-Winkler distance
    if mode == 'winkler' and weight > 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[i] == tar[i]):
            i += 1
        if i:
            weight += i * 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 (((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


def dist_jaro_winkler(src, tar, qval=1, mode='winkler', long_strings=False,
                      boost_threshold=0.7, scaling_factor=0.1):
    """Return the Jaro or Jaro-Winkler distance between two strings.

    Jaro(-Winkler) similarity is the complement of Jaro(-Winkler) distance:
    :math:`sim_{Jaro(-Winkler)} = 1 - dist_{Jaro(-Winkler)}`.

    :param str src, tar: two strings to be compared
    :param int qval: the length of each q-gram (defaults to 1: character-wise
        matching)
    :param str mode: indicates which variant of this distance metric to
        compute:

            - 'winkler' -- computes the Jaro-Winkler distance (default) which
              increases the score for matches near the start of the word
            - 'jaro' -- computes the Jaro distance

    The following arguments apply only when mode is 'winkler':

    :param bool long_strings: set to True to "Increase the probability of a
        match when the number of matched characters is large.  This option
        allows for a little more tolerance when the strings are large.  It is
        not an appropriate test when comparing fixed length fields such as
        phone and social security numbers."
    :param float boost_threshold: a value between 0 and 1, below which the
        Winkler boost is not applied (defaults to 0.7)
    :param float scaling_factor: a value between 0 and 0.25, indicating by how
        much to boost scores for matching prefixes (defaults to 0.1)

    :returns: Jaro or Jaro-Winkler distance
    :rtype: float

    >>> round(dist_jaro_winkler('cat', 'hat'), 12)
    0.222222222222
    >>> round(dist_jaro_winkler('Niall', 'Neil'), 12)
    0.195
    >>> round(dist_jaro_winkler('aluminum', 'Catalan'), 12)
    0.39880952381
    >>> round(dist_jaro_winkler('ATCG', 'TAGC'), 12)
    0.166666666667

    >>> round(dist_jaro_winkler('cat', 'hat', mode='jaro'), 12)
    0.222222222222
    >>> round(dist_jaro_winkler('Niall', 'Neil', mode='jaro'), 12)
    0.216666666667
    >>> round(dist_jaro_winkler('aluminum', 'Catalan', mode='jaro'), 12)
    0.39880952381
    >>> round(dist_jaro_winkler('ATCG', 'TAGC', mode='jaro'), 12)
    0.166666666667
    """
    return 1 - sim_jaro_winkler(src, tar, qval, mode, long_strings,
                                boost_threshold, scaling_factor)


def lcsseq(src, tar):
    """Return the longest common subsequence of two strings.

    Longest common subsequence (LCSseq) is the longest subsequence of
    characters that two strings have in common.

    Based on the dynamic programming algorithm from
    http://rosettacode.org/wiki/Longest_common_subsequence#Dynamic_Programming_6
    :cite:`rosettacode:2018b`. This is licensed GFDL 1.2.

    Modifications include:
        conversion to a numpy array in place of a list of lists

    :param str src, tar: two strings to be compared
    :returns: the longes common subsequence
    :rtype: str

    >>> lcsseq('cat', 'hat')
    'at'
    >>> lcsseq('Niall', 'Neil')
    'Nil'
    >>> lcsseq('aluminum', 'Catalan')
    'aln'
    >>> lcsseq('ATCG', 'TAGC')
    'AC'
    """
    # pylint: disable=no-member
    lengths = np_zeros((len(src)+1, len(tar)+1), dtype=np_int)
    # pylint: enable=no-member

    # row 0 and column 0 are initialized to 0 already
    for i, src_char in enumerate(src):
        for j, tar_char in enumerate(tar):
            if src_char == tar_char:
                lengths[i+1, j+1] = lengths[i, j] + 1
            else:
                lengths[i+1, j+1] = max(lengths[i+1, j], lengths[i, j+1])

    # read the substring out from the matrix
    result = ''
    i, j = len(src), len(tar)
    while i != 0 and j != 0:
        if lengths[i, j] == lengths[i-1, j]:
            i -= 1
        elif lengths[i, j] == lengths[i, j-1]:
            j -= 1
        else:
            result = src[i-1] + result
            i -= 1
            j -= 1
    return result


def sim_lcsseq(src, tar):
    r"""Return the longest common subsequence similarity of two strings.

    Longest common subsequence similarity (:math:`sim_{LCSseq}`).

    This employs the LCSseq function to derive a similarity metric:
    :math:`sim_{LCSseq}(s,t) = \\frac{|LCSseq(s,t)|}{max(|s|, |t|)}`

    :param str src, tar: two strings to be compared
    :returns: LCSseq similarity
    :rtype: float

    >>> sim_lcsseq('cat', 'hat')
    0.6666666666666666
    >>> sim_lcsseq('Niall', 'Neil')
    0.6
    >>> sim_lcsseq('aluminum', 'Catalan')
    0.375
    >>> sim_lcsseq('ATCG', 'TAGC')
    0.5
    """
    if src == tar:
        return 1.0
    elif not src or not tar:
        return 0.0
    return len(lcsseq(src, tar)) / max(len(src), len(tar))


def dist_lcsseq(src, tar):
    """Return the longest common subsequence distance between two strings.

    Longest common subsequence distance (:math:`dist_{LCSseq}`).

    This employs the LCSseq function to derive a similarity metric:
    :math:`dist_{LCSseq}(s,t) = 1 - sim_{LCSseq}(s,t)`

    :param str src, tar: two strings to be compared
    :returns: LCSseq distance
    :rtype: float

    >>> dist_lcsseq('cat', 'hat')
    0.33333333333333337
    >>> dist_lcsseq('Niall', 'Neil')
    0.4
    >>> dist_lcsseq('aluminum', 'Catalan')
    0.625
    >>> dist_lcsseq('ATCG', 'TAGC')
    0.5
    """
    return 1 - sim_lcsseq(src, tar)


def lcsstr(src, tar):
    """Return the longest common substring of two strings.

    Longest common substring (LCSstr).

    Based on the code from
    https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring#Python
    :cite:`Wikibooks:2018`.
    This is licensed Creative Commons: Attribution-ShareAlike 3.0.

    Modifications include:

        - conversion to a numpy array in place of a list of lists
        - conversion to Python 2/3-safe range from xrange via six

    :param str src, tar: two strings to be compared
    :returns: the longes common substring
    :rtype: float

    >>> lcsstr('cat', 'hat')
    'at'
    >>> lcsstr('Niall', 'Neil')
    'N'
    >>> lcsstr('aluminum', 'Catalan')
    'al'
    >>> lcsstr('ATCG', 'TAGC')
    'A'
    """
    # pylint: disable=no-member
    lengths = np_zeros((len(src)+1, len(tar)+1), dtype=np_int)
    # pylint: enable=no-member
    longest, i_longest = 0, 0
    for i in range(1, len(src)+1):
        for j in range(1, len(tar)+1):
            if src[i-1] == tar[j-1]:
                lengths[i, j] = lengths[i-1, j-1] + 1
                if lengths[i, j] > longest:
                    longest = lengths[i, j]
                    i_longest = i
            else:
                lengths[i, j] = 0
    return src[i_longest - longest:i_longest]


def sim_lcsstr(src, tar):
    r"""Return the longest common substring similarity of two strings.

    Longest common substring similarity (:math:`sim_{LCSstr}`).

    This employs the LCS function to derive a similarity metric:
    :math:`sim_{LCSstr}(s,t) = \\frac{|LCSstr(s,t)|}{max(|s|, |t|)}`

    :param str src, tar: two strings to be compared
    :returns: LCSstr similarity
    :rtype: float

    >>> sim_lcsstr('cat', 'hat')
    0.6666666666666666
    >>> sim_lcsstr('Niall', 'Neil')
    0.2
    >>> sim_lcsstr('aluminum', 'Catalan')
    0.25
    >>> sim_lcsstr('ATCG', 'TAGC')
    0.25
    """
    if src == tar:
        return 1.0
    elif not src or not tar:
        return 0.0
    return len(lcsstr(src, tar)) / max(len(src), len(tar))


def dist_lcsstr(src, tar):
    """Return the longest common substring distance between two strings.

    Longest common substring distance (:math:`dist_{LCSstr}`).

    This employs the LCS function to derive a similarity metric:
    :math:`dist_{LCSstr}(s,t) = 1 - sim_{LCSstr}(s,t)`

    :param str src, tar: two strings to be compared
    :returns: LCSstr distance
    :rtype: float

    >>> dist_lcsstr('cat', 'hat')
    0.33333333333333337
    >>> dist_lcsstr('Niall', 'Neil')
    0.8
    >>> dist_lcsstr('aluminum', 'Catalan')
    0.75
    >>> dist_lcsstr('ATCG', 'TAGC')
    0.75
    """
    return 1 - sim_lcsstr(src, tar)


def sim_ratcliff_obershelp(src, tar):
    """Return the Ratcliff-Obershelp similarity of two strings.

    This follows the Ratcliff-Obershelp algorithm :cite:`Ratcliff:1988` to
    derive a similarity measure:

        1. Find the length of the longest common substring in src & tar.
        2. Recurse on the strings to the left & right of each this substring
           in src & tar. The base case is a 0 length common substring, in which
           case, return 0. Otherwise, return the sum of the current longest
           common substring and the left & right recursed sums.
        3. Multiply this length by 2 and divide by the sum of the lengths of
           src & tar.

    Cf.
    http://www.drdobbs.com/database/pattern-matching-the-gestalt-approach/184407970

    :param str src, tar: two strings to be compared
    :returns: Ratcliff-Obserhelp similarity
    :rtype: float

    >>> round(sim_ratcliff_obershelp('cat', 'hat'), 12)
    0.666666666667
    >>> round(sim_ratcliff_obershelp('Niall', 'Neil'), 12)
    0.666666666667
    >>> round(sim_ratcliff_obershelp('aluminum', 'Catalan'), 12)
    0.4
    >>> sim_ratcliff_obershelp('ATCG', 'TAGC')
    0.5
    """
    def _lcsstr_stl(src, tar):
        """Return start positions & length for Ratcliff-Obershelp.

        Return the start position in the source string, start position in
        the target string, and length of the longest common substring of
        strings src and tar.
        """
        # pylint: disable=no-member
        lengths = np_zeros((len(src)+1, len(tar)+1), dtype=np_int)
        # pylint: enable=no-member
        longest, src_longest, tar_longest = 0, 0, 0
        for i in range(1, len(src)+1):
            for j in range(1, len(tar)+1):
                if src[i-1] == tar[j-1]:
                    lengths[i, j] = lengths[i-1, j-1] + 1
                    if lengths[i, j] > longest:
                        longest = lengths[i, j]
                        src_longest = i
                        tar_longest = j
                else:
                    lengths[i, j] = 0
        return (src_longest-longest, tar_longest-longest, longest)

    def _sstr_matches(src, tar):
        """Return the sum of substring match lengths.

        This follows the Ratcliff-Obershelp algorithm :cite:`Ratcliff:1988`:
             1. Find the length of the longest common substring in src & tar.
             2. Recurse on the strings to the left & right of each this
                 substring in src & tar.
             3. Base case is a 0 length common substring, in which case,
                 return 0.
             4. Return the sum.
        """
        src_start, tar_start, length = _lcsstr_stl(src, tar)
        if length == 0:
            return 0
        return (_sstr_matches(src[:src_start], tar[:tar_start]) +
                length +
                _sstr_matches(src[src_start+length:], tar[tar_start+length:]))

    if src == tar:
        return 1.0
    elif not src or not tar:
        return 0.0
    return 2*_sstr_matches(src, tar)/(len(src)+len(tar))


def dist_ratcliff_obershelp(src, tar):
    """Return the Ratcliff-Obershelp distance between two strings.

    Ratcliff-Obsershelp distance the complement of Ratcliff-Obershelp
    similarity:
    :math:`dist_{Ratcliff-Obershelp} = 1 - sim_{Ratcliff-Obershelp}`.

    :param str src, tar: two strings to be compared
    :returns: Ratcliffe-Obershelp distance
    :rtype: float

    >>> round(dist_ratcliff_obershelp('cat', 'hat'), 12)
    0.333333333333
    >>> round(dist_ratcliff_obershelp('Niall', 'Neil'), 12)
    0.333333333333
    >>> round(dist_ratcliff_obershelp('aluminum', 'Catalan'), 12)
    0.6
    >>> dist_ratcliff_obershelp('ATCG', 'TAGC')
    0.5
    """
    return 1 - sim_ratcliff_obershelp(src, tar)


def mra_compare(src, tar):
    """Return the MRA comparison rating of two strings.

    The Western Airlines Surname Match Rating Algorithm comparison rating, as
    presented on page 18 of :cite:`Moore:1977`.

    :param str src, tar: two strings to be compared
    :returns: MRA comparison rating
    :rtype: int

    >>> mra_compare('cat', 'hat')
    5
    >>> mra_compare('Niall', 'Neil')
    6
    >>> mra_compare('aluminum', 'Catalan')
    0
    >>> mra_compare('ATCG', 'TAGC')
    5
    """
    if src == tar:
        return 6
    if src == '' or tar == '':
        return 0
    src = list(mra(src))
    tar = list(mra(tar))

    if abs(len(src)-len(tar)) > 2:
        return 0

    length_sum = len(src) + len(tar)
    if length_sum < 5:
        min_rating = 5
    elif length_sum < 8:
        min_rating = 4
    elif length_sum < 12:
        min_rating = 3
    else:
        min_rating = 2

    for _ in range(2):
        new_src = []
        new_tar = []
        minlen = min(len(src), len(tar))
        for i in range(minlen):
            if src[i] != tar[i]:
                new_src.append(src[i])
                new_tar.append(tar[i])
        src = new_src+src[minlen:]
        tar = new_tar+tar[minlen:]
        src.reverse()
        tar.reverse()

    similarity = 6 - max(len(src), len(tar))

    if similarity >= min_rating:
        return similarity
    return 0


def sim_mra(src, tar):
    """Return the normalized MRA similarity of two strings.

    This is the MRA normalized to :math:`[0, 1]`, given that MRA itself is
    constrained to the range :math:`[0, 6]`.

    :param str src, tar: two strings to be compared
    :returns: normalized MRA similarity
    :rtype: float

    >>> sim_mra('cat', 'hat')
    0.8333333333333334
    >>> sim_mra('Niall', 'Neil')
    1.0
    >>> sim_mra('aluminum', 'Catalan')
    0.0
    >>> sim_mra('ATCG', 'TAGC')
    0.8333333333333334
    """
    return mra_compare(src, tar)/6


def dist_mra(src, tar):
    """Return the normalized MRA distance between two strings.

    MRA distance is the complement of MRA similarity:
    :math:`dist_{MRA} = 1 - sim_{MRA}`.

    :param str src, tar: two strings to be compared
    :returns: normalized MRA distance
    :rtype: float

    >>> dist_mra('cat', 'hat')
    0.16666666666666663
    >>> dist_mra('Niall', 'Neil')
    0.0
    >>> dist_mra('aluminum', 'Catalan')
    1.0
    >>> dist_mra('ATCG', 'TAGC')
    0.16666666666666663
    """
    return 1 - sim_mra(src, tar)


def dist_compression(src, tar, compressor='bz2', probs=None):
    """Return the normalized compression distance between two strings.

    Normalized compression distance (NCD) :cite:`Cilibrasi:2005`.

    :param str src, tar: two strings to be compared
    :param str compressor: a compression scheme to use for the similarity
        calculation, from the following:

            - `zlib` -- standard zlib/gzip
            - `bz2` -- bzip2 (default)
            - `lzma` -- Lempel–Ziv–Markov chain algorithm
            - `arith` -- arithmetic coding
            - `rle` -- run-length encoding
            - `bwtrle` -- Burrows-Wheeler transform followed by run-length
              encoding

    :param doct probs: a dictionary trained with ac_train (for the arith
        compressor only)
    :returns: compression distance
    :rtype: float

    >>> dist_compression('cat', 'hat')
    0.08
    >>> dist_compression('Niall', 'Neil')
    0.037037037037037035
    >>> dist_compression('aluminum', 'Catalan')
    0.20689655172413793
    >>> dist_compression('ATCG', 'TAGC')
    0.037037037037037035

    >>> dist_compression('Niall', 'Neil', compressor='zlib')
    0.45454545454545453
    >>> dist_compression('Niall', 'Neil', compressor='bz2')
    0.037037037037037035
    >>> dist_compression('Niall', 'Neil', compressor='lzma')
    0.16
    >>> dist_compression('Niall', 'Neil', compressor='arith')
    0.6875
    >>> dist_compression('Niall', 'Neil', compressor='rle')
    1.0
    >>> dist_compression('Niall', 'Neil', compressor='bwtrle')
    0.8333333333333334
    """
    if src == tar:
        return 0.0

    if compressor not in {'arith', 'rle', 'bwtrle'}:
        src = src.encode('utf-8')
        tar = tar.encode('utf-8')

    if compressor == 'bz2':
        src_comp = encode(src, 'bz2_codec')[15:]
        tar_comp = encode(tar, 'bz2_codec')[15:]
        concat_comp = encode(src+tar, 'bz2_codec')[15:]
        concat_comp2 = encode(tar+src, 'bz2_codec')[15:]
    elif compressor == 'lzma':
        if 'lzma' in modules:
            src_comp = lzma.compress(src)[14:]
            tar_comp = lzma.compress(tar)[14:]
            concat_comp = lzma.compress(src+tar)[14:]
            concat_comp2 = lzma.compress(tar+src)[14:]
        else:  # pragma: no cover
            raise ValueError('Install the PylibLZMA module in order to use ' +
                             'lzma compression similarity')
    elif compressor == 'arith':
        if probs is None:
            # lacking a reasonable dictionary, train on the strings themselves
            probs = ac_train(src+tar)
        src_comp = ac_encode(src, probs)[1]
        tar_comp = ac_encode(tar, probs)[1]
        concat_comp = ac_encode(src+tar, probs)[1]
        concat_comp2 = ac_encode(tar+src, probs)[1]
        return ((min(concat_comp, concat_comp2) - min(src_comp, tar_comp)) /
                max(src_comp, tar_comp))
    elif compressor in {'rle', 'bwtrle'}:
        src_comp = rle_encode(src, (compressor == 'bwtrle'))
        tar_comp = rle_encode(tar, (compressor == 'bwtrle'))
        concat_comp = rle_encode(src+tar, (compressor == 'bwtrle'))
        concat_comp2 = rle_encode(tar+src, (compressor == 'bwtrle'))
    else:  # zlib
        src_comp = encode(src, 'zlib_codec')[2:]
        tar_comp = encode(tar, 'zlib_codec')[2:]
        concat_comp = encode(src+tar, 'zlib_codec')[2:]
        concat_comp2 = encode(tar+src, 'zlib_codec')[2:]
    return ((min(len(concat_comp), len(concat_comp2)) -
             min(len(src_comp), len(tar_comp))) /
            max(len(src_comp), len(tar_comp)))


def sim_compression(src, tar, compressor='bz2', probs=None):
    """Return the normalized compression similarity of two strings.

    Normalized compression similarity is the complement of normalized
    compression distance:
    :math:`sim_{NCS} = 1 - dist_{NCD}`.

    :param str src, tar: two strings to be compared
    :param str compressor: a compression scheme to use for the similarity
        calculation:

            - `zlib` -- standard zlib/gzip
            - `bz2` -- bzip2 (default)
            - `lzma` -- Lempel–Ziv–Markov chain algorithm
            - `arith` -- arithmetic coding
            - `rle` -- run-length encoding
            - `bwtrle` -- Burrows-Wheeler transform followed by run-length
              encoding

    :param dict probs: a dictionary trained with ac_train (for the arith
        compressor only)
    :returns: compression similarity
    :rtype: float

    >>> sim_compression('cat', 'hat')
    0.92
    >>> sim_compression('Niall', 'Neil')
    0.962962962962963
    >>> sim_compression('aluminum', 'Catalan')
    0.7931034482758621
    >>> sim_compression('ATCG', 'TAGC')
    0.962962962962963

    >>> sim_compression('Niall', 'Neil', compressor='zlib')
    0.5454545454545454
    >>> sim_compression('Niall', 'Neil', compressor='bz2')
    0.962962962962963
    >>> sim_compression('Niall', 'Neil', compressor='lzma')
    0.84
    >>> sim_compression('Niall', 'Neil', compressor='arith')
    0.3125
    >>> sim_compression('Niall', 'Neil', compressor='rle')
    0.0
    >>> sim_compression('Niall', 'Neil', compressor='bwtrle')
    0.16666666666666663
    """
    return 1 - dist_compression(src, tar, compressor, probs)


def sim_monge_elkan(src, tar, sim_func=sim_levenshtein, symmetric=False):
    """Return the Monge-Elkan similarity of two strings.

    Monge-Elkan is defined in :cite:`Monge:1996`.

    Note: Monge-Elkan is NOT a symmetric similarity algoritm. Thus, the
    similarity of src to tar is not necessarily equal to the similarity of
    tar to src. If the sym argument is True, a symmetric value is calculated,
    at the cost of doubling the computation time (since the
    :math:`sim_{Monge-Elkan}(src, tar)` and
    :math:`sim_{Monge-Elkan}(tar, src)` are both calculated and then averaged).

    :param str src, tar: two strings to be compared
    :param function sim_func: the internal similarity metric to emply
    :param bool symmetric: return a symmetric similarity measure
    :returns: Monge-Elkan similarity
    :rtype: float

    >>> sim_monge_elkan('cat', 'hat')
    0.75
    >>> round(sim_monge_elkan('Niall', 'Neil'), 12)
    0.666666666667
    >>> round(sim_monge_elkan('aluminum', 'Catalan'), 12)
    0.388888888889
    >>> sim_monge_elkan('ATCG', 'TAGC')
    0.5
    """
    if src == tar:
        return 1.0

    q_src = sorted(QGrams(src).elements())
    q_tar = sorted(QGrams(tar).elements())

    if not q_src or not q_tar:
        return 0.0

    sum_of_maxes = 0
    for q_s in q_src:
        max_sim = float('-inf')
        for q_t in q_tar:
            max_sim = max(max_sim, sim_func(q_s, q_t))
        sum_of_maxes += max_sim
    sim_em = sum_of_maxes / len(q_src)

    if symmetric:
        sim_em = (sim_em + sim_monge_elkan(tar, src, sim, False))/2

    return sim_em


def dist_monge_elkan(src, tar, sim_func=sim_levenshtein, symmetric=False):
    """Return the Monge-Elkan distance between two strings.

    Monge-Elkan distance is the complement of Monge-Elkan similarity:
    :math:`dist_{Monge-Elkan} = 1 - sim_{Monge-Elkan}`.

    :param str src, tar: two strings to be compared
    :param function sim_func: the internal similarity metric to emply
    :param bool symmetric: return a symmetric similarity measure
    :returns: Monge-Elkan distance
    :rtype: float

    >>> dist_monge_elkan('cat', 'hat')
    0.25
    >>> round(dist_monge_elkan('Niall', 'Neil'), 12)
    0.333333333333
    >>> round(dist_monge_elkan('aluminum', 'Catalan'), 12)
    0.611111111111
    >>> dist_monge_elkan('ATCG', 'TAGC')
    0.5
    """
    return 1 - sim_monge_elkan(src, tar, sim_func, symmetric)


def sim_ident(src, tar):
    """Return the identity similarity of two strings.

    Identity similarity is 1 if the two strings are identical, otherwise 0.

    :param str src, tar: two strings to be compared
    :returns: identity similarity
    :rtype: int

    >>> sim_ident('cat', 'hat')
    0
    >>> sim_ident('cat', 'cat')
    1
    """
    return int(src == tar)


def dist_ident(src, tar):
    """Return the identity distance between two strings.

    This is 0 if the two strings are identical, otherwise 1, i.e.
    :math:`dist_{identity} = 1 - sim_{identity}`.

    :param str src, tar: two strings to be compared
    :returns: indentity distance
    :rtype: int

    >>> dist_ident('cat', 'hat')
    1
    >>> dist_ident('cat', 'cat')
    0
    """
    return 1 - sim_ident(src, tar)


def sim_matrix(src, tar, mat=None, mismatch_cost=0, match_cost=1,
               symmetric=True, alphabet=None):
    """Return the matrix similarity of two strings.

    With the default parameters, this is identical to sim_ident.
    It is possible for sim_matrix to return values outside of the range
    :math:`[0, 1]`, if values outside that range are present in mat,
    mismatch_cost, or match_cost.

    :param str src, tar: two strings to be compared
    :param dict mat: a dict mapping tuples to costs; the tuples are (src, tar)
        pairs of symbols from the alphabet parameter
    :param float mismatch_cost: the value returned if (src, tar) is absent from
        mat when src does not equal tar
    :param float match_cost: the value returned if (src, tar) is absent from
        mat when src equals tar
    :param bool symmetric: True if the cost of src not matching tar is
        identical to the cost of tar not matching src; in this case, the values
        in mat need only contain (src, tar) or (tar, src), not both
    :param str alphabet: a collection of tokens from which src and tar are
        drawn; if this is defined a ValueError is raised if either tar or src
        is not found in alphabet
    :returns: matrix similarity
    :rtype: float

    >>> sim_matrix('cat', 'hat')
    0
    >>> sim_matrix('hat', 'hat')
    1
    """
    if alphabet:
        alphabet = tuple(alphabet)
        for i in src:
            if i not in alphabet:
                raise ValueError('src value not in alphabet')
        for i in tar:
            if i not in alphabet:
                raise ValueError('tar value not in alphabet')

    if src == tar:
        if mat and (src, src) in mat:
            return mat[(src, src)]
        return match_cost
    if mat and (src, tar) in mat:
        return mat[(src, tar)]
    elif symmetric and mat and (tar, src) in mat:
        return mat[(tar, src)]
    return mismatch_cost


def needleman_wunsch(src, tar, gap_cost=1, sim_func=sim_ident):

    """Return the Needleman-Wunsch score of two strings.

    The Needleman-Wunsch score :cite:`Needleman:1970` is a standard edit
    distance measure.

    :param str src, tar: two strings to be compared
    :param float gap_cost: the cost of an alignment gap (1 by default)
    :param function sim_func: a function that returns the similarity of two
        characters (identity similarity by default)
    :returns: Needleman-Wunsch score
    :rtype: int (in fact dependent on the gap_cost & return value of sim_func)

    >>> needleman_wunsch('cat', 'hat')
    2.0
    >>> needleman_wunsch('Niall', 'Neil')
    1.0
    >>> needleman_wunsch('aluminum', 'Catalan')
    -1.0
    >>> needleman_wunsch('ATCG', 'TAGC')
    0.0
    """
    # pylint: disable=no-member
    d_mat = np_zeros((len(src)+1, len(tar)+1), dtype=np_float32)
    # pylint: enable=no-member

    for i in range(len(src)+1):
        d_mat[i, 0] = -(i * gap_cost)
    for j in range(len(tar)+1):
        d_mat[0, j] = -(j * gap_cost)
    for i in range(1, len(src)+1):
        for j in range(1, len(tar)+1):
            match = d_mat[i-1, j-1] + sim_func(src[i-1], tar[j-1])
            delete = d_mat[i-1, j] - gap_cost
            insert = d_mat[i, j-1] - gap_cost
            d_mat[i, j] = max(match, delete, insert)
    return d_mat[d_mat.shape[0]-1, d_mat.shape[1]-1]


def smith_waterman(src, tar, gap_cost=1, sim_func=sim_ident):

    """Return the Smith-Waterman score of two strings.

    The Smith-Waterman score :cite:`Smith:1981` is a standard edit distance
    measure, differing from Needleman-Wunsch in that it focuses on local
    alignment and disallows negative scores.

    :param str src, tar: two strings to be compared
    :param float gap_cost: the cost of an alignment gap (1 by default)
    :param function sim_func: a function that returns the similarity of two
        characters (identity similarity by default)
    :returns: Smith-Waterman score
    :rtype: int (in fact dependent on the gap_cost & return value of sim_func)

    >>> smith_waterman('cat', 'hat')
    2.0
    >>> smith_waterman('Niall', 'Neil')
    1.0
    >>> smith_waterman('aluminum', 'Catalan')
    0.0
    >>> smith_waterman('ATCG', 'TAGC')
    1.0
    """
    # pylint: disable=no-member
    d_mat = np_zeros((len(src)+1, len(tar)+1), dtype=np_float32)
    # pylint: enable=no-member

    for i in range(len(src)+1):
        d_mat[i, 0] = 0
    for j in range(len(tar)+1):
        d_mat[0, j] = 0
    for i in range(1, len(src)+1):
        for j in range(1, len(tar)+1):
            match = d_mat[i-1, j-1] + sim_func(src[i-1], tar[j-1])
            delete = d_mat[i-1, j] - gap_cost
            insert = d_mat[i, j-1] - gap_cost
            d_mat[i, j] = max(0, match, delete, insert)
    return d_mat[d_mat.shape[0]-1, d_mat.shape[1]-1]


def gotoh(src, tar, gap_open=1, gap_ext=0.4, sim_func=sim_ident):
    """Return the Gotoh score of two strings.

    The Gotoh score :cite:`Gotoh:1982` is essentially Needleman-Wunsch with
    affine gap penalties.

    :param str src, tar: two strings to be compared
    :param float gap_open: the cost of an open alignment gap (1 by default)
    :param float gap_ext: the cost of an alignment gap extension (0.4 by
        default)
    :param function sim_func: a function that returns the similarity of two
        characters (identity similarity by default)
    :returns: Gotoh score
    :rtype: float (in fact dependent on the gap_cost & return value of
        sim_func)

    >>> gotoh('cat', 'hat')
    2.0
    >>> gotoh('Niall', 'Neil')
    1.0
    >>> round(gotoh('aluminum', 'Catalan'), 12)
    -0.4
    >>> gotoh('cat', 'hat')
    2.0
    """
    # pylint: disable=no-member
    d_mat = np_zeros((len(src)+1, len(tar)+1), dtype=np_float32)
    p_mat = np_zeros((len(src)+1, len(tar)+1), dtype=np_float32)
    q_mat = np_zeros((len(src)+1, len(tar)+1), dtype=np_float32)
    # pylint: enable=no-member

    d_mat[0, 0] = 0
    p_mat[0, 0] = float('-inf')
    q_mat[0, 0] = float('-inf')
    for i in range(1, len(src)+1):
        d_mat[i, 0] = float('-inf')
        p_mat[i, 0] = -gap_open - gap_ext*(i-1)
        q_mat[i, 0] = float('-inf')
        q_mat[i, 1] = -gap_open
    for j in range(1, len(tar)+1):
        d_mat[0, j] = float('-inf')
        p_mat[0, j] = float('-inf')
        p_mat[1, j] = -gap_open
        q_mat[0, j] = -gap_open - gap_ext*(j-1)

    for i in range(1, len(src)+1):
        for j in range(1, len(tar)+1):
            sim_val = sim_func(src[i-1], tar[j-1])
            d_mat[i, j] = max(d_mat[i-1, j-1] + sim_val,
                              p_mat[i-1, j-1] + sim_val,
                              q_mat[i-1, j-1] + sim_val)

            p_mat[i, j] = max(d_mat[i-1, j] - gap_open,
                              p_mat[i-1, j] - gap_ext)

            q_mat[i, j] = max(d_mat[i, j-1] - gap_open,
                              q_mat[i, j-1] - gap_ext)

    i, j = (n - 1 for n in d_mat.shape)

    return max(d_mat[i, j], p_mat[i, j], q_mat[i, j])


def sim_length(src, tar):
    """Return the length similarty of two strings.

    Length similarity is the ratio of the length of the shorter string to the
    longer.

    :param str src, tar: two strings to be compared
    :returns: length similarity
    :rtype: float

    >>> sim_length('cat', 'hat')
    1.0
    >>> sim_length('Niall', 'Neil')
    0.8
    >>> sim_length('aluminum', 'Catalan')
    0.875
    >>> sim_length('ATCG', 'TAGC')
    1.0
    """
    if src == tar:
        return 1.0
    if not src or not tar:
        return 0.0
    return len(src)/len(tar) if len(src) < len(tar) else len(tar)/len(src)


def dist_length(src, tar):
    """Return the length distance between two strings.

    Length distance is the complement of length similarity:
    :math:`dist_{length} = 1 - sim_{length}`.

    :param str src, tar: two strings to be compared
    :returns: length distance
    :rtype: float

    >>> dist_length('cat', 'hat')
    0.0
    >>> dist_length('Niall', 'Neil')
    0.19999999999999996
    >>> dist_length('aluminum', 'Catalan')
    0.125
    >>> dist_length('ATCG', 'TAGC')
    0.0
    """
    return 1 - sim_length(src, tar)


def sim_prefix(src, tar):

    """Return the prefix similarty of two strings.

    Prefix similarity is the ratio of the length of the shorter term that
    exactly matches the longer term to the length of the shorter term,
    beginning at the start of both terms.

    :param str src, tar: two strings to be compared
    :returns: prefix similarity
    :rtype: float

    >>> sim_prefix('cat', 'hat')
    0.0
    >>> sim_prefix('Niall', 'Neil')
    0.25
    >>> sim_prefix('aluminum', 'Catalan')
    0.0
    >>> sim_prefix('ATCG', 'TAGC')
    0.0
    """
    if src == tar:
        return 1.0
    if not src or not tar:
        return 0.0
    min_word, max_word = (src, tar) if len(src) < len(tar) else (tar, src)
    min_len = len(min_word)
    for i in range(min_len, 0, -1):
        if min_word[:i] == max_word[:i]:
            return i/min_len
    return 0.0


def dist_prefix(src, tar):
    """Return the prefix distance between two strings.

    Prefix distance is the complement of prefix similarity:
    :math:`dist_{prefix} = 1 - sim_{prefix}`.

    :param str src, tar: two strings to be compared
    :returns: prefix distance
    :rtype: float

    >>> dist_prefix('cat', 'hat')
    1.0
    >>> dist_prefix('Niall', 'Neil')
    0.75
    >>> dist_prefix('aluminum', 'Catalan')
    1.0
    >>> dist_prefix('ATCG', 'TAGC')
    1.0
    """
    return 1 - sim_prefix(src, tar)


def sim_suffix(src, tar):

    """Return the suffix similarity of two strings.

    Suffix similarity is the ratio of the length of the shorter term that
    exactly matches the longer term to the length of the shorter term,
    beginning at the end of both terms.

    :param str src, tar: two strings to be compared
    :returns: suffix similarity
    :rtype: float

    >>> sim_suffix('cat', 'hat')
    0.6666666666666666
    >>> sim_suffix('Niall', 'Neil')
    0.25
    >>> sim_suffix('aluminum', 'Catalan')
    0.0
    >>> sim_suffix('ATCG', 'TAGC')
    0.0
    """
    if src == tar:
        return 1.0
    if not src or not tar:
        return 0.0
    min_word, max_word = (src, tar) if len(src) < len(tar) else (tar, src)
    min_len = len(min_word)
    for i in range(min_len, 0, -1):
        if min_word[-i:] == max_word[-i:]:
            return i/min_len
    return 0.0


def dist_suffix(src, tar):
    """Return the suffix distance between two strings.

    Suffix distance is the complement of suffix similarity:
    :math:`dist_{suffix} = 1 - sim_{suffix}`.

    :param str src, tar: two strings to be compared
    :returns: suffix distance
    :rtype: float

    >>> dist_suffix('cat', 'hat')
    0.33333333333333337
    >>> dist_suffix('Niall', 'Neil')
    0.75
    >>> dist_suffix('aluminum', 'Catalan')
    1.0
    >>> dist_suffix('ATCG', 'TAGC')
    1.0
    """
    return 1 - sim_suffix(src, tar)


def sim_mlipns(src, tar, threshold=0.25, maxmismatches=2):
    """Return the MLIPNS similarity of two strings.

    Modified Language-Independent Product Name Search (MLIPNS) is described in
    :cite:`Shannaq:2010`. This function returns only 1.0 (similar) or 0.0
    (not similar). LIPNS similarity is identical to normalized Hamming
    similarity.

    :param str src, tar: two strings to be compared
    :param float threshold: a number [0, 1] indicating the maximum similarity
        score, below which the strings are considered 'similar' (0.25 by
        default)
    :param int maxmismatches: a number indicating the allowable number of
        mismatches to remove before declaring two strings not similar (2 by
        default)
    :returns: MLIPNS similarity
    :rtype: float

    >>> sim_mlipns('cat', 'hat')
    1.0
    >>> sim_mlipns('Niall', 'Neil')
    0.0
    >>> sim_mlipns('aluminum', 'Catalan')
    0.0
    >>> sim_mlipns('ATCG', 'TAGC')
    0.0
    """
    if tar == src:
        return 1.0
    if not src or not tar:
        return 0.0

    mismatches = 0
    ham = hamming(src, tar, difflens=True)
    maxlen = max(len(src), len(tar))
    while src and tar and mismatches <= maxmismatches:
        if maxlen < 1 or (1-(maxlen-ham)/maxlen) <= threshold:
            return 1.0
        else:
            mismatches += 1
            ham -= 1
            maxlen -= 1

    if maxlen < 1:
        return 1.0
    return 0.0


def dist_mlipns(src, tar, threshold=0.25, maxmismatches=2):
    """Return the MLIPNS distance between two strings.

    MLIPNS distance is the complement of MLIPNS similarity:
    :math:`dist_{MLIPNS} = 1 - sim_{MLIPNS}`. This function returns only 0.0
    (distant) or 1.0 (not distant).

    :param str src, tar: two strings to be compared
    :param float threshold: a number [0, 1] indicating the maximum similarity
        score, below which the strings are considered 'similar' (0.25 by
        default)
    :param int maxmismatches: a number indicating the allowable number of
        mismatches to remove before declaring two strings not similar (2 by
        default)
    :returns: MLIPNS distance
    :rtype: float

    >>> dist_mlipns('cat', 'hat')
    0.0
    >>> dist_mlipns('Niall', 'Neil')
    1.0
    >>> dist_mlipns('aluminum', 'Catalan')
    1.0
    >>> dist_mlipns('ATCG', 'TAGC')
    1.0
    """
    return 1.0 - sim_mlipns(src, tar, threshold, maxmismatches)


def bag(src, tar):
    """Return the bag distance between two strings.

    Bag distance is proposed in :cite:`Bartolini:2002`. It is defined as:
    :math:`max(|multiset(src)-multiset(tar)|, |multiset(tar)-multiset(src)|)`.

    :param str src, tar: two strings to be compared
    :returns: bag distance
    :rtype: int

    >>> bag('cat', 'hat')
    1
    >>> bag('Niall', 'Neil')
    2
    >>> bag('aluminum', 'Catalan')
    5
    >>> bag('ATCG', 'TAGC')
    0
    >>> bag('abcdefg', 'hijklm')
    7
    >>> bag('abcdefg', 'hijklmno')
    8
    """
    if tar == src:
        return 0
    elif not src:
        return len(tar)
    elif not tar:
        return len(src)

    src_bag = Counter(src)
    tar_bag = Counter(tar)
    return max(sum((src_bag-tar_bag).values()),
               sum((tar_bag-src_bag).values()))


def dist_bag(src, tar):
    """Return the normalized bag distance between two strings.

    Bag distance is normalized by dividing by :math:`max( |src|, |tar| )`.

    :param str src, tar: two strings to be compared
    :returns: normalized bag distance
    :rtype: float

    >>> dist_bag('cat', 'hat')
    0.3333333333333333
    >>> dist_bag('Niall', 'Neil')
    0.4
    >>> dist_bag('aluminum', 'Catalan')
    0.625
    >>> dist_bag('ATCG', 'TAGC')
    0.0
    """
    if tar == src:
        return 0.0
    if not src or not tar:
        return 1.0

    maxlen = max(len(src), len(tar))

    return bag(src, tar)/maxlen


def sim_bag(src, tar):
    """Return the normalized bag similarity of two strings.

    Normalized bag similarity is the complement of normalized bag distance:
    :math:`sim_{bag} = 1 - dist_{bag}`.

    :param str src, tar: two strings to be compared
    :returns: normalized bag similarity
    :rtype: float

    >>> round(sim_bag('cat', 'hat'), 12)
    0.666666666667
    >>> sim_bag('Niall', 'Neil')
    0.6
    >>> sim_bag('aluminum', 'Catalan')
    0.375
    >>> sim_bag('ATCG', 'TAGC')
    1.0
    """
    return 1-dist_bag(src, tar)


def editex(src, tar, cost=(0, 1, 2), local=False):
    """Return the Editex distance between two strings.

    As described on pages 3 & 4 of :cite:`Zobel:1996`.

    The local variant is based on :cite:`Ring:2009`.

    :param str src, tar: two strings to be compared
    :param tuple cost: a 3-tuple representing the cost of the four possible
        edits:
        match, same-group, and mismatch respectively (by default: (0, 1, 2))
    :param bool local: if True, the local variant of Editex is used
    :returns: Editex distance
    :rtype: int

    >>> editex('cat', 'hat')
    2
    >>> editex('Niall', 'Neil')
    2
    >>> editex('aluminum', 'Catalan')
    12
    >>> editex('ATCG', 'TAGC')
    6
    """
    match_cost, group_cost, mismatch_cost = cost
    letter_groups = ({'A', 'E', 'I', 'O', 'U', 'Y'},
                     {'B', 'P'},
                     {'C', 'K', 'Q'},
                     {'D', 'T'},
                     {'L', 'R'},
                     {'M', 'N'},
                     {'G', 'J'},
                     {'F', 'P', 'V'},
                     {'S', 'X', 'Z'},
                     {'C', 'S', 'Z'})
    all_letters = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'I', 'J', 'K', 'L', 'M',
                   'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'X', 'Y', 'Z'}

    def r_cost(ch1, ch2):
        """Return r(a,b) according to Zobel & Dart's definition."""
        if ch1 == ch2:
            return match_cost
        if ch1 in all_letters and ch2 in all_letters:
            for group in letter_groups:
                if ch1 in group and ch2 in group:
                    return group_cost
        return mismatch_cost

    def d_cost(ch1, ch2):
        """Return d(a,b) according to Zobel & Dart's definition."""
        if ch1 != ch2 and (ch1 == 'H' or ch1 == 'W'):
            return group_cost
        return r_cost(ch1, ch2)

    # convert both src & tar to NFKD normalized unicode
    src = normalize('NFKD', text_type(src.upper()))
    tar = normalize('NFKD', text_type(tar.upper()))
    # convert ß to SS (for Python2)
    src = src.replace('ß', 'SS')
    tar = tar.replace('ß', 'SS')

    if src == tar:
        return 0
    if not src:
        return len(tar) * mismatch_cost
    if not tar:
        return len(src) * mismatch_cost

    # pylint: disable=no-member
    d_mat = np_zeros((len(src)+1, len(tar)+1), dtype=np_int)
    # pylint: enable=no-member
    lens = len(src)
    lent = len(tar)
    src = ' '+src
    tar = ' '+tar

    if not local:
        for i in range(1, lens+1):
            d_mat[i, 0] = d_mat[i-1, 0] + d_cost(src[i-1], src[i])
    for j in range(1, lent+1):
        d_mat[0, j] = d_mat[0, j-1] + d_cost(tar[j-1], tar[j])

    for i in range(1, lens+1):
        for j in range(1, lent+1):
            d_mat[i, j] = min(d_mat[i-1, j] + d_cost(src[i-1], src[i]),
                              d_mat[i, j-1] + d_cost(tar[j-1], tar[j]),
                              d_mat[i-1, j-1] + r_cost(src[i], tar[j]))

    return d_mat[lens, lent]


def dist_editex(src, tar, cost=(0, 1, 2), local=False):
    """Return the normalized Editex distance between two strings.

    The Editex distance is normalized by dividing the Editex distance
    (calculated by any of the three supported methods) by the greater of
    the number of characters in src times the cost of a delete and
    the number of characters in tar times the cost of an insert.
    For the case in which all operations have :math:`cost = 1`, this is
    equivalent to the greater of the length of the two strings src & tar.

    :param str src, tar: two strings to be compared
    :param tuple cost: a 3-tuple representing the cost of the four possible
        edits:
        match, same-group, and mismatch respectively (by default: (0, 1, 2))
    :param bool local: if True, the local variant of Editex is used
    :returns: normalized Editex distance
    :rtype: float

    >>> round(dist_editex('cat', 'hat'), 12)
    0.333333333333
    >>> round(dist_editex('Niall', 'Neil'), 12)
    0.2
    >>> dist_editex('aluminum', 'Catalan')
    0.75
    >>> dist_editex('ATCG', 'TAGC')
    0.75
    """
    if src == tar:
        return 0
    mismatch_cost = cost[2]
    return (editex(src, tar, cost, local) /
            (max(len(src)*mismatch_cost, len(tar)*mismatch_cost)))


def sim_editex(src, tar, cost=(0, 1, 2), local=False):
    """Return the normalized Editex similarity of two strings.

    The Editex similarity is the complement of Editex distance:
    :math:`sim_{Editex} = 1 - dist_{Editex}`.

    :param str src, tar: two strings to be compared
    :param tuple cost: a 3-tuple representing the cost of the four possible
        edits:
        match, same-group, and mismatch respectively (by default: (0, 1, 2))
    :param bool local: if True, the local variant of Editex is used
    :returns: normalized Editex similarity
    :rtype: float

    >>> round(sim_editex('cat', 'hat'), 12)
    0.666666666667
    >>> round(sim_editex('Niall', 'Neil'), 12)
    0.8
    >>> sim_editex('aluminum', 'Catalan')
    0.25
    >>> sim_editex('ATCG', 'TAGC')
    0.25
    """
    return 1 - dist_editex(src, tar, cost, local)


def eudex_hamming(src, tar, weights='exponential', maxlength=8,
                  normalized=False):
    """Calculate the Hamming distance between the Eudex hashes of two terms.

    Cf. :cite:`Ticki:2016`.

    - If weights is set to None, a simple Hamming distance is calculated.
    - If weights is set to 'exponential', weight decays by powers of 2, as
      proposed in the eudex specification: https://github.com/ticki/eudex.
    - If weights is set to 'fibonacci', weight decays through the Fibonacci
      series, as in the eudex reference implementation.
    - If weights is set to a callable function, this assumes it creates a
      generator and the generator is used to populate a series of weights.
    - If weights is set to an iterable, the iterable's values should be
      integers and will be used as the weights.

    :param str src, tar: two strings to be compared
    :param iterable or generator function weights:
    :param maxlength: the number of characters to encode as a eudex hash
    :return:
    """
    def _gen_fibonacci():
        """Yield the next Fibonacci number.

        Based on https://www.python-course.eu/generators.php
        Starts at Fibonacci number 3 (the second 1)
        """
        num_a, num_b = 1, 2
        while True:
            yield num_a
            num_a, num_b = num_b, num_a + num_b

    def _gen_exponential(base=2):
        """Yield the next value in an exponential series of the base.

        Starts at base**0
        """
        exp = 0
        while True:
            yield base ** exp
            exp += 1

    # Calculate the eudex hashes and XOR them
    xored = eudex(src, maxlength=maxlength) ^ eudex(tar, maxlength=maxlength)

    # Simple hamming distance (all bits are equal)
    if not weights:
        return bin(xored).count('1')

    # If weights is a function, it should create a generator,
    # which we now use to populate a list
    if callable(weights):
        weights = weights()
    elif weights == 'exponential':
        weights = _gen_exponential()
    elif weights == 'fibonacci':
        weights = _gen_fibonacci()
    if isinstance(weights, GeneratorType):
        weights = [next(weights) for _ in range(maxlength)][::-1]

    # Sum the weighted hamming distance
    dist = 0
    maxdist = 0
    while (xored or normalized) and weights:
        maxdist += 8*weights[-1]
        dist += bin(xored & 0xFF).count('1') * weights.pop()
        xored >>= 8

    if normalized:
        dist /= maxdist

    return dist


def dist_eudex(src, tar, weights='exponential', maxlength=8):
    """Return normalized Hamming distance between Eudex hashes of two terms.

    This is Eudex distance normalized to [0, 1].

    :param str src, tar: two strings to be compared
    :param iterable or generator function weights:
    :param maxlength: the number of characters to encode as a eudex hash
    :return:
    """
    return eudex_hamming(src, tar, weights, maxlength, True)


def sim_eudex(src, tar, weights='exponential', maxlength=8):
    """Return normalized Hamming similarity between Eudex hashes of two terms.

    Normalized Eudex similarity is the complement of normalized Eudex distance:
    :math:`sim_{Eudex} = 1 - dist_{Eudex}`.

    :param str src, tar: two strings to be compared
    :param iterable or generator function weights:
    :param maxlength: the number of characters to encode as a eudex hash
    :return:
    """
    return 1-dist_eudex(src, tar, weights, maxlength)


def sift4_simplest(src, tar, max_offset=0):
    """Return the "simplest" Sift4 distance between two terms.

    This is an approximation of edit distance, described in
    :cite:`Zackwehdex:2014`.

    :param str src, tar: two strings to be compared
    :param max_offset: the number of characters to search for matching letters
    :return:
    """
    if not src:
        return len(tar)

    if not tar:
        return len(src)

    src_len = len(src)
    tar_len = len(tar)

    src_cur = 0
    tar_cur = 0
    lcss = 0
    local_cs = 0

    while (src_cur < src_len) and (tar_cur < tar_len):
        if src[src_cur] == tar[tar_cur]:
            local_cs += 1
        else:
            lcss += local_cs
            local_cs = 0
            if src_cur != tar_cur:
                src_cur = tar_cur = max(src_cur, tar_cur)
            for i in range(max_offset):
                if not ((src_cur+i < src_len) or (tar_cur+i < tar_len)):
                    break
                if (src_cur+i < src_len) and (src[src_cur+i] == tar[tar_cur]):
                    src_cur += i
                    local_cs += 1
                    break
                if (tar_cur+i < tar_len) and (src[src_cur] == tar[tar_cur+i]):
                    tar_cur += i
                    local_cs += 1
                    break

        src_cur += 1
        tar_cur += 1

    lcss += local_cs
    return round(max(src_len, tar_len) - lcss)


def sift4_common(src, tar, max_offset=0, max_distance=0):
    """Return the "common" Sift4 distance between two terms.

    This is an approximation of edit distance, described in
    :cite:`Zackwehdex:2014`.

    :param str src, tar: two strings to be compared
    :param max_offset: the number of characters to search for matching letters
    :param max_distance: the distance at which to stop and exit
    :return:
    """
    if not src:
        return len(tar)

    if not tar:
        return len(src)

    src_len = len(src)
    tar_len = len(tar)

    src_cur = 0
    tar_cur = 0
    lcss = 0
    local_cs = 0
    trans = 0
    offset_arr = []

    while (src_cur < src_len) and (tar_cur < tar_len):
        if src[src_cur] == tar[tar_cur]:
            local_cs += 1
            is_trans = False
            i = 0
            while i < len(offset_arr):
                ofs = offset_arr[i]
                if src_cur <= ofs['src_cur'] or tar_cur <= ofs['tar_cur']:
                    is_trans = (abs(tar_cur-src_cur) >=
                                abs(ofs['tar_cur']-ofs['src_cur']))
                    if is_trans:
                        trans += 1
                    elif not ofs['trans']:
                        ofs['trans'] = True
                        trans += 1
                    break
                elif src_cur > ofs['tar_cur'] and tar_cur > ofs['src_cur']:
                    del offset_arr[i]
                else:
                    i += 1

            offset_arr.append({'src_cur': src_cur, 'tar_cur': tar_cur,
                               'trans': is_trans})
        else:
            lcss += local_cs
            local_cs = 0
            if src_cur != tar_cur:
                src_cur = tar_cur = min(src_cur, tar_cur)
            for i in range(max_offset):
                if not ((src_cur+i < src_len) or (tar_cur+i < tar_len)):
                    break
                if (src_cur+i < src_len) and (src[src_cur+i] == tar[tar_cur]):
                    src_cur += i-1
                    tar_cur -= 1
                    break
                if (tar_cur+i < tar_len) and (src[src_cur] == tar[tar_cur+i]):
                    src_cur -= 1
                    tar_cur += i-1
                    break

        src_cur += 1
        tar_cur += 1

        if max_distance:
            temporary_distance = max(src_cur, tar_cur) - lcss + trans
            if temporary_distance >= max_distance:
                return round(temporary_distance)

        if (src_cur >= src_len) or (tar_cur >= tar_len):
            lcss += local_cs
            local_cs = 0
            src_cur = tar_cur = min(src_cur, tar_cur)

    lcss += local_cs
    return round(max(src_len, tar_len) - lcss + trans)


def dist_sift4(src, tar, max_offset=0, max_distance=0):
    """Return the normalized "common" Sift4 distance between two terms.

    This is Sift4 distance, normalized to [0, 1].

    :param str src, tar: two strings to be compared
    :param max_offset: the number of characters to search for matching letters
    :param max_distance: the distance at which to stop and exit
    :return:
    """
    return (sift4_common(src, tar, max_offset, max_distance) /
            (max(len(src), len(tar))))


def sim_sift4(src, tar, max_offset=0, max_distance=0):
    """Return the normalized "common" Sift4 similarity of two terms.

    Normalized Sift4 similarity is the complement of normalized Sift4 distance:
    :math:`sim_{Sift4} = 1 - dist_{Sift4}`.

    :param str src, tar: two strings to be compared
    :param max_offset: the number of characters to search for matching letters
    :param max_distance: the distance at which to stop and exit
    :return:
    """
    return 1-dist_sift4(src, tar, max_offset, max_distance)


def sim_baystat(src, tar, min_ss_len=None, left_ext=None, right_ext=None):
    """Return the Baystat similarity.

    Good results for shorter words are reported when setting min_ss_len to 1
    and either left_ext OR right_ext to 1.

    The Baystat similarity is defined in :cite:`Furnohr:2002`.

    This is ostensibly a port of the R module PPRL's implementation:
    https://github.com/cran/PPRL/blob/master/src/MTB_Baystat.cpp
    :cite:`Rukasz:2018`. As such, this could be made more pythonic.

    :param str src, tar: two strings to be compared
    :param int min_ss_len: minimum substring length to be considered
    :param int left_ext: left-side extension length
    :param int right_ext: right-side extension length
    :rtype: float
    :return: the Baystat similarity
    """
    if src == tar:
        return 1
    if not src or not tar:
        return 0

    max_len = max(len(src), len(tar))

    if not (min_ss_len and left_ext and right_ext):
        # These can be set via arguments to the function. Otherwise they are
        # set automatically based on values from the article.
        if max_len >= 7:
            min_ss_len = 2
            left_ext = 2
            right_ext = 2
        else:
            # The paper suggests that for short names, (exclusively) one or the
            # other of left_ext and right_ext can be 1, with good results.
            # I use 0 & 0 as the default in this case.
            min_ss_len = 1
            left_ext = 0
            right_ext = 0

    pos = 0
    match_len = 0

    while (True):
        if pos + min_ss_len > len(src):
            return match_len/max_len

        hit_len = 0
        ix = 1

        substring = src[pos:pos + min_ss_len]
        search_begin = pos - left_ext

        if search_begin < 0:
            search_begin = 0
            left_ext_len = pos
        else:
            left_ext_len = left_ext

        if pos + min_ss_len + right_ext >= len(tar):
            right_ext_len = len(tar) - pos - min_ss_len
        else:
            right_ext_len = right_ext

        if (search_begin + left_ext_len + min_ss_len + right_ext_len >
                search_begin):
            search_val = tar[search_begin:(search_begin + left_ext_len +
                                           min_ss_len + right_ext_len)]
        else:
            search_val = ''

        flagged_tar = ''
        while substring in search_val and pos + ix <= len(src):
            hit_len = len(substring)
            flagged_tar = tar.replace(substring, '#'*hit_len)

            if pos + min_ss_len + ix <= len(src):
                substring = src[pos:pos + min_ss_len + ix]

            if pos+min_ss_len + right_ext_len + 1 <= len(tar):
                right_ext_len += 1

            if (search_begin + left_ext_len + min_ss_len + right_ext_len <=
                    len(tar)):
                search_val = tar[search_begin:(search_begin + left_ext_len +
                                               min_ss_len + right_ext_len)]

            ix += 1

        if hit_len > 0:
            tar = flagged_tar

        match_len += hit_len
        pos += ix


def dist_baystat(src, tar, min_ss_len=None, left_ext=None, right_ext=None):
    """Return the Baystat distance.

    Normalized Baystat similarity is the complement of normalized Baystat
    distance: :math:`sim_{Baystat} = 1 - dist_{Baystat}`.

    :param str src, tar: two strings to be compared
    :param int min_ss_len: minimum substring length to be considered
    :param int left_ext: left-side extension length
    :param int right_ext: right-side extension length
    :rtype: float
    :return: the Baystat distance
    """
    return 1-sim_baystat(src, tar, min_ss_len, left_ext, right_ext)


def typo(src, tar, metric='euclidean', cost=(1, 1, 0.5, 0.5)):
    """Return the typo distance between two strings.

    This is inspired by Typo-Distance :cite:`Song:2011`, and a fair bit of
    this was copied from that module. Compared to the original, this supports
    different metrics for substitution.

    :param str src, tar: two strings to be compared
    :param str metric: supported values include: 'euclidean', 'manhattan',
          'log-euclidean', and 'log-manhattan'
    :param tuple cost: a 4-tuple representing the cost of the four possible
        edits: inserts, deletes, substitutions, and shift, respectively (by
        default: (1, 1, 0.5, 0.5)) The substitution & shift costs should be
        significantly less than the cost of an insertion & deletion unless
        a log metric is used.
    :return: typo distance
    :rtype: float
    """
    ins_cost, del_cost, sub_cost, shift_cost = cost

    if src == tar:
        return 0.0
    if not src:
        return len(tar) * ins_cost
    if not tar:
        return len(src) * del_cost

    layout = {'QWERTY': (
        (('`', '1', '2', '3', '4', '5', '6', '7', '8', '9', '0', '-', '='),
         ('', 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p', '[', ']',
          '\\'),
         ('', 'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l', ';', '\''),
         ('', 'z', 'x', 'c', 'v', 'b', 'n', 'm', ',', '.', '/'),
         ('', '', ' ', ' ', ' ', ' ', ' ', ' ', ' ')),
        (('~', '!', '@', '#', '$', '%', '^', '&', '*', '(', ')', '_', '+'),
         ('', 'Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P', '{', '}', '|'),
         ('', 'A', 'S', 'D', 'F', 'G', 'H', 'J', 'K', 'L', ':', '"'),
         ('', 'Z', 'X', 'C', 'V', 'B', 'N', 'M', '<', '>', '?'),
         ('', '', ' ', ' ', ' ', ' ', ' ', ' ', ' '))
    )}

    keyboard = layout['QWERTY']
    lowercase = {item for sublist in keyboard[0] for item in sublist}
    uppercase = {item for sublist in keyboard[1] for item in sublist}

    def _kb_array_for_char(char):
        """Return the keyboard layout that contains ch."""
        if char in lowercase:
            return keyboard[0]
        elif char in uppercase:
            return keyboard[1]
        else:
            raise ValueError(char + ' not found in any keyboard layouts')

    def _get_char_coord(char, keyboard):
        """Return the row & column of char in the keyboard."""
        for row in keyboard:
            if char in row:
                return keyboard.index(row), row.index(char)
        raise ValueError(char + ' not found in given keyboard layout')

    def _euclidean_keyboard_distance(char1, char2):
        row1, col1 = _get_char_coord(char1, _kb_array_for_char(char1))
        row2, col2 = _get_char_coord(char2, _kb_array_for_char(char2))
        return ((row1 - row2) ** 2 + (col1 - col2) ** 2) ** 0.5

    def _manhattan_keyboard_distance(char1, char2):
        row1, col1 = _get_char_coord(char1, _kb_array_for_char(char1))
        row2, col2 = _get_char_coord(char2, _kb_array_for_char(char2))
        return abs(row1 - row2) + abs(col1 - col2)

    def _log_euclidean_keyboard_distance(char1, char2):
        return log(1 + _euclidean_keyboard_distance(char1, char2))

    def _log_manhattan_keyboard_distance(char1, char2):
        return log(1 + _manhattan_keyboard_distance(char1, char2))

    metric_dict = {'euclidean': _euclidean_keyboard_distance,
                   'manhattan': _manhattan_keyboard_distance,
                   'log-euclidean': _log_euclidean_keyboard_distance,
                   'log-manhattan': _log_manhattan_keyboard_distance}

    def substitution_cost(char1, char2):
        cost = sub_cost
        cost *= (metric_dict[metric](char1, char2) +
                 shift_cost * (_kb_array_for_char(char1) !=
                               _kb_array_for_char(char2)))
        return cost

    d_mat = np_zeros((len(src) + 1, len(tar) + 1), dtype=np_float32)
    for i in range(len(src) + 1):
        d_mat[i, 0] = i * del_cost
    for j in range(len(tar) + 1):
        d_mat[0, j] = j * ins_cost

    for i in range(len(src)):
        for j in range(len(tar)):
            d_mat[i + 1, j + 1] = min(
                d_mat[i + 1, j] + ins_cost,  # ins
                d_mat[i, j + 1] + del_cost,  # del
                d_mat[i, j] + (substitution_cost(src[i], tar[j])
                               if src[i] != tar[j] else 0)  # sub/==
            )

    return d_mat[len(src), len(tar)]


def dist_typo(src, tar, metric='euclidean', cost=(1, 1, 0.5, 0.5)):
    """Return the normalized typo distance between two strings.

    This is typo distance, normalized to [0, 1].

    :param str src, tar: two strings to be compared
    :param str metric: supported values include: 'euclidean', 'manhattan',
          'log-euclidean', and 'log-manhattan'
    :param tuple cost: a 4-tuple representing the cost of the four possible
        edits: inserts, deletes, substitutions, and shift, respectively (by
        default: (1, 1, 0.5, 0.5)) The substitution & shift costs should be
        significantly less than the cost of an insertion & deletion unless
        a log metric is used.
    :return: normalized typo distance
    :rtype: float
    """
    if src == tar:
        return 0
    ins_cost, del_cost = cost[:2]
    return (typo(src, tar, metric, cost) /
            (max(len(src)*del_cost, len(tar)*ins_cost)))


def sim_typo(src, tar, metric='euclidean', cost=(1, 1, 0.5, 0.5)):
    """Return the normalized typo similarity between two strings.

    Normalized typo similarity is the complement of normalized typo distance:
    :math:`sim_{typo} = 1 - dist_{typo}`.

    :param str src, tar: two strings to be compared
    :param str metric: supported values include: 'euclidean', 'manhattan',
          'log-euclidean', and 'log-manhattan'
    :param tuple cost: a 4-tuple representing the cost of the four possible
        edits: inserts, deletes, substitutions, and shift, respectively (by
        default: (1, 1, 0.5, 0.5)) The substitution & shift costs should be
        significantly less than the cost of an insertion & deletion unless
        a log metric is used.
    :return: normalized typo similarity
    :rtype: float
    """
    return 1 - dist_typo(src, tar, metric, cost)


def dist_indel(src, tar):
    """Return the indel distance between two strings.

    This is equivalent to levenshtein distance, when only inserts and deletes
    are possible.

    :param str src, tar: two strings to be compared
    :return: indel distance
    :rtype: float
    """
    return dist_levenshtein(src, tar, mode='lev', cost=(1, 1, 9999, 9999))


def sim_indel(src, tar):
    """Return the indel similarity of two strings.

    Normalized bag similarity is the complement of normalized bag distance:
    :math:`sim_{bag} = 1 - dist_{bag}`

    :param str src, tar: two strings to be compared
    :return: indel similarity
    :rtype: float
    """
    return sim_levenshtein(src, tar, mode='lev', cost=(1, 1, 9999, 9999))


def _synoname_strip_punct(word):
    """Return a word with punctuation stripped out.

    :param word:
    :return:
    """
    stripped = ''
    for char in word:
        if char not in set(',-./:;"&\'()!{|}?$%*+<=>[\\]^_`~'):
            stripped += char
    return stripped.strip()


def synoname_word_approximation(src_ln, tar_ln, src_fn='', tar_fn='', features=None):
    """

    :return:
    """
    if features is None:
        features = {}
    if 'src_specials' not in features:
        features['src_specials'] = []
    if 'tar_specials' not in features:
        features['tar_specials'] = []

    src_len_specials = len(features['src_specials'])
    tar_len_specials = len(features['tar_specials'])

    # 1
    if ('gen_conflict' not in features or features['gen_conflict'] or
            'roman_conflict' not in features or features['roman_conflict']):
        return 0

    # 3 & 7
    full_tar1 = ' '.join((tar_ln, tar_fn)).replace('-', ' ')
    for s_type, s_pos in features['tar_specials']:
        if s_pos == 'a':
            full_tar1 = full_tar1[:1+len(_synoname_special_table[s_type][1])]
        elif s_pos == 'b':
            loc = full_tar1.find(' '+_synoname_special_table[s_type][1]+' ')+1
            full_tar1 = full_tar1[:loc]+full_tar1[loc+len(_synoname_special_table[s_type][1]):]
        elif s_pos == 'c':
            full_tar1 = full_tar1[1+len(_synoname_special_table[s_type][1]):]

    full_src1 = ' '.join((src_ln, src_fn)).replace('-', ' ')
    for s_type, s_pos in features['src_specials']:
        if s_pos == 'a':
            full_src1 = full_src1[:1+len(_synoname_special_table[s_type][1])]
        elif s_pos == 'b':
            loc = full_src1.find(' '+_synoname_special_table[s_type][1]+' ')+1
            full_src1 = full_src1[:loc]+full_src1[loc+len(_synoname_special_table[s_type][1]):]
        elif s_pos == 'c':
            full_src1 = full_src1[1+len(_synoname_special_table[s_type][1]):]

    full_tar2 = full_tar1
    for s_type, s_pos in features['tar_specials']:
        if s_pos == 'd':
            full_tar2 = full_tar2[len(_synoname_special_table[s_type][1]):]
        elif s_pos == 'X' and _synoname_special_table[s_type][1] in full_tar2:
            loc = full_tar2.find(' ' + _synoname_special_table[s_type][1] + ' ') + 1
            full_tar2 = full_tar2[:loc] + full_tar2[loc + len(_synoname_special_table[s_type][1]):]

    full_src2 = full_tar1
    for s_type, s_pos in features['src_specials']:
        if s_pos == 'd':
            full_src2 = full_src2[len(_synoname_special_table[s_type][1]):]
        elif s_pos == 'X' and _synoname_special_table[s_type][1] in full_src2:
            loc = full_src2.find(' ' + _synoname_special_table[s_type][1] + ' ') + 1
            full_src2 = full_src2[:loc] + full_src2[loc + len(_synoname_special_table[s_type][1]):]

    full_tar1 = _synoname_strip_punct(full_tar1)
    tar1_words = full_tar1.split()
    tar1_num_words = len(tar1_words)

    full_src1 = _synoname_strip_punct(full_src1)
    src1_words = full_src1.split()
    src1_num_words = len(src1_words)

    full_tar2 = _synoname_strip_punct(full_tar2)
    tar2_words = full_tar2.split()
    tar2_num_words = len(tar2_words)

    full_src2 = _synoname_strip_punct(full_src2)
    src2_words = full_src2.split()
    src2_num_words = len(src2_words)

    # 2
    if src1_num_words < 2 and src_len_specials == 0 and src2_num_words < 2 and tar_len_specials == 0:
        return 0

    # 4
    if tar1_num_words == 1 and src1_num_words == 1 and tar1_words[0] == src1_words[0]:
        return 1
    if tar1_num_words < 2 and tar_len_specials == 0:
        return 0

    # 5
    last_found = False
    for word in tar1_words:
        if src_ln.endswith(word) or word+' ' in src_ln:
            last_found = True

    if not last_found:
        for word in src1_words:
            if tar_ln.endswith(word) or word+' ' in tar_ln:
                last_found = True

    # 6
    matches = 0
    if last_found:
        for i, s_word in enumerate(src1_words):
            for j, t_word in enumerate(tar1_words):
                if s_word == t_word:
                    src1_words[i] = '@'
                    tar1_words[i] = '@'
                    matches += 1
    w_ratio = matches/max(tar1_num_words, src1_num_words)
    if matches > 1 or (matches == 1 and
                       src1_num_words == 1 and tar1_num_words == 1 and
                       (tar_len_specials > 0 or src_len_specials > 0)):
        return w_ratio

    # 8
    if tar2_num_words == 1 and src2_num_words == 1 and tar2_words[0] == src2_words[0]:
        return 1
    if tar2_num_words < 2 and tar_len_specials == 0:
        return 0

    # 9
    last_found = False
    for word in tar2_words:
        if src_ln.endswith(word) or word+' ' in src_ln:
            last_found = True

    if not last_found:
        for word in src2_words:
            if tar_ln.endswith(word) or word+' ' in tar_ln:
                last_found = True

    if not last_found:
        return 0

    # 10
    matches = 0
    if last_found:
        for i, s_word in enumerate(src2_words):
            for j, t_word in enumerate(tar2_words):
                if s_word == t_word:
                    src2_words[i] = '@'
                    tar2_words[i] = '@'
                    matches += 1
    w_ratio = matches/max(tar2_num_words, src2_num_words)
    if matches > 1 or (matches == 1 and
                       src2_num_words == 1 and tar2_num_words == 1 and
                       (tar_len_specials > 0 or src_len_specials > 0)):
        return w_ratio

    return 0


def synoname(src, tar, word_approx_min=0.3, char_approx_min=0.73,
             tests=2**11-1):
    """Return the Synoname similarity type of two words.

    Cf. :cite:`Getty:1991,Gross:1991`

    :param str src, tar: two strings to be compared
    :return: Synoname value
    :rtype: int
    """
    test_dict = {val: n**2 for n, val in enumerate([
        'exact', 'omission', 'substitution', 'transposition', 'punctuation',
        'initials', 'extended', 'inclusion', 'no_first', 'word_approx',
        'confusions', 'char_approx'])}
    match_type_dict = {val: n for n, val in enumerate([
        'exact', 'omission', 'substitution', 'transposition', 'punctuation',
        'initials', 'extended', 'inclusion', 'no_first', 'word_approx',
        'confusions', 'char_approx', 'no_match'], 1)}

    if isinstance(tests, Iterable):
        new_tests = 0
        for term in tests:
            if term in test_dict:
                new_tests += test_dict[term]
        tests = new_tests

    if isinstance(src, tuple):
        src_ln, src_fn, src_qual = src
    else:
        src_ln, src_fn, src_qual = src.split('#')[1:4]
    if isinstance(tar, tuple):
        tar_ln, tar_fn, tar_qual = tar
    else:
        tar_ln, tar_fn, tar_qual = tar.split('#')[1:4]

    def split_special(spec):
        spec_list = []
        while spec:
            spec_list.append((int(spec[:3]), spec[3:4]))
            spec = spec[4:]
        return spec_list

    # 1. Preprocessing

    # Lowercasing
    src_fn = src_fn.strip().lower()
    src_ln = src_ln.strip().lower()
    src_qual = src_qual.strip().lower()

    tar_fn = tar_fn.strip().lower()
    tar_ln = tar_ln.strip().lower()
    tar_qual = tar_qual.strip().lower()

    # Create toolcodes
    src_fn, src_ln, src_tc = synoname_toolcode(src_fn, src_ln, src_qual)
    tar_fn, tar_ln, tar_tc = synoname_toolcode(tar_fn, tar_ln, tar_qual)

    src_generation = int(src_tc[2])
    src_romancode = int(src_tc[3:6])
    src_len_fn = int(src_tc[6:8])
    src_tc = src_tc.split('#')
    src_specials = split_special(src_tc[1])

    tar_generation = int(tar_tc[2])
    tar_romancode = int(tar_tc[3:6])
    tar_len_fn = int(tar_tc[6:8])
    tar_tc = tar_tc.split('#')
    tar_specials = split_special(tar_tc[1])

    gen_conflict = (src_generation != tar_generation and
                    (src_generation or tar_generation))
    roman_conflict = (src_romancode != tar_romancode and
                      (src_romancode or tar_romancode))

    ln_equal = src_ln == tar_ln
    fn_equal = src_fn == tar_fn

    # approx_c
    def approx_c():
        if gen_conflict or roman_conflict:
            return 0

        full_src = ' '.join((src_ln, src_fn))
        if full_src.startswith('master '):
            full_src = full_src[len('master '):]
            for intro in ['of the ', 'of ', 'known as the ', 'with the ',
                          'with ']:
                if full_src.ssrctswith(intro):
                    full_src = full_src[len(intro):]

        full_tar = ' '.join((tar_ln, tar_fn))
        if full_tar.startswith('master '):
            full_tar = full_tar[len('master '):]
            for intro in ['of the ', 'of ', 'known as the ', 'with the ',
                          'with ']:
                if full_tar.startswith(intro):
                    full_tar = full_tar[len(intro):]

        ca_ratio = sim_ratcliff_obershelp(full_src, full_tar)
        return ca_ratio >= char_approx_min, ca_ratio

    approx_c_result, ca_ratio = approx_c()

    if tests & test_dict['exact'] and fn_equal and ln_equal:
        return match_type_dict['exact']
    if tests & test_dict['omission']:
        if (fn_equal and
                levenshtein(src_ln, tar_ln, cost=(1, 1, 99, 99)) == 1):
            if not roman_conflict:
                return match_type_dict['omission']
        elif (ln_equal and
              levenshtein(src_fn, tar_fn, cost=(1, 1, 99, 99)) == 1):
            return match_type_dict['omission']
    if tests & test_dict['substitution']:
        if (fn_equal and
                levenshtein(src_ln, tar_ln, cost=(99, 99, 1, 99)) == 1):
            return match_type_dict['substitution']
        elif (ln_equal and
              levenshtein(src_fn, tar_fn, cost=(99, 99, 1, 99)) == 1):
            return match_type_dict['substitution']
    if tests & test_dict['transposition']:
        if (fn_equal and
                levenshtein(src_ln, tar_ln, cost=(99, 99, 99, 1)) == 1):
            return match_type_dict['transposition']
        elif (ln_equal and
              levenshtein(src_fn, tar_fn, cost=(99, 99, 99, 1)) == 1):
            return match_type_dict['transposition']
    if tests & test_dict['punctuation']:
        np_src_fn = _synoname_strip_punct(src_fn)
        np_tar_fn = _synoname_strip_punct(tar_fn)
        np_src_ln = _synoname_strip_punct(src_ln)
        np_tar_ln = _synoname_strip_punct(tar_ln)

        if np_src_fn == np_tar_fn and np_src_ln == np_tar_ln:
            return match_type_dict['punctuation']
    if tests & test_dict['initials'] and ln_equal:
        if src_fn or tar_fn:
            src_initials = ''.join(_[0] for _ in src_fn.split())
            tar_initials = ''.join(_[0] for _ in tar_fn.split())
            if src_initials == tar_initials:
                return match_type_dict['initials']
            initial_diff = abs(len(src_initials)-len(tar_initials))
            if (initial_diff and
                    ((initial_diff == levenshtein(src_initials, tar_initials,
                                                 cost=(1, 99, 99, 99))) or
                     (initial_diff == levenshtein(tar_initials, src_initials,
                                                  cost=(1, 99, 99, 99))))):
                return match_type_dict['initials']
    if tests & test_dict['extended']:
        if src_ln[0] == tar_ln[0] and (src_ln.startswith(tar_ln) or
                                       tar_ln.startswith(src_ln)):
            if ((not src_len_fn and not tar_len_fn) or
                    src_ln.startswith(tar_ln) or
                    tar_ln.startswith(src_ln)) and not roman_conflict:
                return match_type_dict['extended']
    if tests & test_dict['inclusion'] and ln_equal:
        if src_fn in tar_fn or tar_fn in src_ln:
            return match_type_dict['inclusion']
    if tests & test_dict['no_first'] and ln_equal:
        if src_fn == '' or tar_fn == '':
            return match_type_dict['no_first']
    if tests & test_dict['word_approx']:
        ratio = synoname_word_approximation(src_ln, tar_ln, src_fn, tar_fn,
                                            {'gen_conflict': gen_conflict,
                                             'roman_conflict': roman_conflict,
                                             'src_specials': src_specials,
                                             'tar_specials': tar_specials})
        if ratio == 1 and tests & test_dict['confusions']:
            if ' '.join((src_fn, src_ln)) == ' '.join((tar_fn, tar_ln)):
                return match_type_dict['confusions']
        if ratio >= word_approx_min:
            return match_type_dict['word_approx']
    if tests & test_dict['char_approx']:
        if ca_ratio >= char_approx_min:
            return match_type_dict['char_approx']
    return match_type_dict['no_match']


def sim_tfidf(src, tar, qval=2, docs_src=None, docs_tar=None):
    """Return the TF-IDF similarity of two strings.

    TF-IDF similarity

    This is chiefly based on the "Formal Definition of TF/IDF Distance" at:
    http://alias-i.com/lingpipe/docs/api/com/aliasi/spell/TfIdfDistance.html

    :param str src, tar: two strings to be compared (or QGrams/Counter objects)
    :param int qval: the length of each q-gram; 0 or None for non-q-gram
        version
    :param Counter docs_src: a Counter object or string representing the
        document corpus for the src string
    :param Counter docs_tar: a Counter object or string representing the
        document corpus for the tar string (or set to None to use the docs_src
        for both)
    :returns: TF-IDF similarity
    :rtype: float
    """
    if src == tar:
        return 1.0  # TODO: confirm correctness of this when docs are different
    elif not src or not tar:
        return 0.0

    q_src, q_tar = _get_qgrams(src, tar, qval)

    if isinstance(docs_src, Counter):
        q_docs = docs_src
    elif qval and qval > 0:
        q_docs = QGrams(docs_src, qval)
    else:
        q_docs = Counter(docs_src.strip().split())

    if not q_src or not q_tar:
        return 0.0

    # TODO: finish implementation
    return 0.5  # hardcoded to half

###############################################################################


def sim(src, tar, method=sim_levenshtein):
    """Return a similarity of two strings.

    This is a generalized function for calling other similarity functions.

    :param str src, tar: two strings to be compared
    :param function method: specifies the similarity metric (Levenshtein by
        default)
    :returns: similarity according to the specified function
    :rtype: float

    >>> round(sim('cat', 'hat'), 12)
    0.666666666667
    >>> round(sim('Niall', 'Neil'), 12)
    0.4
    >>> sim('aluminum', 'Catalan')
    0.125
    >>> sim('ATCG', 'TAGC')
    0.25
    """
    if callable(method):
        return method(src, tar)
    else:
        raise AttributeError('Unknown similarity function: ' + str(method))


def dist(src, tar, method=sim_levenshtein):
    """Return a distance between two strings.

    This is a generalized function for calling other distance functions.

    :param str src, tar: two strings to be compared
    :param function method: specifies the similarity metric (Levenshtein by
        default) -- Note that this takes a similarity metric function, not
        a distance metric function.
    :returns: distance according to the specified function
    :rtype: float

    >>> round(dist('cat', 'hat'), 12)
    0.333333333333
    >>> round(dist('Niall', 'Neil'), 12)
    0.6
    >>> dist('aluminum', 'Catalan')
    0.875
    >>> dist('ATCG', 'TAGC')
    0.75
    """
    if callable(method):
        return 1 - method(src, tar)
    else:
        raise AttributeError('Unknown distance function: ' + str(method))


if __name__ == '__main__':
    import doctest
    doctest.testmod()

chrislit / abydos

Push — master ( 52414d...a2edde )

abydos.distance.lcsstr() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like
