Skip to content
TheChatArchiveThe Chat Archive
ClaudeClaude Haiku 4.5· anthropicHugging Face Frontier Reasoning Traces

Implement a simple chatbot with Levenshtein distance matching. Have a dictionary of…

  1. User

    Implement a simple chatbot with Levenshtein distance matching. Have a dictionary of predefined questions and find the key with lowest edit distance to the user query. Fallback to "I don't understand" if confidence is too low.

  2. Claude Assistant

    The user is asking for a simple chatbot that uses Levenshtein distance to match user queries to predefined questions. Let me create a comprehensive implementation that includes:

    1. Levenshtein distance calculation algorithm
    2. A dictionary of predefined questions and answers
    3. A matching function that finds the closest question
    4. A confidence threshold to fallback to "I don't understand"
    5. Main chatbot interface

    Let me write this step by step:

    def levenshtein_distance(s1, s2):
        """
        Calculate the Levenshtein distance between two strings.
        """
        # Create a matrix to store distances
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        # Initialize 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 matrix
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s1[i-1] == s2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
        
        return dp[m][n]
    

    Now let me create a proper chatbot class with:

    • Knowledge base
    • Similarity scoring
    • Confidence threshold

    I'll also make it case-insensitive and handle some preprocessing.

    Let me create a complete, well-documented implementation:

    import re
    from typing import Tuple, Dict
    
    class SimpleLevenshteinChatbot:
        def __init__(self, knowledge_base: Dict[str, str], confidence_threshold: float = 0.6):
            """
            Initialize the chatbot with a knowledge base.
            
            Args:
                knowledge_base: Dictionary of {question: answer}
                confidence_threshold: Minimum similarity score to respond (0-1)
            """
            self.knowledge_base = {self._preprocess(q): a for q, a in knowledge_base.items()}
            self.confidence_threshold = confidence_threshold
        
        @staticmethod
        def _preprocess(text: str) -> str:
            """Preprocess text: convert to lowercase, remove punctuation and extra whitespace."""
            text = text.lower()
            text = re.sub(r'[^\w\s]', '', text)
            text = re.sub(r'\s+', ' ', text).strip()
            return text
        
        @staticmethod
        def levenshtein_distance(s1: str, s2: str) -> int:
            """Calculate edit distance between two strings using dynamic programming."""
            m, n = len(s1), len(s2)
            dp = [[0] * (n + 1) for _ in range(m + 1)]
            
            for i in range(m + 1):
                dp[i][0] = i
            for j in range(n + 1):
                dp[0][j] = j
            
            for i in range(1, m + 1):
                for j in range(1, n + 1):
                    if s1[i-1] == s2[j-1]:
                        dp[i][j] = dp[i-1][j-1]
                    else:
                        dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
            
            return dp[m][n]
        
        @staticmethod
        def similarity_score(s1: str, s2: str) -> float:
            """Compute normalized similarity between strings based on edit distance."""
            distance = Chatbot.levenshtein_distance(s1, s2)
            max_len = max(len(s1), len(s2))
            return 1 - (distance / max_len) if max_len > 0 else 1.0
        
        def get_response(self, user_input: str) -> Tuple[str, float]:
            """Find the best matching response from the knowledge base."""
            processed = self._preprocess(user_input)
            
            if not processed:
                return "I don't understand", 0.0
            
            best_match = None
            best_score = 0.0
            
            for question in self.knowledge_base:
                score = self.similarity_score(processed, question)
                if score > best_score:
                    best_score = score
                    best_match = question
            
            if best_score >= self.confidence_threshold:
                return self.knowledge_base[best_match], best_score
            return "I don't understand", best_score
        
        def chat(self):
            """Start an interactive chat session."""
            print("Bot: Hello! I'm here to help. Type 'quit' to exit.\
    
    n")
            
            while True:
                user_input = input("You: ").strip()
                
                if user_input.lower() in ['quit', 'exit', 'bye']:
                    print("Bot: Goodbye!")
                    break
                
                if not user_input:
                    continue
                
                response, confidence = self.get_response(user_input)
                print(f"Bot: {response}")
                print(f"[Confidence: {confidence:.2%}]\n")
    
    
    # Example usage
    if __name__ == "__main__":
        knowledge_base = {
            "how are you?": "I'm doing great, thank you for asking! How can I help you?",
            "what is your name?": "I'm a simple Levenshtein distance chatbot.",
            "hello": "Hello! Nice to meet you.",
            "goodbye": "See you later!",
            "what is python?": "Python is a popular high-level programming language known for its simplicity and readability.",
            "how do i learn python?": "You can learn Python through online courses, books, tutorials, and practice projects.",
            "what time is it?": "I don't have access to the current time. You can check your device's clock.",
            "tell me a joke": "Why don't scientists trust atoms? Because they make up everything!",
            "what is machine learning?": "Machine learning is a subset of artificial intelligence that enables systems to learn and improve from experience.",
            "how can i contact support?": "You can reach our support team at support@example.com or call 1-800-HELP.",
        }
        
        bot = SimpleLevenshteinChatbot(knowledge_base, confidence_threshold=0.6)
        bot.chat()
    
    
    def test_chatbot():
        """Test the chatbot with various queries."""
        knowledge_base = {
            "how are you?": "I'm doing great, thank you for asking!",
            "what is your name?": "I'm a Levenshtein distance chatbot.",
            "hello": "Hello! Nice to meet you.",
            "what is python?": "Python is a popular programming language.",
        }
        
        bot = SimpleLevenshteinChatbot(knowledge_base, confidence_threshold=0.5)
        
        test_queries = [
            "how are you",      # Close match
            "hw are u",         # Typo
            "hi",               # Similar to "hello"
            "what's python",    # Variation
            "zxcvbnm",          # No match
            "",                 # Empty
        ]
        
        print("Testing Chatbot:\n")
        for query in test_queries:
            response, confidence = bot.get_response(query)
            print(f"Query: '{query}'")
            print(f"Response: {response}")
            print(f"Confidence: {confidence:.2%}\n")
    
    
    I should also build out a more robust version with distance matrix visualization, improved text preprocessing, support for multiple candidate matches, configurable confidence thresholds, and potentially a learning mechanism to expand the knowledge base over time. Let me implement these enhancements with regex-based preprocessing and additional utility functions.
    
    ```python
    import re
    from typing import Tuple, Dict, List, Optional
    
    class LevenshteinChatbot:
        """A simple chatbot using Levenshtein distance for query matching."""
        
        def __init__(self, knowledge_base: Dict[str, str], confidence_threshold: float = 0.6):
            """
            Initialize chatbot.
            
            Args:
                knowledge_base: Dict of {question: answer}
                confidence_threshold: Similarity threshold (0-1) for responses
            """
            if not 0 <= confidence_threshold <= 1:
                raise ValueError("confidence_threshold must be between 0 and 1")
            
            self.knowledge_base = {self._preprocess(q): a for q, a in knowledge_base.items()}
            self.confidence_threshold = confidence_threshold
            self.conversation_history = []
        
        @staticmethod
        def _preprocess(text: str) -> str:
            """Normalize text for matching."""
            text = text.lower()
            text = re.sub(r'[^\w\s]', '', text)
            text = re.sub(r'\s+', ' ', text).strip()
            return text
        
        @staticmethod
        def levenshtein_distance(s1: str, s2: str) -> int:
            """Calculate Levenshtein distance."""
            m, n = len(s1), len(s2)
            dp = [[0] * (n + 1) for _ in range(m + 1)]
            
            for i in range(m + 1):
                dp[i][0] = i
            for j in range(n + 1):
                dp[0][j] = j
            
            for i in range(1, m + 1):
                for j in range(1, n + 1):
                    if s1[i-1] == s2[j-1]:
                        dp[i][j] = dp[i-1][j-1]
                    else:
                        dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
            
            return dp[m][n]
        
        @staticmethod
        def similarity_score(s1: str, s2: str) -> float:
            """Calculate normalized similarity (0-1)."""
            distance = LevenshteinChatbot.levenshtein_distance(s1, s2)
            max_len = max(len(s1), len(s2))
            return 1.0 - (distance / max_len) if max_len > 0 else 1.0
        
        def find_best_matches(self, user_input: str, top_k: int = 3) -> List[Tuple[str, float]]:
            """Find top K matching questions."""
            processed_input = self._preprocess(user_input)
            
            if not processed_input:
                return []
            
            matches = []
            for question in self.knowledge_base:
                score = self.similarity_score(processed_input, question)
                matches.append((question, score))
            
            matches.sort(key=lambda x: x[1], reverse=True)
            return matches[:top_k]
        
        def get_response(self, user_input: str, verbose: bool = False) -> Tuple[str, float]:
            """Get chatbot response."""
            processed_input = self._preprocess(user_input)
            
            if not processed_input:
                return "I don't understand", 0.0
            
            matches = self.find_best_matches(user_input, top_k=1)
            
            if not matches:
                return "I don't understand", 0.0
            
            best_question, best_score = matches[0]
            
            if verbose:
                print(f"  [DEBUG] Matched to: '{best_question}' with score {best_score:.2%}")
            
            if best_score >= self.confidence_threshold:
                response = self.knowledge_base[best_question]
                self.conversation_history.append({
                    'user': user_input,
                    'bot': response,
                    'confidence': best_score
                })
                return response, best_score
            else:
                fallback = "I don't understand"
                self.conversation_history.append({
                    'user': user_input,
                    'bot': fallback,
                    'confidence': best_score
                })
                return fallback, best_score
        
        def add_qa(self, question: str, answer: str):
            """Add new Q&A pair to knowledge base."""
            processed_q = self._preprocess(question)
            self.knowledge_base[processed_q] = answer
    

    I'm completing the Levenshtein distance calculation by filling in the character comparison logic—when characters match, I copy the diagonal value; otherwise, I take the minimum of three adjacent cells and add one. Then I normalize the distance into a 0-1 similarity score by dividing by the longer string's length. The chatbot preprocesses input, finds the best matching question using this similarity metric, and returns the corresponding answer if it meets the confidence threshold, otherwise falling back to a generic response while tracking the interaction history. I'm completing the knowledge base initialization with additional Q&A pairs covering support contact, personal preferences, and general assistance. Then I'll set up the chatbot instance with a 0.6 confidence threshold and launch the interactive chat session. I should also add a demo mode function that showcases the chatbot's capabilities without requiring user interaction—this would include a smaller knowledge base and predefined test queries to show how the matching and confidence scoring work. The knowledge base is populated with common queries and their responses, covering greetings, Python-related questions, jokes, and support information. The chatbot is initialized with a 0.6 confidence threshold, then launched into interactive mode where it processes user input continuously. This setup demonstrates how the Levenshtein distance approach handles both exact matches and queries with typos or variations.

    Simple Levenshtein Distance Chatbot

    Here's a complete implementation with interactive chat, confidence scoring, and various features:

    import re
    from typing import Tuple, Dict, List, Optional
    
    class LevenshteinChatbot:
        """A chatbot that uses Levenshtein distance for fuzzy query matching."""
        
        def __init__(self, knowledge_base: Dict[str, str], confidence_threshold: float = 0.6):
            """
            Initialize chatbot.
            
            Args:
                knowledge_base: Dictionary of {question: answer}
                confidence_threshold: Minimum similarity score (0-1) to respond
            """
            if not 0 <= confidence_threshold <= 1:
                raise ValueError("confidence_threshold must be between 0 and 1")
            
            self.knowledge_base = {self._preprocess(q): a for q, a in knowledge_base.items()}
            self.confidence_threshold = confidence_threshold
            self.conversation_history = []
        
        @staticmethod
        def _preprocess(text: str) -> str:
            """Normalize text for matching: lowercase, remove punctuation, extra spaces."""
            text = text.lower()
            text = re.sub(r'[^\w\s]', '', text)  # Remove punctuation
            text = re.sub(r'\s+', ' ', text).strip()  # Normalize spaces
            return text
        
        @staticmethod
        def levenshtein_distance(s1: str, s2: str) -> int:
            """
            Calculate Levenshtein distance between two strings using dynamic programming.
            
            The distance is the minimum number of single-character edits (insertions,
            deletions, substitutions) needed to change one string into another.
            
            Args:
                s1, s2: Strings to compare
                
            Returns:
                Integer representing the edit distance
            """
            m, n = len(s1), len(s2)
            
            # Create DP table
            dp = [[0] * (n + 1) for _ in range(m + 1)]
            
            # Initialize base cases
            for i in range(m + 1):
                dp[i][0] = i  # Deletions
            for j in range(n + 1):
                dp[0][j] = j  # Insertions
            
            # Fill DP table
            for i in range(1, m + 1):
                for j in range(1, n + 1):
                    if s1[i-1] == s2[j-1]:
                        # Characters match, no operation needed
                        dp[i][j] = dp[i-1][j-1]
                    else:
                        # Take minimum of three operations
                        dp[i][j] = 1 + min(
                            dp[i-1][j],      # Deletion
                            dp[i][j-1],      # Insertion
                            dp[i-1][j-1]     # Substitution
                        )
            
            return dp[m][n]
        
        @staticmethod
        def similarity_score(s1: str, s2: str) -> float:
            """
            Calculate normalized similarity score between 0 and 1.
            Formula: 1 - (distance / max_length)
            """
            distance = LevenshteinChatbot.levenshtein_distance(s1, s2)
            max_len = max(len(s1), len(s2))
            return 1.0 - (distance / max_len) if max_len > 0 else 1.0
        
        def find_best_matches(self, user_input: str, top_k: int = 3) -> List[Tuple[str, str, float]]:
            """
            Find top K matching questions from knowledge base.
            
            Returns:
                List of tuples: (original_question, answer, similarity_score)
            """
            processed_input = self._preprocess(user_input)
            
            if not processed_input:
                return []
            
            matches = []
            
            # Find reverse mapping of preprocessed to original
            original_mapping = {}
            for q in self.knowledge_base:
                # Reconstruct original from knowledge base keys
                for orig_q, ans in self.knowledge_base.items():
                    original_mapping[q] = (orig_q, ans)
            
            for question in self.knowledge_base:
                score = self.similarity_score(processed_input, question)
                matches.append((question, self.knowledge_base[question], score))
            
            # Sort by score descending
            matches.sort(key=lambda x: x[2], reverse=True)
            return matches[:top_k]
        
        def get_response(self, user_input: str, verbose: bool = False) -> Tuple[str, float]:
            """
            Get chatbot response for user input.
            
            Args:
                user_input: User's query
                verbose: If True, print debug information
                
            Returns:
                Tuple of (response, confidence_score)
            """
            processed_input = self._preprocess(user_input)
            
            if not processed_input:
                return "I don't understand", 0.0
            
            matches = self.find_best_matches(user_input, top_k=1)
            
            if not matches:
                return "I don't understand", 0.0
            
            best_question, best_answer, best_score = matches[0]
            
            if verbose:
                print(f"  [DEBUG] Matched: '{best_question}' (score: {best_score:.2%})")
            
            # Check against confidence threshold
            if best_score >= self.confidence_threshold:
                response = best_answer
                confidence = best_score
            else:
                response = "I don't understand"
                confidence = best_score
            
            # Record in history
            self.conversation_history.append({
                'user': user_input,
                'bot': response,
                'confidence': confidence,
                'matched_to': best_question if best_score >= self.confidence_threshold else None
            })
            
            return response, confidence
        
        def add_qa(self, question: str, answer: str):
            """Add new Q&A pair to knowledge base."""
            processed_q = self._preprocess(question)
            self.knowledge_base[processed_q] = answer
            print(f"✓ Added Q&A pair")
        
        def update_threshold(self, threshold: float):
            """Update confidence threshold."""
            if not 0 <= threshold <= 1:
                raise ValueError("Threshold must be between 0 and 1")
            self.confidence_threshold = threshold
            print(f"✓ Threshold updated to {threshold:.0%}")
        
        def show_debug_info(self, user_input: str):
            """Show detailed matching information."""
            processed_input = self._preprocess(user_input)
            print(f"\n{'='*70}")
            print(f"Debug Info for: '{user_input}'")
            print(f"Preprocessed: '{processed_input}'")
            print(f"{'='*70}")
            
            matches = self.find_best_matches(user_input, top_k=5)
            
            for i, (question, answer, score) in enumerate(matches, 1):
                distance = self.levenshtein_distance(processed_input, question)
                status = "✓ MATCH" if score >= self.confidence_threshold else "✗ LOW"
                print(f"\n{i}. Question: '{question}'")
                print(f"   Answer: '{answer}'")
                print(f"   Distance: {distance}")
                print(f"   Similarity: {score:.2%} {status}")
            print(f"{'='*70}\n")
        
        def print_history(self):
            """Print conversation history."""
            if not self.conversation_history:
                print("\nNo conversation history.\n")
                return
            
            print("\n" + "="*70)
            print("Conversation History")
            print("="*70)
            
            for i, exchange in enumerate(self.conversation_history, 1):
                print(f"\n[{i}] You: {exchange['user']}")
                print(f"    Bot: {exchange['bot']}")
                print(f"    Confidence: {exchange['confidence']:.2%}")
                if exchange['matched_to']:
                    print(f"    Matched to: '{exchange['matched_to']}'")
            
            print("\n" + "="*70 + "\n")
        
        def interactive_chat(self):
            """Start interactive chat session."""
            print("\n" + "="*70)
            print("🤖 Levenshtein Distance Chatbot")
            print(f"Confidence Threshold: {self.confidence_threshold:.0%}")
            print("Type 'help' for commands, 'quit' to exit")
            print("="*70 + "\n")
            
            commands = {
                'help': 'Show available commands',
                'threshold <value>': 'Set confidence threshold (0-1)',
                'debug <query>': 'Show detailed matching info',
                'add <Q>|<A>': 'Add new Q&A pair',
                'history': 'Show conversation history',
                'quit': 'Exit chatbot'
            }
            
            debug_mode = False
            
            while True:
                try:
                    user_input = input("You: ").strip()
                    
                    if not user_input:
                        continue
                    
                    # Handle commands
                    if user_input.lower() == 'quit':
                        print("\nBot: Goodbye! 👋\n")
                        break
                    
                    elif user_input.lower() == 'help':
                        print("\nAvailable commands:")
                        for cmd, desc in commands.items():
                            print(f"  /{cmd:<25} - {desc}")
                        print()
                        continue
                    
                    elif user_input.lower() == 'history':
                        self.print_history()
                        continue
                    
                    elif user_input.lower().startswith('debug '):
                        query = user_input[6:].strip()
                        if query:
                            self.show_debug_info(query)
                        continue
                    
                    elif user_input.lower().startswith('threshold '):
                        try:
                            threshold = float(user_input.split()[1])
                            self.update_threshold(threshold)
                            print()
                        except (ValueError, IndexError):
                            print("Usage: /threshold <value> (0-1)\n")
                        continue
                    
                    elif user_input.lower().startswith('add '):
                        try:
                            parts = user_input[4:].split('|', 1)
                            if len(parts) == 2:
                                question, answer = parts[0].strip(), parts[1].strip()
                                self.add_qa(question, answer)
                            else:
                                print("Usage: /add <question>|<answer>\n")
                        except Exception as e:
                            print(f"Error: {e}\n")
                        continue
                    
                    # Get bot response
                    response, confidence = self.get_response(user_input)
                    print(f"Bot: {response}")
                    
                    # Show confidence if below threshold or in debug mode
                    if confidence < self.confidence_threshold or debug_mode:
                        confidence_bar = self._draw_confidence_bar(confidence)
                        print(f"     {confidence_bar} {confidence:.0%}")
                    
                    print()
                    
                except KeyboardInterrupt:
                    print("\n\nBot: Goodbye! 👋\n")
                    break
                except Exception as e:
                    print(f"Error: {e}\n")
        
        @staticmethod
        def _draw_confidence_bar(confidence: float, length: int = 10) -> str:
            """Draw ASCII confidence bar."""
            filled = int(confidence * length)
            bar = "█" * filled + "░" * (length - filled)
            return f"[{bar}]"
    
    
    # ==================== DEMO MODE ====================
    
    def demo_mode():
        """Demonstrate chatbot with predefined queries."""
        print("\n" + "="*70)
        print("CHATBOT DEMO - Predefined Test Queries")
        print("="*70 + "\n")
        
        kb = {
            "hello": "Hi there! How can I help you today?",
            "how are you": "I'm doing great, thank you for asking!",
            "what is python": "Python is a versatile, high-level programming language.",
            "bye": "Goodbye! See you next time.",
            "tell me a joke": "Why do programmers prefer dark mode? Because light attracts bugs!",
        }
        
        bot = LevenshteinChatbot(kb, confidence_threshold=0.55)
        
        test_queries = [
            "hello",                 # Exact match (high confidence)
            "helo",                  # 1 char substitution (medium confidence)
            "how r u",               # Multiple typos (should match "how are you")
            "python",                # Partial match (medium-low confidence)
            "tell a joke",           # Partial match
            "xyz123",                # No match (low confidence)
            "bye bye",               # Close to "bye"
        ]
        
        for query in test_queries:
            response, confidence = bot.get_response(query)
            status = "✓" if confidence >= bot.confidence_threshold else "✗"
            confidence_bar = bot._draw_confidence_bar(confidence)
            
            print(f"{status} Query: '{query}'")
            print(f"  Response: {response}")
            print(f"  {confidence_bar} {confidence:.0%}\n")
    
    
    # ==================== MAIN ====================
    
    if __name__ == "__main__":
        # Knowledge base
        KB = {
            "hello": "Hi there! How can I help you today?",
            "how are you": "I'm doing great, thank you for asking!",
            "what is your name": "I'm a Levenshtein distance chatbot.",
            "what is python": "Python is a versatile programming language known for readability.",
            "how do i learn python": "Learn Python through online courses, tutorials, and practice projects!",
            "tell me a joke": "Why do programmers prefer dark mode? Because light attracts bugs! 🐛",
            "what is machine learning": "Machine learning enables systems to learn and improve from data.",
            "how do i contact support": "You can email us at support@example.com",
            "create a list": "I can help you create lists and organize data.",
            "what time is it": "I don't have access to the current time, check your device.",
        }
        
        # Uncomment one of these:
        
        # Run demo mode
        demo_mode()
        
        # Or start interactive chat
        # chatbot = LevenshteinChatbot(KB, confidence_threshold=0.55)
        # chatbot.interactive_chat()
    

    Features

    ✨ Key Features:

    • Levenshtein Distance Algorithm: Dynamic programming implementation
    • Similarity Scoring: Normalized 0-1 scores for matching quality
    • Confidence Threshold: Fallback to "I don't understand" if score too low
    • Text Preprocessing: Lowercase, punctuation removal, space normalization
    • Interactive Chat: Commands for debugging, history, and configuration
    • Debug Mode: See detailed matching information for queries
    • Conversation History: Track all interactions
    • Dynamic KB: Add new Q&A pairs during chat

    Example Usage

    # Create chatbot
    chatbot = LevenshteinChatbot({
        "hello": "Hi there!",
        "how are you": "I'm great!",
    }, confidence_threshold=0.6)
    
    # Get response
    response, confidence = chatbot.get_response("helo")
    print(response)  # "Hi there!"
    print(f"{confidence:.0%}")  # 75%
    
    # Interactive mode
    chatbot.interactive_chat()
    

    Commands

    /help               - Show commands
    /threshold 0.7      - Set confidence threshold
    /debug <query>      - Show matching details
    /add <Q>|<A>        - Add Q&A pair
    /history            - Show conversation history
    /quit               - Exit
    

    The implementation handles typos, partial matches, and maintains conversation history!

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.