0和1

至此，整个新闻搜索引擎构建完毕，总体效果令人满意，不过还是有很多可以改进的地方。下面总结一下本系统的优点和不足。 优点 倒排索引存储方式。因为不同词项的倒排记录表长度一般不同，所以没办法以常规的方式存入关系型数据库。通过将一个词项的倒排记录表序列化成一个字符串再存入数据库，读取的时候通过反序列化获得相关数据，整个结构类似于邻接表的形式。 推荐阅读实现方式。利用特征提取的方法，用25个关键词表示一篇新闻，大大减小了文档词项矩阵规模，提高计算效率的同时不影响推荐新闻相关性。 借用了Reddit的热度公式，融合了时间因素。 不足 构建索引时，为了降低索引规模，提高算法速度，我们将纯数字词项过滤了，同时忽略了词项大小写。虽然索引规模下降了，但是牺牲了搜索引擎的正确率。 构建索引时，采用了jieba的精确分词模式，比如句子“我来到北京清华大学”的分词结果为“我/ 来到/ 北京/ 清华大学”，“清华大学”作为一个整体被当作一个词项，如果搜索关键词是“清华”，则该句子不能匹配，但显然这个句子和“清华”相关。所以后续可以采用结巴的搜索引擎分词模式，虽然索引规模增加了，但能提升搜索引擎的召回率。 在推荐阅读模块，虽然进行了维度约减，但是当数据量较大时（数十万条新闻），得到的文档词项矩阵也是巨大的，会远远超过现有PC的内存大小。所以可以先对新闻进行粗略的聚类，再在类内计算两两cosine相似度，得到值得推荐的新闻。 在热度公式中，虽然借用了Reddit的公式，大的方向是正确的，但是引入了参数\(k_1\)和\(k_2\)，而且将其简单的设置为1。如果能够由专家给出或者经过机器学习训练得到，则热度公式的效果会更好。 完整可运行的新闻搜索引擎Demo请看我的Github项目news_search_engine。 以下是系列博客： 和我一起构建搜索引擎（一）简介 和我一起构建搜索引擎（二）网络爬虫 和我一起构建搜索引擎（三）构建索引 和我一起构建搜索引擎（四）检索模型 和我一起构建搜索引擎（五）推荐阅读 和我一起构建搜索引擎（六）系统展示 和我一起构建搜索引擎（七）总结展望

前几个博客已经介绍完搜索引擎的所有功能，为了实现更好的用户体验，需要一个web界面。这一部分是另一个队员做的，我这里借用他的代码。 我们利用开源的Flask Web框架搭建了展示系统，搜索引擎只需要两个界面，一个是搜索界面，另一个是展示详细新闻的页面（实际搜索引擎没有这个页面）。编写好这两个模板页面并调用前面给出的接口，得到数据，展示出来就可以。 这一部分没有太多需要讲解的算法，直接上效果图（点击图片可以查看大图）。 图1. 搜索页面 图2. 新闻详情页面 由于数据量不大，只有1000条新闻，所以第一页中后面几个结果相关度就不是很高了。但是经过测试，在大数据量的情况下，不论是搜索的速度、准确率、召回率以及推荐阅读的相关度，都达到了不错的效果。 完整可运行的新闻搜索引擎Demo请看我的Github项目news_search_engine。 以下是系列博客： 和我一起构建搜索引擎（一）简介 和我一起构建搜索引擎（二）网络爬虫 和我一起构建搜索引擎（三）构建索引 和我一起构建搜索引擎（四）检索模型 和我一起构建搜索引擎（五）推荐阅读 和我一起构建搜索引擎（六）系统展示 和我一起构建搜索引擎（七）总结展望

