精易论坛

标题: 快速计算文本相似度 [打印本页]

作者: 梦中的挂念 时间: 2016-4-19 01:42
标题: 快速计算文本相似度
本帖最后由梦中的挂念于 2016-4-19 09:49 编辑

考虑求出最长子序列（LCS），再除以两串中最长的，得出相似度。

求最长子序列有穷举法，设字符串长度为n，其计算量为2的n次方，十分恐怖。

所以考虑使用动态规划递推解决。

注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。

首先，子序列和子串是不一样的。子串是连续的，而子序列中的元素组成可以是不连续的，但元素的位置下标一定是递增的。以一个字串S = "abcdef"为例，字串S的一个子串是"abc",'cdef'这种连续的，而子序列可以是"abc"，也可以是"af "，给人的直观感觉就是用S中的字符拼凑成的，但f一定在a之前。

   我们设有两个字符串X和Y，其中，X={x0, x1, x2, ....xi }，Y={y0, y1, y2, yj }。用lcs(i , j)表示字符串X与Y的最长公共子序列的长度。
由动态规划思想可知，问题的最优解是由子问题的最优解构成的，所以lcs(i,j) 的值与lcs(i-1, j-1), lcs(i-1, j), lcs(i, j-1) 都有一定的关系。
要确定lcs(i,j)的值，首先比较一下xi, yj 的值，有以下2种情况：

1. xi == yj，说明xi与yj 一定在最长公共子序列中，所以lcs (i , j) 是由lcs(i-1,j -1)之前的值决定的，即
   lcs(i,j) = lcs(i-1, j-1) + 1；
2. xi != yj ，设在最长公共子序列中的最后一个值为zk，可能zk == xi，也可能zk == yj，也可能zk与xi, yj的值都不同。
这3种情况的分析如下：
   a. zk == xi, 那么最长公共子序列取决于去掉yj的Y字符串与X字符串的最长公共子序列，
      即lcs(i, j) = lcs(i, j-1)；
   b. 与a同理，若yj在最长公共子序列中，那么lcs(i, j) = lcs(i - 1, j)；
   c. zk与xi, yj的值都不同，那么lcs( i, j ) 的值取决于去掉xi的X字串与去掉yj的Y字串的最长公共子序列的长度，即
      lcs(i, j) = lcs( i-1, j-1)。

   结合a,b,c的情况，因为最长公共子序列必有最大的长度，所以
   lcs(i, j) = max ( lcs( i-1, j) , lcs( i, j-1) )。这个公式之所以包含情况c，是因为在情况c下，最长公共子序列的最后一个
   值zk肯定是xi与yj之前的位置上的值，xi 与yj 在这种情况下对最长公共子序列的长度没有影响力，所以在这种情况下，
   lcs( i-1, j) 和 lcs( i, j-1)都等于lcs (i -1, j -1)，可归并到公式中。

因此可得状态转移方程为：

if (xi == yj) LCS(i,j) = LCS(i-1, j-1) + 1
if (xi != yj) LCS(i, j) = max ( LCS( i-1, j) , LCS( i, j-1) )

具体请看源码

快速计算文本相似度.zip (2.2 KB, 下载次数: 1064)

作者: qiankun 时间: 2016-4-19 08:24

嘛用呢

作者: ck66 时间: 2016-4-19 08:54
感谢发布原创作品，精易因你更精彩！

作者: 编程爱好者007 时间: 2016-4-19 12:49
提示: 作者被禁止或删除内容自动屏蔽

作者: 118184017 时间: 2016-4-19 12:54
不错，非常好！

