字符串

5.1 字符串排序

键索引计数法：简单说用字符串对应的key，生成数组，然后遍历字符串的时候，对应数组对应的key的索引+1。这样就可计算字符串出现的频率 低位优先字符串排序：从字符串末尾开始进行一个个对比，并用 键索引计数法 进行索引排序回写，具体可参考下图 高位优先的字符串排序:从字符串首字母开始一个个进行排序，大致算法同低位优先字符串排序，不同的是，比较出大小的字符串就不用再进行比较了，如下图所示： 三向字符串排序：类似于排序中的三分取样，取个key，然后将小于,等于,大于整个字符串的数组分为三分，然后再分别进行高位优先字符串排序，如下图所示：

5.2 单词查找树

5.2.1 单词查找树

类似于二叉树查找，但是每个节点多了个索引值，如果该节点有索引值，则表示从根节点到该节点是个字符串，如图所示：

5.2.2 三向单词查找树

主要是为了避免单词查找树过度的空间消耗。 在三向单词查找树中，每个结点都含有一个字符、三条链接和一个值。这三条链接分 别对应着当前字母小于、等于和大于结点字母的所有键，具体结构如下图所示：

5.3 子字符串查找

举例来说，有一个字符串”BBC ABCDAB ABCDABCDABDE”，我想知道，里面是否包含另一个字符串”ABCDABD”？

5.3.2 暴力查找

简单说就是一个个字母进行匹配，如果发现不匹配，则后移一位后继续该操作，如下图所示：

5.3.3 KMP算法

简单说，就是我们比较两个字符串，之前比较过的内容我们是知道的，所以，不需要再重新进行比较，直接将字符串移动到一个合适的位置，然后接着比较后面的即可(从 12312345 中找1234,我们最开始肯定会比较前面的123跟1234，结果最后一个不匹配，按暴力查找的花，我们要从2的位置开始再次跟1234比较，但其实前面123的内容我们已经知道且不符合要求，所以可以直接跨过前面的123，直接比较后面的12345 跟1234 即可)。

参考：字符串匹配的KMP算法

5.3.4 Boyer-Moore算法

粗略的理解：先将要比较的字符串与搜索词的头部对其，从结尾开始对比，如果不匹配，且结尾的字母不包含再搜索词中则直接将搜索词移动到当前结尾的字母后面，如果不匹配，但是结尾的字母包含在搜索词中，如果包含则将搜索词的位置移动到该位置，然后再从最右边开始一个个对比。如果搜索词的结尾跟字符串相同，则一个个向前比较，然后再按上述规则进行移动。

参考：字符串匹配的Boyer-Moore算法

5.3.5 Rabin-Karp指纹字符串查找算法

简单理解就是字符串有个散列值，然后从目标字符串按暴力查找的逻辑计算散列值，然后进行对比，发现匹配即找到

5.4 正则表达式

简单理解，可以将正则表达式的搜索跳转，转化为一个有向图，存储每一步对应的跳转关系，然后我们匹配的时候，一一对应跳转即可，如果能跳转到末尾，则表示匹配成功。如下图所示：

5.5 数据压缩

5.5.4 热身运动，基因组

将特定的字符，用特定的二进制表示，有了一一对应关系，就可以压缩+展开

5.5.5 游程编码

简单说就是将部分重复的数据简单用 长度+数据来表示。 例如，请看下面这条 40 位长的字符串：0000000000000001111111000000011111111111。 该字符串含有 15 个 0，然后是 7 个 1，然后是 7 个 0，然后是 11 个 1，因此我们可以将该比特字符 串编码为 15，7，7，11。所有的比特字符串都是由交替出现的 0 和 1 组成的，因此我们只需要将游程的 长度编码即可。在这个例子中，如果用 4 位表示长度并以连续的 0 作为开头，那么就可以得到一个 16 位 长的字符串（15=1111，7=0111，7=0111，11=1011）：1111011101111011。

5.5.5 霍伊曼压缩

霍伊曼压缩:简单说，对每个字母进行编码，然后生成编码表，一一对应查找。这里的对应方式为。具体的编码方式：将字母按出现的频率进行排序，然后从子节点，到根节点，一个个插入上升，最后构成一个二叉树，每个节点用0/1来表示，最后我们就形成了一张字母表。之后就可以用整个字母表来解析整个字符串 如下图所示:

LZW压缩:同理是生成将每个单词生成一个字母表，然后进行一一对应。整个的一个进步是：比如出现了ABAB，A编码是1，B编码是2 那么再到A的时候，发现A之前出现过，且跟后面的B组合后的的最长前缀也是A，那么就对AB整体进行编码，例如，AB就可以标识为9，整个字符串的表示就是:129。 这个我这边讲述的不明白，可以参考:LZW压缩算法原理解析

--EOF--

若无特别说明，本站文章均为原创，转载请保留链接，谢谢