虽然主要的检索功能实现了，但是我们还需要一个“推荐阅读”的功能。当用户浏览某条具体新闻时，我们在页面底端给出5条和该新闻相关的新闻，也就是一个最简单的推荐系统。 搜狐新闻“相关新闻”模块 推荐模块的思路是度量两两新闻之间的相似度，取相似度最高的前5篇新闻作为推荐阅读的新闻。 我们前面讲过，一篇文档可以用一个向量表示，向量中的每个值是不同词项t在该文档d中的词频tf。但是一篇较短的文档（如新闻）的关键词并不多，所以我们可以提取每篇新闻的关键词，用这些关键词的tfidf值构成文档的向量表示，这样能够大大减少相似度计算量，同时保持较好的推荐效果。 jieba分词组件自带关键词提取功能，并能返回关键词的tfidf值。所以对每篇新闻，我们先提取tfidf得分最高的前25个关键词，用这25个关键词的tfidf值作为文档的向量表示。由此能够得到一个1000*m的文档词项矩阵M，矩阵每行表示一个文档，每列表示一个词项，m为1000个文档的所有互异的关键词（大概10000个）。矩阵M当然也是稀疏矩阵。 得到文档词项矩阵M之后，我们利用sklearn的pairwise_distances函数计算M中行向量之间的cosine相似度，对每个文档，得到与其最相似的前5篇新闻id，并把结果写入数据库。 推荐阅读模块的代码如下： 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 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 # -*- coding: utf-8 -*- """ Created on Wed Dec 23 14:06:10 2015 @author: bitjoy.net """ from os import listdir import xml.etree.ElementTree as ET import jieba import jieba.analyse import sqlite3 import configparser from datetime import * import math import pandas as pd import numpy as np from sklearn.metrics import pairwise_distances class RecommendationModule: stop_words = set() k_nearest = [] config_path = '' config_encoding = '' doc_dir_path = '' doc_encoding = '' stop_words_path = '' stop_words_encoding = '' idf_path = '' db_path = '' def __init__(self, config_path, config_encoding): self.config_path = config_path self.config_encoding = config_encoding config = configparser.ConfigParser() config.read(config_path, config_encoding) self.doc_dir_path = config['DEFAULT']['doc_dir_path'] self.doc_encoding = config['DEFAULT']['doc_encoding'] self.stop_words_path = config['DEFAULT']['stop_words_path'] self.stop_words_encoding = config['DEFAULT']['stop_words_encoding'] self.idf_path = config['DEFAULT']['idf_path'] self.db_path = config['DEFAULT']['db_path'] f = open(self.stop_words_path, encoding = self.stop_words_encoding) words = f.read() self.stop_words = set(words.split('\n')) def write_k_nearest_matrix_to_db(self): conn = sqlite3.connect(self.db_path) c = conn.cursor() c.execute("'DROP TABLE IF EXISTS knearest'") c.execute("'CREATE TABLE knearest(id INTEGER PRIMARY KEY, first INTEGER, second INTEGER, third INTEGER, fourth INTEGER, fifth INTEGER)'") for docid, doclist in self.k_nearest: c.execute("INSERT INTO knearest VALUES (?, ?, ?, ?, ?, ?)", tuple([docid] + doclist)) conn.commit() conn.close() def is_number(self, s): try: float(s) return True except ValueError: return False def construct_dt_matrix(self, files, topK = 200): jieba.analyse.set_stop_words(self.stop_words_path) jieba.analyse.set_idf_path(self.idf_path) M = len(files) N = 1 terms = {} dt = [] for i in files: root = ET.parse(self.doc_dir_path + i).getroot() title = root.find('title').text body = root.find('body').text docid = int(root.find('id').text) tags = jieba.analyse.extract_tags(title + '。' + body, topK=topK, withWeight=True) #tags = jieba.analyse.extract_tags(title, topK=topK, withWeight=True) cleaned_dict = {} for word, tfidf in tags: word = word.strip().lower() if word == '' or self.is_number(word): continue cleaned_dict[word] = tfidf if word not in terms: terms[word] = N N += 1 dt.append([docid, cleaned_dict]) dt_matrix = [[0 for i in range(N)] for j in range(M)] i =0 for docid, t_tfidf in dt: dt_matrix[i][0] = docid for term, tfidf in t_tfidf.items(): dt_matrix[i][terms[term]] = tfidf i += 1 dt_matrix = pd.DataFrame(dt_matrix) dt_matrix.index = dt_matrix[0] print('dt_matrix shape:(%d %d)'%(dt_matrix.shape)) return dt_matrix def construct_k_nearest_matrix(self, dt_matrix, k): tmp = np.array(1 – pairwise_distances(dt_matrix[dt_matrix.columns[1:]], metric = "cosine")) similarity_matrix = pd.DataFrame(tmp, index = dt_matrix.index.tolist(), columns = dt_matrix.index.tolist()) for i in similarity_matrix.index: tmp = [int(i),[]] j = 0 while j <= k: max_col = similarity_matrix.loc[i].idxmax(axis = 1) similarity_matrix.loc[i][max_col] = -1 if max_col != i: tmp[1].append(int(max_col)) #max column name j += 1 self.k_nearest.append(tmp) def gen_idf_file(self): files = listdir(self.doc_dir_path) n = float(len(files)) idf = {} for i in files: root = ET.parse(self.doc_dir_path + i).getroot() title = root.find('title').text body = root.find('body').text seg_list = jieba.lcut(title + '。' + body, cut_all=False) seg_list = set(seg_list) – self.stop_words for word in seg_list: word = word.strip().lower() if word == '' or self.is_number(word): continue if word not in idf: idf[word] = 1 else: idf[word] = idf[word] + 1 idf_file = open(self.idf_path, 'w', encoding = 'utf-8') for word, df in idf.items(): idf_file.write('%s %.9f\n'%(word, math.log(n / df))) idf_file.close() def find_k_nearest(self, k, topK): self.gen_idf_file() files = listdir(self.doc_dir_path) dt_matrix = self.construct_dt_matrix(files, topK) self.construct_k_nearest_matrix(dt_matrix, k) self.write_k_nearest_matrix_to_db() if __name__ == "__main__": print('—–start time: %s—–'%(datetime.today())) rm = RecommendationModule('../config.ini', 'utf-8') rm.find_k_nearest(5, 25) print('—–finish time: %s—–'%(datetime.today())) 这个模块的代码量最多，主要原因是需要构建文档词项矩阵，并且计算k邻居矩阵。矩阵数据结构的设计需要特别注意，否则会严重影响系统的效率。我刚开始把任务都扔给了pandas.DataFrame，后来发现当两个文档向量合并时，需要join连接操作，当数据量很大时，非常耗时，所以改成了先用python原始的list存储，最后一次性构造一个完整的pandas.DataFrame，速度比之前快了不少。 ...

