javascript拡張配列

8127 ワード
javascript アルゴリズム
接尾配列は文字列を処理する利器であり、それ自体は多くの補助概念を含む.
基本概念
1.1サブストリング
文字列の一部を表します.awbcdewgはawbc、awbcd、awbcdeなどのサブストリングを持っています.
1.2サフィックス
サフィックスとは、文字列がある場所から最後に到達する特殊なサブストリングです.サフィックスは自分自身に等しいことができます.相は1文字から始まります.サフィックスを取る関数を設計します.このように実現できます.
function suffix(str, i ){
    if(i >= 0 || i <= str.length-1){
       return str.slice(i)
    }
    throw "i   "
}
最後の文字を含む必要があります.
文字列rubylouvreは、そのサフィックスにはrubylouvre、bylouvre、bylouvre、ylouvre、louvre、ouvre、uvre、vre、eが含まれています.
1.3辞書の並べ替え
文字列のデフォルトの比較アルゴリズムは、「aa」「ab」がfalseに戻るのではなくtrueに戻ります.
まず左から右へ、それぞれ第一文字を取得します.「a」と「a」は同じであれば、それぞれの第二文字を比較します.そうでなければ、charCodeの値を比較します.iとb比、iのcharCodeは105、bのcharCodeは98、bはiより小さいです.
その中の一つが別のプレフィックスであれば、短いその列の前:aa
1.4サフィックス配列
バックエンド配列とは、ある文字列のすべてのサフィックスを辞書順に並べ替えて得られた位置配列のことです.文字列ADCEFDのように、iが0から5までインクリメントされるとき、上のスffix関数を通じて、そのサフィックスをすべて取得します.
index
A
D
C
E
F
D
0
A
D
C
E
F
D
1
 
D
C
E
F
D
2
 
 
C
E
F
D
3
 
 
 
E
F
D
4
 
 
 
 
F
D
5
 
 
 
 
 
D
辞書で並べ替えたら
index
A
D
C
E
F
D
0
A
D
C
E
F
D
2
 
 
C
E
F
D
5
 
 
 
 
 
D
1
 
D
C
E
F
D
3
 
 
 
E
F
D
4
 
 
 
 
F
D
この[0,2,5,1,3,4]は文字列のサフィックス配列です.
// by     
var str = "ADCEFD", arr = []
function spawnSuffix(str, arr){
     if(str){
        arr.push(str)
        spawnSuffix(str.slice(1), arr)
     }
 }
spawnSuffix(str, arr)
console.log(arr)
//["ADCEFD", "DCEFD", "CEFD", "EFD", "FD", "D"]
//  abadefg             
var sa = arr.map(function(str, i){
  return {el: str, index: i}
}).sort(function(a, b){
 return a.el > b.el
}).map(function(obj){
 return obj.index  //   1，     ，     
})
console.log(sa)// [0, 2, 5, 1, 3, 4]
倍増アルゴリズム
上の方は非常にシンプルな方法で、一つ一つの接尾辞を取って、言語そのもののsort方法によって辞書を並べます.このsortは異なる宿主環境の中で、内部で取った順序付けアルゴリズムは全部違っています.ブラックボックスです.
全体の過程では、ロバートの論文を参考にしてもいいですが、言葉の違いから彼が何を書いているのか分かりません.直接にその絵に向かってやりました.
// by     
function getSuffix(str) {
    var len = str.length, 
        max = str.charCodeAt(0), 
        min = max,
        xbuckets = [],
        sa = [],
        rank = [];
    //               charCode ，        
    for (let i = 0; i < len; i++) {
        let c = str.charCodeAt(i);
        rank[i] = c;
        max = Math.max(max, c);
        min = Math.min(min, c);
    }
    //    rank      ，      ，  90－128  ，
    //            
    //         ，     ,     2－10     。

    //                     x    
    //          ，      rank         
    rank.forEach(function(el, i){
        rank[i] = {x: el - min + 1 };
    });
  
    var hasDuplicate = true, k = 0;
    while(hasDuplicate){
        //    
        hasDuplicate = false;
        xbuckets.length = 0;
        //k  ，    y  
        //y             
        var d = 1 << k; k ++;
        rank.forEach(function(el, i){
            el.y = rank[i+ d] ? rank[i+ d].x: 0;
        });
        //     x，      
        rank.forEach(function(el){
            var index = el.x;
            if(!xbuckets[index]){
                xbuckets[index] = [el];
            }else{
                xbuckets[index].push(el);
            }
        });
        //     xbucket  y    
        var newIndex = 1, last = {};
        xbuckets.forEach(function(bucket){
            if(bucket){
                let cache = {};
                bucket.sort(function(a, b){
                    return a.y - b.y;
                }).forEach(function(el ){
                    //  x
                    if(el.y !== last.y){
                        el.x = newIndex++;
                        cache[el.y] = el.x;
                    }else{
                        hasDuplicate = true;
                        el.x = cache[el.y];
                    }
                    last = el;
                });
            }
        });
    }
    //rank  1   ，       1
    rank = rank.map(function(el, i ){
        sa[el.x - 1] = i;
        return el.x;
    });
    console.log("rank  ", rank);
    console.log("    ", sa);
    return sa;
}

