bit calculation & Rabin-Karp Algorithm

Shain

2023-08-27

将字符串映射成 N 进制数字，然后再转成10进制存储

// R 为 N
// L 为 字符串长度
private int R;
private int L;

private int addToRight(int hash, int n) {
    return hash * R + n;
}

private int removeFromLeft(int hash, int n) {
    return hash - n * (int) Math.pow(R, L-1);
}

如果忘了，就拿十进制举例子。将“123” 变成int 123 怎么变？ 1 * 10 + 2 -> 12; 12* 10 + 3 -> 123;

将123中的1 移除变成23 怎么移？ 123 - 1 * 100; 此处的100 即 10^2

即这里的 addToRight & removeFromLeft 方法实际上就是在直接进行进制转换。举个例子：

二进制数 1101 转换成 十进制怎么算？

1 1 0 1
1 * 2^3 + 1* 2^2 + 0 * 2^1 + 1 * 2^0

进制R的值怎么确定？

每一位上的值有几种可能性就是几进制。

例题 - leetcode187

package com.shain.array.limitedComplexity;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FindRepeat_L187 {
    private static final int L = 10;

    public static void main(String[] args) {
        var test = new FindRepeat_L187();
        System.out.println(test.findRepeatedDnaSequences_v2("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"));
    }
    /**
     * 基础方法， 时间复杂度，空间复杂度均为 O(NL) where N is length of String, L is length of window.
     * Why O(NL)?
     * for遍历N次， 每次遍历都要进行substring操作， substring的长度为L， 进而记为O(NL)， 实际上可以取为O(N)， 但是这里强调 NL 的目的为
     * 理解对其进行的优化
     *
     * 空间复杂度为O(NL)好理解， key为String， 共N个key
     *
     * 仅用滑动窗口优化？
     * 没用， 就算加入滑动窗口， 记录窗口内的字符串， 然后将其进行toString, toString 这个操作仍然是O(L)
     *
     * e.g.
     * String windowStr = window.toString();
     *
     * 同时这样的方案无法优化空间复杂度到真正的 O(N);
     * @param s
     * @return
     */
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ans = new ArrayList<String>();
        Map<String, Integer> cnt = new HashMap<String, Integer>();
        int n = s.length();
        for (int i = 0; i <= n - L; ++i) {
            String sub = s.substring(i, i + L);
            cnt.put(sub, cnt.getOrDefault(sub, 0) + 1);
            if (cnt.get(sub) == 2) {
                ans.add(sub);
            }
        }
        return ans;
    }

    /**
     * 利用对字符串进行HASH 来优化。
     */
    private int R;
    public List<String> findRepeatedDnaSequences_v2(String s) {
        int[] converted = new int[s.length()];
        Map<Integer, Integer> occured = new HashMap<>();
        List<String> result = new ArrayList<>();

        // Since There is only 4 possible values ACGT, 所以是四进制
        // 注意理解这个hash的过程， 由于只有四种可能的核苷酸值， 所以每一位的值就只有四种可能性。
        // 也即， 将一个窗口中的字符串， 转换成了一个长度为L的四进制数
        // 然后又将这个四进制数转换成了十进制的值作为hash
        // 也即这种方法是将一个字符串， 先转换成一个 R 进制的数字， 再将其转换成10进制保存。
        R = 4;
        int i = 0;
        for (Character c : s.toCharArray()) {
            switch (c) {
                case 'A': converted[i++] = 0; break;
                case 'C': converted[i++] = 1; break;
                case 'G': converted[i++] = 2; break;
                case 'T': converted[i++] = 3; break;
                default: return null;
            }
        }

        int right = 0;
        int left = 0;
        int hash = 0;
        while (right < s.length()) {
            hash = addToRight(hash, converted[right]);
            right++;

            if (right - left == 10) {
                if (occured.getOrDefault(hash, 0) == 1) {
                    result.add(s.substring(left, right));
                }
                occured.put(hash, occured.getOrDefault(hash, 0) + 1);

                hash = removeFromLeft(hash, converted[left]);
                left++;
            }



        }

        return result;
    }

    private int addToRight(int hash, int n) {
        return hash * R + n;
    }

    private int removeFromLeft(int hash, int n) {
        return hash - n * (int) Math.pow(R, L-1);
    }
}

正常的java位运算：左移右移与或等

与上述方法的异同

正常的 java 位运算，实际相当于把 “上一个方法中的，将2进制转换为10进制这一个过程让java自动完成了”，同时它有一个局限是，只能操作2进制的数字。换句话说，如果要将 Leetcode187 用这种正常的位运算来做的话，那么 ACGT 对应的hash值分别应为： 00, 01, 10, 11

这样有个缺点，即，对于一个长度为10 的字符串，这种方法所转换出来的数字占用20个字节，但是上个方法占用10个字节。虽然10个字节与20个字节， int都能够表示，但是如果是长度为100的字符串呢？