构建好倒排索引之后，就可以开始检索了。 检索模型有很多，比如向量空间模型、概率模型、语言模型等。其中最有名的、检索效果最好的是基于概率的BM25模型。 给定一个查询Q和一篇文档d，d对Q的BM25得分公式为 $$BM25_{score}(Q,d)=\sum_{t\in Q}w(t,d)$$$$w(t,d)=\frac{qtf}{k_3+qtf}\times \frac{k_1\times tf}{tf+k_1(1-b+b\times l_d/avg\_l)}\times log_2\frac{N-df+0.5}{df+0.5}$$公式中变量含义如下： \(qtf\)：查询中的词频 \(tf\)：文档中的词频 \(l_d\)：文档长度 \(avg\_l\)：平均文档长度 \(N\)：文档数量 \(df\)：文档频率 \(b,k_1,k_3\)：可调参数 这个公式看起来很复杂，我们把它分解一下，其实很容易理解。第一个公式是外部公式，一个查询Q可能包含多个词项，比如“苹果手机”就包含“苹果”和“手机”两个词项，我们需要分别计算“苹果”和“手机”对某个文档d的贡献分数w(t,d)，然后将他们加起来就是整个文档d相对于查询Q的得分。 第二个公式就是计算某个词项t在文档d中的得分，它包括三个部分。第一个部分是词项t在查询Q中的得分，比如查询“中国人说中国话”中“中国”出现了两次，此时qtf=2，说明这个查询希望找到的文档和“中国”更相关，“中国”的权重应该更大，但是通常情况下，查询Q都很短，而且不太可能包含相同的词项，所以这个因子是一个常数，我们在实现的时候可以忽略。 第二部分类似于TFIDF模型中的TF项。也就是说某个词项t在文档d中出现次数越多，则t越重要，但是文档长度越长，tf也倾向于变大，所以使用文档长度除以平均长度\(l_d/avg\_l\)起到某种归一化的效果，\(k_1\)和\(b\)是可调参数。 第三部分类似于TFIDF模型中的IDF项。也就是说虽然“的”、“地”、“得”等停用词在某文档d中出现的次数很多，但是他们在很多文档中都出现过，所以这些词对d的贡献分并不高，接近于0；反而那些很稀有的词如”糖尿病“能够很好的区分不同文档，这些词对文档的贡献分应该较高。 所以根据BM25公式，我们可以很快计算出不同文档t对查询Q的得分情况，然后按得分高低排序给出结果。 下面是给定一个查询句子sentence，根据BM25公式给出文档排名的函数 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 def result_by_BM25(self, sentence): seg_list = jieba.lcut(sentence, cut_all=False) n, cleaned_dict = self.clean_list(seg_list) BM25_scores = {} for term in cleaned_dict.keys(): r = self.fetch_from_db(term) if r is None: continue df = r[1] w = math.log2((self.N - df + 0.5) / (df + 0.5)) docs = r[2].split('\n') for doc in docs: docid, date_time, tf, ld = doc.split('\t') docid = int(docid) tf = int(tf) ld = int(ld) s = (self.K1 * tf * w) / (tf + self.K1 * (1 - self.B + self.B * ld / self.AVG_L)) if docid in BM25_scores: BM25_scores[docid] = BM25_scores[docid] + s else: BM25_scores[docid] = s BM25_scores = sorted(BM25_scores.items(), key = operator.itemgetter(1)) BM25_scores.reverse() if len(BM25_scores) == 0: return 0, [] else: return 1, BM25_scores 首先将句子分词得到所有查询词项，然后从数据库中取出词项对应的倒排记录表，对记录表中的所有文档，计算其BM25得分，最后按得分高低排序作为查询结果。 ...

