Python Implementation of Levenshtein Distance for Fuzzy String Matching.

levenshtein_distance_fuzzy_search.py

"""
Copyright (C) 2024 promto-c
Permission Notice:
- You are free to use, copy, modify, and distribute this software for any purpose.
- No restrictions are imposed on the use of this software.
- You do not need to give credit or include this notice in your work.
- Use at your own risk.
- This software is provided "AS IS" without any warranty, either expressed or implied.
Note: This code is intended primarily as an example. While you can use it freely as described above, be aware that it utilizes PyQt5, which is licensed under GPL v3. Ensure you adhere to PyQt5's licensing terms when using or distributing this code.
"""
from typing import List

def levenshtein_distance(s1: str, s2: str) -> int:
    """Calculates the Levenshtein distance between two strings.

    Args:
        s1: The first string to compare.
        s2: The second string to compare.

    Returns:
        The Levenshtein distance between the two strings.

    Examples:
        >>> levenshtein_distance("kitten", "sitting")
        3
        >>> levenshtein_distance("flaw", "lawn")
        2
        >>> levenshtein_distance("", "")
        0
    """
    # Swap to ensure shorter string in s1 for efficiency
    if len(s1) < len(s2):
        return levenshtein_distance(s2, s1)
    
    # Distance is length of second string if first is empty
    if len(s2) == 0:
        return len(s1)
    
    # Initialize the previous row of distances
    previous_row = range(len(s2) + 1)

    # Iterate over each character in s1
    for i, c1 in enumerate(s1):
        current_row = [i + 1]

        # Iterate over each character in s2
        for j, c2 in enumerate(s2):
            # Calculate costs for various operations
            insertions = previous_row[j + 1] + 1
            deletions = current_row[j] + 1
            substitutions = previous_row[j] + (c1 != c2)

            # Choose the minimum cost operation
            current_row.append(min(insertions, deletions, substitutions))

        # Prepare for next iteration
        previous_row = current_row
    
    # The distance is the last element in the final row
    return previous_row[-1]

def fuzzy_search(query: str, strings: List[str], max_distance: int = 6, 
                 sort_by_distance: bool = True) -> List[str]:
    """Performs a fuzzy search of a query string within a list of strings.

    This function returns matches within a specified maximum Levenshtein distance from the query string,
    optionally sorted by their distance.

    Args:
        query: The query string to search for.
        strings: A list of strings to search within.
        max_distance: The maximum Levenshtein distance of matches to include.
        sort_by_distance: Whether to sort the results by their Levenshtein distance to the query string.

    Returns:
        A list of strings that match the query within the specified maximum distance, optionally sorted
        by their Levenshtein distance to the query.

    Examples:
        >>> fuzzy_search("test", ["best", "test", "taste"], max_distance=1, sort_by_distance=False)
        ['best', 'test']
        >>> fuzzy_search("book", ["back", "bock", "book"], max_distance=2, sort_by_distance=False)
        ['back', 'bock', 'book']
        >>> fuzzy_search("book", ["back", "bock", "book"], max_distance=2)
        ['book', 'bock', 'back']
    """
    # Calculate distance for each string and filter by max_distance
    matches_with_distance = [(s, levenshtein_distance(query, s)) for s in strings]
    filtered_matches = [match for match in matches_with_distance if match[1] <= max_distance]

    # Sort matches by distance if required
    if sort_by_distance:
        filtered_matches.sort(key=lambda x: x[1])

    # Return only the strings, not their distances
    return [match[0] for match in filtered_matches]


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

    print(fuzzy_search("scene12_Shot001_compp_v01", ["Scene12 Shot001_Comp_v02", "Scene12_Shot001 Comp_v01", "Scene13_Shot002_Light_v02", "Scene12_Shot003_Anim_v03"]))
    print(levenshtein_distance("talaw", "tlawn"))
    print(levenshtein_distance("talaw", "tzawn"))