安企神电脑监控软件 在线试用
扫码咨询客服
安企神电脑监控软件、局域网监控软件
首页
功能介绍
产品简介
下载中心
帮助中心
客户列表
关于安企神

哈希算法在字典上的测试应用

更新时间:2022-10-28 15:46:47


本文简介:此前我们了解过二叉树算法,哈希算法,二分法等等,其中由最常用的二叉树算法演变过来的哈希算法乃是从刚开始就学过的,此次因为一些项目的需要,要做一个类似ispell 的软件,其中会产生大量的对单词的查找操作,于是经过一翻研究,得出以下HASH算法,经过验证比一般的查表的FNV HASH算法产生的分布曲线基本没什么两样,并且在大部分的不同字典下,本算法要比查表的FNV HASH算法表现出速度更快,分布更

哈希算法在字典上的测试应用

此前我们了解过二叉树算法,哈希算法,二分法等等,其中由最常用的二叉树算法演变过来的哈希算法乃是从刚开始就学过的,此次因为一些项目的需要,要做一个类似ispell 的软件,其中会产生大量的对单词的查找操作,于是经过一翻研究,得出以下HASH算法,经过验证比一般的查表的FNV HASH算法产生的分布曲线基本没什么两样,并且在大部分的不同字典下,本算法要比查表的FNV HASH算法表现出速度更快,分布更均匀。但是因为是实验结果,所以暂时还没得出有效的数学推论,但是从大量的不同的字典测试数据来看,此算法确实效率不错。
由于以前没有涉及过相关的纯算法的设计,所以刚刚开始的时候,打算随便选用一种HASH,比如说用%除大质数,然后借此搭建一个比较强壮的测试环境,然后打算根据测试结果来改进HASH算法的模型。

最开始,我的HASH函数是这样的:
unsigned int hash_func(char *str, int len)
{
register unsigned int sum = 0;
register char *p = str;

while(p - str < len)
sum += *(p++);

return sum % MAX_PRIME_LESS_THAN_HASH_LEN;
}
非常简单,但是这是绝对不可取的,通过这个函数,我选取了一个23w词的字典做为测试,当HASH SIZE=1024的时候,震荡幅度相当大,那么如何来改进呢?首先想到可能产生的冲突的是这种情况:abcd和acbd,对于这两种单词来说,如果用上面的HASH函数,就一定会发生碰撞,为什么呢?因为每个字符少了关于它自己的位置信息,于是第一次改进版本的HASH函数就给每个字符加上了它的位置信息,将上面所描述的函数改进为:

unsigned int hash_func(char *str, int len)
{
register unsigned int sum = 0;
register char *p = str;

while(p - str < len)
sum += *(p++) * (p–str);

return sum % MAX_PRIME_LESS_THAN_HASH_LEN;
}

某种程度上来说,比不带位置信息产生的分布图要好多了,但是仍然非常的不均匀。那么接来分析产生分布不均匀的原因,因为是用的乘法,所以仍然太过于依赖字母产生的结果了。于是改用XOR操作,选用以下函数:

unsigned int hash_func(char *str, int len)
{
register unsigned int sum = 0;
register char *p = str;

while(p - str < len)
sum += (*(p++) * (p–str)) ^ sum;

return sum % MAX_PRIME_LESS_THAN_HASH_LEN;
}

虽然震荡幅度比较,不过做出来的regression line明显比上两张图片平得多了。但是结果仍然非常不好,从800到100的range太大。原因还是因为数据分布得不够均匀,于是思考单独的用加法来算是不是不太好,根据其他查表类HASH算法的过程,发现其大多都用了高低位来组合成最后的结果,于是我也采用了他们的方法:

unsigned int hash_func(char *str, int len)
{
register unsigned int sum = 0; 
register unsigned int h = 0;
register char *p = str;

while(p - s < len) 
{
register unsigned short a = *(p++);
sum ^=  a * (p - str); 
h ^= a / (p - str);
}
return ((sum << 16) | h) % MAX_PRIME_LESS_THAN_HASH_LEN;
}

最后得出结论,不用查表的方法,而通过字符串本身的位置对字符本身进行修正的方法也能得到结果相当满意的HASH函数,之后换了几个大小不同的字典进行测试,得出的图象都大致和上图一致,非常令人满意。对于这个项目,包括如何检查单词错误,和自动修正等等相关的内容,会随着项目的完成一一在整理成文档,希望大家支持。

立即下载试用

DSA加密算法和RSA加密算法的区别在哪里?

DSA是基于整数有限域离散对数难题的,DSA的一个重要特点是两个素数公开,这样,当使用别人的p和q时,即使不知道私钥,你也能确认它们是否是随机产生的,还是作了手脚。RSA算法却做不到。

RSA算法在网络容易实现密钥管理,便进行数字签名,算法复杂,加/解速度慢,采用非对称加密

DSA = Digital Signature Algorithm. based on discrete logarithms computation.

DES = Digital Encryption Standard. Obsolete standard.

What is DCE?

DSA 用于签名,而 RSA 可用于签名和加密。

DSA is faster in *signing*, but slower in *verifying*.

A DSA key of the same strength as RSA (1024 bits) generates a smaller signature.

An RSA 512 bit key has been cracked, but only a 280 DSA key.

It doesn’t matter because with Ssh only authentication is done using RSA or DSA algorithm, and then the “rest” is encoded using a (uh, was it block?) cipher like IDEA, DES, Blowfish, etc, etc after the authentication is done.

While SSH2 can use either DSA or RSA keys, SSH1 cannot. Ssh2 will also not use patented cypers like IDEA.

Filed under: System — Tags: cryptography — Commen

RSA的安全性一直未能得到理论上的证明。 RSA的安全性依赖于大数分解。公钥和私钥都是两个大素数( 大于 100个十进制位)的函数。据猜测,从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。

本文为收集整理,文章部分观点不代表本站观点,如有侵权或其它问题请反馈客服。https://www.wgj7.com/cjwt/16498.html