运算

左移右移 << >>

1	System.out.println(5 << 2); // 输出20

5 = 0101 (开头的0 为符号为)

左移两位后：

010100 = 1 * 2^4 + 1 * 2 ^ 2 = 20

按位与/或 & |

略。

但是注意通过 “将 ‘左/右移 ’ 与 ‘按位与或’ 结合改变二进制中某一个特定值的操作。

例如，利用二进制存储某个用户一年中的登陆信息，要改变二进制中某一个bit的值，则需利用这种操作

无符号左移右移

取反～

一元操作，自身取反，不太用的到。

这里涉及到二进制符号位等等问题，不看了，感觉用不着。

Robin-Karp 算法

What

用于在文本中匹配目标字符串。

How

实际上就与第一种hash方法一样。通过将pattern 字符串进行hash， map中的空间复杂度。

同时，由于用了hash，再结合滑动窗口，那么在匹配过程中的时间复杂度也从 O(NL) 优化到了 O(N). （如果忘了为什么是NL看上面的代码注释）。

换句话说，上面的Leetcode187 其实就是简易版的 Robin-Karp 算法。

为什么说是简易版？因为 Robin-Karp算法需要对hash后的十进制数进行mod, 同时mod以后就可能产生hash冲突，进而在发现当前hash值已经出现过以后，需要进行 “暴力遍历” 判断来确定找到的字符串是不是跟pattern串一样。

关于mod

为什么Robin-Karp 需要mod? 因为， L187 中每个字符只有四种取值，但是实际的 ASCII 码有 256种取值（因为ASCII 取值 0 - 255）。

Which means, 一个长度为L 的字符串，每一位有 256 种取值可能性，也就是 hash后，所得的数字是 256 进制的，而当L值很大时， int/long 肯定都是装不下的。

e.g. L = 1000, -> 则所得的十进制数范围为 1000^256

所以我们要做的就是缩小转换为十进制以后的hash值的范围，进而需要进行mod操作。

而这个被余的数 P 可以是 1658598167 ，也可以是别的数，但是要是尽可能大的素数（涉及数学知识，不仔细看了）

关于被余数 P 的选择

为什么要这个 Q 尽可能大呢？主要是为了降低哈希冲突的概率。

因为代码中你把这个 Q 作为除数，余数（哈希值）一定落在 [0, Q-1] 之间，所以 Q 越大，哈希值的空间就越大，就越不容易出现哈希冲突，整个算法的效率就会高一些。

为什么这个 Q 要是素数呢？依然是为了降低哈希冲突的概率。

举个极端一点的例子，你令 Q = 100，那么无论一个数 X 再大，X % Q 的结果必然是 X 的最后两位。换句话说 X 前面的那些位你根本没利用，可想而知你这个哈希算法存在某些规律性，不够随机，进而更容易导致哈希冲突，降低算法的效率。

代码（copy的）

// Rabin-Karp 指纹字符串查找算法
int rabinKarp(String txt, String pat) {
// 位数
int L = pat.length();
// 进制（只考虑 ASCII 编码）
int R = 256;
// 取一个比较大的素数作为求模的除数
long Q = 1658598167;
// R^(L - 1) 的结果
long RL = 1;
for (int i = 1; i <= L - 1; i++) {
// 计算过程中不断求模，避免溢出
RL = (RL * R) % Q;
}
// 计算模式串的哈希值，时间 O(L)
long patHash = 0;
for (int i = 0; i < pat.length(); i++) {
patHash = (R * patHash + pat.charAt(i)) % Q;
}

// 滑动窗口中子字符串的哈希值
long windowHash = 0;

// 滑动窗口代码框架，时间 O(N)
int left = 0, right = 0;
while (right < txt.length()) {
    // 扩大窗口，移入字符
    windowHash = ((R * windowHash) % Q + txt.charAt(right)) % Q;
    right++;

    // 当子串的长度达到要求
    if (right - left == L) {
        // 根据哈希值判断是否匹配模式串
        if (windowHash == patHash) {
            // 当前窗口中的子串哈希值等于模式串的哈希值
            // 还需进一步确认窗口子串是否真的和模式串相同，避免哈希冲突
            if (pat.equals(txt.substring(left, right))) {
                return left;
            }
        }
        // 缩小窗口，移出字符
        windowHash = (windowHash - (txt.charAt(left) * RL) % Q + Q) % Q;
        // X % Q == (X + Q) % Q 是一个模运算法则
        // 因为 windowHash - (txt[left] * RL) % Q 可能是负数
        // 所以额外再加一个 Q，保证 windowHash 不会是负数

        left++;
    }
}
// 没有找到模式串
return -1;
}

唯一需要注意的就是

X % Q == (X + Q) % Q 这个模运算法则

将字符串映射成 N 进制数字， 然后再转成10进制存储