目前正是所谓的“大数据”时代，数据量多到难以计数，怎样结构化的存储以便于分析计算，是当前的一大难题。上一篇博客我们简单抓取了1000个搜狐新闻数据，搜索的过程就是从这1000个新闻中找出和关键词相关的新闻来，那么怎样快速搜索呢，总不可能依次打开xml文件一个字一个字的找吧，这时就需要借助倒排索引这个强大的数据结构。 在讲倒排索引之前，我们先介绍一下布尔检索。布尔检索只是简单返回包含某个关键词的文档，比如查询“苹果手机”，则返回所有包含“苹果”和“手机”关键词的文档，布尔检索并不对返回结果排序，所以有可能返回的第一个文档是“某个男孩边吃苹果边玩手机…“。 实现布尔检索并不难，我们需要构建一个如下图的词项文档矩阵： 图1. 布尔检索中的词项文档矩阵 每行对应一个词项，每列对应一个文档，如果该值为1，表示该行词项出现在该列文档中。比如词项”苹果“出现在doc1和doc3文档中，如果我们要找同时出现”苹果“和”手机“的文档，只需把他们对应的向量取出来进行”与“操作，此为101&011=001，所以doc3同时出现了”苹果“和”手机“两个关键词，我们将其返回。 布尔检索虽然很快，但是它也有很多缺陷，比如不能对结果排序，词项只有出现和不出现两种状态，但是一篇文档中出现10次“苹果“和只出现1次”苹果“，他们的相关度肯定是不相同的。所以需要对布尔检索进行改进。 在扫描文档时，不但记录某词项出现与否，还记录该词项出现的次数，即词项频率(tf)；同时我们记录该文档的长度(ld)，以及某词项在不同文档中出现的次数，即文档频率(df)。 图2. 倒排索引结构图 这样我们就得到了如上图的倒排索引。左边部分被称为词典，存储的是1000个新闻中所有不同的词项；右边部分被称为倒排记录表，存储的是出现Term_i的那些文档信息。倒排索引中存储的变量都是为了给后续检索模型使用。 讲到这里，我们需要解决如下几个问题。 怎样得到一篇文档中的所有词项。给我们一篇新闻稿子，人类很容易分辨出”苹果“和”手机“是两个不同的词项，但是计算机怎么知道是这两个词呢？为什么不是”苹”、”国手“和”机“呢？这就需要进行中文分词，我们可以借助开源的jieba中文分词组件来完成，jieba分词能够将一个中文句子切成一个个词项，这样我们就可以统计tf, df了。 有些词，如”的“、”地“、”得“、”如果“等，几乎每篇文档都会出现，他们起不到很好的区分文档的效果，这类词被称为”停用词“，我们需要把他们去掉。去停词的步骤可以在jieba分词之后完成。 怎样存储倒排记录表。假设1000个文档共有20000个不同的词项，如果用类似图1的矩阵形式存储，需要耗费100020000=210^7个存储单元，但是图1往往是一个稀疏矩阵，因为一个文档中可能只出现了200个不同的词项，剩余的19800个词项都是空的。用矩阵方式存储时空效率都不高。所以我们可以采用图2的方式，词典用B-树或hash存储，倒排记录表用邻接链表存储方式，这样能大大减少存储空间。如果我们要将图2保存到数据库，可以对倒排记录表序列化成一个长的字符串，写入到一个单元格，读取的时候再反序列化。比如每个Doc内部用’\t’连接，Doc之间用’\n’连接，读取的时候split即可。 倒排索引构建算法使用内存式单遍扫描索引构建方法（SPIMI），其实就是依次对每篇新闻进行分词，如果出现新的词项则插入到词典中，否则将该文档的信息追加到词项对应的倒排记录表中。SPIMI的伪代码如下： 图3. SPIMI算法伪代码 下面是构建索引的所有代码： 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 # -*- coding: utf-8 -*- """ Created on Sat Dec 5 23:31:22 2015 @author: bitjoy.net """ from os import listdir import xml.etree.ElementTree as ET import jieba import sqlite3 import configparser class Doc: docid = 0 date_time = '' tf = 0 ld = 0 def __init__(self, docid, date_time, tf, ld): self.docid = docid self.date_time = date_time self.tf = tf self.ld = ld def __repr__(self): return(str(self.docid) + '\t' + self.date_time + '\t' + str(self.tf) + '\t' + str(self.ld)) def __str__(self): return(str(self.docid) + '\t' + self.date_time + '\t' + str(self.tf) + '\t' + str(self.ld)) class IndexModule: stop_words = set() postings_lists = {} config_path = '' config_encoding = '' def __init__(self, config_path, config_encoding): self.config_path = config_path self.config_encoding = config_encoding config = configparser.ConfigParser() config.read(config_path, config_encoding) f = open(config['DEFAULT']['stop_words_path'], encoding = config['DEFAULT']['stop_words_encoding']) words = f.read() self.stop_words = set(words.split('\n')) def is_number(self, s): try: float(s) return True except ValueError: return False def clean_list(self, seg_list): cleaned_dict = {} n = 0 for i in seg_list: i = i.strip().lower() if i != '' and not self.is_number(i) and i not in self.stop_words: n = n + 1 if i in cleaned_dict: cleaned_dict[i] = cleaned_dict[i] + 1 else: cleaned_dict[i] = 1 return n, cleaned_dict def write_postings_to_db(self, db_path): conn = sqlite3.connect(db_path) c = conn.cursor() c.execute("'DROP TABLE IF EXISTS postings'") c.execute("'CREATE TABLE postings(term TEXT PRIMARY KEY, df INTEGER, docs TEXT)'") for key, value in self.postings_lists.items(): doc_list = '\n'.join(map(str,value[1])) t = (key, value[0], doc_list) c.execute("INSERT INTO postings VALUES (?, ?, ?)", t) conn.commit() conn.close() def construct_postings_lists(self): config = configparser.ConfigParser() config.read(self.config_path, self.config_encoding) files = listdir(config['DEFAULT']['doc_dir_path']) AVG_L = 0 for i in files: root = ET.parse(config['DEFAULT']['doc_dir_path'] + i).getroot() title = root.find('title').text body = root.find('body').text docid = int(root.find('id').text) date_time = root.find('datetime').text seg_list = jieba.lcut(title + '。' + body, cut_all=False) ld, cleaned_dict = self.clean_list(seg_list) AVG_L = AVG_L + ld for key, value in cleaned_dict.items(): d = Doc(docid, date_time, value, ld) if key in self.postings_lists: self.postings_lists[key][0] = self.postings_lists[key][0] + 1 # df++ self.postings_lists[key][1].append(d) else: self.postings_lists[key] = [1, [d]] # [df, [Doc]] AVG_L = AVG_L / len(files) config.set('DEFAULT', 'N', str(len(files))) config.set('DEFAULT', 'avg_l', str(AVG_L)) with open(self.config_path, ‘w’, encoding = self.config_encoding) as configfile: config.write(configfile) self.write_postings_to_db(config[‘DEFAULT’][‘db_path’]) if __name__ == "__main__": im = IndexModule('../config.ini', 'utf-8') im.construct_postings_lists() 运行之后会在./data/下生成一个ir.db数据库文件，这就是构建好的索引数据库。 ...

