匹配算法

背景

• 在项目学习中, 有随机匹配的需求, 根据用户的标签进行匹配, 所以需要设计一个匹配算法.

需求分析

1. 找到有共同标签最多的用户（TopN）
2. 共同标签越多, 分数越高, 越排在前面
3. 如果没有匹配的用户, 则随机推荐几个用户(降级方案)

算法选择

1. 编辑距离算法(Levenshtein Distance)
   • 计算两个字符串之间的编辑距离, 即将一个字符串转换成另一个字符串所需要的最少的操作次数.
   • 编辑距离算法可以用来计算两个字符串之间的相似度, 也可以用来计算两个字符串之间的匹配度.
   • 编辑距离算法的复杂度为 O(nm), n 为两个字符串的长度, m 为字符集的大小.
2. 余弦相似度算法(Cosine Similarity)
   • 余弦相似度算法可以用来计算两个向量之间的相似度.
   • 需要带权重的标签, 如用户的标签中包含了用户的年龄, 性别等信息.
   • 余弦相似度算法的复杂度为 O(n), n 为向量的维度.

算法实现

1. 编辑距离算法

   package com.hjx.ucback.utils;
      
   import java.util.List;
   import java.util.Objects;
      
   /**
    * Description: 算法工具类
    * Author: HanGR
    * Project: uc-back
    * Date: 2024/9/21 8:49
    * Realize:
    */
   public class AlgorithmUtils {
      
       /**
        * 编辑距离算法（用于计算最相似的两组标签）
        *
        * @param tagList1       标签列表1
        * @param tagList2       标签列表2  
        * @return              编辑距离
        */
       public static int minDistance(List<String> tagList1, List<String> tagList2) {
           int n = tagList1.size();
           int m = tagList2.size();
      
           if (n * m == 0) {
               return n + m;
           }
      
           int[][] d = new int[n + 1][m + 1];
           for (int i = 0; i < n + 1; i++) {
               d[i][0] = i;
           }
      
           for (int j = 0; j < m + 1; j++) {
               d[0][j] = j;
           }
      
           for (int i = 1; i < n + 1; i++) {
               for (int j = 1; j < m + 1; j++) {
                   int left = d[i - 1][j] + 1;
                   int down = d[i][j - 1] + 1;
                   int leftDown = d[i - 1][j - 1];
                   if (!Objects.equals(tagList1.get(i - 1), tagList2.get(j - 1))) {
                       leftDown += 1;
                   }
                   d[i][j] = Math.min(left, Math.min(down, leftDown));
               }
           }
           return d[n][m];
       }
      
       /**
        * 编辑距离算法（用于计算最相似的两个字符串）
        *
        * @param word1     单词1  
        * @param word2     单词2
        * @return        编辑距离
        */
       public static int minDistance(String word1, String word2) {
           int n = word1.length();
           int m = word2.length();
      
           if (n * m == 0) {
               return n + m;
           }
      
           int[][] d = new int[n + 1][m + 1];
           for (int i = 0; i < n + 1; i++) {
               d[i][0] = i;
           }
      
           for (int j = 0; j < m + 1; j++) {
               d[0][j] = j;
           }
      
           for (int i = 1; i < n + 1; i++) {
               for (int j = 1; j < m + 1; j++) {
                   int left = d[i - 1][j] + 1;
                   int down = d[i][j - 1] + 1;
                   int leftDown = d[i - 1][j - 1];
                   if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                       leftDown += 1;
                   }
                   d[i][j] = Math.min(left, Math.min(down, leftDown));
               }
           }
           return d[n][m];
       }
   }
   

参考

• 编辑距离算法