EdmondFrank's 时光足迹

この先は暗い夜道だけかもしれない それでも信じて進むんだ。星がその道を少しでも照らしてくれるのを。
或许前路永夜,即便如此我也要前进,因为星光即使微弱也会我为照亮前途。
——《四月は君の嘘》

计算编辑距离(Levenshtein距离)

计算字符串的相似度(编辑距离)

Levenshtein 距离

Levenshtein距离,又称编辑距离,指的是两个字符串之间,由一个转换成另外一个所需的最少编辑量。 编辑距离算法首先由俄国科学家Levenshstance提出,原理可大致举例如下:

字符串A:abcdefg 字符串B:abcdef

以上两串字符串可以通过添加或是删除字符“g”的方式达到一致的目的。这两种方案都需要一次操作。

算法实现

此问题可以采用经典的动态规划求解。

计算两字符串的最长公共子序列相似

设Ai为字符串A(a1a2a3 … am)的前i个字符(即为a1,a2,a3 … ai) 设Bj为字符串B(b1b2b3 … bn)的前j个字符(即为b1,b2,b3 … bj)

设 L(i,j)为使两个字符串和Ai和Bj相等的最小操作次数。 当ai==bj时 显然

L(i,j) = L(i-1,j-1)

当ai!=bj时

若将它们修改为相等,则对两个字符串至少还要操作L(i-1,j-1)次 若删除ai或在bj后添加ai,则对两个字符串至少还要操作L(i-1,j)次 若删除bj或在ai后添加bj,则对两个字符串至少还要操作L(i,j-1)次 此时L(i,j) = min( L(i-1,j-1), L(i-1,j), L(i,j-1) ) + 1

所以,L(i,0)=i,L(0,j)=j, 再利用上述的递推公式,可以直接计算出L(i,j)值。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <string>
using namespace std;
int calcdistance(string,string);
int minvalue(int,int,int);
int main(int argc, char *argv[])
{
    string str1 ,str2;
    cout<<"Please input 2 strings:"<<endl;
    cin>>str1>>str2;
    cout<<str1<<endl;
    cout<<str2<<endl;
    cout<<calcdistance(str1,str2)<<endl;
    //cout << "Hello World!" << endl;
    return 0;
}
int calcdistance(string s1, string s2)
{
    int len1 = s1.size()+1;
    int len2 = s2.size()+1;
    if(len1==0)
        return len2;
    if(len2==0)
        return len1;

    int ** cnt = new int*[len1];
    for(int i=0;i<len1;i++)
        cnt[i]=new int[len2];

    for(int i=0;i<len1;i++)cnt[i][0]=i;
    for(int j=0;j<len2;j++)cnt[0][j]=j;
    //cnt[0][0] = 0;

    for(int i=1;i<len1;i++)
    {
        for(int j=1;j<len2;j++){
            if(s1[i-1]==s2[j-1])
                cnt[i][j]=cnt[i-1][j-1];
            else
            {
                cnt[i][j]=minvalue(cnt[i-1][j-1],
                        cnt[i-1][j],
                        cnt[i][j-1])+1;
            }
        }
    }
    int ret = cnt[len1-1][len2-1];
    for(int i=0;i<len1;i++)
        delete [] cnt[i];
    delete [] cnt;
    return ret;
}
int minvalue(int a, int b, int c){
 int t = a <=b ? a : b;
 return t <= c? t : c;
}

Vector版本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int calcdistance(string,string);
int main(int argc, char *argv[])
{
    string str1 ,str2;
    cout<<"Please input 2 strings:"<<endl;
    cin>>str1>>str2;
    cout<<str1<<endl;
    cout<<str2<<endl;
    cout<<calcdistance(str1,str2)<<endl;
    //cout << "Hello World!" << endl;
    return 0;
}
int calcdistance(string str1,string str2)
{
    int n = str1.size();
    int m = str2.size();
    if ( n == 0)
        return m;
    if ( m == 0)
        return n;
    vector<int> vec1(n+1);
    vector<int> vec2(m+1);
    for(int i=0;i<=n;i++)
        vec1[i] = i;
    int cost = 0;

    for(int i=1;i<=n;i++)
    {
        vec2[0] = i;
        for(int j=1;j<=m;j++)
        {
            if( str1[i-1] == str2[j-1] )
                cost = 0;
            else
                cost = 1;
            vec2[j] = vec2[j-1]+1 < vec1[j]+1 ? vec2[j-1]+1 : vec1[j]+1;
            vec2[j] = vec2[j] < vec1[j-1]+cost ? vec2[j] : vec1[j-1]+cost;
        }
        vec1 = vec2;
    }
    return vec2.back();
}

认识网络爬虫

认识网络爬虫

什么是网络爬虫