网络爬虫又称网络蜘蛛、Web采集器等，它是一种按照一定的规则，自动地抓取万维网信息的程序或者脚本。 我们在设计网络爬虫的时候需要注意两点： 鲁棒性。Web中有些服务器会制造采集器陷阱（spider traps），这些陷阱服务器实际上是Web页面的生成器，它能在某个域下生成无数网页，从而使采集器陷入到一个无限的采集循环中去。采集器必须能从这些陷阱中跳出来。当然，这些陷阱倒不一定都是恶意的，有时可能是网站设计疏忽所导致的结果。 礼貌性。Web服务器具有一些隐式或显式的政策来控制采集器访问它们的频率。设计采集器时必须要遵守这些代表礼貌性的访问政策。 采集器的基本架构如下图所示。 基本上是“抓取→分析→得到新的URL→再抓取→再分析”这样一个死循环过程。 以上内容摘自王斌老师翻译的《信息检索导论》课本。 由于我们要做的是一个新闻搜索引擎，所以抓取的是新闻数据，对于爬虫，网上也有很多的开源程序，如nutch等，Github上还有人专门开发了抓取新闻的组件newspaper，可以很方便的提取新闻标题、正文、时间等信息。不过用python写爬虫也是分分钟的事情，下面我们一起来试一试。 首先找一个新闻网站，为简单起见，要找那种结构清晰、html代码便于解析的门户网站，比如搜狐新闻、参考消息等。 搜狐新闻的国内要闻列表如下： 结构非常清楚，左边是带URL的标题，右边括号里有新闻时间。这一页列表就有200条新闻，如果我们要获取1000条，只要不断模拟点击下一页即可。下一页的URL也只是在首页的基础上加上_xxx.shtml，xxx就是不同的页码。 查看列表的html源码，得知列表都在类名为newsblue1的td中，所以只需要解析html源码就可以得到新闻标题、URL和时间，python解析html可以用BeautifulSoup包，非常方便。 进入到新闻详细页面，正文部分如下： 查看html源码，正文位于类名为text clear的div中，据此可以很方便的提取新闻正文。 得到一条新闻的所有数据之后，我们需要将之结构化成xml文件，借助相应的xml包可以很方便的完成这项工作。xml格式定义如下： 注意爬虫需要访问网络，难免会出现一些异常，所以捕获异常是非常有必要的。另外，搜狐每篇新闻正文后面都会有一段’//’开始的注释，这个需要过滤掉，短于140个字的新闻我也过滤掉了。整个搜索系统的配置参数都存储在config.ini文件中。 下面是完整的python 3.4+代码。 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 # -*- coding: utf-8 -*- """ Created on Sat Dec 19 11:57:01 2015 @author: bitjoy.net """ from bs4 import BeautifulSoup import urllib.request import xml.etree.ElementTree as ET import configparser def get_news_pool(root, start, end): news_pool = [] for i in range(start,end,-1): page_url = '' if i != start: page_url = root +'_%d.shtml'%(i) else: page_url = root + '.shtml' try: response = urllib.request.urlopen(page_url) except Exception as e: print("—–%s: %s—–"%(type(e), page_url)) continue html = response.read() soup = BeautifulSoup(html) td = soup.find('td', class_ = "newsblue1") a = td.find_all('a') span = td.find_all('span') for i in range(len(a)): date_time = span[i].string url = a[i].get('href') title = a[i].string news_info = ['2016-'+date_time[1:3]+'-'+date_time[4:-1]+':00',url,title] news_pool.append(news_info) return(news_pool) def crawl_news(news_pool, min_body_len, doc_dir_path, doc_encoding): i = 1 for news in news_pool: try: response = urllib.request.urlopen(news[1]) except Exception as e: print("—–%s: %s—–"%(type(e), news[1])) continue html = response.read() soup = BeautifulSoup(html) try: body = soup.find('div', class_ = "text clear").find('div').get_text() except Exception as e: print("—–%s: %s—–"%(type(e), news[1])) continue if '//' in body: body = body[:body.index('//')] body = body.replace(" ", "") if len(body) <= min_body_len: continue doc = ET.Element("doc") ET.SubElement(doc, "id").text = "%d"%(i) ET.SubElement(doc, "url").text = news[1] ET.SubElement(doc, "title").text = news[2] ET.SubElement(doc, "datetime").text = news[0] ET.SubElement(doc, "body").text = body tree = ET.ElementTree(doc) tree.write(doc_dir_path + "%d.xml"%(i), encoding = doc_encoding, xml_declaration = True) i += 1 if __name__ == '__main__': config = configparser.ConfigParser() config.read('../config.ini', 'utf-8') root = 'http://news.sohu.com/1/0903/61/subject212846158' news_pool = get_news_pool(root, 854, 849) crawl_news(news_pool, 140, config['DEFAULT']['doc_dir_path'], config['DEFAULT']['doc_encoding']) print('done!') 完整可运行的新闻搜索引擎Demo请看我的Github项目news_search_engine。 ...

