接尾辞アレイの基本的な概念については、Baiduをお願いします。簡単に言えば、接尾辞アレイは、文字列のすべての接尾辞サイズのコレクションです。その後、接尾辞アレイの一部のプロパティに基づいてさまざまなニーズを実現できます。
パブリッククラスmysuffixarraytest {public char wubl suffix; //オリジナル文字列public int n; // string length public int [] lank; //すべての接尾辞パブリックint [] saランク）public int [] heigh; //は接尾辞[sa [i]]と接尾辞[sa [i -1]]、つまり2つの隣接する接尾辞の最長のパブリックプレフィックスを示します。 y; // 2番目のキーワードランク配列public int [] x; // rank Auxiliary Array}次の説明では、文字列「aabaaaab」を例として掲載します。最初に結果を示しましょう。理解と分析については、この結果を参照してください（この結果の他の人の写真をコピーしました。サブスクリプト1をデフォルトでご利用ください。
接尾辞：元の文字列アレイは、元の文字列が「aabaaaab」であると想定しています。この配列の対応する値は、{'a'、 'a'、 'b'、 'a'、 'a'、 'a'、 'b'である必要があります。
n：ここの文字列長は8です
ランク：接尾辞配列のランキング配列は、i番目の接尾辞に対応するランキングに相当します。たとえば、ランク[0]は、接尾辞「aabaaaab」ランクのランキングを指します。
SA：これは、ランク配列に逆のアレイです。 Xノードは接尾辞を保存しますか？または、SA [0]が最初のランクの接尾辞アレイ、つまり3、つまり、配列の対応するランク[3]が0です。式SA [ランク[i]] = iを理解してください。 SAとランクの関係を理解している場合は、それも理解する必要があります。
高さ：高さ[I]は、SA [I]接尾辞アレイの最大の共通接頭辞の長さであり、SA [I-1]接尾辞アレイの高さ[1]は、「AAAB」および「AAAAB」の最大の共通接頭辞SA [1]およびSA [0]を指します。
H：h [i]はi番目の接尾辞を指し、前の1つの最大のパブリックプレフィックスを指します[0]は、最初の接尾辞アレイ、すなわち「aabaaaab」と「aab」の最大のパブリックプレフィックス、つまり「rank [0]] = height [3] = 3を指します。あなたは当分の間理解することができず、読み続けます。
WS：補助配列のソートをカウントすることはありません
Y：2番目のキーワードソートは、2番目のキーワードが2番目のキーワードに相当するSAアレイです。
X：ランクアレイのバックアップとして理解できます。最初はランクアレイバックアップを使用し、各ループの後にランク配列を記録します
まず、SAアレイのコードを見てみましょう。コードの機能を1つずつ説明し、総コードを次のものに添付します
rank = new int [n]; sa = new int [n]; ws = new int [255]; y = new int [n]; x = new int [n]; //元の文字列をループして、int値をランク配列に変換します（int i = 0; i <n; i ++）{rank [i] =（int）suffix [i]; }上記のコードの機能は、配列を初期化し、最初のカウントとソートを実行することです。最初のループは、ランク配列に初期値を割り当てることです。実行後、ランク配列の対応する値は{97、97、98、97、97、97、97、98}です。ランク配列の初期値は、文字に対応するASCIIコードであることがわかります。
次の3つのサイクルは、最初のカウントソートです。選別のカウントがわからない場合は、Baiduをお願いします。これら3つのサイクルのプロセスについて話させてください
for（int i = 0; i <n; i ++）{ws [rank [i]] ++; x [i] = rank [i]; } for（int i = 1; i <ws.length; i ++）{ws [i]+= ws [i -1]; }これらの2つのループが行うことは、すべての発生値をカウントし、Xアレイにランク配列をバックアップすることです。最初のループが実行された後、WS [97] = 6、WS [98] = 2、および2番目のループが実行された後、WS [97] = 6、WS [98] = 8
for（int i = n-1; i> = 0; i-）{sa [ - ws [rank [i]]] = i; }上記の段落は、SAアレイを見つけるためのカウントとソートのための特定のコードです。誰もが初めて読んだときに誤解しているに違いありません。なぜ彼らはSAを見つけたのですか？私も初めて混乱しましたが、忍耐強く、このコードを注意深く理解してください。上記のSA [rank [i]] = i上記の式を覚えていますか？明らかに、SA [98]は存在しませんが、WSアレイに98が表示される回数を記録したため、WS [98]は「B」の対応するランキングである必要があります。 1を差し引くことを忘れないでください。背中から前面へと移動する必要がある理由については、ここで慎重に理解する必要があります。そうしないと、2番目のキーワードに従って並べ替えによって完全に盲目になります。同じ2つのランク値がある場合、どのように並べ替えますか？ SAアレイの前に最初に表示する必要があります。このループとWSアレイ値の変更について考えると、ランク値が同じ場合、forループの順序は実際に配置の順序を表すことを理解できます。後方から前面へのトラバーサルは、ランク値が同じ場合、接尾辞のランキングも低いことを意味します。
上記は最初のカウントソートにすぎません。これは、各接尾辞アレイの最初の文字をSAを見つける最初の文字のみを比較するのと同等です。対応する結果は、下の図に示されています。
//ループの組み合わせsort（int j = 1、p = 0; j <= n; j = j << 1）{//それを入力する必要がある場合は、並べ替え配列を最初に追加しますyp = 0; for（int i = n -j; i <n; i ++）{y [p ++] = i; } // 2番目のキーワードの範囲の最初のキーワードsa for（int i = 0; i <n; i ++）{if（sa [i]> = j）{y [p ++] = sa [i] -j; }} // 2つのキーワードのソート（int i = 0; i <ws.length; i ++）{ws [i] = 0; } for（int i：x）{ws [i] ++; } for（int i：x）{ws [i] ++; } for（int i = 1; i <ws.length; i ++）{ws [i]+= ws [i -1]; } for（int i = n-1; i> = 0; i-）{sa [ - ws [x [y [i]]] = y [i]; y [i] = 0; } // sa int xb [] = new int [n]; // xアレイバックアップ（int i = 0; i <n; i ++）{xb [i] = x [i]; } int number = 1; x [sa [0]] = 1; for（int i = 1; i <n; i ++）{if（xb [sa [i]]！= xb [sa [i -1]]）{x [sa [i]] = ++ number; } else if（sa [i] + j> = n && sa [i -1] + j> = n）{x [sa [i]] = number; } else if（sa [i] + j <n && sa [i -1] + j> = n）{x [sa [i]] = ++ number; } else if（xb [sa [i] + j]！= xb [sa [i -1] + j]）{x [sa [i]] = ++ number; } else {x [sa [i]] = number; } if（number> = n）break; }}これは、SAアレイを見つけるときに理解するのが最も難しいコードです。まず、乗算アルゴリズムのアイデアを理解する必要があります。最初のカウント順序の後、すべての接尾辞アレイの最初の初期文字の並べ替えをすでに知っていますか？最初の最初の文字の並べ替えは彼の2番目の文字の順序に相当することを知っているので（並べ替えと順序の違いに注意してください。ソートは、彼が固定されているものを知っていることです。順序は、彼が表示される順序しか知らないことですが、彼がどのようにランク付けされているのかわからないことです）。もちろん、これは元々弦からのものであり、各接尾辞については、以前の接尾辞の接尾辞としても使用できます。たとえば、「baaaab」の場合、最初の文字の順序は、「abaaaab」の2番目のキーワード順序に対応しています。最初のキーワードの順序と2番目のキーワードの種類を使用すると、2つのキーワードの組み合わせの種類を見つけることができます。組み合わせソートの結果によると、以前のアイデアを使用できます。 「baaaab」の最初の組み合わせの後、最初の2文字「ba」の順序を整理するため、「aabaaaab」の2番目のキーワードの順序も使用できます。全体のロジックを以下に参照してください
次に、セグメントのコードを分析します
for（int i = n -j; i <n; i ++）{y [p ++] = i; } //最初のキーワードsa for（int i = 0; i <n; i ++）{if（sa [i]> = j）{y [p ++] = sa [i] -j; }}上記のコードは、SA、つまり2番目のキーワードのy配列を見つけることです。Pの初期値は0です。最初のループは、配列の前面に記入する必要がある接尾辞をランク付けすることです。
前のロジック図と組み合わせて、2番目のループのロジックを理解する必要があります。最初のキーワードSAのソート結果を横断します。 if（sa [i]> = j）は、接尾辞を他のサフィックスの2番目のキーワードとして使用できるかどうかを決定します。 Sa [i] = 0が接尾辞アレイ「aabaaaab」を表す場合、最初のループj = 1を例として取ります。明らかに、他の接尾辞の2番目のキーワードとして使用することはできません。他の接尾辞として使用できる2番目のキーワードの場合、彼のSAの順序は対応する2番目のキーワードです。 Sa [i] -Jは、彼の接尾辞を2番目のキーワードとして見つけ、YアレイとP ++に入れます。ここでゆっくりと理解する必要があります。
//（int i = 0; i <ws.length; i ++）{ws [i] = 0; } for（int i：x）{ws [i] ++; } for（int i = 1; i <ws.length; i ++）{ws [i]+= ws [i -1]; } for（int i = n-1; i> = 0; i-）{sa [ - ws [x [y [i]]] = y [i]; y [i] = 0; }上記は、最初のキーワードソートSAと2番目のキーワードソートYに基づいて、組み合わせのソートを見つけることです。このコードは非常にあいまいです。最初にコードを理解することはできませんが、アイデアを理解できます。 2つのキーワードの並べ替えの場合、実際のルールは2つの数字の並べ替えに似ています。たとえば、11と12はサイズを比較し、10ビットが最初のキーワードであり、シングルビットが2番目のキーワードです。 10ビットを比較した後、11 = 12を見つけてから、シングルビットを比較すると、11 <12がわかっています。 10ビットが同じ場合、シングルビットの順序はサイズの順序です。上記の並べ替えを初めてカウントしたとき、ループのカウントソートの順序は、ランクの値が同じ場合に実際に配置の順序を表すと言いました。では、2つのキーワードが1つのカウントソートでマージされた後、どのようにして順序を見つけるのでしょうか？私の理解を教えてください。 1つのカウントソートには実際には2つのソートが含まれています。1つは数値の値の種類、もう1つは発生順序の種類です。ルールは、11と12の比較の以前の例に相当します。数値の値の種類は10ビットであり、発生順序の種類は1ビットです。この時点で、アイデアがあります。値の並べ替えは最初のキーワードでソートされ、発生の並べ替えは2番目のキーワードでソートされるため、2つのキーワードが組み合わされた後、一度にカウントしてソートするためにソートを見つけることができます。上記のコードは、このアイデアの実装です。 X配列は最初のキーワードのランク配列であり、カウントします。
for（int i = n-1; i> = 0; i-）{sa [ - ws [x [y [i]]] = y [i]; y [i] = 0; }このループは、上記のすべてのアイデアの実装です。背面から2番目のキーワード配列yを横断します。 y [i]の場合、最初のキーワードのカウントランキングを計算します。このカウントランキングはy [i]のランキングであり、最終カウントは1削減されます。マージされたキーワードソートは正常に見つかりました。
上記のコードをすべて理解すれば、間違いなく驚かれることになると思います。また、このコードについて何度も何度も考えたとき、私は興奮していましたが、私は単に確信していました。これがアルゴリズムの魅力です。
SAアレイを使用すると、ランク配列を見つけることができます。これは難しくないので、説明しません。 SAを見つけるためのすべてのコードを以下に添付します。
public static void main（string [] args）{string str = "aabaaaab"; mysuffixarraytest arraytest = new mysuffixarraytest（str.tostring（））; arraytest.initsa（）; // sa array} public void initsa（）{rank = new int [n]; sa = new int [n]; ws = new int [255]; y = new int [n]; x = new int [n]; //元の文字列をループして、int値をランク配列に変換します（int i = 0; i <n; i ++）{rank [i] =（int）suffix [i]; } //最初のカウントsort（int i = 0; i <n; i ++）{ws [rank [i]] ++; x [i] = rank [i]; } for（int i = 1; i <ws.length; i ++）{ws [i]+= ws [i -1]; } for（int i = n-1; i> = 0; i-）{sa [ - ws [rank [i]]] = i; } //（int j = 1、p = 0; j <= n; j = j << 1）for（int j = 1、p = 0; j = j << 1）for（//入力する必要がある場合は、並べ替えられた配列を最初に追加します= 0; for（int i = n -j; i <n; i ++）{y [p ++] = i; } // 2番目のキーワードの範囲の最初のキーワードsa for（int i = 0; i <n; i ++）{if（sa [i]> = j）{y [p ++] = sa [i] -j; }} // 2つのキーワードのソート（int i = 0; i <ws.length; i ++）{ws [i] = 0; } for（int i：x）{ws [i] ++; } for（int i = 1; i <ws.length; i ++）{ws [i]+= ws [i -1]; } for（int i = n-1; i> = 0; i-）{sa [ - ws [x [y [i]]] = y [i]; y [i] = 0; } // sa int xb [] = new int [n]; // xアレイバックアップ（int i = 0; i <n; i ++）{xb [i] = x [i]; } int number = 1; x [sa [0]] = 1; for（int i = 1; i <n; i ++）{if（xb [sa [i]]！= xb [sa [i -1]]）{x [sa [i]] = ++ number; } else if（sa [i] + j> = n && sa [i -1] + j> = n）{x [sa [i]] = number; } else if（sa [i] + j <n && sa [i -1] + j> = n）{x [sa [i]] = ++ number; } else if（xb [sa [i] + j]！= xb [sa [i -1] + j]）{x [sa [i]] = ++ number; } else {x [sa [i]] = number; } if（number> = n）break; }}}}要約します
上記は、紹介されたJavaサフィックスアレイのSACアレイのサンプルコードです。それがあなたに役立つことを願っています。ご質問がある場合は、メッセージを残してください。編集者は時間内に返信します。 wulin.comのウェブサイトへのご支援ありがとうございます！