您所在的位置:小祥子 » 编程 » JavaScript » 正文

使用后缀数组寻找最长公共子字符串JavaScript版

时间:2015-05-01 编辑:杨元 来源:本站整理

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

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

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

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

空间换时间版本

 /*
   利用后缀数组获取两个字符串最长公共子字符串
   空间换时间版本
   @params
     s1 String,要分析的字符串
     s2 String,要分析的字符串
     norepeat Boolean,是否对结果进行去重,默认true
 */
 function commonSubString(s1, s2, norepeat){
   var norepeat = norepeat == undefined ? true : norepeat,
       array = suffixArray(s1, 1).concat(suffixArray(s2, 2)),
       maxLength = 0,
       maxStrings = [],
       tempLength = 0,
       i = 0,
       length = 0,
       result = {};
   
   //排序,根据字符串排序,直接比较即可
   array.sort(function(s1, s2){
     return (s1.s == s2.s) ? 0 : (s1.s > s2.s) ? 1 : -1;
   });
   
   //寻找最长公共子字符串
   for(i = 0, length = array.length - 1; i < length; i++){
     tempLength = commonLength(array[i].s, array[i+1].s);
     if(array[i].g != array[i+1].g){
       if(maxLength == tempLength){
         maxStrings.push(array[i]);
       }
       if(maxLength < tempLength){
         maxLength = tempLength;
         maxStrings = [];
         maxStrings.push(array[i]);
       }
     }
   }
   
   //构造结果
   result.length = maxLength;
   result.contents = [];
   for(i in maxStrings){
     result.contents.push(maxStrings[i].s.substring(0, maxLength));
   }
   
   //去重
   if(norepeat){
     result.contents  = norepeatArray(result.contents);
   }
   
   return result;
   
   /*
     获取字符串的后缀数组
   */
   function suffixArray(s, g){
     var array = [],
         i = 0,
         length = s.length;
     for(i = 0; i < length; i++){
       array.push({
         s: s.substring(i),
         g: g   //加分组是为了保证最长公共子字符串分别来自两个字符串
       });
     }
     
     return array;
   }
   /*
     获取最大匹配长度
   */
   function commonLength(s1, s2){
     var slength = s1.length > s2.length ? s2.length : s1.length,
         i = 0;
     
     //循环次数=较短的字符串长度
     for(i = 0; i < slength; i++){
       //逐位比较
       if(s1.charAt(i) != s2.charAt(i)){
         break;
       }
     }
     
     return i;
   }
   
   /*
     字符串数组去重,不会影响原数组,返回一个新数组
   */
   function norepeatArray(array){
     var _array = array.slice(0),
         map = {},
         i = 0,
         key = "";
     
     //将内容作为散列的key
     for(i in _array){
       map[_array[i]] = 1;
     }
     
     //提取散列key,重新填充到数组
     _array.splice(0, _array.length);
     for(key in map){
       _array.push(key);
     }
     
     return _array;
   }
 }
View Code

时间换空间版本

 /*
   利用后缀数组获取两个字符串最长公共子字符串
   时间换空间版本
   @params
     s1 String,要分析的字符串
     s2 String,要分析的字符串
     norepeat Boolean,是否对结果进行去重,默认true
 */
 function commonSubStringPro(s1, s2, norepeat){
   var norepeat = norepeat == undefined ? true : norepeat,
       array = suffixArray(s1, 1).concat(suffixArray(s2, 2)),
       maxLength = 0,
       maxStrings = [],
       tempLength = 0,
       i = 0,
       length = 0,
       result = {};
   
   //排序,根据实际内容排序,不能根据指针排序
   array.sort(function(s1, s2){
     var ts1 = s1.str.substring(s1.index),
         ts2 = s2.str.substring(s2.index);
     return (ts1 == ts2) ? 0 : (ts1 > ts2) ? 1 : -1;
   });
   
   //寻找最长公共子字符串
   for(i = 0, length = array.length - 1; i < length; i++){
     tempLength = commonLength(array[i], array[i+1]);
     if(array[i].group != array[i+1].group){
       if(maxLength == tempLength){
         maxStrings.push(array[i]);
       }
       if(maxLength < tempLength){
         maxLength = tempLength;
         maxStrings = [];
         maxStrings.push(array[i]);
       }
     }
   }
   
   //构造结果
   result.length = maxLength;
   result.contents = [];
   for(i in maxStrings){
     result.contents.push(maxStrings[i].str.substr(maxStrings[i].index, maxLength));
   }
   
   //去重
   if(norepeat){
     result.contents  = norepeatArray(result.contents);
   }
   
   return result;
   
   /*
     获取字符串的后缀数组
     只存指针,不存实际内容
   */
   function suffixArray(s, g){
     var array = [],
         i = 0,
         length = 0;
     for(i = 0, length = s.length; i < length; i++){
       array.push({
         index: i,
         str: s,    //这里仅仅存放的是字符串指针,不会创建多个副本
         group: g   //加分组是为了保证最长公共子字符串分别来自两个字符串
       });
     }
     
     return array;
   }
   /*
     获取最大匹配长度
   */
   function commonLength(s1, s2){
     var slength = 0,
         i = 0;
     
     //循环次数=较短的字符串长度
     slength = (s1.str.length - s1.index) > (s2.str.length - s2.index) ? (s2.str.length - s2.index) : (s1.str.length - s1.index);
     for(i = 0; i < slength; i++){
       //逐位比较
       if(s1.str.substr(i + s1.index, 1) != s2.str.substr(i  + s2.index, 1)){
         break;
       }
     }
     
     return i;
   }
   
   /*
     字符串数组去重,不会影响原数组,返回一个新数组
   */
   function norepeatArray(array){
     var _array = array.slice(0),
         map = {},
         i = 0,
         key = "";
     
     //将内容作为散列的key
     for(i in _array){
       map[_array[i]] = 1;
     }
     
     //提取散列key,重新填充到数组
     _array.splice(0, _array.length);
     for(key in map){
       _array.push(key);
     }
     
     return _array;
   }
 }
View Code

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

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

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

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

关键词:数组 字符 字符串