Heart.X.Raid
- 浏览: 898277 次
- 性别:
- 来自: 武汉
-
最新评论
-
小宇宙_WZY：
膜拜一下大神，解决了我一个大问题，非常感谢 orz
【解惑】深入jar包：从jar包中读取资源文件 -
JKL852qaz：
感谢，遇到相同的问题！
【解惑】深入jar包：从jar包中读取资源文件 -
lgh1992314：
为什么java中调用final方法是用invokevirtua ...
【解惑】Java动态绑定机制的内幕 -
鲁曼1991：
说的都有道理，protected只能被同一级包的类所调用
【解惑】真正理解了protected的作用范围 -
鲁曼1991：
...
【总结】String in Java
文章列表
LCS：又称
最长公共子序列。
其中子序列(subsequence)的概念不同于串的子串。它是一个不一定连续但按顺序取自字符串X中的字符序列。
例如：串"AAAG"就是串“CGATAATTGAGA”的一个子序列。
字符串的相似性问题可以通过求解两个串间的最长公共子序列(LCS)来得到。
当然如果使用穷举算法列出串的所有子序列，一共有2^n种，而每个子序列是否是另外一个串的子序列又需要O(m)的时间复杂度，因此这个穷举的方法时间复杂度是O(m*(2^n))指数级别，效率相当的可怕。我们采用动态规划算法来解决这个问题。
动态规划算法解决 ...
模式匹配：
在字符串S中，子串P的定位操作通常称做串的模式匹配。说白了，就是在一个字符串中寻找子串。在Suffix Trie和PAT tree中我们已经讨论过匹配子串的方法了。这里我们讨论一种线性匹配算法来寻找子串。
例： 我 ...
问题：快速求取正整数a，b的最大公约数？
欧几里得算法（又称辗转相除法）
定理：gcd(a,b) = gcd(a,a mod b)
证明：对于任何正整数a，b。如果a>b，都有a=k*b+r 即r=a-k*b => r=a mod b.
假设d为a，b的公约数，则a=a1*d，b=b1*d。
而r=a1*d-k*b1*d=(a1-k*b1)*d => d也是r的约数 => d也是(a，r)的公约数
则说明(a，b)的公约数也就是(a，r)的公约数。因此 ...
Suffix Trie
：
又称后缀Trie或后缀树。它与Trie树的最大不同在于，后缀Trie的字符串集合是由指定字符串的后缀子串构成的。比如、完整字符串"minimize"的后缀子串组成的集合S分别如下：
s1=minimize
...
Trie 树，
又称字典树，单词查找树。它来源于retrieval(检索)中取中间四个字符构成(读音同try)。用于存储大量的字符串以便支持快速模式匹配。主要应用在信息检索领域。
Trie 有三种结构： 标准trie (standard trie)、压缩trie、后缀trie(suffix trie)
。
最后一种将在《字符串处理4：后缀树》中详细讲，这里只将前两种。
1. 标准Trie (standard trie)
标准
Trie树的结构
： 所有含有公共前缀的字符串将挂在树中同一个结点下。实际上trie简明的存储了 ...
该系列文章是《An Introduce to Information Retrieval》Chapter 1 的读书笔记。
IR的概念很广泛，即使从钱包中拿出一张信用卡并输入卡号也是一种形式的信息检索。在学术领域，我们这样定义IR：
信息检索(IR)就是一种从大量数据集合中(通常指存储在计算机中文档)寻找满足信息需求的非结构化(通常指文本)得数据(通常指文档)。
布尔检索模型(Boolean Retrieval)
要点： (1) 倒排/反向索引模型 inverted indexes
...
1. 问题：100个连续
的数打乱
之后，随机取出1个数
，问如何最快速
的判断出少了哪一个？
分析：对于所有100个连续的数，只要除余100。一定在0~99之间。一般来说，比较常规的做法就是先排序（利用Hash表定位），在循环查找。当然时间复杂度是O(2n)。现在介绍一种很牛的O(n)做法：求二进制异或运算。
异或运算： 0^0=1^1=0; 0^1=1^0=1。0~99个数全部异或的结果只能是0。如果缺少一个数，那么全部异或的结果正好就是那个数。为什么呢？我们做个小实验：假如有四个数： 0001 0010,0101, 0110 排列成一 ...
我们来看一个实际应用。现代搜索技术的发展很多以提供优质、高效的服务作为目标。比如说：baidu、google、sousou等知名全文搜索系统。当我们输入一个错误的query="Jave" 的时候，返回中有大量包含正确的拼写 "Java"的网页。当然这里面用到的技术绝对不会是我们今天讲的怎么简单。但我想说的是：字符串的相似度计算也是做到这一点的方法之一。
字符串编辑距离：
是一种字符串之间相似度计算的方法。给定两个字符串S、T，将S转换成T所需要的删除，插入，替换操作的数量就叫做S到T的编辑路径。而最短的编辑路径就叫做字符串S和T的编辑距 ...
Patricia Tree 简称PAT tree。
它是 trie 结构的一种特殊形式。是目前信息检索领域应用十分成功的索引方
法，它是1992年由Connel根据《PATRICIA——Patrical Algorithm to Retrieve Information Coded in Alphanumeric》算法发展起来的。
PAT tree ...
Bin
Dec
Hex
缩写/字符
解释
00000000
0
00
NUL(null)
空字符
00000001
1
01
SOH(start of handling)
标题开始
00000010
2
02
STX (start of text)
正文开始
00000011
3
03
ETX (end of ...
我们首先来看一段代码：
Integer i=100;
Integer j=100;
System.out.println(i==j); //true
Integer i=200;
Integer j=200;
System.out.println(i==j); //false
差不多的两段代码，怎么结果完全不同呢。我们分两步来说明这个问题：
首先 Integer i=100; 编译器会自动将int类型常数100包装成Interger，采用的是Integer.valueOf(100)；
这个方法。
然后我们看看valueOf(int)这个方法的源代码：
...
我们这个专题介绍的动态查找树主要有： 二叉查找树(BST)，平衡二叉查找树(AVL)，红黑树(RBT)，B~/B+树(B-tree)。这四种树都具备下面几个优势：
(1) 都是动态结构。在删除，插入操作的时候，都不需要彻底重建原始的索引树。最多就是执行一定量的旋转，变色操作来有限的改变树的形态。而这些操作所付出的代价都远远小于重建一棵树。这一优势在《查找结构专题(1)：静态查找结构概论
》中讲到过。
(2) 查找的时间复杂度大体维持在O(log(N))数量级上。可能有些结构在最差的情况下效率将会下降很快，比如BST。这个会在下面的对比中详细阐述。
下面我们 ...
大部分转载：http://yanglongylj.blog.163.com/blog/static/563834532009113021438417/
红黑树的性质与定义
红黑树(red-black tree)
是一棵满足下述性质的二叉查找树：
1. 每一个结点要么是红色，要么是黑色。
2. 根结点是黑色的。
3. 所有叶子结点都是黑色的（实际上都是Null指针，下图用NIL表示）。叶子结点不包含任何关键字信息，所有查询关键字都在非终结点上。
4. 每个红色结点的两个子节点必须是黑色的。换句话说：从每个 ...
在前面专题中讲的BST、AVL、RBT都是典型的二叉查找树结构，其查找的时间复杂度与树高相关。那么降低树高自然对查找效率是有所帮助的。另外还有一个比较实际的问题：就是大量数据存储中，实现查询这样一个实际背景下，平 ...
在上一个专题中，我们在谈论二叉查找树的效率的时候。不同结构的二叉查找树，查找效率有很大的不同（单支树结构的查找效率退化成了顺序查找）。如何解决这个问题呢？关键在于如何最大限度的减小树的深度。正是基于这 ...