代码收藏家 喜迎国庆，居家五黑，自己写个组队匹配叭
😊你好，我是小航，一个正在变秃、变强的文艺倾年。
🔔本文讲解使用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，先鸽这叭，能力有限，大家尽情发挥！
文章涉及到的代码：
最后祝大家，国庆节快乐！
