Implement a simple chatbot with Levenshtein distance matching. Have a dictionary of…
- 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.
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:
- Levenshtein distance calculation algorithm
- A dictionary of predefined questions and answers
- A matching function that finds the closest question
- A confidence threshold to fallback to "I don't understand"
- 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] = answerI'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 - ExitThe implementation handles typos, partial matches, and maintains conversation history!
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.