基于C++的Levenshtein算法构建多字符串距离矩阵方案咨询

Great to hear you’ve already nailed the two-string Levenshtein distance implementation—half the battle is won! Here’s a straightforward, practical approach to extend that work to handle all pairwise comparisons from your text file:

Step 1: Extract All Target Strings from the File #

First, you need to parse your input text to gather all the strings into a manageable list:

• Open and read the file line by line (or in one go for small files).
• For each line, clean up the content to extract the raw string:
  • Strip off the prefix like S[n] : " and trailing " to isolate the actual string value.
  • Ignore any extra whitespace or formatting characters that aren’t part of the string itself.
• Add each cleaned string to a list (e.g., all_strings) for easy access later.

Step 2: Generate Unique String Pairs #

Since Levenshtein distance is symmetric (distance between S1 and S2 equals S2 and S1), you only need to compute each pair once. To avoid redundant work:

• Use combinations (not permutations) of the strings in your list. For N strings, this gives you N*(N-1)/2 unique pairs.
• For example, with S1, S2, S3, the pairs would be (S1,S2), (S1,S3), (S2,S3).

Step 3: Calculate Distances for Each Pair #

Loop through each unique pair and leverage your existing two-string function to get the distance:

• For every pair (str_a, str_b) in the combinations:
  • Call your pre-built levenshtein_distance(str_a, str_b) function.
  • Store or output the result along with the pair identifiers (e.g., "S1 vs S2: 5").

Pseudocode Overview #

// Step 1: Parse the input file to collect strings
all_strings = empty list
open input_file
for each line in input_file:
    // Extract the quoted string from the line
    cleaned_string = remove "S[n] : " prefix and trailing quotes from line
    add cleaned_string to all_strings
close input_file

// Step 2 & 3: Compute all unique pairwise distances
for i from 0 to length(all_strings) - 2:
    for j from i + 1 to length(all_strings) - 1:
        string1 = all_strings[i]
        string2 = all_strings[j]
        distance = levenshtein_distance(string1, string2)
        print or save "S{i+1} vs S{j+1}: {distance}"

Quick Tips #

• Edge Case Handling: Double-check that your existing Levenshtein function handles empty strings gracefully (if any exist in your input).
• Scalability: If you’re working with hundreds of strings, you might want to look into minor optimizations like precomputing common substrings, but for most use cases, the above approach will work smoothly.
• Output Options: You can print results to the console, write them to an output file, or store them in a matrix/dictionary for further analysis.

内容的提问来源于stack exchange，提问作者Ugur Ç.