传统网络爬虫是一个自动提取网页的程序,它为搜索引擎从万维网上下载网页,是搜索引擎的重要组成。 一般从一个或若干初始网页的URL开始,获得初始网页上的URL,在抓取网页的过程中,不断从当前页面上抽取新的URL放入队列,直到满 足系统的一定停止条件。

爬虫有什么用?

随着现代商业元素的发展,网络爬虫也开始呈现出一种多元化发展的趋势,应用在各种不同的领域。例如:商业数据收集、科学数据采集、社会特征分析等等

  1. 通用搜索引擎网页搜集器
  2. 垂直搜索引擎(招聘网,二手车,买房网)
  3. 科学研究
  4. hacking ……

一个简单的python爬虫

1
2
3
4
5
6
7
8
9
10
11
12
13
#!/usr/bin/env python
#coding=utf-8
import requests
from pyquery import PyQuery as pq

url = 'http://zhixing.bjtu.edu.cn/portal.php'
r = requests.get(url)
print r.text
print r.content
p = pq(r.text).find('#portal_block_617 li>a')
for d in p:
    print pq(d).text()
    print 'http://zhixing.bjtu.edu.cn/'+pq(d).attr('href')

爬虫工作过程解析

网络爬虫框架主要由控制器、解析器和索引库三大部分组成,而爬虫工作原理主要是解析器这个环节,解析器的主要工作是下载网页,进行页面的处理,主要是将一些JS脚本标签、CSS代码内容、空格字符、HTML标签等内容处理掉,爬虫的基本工作是由解析器完成。所以解析器的具体流程是:

入口访问->下载内容->分析结构->提取内容

下面以爬取落网为例子

第一步 确定目的 抓取目标网站的某一期所有音乐

第二步 分析页面结构 访问落网的某一期刊,通过Chrome的(F12)开发者模式查看播放列表中的歌曲,右侧选中的是一些需要特别注意的语义结构,见下图所示:

这时我们可以看到在Chrome的开发者模式的Network中看到实际请求的播放文件。 根据以上分析我们可以得到播放清单的位置和音乐文件的路径,接下来我们通过Python来实现这个目的。

实现爬虫

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#-*- coding: utf-8 -*-
import os
import requests
from bs4 import BeautifulSoup
import random
from faker import Factory
import Queue
import threading

fake = Factory.create()
luoo_site = 'http://www.luoo.net/music/'
luoo_site_mp3 = 'http://luoo-mp3.kssws.ks-cdn.com/low/luoo/radio%s/%s.mp3'

headers = {'Connection': 'keep-alive',
    'User-Agent': fake.user_agent()
    }

def random_proxies():
    ip_index = random.randint(0, len(proxy_ips)-1)
    res = { 'http': proxy_ips[ip_index] }
    return res

def fix_characters(s):
    for c in ['<', '>', ':', '"', '/', '\\\\', '|', '?', '*']:
        s = s.replace(c, '')
    return s


class LuooSpider(threading.Thread):
    def __init__(self, url, vols, queue=None):
        threading.Thread.__init__(self)
        print '[luoo spider]'
        print '=' * 20
        self.url = url
        self.queue = queue
        self.vol = '1'
        self.vols = vols

    def run(self):
        for vol in self.vols:
            self.spider(vol)
        print '\\ncrawl end\\n\\n'
        def spider(self, vol):
        url = luoo_site + vol
        print 'crawling: ' + url + '\\n'
        res = requests.get(url, proxies=random_proxies())
                soup = BeautifulSoup(res.content, 'html.parser')
        title = soup.find('span', attrs={'class': 'vol-title'}).text
        cover = soup.find('img', attrs={'class': 'vol-cover'})['src']
        desc = soup.find('div', attrs={'class': 'vol-desc'})
        track_names = soup.find_all('a', attrs={'class': 'trackname'})
        track_count = len(track_names)
        tracks = []
        for track in track_names:
            _id = str(int(track.text[:2])) if (int(vol) < 12) else track.text[:2]
            _name = fix_characters(track.text[4:])
            tracks.append({'id': _id, 'name': _name})
            phases = {
                'phase': vol,                         # 期刊编号
                'title': title,                       # 期刊标题
                 'cover': cover,                      # 期刊封面
                 'desc': desc,                        # 期刊描述
                 'track_count': track_count,          # 节目数
                 'tracks': tracks                     # 节目清单(节目编号,节目名称)
            }
            self.queue.put(phases)


