如何在JavaScript中实现数组内给定字符串的近似匹配与拼写纠错？

Great question! To solve this problem, the most reliable approach is to use the Levenshtein Distance (also known as edit distance). This metric calculates the minimum number of single-character changes (insertions, deletions, substitutions) required to turn one string into another. The smaller the distance, the more similar the two strings are.

Step 1: Implement the Levenshtein Distance Function #

First, we need a function to compute the edit distance between two strings. Here's an efficient dynamic programming implementation:

function calculateLevenshteinDistance(a, b) {
  // Create a 2D array to store distance values
  const distanceMatrix = Array(b.length + 1)
    .fill(null)
    .map(() => Array(a.length + 1).fill(null));

  // Initialize the first row and column (base cases)
  for (let i = 0; i <= a.length; i++) {
    distanceMatrix[0][i] = i;
  }
  for (let j = 0; j <= b.length; j++) {
    distanceMatrix[j][0] = j;
  }

  // Fill the matrix with calculated distances
  for (let j = 1; j <= b.length; j++) {
    for (let i = 1; i <= a.length; i++) {
      const indicator = a[i - 1] === b[j - 1] ? 0 : 1;
      distanceMatrix[j][i] = Math.min(
        distanceMatrix[j][i - 1] + 1, // Insertion
        distanceMatrix[j - 1][i] + 1, // Deletion
        distanceMatrix[j - 1][i - 1] + indicator // Substitution
      );
    }
  }

  return distanceMatrix[b.length][a.length];
}

Step 2: Build the Matching Function #

Next, we'll create a function that iterates through the target array, calculates the distance for each item, and returns the most similar one. We'll also handle edge cases like empty arrays or ties in similarity.

function findMostSimilarString(inputStr, stringArray) {
  // Handle empty array edge case
  if (stringArray.length === 0) {
    return null;
  }

  let mostSimilar = stringArray[0];
  let smallestDistance = calculateLevenshteinDistance(inputStr, mostSimilar);

  for (const str of stringArray.slice(1)) {
    const currentDistance = calculateLevenshteinDistance(inputStr, str);
    // Update if current string is more similar
    // Adjust the condition if you want different tie-breaking logic (e.g., return last match)
    if (currentDistance < smallestDistance) {
      smallestDistance = currentDistance;
      mostSimilar = str;
    }
  }

  return mostSimilar;
}

Step 3: Test the Implementation #

Let's test this with your exact example:

const input = "Pikachi";
const pokemonArray = ["Pikachu","Rawrr","Squirtle"];

const result = findMostSimilarString(input, pokemonArray);
console.log(result); // Output: "Pikachu"

Notes on Edge Cases #

• Empty input string: If your input could be empty, add a check at the start of findMostSimilarString (e.g., return the shortest string in the array, or handle it based on your specific needs).
• Tied similarity: If multiple strings have the same smallest distance, the function above returns the first match it encounters. To return all matches instead, modify the function to collect all strings with the smallest distance and return an array.

内容的提问来源于stack exchange，提问作者king