匹配算法

背景

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

需求分析

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

算法选择

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

算法实现

编辑距离算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
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];
    }
}

参考

编辑距离算法