class LuooDownloader(threading.Thread):
    def __init__(self, url, dist, queue=None):
        threading.Thread.__init__(self)
        self.url = url
        self.queue = queue
        self.dist = dist
        self.__counter = 0

     def run(self):
        while True:
            if self.queue.qsize() <= 0:
                pass
            else:
                phases = self.queue.get()
                self.download(phases)

    def download(self, phases):
        for track in phases['tracks']:
            file_url = self.url % (phases['phase'], track['id'])

            local_file_dict = '%s/%s' % (self.dist, phases['phase'])
            if not os.path.exists(local_file_dict):
                os.makedirs(local_file_dict)

            local_file = '%s/%s.%s.mp3' % (local_file_dict, track['id'], track['name'])
            if not os.path.isfile(local_file):
                print 'downloading: ' + track['name']
                res = requests.get(file_url, proxies=random_proxies(), headers=headers)
                with open(local_file, 'wb') as f:
                    f.write(res.content)
                    f.close()
                print 'done.\\n'
            else:
                print 'break: ' + track['name']


if __name__ == '__main__':
    spider_queue = Queue.Queue()

    luoo = LuooSpider(luoo_site, vols=['680', '721', '725', '720'],queue=spider_queue)
    luoo.setDaemon(True)
    luoo.start()

    downloader_count = 5
    for i in range(downloader_count):
        luoo_download = LuooDownloader(luoo_site_mp3, '/home/luoo', queue=spider_queue)
        luoo_download.setDaemon(True)
        luoo_download.start()

中文分词的简介

中文分词的简介

一:中文分词是什么?

中文分词指的是将一个汉字序列切分成一个一个单独的词。 中文分词技术属于自然语言处理技术范畴,对于一句话,人可以通过自己的知识来明白哪些是词,哪些不是词,但如何让计算机也能理解?其处理过程就是分词算法。

二:为什么要进行中文分词?

词是最小的能够独立活动的有意义的语言成分,英文单词之间是以空格作为自然分界符的,而汉语是以字为基本的书写单位,词语之间没有明显的区分标记,因此,中文词语分析是中文信息处理的基础与关键。

中文分词对于搜索引擎来说,最重要的并不是找到所有结果,因为在上百亿的网页中找到所有结果没有太多的意义,没有人能看得完,最重要的是把最相关的结果排在最前面,这也称为相关度排序。中文分词的准确与否,常常直接影响到对搜索结果的相关度排序。

三:常用的中文分词算法及原理

分词算法大体上可分为三大类:(1)基于字典、词库匹配的分词方法(2)基于词频度统计的分词方法(3)基于知识理解的分词方法

(1)词典匹配:

词典匹配、汉语词法或其它汉语语言知识进行分词,如:最大匹配法、最小分词方法等。这类方法简单、分词效率较高,但汉语语言现象复杂丰富,词典的完备性、规则的一致性等问题使其难以适应开放的大规模文本的分词处理

最大正向匹配法:通常简称为MM法。其基本思想为:假定分词词典中的最长词有i个汉字字符,则用被处理文档的当前字串中的前i个字作为匹配字段,查找字典。若字典中存在这样的一个i字词,则匹配成功,匹配字段被作为一个词切分出来。如果词典中找不到这样的一个i字词,则匹配失败,将匹配字段中的最后一个字去掉,对剩下的字串重新进行匹配处理,如此进行下去,直到匹配成功,即切分出一个词或剩余字串的长度为零为止。这样就完成了一轮匹配,然后取下一个i字字串进行匹配处理,直到文档被扫描完为止。

由于汉语中偏正结构较多,若从后向前匹配,可以适当提高精确度。所以,逆向最大匹配法比正向最大匹配法的误差要小。

逆向最大匹配法:通常简称为RMM法。RMM法的基本原理与MM法相同 ,不同的是分词切分的方向与MM法相反,而且使用的分词辞典也不同。逆向最大匹配法从被处理文档的末端开始匹配扫描,每次取最末端的2i个字符(i字字串)作为匹配字段,若匹配失败,则去掉匹配字段最前面的一个字,继续匹配。相应地,它使用的分词词典是逆序词典,其中的每个词条都将按逆序方式存放。在实际处理时,先将文档进行倒排处理,生成逆序文档。然后,根据逆序词典,对逆序文档用正向最大匹配法处理即可。

最少切分法(最小分词法):使每一句中切出的词数最小。

(2)基于统计的分词算法:

统计模型则基于字和词的统计信息,把相邻字间的信息、词频及相应的共现信息通过条件概率分布模型应用于分词,由于这些信息是通过调查真实语料而取得的,因而基于统计的分词方法具有较好的实用性。

其中最具代表性的是:马尔可夫模型

四:常用中文分词工具(引擎)

  1. 结巴中文分词(多语言版本)
  2. Ansj中文分词(java)
  3. BosonNLP
  4. IKAnalyzer
  5. NLPIR
  6. SCWS中文分词
  7. 盘古分词
  8. 庖丁解牛
  9. 搜狗分词

大数据下的Hadoop

大数据下的Hadoop

(1) 什么是大数据概念? 大数据(big data,mega data),或称巨量资料,指的是需要新处理模式才能具有更强的决策力、洞察力和流程优化能力的海量、高增长率和多样化的信息资产。

