算法

首页算法
03
Jan
0

rsa加密

目前RSA算法据说 是当前最强算非对称加密算法 超过1024位基本无法破解

所以先准备一个备用 ^_^

pip install rsa

import rsa

rsa加密

def rsaEncrypt(str):

#生成公钥、私钥  
(pubkey, privkey) = rsa.newkeys(512)  
#明文编码格式  
content = str.encode('utf-8')  
#公钥加密  
crypto = rsa.encrypt(content,pubkey)  
return (crypto,privkey)  

rsa解密

def rsaDecrypt(str,pk):

#私钥解密  
content = rsa.decrypt(str,pk)  
con=content.decode('utf-8')  
return con  

(a,b) = rsaEncrypt("hello")
print('加密后密文:')
print(a)
content = rsaDecrypt(a,b)
print('解密后明文:')
print(content)

25
Dec
0
25
Dec
0

基于信息熵的无字典分词算法

这几天在研究如何用统计方法来发现新词,扩充自己的词典。看到了几篇很有想法的文章,作者阐述了一下思路。文章里面的数据,我计算了一下,发现文有很多数据不够严谨,最主要的问题,并没有给出很详细的理论方面的说明。结合作者的思路,我进行了如下数学模型的构建和算法的实现。

一、概念介绍

1、词语分片

设一个文档集 。其中,为一个文本,。

设 为文档的分片集合。其中,为文档的一个词语分片,分片就是按step步长对文档进行分割的词语单位。这里说的词语分片可以是一个字、一个词或者一个长词。

譬如:中国队,

按step=1进行切分 S={中,国,队}

按step=2进行切分 S={中,国,队,中国,国队}

按step=3进行切分 S={中,国,队,中国,国队,中国队}。

当然,这个定义可以推广到有字典的情况:

譬如 字典 {中国}

"中国国家队"的词语分片为{中国,国,家,队,中国国,国家,家队,中国国家,国家队,中国国家队}。

这样来看,一个文本分若干段落;一个段落通过标点符号进行分割,分割成若干短句,我们成为语义单元;一个语义单元按step步长进行切分成若干个词语切片。我们把所有切片合并成一个大集合。

2、分片属性

为了解决上面的问题,对于分片S我们从分片概率、分片频度、自由度、凝固程度等属性去考虑。这些属性都是概率变量。

这样,一个分片s用6个属性去进行描述

参数说明

f: 文档唯一标识

w: 分片的频度,表示分片在一种切分过程中出现的次数

s: 分片

co: 分片的凝固度

fr: 分片的自由度

st: 分片的概率

3、词语分片的概率

分片的概率,如果一个字串S长度为L,按stepN进行切分,切分出来的集合为M,为每个分片的频度。那么每一个分片的概率可以用下面公式表示:

----------------------------------------------------------(1)

S="中国国家的中国队",长度N = 8 按step=2进行切分,切分为

M={中,国,家,的,队,中国,国国,国家,家的,的中,国队}。

分片 中 国 家 的 队 中国 国国 国家 家的 的中 国队
频次 2 3 1 1 1 2 1 1 1 1 1 15 P
总计 2/15 3/15 1/15 1/15 1/15 2/15 1/15 1/15 1/15 1/15 1/15 100%

4、分片的凝固度

要想从一段文本中抽出词来,我们的第一个问题就是,怎样的文本片段才算一个词?大家想到的第一个标准或许是,看这个文本片段出现的次数是否足够多。我们可以把所有出现频数超过某个阈值的片段提取出来,作为该语料中的词汇输出。不过,光是出现频数高还不够,一个经常出现的文本片段有可能不是一个词,而是多个词构成的词组。通过我们的数据分析,"的电影"出现了 389 次,"电影院"只出现了 175 次,然而我们却更倾向于把"电影院"当作一个词,因为直觉上看,"电影"和"院"凝固得更紧一些。

为了描述这个属性,我们用一下公式:

---------------------------------(2)

为分片的概率,分片对应的子分片的概率。

 分片"电影院"的概率P(电影院)=0.0005 电影院对应的子分片 {电影,院} 和{电,影院},

"的电影"的凝合程度则是 p(的电影) 分别除以 p(的) · p(电影) 和 p(的电) · p(影) 所得的商的较小值。

光看文本片段内部的凝合程度还不够,我们还需要从整体来看它在外部的表现。考虑"被子"和"辈子"这两个片段。我们可以说"买被子"、"盖被子"、"进被子"、"好被子"、"这被子"等等,在"被子"前面加各种字;但"辈子"的用法却非常固定,除了"一辈子"、"这辈子"、"上辈子"、"下辈子",基本上"辈子"前面不能加别的字了。"辈子"这个文本片段左边可以出现的字太有限,以至于直觉上我们可能会认为,"辈子"并不单独成词,真正成词的其实是"一辈子"、"这辈子"之类的整体。可见,文本片段的自由运用程度也是判断它是否成词的重要标准。如果一个文本片段能够算作一个词的话,它应该能够灵活地出现在各种不同的环境中,具有非常丰富的左邻字集合和右邻字集合。

二、信息熵和自由度

"信息熵"是一个非常神奇的概念,它能够反映知道一个事件的结果后平均会给你带来多大的信息量。如果某个结果的发生概率为 p ,当你知道它确实发生了,你得到的信息量就被定义为 - log(p) 。 p 越小,你得到的信息量就越大。

