• 欢迎光临~

喜迎国庆,居家五黑,自己写个组队匹配叭

开发技术 开发技术 2022-10-11 次浏览

喜迎国庆,居家五黑,自己写个组队匹配叭

😊你好,我是小航,一个正在变秃、变强的文艺倾年。
🔔本文讲解使用Java实现组队匹配功能,欢迎大家多多关注!
🔔国庆节到了,一起卷起来叭!

前言:

在排位上分中,或者在日常做项目中,常常会有找队友的需求。于是借国庆休息,写一篇组队匹配的文章叭,大佬勿喷!

一、数据库设计:

create database match_demo;

use match_demo;

CREATE TABLE `user_info` (
  `id` bigint NOT NULL AUTO_INCREMENT COMMENT '主键ID',
  `user_name` varchar(50) DEFAULT NULL COMMENT '用户名',
  `sex` tinyint DEFAULT NULL COMMENT '性别',
  `age` int DEFAULT NULL COMMENT '年龄',
  `tags` varchar(255) DEFAULT NULL COMMENT '标签',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;

二、初始化项目:

项目目录:
喜迎国庆,居家五黑,自己写个组队匹配叭
我们首先构建几条假数据:

喜迎国庆,居家五黑,自己写个组队匹配叭
新建一个接口:

@RestController
public class ApiController {

    @Autowired
    DemoService demoService;

    @PostMapping("/match")
    public Result<List<DemoEntity>> matchUser(@RequestBody List<String> tags) {
        List<DemoEntity> demoEntities = demoService.matchUserByTags(tags);
        return new Result<List<DemoEntity>>().ok(demoEntities);
    }
}

测试打印:

package com.example.demo.service.impl;

import com.baomidou.mybatisplus.extension.service.impl.ServiceImpl;
import com.example.demo.dao.DemoDao;
import com.example.demo.entity.DemoEntity;
import com.example.demo.service.DemoService;
import org.springframework.stereotype.Service;
import org.springframework.util.StringUtils;

import java.util.List;

/**
 * @author artboy
 */
@Service
public class DemoServiceImpl extends ServiceImpl<DemoDao, DemoEntity> implements DemoService {

    @Override
    public List<DemoEntity> matchUserByTags(List<String> tags) {
        List<DemoEntity> demoEntities = baseMapper.selectList(null);
        System.out.println(demoEntities);
        return demoEntities ;
    }
}

测试效果:
喜迎国庆,居家五黑,自己写个组队匹配叭

三、标签匹配:

首先我们引入最小编辑距离算法工具类:

最短编辑距离(Minimum Edit Distance),也被称为Levenshtein距离,是一种计算两个字符串间的差异程度的字符串度量(string metric)。我们可以认为Levenshtein距离就是从一个字符串修改到另一个字符串时,其中编辑单个字符(比如修改、插入、删除)所需要的最少次数。
我们试图找到“从字符串AA修改到字符串BB”这一问题的子解结构。当然反过来说“从字符串BB修改到字符串AA”和它是同一个问题,因为从AA中删掉一个字符来匹配BB,就相当于在BB中插入一个字符来匹配AA,这两个操作是可以互相转化的。
假设字符序列A[1…i]A[1…i]、B[1…j]B[1…j]分别是字符串AA、BB的前ii、jj个字符构成的子串,我们得到一个子问题是“从字符串A[1…i]A[1…i]修改到字符串B[1…j]B[1…j]”:出了这一概念。

具体实现大家可以参考文章:最短编辑距离的原理解释
我们这里的做法即是:计算待匹配串数组和某一用户的标签字符串数组的相近距离(只不过这里距离只有0和1)

我们先以字符串为例:

package com.example.demo.utils;

public class MinimumEditDistance {
    public static void main(String[] args) {
        //字符串word1和word2分别是要进行对比的两个字符串
        String word1 = "Java";
        String word2 = "javase";
        //在本类中调用本类的静态方法minimumEditDistance(...)故不需在方法前加类名或创建类对象
        //输出字符串word1和word2互相转换的最小编辑距离
        System.out.println(minimumEditDistance(word1, word2));
    }

    //注意此方法是静态方法,这样在本类的main方法中可直接用本方法名调用本方法,而不需要创建对象再调用此方法
    //本方法的形式参数word1和word2分别是要进行对比的两个字符串,最后返回的是int型的两个字符串互相转换的最小编辑距离
    public static int minimumEditDistance(String word1, String word2) {
        //新建一个二维数组,用于存取两字符串的各个子字符串之间的最短编辑距离
        //其中新建的二维数组的行列都+1是因为最短编辑距离的矩阵的子字符串从空串""开始,把空串""考虑进去,因此行列都+1
        int[][] minMatrix = new int[word1.length() + 1][word2.length() + 1];
        //minMatrix[i][j]表示:字符串word1的第0到第i-1个字符构成的子字符串 与 字符串word2的第0到第j-1个字符构成的子字符串 互相转换的最小编辑距离
        //例如word1="legend"而word2="laland",那么minMatrix[2][3]的结果是2,其表示 字符串word1的第0到第1个字符构成的子字符串"le" 与 字符串word2的第0到第2个字符构成的子字符串"lal" 互相转换的最小编辑距离为2

        //当word2的子字符串是空串""时,而当word1的子字符串分别是:空串""、第0个字符、第0到第1个字符、第0到第2个字符...第0到第i-1个字符构成的子字符串时,
        //minMatrix[i][0]表示该两个子字符串互相转换的最小编辑距离
        for (int i = 0; i < word1.length(); i++) {
            minMatrix[i][0] = i;
        }
        //当word1的子字符串是空串""时,而当word2的子字符串分别是:空串""、第0个字符、第0到第1个字符、第0到第2个字符...第0到第j-1个字符构成的子字符串时,
        //minMatrix[0][j]表示该两个子字符串互相转换的最小编辑距离
        for (int j = 0; j < word2.length(); j++) {
            minMatrix[0][j] = j;
        }
        //建一个二层循环嵌套,分别比较并计算word1和word2的子字符串都不是空串""时互相转换的最小编辑距离
        for (int i = 1; i < word1.length() + 1; i++) {
            for (int j = 1; j < word2.length() + 1; j++) {
                //word1.charAt(i-1)方法指字符串word1的第i个字符,而第i个字符的数组下标是i-1
                //若某两个子字符串的最后一个字符相同,那么此时此两个子字符串的最短编辑距离等价于:没有最后一个相同字符的两个子字符串互相转换的最短编辑距离
                //例如"lalan"和"legen"的最后一个字符都是"n",则 "lalan"和"legen"的最小编辑距离 等于 "lala"和"lege"的最小编辑距离
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    minMatrix[i][j] = minMatrix[i - 1][j - 1];
                }
                //若某两个子字符串的最后一个字符不相同,那么此时此两个子字符串的最短编辑距离等价于:minMatrix[i-1][j]和minMatrix[i][j-1]和minMatrix[i-1][j-1]之间的最小值,再+1
                //最后+1是因为最后一个字符不相同。若是minMatrix[i-1][j-1]+1,则是某两个子字符串的最后两个不同字符进行1次替换字符操作,从而让该两字符相同;
                //若是minMatrix[i-1][j]+1或minMatrix[i][j-1]+1,则是某两个子字符串的两个不同字符进行1次插入/删除字符操作;
                else {
                    minMatrix[i][j] = (Math.min((Math.min(minMatrix[i - 1][j], minMatrix[i][j - 1])), minMatrix[i - 1][j - 1])) + 1;
                }
            }
        }

        //最后返回的是int型的两个字符串互相转换的最小编辑距离,该值是行列分别是word1和word2的长度的二维数组minMatrix的元素值
        return minMatrix[word1.length()][word2.length()];
    }
}