(2) 常规的数据处理 * 数据的采集 * 明确数据处理的目的 * 数据清洗 : 统一数据格式、删除重复值、处理缺失字段、检查数据逻辑错误等 * 数据加工 : 数据抽取、数据计算、数据分组和数据转换等 * 数据抽样 数据处理完毕后,就可以进行数据分析了

(3) 主流的三大分布式计算系统

一.Hadoop 基于java

Hadoop采用MapReduce分布式计算框架,并根据GFS开发了HDFS分布式文件系统,根据BigTable开发了HBase数据存储系统。

二.Spark 基于scala

Spark也是Apache基金会的开源项目,它由加州大学伯克利分校的实验室开发,是另外一种重要的分布式计算系统。它在Hadoop的基础上进行了一些架构上的改良。Spark与Hadoop最大的不同点在于,Hadoop使用硬盘来存储数据,而Spark使用内存来存储数据,因此Spark可以提供超过Hadoop 100倍的运算速度。但是,由于内存断电后会丢失数据,Spark不能用于处理需要长期保存的数据。

三.Storm 基于clojure

Storm是Twitter主推的分布式计算系统,它由BackType团队开发,是Apache基金会的孵化项目。它在Hadoop的基础上提供了实时运算的特性,可以实时的处理大数据流。不同于Hadoop和Spark,Storm不进行数据的收集和存储工作,它直接通过网络实时的接受数据并且实时的处理数据,然后直接通过网络实时的传回结果。

然而,以上的平台的语言开发组件都有一个共同点,即,基于java的JVM

(4) 有关hadoop

Hadoop核心 HDFS和MapReduce

HDFS

HDFS(Hadoop Distributed File System,Hadoop分布式文件系统),它是一个高度容错性的系统,适合部署在廉价的机器上。HDFS能提供高吞吐量的数据访问,适合那些有着超大数据集(large data set)的应用程序。

HDFS的设计特点是:

  1. 大数据文件,非常适合上T级别的大文件或者一堆大数据文件的存储,如果文件只有几个G甚至更小就没啥意思了。
  2. 文件分块存储,HDFS会将一个完整的大文件平均分块存储到不同计算器上,它的意义在于读取文件时可以同时从多个主机取不同区块的文件,多主机读取比单主机读取效率要高得多得都。
  3. 流式数据访问,一次写入多次读写,这种模式跟传统文件不同,它不支持动态改变文件内容,而是要求让文件一次写入就不做变化,要变化也只能在文件末添加内容。
  4. 廉价硬件,HDFS可以应用在普通PC机上,这种机制能够让给一些公司用几十台廉价的计算机就可以撑起一个大数据集群。
  5. 硬件故障,HDFS认为所有计算机都可能会出问题,为了防止某个主机失效读取不到该主机的块文件,它将同一个文件块副本分配到其它某几个主机上,如果其中一台主机失效,可以迅速找另一块副本取文件。

HDFS的关键元素:

Block:将一个文件进行分块,通常是64M。

NameNode:保存整个文件系统的目录信息、文件信息及分块信息,这是由唯一一台主机专门保存,当然这台主机如果出错,NameNode就失效了。在Hadoop2.*开始支持activity-standy模式—-如果主NameNode失效,启动备用主机运行NameNode。

DataNode:分布在廉价的计算机上,用于存储Block块文件。

MapReduce

通俗说MapReduce是一套从海量·源数据提取分析元素最后返回结果集的编程模型,将文件分布式存储到硬盘是第一步,而从海量数据中提取分析我们需要的内容就是MapReduce做的事了。

下面以一个计算海量数据最大值为例:一个银行有上亿储户,银行希望找到存储金额最高的金额是多少,按照传统的计算方式,我们会这样:

1
2
3
4
5
6
7
8
//java
Long moneys[] ...
Long max = 0L;
for(int i=0;i<moneys.length;i++){
  if(moneys[i]>max){
    max = moneys[i];
  }
}

如果计算的数组长度少的话,这样实现是不会有问题的,还是面对海量数据的时候就会有问题。

MapReduce会这样做:首先数字是分布存储在不同块中的,以某几个块为一个Map,计算出Map中最大的值,然后将每个Map中的最大值做Reduce操作,Reduce再取最大值给用户。

MapReduce的基本原理就是:将大的数据分析分成小块逐个分析,最后再将提取出来的数据汇总分析,最终获得我们想要的内容。当然怎么分块分析,怎么做Reduce操作非常复杂,Hadoop已经提供了数据分析的实现,我们只需要编写简单的需求命令即可达成我们想要的数据。

总结

总的来说: Hadoop适合应用于大数据存储和大数据分析的应用,适合于服务器几千台到几万台的集群运行,支持PB级的存储容量。Hadoop典型应用有:搜索、日志处理、推荐系统、数据分析、视频图像分析、数据保存等。