Damerau-Levenshtein Distance: A Guide to String Similarity with Transpositions

class EnhancedSpellChecker:
    def __init__(self, dictionary_words):
        """Initialize spell checker with a dictionary of valid words."""
        self.dictionary = set(word.lower() for word in dictionary_words)
        self.cache = {}  # For memoization

    def suggest_corrections(self, word: str, max_distance: int = 2) -> list:
        """
        Find potential corrections for a misspelled word using Damerau-Levenshtein distance
        and categorizing error types.

        Args:
            word: The word to check
            max_distance: Maximum allowed edit distance
        Returns:
            List of (suggestion, distance, error_type, operations) tuples
        """
        word = word.lower()
        if word in self.dictionary:
            return []

        suggestions = []
        for dict_word in self.dictionary:
            distance_result = damerau_levenshtein_distance(word, dict_word)
            distance = distance_result[0]
            matrix = distance_result[1]

            if distance <= max_distance:
                # Get detailed operations
                operations = self._analyze_operations(word, dict_word, matrix)
                error_type = self._categorize_error(operations)

                suggestions.append((
                    dict_word,
                    distance,
                    error_type,
                    operations
                ))

        # Sort suggestions by:
        # 1. Common error patterns (transpositions first)
        # 2. Edit distance
        # 3. Word length similarity
        return sorted(suggestions,
                     key=lambda x: (
                         0 if x[2] == "transposition" else 1,  # Prioritize transpositions
                         x[1],  # Then by edit distance
                         abs(len(x[0]) - len(word)),  # Then by length difference
                         x[0]  # Finally alphabetically
                     ))

    def _analyze_operations(self, s1: str, s2: str, matrix) -> list:
        """Analyze the sequence of operations needed to transform s1 into s2."""
        operations = visualize_operations(s1, s2, matrix)
        return operations

    def _categorize_error(self, operations) -> str:
        """
        Categorize the type of spelling error based on the operations.
        """
        op_types = [op[0] for op in operations]

        # Common error patterns
        if 'transpose' in op_types:
            return 'transposition'
        elif op_types.count('substitute') == 1 and len(op_types) == 1:
            return 'single_substitution'
        elif op_types.count('insert') == 1 and len(op_types) == 1:
            return 'single_insertion'
        elif op_types.count('delete') == 1 and len(op_types) == 1:
            return 'single_deletion'
        elif all(op == 'match' for op in op_types):
            return 'perfect_match'
        elif len(op_types) > 2:
            return 'multiple_errors'
        else:
            return 'other'

    def _format_suggestion(self, original: str, suggestion: str, operations: list) -> str:
        """
        Format a suggestion with detailed explanation.
        """
        explanation = []
        for op_type, from_char, to_char in operations:
            if op_type == 'transpose':
                explanation.append(f"swap '{from_char}' with '{to_char}'")
            elif op_type == 'substitute':
                explanation.append(f"change '{from_char}' to '{to_char}'")
            elif op_type == 'insert':
                explanation.append(f"insert '{to_char}'")
            elif op_type == 'delete':
                explanation.append(f"remove '{from_char}'")

        return f"{suggestion} ({', '.join(explanation)})"

# Example Usage
dictionary = [
    "their", "there", "they're", "receive",
    "believe", "achievement", "separate",
    "definitely", "occurrence", "reference"
]
spell_checker = EnhancedSpellChecker(dictionary)

test_words = [
    "thier",   # their (transposition)
    "recieve", # receive (transposition)
    "seperate" # separate (substitution)
]

for word in test_words:
    print(f"\nSuggestions for '{word}':")
    suggestions = spell_checker.suggest_corrections(word)
    for suggestion, distance, error_type, operations in suggestions:
        formatted = spell_checker._format_suggestion(word, suggestion, operations)
        print(f"  {formatted}")
        print(f"  Distance: {distance}, Type: {error_type}")