为了符合真实场景,我们对单词忽略大小写:

package com.example.demo.utils;

public class MinimumEditDistance {
    public static void main(String[] args) {
        String word1 = "Java";
        String word2 = "javase";
        System.out.println(minimumEditDistance(word1, word2));
    }

    public static int minimumEditDistance(String word1, String word2) {
        word1 = word1.toLowerCase();
        word2 = word2.toLowerCase();
       .....
    }
}

输出结果:

2

将字符串匹配更换为字符串数组匹配:(注意这里要以待匹配的标签为准)

public static void main(String[] args) {
        List<String> tags1 = Arrays.asList("Java", "Python");
        List<String> tags2 = Arrays.asList("Java", "Python");
        System.out.println(minimumEditDistance(tags1, tags2));
    }

    /**
     * @param tags1 待匹配标签
     * @param tags2 标签库
     */
    public static int minimumEditDistance(List<String> tags1, List<String> tags2) {
        int len1 = tags1.size();
        int len2 = Math.min(tags1.size(), tags2.size());
        int[][] minMatrix = new int[len1 + 1][len2 + 1];

        for (int i = 0; i < len1; i++) {
            minMatrix[i][0] = i;
        }
        for (int j = 0; j < len2; j++) {
            minMatrix[0][j] = j;
        }
        for (int i = 1; i < len1 + 1; i++) {
            for (int j = 1; j < len2 + 1; j++) {
                if (tags1.get(i - 1).equalsIgnoreCase(tags2.get(j - 1))) {
                    minMatrix[i][j] = minMatrix[i - 1][j - 1];
                }
                else {
                    minMatrix[i][j] = (Math.min((Math.min(minMatrix[i - 1][j], minMatrix[i][j - 1])), minMatrix[i - 1][j - 1])) + 1;
                }
            }
        }
        return minMatrix[len1][len2];
    }

