Thuật toán tìm kiếm Rabin Karp

Posted on by cuongth

Giới thiệu về bài toán tìm kiếm mẫu, string: https://stackjava.com/mot-so-thuat-toan-tim-kiem-mau, tìm kiếm mẫu với thuật toán tìm kiếm Rabin Karp, cài đặt rabin karp.

Thuật toán tìm kiếm Rabin Karp

Tư tưởng chính của phương pháp này là sử dụng phương pháp băm (hashing). Tức là mỗi một xâu sẽ được gán với một giá trị của hàm băm (hash function), ví dụ xâu “hello” được gán với giá trị 5 chẳng hạn, và hai xâu được gọi là bằng nhau nếu giá trị băm của nó bằng nhau. Như vậy thay vì việc phải đối sánh các xâu con của y với mẫu x, ta chỉ cần so sánh giá trị hàm băm của chúng và đưa ra kết luận. Hàm băm được dùng ở đây là hàm băm rollHash tức là giá trị băm của chuỗi con tiếp theo được tính dựa theo giá trị băm của chuỗi con trước đó như thế sẽ tiết kiệm được nhiều công sức

Hash(x[0,1,…,m-1])= x[0]*2­m-1+ x[1]*2m-2+…+x[m-1]*20

Đặc điểm:

  • Thực hiện trái qua phải
  • Có pha tiền xử lí với độ phức tạp O(m)
  • Độ phức tạp xấu nhất O(mn) mong đợi O(m+n)

Input:

  • Xâu mẫu x=(x0,x1,…,xm-1) độ dài m
  • Xâu văn bản: y= (y0, y1,…, yn-1) độ dài n

Ouput: tất cả các vị trí của x trong y

Cài đặt thuật toán:

public class RabinKarp {
  // tính giá trị băm của một mảng kí tự
  public static int hash(char[] x) {
    int result = 0;
    for (int i = 0; i < x.length; i++) {
      result = (int) (result + (int) x[i] * Math.pow(2, x.length - i - 1));
    }
    return result;
  }

  // tính giá trị băm của 1 mảng kí tự dựa t rên giá trị băm đã tính trước đó
  // a: là kí tự đầu tiên của mảng trước đó
  // b: là kí tự cuối cùng của mảng mới
  // h: là giá trị băm của mảng cũ
  // m: là chiều dài của chuỗi cần so sánh
  public static int rehash(char a, char b, int h, int m) {
    int result = 0;
    result = (int) ((2 * (h - a * Math.pow(2, m - 1))) + b);
    return result;
  }

  // in ra các vị trí của x trong y
  public static void search(char[] x, char[] y) {

    int hx = hash(x);
    char[] init = Arrays.copyOfRange(y, 0, x.length);
    int hy = hash(init);
    System.out.println("hx= " + hx);
    System.out.println("hy ban dau= " + hy);

    if (hx == hy) {
      System.out.println("Vị trí trùng nhau: 0");
    }

    for (int i = 1; i <= y.length - x.length; i++) {
      hy = rehash(y[i - 1], y[i + x.length - 1], hy, x.length);
      // System.out.println(hy);
      if (hx == hy) {
        System.out.println("vị trí trùng nhau: "+ i);
      }
    }
  }
  
  public static void main(String[] args) {
    search("GCAGAGAG".toCharArray(), "GCATCGCAGAGAGTTATACAGTACG".toCharArray());
  }

}

Kết quả:

Thuật toán tìm kiếm Rabin Karp

Kiểm nghiệm thuật toán:

Thuật toán tìm kiếm Rabin Karp, cài đặt rabin karp

 

stackjava.com