杨氏矩阵查找倒排索引关键词Hash编码.doc
文本预览下载声明
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冲突的问题,下文会详细介绍。
? ? 有一点必须提醒读者的是,倒排索引包含词典和倒排记录表两个部分,词典一般有词项(或称为关键词)和词项频率(即这个词项或关键词出现的次数)
显示全部