运行结果:

0

注意这里我们匹配的是下标已经一一对应好的字符串数组
["Java", "Python"] 与 ["Python", "Java"]这样是不行的,原因其实也很好理解,ab字符串与ba字符串最小编辑距离为2,而不是0,由于标签具有唯一性,我们只需要对字符串数组按字典排序即可。

喜迎国庆,居家五黑,自己写个组队匹配叭
所以我们将字符串数组进行预处理排序:(可以导入标签的时候进行这一步)

public static void main(String[] args) {
        List<String> tags1 = Arrays.asList("Java", "Python");
        List<String> tags2 = Arrays.asList("Python", "Java");
        tags1.sort(String::compareTo);
        tags2.sort(String::compareTo);
        System.out.println("[Java, Python]与[Python, Java]的最小编辑距离:" + minimumEditDistance(tags1, tags2));
    }

测试结果:

[Java, Python]与[Python, Java]的最小编辑距离:0

编写业务层:DemoServiceImpl

@Override
    public List<DemoEntity> matchUserByTags(List<String> tags) {
        List<DemoEntity> demoEntities = baseMapper.selectList(null);
        Gson gson = new Gson();
        // <用户列表下标, 相似度>
        HashMap<Integer, Integer> indexDistanceMap = new HashMap<>();
        for (int i = 0; i < demoEntities.size(); i ++) {
            DemoEntity demoEntity = demoEntities.get(i);
            String tags1 = demoEntity.getTags();
            // 无标签
            if (StringUtils.isEmpty(tags1)) {
                continue;
            }
            List<String> userTag = gson.fromJson(tags1, new TypeToken<List<String>>() {
            }.getType());
            // 字符串数组预处理
            tags.sort(String::compareTo);
            userTag.sort(String::compareTo);
            // 计算最小编辑距离得分
            Integer score = MinimumEditDistance.minimumEditDistance(tags, userTag);
            indexDistanceMap.put(i, score);
        }
        // 对相似度进行升序排序
        //利用Map的entrySet方法,转化为list进行排序
        List<Map.Entry<Integer, Integer>> entryList = new ArrayList<>(indexDistanceMap.entrySet());
        //利用Collections的sort方法对list排序
        entryList.sort(Comparator.comparingInt(Map.Entry::getValue));
        List<DemoEntity> collect = entryList.stream().limit(5).map(
                entry -> demoEntities.get(entry.getKey())
        ).collect(Collectors.toList());
        return collect;
    }

测试:
修改数据库用例:
喜迎国庆,居家五黑,自己写个组队匹配叭

请求JSON:["java"]

返回结果:
{
    "code": 0,
    "msg": "success",
    "data": [
        {
            "id": 2,
            "userName": "b",
            "sex": "1",
            "age": 28,
            "tags": "["Java"]"
        },
        {
            "id": 3,
            "userName": "c",
            "sex": "1",
            "age": 45,
            "tags": "["Java","Python"]"
        },
        {
            "id": 1,
            "userName": "a",
            "sex": "1",
            "age": 16,
            "tags": "["Python"]"
        }
    ]
}

可能还是有很多很多bug,先鸽这叭,能力有限,大家尽情发挥!

文章涉及到的代码:

代码链接

最后祝大家,国庆节快乐!

喜迎国庆,居家五黑,自己写个组队匹配叭

程序员灯塔
转载请注明原文链接:喜迎国庆,居家五黑,自己写个组队匹配叭
喜欢 (0)