class NameMatcher:
    def __init__(self, threshold: float = 0.85):
        """
        Initialize name matcher with similarity threshold.

        Args:
            threshold: Minimum similarity score (0-1) for considering names as matches
        """
        if not 0 <= threshold <= 1:
            raise ValueError("Threshold must be between 0 and 1")
        self.threshold = threshold
        self.cache = {}  # For memoization of normalized names

    def normalize_name(self, name: str) -> str:
        """
        Normalize name for comparison by:
        - Converting to lowercase
        - Removing extra whitespace
        - Handling special characters and common substitutions

        Args:
            name: The input name to normalize

        Returns:
            Normalized name string
        """
        if name in self.cache:
            return self.cache[name]

        # Basic normalization
        normalized = ' '.join(
            part.lower().strip()
            for part in name.split()
            if part.strip()
        )

        # Cache the result
        self.cache[name] = normalized
        return normalized

    def calculate_similarity(self, name1: str, name2: str) -> tuple[float, list]:
        """
        Calculate normalized similarity between names using Damerau-Levenshtein distance.

        Args:
            name1: First name to compare
            name2: Second name to compare

        Returns:
            Tuple of (similarity_score, operations)
            - similarity_score: Float between 0 and 1
            - operations: List of operations to transform name1 into name2
        """
        name1 = self.normalize_name(name1)
        name2 = self.normalize_name(name2)

        if name1 == name2:
            return 1.0, [("match", name1, name2)]
        if not name1 or not name2:
            return 0.0, []

        # Get both distance and operations
        distance_result = damerau_levenshtein_distance(name1, name2)
        distance = distance_result[0]
        matrix = distance_result[1]

        # Get detailed operations
        operations = visualize_operations(name1, name2, matrix)

        # Calculate similarity score
        max_length = max(len(name1), len(name2))
        similarity = 1 - (distance / max_length)

        return similarity, operations

    def find_matches(self, query: str, candidates: list) -> list:
        """
        Find matching names above threshold with detailed operation information.

        Args:
            query: Name to search for
            candidates: List of candidate names to match against

        Returns:
            List of (candidate, similarity, operations) tuples, sorted by similarity
        """
        matches = []
        for candidate in candidates:
            similarity, operations = self.calculate_similarity(query, candidate)
            if similarity >= self.threshold:
                matches.append((candidate, similarity, operations))

        return sorted(matches,
                     key=lambda x: (x[1], len(x[0])),  # Sort by similarity, then by length
                     reverse=True)

    def explain_match(self, query: str, match: str, operations: list) -> str:
        """
        Generate a human-readable explanation of the match.

        Args:
            query: Original query name
            match: Matched name
            operations: List of operations from calculate_similarity

        Returns:
            String explaining the match
        """
        if not operations:
            return "Exact match"

        explanations = []
        for op_type, from_str, to_str in operations:
            if op_type == "transpose":
                explanations.append(f"swap '{from_str}' with '{to_str}'")
            elif op_type == "substitute":
                explanations.append(f"change '{from_str}' to '{to_str}'")
            elif op_type == "insert":
                explanations.append(f"insert '{to_str}'")
            elif op_type == "delete":
                explanations.append(f"remove '{from_str}'")

        return ", ".join(explanations)

# Example Usage:
# Initialize matcher
matcher = NameMatcher(threshold=0.85)

# Test database
database = [
    "John Smith",
    "Jon Smith",
    "Johnny Smith",
    "Jane Smith"
]

# Test queries with various types of errors
queries = [
    "John Smtih",  # Transposition error
    "Jon Smithh",  # Extra character
    "Jhon Smith",  # Transposition in first name
    "John Smiht"   # Transposition at end
]

for query in queries:
    print(f"\nMatches for '{query}':")
    matches = matcher.find_matches(query, database)
    for name, similarity, operations in matches:
        explanation = matcher.explain_match(query, name, operations)
        print(f"  {name:<15} ({similarity:.1%}) - {explanation}")

