你的位置:首页 > Java教程

[Java教程]使用后缀数组寻找最长公共子字符串JavaScript版


     后缀数组很久很久以前就出现了,具体的概念读者自行搜索,小菜仅略知一二,不便讨论。

     本文通过寻找两个字符串的最长公共子字符串,演示了后缀数组的经典应用。

     首先需要说明,小菜实现的这个后缀数组算法,并非标准,只是借鉴了其中的思想。

     小菜实现的算法,有两个版本,第一个是空间换时间,第二个是时间换空间。

空间换时间版本

 1 /* 2  利用后缀数组获取两个字符串最长公共子字符串 3  空间换时间版本 4  @params 5   s1 String,要分析的字符串 6   s2 String,要分析的字符串 7   norepeat Boolean,是否对结果进行去重,默认true 8 */ 9 function commonSubString(s1, s2, norepeat){ 10  var norepeat = norepeat == undefined ? true : norepeat, 11    array = suffixArray(s1, 1).concat(suffixArray(s2, 2)), 12    maxLength = 0, 13    maxStrings = [], 14    tempLength = 0, 15    i = 0, 16    length = 0, 17    result = {}; 18   19  //排序,根据字符串排序,直接比较即可 20  array.sort(function(s1, s2){ 21   return (s1.s == s2.s) ? 0 : (s1.s > s2.s) ? 1 : -1; 22  }); 23   24  //寻找最长公共子字符串 25  for(i = 0, length = array.length - 1; i < length; i++){ 26   tempLength = commonLength(array[i].s, array[i+1].s); 27   if(array[i].g != array[i+1].g){ 28    if(maxLength == tempLength){ 29     maxStrings.push(array[i]); 30    } 31    if(maxLength < tempLength){ 32     maxLength = tempLength; 33     maxStrings = []; 34     maxStrings.push(array[i]); 35    } 36   } 37  } 38   39  //构造结果 40  result.length = maxLength; 41  result.contents = []; 42  for(i in maxStrings){ 43   result.contents.push(maxStrings[i].s.substring(0, maxLength)); 44  } 45   46  //去重 47  if(norepeat){ 48   result.contents = norepeatArray(result.contents); 49  } 50   51  return result; 52   53  /* 54   获取字符串的后缀数组 55  */ 56  function suffixArray(s, g){ 57   var array = [], 58     i = 0, 59     length = s.length; 60   for(i = 0; i < length; i++){ 61    array.push({ 62     s: s.substring(i), 63     g: g  //加分组是为了保证最长公共子字符串分别来自两个字符串 64    }); 65   } 66    67   return array; 68  } 69  /* 70   获取最大匹配长度 71  */ 72  function commonLength(s1, s2){ 73   var slength = s1.length > s2.length ? s2.length : s1.length, 74     i = 0; 75    76   //循环次数=较短的字符串长度 77   for(i = 0; i < slength; i++){ 78    //逐位比较 79    if(s1.charAt(i) != s2.charAt(i)){ 80     break; 81    } 82   } 83    84   return i; 85  } 86   87  /* 88   字符串数组去重,不会影响原数组,返回一个新数组 89  */ 90  function norepeatArray(array){ 91   var _array = array.slice(0), 92     map = {}, 93     i = 0, 94     key = ""; 95    96   //将内容作为散列的key 97   for(i in _array){ 98    map[_array[i]] = 1; 99   }100   101   //提取散列key,重新填充到数组102   _array.splice(0, _array.length);103   for(key in map){104    _array.push(key);105   }106   107   return _array;108  }109 }

View Code

时间换空间版本

 1 /* 2  利用后缀数组获取两个字符串最长公共子字符串 3  时间换空间版本 4  @params 5   s1 String,要分析的字符串 6   s2 String,要分析的字符串 7   norepeat Boolean,是否对结果进行去重,默认true 8 */ 9 function commonSubStringPro(s1, s2, norepeat){ 10  var norepeat = norepeat == undefined ? true : norepeat, 11    array = suffixArray(s1, 1).concat(suffixArray(s2, 2)), 12    maxLength = 0, 13    maxStrings = [], 14    tempLength = 0, 15    i = 0, 16    length = 0, 17    result = {}; 18   19  //排序,根据实际内容排序,不能根据指针排序 20  array.sort(function(s1, s2){ 21   var ts1 = s1.str.substring(s1.index), 22     ts2 = s2.str.substring(s2.index); 23   return (ts1 == ts2) ? 0 : (ts1 > ts2) ? 1 : -1; 24  }); 25   26  //寻找最长公共子字符串 27  for(i = 0, length = array.length - 1; i < length; i++){ 28   tempLength = commonLength(array[i], array[i+1]); 29   if(array[i].group != array[i+1].group){ 30    if(maxLength == tempLength){ 31     maxStrings.push(array[i]); 32    } 33    if(maxLength < tempLength){ 34     maxLength = tempLength; 35     maxStrings = []; 36     maxStrings.push(array[i]); 37    } 38   } 39  } 40   41  //构造结果 42  result.length = maxLength; 43  result.contents = []; 44  for(i in maxStrings){ 45   result.contents.push(maxStrings[i].str.substr(maxStrings[i].index, maxLength)); 46  } 47   48  //去重 49  if(norepeat){ 50   result.contents = norepeatArray(result.contents); 51  } 52   53  return result; 54   55  /* 56   获取字符串的后缀数组 57   只存指针,不存实际内容 58  */ 59  function suffixArray(s, g){ 60   var array = [], 61     i = 0, 62     length = 0; 63   for(i = 0, length = s.length; i < length; i++){ 64    array.push({ 65     index: i, 66     str: s,  //这里仅仅存放的是字符串指针,不会创建多个副本 67     group: g  //加分组是为了保证最长公共子字符串分别来自两个字符串 68    }); 69   } 70    71   return array; 72  } 73  /* 74   获取最大匹配长度 75  */ 76  function commonLength(s1, s2){ 77   var slength = 0, 78     i = 0; 79    80   //循环次数=较短的字符串长度 81   slength = (s1.str.length - s1.index) > (s2.str.length - s2.index) ? (s2.str.length - s2.index) : (s1.str.length - s1.index); 82   for(i = 0; i < slength; i++){ 83    //逐位比较 84    if(s1.str.substr(i + s1.index, 1) != s2.str.substr(i + s2.index, 1)){ 85     break; 86    } 87   } 88    89   return i; 90  } 91   92  /* 93   字符串数组去重,不会影响原数组,返回一个新数组 94  */ 95  function norepeatArray(array){ 96   var _array = array.slice(0), 97     map = {}, 98     i = 0, 99     key = "";100   101   //将内容作为散列的key102   for(i in _array){103    map[_array[i]] = 1;104   }105   106   //提取散列key,重新填充到数组107   _array.splice(0, _array.length);108   for(key in map){109    _array.push(key);110   }111   112   return _array;113  }114 }

View Code

     为啥会有两个版本呢?小菜原本只写了空间换时间版本,这个版本实现复杂度低,但是有一个明显的弊端,它占用了太多无谓的内存,分析数据量不大的时候,可以完美胜任,一旦数据量达到一定程度,它表现出来的不仅仅是执行时间变长,而是根本无法运行,除非有足够大的内存。

     基于以上思考,小菜发现在生成后缀数组的时候,根本没必要保存实际字符串,只需记录位置信息即可,这样一来,内存中的大量字符串,均变成一个个整型数值,在做比较的时候,我们甚至不需要还原字符串,直接用位置去截取单个字符即可,最终内存极大节省,这就是时间换空间版本。

     通过时间换空间,带来的不仅仅是节省内存,而是一种质的变化,从不可能变成可能,现在,无论有多大的数据量,只需很小一部分内存,即可支持程序运转,就算运行时间再长,它也是可行的,不会直接崩溃。当然,现在的CPU运行速度已经很快了。

     希望对读者有所启发,至于具体代码,就不多说了,注释很详细。