本文介绍如何使用莱文斯坦距离（levenshtein distance）实现电影数组的动态重排序，使用户输入关键词（无论是完整片名还是片段）后，匹配度最高的对象优先显示，同时支持按类型、年份等元数据扩展排序逻辑。
本文介绍如何使用莱文斯坦距离（levenshtein distance）实现电影数组的动态重排序，使用户输入关键词（无论是完整片名还是片段）后，匹配度最高的对象优先显示，同时支持按类型、年份等元数据扩展排序逻辑。
在构建搜索型前端应用（如电影库、内容平台）时，仅靠精确匹配（===）无法满足真实用户行为——用户常输入缩写（如 "MovN"）、拼写变体或部分关键词（如 "fun"），此时需引入模糊匹配驱动的排序策略。核心思路是：为每个电影对象计算其与搜索词的“相似度得分”，再依据得分升序排列（距离越小越相关）。
莱文斯坦距离是一种经典字符串编辑距离算法，定义为将一个字符串转换为另一个所需最少的单字符编辑操作数（插入、删除、替换）。距离为 0 表示完全匹配；数值越小，语义越接近。
以下是可直接集成的完整实现：
// ✅ 莱文斯坦距离工具函数（经优化，时间复杂度 O(m×n)）
const levenshteinDistance = (s, t) => {
if (!s.length) return t.length;
if (!t.length) return s.length;
const dp = Array(t.length + 1).fill().map(() => Array(s.length + 1).fill(0));
for (let i = 0; i <= t.length; i++) dp[i][0] = i;
for (let j = 0; j <= s.length; j++) dp[0][j] = j;
for (let i = 1; i <= t.length; i++) {
for (let j = 1; j <= s.length; j++) {
const cost = s[j - 1] === t[i - 1] ? 0 : 1;
dp[i][j] = Math.min(
dp[i - 1][j] + 1, // 删除
dp[i][j - 1] + 1, // 插入
dp[i - 1][j - 1] + cost // 替换
);
}
}
return dp[t.length][s.length];
};
// ? 示例电影数据（键为片名，值为标签数组）
const movies = [
{ "MovNameOne": ["comedy", "fun", "2021"] },
{ "MovNameTwo": ["thriller", "suspense", "2022"] },
{ "MovNameThree": ["thriller", "comedy", "2021"] },
{ "MovNameFour": ["action", "mixed", "2000"] },
{ "MovNameFive": ["fun", "mixed", "2021"] }
];
// ? 搜索排序函数：接收用户输入，返回按匹配度升序排列的新数组
const sortMoviesBySearch = (query) => {
return [...movies].sort((a, b) => {
const keyA = Object.keys(a)[0];
const keyB = Object.keys(b)[0];
const distA = levenshteinDistance(query, keyA);
const distB = levenshteinDistance(query, keyB);
return distA - distB; // 升序：距离小者在前
});
};
// ✅ 使用示例
console.log(sortMoviesBySearch("MovNameF")); // ["MovNameFour", "MovNameFive", ...]
console.log(sortMoviesBySearch("fun")); // 匹配含 "fun" 的片名及标签（见下文扩展）⚠️ 重要注意事项：
- 当前实现仅对电影名称（Object.keys） 进行模糊匹配。若需支持按类型（如 "comedy"）、年份（如 "2021"）等标签搜索，应扩展评分逻辑：例如对每个对象遍历其所有标签，取最小距离作为该对象综合得分，再参与排序；
- 性能敏感场景（如 >1000 条数据）建议预计算索引或改用更高效的近似算法（如 fuse.js）；
- 对中文支持较弱（依赖字面字符比对），如需中文分词匹配，应先接入 jieba 或 segmentit 等分词库；
- sort() 会原地修改数组，务必使用 [...movies] 创建副本，避免副作用。
✅ 进阶建议： 可叠加多级权重排序——例如：名称匹配距离占 60% 权重，类型标签匹配占 30%，年份接近度占 10%，实现更自然的搜索体验。
通过本方案，你已掌握一种工业级可用的模糊搜索排序范式：它不依赖外部库、逻辑透明、易于调试与定制，是构建智能内容发现功能的坚实基础。
