出个题目大家玩玩 : 比较14万单词的相似度

2024-01-11 23:18

本文主要是介绍出个题目大家玩玩 : 比较14万单词的相似度,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:比较14万单词的相似度
输入:14万单词表,table( ID,word)
输出:给出单词关系表( ID1,ID2,相似度),相似度要大于60%

例如:
aoc和aoe的相似度为(百分之):67
abc和abcd的相似度为75

实验用三万单词库下载:

http://www.dullwolf.cn/word/word.rar

14万单词库已经有了,加工后和3万的一起打包再给大家下载.
3万的适合做背单词,14万适合做字典.


包括真人发声,全部单词读音的mp3
 我是先切词,所有词都拆成匹配原子表table(ID,原子),原子的长度要大于单词自身长度的60%才有意义.
然后用 原子表 join   自联原子表 on 原子=原子
比较所有 最大长度 原子相同 /两个单词中长的那个

就是相似程度.
3万词切成原子,大概有30万行.

spide
总长度是5
那么>=3的原子才有用
3个的:spi/pid/ide
4个的:spid/pide
5个的:spide
1夹2的:s_id/p_de/
2夹1的:sp_i/pi_e
1夹3的:s_ide
3夹1的:spi_e
2夹2的:sp_de
....
这样一来
假设这词id是900
那么全部词就形成这样的原子对照表
900  spi
900  pid
900  ide
900  spid
....
901  ...
999  ....
自联去比较,可能是一个很大的集合.
假设有一个靶有26个靶环,分别是 a,b,c,d,----z;我们规定如果击中了靶环,该环得分为1,反之为零,每个单词的字母表示该单词击中了对应的靶环的位置.

ok:照上面的规定
abc:就是1110000000000000000000000000有3个1
abd:就是1101000000000000000000000000有3个1

异或运算
结果:就是1100000000000000000000000000有2个1

好了结果就有了,相似度为2/3
我给一个oracle数据库的简单算法:
先创建一个函数,返回相关性。
Create Or Replace Function f_Correlation(f_Str Varchar2, f_Data Varchar2)
 Return Number Is
 l_Corr Number;
 l_Pos  Int;
Begin
 l_Corr := 0;
 For c_Str In (Select Substr(f_Data, Rownum, 1) s
                 From All_Objects
                Where Rownum <= Length(f_Data)) Loop
   Select Instr(f_Str, c_Str.s) Into l_Pos From Dual;
   If l_Pos > 0 Then
     l_Corr := l_Corr + 1;
   End If;
 End Loop;
 Return l_Corr;
End f_Correlation;

然后调用函数:
--源数据
SQL> select * from ta;

A
------------------------------
这是
这是排名
相关
相关度排名
度数

--以“这是相关度测试排名'”作为匹配标准

SQL> select a,f_correlation(a,'这是相关度测试排名') "相关性" from ta order by 2 desc;

A                                  相关性
------------------------------ ----------
相关度排名                              5
这是排名                                4
这是                                    2
相关                                    2
度数                                    1

实际中,如何分词是搜索的关键。
比较单词相似度,必须首先切词,英文单词切词法,combine排列组合的“组合”数学算法是关键。

下面代码给出原子的一种思路:比如输入单词“spide”,输出所有可能用来和其他单词比较的原子,由于单词长度是5,匹配度小于60%的没意义,所以原子最小长度是3。

代码是从C语言算法改过来的,同样代码也可以修改成任何编程语言。


ide
pde
sde
pie
sie
spe
pid
sid
spd
spi
pide
side
spde
spie
spid
spide

这里用到了Combine 输出全部组合,Combine 5,3就是得到在5个里选3个的全部可能选法。
<SCRIPT LANGUAGE="vbScript">

str="spide"
''创建全局字典对象,用来存储所有得到的原子结果
Set dict=CreateObject("Scripting.Dictionary")

Dim  a(100)
strLength=Len(str)
''原子
atomyLength=round(strLength*0.6)

For x=atomyLength To strLength
 a(0)=x
 ''计算5选3,5选4,5选5组合
 combine strLength,x
next
 


