Stream Deduplication with Near-Duplicate Detection

Implement a streaming deduplicator that preserves the first occurrence of each string, then extend it to suppress near-duplicates using a similarity threshold. The core trade-off is exact O(1) set membership versus more expensive fuzzy matching over previously accepted strings. Problem Statement You have a stream of strings (text) that arrive one by one. Some strings might appear more than once. Your task is to write a program that reads these strings and removes any duplicates. You should only keep the first time a string appears. Input: A stream of strings separated by commas. Output: A stream of strings with duplicates removed, separated by commas. Example: Input: "apple,banana,apple,orange,banana" Output: "apple,banana,orange" Requirements: Strings are case-sensitive (e.g., "Apple" is different from "apple"). You must process the strings one at a time. Part 1: Removing Exact Duplicates Solution Approach We can use a HashSet to keep track of the strings we have already seen. This allows us to check if a string is a duplicate very quickly. Algorithm: Create an empty HashSet called seen. Look at each string coming from the stream: Check if the string is already in the seen set. If it is not in the set, add it to seen and return the string. If it is in the set, ignore it and move to the next one. Code Implementation from typing import Iterator, Set def deduplicate_stream(stream: Iterator[str]) -> Iterator[str]: """ Remove duplicate strings from a stream. Keep only the first time a string appears. Args: stream: An iterator that yields strings Yields: Unique strings in the order they first appear """ seen: Set[str] = set() for item in stream: if item not in seen: seen.add(item) yield item def deduplicate_csv_stream(csv_stream: str) -> str: """ Helper function for comma-separated string streams. Args: csv_stream: A string of items separated by commas Returns: A comma-separated string with duplicates removed """ items = (item.strip() for item in csv_stream.split(',')) return ','.join(deduplicate_stream(items)) Usage Example # Basic deduplication input_stream = "apple,banana,apple,orange,banana" output = deduplicate_csv_stream(input_stream) print(output) # Output: "apple,banana,orange" Part 2: Removing Near-Duplicates Problem Requirements Now, we need to remove strings that are "near-duplicates." A string is a near-duplicate if it is almost the same as a previous string. Two strings are considered near-duplicates if: They only differ by punctuation. They have different capitalization (uppercase vs lowercase). Their Edit Distance is very low (below a specific limit). Example: Input: "apple,aple,apple,orange,orang" Threshold: Edit distance ≤ 1 Output: "apple,orange" Technical Detail: We check similarity using the Edit Distance (how many changes it takes to turn one string into another). Solution Approach To find near-duplicates: Compare the new string with every string we have already kept. Calculate the Edit Distance between the new string and the saved strings. If the distance is small (less than or equal to the threshold), we skip the new string. If the distance is large, we save the new string and return it. Code Implementation from typing import Iterator, List import re def levenshtein_distance(s1: str, s2: str) -> int: """ Calculate the Levenshtein (edit) distance between two strings. Uses dynamic programming. Time: O(m * n), Space: O(min(m, n)) """ if len(s1) < len(s2): s1, s2 = s2, s1 # Use only two rows for space optimization previous_row = range(len(s2) + 1) for i, c1 in enumerate(s1): current_row = [i + 1] for j, c2 in enumerate(s2): # Cost of insertions, deletions, or substitutions insertions = previous_row[j + 1] + 1 deletions = current_row[j] + 1 substitutions = previous_row[j] + (c1 != c2) current_row.append(min(insertions, deletions, substitutions)) previous_row = current_row return previous_row[-1] def normalize_string(s: str, remove_punctuation: bool = True, lowercase: bool = True) -> str: """ Clean up a string to make comparison easier. Args: s: Input string remove_punctuation: If True, remove punctuation marks lowercase: If True, convert to lowercase Returns: The cleaned (normalized) string """ result = s if lowercase: result = result.lower() if remove_punctuation: # Remove common punctuation result = re.sub(r'[^\w\s]', '', result) # Remove extra whitespace result = ' '.join(result.split()) return result def deduplicate_near_duplicates( stream: Iterator[str], threshold: int = 1, normalize: bool = True ) -> Iterator[str]: """ Remove near-duplicate strings using edit distance. Args: stream: An iterator yielding strings threshold: The max edit distance to count as a duplicate normalize: Whether to clean strings (lowercase, remove punctuation) Yields: Strings that are NOT near-duplicates of previously seen strings """ seen_normalized: List[str] = [] seen_original: List[str] = [] for item in stream: # Clean the string for comparison normalized = normalize_string(item) if normalize else item # Check if it is a near-duplicate of any seen string is_duplicate = False for seen_norm in seen_normalized: distance = levenshtein_distance(normalized, seen_norm) if distance <= threshold: is_duplicate = True break if not is_duplicate: seen_normalized.append(normalized) seen_original.append(item) yield item def deduplicate_near_duplicates_csv( csv_stream: str, threshold: int = 1, normalize: bool = True ) -> str: """ Helper function for comma-separated strings with near-duplicate removal. Args: csv_stream: A string of items separated by commas threshold: Max edit distance to count as a duplicate normalize: Whether to clean strings Returns: A comma-separated string with near-duplicates removed """ items = (item.strip() for item in csv_stream.split(',')) return ','.join(deduplicate_near_duplicates(items, threshold, normalize)) Usage Example # Example 1: Near-duplicates with edit distance input_stream = "apple,aple,apple,orange,orang" output = deduplicate_near_duplicates_csv(input_stream, threshold=1) print(output) # Output: "apple,orange" # Example 2: Case and punctuation variations input_stream = "Hello,hello,HELLO!,world,World." output = deduplicate_near_duplicates_csv(input_stream, threshold=0, normalize=True) print(output) # Output: "Hello,world" # Example 3: Threshold = 2 (allows more differences) input_stream = "apple,aple,appl,applee,orange" output = deduplicate_near_duplicates_csv(input_stream, threshold=2) print(output) # Output: "apple,orange" Time and Space Complexity Exact Deduplication Time Complexity: O(n), where n is the total number of strings. Space Complexity: O(k), where k is the number of unique strings. Near-Duplicate Detection Time Complexity: O(n × k × m²). n: Total number of strings. k: Number of unique strings kept. m: The average length of a string. Space Complexity: O(k × m).