字符串匹配算法介绍及js字符串indexOf源码探究

前言

之前学过的字符串匹配算法，一种是朴素算法，一种是KMP算法。

朴素算法即暴力，两层for循环，算法复杂度 O(n*m)

function match(s1,s2){
  var n = s1.length
  var m = s2.length
  f1:
  for(var i=0;i<n;i++){
    if(s1[i]===s2[0]){
      f2:
      for(var j=1;j<m;j++){
        if(s1[i+j]!==s2[j])continue f1;
      }
      return i
    }
  }
  return -1
}

KMP 的实现比较巧妙，下文会提到，我们先来介绍一种新的算法 Rabin-Karp

最近在分析 adblockplus.js 源码的时候了解到的，其实该算法性能比KMP差多了，这里权当学习算法思想

Rabin-Karp 介绍

先进行名词的说明:源串(S1)长度为n,子串(S2)长度为m

暴力之所以会慢，主要在于S1匹配了S2的第一个字符后，还要进行至多m-1个字符的判断。

如果能将S2映射到某个数字num1，S1每次也得到当前m长度字符串的映射数字num2，判断num1和num2是否相同（一次操作）即可快速判断两个字符串可能相同。

上面说法需要注意两个问题：

1. S1每次计算m长度字符串的映射数字需要足够快，必须仅做一次操作
2. num1和num2相同仅能判断两个字符串可能相同，还需要进行字符串每一位的判断

如何快速计算字符串的映射数字呢？

我们假设 s1="jijiaxing" s2="jia"，字符对应的数字采用ASCII值，取ASCII字符集长度M为128

左部为高位，最高位hash值为 s2[0].charCodeAt(0)*(128**(m-1)) ( ** 在js中表示指数运算)

计算s2("jia")对应的hash值：

1. hash("j")=106
2. hash("ji")=hash("j")*128+105=13673
3. hash("jia")=hash("ji")*128+97=1750241

我们可以添加或者删减一个字符，快速得到新字符串的hash值

hash("iax")=(hash("jia")-hash("j")*(128**2))*128+120=(1750241-106*16384)*128+120=1732856

这样我们就可以先计算s1前m长度字符串的hash值，hash值一致再逐个比较，否则删去第一个字符，从s1再加一个字符，继续比较。。

前面的操作，我们没有做 mod 运算，当s2长度计算出来的hash值过大的时候，(js大数运算相对耗时)，我们需要对该值取余散列。假设哈希表长度Q为 10007

于是前面的操作hash("jia")变成:

1. hash("j")=106%10007=106

2. hash("ji")
   =(106*128+105)%10007
   =((106*128)%10007+105%10007)%10007
   =(((106%10007)*(128%10007))%10007+105%10007)%10007
   =((hash("j")*128)%10007+105%10007)%10007
   =((hash("j")*128)+105)%10007
   =3666

   即，hash("ji")=((hash("j")*128)+105)%10007

3. 同理，hash("jia")=(hash("ji")*128+97)%10007=9023

增减字符串的计算过程如下：