sub combine(m,  k)
''计算组合在m里面选k个元素的全部组合情况,添加到字典对象里
 i=0
 j=0
 For i=m To k Step -1
  a(k)=i
  if (k>1)  then
   combine i-1,k-1 
  else
   tempStr=""
   for  j=1 To a(0) 
    tempStr=tempStr &  Mid(str,a(j),1)
   Next
   ''排除重复的,加到字典里
   If Not dict. Exists(tempStr) then  dict.add tempStr,Len(tempStr)
  End if
 next
End sub

Main()

Sub Main
 ''输出显示结果
 For i=0 To dict.count-1
  Document.write  dict.keys()(i) & "<br/>"
 next
End sub
</SCRIPT>
考虑到抠去某些字符的组合,结果就非常多,以combine为例有64种不重复切法,输入superdullwolf达到了1700多种!按照平均每个词200种原子算,14万词要产生3000万,在数据库里原子表自联后是个天文数字。
bine
mine
oine
cine
mbne
obne
cbne
omne
cmne
cone
mbie
obie
cbie
omie
cmie
coie
ombe
cmbe
cobe
come
mbin
obin
cbin
omin
cmin
coin
ombn
cmbn
cobn
comn
ombi
cmbi
cobi
comi
comb
mbine
obine
cbine
omine
cmine
coine
ombne
cmbne
cobne
comne
ombie
cmbie
cobie
comie
combe
ombin
cmbin
cobin
comin
combn
combi
ombine
cmbine
cobine
comine
combne
combie
combin
combine
按照在索引中对两个词的相似度的定义:两个单词的编辑距离ed(word1,word2)为word1经过编辑到达word2所需的最小的步骤,这里编辑所指为:
1.插入:如ab->acb
2.删除:如abc->ab
3.修改:如abc->abb

如ed(surgery,survey)=2
ed()越小证明两个单词就越相似,这个的原始定义可以看“A Guided Tour to Approximate String Matching”作者Gonzalo Navarro

确定两个单词的相似有很多方法,可以用动态规划,Q-gram,不确定自动机等。在Gonzalo Navarro的这篇文章中也都有介绍“A Guided Tour to Approximate String Matching”。

把这个给这里的大牛们,看看有人实现没。
Transact-SQL 参考

 
SOUNDEX
返回由四个字符组成的代码 (SOUNDEX) 以评估两个字符串的相似性。

语法
SOUNDEX ( character_expression )

参数
character_expression

是字符数据的字母数字表达式。character_expression 可以是常数、变量或列。

返回类型
char

注释
SOUNDEX 将 alpha 字符串转换成由四个字符组成的代码,以查找相似的词或名称。代码的第一个字符是 character_expression 的第一个字符,代码的第二个字符到第四个字符是数字。将忽略 character_expression 中的元音,除非它们是字符串的第一个字母。可以嵌套字符串函数。

示例
下例显示 SOUNDEX 函数及相关的 DIFFERENCE 函数。在第一个示例中,返回所有辅音字母的标准 SOUNDEX 值。为 Smith 和 Smythe 返回的 SOUNDEX 结果相同,因为不包括所有元音、字母 y、连写字母和字母 h。

-- Using SOUNDEX
SELECT SOUNDEX ('Smith'), SOUNDEX ('Smythe')

下面是结果集:

----- -----
S530  S530 

(1 row(s) affected)

DIFFERENCE 函数比较 SOUNDEX 模式结果的差。第一个示例显示两个仅元音不同的字符串。返回的差是 4(可能的最小差)。

-- Using DIFFERENCE
SELECT DIFFERENCE('Smithers', 'Smythers')
GO

下面是结果集:

-----------
4          

(1 row(s) affected)

在下例中,字符串的辅音不同,所以返回的差是 2(较高的差)。

SELECT DIFFERENCE('Anothers', 'Brothers')
GO

下面是结果集:

-----------
2          

