(a, b, max_cost)
| 1683 | |
| 1684 | |
| 1685 | def _levenshtein_distance(a, b, max_cost): |
| 1686 | # A Python implementation of Python/suggestions.c:levenshtein_distance. |
| 1687 | |
| 1688 | # Both strings are the same |
| 1689 | if a == b: |
| 1690 | return 0 |
| 1691 | |
| 1692 | # Trim away common affixes |
| 1693 | pre = 0 |
| 1694 | while a[pre:] and b[pre:] and a[pre] == b[pre]: |
| 1695 | pre += 1 |
| 1696 | a = a[pre:] |
| 1697 | b = b[pre:] |
| 1698 | post = 0 |
| 1699 | while a[:post or None] and b[:post or None] and a[post-1] == b[post-1]: |
| 1700 | post -= 1 |
| 1701 | a = a[:post or None] |
| 1702 | b = b[:post or None] |
| 1703 | if not a or not b: |
| 1704 | return _MOVE_COST * (len(a) + len(b)) |
| 1705 | if len(a) > _MAX_STRING_SIZE or len(b) > _MAX_STRING_SIZE: |
| 1706 | return max_cost + 1 |
| 1707 | |
| 1708 | # Prefer shorter buffer |
| 1709 | if len(b) < len(a): |
| 1710 | a, b = b, a |
| 1711 | |
| 1712 | # Quick fail when a match is impossible |
| 1713 | if (len(b) - len(a)) * _MOVE_COST > max_cost: |
| 1714 | return max_cost + 1 |
| 1715 | |
| 1716 | # Instead of producing the whole traditional len(a)-by-len(b) |
| 1717 | # matrix, we can update just one row in place. |
| 1718 | # Initialize the buffer row |
| 1719 | row = list(range(_MOVE_COST, _MOVE_COST * (len(a) + 1), _MOVE_COST)) |
| 1720 | |
| 1721 | result = 0 |
| 1722 | for bindex in range(len(b)): |
| 1723 | bchar = b[bindex] |
| 1724 | distance = result = bindex * _MOVE_COST |
| 1725 | minimum = sys.maxsize |
| 1726 | for index in range(len(a)): |
| 1727 | # 1) Previous distance in this row is cost(b[:b_index], a[:index]) |
| 1728 | substitute = distance + _substitution_cost(bchar, a[index]) |
| 1729 | # 2) cost(b[:b_index], a[:index+1]) from previous row |
| 1730 | distance = row[index] |
| 1731 | # 3) existing result is cost(b[:b_index+1], a[index]) |
| 1732 | |
| 1733 | insert_delete = min(result, distance) + _MOVE_COST |
| 1734 | result = min(insert_delete, substitute) |
| 1735 | |
| 1736 | # cost(b[:b_index+1], a[:index+1]) |
| 1737 | row[index] = result |
| 1738 | if result < minimum: |
| 1739 | minimum = result |
| 1740 | if minimum > max_cost: |
| 1741 | # Everything in this row is too big, so bail early. |
| 1742 | return max_cost + 1 |
no test coverage detected