我们上网用得最多的一项服务应该是搜索，不管大事小情，都喜欢百度一下或谷歌一下，那么百度和谷歌是怎样从浩瀚的网络世界中快速找到你想要的信息呢，这就是搜索引擎的艺术，属于信息检索的范畴。 这学期学习了《现代信息检索》课程，使用的是Stanford的教材Introduction to Information Retrieval，网上有电子版，大家可以参考。 本课程的大作业是完成一个新闻搜索引擎，要求是这样的：定向采集3-4个新闻网站，实现这些网站信息的抽取、索引和检索。网页数目不少于10万条。能按相关度、时间和热度（需要自己定义）进行排序，能实现相似新闻的自动聚类。 截止日期12月31日，我们已经在规定时间完成了该系统，自认为检索效果不错，所以在此把过程记录如下，欢迎讨论。 网上有很多开源的全文搜索引擎，比如Lucene、Sphinx、Whoosh等，都提供了很好的API，开发者只需要调用相关接口就可以实现一个全功能的搜索引擎。不过既然学习了IR这门课，自然要把相关技术实践一下，所以我们打算自己实现一个搜索引擎。 这是简介部分，主要介绍整个搜索引擎的思路和框架。 上图为本搜索引擎的框架图。首先爬虫程序从特定的几个新闻网站抓取新闻数据，然后过滤网页中的图片、视频、广告等无关元素，抽取新闻的主体内容，得到结构化的xml数据。然后一方面使用内存式单遍扫描索引构建方法（SPIMI）构建倒排索引，供检索模型使用；另一方面根据向量空间模型计算两两新闻之间的余弦相似度，供推荐模块使用。最后利用概率检索模型中的BM25公式计算给定关键词下的文档相关性评分，BM25打分结合时间因素得到热度评分，根据评分给出排序结果。 在后续博文中，我会详细介绍每个部分的实现。 完整可运行的新闻搜索引擎Demo请看我的Github项目news_search_engine。 以下是系列博客： 和我一起构建搜索引擎（一）简介 和我一起构建搜索引擎（二）网络爬虫 和我一起构建搜索引擎（三）构建索引 和我一起构建搜索引擎（四）检索模型 和我一起构建搜索引擎（五）推荐阅读 和我一起构建搜索引擎（六）系统展示 和我一起构建搜索引擎（七）总结展望