(1 row(s) affected)
组合算法 ,子陌红尘的存储过程:
create procedure sp_test(@n int,@r int)
as
begin
    if isnull(@n,0)<isnull(@r,0)
        return

    set rowcount @n
    select identity(int,1,1) as num into # from sysobjects a,syscolumns b
    set rowcount 0
   
    declare @sql varchar(8000),@ord varchar(8000),@i int
    set @sql='select * from # [1]'
    set @ord='[1].num'
    set @i=1
    while @i<@r
    begin
        set @i=@i+1
        set @sql=@sql+' inner join # ['+rtrim(@i)+'] on ['+rtrim(@i)+'].num>['+rtrim(@i-1)+'].num'
        set @ord=@ord+',['+rtrim(@i)+'].num'
    end

    set @sql=@sql+' order by '+@ord

    print @sql
   
    exec(@sql)
end
go

--exec sp_test 5,1
--exec sp_test 5,2
exec sp_test 15,10
go

drop procedure sp_test
go
单词表:word(id,word)
假设单词最长20个
select a.id, b.id,a.word, b.word,
(decode(substr(a.word,1,1),null,0,substr(b.word,1,1),1,0)+
decode(substr(a.word,2,1),null,0,substr(b.word,2,1),1,0)+
decode(substr(a.word,3,1),null,0,substr(b.word,3,1),1,0)+
decode(substr(a.word,4,1),null,0,substr(b.word,4,1),1,0)+
decode(substr(a.word,5,1),null,0,substr(b.word,5,1),1,0)+
decode(substr(a.word,6,1),null,0,substr(b.word,6,1),1,0)+
decode(substr(a.word,7,1),null,0,substr(b.word,7,1),1,0)+
decode(substr(a.word,8,1),null,0,substr(b.word,8,1),1,0)+
decode(substr(a.word,9,1),null,0,substr(b.word,9,1),1,0)+
decode(substr(a.word,10,1),null,0,substr(b.word,10,1),1,0)+
decode(substr(a.word,11,1),null,0,substr(b.word,11,1),1,0)+
decode(substr(a.word,12,1),null,0,substr(b.word,12,1),1,0)+
decode(substr(a.word,13,1),null,0,substr(b.word,13,1),1,0)+
decode(substr(a.word,14,1),null,0,substr(b.word,14,1),1,0))
decode(substr(a.word,15,1),null,0,substr(b.word,15,1),1,0))
decode(substr(a.word,16,1),null,0,substr(b.word,16,1),1,0))
decode(substr(a.word,17,1),null,0,substr(b.word,17,1),1,0))
decode(substr(a.word,18,1),null,0,substr(b.word,18,1),1,0))
decode(substr(a.word,19,1),null,0,substr(b.word,19,1),1,0))
decode(substr(a.word,20,1),null,0,substr(b.word,20,1),1,0)) --比较每个位置是否相同
/
decode(trunc((length(a.word)-length(b.word)+1000)/1000),1,length(a.word),length  (b.word)) -- 取两个单词中最大的长度

from word a, word b
where a.id<>b.id
我现在是找到了原子.问题是数据量太大,回家实验下,原子需要用非SQL程序来找,计划用ASP, 因为懒得编译,做一个页面不停的刷,先把全部词的原子找出来.
然后实验:
一:
1种方案,海量数据的原子表包含(单词ID,原子)其中原子重复数据,自联接,找出最长公共子串.
二:
原子表单独建立,建立一个单词和原子的对应关系表,再连接.
三:
如果上面两种办法都导致机器冒烟,那么把每个单词的原子生成一个XML文件,用SQL 去load成单独的小表,这样一个一个表慢慢比较.(可能要很久),每次比较耗费的资源不多,就是比较的次数比较多,大概是单词数量的阶乘,就算每秒比较10次,可能这辈子都比较不完了.

如果按照Honey_boy(阿良)的余弦算法,采样点到原点的距离,x轴是字母a-z用1-26表示
y轴用单词出现的位置来表示.
那么,
对于单词abc,坐标分别是(1,1)(2,2)(3,3)(0,4) P1=sqrt(2);P2=sqrt(8);P3=sqrt(18);P4=4;
对于单词abcd,坐标分别是(1,1)(2,2)(3,3) Q1=sqrt(2);Q2=sqrt(8);Q3=sqrt(18);Q4=sqrt(32);
计算大概是1.68
越接近1越相似.

