{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"“搜索引擎”这个词对你来说可能并不陌生。一般来说,搜索引擎搜索\n\n互联网上可用的网页,提取和组织信息并响应用户的\n\n具有最相关页面的查询。世界著名的搜索引擎,像谷歌,已经变得非常\n\n当我们访问网络时使用的重要工具。这种对话现在在我们的日常生活中很常见\n\n生活:\n\n“像这个词是什么意思?“\n\n“嗯。…我不确定,只是用谷歌搜索。”\n\n在这个问题中,您需要构造一个小的搜索引擎。听起来不可能,是吗?\n\n别担心,这里有一个教程教你如何有效地组织大量的文本集,以及\n\n逐步快速响应查询。你不必担心网络的获取过程\n\n网页,所有网页都以文本格式作为输入数据提供给您。另外,很多问题\n\n还提供用于验证您的系统。\n\n现代搜索引擎使用一种称为反转的技术来处理非常大的文档集。\n\n该方法依赖于数据结构(称为反向索引)的构造,该结构将\n\n术语(词)在文件集合中出现的术语(词)。这套利息条款被称为\n\n用v表示的词汇。在其最简单的形式中,倒排索引是一个字典,其中每个搜索\n\n关键是一个术语ω∈v。关联值b(ω)是指向额外中间数据结构的指针,\n\n称为桶。与某个术语ω相关联的bucket本质上是标记所有\n\n文本集合中出现ω。每个bucket中的每个条目只包含文档\n\n标识符(did)、集合中文档的序号和序号行号\n\n在文档中出现的术语。\n\n让我们以图1为例,它描述了一般的结构。假设我们只是\n\n有三个文档要处理,如图1中右侧所示;首先,我们需要标记\n\n单词文本(空格、标点和其他非字母字符用于分隔单词)\n\n并根据文档中出现的术语构建词汇表。为了简单起见,我们不需要\n\n考虑任何短语,只有一个词作为术语。此外,这些术语不区分大小写(例如,我们\n\n把“book”和“book”看作是同一个词),我们不考虑任何形态的变体。\n\n(例如,我们认为“书”和“书”、“保护”和“保护”是不同的术语)并用连字符连接\n\n单词(例如,“中产阶级”不是一个单独的词,而是通过以下方式分为两个词:“中产阶级”和“阶级”\n\n连字符词汇表如图1左侧所示。词汇表的每个术语都有一个\n\n指向其桶的指针。图1的中间部分显示了这些桶的集合。每个项目\n\n在存储桶中记录术语发生的DID。\n\n在构造完整个反向索引结构后,我们可以将其应用到查询中。查询\n\n采用以下任何格式:\n\n学期\n\n术语和术语\n\n术语或术语\n\n非术语\n\n单个术语可以由布尔运算符组合:“and”、“or”和“not”(“term1和term2”表示\n\n查询包括term1和term2在内的文档;“term1或term2”是指查询文档。\n\n包括term1或term2;“not term1”是指查询不包括term1的文档。条款\n\n是上面定义的单个词。您可以保证在\n\n术语,所有术语都是小写的。此外,一些无意义的停止词(常用词\n\n例如在我们的问题中被指定为“the,a,to,and,or,not”的冠词、介词和副词)\n\n也不会出现在查询中。\n\n对于每个查询,基于构造的反向索引的引擎搜索vocabu中的术语-\n\nLary,比较术语的存储桶信息,然后将结果提供给用户。现在你能建造\n\n发动机?\n\n图1。倒排索引\n\n输入\n\n输入以整数n(0\u003cn\u003c100)开始,表示提供的n个文档。然后下一个n\n\n节是n个文档。每个部分包含文档内容,并以一行\n\n十星号。\n\n***\n\n您可以假定每行包含的字符不超过80个,并且行的总数\n\nn份文件中不得超过1500份。\n\n接下来,给出表示查询数的整数m(0\u003cm≤50000),后跟m行,\n\n一行中的每个查询。所有查询都对应于上述格式。\n\n产量\n\n对于每个查询,您需要找到满足查询的文档,并只输出\n\n包含搜索词的文档(对于“not”查询,需要输出整个文档)。\n\n您应该按照输入中显示的顺序打印行。分开不同的文件\n\n一行10个破折号。\n\n----------\n如果找不到与查询匹配的文档,只需输出一行:“对不起,我什么也没找到。”\n\n每个查询的输出以一行10个等号结束。\n\n国际贸易协会\n\n样本输入\n\n四\n\n制造商、进口商或卖方\n\n数字媒体设备不得(1)销售,\n\n或在州际贸易中提供出售,\n\n或(2)导致被运入,或\n\n影响方式,州际贸易,\n\n数字媒体设备,除非\n\n包括并使用标准安全\n\n坚持安全的技术\n\n系统标准。\n\n***\n\n当然,丽莎不一定\n\n打算读他的书。她可能\n\n只想让电脑给她写信\n\n期中考试。但丹知道她来自\n\n一个中产阶级家庭\n\n付得起学费,更不用说看书了\n\n费用。书可能是她唯一的方式\n\n可以毕业\n\n***\n\n分析研究(即评价\n\n的优点和缺点\n\n计算机系统)是\n\n有效安全的发展\n\n版权法保护的作品\n\n以及一般信息。这样\n\n研究只能通过\n\n公开出版和交换\n\n完整的科学成果\n\n***\n\n我很高兴!\n\n那你呢?\n\n***\n\n六\n\n计算机\n\n书籍和计算机\n\n书籍或受保护的\n\n不安全\n\n非常\n\n光滑的\n\n样本输出\n\n只想让电脑给她写信\n\n----------\n\n计算机系统)是\n\n国际贸易协会\n\n打算读他的书。她可能\n\n只想让电脑给她写信\n\n费用。书可能是她唯一的方式\n\n国际贸易协会\n\n打算读他的书。她可能\n\n费用。书可能是她唯一的方式\n\n----------\n\n版权法保护的作品\n\n国际贸易协会\n\n当然,丽莎不一定\n\n打算读他的书。她可能\n\n只想让电脑给她写信\n\n期中考试。但丹知道她来自\n\n一个中产阶级家庭\n\n付得起学费,更不用说看书了\n\n费用。书可能是她唯一的方式\n\n可以毕业\n\n----------\n\n我很高兴!\n\n那你呢?\n\n国际贸易协会\n\n我很高兴!\n\n国际贸易协会\n\n对不起,我什么也没找到。\n\n国际贸易协会"}}]}