设U1…Ui…Un,对应概率为:P1…Pi…Pn,且各种符号的出现彼此独立。这时,信源的平均不确定性应当为单个符号不确定性-logPi的统计平均值(E),可称为信息熵,即

----------------------------------------------(3)

式中对数一般取2为底,单位为比特。

我们用信息熵来衡量一个文本片段的左邻字集合和右邻字集合有多随机。考虑这么一句话"吃葡萄不吐葡萄皮不吃葡萄倒吐葡萄皮","葡萄"一词出现了四次,其中左邻字分别为 {吃, 吐, 吃, 吐} ,右邻字分别为 {不, 皮, 倒, 皮} 。根据公式,"葡萄"一词的左邻字的信息熵为 - (1/2) · log(1/2) - (1/2) · log(1/2) ≈ 0.693 ,它的右邻字的信息熵则为 - (1/2) · log(1/2) - (1/4) · log(1/4) - (1/4) · log(1/4) ≈ 1.04 。可见,在这个句子中,"葡萄"一词的右邻字更加丰富一些。

我们不妨就把一个文本片段的自由运用程度定义为它的左邻字信息熵和右邻字信息熵中的较小值。

------------------------------------------(4)

通过信息熵算法,可以很好的区分一些专有名词像玫瑰、蝙蝠等,一些地名像新西兰、伦敦等,这些自由度较低的词汇的。

三、算法的构建

在实际运用中你会发现,文本片段的凝固程度和自由程度,两种判断标准缺一不可。只看凝固程度的话,程序会找出"巧克"、"俄罗"、"颜六色"、"柴可夫"等实际上是"半个词"的片段;只看自由程度的话,程序则会把"吃了一顿"、"看了一遍"、"睡了一晚"、"去了一趟"中的"了一"提取出来,因为它的左右邻字都太丰富了。
无词典分词法的基本步骤:

  1. 输入阀值参数 出现频数w、凝固程度co、自由程度fr和最大切片stepN,词典集合的大小N;
  2. 对文档集进行预处理,包括:编码转换、全半角 处理、字符转换,再将停用词、英文字母、数学运算符等其它非汉字字符用占位符替代;
  3. 从文档集里取一个文档D,按1,2,...,stepN进行切片形成切片集合S;
  4. 通过公式(1)计算切片集合S的每一个切片的频数W和概率P,通过给定频数阀值过滤;
  5. 结果4 中的长度>1的词语切片,通过公式(2)计算凝固程度,并通过给定的阀值参数过滤。
  6. 结果5 中的词语切片,通过公式(3)计算左邻右邻的信息熵,通过公式(4),得出词语切片的自由度,并通过给定的阀值参数过滤。
  7. 对于结果6,按照分片的频数倒排序,取前N个,就产生了我们需要的词典。

四、参考

《基于SNS的文本数据挖掘》http://www.matrix67.com/blog/archives/5044

17
Oct
0

排序插入单元bisect 及列表内存分配公式

bisect是一个用于对数组进行排序插入的单元,就是排好要插入的数据位置,再插入数据

有如下成员:
['__builtins__', '__cached__', '__doc__', '__file__', '__loader__', '__name__', '__package__', '__spec__', 'bisect', 'bisect_left', 'bisect_right', 'insort', 'insort_left', 'insort_right']

如有列表
data = [7,9,4,2,30]

1.insort成员:

插入一个6

bisect.insort(data,6)

返回

[7, 9, 4, 2, 6, 30]

说明它不对源数据进行排序
所以源数据,需要data.sort(),先进行一次排序

2.预插入函数:'bisect', 'bisect_left', 'bisect_right

假如要插入15

i = bisect.bisect(data,15)
print(i) # i = 5
代表插入的15会被放在下标为5的地方,但是data值仍然为[2, 4, 6, 7, 9, 30],所以并没有真的放进去
'bisect_left', 'bisect_right:分别为假如15是会重复的情况下,把15前在左边还是右边,并返回下标,
但在实际结果中看不出什么区别,但如果有其它,比如属性要求的情况下,就有很大的作用了
i = bisect.bisect(data,15)

  1. 'insort', 'insort_left', 'insort_right' 分别对应上面三个预插入函数,但插入时不返回下标
    如:

bisect.insort(data,6)
返回None

当列表新增需要增加大小时会产生复制导致效率低下
列表的内存分配公式 M = (N >> 3) + (N: < 9 ? 3 :6)

N 0 1-4 5-8 9-16 17-25 26-35 36-46 ... 991-1120

M 0 4 8 16 25 35 46 1120

字典和集合默认大小为8 每次改变大小时增加到原来的4倍 达到50000个元素后每次为原来的2倍
在删除时可能会变小 但只发生在插入时
8 32 128 512 2048 8192 32768 131072 262144

数字 int 和 float散列值是它们的数字比特值 字符串元组是基于他们的内容
自定义类通过默认 __hash__得到内建id函数返回内存中的位置 __cmp__比较也是内存位置的数字值

散列碰撞 导致不相等
自定义类判断类实例是否相等
def __eq__(self,other):
return self.x == other.x and self.y == other.y

12
May
0