var ret = getSuffix("aabaaaab"); 
//ret:  3, 4, 5, 0, 6, 1, 7, 2 
/*
しかし、これは生のsortに依存しています.私たちはsortをカウントアップに変えられます.
// by     
function getSuffix(str) {
    var len = str.length, 
        max = str.charCodeAt(0), 
        min = max,
        xbuckets = [],
        sa = [],
        rank = [];
    //     charCode
    for (let i = 0; i < len; i++) {
        let c = str.charCodeAt(i);
        rank[i] = c;
        max = Math.max(max, c);
        min = Math.min(min, c);
    }
    //  charCode 
    rank.forEach(function(el, i){
        rank[i] = {x: el - min + 1 };
    });
    var hasDuplicate = true, k = 0;
    while(hasDuplicate){
        //    
        hasDuplicate = false;
        xbuckets.length = 0;
        //  ，       y
        var d = 1 << k; k ++;

        rank.forEach(function(el, i){
            //     x，      ，        y
            el.y = rank[i+ d] ? rank[i+ d].x: 0;
           
            var index = el.x;
            if(!xbuckets[index]){
                xbuckets[index] = [el];
            }else{
                xbuckets[index].push(el);
            }
        });

        var newIndex = 1, last = {};
        xbuckets.forEach(function(bucket){
            if(bucket){
                //               
                var cache = {};
                var yxbuckets = [];
                bucket.forEach(function(el){
                    var index = el.y;
                    if(!yxbuckets[index]){
                        yxbuckets[index] = [el];
                    }else{
                        yxbuckets[index].push(el);
                    }
                });
                var j = 0;
                yxbuckets.forEach(function(ybucket){
                    if(ybucket){
                        ybucket.forEach(function(el){
                            if(el.y !== last.y){
                                el.x = newIndex++;
                                cache[el.y] = el.x;
                            }else{
                                hasDuplicate = true;
                                el.x = cache[el.y];
                            }
                            bucket[j++] = el; //      
                            last = el;
                        });
                    }
                });
            }
        });
     
    }
    //rank  1   ，       1
    rank = rank.map(function(el, i ){
        sa[el.x - 1] = i;
        return el.x;
    });
    console.log("rank  ", rank);
    console.log("    ", sa);
    return sa;
}
var a = getSuffix("aabaaaab");
ヘight配列
では、どうやってheightを計算しますか?h[i]=height[rank[i]を定義します.つまり、Suffix[i]とその前の1つの最長共通プレフィックスです.h[i]==h[i-1]-1が明らかにあります.h[i-1]は、Suffix[i-1]とその上位の共通プレフィックスであるため、Suffix[k]とすると、Suffix[i]とSuffix[k+1]の最長の共通プレフィックスはh[i-1]-1であるため、h[i]は少なくともh[i-1]−1である.だから、私たちはht[1],h[2],h[3]の順にすべてのヘightを計算することができます.コードは以下の通りです
//by    
function getHeight(str, sa){
    var n = str.length, k = 0, rank = [], height = []
    for(var i = 1;i<=n;i++) {
        rank[sa[i]]=i;
    }
    for(var i=0;i
DC 3アルゴリズム
DC 3アルゴリズム(Difference Cover mod 3)はJ.K囌rk囌囔inenとP.Sandersが2003年に発表した論文「Simple Liner Work Suffix Aray Costruction」に記述されている線形時間内に後方結合配列を構成するアルゴリズムである.詳細は以下を参照せよ
http://spencer-carroll.com/th...
難しすぎて、省略しました.他にもSA-ISなどの構造アルゴリズムがあります.
https://zhuanlan.zhihu.com/p/...
私は学習の順序を間違えたはずです.まずhashの木を習ってからtrieの木を習ってから、接尾樹を習ってから、つぎの木を習います.こんなに頭がいいとしても、スパンが大きいと顔がほこりだらけになります.
参照リンク
  • http://blog.csdn.net/sojisub_...
  • http://blog.csdn.net/yxuanwke...
  • https://wenku.baidu.com/view/... (PPT)
    • javascriptは同じ属性のパラメータすなわち配列パラメータをバックグラウンドに転送する.