安装WIN10一个月以来，校园有线网经常间歇性断网，通常是20分钟不到就断了，需要重启或者把有线连接关闭再打开才可以。在微博上问过微软客服也无果，后来Google到某国外的解决办法，现记录如下。 说到底WIN10断网的问题还是和驱动有关，先看一下我的有线网卡Broadcom NetLink (TM) Gigabit Ethernet，驱动信息是这样的： 还是13年的驱动，版本号是15.6.0.14，于是第一想到的是更新驱动。点击驱动右键选更新->自动搜索更新的驱动程序软件->提示“已安装适合设备的最佳驱动程序软件”，但这明明不是最新的驱动啊！ 于是在Broadcom的官网上找到了最新驱动win_b57_x64-17.2.0.2，版本号是17.2.0.2，更新日期2015-10-27，原来这才是最新的驱动。 （2018.1.25更新：上面的地址已失效，最新地址请点击此处，并选择DOWNLOADS→Software→NetLink®/NetXtreme® I Desktop/Mobile/Server (x64)，也可以从本站下载。） 在安装最新驱动之前，我们需要关闭WIN10的自动更新驱动功能，因为WIN10会认为它的15.6.0.14版本是最新的，在windows update时把实际最新的17.2.0.2版本替换掉。具体做法是在Cortana中搜索“更改设备安装设置”并打开，选择否，从不安装来自Windows更新的驱动程序软件，如下。 然后重启进入安全模式，再次在设备管理器中右键点击网卡驱动，选择更新->浏览计算机以查找驱动程序软件->从计算机的设备驱动程序列表中选取->点击从磁盘安装按钮->浏览找到你之前在网上下载的最新驱动（*.inf格式）->选中->依次确定。刷新之后再次查看驱动信息如下： 可以看到驱动已经更新到最新的版本了。再次重启进入正常模式，目前用了两天了也没有再断过网。 其他WIN10驱动问题应该也可以用类似的方法解决。 （话说我的WIN10偶尔会死机，就是用着用着突然鼠标和键盘完全动不了了，只能强制重启，有谁知道这是怎么回事吗？）

进入研究生生涯完成的第一个新生培训作业是“2.5亿个浮点数的外部排序算法”，前后折腾了将近一个月，结果是在i7处理器上，限制512MB内存，排序用时250秒左右。 这个作业的常规思路大部分人都能想到，按块读取文件->atof转换为double->内部快速排序或基数排序->dtoa转换为char*->按块写入文件。这里面中间的三个过程都很耗时，特别是atof和dtoa，因为精度只要求保留9位小数，所以可以自己实现atof和dtoa来加速，也可以使用多线程加速。 整个作业都是基于对IEEE754浮点数的深刻理解展开的，所以下面详细讲解浮点数的一些知识。 IEEE754双精度浮点数 目前大多数CPU内浮点数的表示都遵循IEEE754标准，IEEE754双精度浮点数（double）表示如下图所示。 IEEE754 double在内存中的形式[1] sign bit：符号位，1位，用来表示正负号，0表示非负；1表示负 exponent：指数位，11位，用来表示次方数，是一个无符号数 fraction：尾数位，52位，用来表示精确度，也是一个无符号数，有些资料也叫做mantissa或significand 这种表示形式有两点需要注意。 第一，既然exponent是无符号的，那么怎样表示负指数呢？ IEEE754规定，二进制串中算得的e需要减去一个偏移量bias，对于double，bias=1023，即e’=e-bias。因为\(e\in[0,2^{11}-1]\)，所以最终\(e’\in[-2^{10}+1,2^{10}]\)。但是如果把e本身看作有符号数e”，则\(e”\in[-2^{10},2^{10}-1]\)，既然e”和e’相差微小，为什么不直接把e看成有符号数，而非要把它看成无符号数，再减去一个偏移量bias呢？ 这是因为如果把e看成无符号数再减偏移量，浮点数大小比较速度更快。引用维基百科的一段话： By arranging the fields so that the sign bit is in the most significant bit position, the biased exponent in the middle, then the mantissa in the least significant bits, the resulting value will be ordered properly, whether it’s interpreted as a floating point or integer value. This allows high speed comparisons of floating point numbers using fixed point hardware. ...

