文档详情

杨氏矩阵查找倒排索引关键词Hash编码.doc

发布:2018-08-25约1.89万字共22页下载文档
文本预览下载声明
HYPERLINK /v_july_v/article/details/ 杨氏矩阵查找,倒排索引关键词Hash编码 分类:? HYPERLINK /v_JULY_v/article/category/ 11.TAOPP(编程艺术)? HYPERLINK /v_JULY_v/article/category/ 13.TAOPP array? HYPERLINK /v_JULY_v/article/category/ 29.RecommendSearch2011-12-19 21:23?45208人阅读? HYPERLINK /v_july_v/article/details/ \l comments 评论(38) HYPERLINK javascript:void(0); \o 收藏 收藏? HYPERLINK /v_july_v/article/details/ \l report \o 举报 举报 HYPERLINK /tag/%e7%bc%96%e7%a8%8b \t _blank 编程 HYPERLINK /tag/%e7%ae%97%e6%b3%95 \t _blank 算法 HYPERLINK /tag/%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84 \t _blank 数据结构 HYPERLINK /tag/%e6%96%87%e6%a1%a3 \t _blank 文档 HYPERLINK /tag/null \t _blank null 目录 HYPERLINK /v_july_v/article/details/ \o 系统根据文章中H1到H6标签自动生成文章目录 (?) HYPERLINK /v_july_v/article/details/ \o 展开 [+] ? 第二十三、四章:杨氏矩阵查找,倒排索引关键词Hash不重复编码实践 作者:July、yansha。编程艺术室出品。 出处:结构之法算法之道。 前言 ? ? 本文阐述两个问题,第二十三章是杨氏矩阵查找问题,第二十四章是有关倒排索引中关键词Hash编码的问题,主要要解决不重复以及追加的功能,同时也是经典算法研究系列十一、从头到尾彻底解析Hash表算法之续。 ? ? OK,有任何问题,也欢迎随时交流或批评指正。谢谢。 第二十三章、杨氏矩阵查找 杨氏矩阵查找 ? ? 先看一个来自算法导论习题里6-3与剑指offer的一道编程题(也被经常用作面试题,本人此前去搜狗二面时便遇到了): ? ? 在一个m行n列二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 ? ? 例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字6,则返回true;如果查找数字5,由于数组不含有该数字,则返回false。 ? ? 本Young问题解法有二(如查找数字6): ? ? 1、分治法,分为四个矩形,配以二分查找,如果要找的数是6介于对角线上相邻的两个数4、10,可以排除掉左上和右下的两个矩形,而递归在左下和右上的两个矩形继续找,如下图所示: ? ? 2、定位法,时间复杂度O(m+n)。首先直接定位到最右上角的元素,再配以二分查找,比要找的数(6)大就往左走,比要找数(6)的小就往下走,直到找到要找的数字(6)为止,如下图所示: ? ? 上述方法二的关键代码+程序运行如下图所示: ? ? 试问,上述算法复杂么?不复杂,只要稍微动点脑筋便能想到,还可以参看友人老梦的文章,Young氏矩阵: HYPERLINK /zhanglei8893/article/details/ \t _blank /zhanglei8893/article/details/,以及IT练兵场的: HYPERLINK /array/matrix/young-tableau-problem/ \t _blank /array/matrix/young-tableau-problem/,除此之外,何海涛先生一书剑指offer中也收集了此题,感兴趣的朋友也可以去看看。 第二十四章、经典算法十一Hash表算法(续)、倒排索引关键词不重复Hash编码? ? ??本章要介绍这样一个问题,对倒排索引中的关键词进行编码。那么,这个问题将分为两个个步骤: 首先,要提取倒排索引内词典文件中的关键词; 对提取出来的关键词进行编码。本章采取hash编码的方式。既然要用hash编码,那么最重要的就是要解决hash冲突的问题,下文会详细介绍。 ? ? 有一点必须提醒读者的是,倒排索引包含词典和倒排记录表两个部分,词典一般有词项(或称为关键词)和词项频率(即这个词项或关键词出现的次数)
显示全部
相似文档