原子表包括了一些联想元素,符合人的思维习惯,比如Combine的原子可以是
mine
oine
cine
这些并不是单纯的字符片段,而是抠掉了部分字母.
建立原子字典表和单词关系两个表,速度上会有提升,hansonboy() 说的对,提前计算出原子长度和单词长度储存在合适的位置,会加速计算的速度.

这篇关于出个题目大家玩玩 : 比较14万单词的相似度的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/596029

相关文章

Python如何计算两个不同类型列表的相似度

《Python如何计算两个不同类型列表的相似度》在编程中,经常需要比较两个列表的相似度,尤其是当这两个列表包含不同类型的元素时,下面小编就来讲讲如何使用Python计算两个不同类型列表的相似度吧... 目录摘要引言数字类型相似度欧几里得距离曼哈顿距离字符串类型相似度Levenshtein距离Jaccard相

C#比较两个List集合内容是否相同的几种方法

《C#比较两个List集合内容是否相同的几种方法》本文详细介绍了在C#中比较两个List集合内容是否相同的方法,包括非自定义类和自定义类的元素比较,对于非自定义类,可以使用SequenceEqual、... 目录 一、非自定义类的元素比较1. 使用 SequenceEqual 方法(顺序和内容都相等)2.

对postgresql日期和时间的比较

《对postgresql日期和时间的比较》文章介绍了在数据库中处理日期和时间类型时的一些注意事项,包括如何将字符串转换为日期或时间类型,以及在比较时自动转换的情况,作者建议在使用数据库时,根据具体情况... 目录PostgreSQL日期和时间比较DB里保存到时分秒,需要和年月日比较db里存储date或者ti

百度/小米/滴滴/京东,中台架构比较

小米中台建设实践 01 小米的三大中台建设:业务+数据+技术 业务中台--从业务说起 在中台建设中,需要规范化的服务接口、一致整合化的数据、容器化的技术组件以及弹性的基础设施。并结合业务情况,判定是否真的需要中台。 小米参考了业界优秀的案例包括移动中台、数据中台、业务中台、技术中台等,再结合其业务发展历程及业务现状,整理了中台架构的核心方法论,一是企业如何共享服务,二是如何为业务提供便利。

业务中14个需要进行A/B测试的时刻[信息图]

在本指南中,我们将全面了解有关 A/B测试 的所有内容。 我们将介绍不同类型的A/B测试,如何有效地规划和启动测试,如何评估测试是否成功,您应该关注哪些指标,多年来我们发现的常见错误等等。 什么是A/B测试? A/B测试(有时称为“分割测试”)是一种实验类型,其中您创建两种或多种内容变体——如登录页面、电子邮件或广告——并将它们显示给不同的受众群体,以查看哪一种效果最好。 本质上,A/B测

题目1254:N皇后问题

题目1254:N皇后问题 时间限制:1 秒 内存限制:128 兆 特殊判题:否 题目描述: N皇后问题,即在N*N的方格棋盘内放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在同一斜线上。因为皇后可以直走,横走和斜走如下图)。 你的任务是,对于给定的N,求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入

题目1380:lucky number

题目1380:lucky number 时间限制:3 秒 内存限制:3 兆 特殊判题:否 提交:2839 解决:300 题目描述: 每个人有自己的lucky number,小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话,都是他的lucky number。但是,现在这个序列很大,他无法快速找到所有lucky number。既然

关键字synchronized、volatile的比较

关键字volatile是线程同步的轻量级实现,所以volatile性能肯定比synchronized要好,并且volatile只能修饰于变量,而synchronized可以修饰方法,以及代码块。随着JDK新版本的发布,synchronized关键字的执行效率上得到很大提升,在开发中使用synchronized关键字的比率还是比较大的。多线程访问volatile不会发生阻塞,而synchronize

每日一练7:简写单词(含链接)

1.链接 简写单词_牛客题霸_牛客网 2.题目 3.代码1(错误经验) #include <iostream>#include <string>using namespace std;int main() {string s;string ret;int count = 0;while(cin >> s)for(auto a : s){if(count == 0){if( a <=

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(