Spaces:
Sleeping
Sleeping
| def levenshtein_with_wildcard(str1, str2, wildcard_offsets_str1=None, wildcard_offsets_str2=None, verbose=False): | |
| """ | |
| Calculate the Levenshtein distance between two strings with support for wildcards at specific positions. | |
| Args: | |
| str1 (str): The first string. | |
| str2 (str): The second string. | |
| wildcard_offsets_str1 (iterable, optional): Indices in str1 that are wildcards. Defaults to None. | |
| wildcard_offsets_str2 (iterable, optional): Indices in str2 that are wildcards. Defaults to None. | |
| verbose (bool, optional): If True, prints the DP matrix and explains the process. | |
| Returns: | |
| int: The Levenshtein distance between the two strings. | |
| list: If verbose=True, also returns a list of operations performed. | |
| """ | |
| # Initialize empty sets if None | |
| wildcard_offsets_str1 = set(wildcard_offsets_str1 or []) | |
| wildcard_offsets_str2 = set(wildcard_offsets_str2 or []) | |
| m, n = len(str1), len(str2) | |
| # Create a matrix of size (m+1) x (n+1) | |
| dp = [[0] * (n + 1) for _ in range(m + 1)] | |
| # Initialize the first row and column | |
| for i in range(m + 1): | |
| dp[i][0] = i | |
| for j in range(n + 1): | |
| dp[0][j] = j | |
| # Fill the dp matrix | |
| for i in range(1, m + 1): | |
| for j in range(1, n + 1): | |
| # Check if either position is a wildcard | |
| is_str1_wildcard = (i - 1) in wildcard_offsets_str1 | |
| is_str2_wildcard = (j - 1) in wildcard_offsets_str2 | |
| # If either position is a wildcard, treat it as a match (cost = 0) | |
| if is_str1_wildcard or is_str2_wildcard: | |
| dp[i][j] = dp[i - 1][j - 1] # No cost for wildcard matches | |
| else: | |
| cost = 0 if str1[i - 1] == str2[j - 1] else 1 | |
| dp[i][j] = min( | |
| dp[i - 1][j] + 1, # deletion | |
| dp[i][j - 1] + 1, # insertion | |
| dp[i - 1][j - 1] + cost # substitution | |
| ) | |
| if verbose: | |
| operations = explain_match(str1, str2, dp, wildcard_offsets_str1, wildcard_offsets_str2) | |
| return dp[m][n], operations | |
| return dp[m][n] | |
| def explain_match(str1, str2, dp, wildcard_offsets_str1, wildcard_offsets_str2): | |
| """ | |
| Traces the optimal alignment path and explains each step of the matching process. | |
| Args: | |
| str1 (str): The first string. | |
| str2 (str): The second string. | |
| dp (list): The dynamic programming matrix. | |
| wildcard_offsets_str1 (set): Indices in str1 that are wildcards. | |
| wildcard_offsets_str2 (set): Indices in str2 that are wildcards. | |
| Returns: | |
| list: A list of explanation strings for each operation performed. | |
| """ | |
| m, n = len(str1), len(str2) | |
| operations = [] | |
| # Find the optimal path | |
| i, j = m, n | |
| path = [] | |
| while i > 0 or j > 0: | |
| path.append((i, j)) | |
| if i == 0: | |
| j -= 1 | |
| elif j == 0: | |
| i -= 1 | |
| else: | |
| substitution_cost = dp[i-1][j-1] | |
| deletion_cost = dp[i-1][j] | |
| insertion_cost = dp[i][j-1] | |
| min_cost = min(substitution_cost, deletion_cost, insertion_cost) | |
| if min_cost == substitution_cost: | |
| i -= 1 | |
| j -= 1 | |
| elif min_cost == deletion_cost: | |
| i -= 1 | |
| else: | |
| j -= 1 | |
| path.append((0, 0)) | |
| path.reverse() | |
| # Generate explanations for each step | |
| for idx in range(1, len(path)): | |
| prev_i, prev_j = path[idx-1] | |
| curr_i, curr_j = path[idx] | |
| # Diagonal move (match or substitution) | |
| if curr_i > prev_i and curr_j > prev_j: | |
| char1_idx = curr_i-1 | |
| char2_idx = curr_j-1 | |
| char1 = str1[char1_idx] | |
| char2 = str2[char2_idx] | |
| is_str1_wildcard = char1_idx in wildcard_offsets_str1 | |
| is_str2_wildcard = char2_idx in wildcard_offsets_str2 | |
| if is_str1_wildcard and is_str2_wildcard: | |
| operations.append(f"Double wildcard: Position {char1_idx} in str1 and position {char2_idx} in str2 are both wildcards") | |
| elif is_str1_wildcard: | |
| operations.append(f"Wildcard match: Position {char1_idx} in str1 is a wildcard, matches '{char2}' at position {char2_idx} in str2") | |
| elif is_str2_wildcard: | |
| operations.append(f"Wildcard match: Position {char2_idx} in str2 is a wildcard, matches '{char1}' at position {char1_idx} in str1") | |
| elif char1 == char2: | |
| operations.append(f"Match: '{char1}' at position {char1_idx} matches '{char2}' at position {char2_idx}") | |
| else: | |
| operations.append(f"Substitution: Replace '{char1}' at position {char1_idx} with '{char2}' at position {char2_idx}") | |
| # Horizontal move (insertion) | |
| elif curr_i == prev_i and curr_j > prev_j: | |
| char_idx = curr_j-1 | |
| operations.append(f"Insertion: Insert '{str2[char_idx]}' at position {char_idx} in str2") | |
| # Vertical move (deletion) | |
| elif curr_i > prev_i and curr_j == prev_j: | |
| char_idx = curr_i-1 | |
| operations.append(f"Deletion: Delete '{str1[char_idx]}' at position {char_idx} in str1") | |
| return operations | |
| def print_match_summary(str1, str2, wildcard_offsets_str1=None, wildcard_offsets_str2=None): | |
| """ | |
| Prints a summary of the match between two strings, highlighting wildcards by their offsets. | |
| Args: | |
| str1 (str): The first string. | |
| str2 (str): The second string. | |
| wildcard_offsets_str1 (iterable, optional): Indices in str1 that are wildcards. Defaults to None. | |
| wildcard_offsets_str2 (iterable, optional): Indices in str2 that are wildcards. Defaults to None. | |
| """ | |
| # Initialize empty lists if None | |
| wildcard_offsets_str1 = set(wildcard_offsets_str1 or []) | |
| wildcard_offsets_str2 = set(wildcard_offsets_str2 or []) | |
| distance, operations = levenshtein_with_wildcard( | |
| str1, str2, wildcard_offsets_str1, wildcard_offsets_str2, verbose=True | |
| ) | |
| # Create visual representations of the strings with wildcard markers | |
| str1_visual = "" | |
| for i, char in enumerate(str1): | |
| if i in wildcard_offsets_str1: | |
| str1_visual += f"[{char}]" # Mark wildcards with brackets | |
| else: | |
| str1_visual += char | |
| str2_visual = "" | |
| for i, char in enumerate(str2): | |
| if i in wildcard_offsets_str2: | |
| str2_visual += f"[{char}]" # Mark wildcards with brackets | |
| else: | |
| str2_visual += char | |
| print(f"Comparing '{str1_visual}' and '{str2_visual}'") | |
| print(f"Wildcards in str1: {sorted(wildcard_offsets_str1)}") | |
| print(f"Wildcards in str2: {sorted(wildcard_offsets_str2)}") | |
| print(f"Edit distance: {distance}") | |
| print("\nMatch process:") | |
| for i, op in enumerate(operations): | |
| print(f"Step {i+1}: {op}") | |
| # Visual representation of the alignment | |
| i, j = 0, 0 | |
| aligned_str1 = "" | |
| aligned_str2 = "" | |
| match_indicators = "" | |
| for op in operations: | |
| if "Match:" in op or "Substitution:" in op or "Wildcard match:" in op or "Double wildcard:" in op: | |
| is_str1_wildcard = i in wildcard_offsets_str1 | |
| is_str2_wildcard = j in wildcard_offsets_str2 | |
| # Add brackets around wildcards | |
| if is_str1_wildcard: | |
| aligned_str1 += f"[{str1[i]}]" | |
| else: | |
| aligned_str1 += str1[i] | |
| if is_str2_wildcard: | |
| aligned_str2 += f"[{str2[j]}]" | |
| else: | |
| aligned_str2 += str2[j] | |
| # Determine match indicator | |
| if "Wildcard match:" in op or "Double wildcard:" in op: | |
| match_indicators += "*" # Wildcard match | |
| elif "Match:" in op: | |
| match_indicators += "|" # Exact match | |
| else: | |
| match_indicators += "X" # Substitution | |
| i += 1 | |
| j += 1 | |
| elif "Insertion:" in op: | |
| aligned_str1 += "-" | |
| if j in wildcard_offsets_str2: | |
| aligned_str2 += f"[{str2[j]}]" | |
| else: | |
| aligned_str2 += str2[j] | |
| match_indicators += " " | |
| j += 1 | |
| elif "Deletion:" in op: | |
| if i in wildcard_offsets_str1: | |
| aligned_str1 += f"[{str1[i]}]" | |
| else: | |
| aligned_str1 += str1[i] | |
| aligned_str2 += "-" | |
| match_indicators += " " | |
| i += 1 | |
| print("\nAlignment:") | |
| print(aligned_str1) | |
| print(match_indicators) | |
| print(aligned_str2) | |
| print("\nLegend:") | |
| print("| = exact match, * = wildcard match, X = substitution, - = gap (insertion/deletion), [c] = wildcard position") | |
| # Summary of wildcard matches | |
| wildcard_matches = [op for op in operations if "Wildcard match:" in op or "Double wildcard:" in op] | |
| if wildcard_matches: | |
| print("\nWildcard matches:") | |
| for match in wildcard_matches: | |
| print(f"- {match}") | |
| return distance, operations | |
| # Example usage | |
| if __name__ == "__main__": | |
| # Example 1: "hello" vs "hello" with no wildcards | |
| print_match_summary("hello", "hello") | |
| # Example 2: "hello" vs "hallo" with no wildcards - expect distance of 1 | |
| print_match_summary("hello", "hallo") | |
| # Example 3: "hello" with 3rd position (index 2) as wildcard vs "hallo" - expect distance of 0 | |
| print_match_summary("hello", "hallo", wildcard_offsets_str1=[2]) | |
| # Example 4: "hello" vs "hillo" with 2nd position (index 1) as wildcard in str2 - expect distance of 0 | |
| print_match_summary("hello", "hillo", wildcard_offsets_str2=[1]) | |
| # Example 5: Multiple wildcards in str1 | |
| print_match_summary("hello", "haxyz", wildcard_offsets_str1=[2, 3, 4]) | |
| # Example 6: Wildcards in both strings at different positions | |
| print_match_summary("hello", "howdy", wildcard_offsets_str1=[2], wildcard_offsets_str2=[3, 4]) |