Repository: roboflow/supervision
File: supervision/detection/utils/vlms.py (Python)

Code before:
    if not case_sensitive:
        string_1 = string_1.lower()
        string_2 = string_2.lower()

    length_1 = len(string_1)
    length_2 = len(string_2)
    distance_matrix = [[0] * (length_2 + 1) for _ in range(length_1 + 1)]

    for i in range(length_1 + 1):
        distance_matrix[i][0] = i
    for j in range(length_2 + 1):
        distance_matrix[0][j] = j

    for i in range(1, length_1 + 1):
        for j in range(1, length_2 + 1):
            if string_1[i - 1] == string_2[j - 1]:
                substitution_cost = 0
            else:
                substitution_cost = 1
            distance_matrix[i][j] = min(
                distance_matrix[i - 1][j] + 1,
                distance_matrix[i][j - 1] + 1,
                distance_matrix[i - 1][j - 1] + substitution_cost,
            )

    return distance_matrix[length_1][length_2]


def fuzzy_match_index(
    candidates: list[str],
    query: str,
    threshold: int,
    case_sensitive: bool = True,
) -> int | None:
    """
    Searches for the first string in `candidates` whose edit distance
    to `query` is less than or equal to `threshold`.

    Args:
        candidates (list[str]): List of strings to search.
        query (str): String to compare against the candidates.
        threshold (int): Maximum allowed edit distance for a match.
        case_sensitive (bool, optional): Whether matching should be case-sensitive.

    Returns:
        Optional[int]: Index of the first matching string in candidates,
            or None if no match is found.

    Examples:
        ```python
        fuzzy_match_index(["cat", "dog", "rat"], "dat", threshold=1)

Review comment (performance):
Suggestion for optimization of space complexity: The current implementation uses a DP approach with space complexity `O(len(string_1) * len(string_2))`. However, the calculation of each row in the `distance_matrix` only depends on the previous row, so we don't need to store the entire matrix, instead just keep track of only the previous and current rows. This can reduce the space complexity to `O(min(len(string_1), len(string_2)))`.

Code after:
    if not case_sensitive:
        string_1 = string_1.lower()
        string_2 = string_2.lower()

    if len(string_1) < len(string_2):
        string_1, string_2 = string_2, string_1

    prev_row = list(range(len(string_2) + 1))
    curr_row = [0] * (len(string_2) + 1)

    for i in range(1, len(string_1) + 1):
        curr_row[0] = i
        for j in range(1, len(string_2) + 1):
            if string_1[i - 1] == string_2[j - 1]:
                substitution_cost = 0
            else:
                substitution_cost = 1
            curr_row[j] = min(
                prev_row[j] + 1,
                curr_row[j - 1] + 1,
                prev_row[j - 1] + substitution_cost,
            )
        prev_row, curr_row = curr_row, prev_row

    return prev_row[len(string_2)]


def fuzzy_match_index(
    candidates: list[str],
    query: str,
    threshold: int,
    case_sensitive: bool = True,
) -> int | None:
    """
    Searches for the first string in `candidates` whose edit distance
    to `query` is less than or equal to `threshold`.

    Args:
        candidates (list[str]): List of strings to search.
        query (str): String to compare against the candidates.
        threshold (int): Maximum allowed edit distance for a match.
        case_sensitive (bool, optional): Whether matching should be case-sensitive.

    Returns:
        Optional[int]: Index of the first matching string in candidates,
            or None if no match is found.

    Examples:
        ```python
        fuzzy_match_index(["cat", "dog", "rat"], "dat", threshold=1)
        # 0