多媒体有哪些信誉好的足球投注网站引擎 - 20090307055430.ppt

Multimedia Search Engine 多媒体有哪些信誉好的足球投注网站引擎 有哪些信誉好的足球投注网站引擎基础 基本概念 有哪些信誉好的足球投注网站引擎(Search Engine) 实现信息检索功能的…? 信息检索(Information Retrieval) 从大量非结构化的素材中找出满足一定信息需求的素材 大量 非结构化(unstructured) 数据库：结构化数据；网页：非结构化数据 信息需求(information need) 描述？匹配？ 基本概念 “有哪些信誉好的足球投注网站”或“检索” 有哪些信誉好的足球投注网站(search) 常指在结构化数据上的操作 检索(retrieval) 在非结构化数据上的操作 “信息检索”或“…检索” 信息检索(Information Retrieval) 一般指对文本素材的检索 基本概念 信息需求(information need) 用户实际需要的信息的模型 如何描述？如何匹配？ 基本概念 信息需求(information need) 如何描述？ 便于计算机接收 便于用户心算 容易手工输入 ?关键字 关键字检索 用关键字描述用户的信息需求进行检索 匹配：字符串匹配 检索模型 关键字检索 最简单的实现：grep 检索模型 关键字检索 最简单的实现：grep 优点：实现简单 缺点：慢，低效 使用环境 少量小文件的有哪些信誉好的足球投注网站 偶尔进行的有哪些信誉好的足球投注网站 ?大量文件，经常有哪些信誉好的足球投注网站？ 检索模型 关键字检索 索引(index) 检索模型 关键字检索 索引(index) 如何建立？ 检索模型 关键字检索 索引(index) 如何建立？ 检索模型 关键字检索 存在的问题 标签的“粒度”与完备性？ 检索模型 关键字检索 布尔检索(Boolean Retrieval) 以较小的词为标签 复杂的检索分解成简单关键字检索结果的运算 华东师范大学?华东+师范+大学 软件学院?软件+学院 兄弟院系?华师大-软件学院 ?如何实现？ 检索模型 布尔检索 相关矩阵 检索模型 布尔检索 相关矩阵 问题：100亿个文档？ 1010×1(bit/doc)÷233(bit/GB)≈11.6GB 每个标签！ ?如何加速？ 特性：极度稀疏 ?倒排文件+集合运算 检索模型 布尔检索 倒排文件 检索模型 布尔检索 集合运算 线性扫描 要求：两个输入集合是排序了的 检索模型 布尔检索 集合运算 线性扫描 复杂度：O(m+n) 能更快吗？ 标签对应的文档数在1万~1亿的数量级 华东~1500万，师范~5000万，大学~1000万 华东师范大学~329万 检索模型 布尔检索 集合运算 Skip Pointer (快扫指针？) 检索模型 布尔检索 集合运算 Skip Pointer是否可以加速“或”运算？ 基本上不行 “或”需要处理所有元素 如果相邻指针之间的所有元素可以作为整体进行操作，则有一定的加速可能性 检索模型 布尔检索 集合运算 Skip Pointer 如何用数组实现的集合实现Skip Pointer？ ?课后思考题 其它问题 究竟有多少性能提升？ 一次跳多远？ 插入/删除/修改？ 是否可以有更多的改进？ ?课程项目之一二三…… 索引之索引 如何快速从词典中找到标签？ 索引之索引 如何快速从词典中找到标签？ 索引之索引 如何快速从词典中找到标签？ 倒排文件？ 不可能 问题定义 给定一个大词典和一个标签，快速从词典中找到该标签对应的数据 二分查找，B树，Hash表，Trie结构 ?下一次课 * * 实际需求 用户描述的需求 计算机理解的需求 华东师范大学 ? ? ? 华东师范大学 华东师范大学 上海交通大学 领导视察 …… ? ? …… 标签(label) 词典(dictionary) 华东师范大学 上海交通大学 领导视察 …… …… 再连接？ 多少个？ 华东师范大学：7 领导视察：2 中山北路：1 …… 关键字 词频 华东师范大学：3 软件学院：5 …… …… …… 华东师范大学 软件学院 领导视察 …… 华东师范大学 华东 师范 大学 软件学院 软件 学院 兄弟院系 =华师大—软件学院 华东 师范 大学 软件 学院 领导 视察 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 “华东师范大学”：110 110 111 ? 110 “兄弟院校”：110 110 111 ~(010 111) ? 100 华东 0 1 师范 0 1 大学 0 1 2 …… 集合 1 2 5 1 3 5 1 ? ? ? 5 “与” “或” “非” 1 2 5 1 3 5 1 2 5 ? ? 3 ? 以“与非”和“或非”方式实现 复杂度：O(m*n) 如何