如何在Flutter(Dart)中实现精准的模糊搜索？

我在实现模糊搜索前做了大量调研，尝试过fuzzy和distance库但效果不佳。当前基于Levenshtein距离实现的模糊搜索排序逻辑存在问题：即使搜索词与文本匹配度达70%，其他结果仍排在前面。

当前实现代码 #

int levenshtein(String s, String t) {
  if (s == t) return 0;
  if (s.isEmpty) return t.length;
  if (t.isEmpty) return s.length;

  List<int> v0 = List<int>.filled(t.length + 1, 0);
  List<int> v1 = List<int>.filled(t.length + 1, 0);

  for (int i = 0; i < t.length + 1; i++) v0[i] = i;

  for (int i = 0; i < s.length; i++) {
    v1[0] = i + 1;

    for (int j = 0; j < t.length; j++) {
      int cost = (s[i] == t[j]) ? 0 : 1;
      v1[j + 1] = min(v1[j] + 1, min(v0[j + 1] + 1, v0[j] + cost));
    }

    for (int j = 0; j < t.length + 1; j++) {
      v0[j] = v1[j];
    }
  }

  return v1[t.length];
}

List<T> fuzzySearch<T>(
    List<T> list, String Function(T item) getProperty, String searchTerm) {
  final lowerSearchTerm = searchTerm.toLowerCase();

  // Sort by score (lower score means more similar)
  return [...list]..sort((a, b) {
      final aScore = levenshtein(getProperty(a).toLowerCase(), lowerSearchTerm);
      final bScore = levenshtein(getProperty(b).toLowerCase(), lowerSearchTerm);

      return aScore.compareTo(bScore);
    });
}

// Some example usage below

class _SomeItem {
  final String name;

  _SomeItem(this.name);
}

Future<void> main() async {
  List<_SomeItem> items = [
    _SomeItem('banana johnes'),
    _SomeItem('other random stuff'),
    _SomeItem('whatever'),
    _SomeItem('bendana'),
    _SomeItem('buonana'),
    _SomeItem('mr bean'),
    _SomeItem('dandy trout'),
    _SomeItem('don john'),
  ];

  final searchResult = fuzzySearch(items, (item) => item.name, 'banana');

  for (var element in searchResult) {
    print(element.name);
  }
}

当前运行结果 #

搜索banana时，输出结果为：

bendana
buonana
mr bean
banana johnes
whatever
don john
dandy trout
other random stuff

预期banana johnes应排在首位，请问如何优化代码以提升搜索准确性？

解决方案 #

问题核心在于原始Levenshtein距离是绝对数值，未考虑字符串长度差异。比如banana johnes长度远大于banana，计算出的绝对距离会比短字符串（如bendana）更高，导致排序靠后。以下是针对性优化方案：

优化方案1：结合子串匹配+归一化相似度 #

先优先匹配包含完整搜索词的项，再用归一化后的Levenshtein相似度排序，确保不同长度的字符串能公平比较：

// 新增：计算归一化相似度（范围0-1，1表示完全匹配）
double normalizedLevenshteinSimilarity(String s, String t) {
  int distance = levenshtein(s, t);
  int maxLength = max(s.length, t.length);
  return maxLength == 0 ? 1.0 : 1.0 - (distance / maxLength);
}

// 修改搜索排序逻辑
List<T> fuzzySearch<T>(
    List<T> list, String Function(T item) getProperty, String searchTerm) {
  final lowerSearchTerm = searchTerm.toLowerCase();

  return [...list]..sort((a, b) {
      final aStr = getProperty(a).toLowerCase();
      final bStr = getProperty(b).toLowerCase();
      
      // 优先级1：包含完整搜索词的项排前面
      final aContains = aStr.contains(lowerSearchTerm);
      final bContains = bStr.contains(lowerSearchTerm);
      if (aContains != bContains) {
        return aContains ? -1 : 1;
      }
      
      // 优先级2：用归一化相似度排序，得分高的排前面
      final aScore = normalizedLevenshteinSimilarity(aStr, lowerSearchTerm);
      final bScore = normalizedLevenshteinSimilarity(bStr, lowerSearchTerm);
      
      return bScore.compareTo(aScore);
    });
}

优化方案2：增加前缀匹配权重（可选） #

如果希望前缀完全匹配的结果优先级最高，可以在排序逻辑中加入前缀检查：

List<T> fuzzySearch<T>(
    List<T> list, String Function(T item) getProperty, String searchTerm) {
  final lowerSearchTerm = searchTerm.toLowerCase();

  return [...list]..sort((a, b) {
      final aStr = getProperty(a).toLowerCase();
      final bStr = getProperty(b).toLowerCase();
      
      // 优先级1：前缀完全匹配的项排最前
      final aStartsWith = aStr.startsWith(lowerSearchTerm);
      final bStartsWith = bStr.startsWith(lowerSearchTerm);
      if (aStartsWith != bStartsWith) {
        return aStartsWith ? -1 : 1;
      }
      
      // 优先级2：包含完整搜索词的项次之
      final aContains = aStr.contains(lowerSearchTerm);
      final bContains = bStr.contains(lowerSearchTerm);
      if (aContains != bContains) {
        return aContains ? -1 : 1;
      }
      
      // 优先级3：归一化相似度排序
      final aScore = normalizedLevenshteinSimilarity(aStr, lowerSearchTerm);
      final bScore = normalizedLevenshteinSimilarity(bStr, lowerSearchTerm);
      
      return bScore.compareTo(aScore);
    });
}

优化后运行结果 #

搜索banana时，输出会变为：

banana johnes
bendana
buonana
mr bean
whatever
don john
dandy trout
other random stuff

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