垂直搜索引擎是针对某一特定领域、人群或需求提供的信息检索服务因此垂直搜索引擎的爬虫在 抽取数据时应该具有相当的选择性 。DIPRE(DualIterativePatternRelationExtraction)是 Google创始人之一SergeyBrin针对抽取互联网上特定格式或类型的数据而提出的一种算法，由于垂直搜索引擎具有较强的专业性和针对性，因而DIPRE算法在垂直搜索领域里具有较为广阔的应用前景。
互联网是巨大的信息资源，同时它的分布非常分散。特定类型的数据（例如餐厅清单）可能散布在成千上万种不同格式的独立信息源中。我们考虑了以下问题：从所有这些来源中自动提取此类数据类型的关系，我们提出了一种利用模式和关系集之间的对偶关系，从小样本开始发展目标关系的技术。要测试我们的技术，我们使用它来提取关系万维网上的作者标题对。
万维网可以提供几乎所有类型的信息，从 DNA 数据库到履历再到喜欢的餐馆列表。但是，这些信息通常会散布在许多使用不同格式的 Web 服务器和主机中。如果可以从中提取这些信息，将其整合为结构化形式，它们将形成前所未有的信息来源。它将包括最大的国际人员目录，最大，最多样化的产品数据库，最大的学术著作目录和许多其他有用资源。
在仔细阅读论文原文及一些参考文献后，为了实现论文中所描述的代码，对论文中需要深刻理解的地方和需要用到的数据结构做了记录，并归纳总结如下。
根据原文：Let D be a large database of unstructured information such as the World Wide Web.这里所指的非结构化信息的大型数据库实际上就是我们的信息源，它包含的是庞大的网页URL地址及其内容，而其内容应该是带有标签的网页源代码，我们需要在其中通过元组及关系对目标进行提取。
其次是了解了模式、事件、种子三者的概念及其构成：
原文描述了一些关于模式的错误率、查全率等概念，但是首先需要了解的是模式的构成，原文中：We dened a pattern as a ve-tuple: (order, urlprex, prefix, middle, suffix)
也就是：（标题作者的顺序、URL前缀、前缀、中缀、后缀）
利用该模式在数据库中进行搜寻，如果一个网页的URL符合模式中的URL前缀，则构造正则表达式对该网页进行搜寻，可以采用如下正则表达式构造方法：前缀(.*?)中缀(.?*)后缀。而顺序（order）是最容易被忽略的部分，他的作用是利用正则表达式匹配到元素后，如果order等于0说明作者在前标题在后，也就是利用正则表达式匹配到的第一个括号内的内容是作者，第二个括号内的内容是标题。反之亦然。
原文中提到事件：We also have to define how an occurrence is structured since it should have a correspondance to the denition of a pattern. An occurrence of an (author,title) pair consists of a seven-tuple: (author, title, order, url, prefix, middle, suffix)
事件的形成是利用种子进行搜索的时候对搜索到元组的位置进行记录，并记录下一些相关信息，这里的作者和标题显然就是所用到的种子，order是作者和标题出现的顺序，文章中是order为真的时候表示作者在前标题在后，url是出现种子的网页的url地址，prefix(suffix)可以默认记录作者(标题)前(后)的m个字符，middle即为作者和标题中间的字符串。
这里所提到的种子，在初始化的时候是通过手动创建的一些元组，以便利用这些元组生成事件从而形成模式，而后续通过模式搜索到的元组便可以加入到种子中来，进行下一轮的搜索。
上述对模式、事件及种子的说明基本告知了它们的具体用法，而为了形成模式，首先要查找到一系列的事件，而事件的形成方法在上面已经有说明，如下为通过事件形成模式的过程：
1、验证所有查询结果即事件（occurrences）中的作者标题出现顺序（order）和中间字符串（middle）是否相同，如果都不同则无法形成模式，否则将相同的order和middle作为一个输出模式的一部分（此处指的查询结果occurrences应该指的是所有种子查询的结果集，而非一个种子查询的结果）
2、寻找所有url中最长匹配的前缀，作为输出模式的url前缀（urlprefix）
3、将输出模式的前缀设置为事件前缀中最长匹配的后缀（大致意思是，比如搜索结果中作者前的所有字符串中，匹配最长的后缀，将其作为输出模式的前缀）
4、将输出模式的后缀设置为事件后缀中最长匹配的前缀
而原文中还引用到了模式的特异性，用以约束模式的形成结果：A pattern generated like the above can be too general or too specific, the pattern may be too general and may produce many nonbooks.简单来说，就是形成的模式中的前缀、中缀、后缀和url前缀都不能为空，否则则拒绝该模式，这在编写代码的时候会比较容易理解，因为如果一个模式前缀为空，就不能构造有效的正则表达式。
论文中还说明了一些查全率、查准率、覆盖率等，以及一些优化方案，但在实际应用中都不太好实现，所以并不在此赘述，在之前对论文和相关参考文献的阅读中也做了一些笔记，笔记如下：
第一次原文阅读记录：https://blog.csdn.net/qq_39591838/article/details/102096581
第二次原文阅读记录：https://blog.csdn.net/qq_39591838/article/details/102489385
参考文献阅读记录：https://blog.csdn.net/qq_39591838/article/details/102489459
实现方案分为四步：数据源的获取，形成事件、形成模式、利用模式搜索元组，下面说明实现这些步骤的关键代码。
首先是数据来源的获取，由于我们没有非结构化信息的大型数据库，所以我采用编写爬虫的方法，选择性的获取网页及网页内容：
import requests from bs4 import BeautifulSoup def CrawlWeb(path): # 利用爬虫获取URL中body的内容： html = requests.get(path) soup = BeautifulSoup(html.text) body = soup.body return str(body) # 这里一定要注意转化成字符串，不然返回的是soup对象由于我使用的是mysql数据库，text字段不一定能存储下一个网页的所有源代码，所以我选择只存储一个网页的url，在使用到的时候再通过爬虫进行获取。
为了形成事件，首先需要一定量的初始种子，然后利用种子在网页中进行查找，我们先假设在一个页面中查询一个种子（即一对元组）并得到事件，编写如下代码：
def SearchSeedInPage(author,title,url,line): # 在文章中搜索一个种子的元组对并记录事件 occurrence = {} if author in line and title in line: # 作者和标题都在该行则记录事件,需要先判定是作者在前还是标题在前 posA = line.index(author) posT = line.index(title) if(posA<posT): # 如果作者在前则为1，否则为0 order = 1 if posA-CONST_M>=0: prefix = line[posA-CONST_M:posA] # 记录author前m个字符作为前缀 else: prefix = line[:posA] # 如果前m个字符超出下界则m记为0 middle = line[posA+len(author):posT] suffix = line[posT+len(title):posT+len(title)+CONST_M] # 记录title后m个字符作为后缀，后界不用if，因为默认超出len按len计算 else: order = 0 if posT-CONST_M>=0: prefix = line[posT-CONST_M:posT] else: prefix = line[:posT] middle = line[posT+len(title):posA] suffix = line[posA+len(author):posA+len(author)+CONST_M] occurrence['author'] = author # 记录事件并返回 occurrence['title'] = title occurrence['order'] = order occurrence['url'] = url occurrence['prefix'] = prefix.strip() occurrence['middle'] = middle.strip() occurrence['suffix'] = suffix.strip() return occurrence return None occurrence = SearchSeedInPage(seeds[0]['author'],seeds[0]['title'],data[0]['url'],data[0]['text']) print(occurrence) # 在第一个数据中搜索到的第一个种子
有了在一个页面中搜索一个种子的函数后，我们需要将所有种子在所有页面中搜索，以下的occurrences才是我们需要拿来形成模式的事件结果集：
def SearchSeeds(): # 在所有数据中搜索所有种子 ouccurrences = [] # 事件列表 for seed in seeds: for page in data: occurrence = SearchSeedInPage(seed['author'],seed['title'],page['url'],page['text']) if occurrence is not None: ouccurrences.append(occurrence) return ouccurrences occurrences = SearchSeeds() print(occurrences) # 在所有数据中搜索到的所有种子结果根据以上事件，我们需要形成模式，首先是通过middle和order分组，将所有具有相同middle和order的事件分为一组，并尝试利用它们形成模式（分组后如果一组的长度大于一才能尝试形成模式）：
def GroupByOrderAndMiddle(): # 通过order和middle进行分组，并对每组数据形成模式 patterns = [] occurrences.sort(key = itemgetter('order')) # 按照对order字段进行排序 for middle,items in groupby(occurrences,key = itemgetter('middle')): # groupby（）函数在每次迭代的时候，会返回一个分组后的分组值和一个迭代器对象，迭代器对象包含对应分组值的所有对象。 lists = list(items) # 迭代器只能迭代一次，所以转化为列表进行操作 if len(lists) > 1: # 每类分组中需要至少两组数据才能形成模式 eachpatterns = GroupByUrl(lists) # 这里eachpatterns的结构为[{'a':'a','b':'b'},{'a':'c','b':'d'}]，因此需要用+做合并列表操作 patterns = patterns + eachpatterns return patterns
接着我们需要将分组后的数据取最长的url前缀（这里就需要注意了，不能取到http://或者http://作为前缀，需要用strip()函数剔除），为了方便起见，我在这里直接用split()函数对网址利用'\'进行分割，取第一个分割结果作为主网址，再利用主网址进行分组，并对分组后的数据再取prefix和suffix，同理，这里分组后的每组长度也需要大于1才能继续操作：
def GroupByUrl(lists): # 从已经通过order和middle分组的数据组中再通过网址进行分组 patterns = [] for each in lists: each['url'] = each['url'].split('/')[0] # 切割分组后每组数据的url，取主网址 for url,items in groupby(lists,key = itemgetter('url')): # 再通过url主网址进行分组 lists = list(items) if len(lists) > 1: pattern = GetPrefixAndSuffix(lists) if pattern is not None: patterns.append(pattern) # 这里获取到的是一个模式集合，因此在列表中追加即可 return patterns
接着我们对分了两次组的数据取prefix和suffix，这里就不再分组了，直接取每组数据中最长的前缀和后缀匹配值，这里为了获取多个字符串中的公共前缀，先设公共前缀为第一个字符串，再利用这个字符串与第二个字符串进行从头到尾每个字符的匹配，如果匹配不成功则截取两个字符串的公共部分作为公共前缀，依次类推，后缀同理从后往前逐一匹配：
def GetPrefixAndSuffix(lists): # 经过order、middle和url的分组后，剩下的数据量大于1且不再分组，形成一个模式 prefix = lists[0]['prefix'] # 匹配每组数据中公共的前缀，不保证不为空 suffix = lists[0]['suffix'] pattern = {} pattern['order'] = lists[0]['order'] pattern['middle'] = lists[0]['middle'].strip() pattern['url'] = lists[0]['url'] for index in range(len(lists)-1,-1,-1): # 这里的操作是默认前缀为第一个数据，然后与后面的数据进行匹配，在第一个数据的基础上做缩减操作 i = len(prefix)-1 j = len(lists[index]['prefix'])-1 while i>=0 and j>=0 and lists[index]['prefix'][j] == prefix[i]: i = i-1 j = j-1 prefix = prefix[i+1:] m = 0 n = 0 while m<len(suffix) and n<len(lists[index]['suffix']) and lists[index]['suffix'][n] == suffix[m]: m = m+1 n = n+1 suffix = suffix[:m] pattern['prefix'] = prefix.strip() pattern['suffix'] = suffix.strip() if len(pattern['prefix']) and len(pattern['suffix']) and len(pattern['url']): return pattern return None
我们已经有了一个模式，我们可以利用现有的模式构造正则表达式搜索更多的元组了，搜索到的元组如果已经存在在我们的数据库中则忽略，不存在则添加到数据库的seeds表中：
上述详情可参考：https://blog.csdn.net/qq_39591838/article/details/102628466
实验中所使用的的数据及其说明如下：
data：存放所有web页面的url及其内容 seeds：存放所有初始元组对及通过模式查找到的元组对 occurences：存放通过seeds查找到的所有事件 patterns：存放所有通过occurrences形成的模式列表
利用实验方案和开发实施中的代码进行试验设计，首先我们利用本地服务器上的页面进行测试，创建两个HTML页面，并存放在本地服务器下，在第一个页面中有五对元组，分别为：（Ernest Miller Hemingway，The Old Man and the Sea）（Jonathan Swift，GULLIVER`S TRAVELS）（Charles Dickens，Pickwick Papers）（Nicholas Sparks，The Last Song）（W. William Shakespeare，A Midsummer Night's Dream），第二个页面中存有一对元组（Charles Dickens，Great Expectations）
http://localhost/DIPRE/BestSeller.html
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Document</title> </head> <body> <h2>famous writer Ernest Miller Hemingway wrote The Old Man and the Sea book</h2> <h2>great writer Jonathan Swift wrote GULLIVER`S TRAVELS book</h2> <h2>amazing writer Charles Dickens wrote Pickwick Papers book</h2> <h2>favorite writer Nicholas Sparks wrote The Last Song book</h2> <h2>amazing writer W. William Shakespeare wrote A Midsummer Night's Dream book</h2> </body> </html>
http://localhost/DIPRE/TopRated.html
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Document</title> </head> <body> <h2>The famous writer Charles Dickens wrote Great Expectations book</h2> </body> </html>
然后我们将这两个页面存入数据库，并在python中连接数据库读取数据，将页面信息存入在data列表下：
我们有了源数据之后，需要手动输入一些种子，在这个测试用例中至少需要来自同一个页面的两个种子才能形成一个模式，我们选择（Ernest Miller Hemingway，The Old Man and the Sea）和（W. William Shakespeare，A Midsummer Night's Dream）这两个元组对，因为这两个元组在BestSeller.html同时存在，方便我们形成模式。
接下来，通过seeds查找到的事件（occurrences ）列表如下：
[{'author': 'Ernest Miller Hemingway', 'title': 'The Old Man and the Sea', 'order': 1, 'url': 'http://localhost/DIPRE/BestSeller.html', 'prefix': '2>The famous writer', 'middle': 'wrote', 'suffix': 'book</h2>\n<h2>The g'}, {'author': 'Charles Dickens', 'title': 'Pickwick Papers', 'order': 1, 'url': 'http://localhost/DIPRE/BestSeller.html', 'prefix': '>The amazing writer', 'middle': 'wrote', 'suffix': 'book</h2>\n<h2>The g'}]
然后我们可以通过以上的事件，用已有的代码形成模式patterns如下：
[{'order': 1, 'middle': 'wrote', 'url': 'localhost', 'prefix': 'writer', 'suffix': 'book</h2>\n<h2>'}]通过已有的模式，在data中进行搜索，得到的新元组加入seeds：
添加成功 Jonathan Swift GULLIVERâS TRAVELS 添加成功 Charles Dickens Pickwick Papers 添加成功 Nicholas Sparks The Last Song 添加成功 Charles Dickens Great Expectations
同理，我们通过真实数据，以当当网的一个书籍子页为例：http://e.dangdang.com/list-WX-dd_sale-0-1.html
首先我们在数据库中手动在seeds表中插入三个元组（林清玄，在这坚硬的世界里,修得一颗柔软心）、（兰陵笑笑生，金瓶梅(全两册)(崇祯版)(简体横排、无批评)）、（余华，余华：我们生活在巨大的差距里），这是该测试页面下存在的三个元组，并把URL存入webpage表。
然后按照上述流程运行代码，得到data数据的部分：
这里的text是要使用URL的时候再利用爬虫去爬取，得到的seeds如下：
{'id': 33, 'author': '林清玄', 'title': '在这坚硬的世界里,修得一颗柔软心'}, {'id': 43, 'author': '兰陵笑笑生', 'title': '金瓶梅(全两册)(崇祯版)(简体横排、无批评)'}, {'id': 46, 'author': '余华', 'title': '余华：我们生活在巨大的差距里'}]
接着利用种子在text中进行搜索记录，我们会得到一些事件：
{'author': '林清玄', 'title': '在这坚硬的世界里,修得一颗柔软心', 'order': 1, 'url': 'e.dangdang.com/list-WX-dd_sale-0-1.html', 'prefix': 'v>\n</a>\n<a dd_name="', 'middle': '" target="_blank" title="', 'suffix': '">\n<span class="book'}, {'author': '兰陵笑笑生', 'title': '金瓶梅(全两册)(崇祯版)(简体横排、无批评)', 'order': 1, 'url': 'e.dangdang.com/list-WX-dd_sale-0-1.html', 'prefix': 'v>\n</a>\n<a dd_name="', 'middle': '" target="_blank" title="', 'suffix': '">\n<span class="book'}, {'author': '余华', 'title': '余华：我们生活在巨大的差距里', 'order': 1, 'url': 'e.dangdang.com/list-WX-dd_sale-0-1.html', 'prefix': 'v>\n</a>\n<a dd_name="', 'middle': '" target="_blank" title="', 'suffix': '">\n<span class="book'}]
利用以上事件，我们可以形成一个模式：
{'order': 1, 'middle': '" target="_blank" title="', 'url': 'e.dangdang.com', 'prefix': 'v>\n</a>\n<a dd_name="', 'suffix': '">\n<span class="book'}
利用上述模式在该页面中查找，可以查找到一系列元组：
将以上元组和网页源代码进行对比我们可以发现，该网页中的元组对已经全部被我们的这个模式捕获到，接下来只需要将我们形成的模式和搜索到的元组插入数据库，然后进行下一轮迭代。
原代码由于是在所有数据中查找所有种子，并且通过对所有事件进行分组从而形成模式，当数据和种子数规模较大的时候，生成事件、形成模式的过程都会非常慢，同时我们所得到结果的时间也会花费的很多，更致命的是由于网页源码包含了许多无用的信息，同时爬取所有网页及其内容可能会导致内存溢出，所有有没有一种方式可以在用完某些数据后将其删除，并且在过程中逐步得到我们想要的元组对。
由此提出一种思想来改进算法，大体来说就是逐个处理网页，并将处理过的网页删除，防止进一步占用内存，在此步骤中也可以同时产生我们想要的元组，同步存入到数据库中，防止程序异常中断，具体算法思维步骤见：https://blog.csdn.net/qq_39591838/article/details/102633307
改进后的代码是针对单个界面处理，所以需要查询一个网页是否有匹配的模式，而对同个主网站下的不同子网页形成不同的模式，所以可能有多个适用该网页的模式，此时应该取第一个能匹配出结果的模式：
def GetMatchPattern(patterns,url): #查询某个网页是否有匹配的模式，返回匹配的第一个模式 if patterns is None: # None不能进行迭代 return None for item in patterns: if item['urlprefix'] in url: if FindBooksByPattern(item,data[index]['text']) is not None: # 如果通过该匹配模式找到事件并存储，则返回1 return 1 return 0 # 没有找到匹配的模式或者没有通过匹配模式查找到事件则返回0
同样是因为针对单个界面的处理，这里形成模式的过程就简化了不少，如果在某页面查找到的事件数大于2，就可以尝试形成模式，此时不需要再对order和middle进行分组，只需要检查这些事件是否具有相同的order和middle即可，也无需对url再进行分组，取当前页面的主网址就可：
def WhetherFormPattern(occurrences): # 判断同个页面的事件集能否形成事件，即middle和order是否相同 order = occurrences[0]['order'] middle = occurrences[0]['middle'] for item in occurrences: if order != item['order'] or middle != item['middle']: return 0 return 1 def FormPattern(occurrences): # 利用查找到的事件形成模式，此时的事件集>2，且在同个url下 prefix = occurrences[0]['prefix'] # 匹配数据中公共的前缀，不保证不为空 suffix = occurrences[0]['suffix'] pattern = {} for index in range(len(occurrences)-1,-1,-1): # 这里的操作是默认前缀为第一个数据，然后与后面的数据进行匹配，在第一个数据的基础上做缩减操作 i = len(prefix)-1 j = len(occurrences[index]['prefix'])-1 while i>=0 and j>=0 and occurrences[index]['prefix'][j] == prefix[i]: i = i-1 j = j-1 prefix = prefix[i+1:] m = 0 n = 0 while m<len(suffix) and n<len(occurrences[index]['suffix']) and occurrences[index]['suffix'][n] == suffix[m]: m = m+1 n = n+1 suffix = suffix[:m] pattern['order'] = occurrences[0]['order'] pattern['middle'] = occurrences[0]['middle'].strip() pattern['urlprefix'] = occurrences[0]['url'].lstrip('http://').lstrip('https://').split('/')[0] # 去除http头，并取主网址，保存url pattern['prefix'] = prefix.strip() pattern['suffix'] = suffix.strip() if len(pattern['prefix']) and len(pattern['suffix']) and len(pattern['urlprefix']) and len(pattern['middle']): # 只返回符合特异性的模式 return pattern return None
然后便是主代码，第一重循环是重复处理所有未处理过的网页，第二重循环是对每个单个网页进行处理，如果不能处理则转为处理下一个网页：
if __name__ == '__main__': flag = 0 # 跳出循环的标志，0不跳出，1跳出 patterns = GetPatterns() data = GetData() # 获取所有没有被处理过的数据 seeds = GetSeeds() # 获取所有种子 while flag == 0 or len(seeds)>=CONST_MAXBOOK: flag = 1 for index in range(len(data)-1,-1,-1): # 因为中途需要删除数据，所以从后往前遍历 try: if len(data[index]['text']) == 0: data[index]['text'] = DelHrefInString(CrawlWeb(data[index]['url'])) except: MarkPage(data[index]['id']) # 对于无效的网页，删除该数据 flag = 0 print(data[index]['url'],'该网页无效：') del data[index] continue res = GetMatchPattern(patterns,data[index]['url']) # 对于每组数据，首先查找是否有现有匹配模式 if res == 1: # 如果通过匹配模式匹配到事件并存储，则标记并删除，如果没有则利用种子查询 print(data[index]['url'],'该网页找到已有的匹配模式') flag = 0 MarkPage(data[index]['id']) # 标记该网页已查询 del data[index] # 在内存中删除处理过的数据 continue # 处理下一个网页 # # 如果没有匹配的模式，或者利用匹配模式查出来的结果为空，则进行以下步骤 occurrences = SearchSeedsInText(seeds,data[index]) # 在该条数据中搜索所有种子对，并记录成事件集 if len(occurrences) != 0: flag = 0 if len(occurrences)<2: # 如果种子查询个数仅仅为1，则无法形成事件（后续改为存储到数据库中） # print(data[index]['url'],'该种子查询结果仅为1') # print(occurrences) continue if WhetherFormPattern(occurrences): # 如果事件集具有相同的middle和order则尝试形成模式 pattern = FormPattern(occurrences) print(data[index]['url'],'在该网页下形成模式') print(pattern) if pattern is not None: # 如果形成有效的模式，则利用模式在该页面下搜索 patterns.append(pattern) # 添加到模式数据中 SavePattern(pattern['order'],pattern['urlprefix'],pattern['prefix'],pattern['middle'],pattern['suffix']) # 直接存储 FindBooksByPattern(pattern,data[index]['text']) # 通过形成的模式查找元组并存储 print(data[index]['url'],'在该网页下无法形成模式') print(occurrences) # MarkPage(data[index]['id']) # 现在无法形成模式，但并不代表不能使用其他子网页形成的模式 del data[index]
我们将255个页面通过爬虫插入数据库，并手动将6个种子插入到数据库中，在python中传给变量data和seeds进行存储，然后运行代码，在十分钟内共计得到了6389条元组和三个模式
上述详情可参考：
改进方案：https://blog.csdn.net/qq_39591838/article/details/102750858
改进后运行结果：https://blog.csdn.net/qq_39591838/article/details/102751044
