| 1586 | #define UNIT (1 << 16) |
| 1587 | |
| 1588 | uint32 fuzzy_distance(const char *s1, unsigned len1, const char *s2, unsigned len2, uint32 upperlimit) |
| 1589 | { |
| 1590 | uint32 a[MAXPATHLEN], diag, above, left, diag_inc, above_inc, left_inc; |
| 1591 | int32 cost; |
| 1592 | unsigned i1, i2; |
| 1593 | |
| 1594 | /* Check to see if the Levenshtein distance must be greater than the |
| 1595 | * upper limit defined by the previously found lowest distance using |
| 1596 | * the heuristic that the Levenshtein distance is greater than the |
| 1597 | * difference in length of the two strings */ |
| 1598 | if ((len1 > len2 ? len1 - len2 : len2 - len1) * UNIT > upperlimit) |
| 1599 | return 0xFFFFU * UNIT + 1; |
| 1600 | |
| 1601 | if (!len1 || !len2) { |
| 1602 | if (!len1) { |
| 1603 | s1 = s2; |
| 1604 | len1 = len2; |
| 1605 | } |
| 1606 | for (i1 = 0, cost = 0; i1 < len1; i1++) |
| 1607 | cost += s1[i1]; |
| 1608 | return (int32)len1 * UNIT + cost; |
| 1609 | } |
| 1610 | |
| 1611 | for (i2 = 0; i2 < len2; i2++) |
| 1612 | a[i2] = (i2+1) * UNIT; |
| 1613 | |
| 1614 | for (i1 = 0; i1 < len1; i1++) { |
| 1615 | diag = i1 * UNIT; |
| 1616 | above = (i1+1) * UNIT; |
| 1617 | for (i2 = 0; i2 < len2; i2++) { |
| 1618 | left = a[i2]; |
| 1619 | if ((cost = *((uchar*)s1+i1) - *((uchar*)s2+i2)) != 0) { |
| 1620 | if (cost < 0) |
| 1621 | cost = UNIT - cost; |
| 1622 | else |
| 1623 | cost = UNIT + cost; |
| 1624 | } |
| 1625 | diag_inc = diag + cost; |
| 1626 | left_inc = left + UNIT + *((uchar*)s1+i1); |
| 1627 | above_inc = above + UNIT + *((uchar*)s2+i2); |
| 1628 | a[i2] = above = left < above |
| 1629 | ? (left_inc < diag_inc ? left_inc : diag_inc) |
| 1630 | : (above_inc < diag_inc ? above_inc : diag_inc); |
| 1631 | diag = left; |
| 1632 | } |
| 1633 | } |
| 1634 | |
| 1635 | return a[len2-1]; |
| 1636 | } |
| 1637 | |
| 1638 | #define BB_SLOT_SIZE (16*1024) /* Desired size in bytes */ |
| 1639 | #define BB_PER_SLOT_BITS (BB_SLOT_SIZE * 8) /* Number of bits per slot */ |