hash("iax")
=(105*(128**2)+97*128+120)%10007
=((105*(128**2)+97*128)%10007+120%10007)%10007
=(((105*128+97)%10007*128%10007)%10007+120%10007)%10007
=(((106*(128**2)+105*128+97-106*(128**2))%10007*128%10007)%10007+120%10007)%10007
=((((106*(128**2)+105*128+97)%10007-(106*(128**2))%10007+10007)%10007*128%10007)%10007+120%10007)%10007
//用hash("jia")替换
=((((hash("jia")-(106*(128**2))%10007+10007)%10007*128%10007)%10007+120%10007)%10007
=(((hash("jia")+(10007-(106*(128**2))%10007))%10007*128%10007)%10007+120%10007)%10007
//化简10007-(106*(128**2))%10007
//=(10007-(106*(128**2))%10007)%10007
//增加一个10007倍数的值，不影响
//=(10007-(106*(128**2))%10007+105*10007)%10007
//=(106*10007-106*(128**2)%10007)%10007
//=(106*(10007-128**2%10007))%10007 
=((((106*(128**2)+105*128+97)%10007+(106*(10007-128**2%10007))%10007)%10007*128%10007)%10007+120%10007)%10007
=(((hash("jia")+(106*(10007-128**2%10007))%10007)*128)%10007+120%10007)%10007
=(((hash("jia")+(106*(10007-128**2%10007))%10007)*128)+120)%10007
// 计算本例的固定值10007-128**2%10007=3630
=(((hash("jia")+106*3630%10007)*128)+120)%10007
=(((9023+106*3630%10007)*128)+120)%10007
=1645

计算的时候，采用该式子： (((hash("jia")+106*3630%10007)*128)+120)%10007

以上用到了 同余定理

A*B % C = (A%C * B%C)%C
(A+B)%C = (A%C + B%C)%C
(A-B)%C = (A%C - B%C + C)%C // js运算中 -2%5=-2而不是3 故这里我们需要补上C,让差大于0

下面给出Rabin-Karp的简单实现：

var Q = 10007
var M = 128
function getHash(str,len){
  var val = 0
  for(var i=0;i<len;i++){
    val=(val*M+str[i].charCodeAt(0))%Q
  }
  return val
}
//逐个比较相同长度字符串,s1从index位置开始取
function compare(s1,s2,offset){
  for(var i=0;i<s2.length;i++){
    if(s1[i+offset]!==s2[i])return false
  }
  return true
}
function match(s1,s2){
  var n = s1.length
  var m = s2.length
  if(n<m)return -1
  var s2Hash = getHash(s2,m)
  // 一个固定值
  var fix = Q-M**(m-1)%Q
  var curHash = getHash(s1,m)
  if(curHash===s2Hash&&compare(s1,s2,0))return 0
  for(var i=m;i<s1.length;i++){
    var offset = i-m+1
    curHash = (((curHash+(s1.charCodeAt(i-m))*fix%Q)*M)+s1.charCodeAt(i))%Q
    if(curHash===s2Hash&&compare(s1,s2,offset))return offset
  }
  return -1
}
//match("jijiaxing","jia")=2

效率

理论时间复杂度为O(n*m),但是由于hash不一致能排除大部分情况，故实际复杂度大概在O(n+m)

参考

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

KMP 算法介绍

有空写..

js indexOf源码

ECMAScript 2015中的定义: String.prototype.indexOf

v8 源码实现

1. 参数检查

Object* String::IndexOf(Isolate* isolate, Handle<Object> receiver,
                        Handle<Object> search, Handle<Object> position) {
  if (receiver->IsNullOrUndefined(isolate)) {
    THROW_NEW_ERROR_RETURN_FAILURE(
        isolate, NewTypeError(MessageTemplate::kCalledOnNullOrUndefined,
                              isolate->factory()->NewStringFromAsciiChecked(
                                  "String.prototype.indexOf")));
  }
  Handle<String> receiver_string;
  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, receiver_string,
                                     Object::ToString(isolate, receiver));

  Handle<String> search_string;
  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, search_string,
                                     Object::ToString(isolate, search));

  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, position,
                                     Object::ToInteger(isolate, position));

  uint32_t index = receiver_string->ToValidIndex(*position);
  return Smi::FromInt(
      String::IndexOf(isolate, receiver_string, search_string, index));
}

2. 确定字符编码对应的查找方法

int String::IndexOf(Isolate* isolate, Handle<String> receiver,
                    Handle<String> search, int start_index) {
  DCHECK_LE(0, start_index);
  DCHECK(start_index <= receiver->length());

  uint32_t search_length = search->length();
  if (search_length == 0) return start_index;

  uint32_t receiver_length = receiver->length();
  if (start_index + search_length > receiver_length) return -1;

  receiver = String::Flatten(isolate, receiver);
  search = String::Flatten(isolate, search);

  // 不开gc vectors保持有效
  DisallowHeapAllocation no_gc;  // ensure vectors stay valid
  // Extract flattened substrings of cons strings before getting encoding.
  // 获取扁平字串？
  String::FlatContent receiver_content = receiver->GetFlatContent();
  String::FlatContent search_content = search->GetFlatContent();

  // dispatch on type of strings
  // 根据字符串编码类型
  if (search_content.IsOneByte()) {
    Vector<const uint8_t> pat_vector = search_content.ToOneByteVector();
    return SearchString<const uint8_t>(isolate, receiver_content, pat_vector,
                                       start_index);
  }
  Vector<const uc16> pat_vector = search_content.ToUC16Vector();
  return SearchString<const uc16>(isolate, receiver_content, pat_vector,
                                  start_index);
}

我们进到 src/string-search.h 中来，

template <typename SubjectChar, typename PatternChar>
int SearchString(Isolate* isolate,
                 Vector<const SubjectChar> subject,
                 Vector<const PatternChar> pattern,
                 int start_index) {
  StringSearch<PatternChar, SubjectChar> search(isolate, pattern);
  return search.Search(subject, start_index);
}

里面定义了几种搜索算法

1. LinearSearch
2. BoyerMooreSearch
3. BoyerMooreHorspoolSearch
4. InitialSearch
5. SingleCharSearch

具体使用哪种，是由初始化StringSearch时定义的

StringSearch(Isolate* isolate, Vector<const PatternChar> pattern)
      : isolate_(isolate),
        pattern_(pattern),
        start_(Max(0, pattern.length() - kBMMaxShift)) {
    if (sizeof(PatternChar) > sizeof(SubjectChar)) {
      if (!IsOneByteString(pattern_)) {
        strategy_ = &FailSearch;
        return;
      }
    }
    int pattern_length = pattern_.length();
    if (pattern_length < kBMMinPatternLength) {
      if (pattern_length == 1) {
        strategy_ = &SingleCharSearch;
        return;
      }
      strategy_ = &LinearSearch;
      return;
    }
    strategy_ = &InitialSearch;
  }

  int Search(Vector<const SubjectChar> subject, int index) {
    return strategy_(this, subject, index);
  }

有空再介绍里面每种算法..