(a, b, max_cost)
| 1843 | |
| 1844 | |
| 1845 | def _levenshtein_distance(a, b, max_cost): |
| 1846 | # A Python implementation of Python/suggestions.c:levenshtein_distance. |
| 1847 | |
| 1848 | # Both strings are the same |
| 1849 | if a == b: |
| 1850 | return 0 |
| 1851 | |
| 1852 | # Trim away common affixes |
| 1853 | pre = 0 |
| 1854 | while a[pre:] and b[pre:] and a[pre] == b[pre]: |
| 1855 | pre += 1 |
| 1856 | a = a[pre:] |
| 1857 | b = b[pre:] |
| 1858 | post = 0 |
| 1859 | while a[:post or None] and b[:post or None] and a[post-1] == b[post-1]: |
| 1860 | post -= 1 |
| 1861 | a = a[:post or None] |
| 1862 | b = b[:post or None] |
| 1863 | if not a or not b: |
| 1864 | return _MOVE_COST * (len(a) + len(b)) |
| 1865 | if len(a) > _MAX_STRING_SIZE or len(b) > _MAX_STRING_SIZE: |
| 1866 | return max_cost + 1 |
| 1867 | |
| 1868 | # Prefer shorter buffer |
| 1869 | if len(b) < len(a): |
| 1870 | a, b = b, a |
| 1871 | |
| 1872 | # Quick fail when a match is impossible |
| 1873 | if (len(b) - len(a)) * _MOVE_COST > max_cost: |
| 1874 | return max_cost + 1 |
| 1875 | |
| 1876 | # Instead of producing the whole traditional len(a)-by-len(b) |
| 1877 | # matrix, we can update just one row in place. |
| 1878 | # Initialize the buffer row |
| 1879 | row = list(range(_MOVE_COST, _MOVE_COST * (len(a) + 1), _MOVE_COST)) |
| 1880 | |
| 1881 | result = 0 |
| 1882 | for bindex in range(len(b)): |
| 1883 | bchar = b[bindex] |
| 1884 | distance = result = bindex * _MOVE_COST |
| 1885 | minimum = sys.maxsize |
| 1886 | for index in range(len(a)): |
| 1887 | # 1) Previous distance in this row is cost(b[:b_index], a[:index]) |
| 1888 | substitute = distance + _substitution_cost(bchar, a[index]) |
| 1889 | # 2) cost(b[:b_index], a[:index+1]) from previous row |
| 1890 | distance = row[index] |
| 1891 | # 3) existing result is cost(b[:b_index+1], a[index]) |
| 1892 | |
| 1893 | insert_delete = min(result, distance) + _MOVE_COST |
| 1894 | result = min(insert_delete, substitute) |
| 1895 | |
| 1896 | # cost(b[:b_index+1], a[:index+1]) |
| 1897 | row[index] = result |
| 1898 | if result < minimum: |
| 1899 | minimum = result |
| 1900 | if minimum > max_cost: |
| 1901 | # Everything in this row is too big, so bail early. |
| 1902 | return max_cost + 1 |
no test coverage detected
searching dependent graphs…