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

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冲突的问题，下文会详细介绍。 ? ? 有一点必须提醒读者的是，倒排索引包含词典和倒排记录表两个部分，词典一般有词项（或称为关键词）和词项频率（即这个词项或关键词出现的次数）