作者: nr4dyz 时间: 2016-4-19 13:48
66666666666666666666666 计算能力```

作者: 小侯 时间: 2016-4-19 17:35

作者: ☆心酸☆点击资 时间: 2016-4-19 17:57
虽然不知道有什么用，但是感觉很牛逼的样子，这样计算哪里有帮助？

作者: 绝版ん楠楠 时间: 2016-4-19 18:58
感谢分享，很给力！~

作者: 无名侠 时间: 2016-4-19 18:59
易语言高级玩家，动态规划

作者: BlueBoy 时间: 2016-4-28 20:48
#在这里快速回复#精彩文章希望继续努力

作者: Ai鹿 时间: 2016-5-20 05:16
感谢发布原创作品，精易因你更精彩！

作者: SEA游游 时间: 2016-8-8 16:19
学习一下..

作者: 1448593083 时间: 2016-12-9 09:20
感谢分享，很给力！~

作者: 星云散落 时间: 2017-3-13 06:35
学习一下哈

作者: 307840899 时间: 2017-3-13 12:28
学习一下..

作者: 519505667 时间: 2018-12-10 11:52
十分感谢，正好借用

作者: wjclyaa 时间: 2018-12-13 18:13
谢谢分享，下载来学习下

作者: 春风秀才 时间: 2018-12-19 14:00
希望楼主优化下，abc和cab应该完全不同，但是输出却是66.6%相似度

作者: 448921899 时间: 2018-12-29 16:19
感谢分享，

作者: orjg 时间: 2019-6-12 13:38
感谢发布原创作品，精易因你更精彩！

作者: 神女软件定制 时间: 2020-1-25 23:37
很牛逼，但是我暂时没有这个需求

作者: 小k666 时间: 2020-3-25 08:55
看看是什么，正好需要

作者: 天道酬勤V8 时间: 2020-4-15 20:38
谢谢分享谢谢分享谢谢分享谢谢分享

作者: 辽阳小哲 时间: 2020-7-3 16:24
看起来很高级的样子，来试试

作者: 小毛皮 时间: 2021-11-3 15:08
好厉害，刚好需要，学习了

作者: hongfangs 时间: 2021-12-10 09:55
感谢发布原创作品，精易因你更精彩！

作者: caoxiaojun521 时间: 2022-1-1 17:51
下载试试下载试试下载试试

作者: 暮色夕阳 时间: 2022-1-7 17:31
真好需要这方面的知识谢谢

作者: zexian 时间: 2022-7-13 11:15
两个文本必须是顺序一致,文本中倒一下位置,即使里面文字或英文都有,也会影响相似度,空格也会影响

作者: yingle 时间: 2022-12-21 10:14
精彩文章希望继续努力

作者: 18072699966 时间: 2023-3-2 17:35
感谢发布原创作品，精易因你更精彩！

作者: asd5585 时间: 2023-3-17 02:34
感谢发布原创作品，精易因你更精彩！

作者: 百度搜不到你 时间: 2023-3-30 18:18
学习收藏，感谢分享

作者: ♂隐 时间: 2023-4-3 10:37
哦，尼玛我都看晕了···这个很尴尬啊！

作者: lmluo 时间: 2023-4-6 15:20
前面我还找来着，说要学什么正则，现在有这个，学习学习

作者: dliangyu 时间: 2023-5-4 20:14
个打个打个

作者: 小风明SS 时间: 2023-5-20 21:04
oi人表示很喜欢

作者: 脚本爱好者 时间: 2023-5-26 11:28
oi人表示很喜欢

作者: lhbismy1 时间: 2023-6-8 12:43
非常感谢！

作者: 9929507a 时间: 2023-7-17 03:19

前面我还找来着，说要学什么正则，现在有这个，学习学习

作者: sunsail2018 时间: 2023-7-26 12:34
感谢发布原创作品，精易因你更精彩！

作者: w7188148 时间: 2023-8-18 11:24
感谢发布原创作品，精易因你更精彩！

作者: wqchat 时间: 2023-8-21 10:15
感谢发布原创作品，精易因你更精彩！

作者: nwzhi 时间: 2023-9-24 14:58
谢谢分享，学习下

作者: 瀚伟00 时间: 2023-11-18 23:22
学习一下

作者: shelkio 时间: 2024-1-15 22:05
我来看看了

作者: kfccfk 时间: 2024-1-20 22:20
谢谢分享，学习一下

作者: 小情缘 时间: 2024-1-24 07:46
谢谢分享，学习一下

作者: itoljeipw 时间: 2024-2-7 21:52
谢谢分享，学习一下

作者: Conquer 时间: 2024-2-22 21:38
谢谢分享，学习一下

作者: single刘 时间: 2024-2-29 19:12
为什么是短整数型啊？我要比较的字符串比较长呢？

作者: aosheng 时间: 2024-3-16 23:10
666666666666666666666

作者: 一曲长歌入冬流 时间: 2024-5-17 22:23
精彩文章希望继续努力

作者: w322zkkw 时间: 2024-9-18 22:15

作者: 1417692308 时间: 2024-10-7 22:35
感谢发布原创作品，精易因你更精彩

作者: zml521 时间: 2024-12-8 14:00
感谢分享谢谢谢

作者: yksuper 时间: 2025-3-4 10:55
快速计算文本相似度

作者: wenllson 时间: 2025-3-31 15:02
谢谢分享，学习一下

欢迎光临精易论坛 (https://125.confly.eu.org/)