class DNAAnalyzer:
    def __init__(self):
        """Initialize analyzer with valid DNA bases and common mutations."""
        self.valid_bases = set('ATCG')
        # Common point mutations
        self.transition_pairs = {
            'A': 'G', 'G': 'A',  # Purine transitions
            'C': 'T', 'T': 'C'   # Pyrimidine transitions
        }
        self.transversion_pairs = {
            'A': ['C', 'T'], 'G': ['C', 'T'],
            'C': ['A', 'G'], 'T': ['A', 'G']
        }

    def validate_sequence(self, sequence: str) -> bool:
        """
        Validate DNA sequence.
        Returns False if sequence contains invalid bases.
        """
        return all(base in self.valid_bases
                  for base in sequence.upper())

    def analyze_mutations(self, seq1: str, seq2: str) -> dict:
        """
        Analyze mutations between DNA sequences using Damerau-Levenshtein distance.
        Provides detailed analysis of mutation types and their biological significance.

        Args:
            seq1: First DNA sequence
            seq2: Second DNA sequence

        Returns:
            Dictionary containing detailed mutation analysis
        """
        # Input validation
        sequences = [seq1.upper(), seq2.upper()]
        for seq in sequences:
            if not self.validate_sequence(seq):
                raise ValueError(f"Invalid DNA sequence: {seq}")

        # Get distance and operations
        distance_result = damerau_levenshtein_distance(seq1, seq2)
        distance = distance_result[0]
        matrix = distance_result[1]
        operations = visualize_operations(seq1, seq2, matrix)

        # Analyze mutations in detail
        mutations = self._categorize_mutations(operations)

        return {
            'distance': distance,
            'similarity': 1 - (distance / max(len(seq1), len(seq2))),
            'mutations': mutations,
            'operations': operations,
            'mutation_details': self._generate_mutation_details(operations),
            'biological_impact': self._assess_biological_impact(mutations)
        }

    def _categorize_mutations(self, operations: list) -> dict:
        """Categorize mutations into biological types."""
        mutations = {
            'transitions': 0,     # A↔G or C↔T mutations
            'transversions': 0,   # Other base substitutions
            'transpositions': 0,  # Base swaps
            'insertions': 0,
            'deletions': 0
        }

        for op_type, from_base, to_base in operations:
            if op_type == 'substitute':
                if to_base == self.transition_pairs.get(from_base):
                    mutations['transitions'] += 1
                else:
                    mutations['transversions'] += 1
            elif op_type == 'transpose':
                mutations['transpositions'] += 1
            elif op_type == 'insert':
                mutations['insertions'] += 1
            elif op_type == 'delete':
                mutations['deletions'] += 1

        return mutations

    def _generate_mutation_details(self, operations: list) -> list:
        """Generate detailed descriptions of each mutation."""
        details = []
        position = 0

        for op_type, from_base, to_base in operations:
            if op_type == 'substitute':
                mutation_type = 'transition' if to_base == self.transition_pairs.get(from_base) else 'transversion'
                details.append(f"Position {position}: {mutation_type} mutation {from_base}→{to_base}")
            elif op_type == 'transpose':
                details.append(f"Position {position}: transposition of {from_base}")
            elif op_type == 'insert':
                details.append(f"Position {position}: insertion of {to_base}")
            elif op_type == 'delete':
                details.append(f"Position {position}: deletion of {from_base}")

            if op_type != 'delete':
                position += 1

        return details

    def _assess_biological_impact(self, mutations: dict) -> dict:
        """Assess potential biological impact of mutations."""
        total_mutations = sum(mutations.values())

        impact = {
            'severity': 'low' if total_mutations <= 2 else 'medium' if total_mutations <= 4 else 'high',
            'notes': []
        }

        # Add relevant biological context
        if mutations['transitions'] > mutations['transversions']:
            impact['notes'].append(
                "Majority of point mutations are transitions, which are generally less disruptive"
            )
        if mutations['transpositions'] > 0:
            impact['notes'].append(
                "Contains local base swaps which may affect DNA secondary structure"
            )
        if mutations['insertions'] + mutations['deletions'] > 0:
            impact['notes'].append(
                "Contains indels which may cause frameshift mutations"
            )

        return impact

# Example Usage
analyzer = DNAAnalyzer()

# Test sequences with various mutation types
sequences = [
    ("ACGTACGT", "ACGTATCG"),  # Transposition
    ("AGCTACGT", "AGATACGT"),  # Transition (C→T)
    ("ACGTACGT", "ACATACGT"),  # Transversion (G→A)
    ("ACGTACGT", "ACGTTACGT")  # Insertion
]

for seq1, seq2 in sequences:
    print(f"\nAnalyzing sequences:")
    print(f"Sequence 1: {seq1}")
    print(f"Sequence 2: {seq2}")

    result = analyzer.analyze_mutations(seq1, seq2)

    print("\nResults:")
    print(f"Edit distance: {result['distance']}")
    print(f"Similarity: {result['similarity']:.1%}")

    print("\nMutation analysis:")
    for mutation_type, count in result['mutations'].items():
        if count > 0:
            print(f"  {mutation_type}: {count}")

    print("\nDetailed changes:")
    for detail in result['mutation_details']:
        print(f"  {detail}")

    print("\nBiological impact:")
    print(f"  Severity: {result['biological_impact']['severity']}")
    for note in result['biological_impact']['notes']:
        print(f"  Note: {note}")