该项目的算法思路取自https://blog.csdn.net/DBC_121/article/details/104198838 该算法的思路是将一个字符串转换为另一个字符串所需要操作次数就是编辑距离
更通俗的理解，假设我们可以使用d[ i , j ]个步骤（可以使用一个二维数组保存这个值，使用动态规划的思想），表示将串s[ 1…i ] 转换为串t [ 1…j ]所需要的最少步骤个数，那么，在最基本的情况下，即在 i 等于 0 时，也就是说串 s 为空，那么对应的d[ 0 , j ] 就是 增加 j 个字符，使得 s 转化为 t，在 j 等于 0 时，也就是说串 t 为空，那么对应的 d[ i, 0] 就是 减少 i 个字符，使得 s 转化为 t。
首先，我们定义一个二维数组 D，其中 D[i][j] 表示将word1的前 i 个字符转换为 word2 的前 j个字符所需要的操作次数
- 如果
word1为空字符串（即i=0），则将其转换为word2需要插入word2的所有字符，所以D[0][j] = j。 - 如果
word2为空字符串（即j=0），则将其转换为word1需要删除word1的所有字符，所以D[i][0] = i。
得到一个初始填充的数组 D
// 初始化第一行和第一列
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j;
}
D = [
[0, 1, 2, 3],
[1, 0, 0, 0],
[2, 0, 0, 0],
[3, 0, 0, 0],
[4, 0, 0, 0],
[5, 0, 0, 0]
]-
假设我们的word 是
String A = "horse";String B = "ros";那么D 最后的结果 则为外层为A.length的长度5内层为B,length的长度3的矩阵 如下图r o s +----------------- | 0 1 2 3 h | 1 1 2 3 o | 2 r | 3 s | 4 e | 5
-
因为该算法是在每一次字符 操作中想要得到增 删 或者 替换操作 次数最少的那一次 也就是 表示将串A[ 1…i ] 转换为串**B [ 1…j ]**所需要的最少步骤个数 简单理解 表示将
A的前i个字符转换成B的前j个字符所需的最少编辑操作次数.那么我们就必须在之前可以以最少操作次数进行增加，删除，或者替换操作，使得现在串 A 和串 B 只需要再做一次操作或者不做就可以完成 A[1..i] == B[1..j] 的转换。也就是说我们只需要基于上一次的1-i 完成 1-j 的最优解的基础上进行一次操作就是这次一次的最优解
-
那么这个之前指的就是我们之前计算的最小操作次数的基础上进行
+1因为是个矩阵我们只需要找出之前计算出的增,删,替换,操作的次数然后+1取出最小值就是这次的最佳操作次数所谓的“之前”分为下面三种情况：
- 要得到 A[1…i] == B[1…j-1]，需要 k 个操作
- B[j-1]得到的是B当前在操作的字符(前[i]字符-1次)也就是上一次操作时的次数 即将当前子字符串的最后一个字符删除（删除操作），将其转换为目标子字符串所需的最小操作数。
- 要得到A[1..i-1] == B[1..j]，需要 k 个操作
- **A[i-1]**得到的就是A字符串的上一次字符的操作次数,即将当前子字符串添加一个字符（插入操作），将其转换为目标子字符串所需的最小操作数
- 要得到 A[1…i-1] == [1…j-1]，需要 k 个操作
- A[-1] == **[j-1]**的意思就是该字符相等与上次一锁执行的最小操作数保持一致
- 要得到 A[1…i] == B[1…j-1]，需要 k 个操作
-
接下来是代码演示
String word1 = "horse"; String word2 = "ros"; int m = word1.length(); int n = word2.length(); // 初始化第一行和第一列 for (int i = 0; i <= m; i++) { dp[i][0] = i; } for (int j = 0; j <= n; j++) { dp[0][j] = j; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (word1.charAt(i - 1) == word2.charAt(j - 1)) { // 如果一样则与上一个字符的操作次数保持一致 dp[i][j] = dp[i - 1][j - 1]; // 如果当前字符相同，则不需要操作 } else { // 否则，取插入、删除、替换操作的最小值，并加上操作的代价1 dp[i][j] = Math.min( // 获得的是上一次的对比的结果 也就是删除的操作次数 dp[i - 1][j - 1], // 获得的是上一次的次数 也就是添加一个字符的次数 Math.min(dp[i][j - 1], dp[i - 1][j]) ) + 1; } } }
初始化的视图
r o s +----------------- | 0 1 2 3 h | 1 o | 2 r | 3 s | 4 e | 5
-
此时当我们执行该嵌套for循环的时候其实就是判断
D[1][1]上的值是否相等i = 1，word1的前1个字符是 "h"j = 1，word2的前1个字符是 "r"：执行该公式 $$ D[1][1] = min(D[i-1][1] + 1, D[1][j-1] + 1, D[i-1][j-1] + 1) = min(2, 2, 1) = 1 $$ 视图如下
r o s +----------------- | 0 1 2 3 h | 1 1 o | 2 r | 3 s | 4 e | 5
-
i = 1，word1的前1个字符是 "h"j = 2，word2的前2个字符是 "ro" $$ D[1][2] = min(D[0][2] + 1, D[1][1] + 1, D[0][1] + 1) = min(3, 2, 2) = 2 $$ 矩阵如下**
r o s +----------------- | 0 1 2 3 h | 1 1 2 o | 2 r | 3 s | 4 e | 5
-
以此类推 每一步的最小操作数依赖于前一步的结果。通过逐步计算，我们确保了所有可能的操作路径都被考虑，从而保证全局最优解。
但是由于该算法是基于A=B的这种结果去进行推演的所以标签的顺序就变得至关重要,为了解决这个问题进行计算匹配值之前我首先对要匹配的标签进行了一致性的过滤代码如下
// 找出共同标签
List<String> commonElements = tagList.stream()
.filter(userTagsList::contains)
.collect(Collectors.toList());
// 排序list1，将共同的元素放在前面，保留原来的顺序
List<String> sortedList1 = tagList.stream()
.sorted(Comparator.comparingInt(s -> commonElements.contains(s) ? commonElements.indexOf(s) : Integer.MAX_VALUE))
.collect(Collectors.toList());
// 排序list2，将共同的元素放在前面，保留原来的顺序
List<String> sortedList2 = userTagsList.stream()
.sorted(Comparator.comparingInt(s -> commonElements.contains(s) ? commonElements.indexOf(s) : Integer.MAX_VALUE))
.collect(Collectors.toList());这种方法需要将自己的标签与数据库中所有用户的标签进行算法计算。在执行过程中，由于计算量庞大，代码的复杂度可能会变得极其高。然而，如果数据量不是特别庞大，该方法仍然具有一定的可用性。
- Vue 3
- Vant UI 组件库
- TypeScript
- Vite 脚手架
- Axios 请求库
- Java SpringBoot 2.7.x 框架
- MySQL 数据库
- MyBatis-Plus
- MyBatis X 自动生成
- Redis 缓存（Spring Data Redis 等多种实现方式）
- Redisson 分布式锁
- Easy Excel 数据导入
- Spring Scheduler 定时任务
- Swagger + Knife4j 接口文档
- Gson：JSON 序列化库
- 相似度匹配算法
- 该项目部署在阿里云ECS云服务器
- ubuntu 22.4版本
- 需求分析
- 技术选型（各技术作用讲解）
- 前端项目初始化
- 脚手架
- 组件 / 类库引入
- 前端页面设计及通用布局开发
- 后端数据库表设计
- 按标签搜索用户功能
- 前端开发
- 后端开发
- 性能分析
- 接口调试
- Swagger + Knife4j 接口文档整合
- 后端分布式登录改造（Session 共享）
- 用户登录功能开发
- 修改个人信息功能开发
- 主页开发（抽象通用列表组件）
- 批量导入数据功能
- 几种方案介绍及对比
- 测试及性能优化（并发编程）
- 主页性能优化
- 缓存和分布式缓存讲解
- Redis 讲解
- 缓存开发和注意事项
- 缓存预热设计与实现
- 定时任务介绍和实现
- 锁 / 分布式锁介绍
- 分布式锁注意事项讲解
- Redisson 分布式锁实战
- 控制定时任务执行的几种方案介绍及对比
- 组队功能
- 需求分析
- 系统设计
- 多个接口开发及测试
- 前端多页面开发
- 权限控制
- 随机匹配功能
- 匹配算法介绍及实现
- 性能优化及测试
- 项目优化及完善
因为该项目使用session 用于用户的身份校验,所以当服务器进行横向拓展时由于一些负载均衡机制导致用户登录后会随机交由某个服务器去进行业务服务,但是当用户的下次请求被请求到了一个没有该用户缓存的服务时会让用户重新进行登录,为了避免这种问题我们将用户登录的session信息保存在redis中 让所有的服务器去连接同一个redis,当用户被分配到其他服务时也可以到redis 中获取到对应的登录信息
当用户登录时后端会通过HttpServletRequest 对象实例 的api 对该用户信息进行一个session 配置 随后会将该信息保存在redis 中同时也会向浏览器发送一个 cookie
当用户进行某些行为时我们可以通过cookie 的session与缓存中的信息进行一次比对来完成对用户的鉴权