去年暑假在北大计算所实习的时候，任务之一就是批量下载百度图片。当时没学python，用c#实现了一个简易版本的批量下载器，如下图。 C#版本百度图片批量下载器（抓的是百度的wap站点，现在好像不能用了） 当时“时间紧，任务重“，既没仔细研究百度图片API，也没处理好界面线程阻塞的问题。这个问题其实很有意思，趁着暑假在家，实现了一个比较完美的python版本，先上效果图。 python3版本百度图片批量下载器 新版使用了python-3.4.3.amd64.msi + PyQt5-5.5-gpl-Py3.4-Qt5.5.0-x64.exe + eric6-6.0.8.zip + cx_Freeze-4.3.4-cp34-none-win_amd64.whl，完整项目在我的GitHub上。大致有如下几点工作： 研究百度图片API，获取原始图片URL列表 使用python3进行多线程下载 利用pyqt5实现界面 利用cx_Freeze4打包整个程序 下面记录每个步骤的要点，供后人参考。 百度图片API 正常使用百度图片搜索的时候，URL是这样的： http://image.baidu.com/search/index?ct=201326592&z=0&tn=baiduimage&ipn=r&word=%E6%AD%A6%E6%B1%89%E5%A4%A7%E5%AD%A6&pn=0&istype=2&ie=utf-8&oe=utf-8&cl=2&lm=-1&st=-1&fr=&fmq=1439374041843_R&ic=0&se=&sme=&width=0&height=0&face=0 里面有很多参数，有些我们并不需要，精简之后大概是这样的： http://image.baidu.com/i?tn=baiduimage&ie=utf-8&word=%E7%BE%8E%E5%A5%B3&pn=&rn=&z= word为搜索关键词；pn为page number当前是第几页，实际含义是image id，表示第几张图片，从0开始；rn为每一页的图片数量，最大为60；z表示图片尺寸，z=9特大尺寸，z=3大尺寸，z=2中等尺寸，z=1小尺寸，z=0所有尺寸。 但是这个URL是给”人“看的，下一页的图片是动态加载的，其html代码的图片URL数量固定。一番查询之后发现，将tn=baiduimage换成tn=resultjson_com能获取到所有图片URL的json，json当然是给”猴“看的，这样就能轻松获取到所有图片的URL。 慢着，仔细看看json中的objURL，是一串连”猴“都看不懂的字符串，原来百度把图片真实URL加密了，好在加密方法是简单的字符映射，参考这篇博客成功解密。 更新：tn=resultjson_com的objURL是加密了，但是tn=resultjson的objURL并没有加密，所以采用tn=resultjson最佳。 通过控制pn和rn就能获取指定数量的图片URL，但是我发现rn最大只能为60，并且不同的pn可能会有相同的图片url（比如pn=0和pn=1都有ippr_z2C$qAzdH3FAzdH3Fooo_z&e3Bd8vs7k_z&e3Bv54_z&e3BvgAzdH3F7rs5w1utsjAzdH3Fda8nAzdH3Fa080AzdH3Fda8na080aldm9bb8m_z&e3B3r2这个objURL），所以使用python的集合（set）去重。 更新：pn实际上指图片的id，pn=0、rn=60能获取到从0~59这60个URL列表，pn=1、rn=60能获取到从1~60这60个URL列表，所以pn=0和pn=1的列表中当然有59个是重复的。正确的做法是pn=0、rn=60获取0~59这60个URL列表，然后pn=60、rn=60获取60~119这60个列表，以此类推，这样获取到的URL就不会有重复的了。 获取图片URL列表的简要代码如下： 1 2 3 4 5 6 7 8 9 10 11 def ParseJSON(self, pn, rn, st): url = 'http://image.baidu.com/i?tn=resultjson_com&amp;amp;ie=utf-8&amp;amp;word=%s&amp;amp;pn=%d&amp;amp;rn=%d&amp;amp;z=%d'%(self.word, pn, rn, self.size) #print(url) request = urllib.request.Request(url = url, headers = my_header) html = urllib.request.urlopen(request).read() hjson = json.loads(html.decode('gbk')) for i in range(0, len(hjson['data'])-1):#最后一个数据为空 img_url = self.DecodeURL(hjson['data'][i]['objURL']) if img_url not in st: st.add(img_url)#去重 self.progressBar_updated_signal.emit()#更新进度条 DecodeURL是解密函数。很奇怪，json最后一个数据是空的。 ...