โปรด Baidu สำหรับแนวคิดพื้นฐานบางอย่างของอาร์เรย์ต่อท้าย พูดง่ายๆคืออาร์เรย์คำต่อท้ายเป็นคอลเลกชันขนาดต่อท้ายทั้งหมดของสตริง จากนั้นเราสามารถบรรลุความต้องการที่หลากหลายตามคุณสมบัติบางอย่างของอาร์เรย์ต่อท้าย
คลาสสาธารณะ mysuffixarraytest {public char [] suffix; // string ดั้งเดิม public int n; // string ความยาวสาธารณะ int [] อันดับ; // การจัดอันดับของคำต่อท้าย [i] ในคำต่อท้ายทั้งหมด int int [] sa; // คำต่อท้าย [sa [1]] <ต่อท้าย [sa [2]] อันดับ) สาธารณะ int [] ความสูง; // หมายถึงคำต่อท้าย [SA [I]] และคำต่อท้าย [SA [I - 1]] นั่นคือคำนำหน้าสาธารณะที่ยาวที่สุดของคำต่อท้ายที่อยู่ติดกันสองอัน, INT [] h; // มีความสูง [อันดับ] y; // คำหลักที่สองอันดับอาร์เรย์สาธารณะ int [] x; // array อันดับเสริม}คำอธิบายต่อไปนี้ใช้สตริง "aabaaaab" เป็นตัวอย่าง ก่อนอื่นแสดงผลลัพธ์ โปรดดูผลลัพธ์นี้เพื่อความเข้าใจและการวิเคราะห์ (ฉันคัดลอกรูปภาพของคนอื่นเกี่ยวกับผลลัพธ์นี้โปรด Subscript 1 โดยค่าเริ่มต้นเนื่องจากอาร์เรย์ของฉันเริ่มต้นด้วยตัวห้อย 0)
คำต่อท้าย: อาร์เรย์สตริงดั้งเดิมถือว่าสตริงต้นฉบับคือ "aabaaaab" จากนั้นค่าที่สอดคล้องกันของอาร์เรย์นี้ควรเป็น {'a', 'a', 'b', 'a', 'a', 'a', 'b'}
n: ความยาวสตริงที่นี่ n คือ 8
อันดับ: อาร์เรย์การจัดอันดับของอาร์เรย์คำต่อท้ายเท่ากับการจัดอันดับที่สอดคล้องกับคำต่อท้าย i-th ตัวอย่างเช่นอันดับ [0] หมายถึงการจัดอันดับของคำต่อท้าย "Aabaaaab" อันดับ [1] หมายถึงการจัดอันดับของคำต่อท้าย "abaaaab"
SA: นี่คืออาร์เรย์ที่ผกผันกับอาร์เรย์อันดับ X-Node เก็บคำต่อท้ายหรือไม่? หรือเพื่อยกตัวอย่างเพื่อแสดงให้เห็นว่า SA [0] หมายถึงอาร์เรย์คำต่อท้ายอันดับแรกนั่นคือ 3. นั่นคืออันดับที่สอดคล้องกัน [3] ของอาร์เรย์คือ 0 โปรดอย่าลืมเข้าใจสูตร SA [อันดับ [i]] = i หากคุณเข้าใจความสัมพันธ์ระหว่าง SA และอันดับคุณควรเข้าใจด้วย
ความสูง: ความสูง [i] คือความยาวของคำนำหน้าทั่วไปที่ใหญ่ที่สุดของ SA [i] คำต่อท้ายอาร์เรย์และ SA [I-1] ความสูงของอาร์เรย์ต่อท้าย [1] หมายถึงคำนำหน้าทั่วไปที่สองและใหญ่เป็นครั้งแรก SA [1] และ SA [0] นั่นคือคำนำหน้าทั่วไปที่ใหญ่ที่สุดของ "AAAB" และ "AAAAB"
H: H [i] หมายถึงคำต่อท้าย i-th และคำนำหน้าสาธารณะที่ใหญ่ที่สุดของหนึ่งก่อนหน้า H [0] หมายถึงอาร์เรย์คำต่อท้ายแรกคือ "aabaaaab" และคำนำหน้าสาธารณะที่ใหญ่ที่สุดของหนึ่งก่อนหน้านี้คือ "AAB" นั่นคือความสูง [0] = ความสูง [3] = 3 คุณไม่สามารถเข้าใจได้ในขณะนี้และอ่านต่อ
WS: ไม่มีอะไรจะพูดนับการเรียงลำดับอาร์เรย์เสริม
y: การเรียงลำดับคำหลักที่สองคืออาร์เรย์ SA ที่มีคำหลักที่สองเรียงลำดับเทียบเท่ากับคำหลักที่สอง
X: คุณสามารถเข้าใจว่ามันเป็นสำรองของอาร์เรย์อันดับ ในขั้นต้นใช้การสำรองข้อมูลอันดับอาร์เรย์จากนั้นบันทึกอาร์เรย์อันดับหลังจากแต่ละลูป
ก่อนอื่นมาดูรหัสสำหรับอาร์เรย์ SA ฉันจะอธิบายฟังก์ชั่นของรหัสหนึ่งทีละหนึ่งและแนบรหัสทั้งหมดกับต่อไปนี้
อันดับ = ใหม่ int [n]; SA = ใหม่ int [n]; ws = new int [255]; y = ใหม่ int [n]; x = ใหม่ int [n]; // วนซ้ำสตริงต้นฉบับเพื่อแปลงค่า int เป็นอาร์เรย์อันดับสำหรับ (int i = 0; i <n; i ++) {road [i] = (int) คำต่อท้าย [i]; -ฟังก์ชั่นของรหัสด้านบนคือการเริ่มต้นอาร์เรย์และทำการนับและการเรียงลำดับแรก ลูปแรกคือการกำหนดค่าเริ่มต้นให้กับอาร์เรย์อันดับ หลังจากดำเนินการค่าที่สอดคล้องกันของอาร์เรย์อันดับคือ {97, 97, 98, 97, 97, 97, 97, 98} คุณควรเห็นว่าค่าเริ่มต้นของอาร์เรย์อันดับคือรหัส ASCII ที่สอดคล้องกับตัวอักษร
สามรอบถัดไปคือการเรียงลำดับการนับครั้งแรก หากคุณไม่เข้าใจการเรียงลำดับการเรียงลำดับโปรด Baidu ให้ฉันพูดคุยเกี่ยวกับกระบวนการของสามรอบนี้
สำหรับ (int i = 0; i <n; i ++) {ws [อันดับ [i]] ++; x [i] = อันดับ [i]; } สำหรับ (int i = 1; i <ws.length; i ++) {ws [i]+= ws [i - 1]; -สิ่งที่ลูปทั้งสองนี้ทำคือนับค่าที่เกิดขึ้นทั้งหมดและสำรองข้อมูลอาร์เรย์อันดับเป็นอาร์เรย์ X หลังจากการวนรอบแรกทำงาน WS [97] = 6, WS [98] = 2 และหลังจากวนรอบที่สองทำงาน WS [97] = 6, WS [98] = 8
สำหรับ (int i = n-1; i> = 0; i--) {sa [-ws [อันดับ [i]]] = i; -ย่อหน้าข้างต้นเป็นรหัสเฉพาะสำหรับการนับและการเรียงลำดับเพื่อค้นหาอาร์เรย์ SA ทุกคนต้องเข้าใจผิดในครั้งแรกที่พวกเขาอ่าน ทำไมพวกเขาถึงพบ SA? ฉันยังสับสนเป็นครั้งแรก แต่โปรดอดทนและเข้าใจรหัสนี้อย่างระมัดระวัง คุณยังจำสูตรที่กล่าวถึงข้างต้น sa [อันดับ [i]] = ฉันตัวอย่างเช่นคำต่อท้าย "b" เราถาม SA ของเขานั่นคือ SA [อันดับ [7]] = SA [98] = 7 เห็นได้ชัดว่า SA [98] ไม่มีอยู่จริง แต่เราได้บันทึกจำนวนครั้งที่ 98 ปรากฏในอาร์เรย์ WS ดังนั้น WS [98] ควรเป็นอันดับที่สอดคล้องกันของ "B" โปรดอย่าลืมลบ 1 ให้เป็น sa [-ws [อันดับ [i]]] = i สำหรับสาเหตุที่คุณต้องสำรวจจากด้านหลังไปด้านหน้าคุณต้องเข้าใจอย่างรอบคอบที่นี่มิฉะนั้นคุณจะตาบอดอย่างสมบูรณ์โดยวิธีที่คุณเรียงลำดับตามคำหลักที่สอง คุณจะเรียงลำดับได้อย่างไรหากมีค่าอันดับสองที่เหมือนกัน? มันจะต้องปรากฏขึ้นก่อนหน้าอาร์เรย์ SA หากคุณคิดเกี่ยวกับลูปนี้และการเปลี่ยนแปลงในค่าอาร์เรย์ WS คุณจะเข้าใจว่าคำสั่งของการวนรอบจริงแสดงถึงลำดับของการจัดเรียงเมื่อค่าอันดับเหมือนกัน การสำรวจจากด้านหน้าไปด้านหน้าหมายความว่าการจัดอันดับคำต่อท้ายจะลดลงเช่นกันเมื่อค่าอันดับเหมือนกัน
ข้างต้นเป็นเพียงการเรียงลำดับการนับครั้งแรกซึ่งเทียบเท่ากับการเปรียบเทียบตัวอักษรตัวแรกของแต่ละอาร์เรย์คำต่อท้ายแต่ละตัวเพื่อค้นหา SA ผลลัพธ์ที่สอดคล้องกันดังแสดงในรูปด้านล่าง
// วนการเรียงลำดับการรวมกันสำหรับ (int j = 1, p = 0; j <= n; j = j << 1) {// ถ้าคุณต้องการเติมให้เพิ่มอาร์เรย์การเรียงลำดับแรก yp = 0; สำหรับ (int i = n - j; i <n; i ++) {y [p ++] = i; } // ช่วงคำหลักที่สองตามคำหลักแรก sa สำหรับ (int i = 0; i <n; i ++) {ถ้า (sa [i]> = j) {y [p ++] = sa [i] - j; }} // การเรียงลำดับคำหลักสองคำสำหรับ (int i = 0; i <ws.length; i ++) {ws [i] = 0; } สำหรับ (int i: x) {ws [i] ++; } สำหรับ (int i: x) {ws [i] ++; } สำหรับ (int i = 1; i <ws.length; i ++) {ws [i]+= ws [i - 1]; } สำหรับ (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 = 1; x [sa [0]] = 1; สำหรับ (int i = 1; i <n; i ++) {ถ้า (xb [sa [i]]! = xb [sa [i - 1]]) {x [sa [i]] = ++ จำนวน; } อื่นถ้า (sa [i] + j> = n && sa [i - 1] + j> = n) {x [sa [i]] = number; } อื่นถ้า (sa [i] + j <n && sa [i - 1] + j> = n) {x [sa [i]] = ++ จำนวน; } อื่นถ้า (xb [sa [i] + j]! = xb [sa [i - 1] + j]) {x [sa [i]] = ++ จำนวน; } else {x [sa [i]] = number; } if (number> = n) break; -นี่เป็นรหัสที่ยากที่สุดที่จะเข้าใจเมื่อค้นหาอาร์เรย์ SA ก่อนอื่นคุณต้องเข้าใจแนวคิดของอัลกอริทึมการคูณ หลังจากคำสั่งซื้อครั้งแรกเรารู้แล้วว่าการเรียงลำดับตัวอักษรเริ่มต้นแรกของอาร์เรย์คำต่อท้ายทั้งหมดหรือไม่? เนื่องจากเรารู้ว่าการเรียงลำดับของตัวอักษรเริ่มต้นตัวแรกนั้นเทียบเท่ากับคำสั่งของตัวอักษรตัวที่สองของเขา (หมายเหตุความแตกต่างระหว่างการเรียงลำดับและคำสั่งการเรียงลำดับคือเรารู้ว่าเขาได้รับการแก้ไขข้อใดคำสั่งคือเรารู้เพียงคำสั่งที่เขาปรากฏ แต่เราไม่รู้ว่าเขาอยู่ในอันดับใด นี่คือแน่นอนเพราะพวกเขามาจากสตริงและสำหรับแต่ละคำต่อท้ายมันยังสามารถใช้เป็นคำต่อท้ายสำหรับคำต่อท้ายก่อนหน้าของเขา ตัวอย่างเช่นการพูดถึง "baaaab" คำสั่งของตัวอักษรตัวแรกสอดคล้องกับคำหลักคำหลักที่สองของ "abaaaab" ด้วยลำดับของคำหลักแรกและการเรียงลำดับของคำหลักที่สองเราสามารถค้นหาการเรียงลำดับของคำหลักสองคำ จากผลของการเรียงลำดับการรวมกันเรายังสามารถใช้แนวคิดก่อนหน้านี้ได้ หลังจากการรวมกันครั้งแรกของ "baaaab" เราจัดลำดับคำสั่งของตัวอักษรสองตัวแรก "BA" ดังนั้นเขาจึงสามารถใช้ลำดับคำหลักที่สองของ "AABAAAAAB" ตรรกะของการเรียงลำดับทั้งหมดอ้างอิงด้านล่าง
จากนั้นเราจะวิเคราะห์รหัสในเซ็กเมนต์
สำหรับ (int i = n - j; i <n; i ++) {y [p ++] = i; } // เลือกคำหลักที่สองตามคำหลักแรก sa สำหรับ (int i = 0; i <n; i ++) {ถ้า (sa [i]> = j) {y [p ++] = sa [i] - j; -รหัสข้างต้นคือการค้นหา SA นั่นคืออาร์เรย์ y ของคำหลักที่สองโดยมีค่าเริ่มต้นของ p เป็น 0 และลูปแรกคือการจัดอันดับคำต่อท้ายที่ต้องกรอกในด้านหน้าของอาร์เรย์
คุณต้องเข้าใจตรรกะของลูปที่สองร่วมกับไดอะแกรมตรรกะก่อนหน้า เราสำรวจผลลัพธ์การเรียงลำดับของคำหลักแรก SA ถ้า (sa [i]> = j) กำหนดว่าคำต่อท้ายสามารถใช้เป็นคำหลักที่สองสำหรับคำต่อท้ายอื่น ๆ ได้หรือไม่ การใช้ลูปแรก j = 1 เป็นตัวอย่างเมื่อ sa [i] = 0 หมายถึงอาร์เรย์ต่อท้าย "aabaaaab" เห็นได้ชัดว่ามันไม่สามารถใช้เป็นคำหลักที่สองสำหรับคำต่อท้ายอื่น ๆ สำหรับคำหลักที่สองที่สามารถใช้เป็นคำต่อท้ายอื่น ๆ คำสั่งของ SA ของเขาคือคำหลักที่สองที่สอดคล้องกัน Sa [i] - J พบคำต่อท้ายของเขาเป็นคำหลักที่สองและวางไว้ในอาร์เรย์ y และ p ++ คุณต้องเข้าใจที่นี่อย่างช้าๆ
// ผสานการเรียงลำดับของคำหลักสองคำสำหรับ (int i = 0; i <ws.length; i ++) {ws [i] = 0; } สำหรับ (int i: x) {ws [i] ++; } สำหรับ (int i = 1; i <ws.length; i ++) {ws [i]+= ws [i - 1]; } สำหรับ (int i = n-1; i> = 0; i--) {sa [-ws [x [y [i]]]] = y [i]; y [i] = 0; -ข้างต้นคือการค้นหาการเรียงลำดับแบบผสมผสานตามคำหลักแรกการเรียงลำดับ SA และการเรียงลำดับคำหลักที่สอง y รหัสนี้ค่อนข้างคลุมเครือ ก่อนอื่นเราไม่สามารถเข้าใจรหัส แต่เข้าใจความคิด สำหรับการเรียงลำดับของคำหลักสองคำกฎจริงจะคล้ายกับการเรียงลำดับของตัวเลขสองตัว ตัวอย่างเช่น 11 และ 12 เปรียบเทียบขนาด 10 บิตเป็นคำหลักแรกและบิตเดียวเป็นคำหลักที่สอง หลังจากเปรียบเทียบ 10 บิตเราพบ 11 = 12 จากนั้นเปรียบเทียบบิตเดียวเรารู้ว่า 11 <12 หาก 10 บิตเหมือนกันลำดับของบิตเดียวคือลำดับขนาด ฉันบอกว่าครั้งแรกที่ฉันนับการเรียงลำดับข้างต้นว่าลำดับของการเรียงลำดับการเรียงลำดับสำหรับลูปจริง ๆ แล้วหมายถึงลำดับของการจัดเรียงเมื่อค่าอันดับเหมือนกัน ดังนั้นเราจะหาคำสั่งซื้อหลังจากคำหลักทั้งสองถูกรวมเข้าด้วยกันในการเรียงลำดับนับได้อย่างไร ให้ฉันบอกความเข้าใจของฉัน การเรียงลำดับหนึ่งการเรียงลำดับมีสองประเภทหนึ่งคือการเรียงลำดับของค่าตัวเลขและอีกประเภทหนึ่งคือการเรียงลำดับของลำดับการเกิดขึ้น กฎนั้นเทียบเท่ากับตัวอย่างก่อนหน้าของการเปรียบเทียบ 11 และ 12 การเรียงลำดับของค่าตัวเลขคือ 10 บิตและการเรียงลำดับของลำดับการเกิดขึ้นคือหนึ่งบิต ณ จุดนี้เรามีความคิด การเรียงลำดับของค่าถูกจัดเรียงตามคำหลักแรกและการเรียงลำดับของเหตุการณ์จะถูกจัดเรียงตามคำหลักที่สองเพื่อให้เราสามารถนับและเรียงลำดับในครั้งเดียวเพื่อค้นหาการเรียงลำดับหลังจากคำหลักทั้งสองรวมกัน รหัสข้างต้นคือการใช้แนวคิดนี้ อาร์เรย์ X เป็นอาร์เรย์อันดับของคำหลักแรกและเรานับมัน
สำหรับ (int i = n-1; i> = 0; i--) {sa [-ws [x [y [i]]]] = y [i]; y [i] = 0; -ลูปนี้เป็นการดำเนินการตามแนวคิดทั้งหมดข้างต้น เราสำรวจอาร์เรย์คำหลักที่สอง y จากด้านหลัง สำหรับ y [i] เราคำนวณการจัดอันดับการนับของคำหลักแรก การจัดอันดับการนับนี้คือการจัดอันดับของ y [i] และการนับสุดท้ายจะลดลง 1 พบการเรียงลำดับคำหลักที่ผสานได้สำเร็จ
ฉันเชื่อว่าถ้าคุณเข้าใจรหัสข้างต้นทั้งหมดคุณจะประหลาดใจอย่างแน่นอน ฉันก็ตื่นเต้นเมื่อฉันคิดถึงรหัสนี้ซ้ำแล้วซ้ำอีกและฉันก็มั่นใจ นี่คือเสน่ห์ของอัลกอริทึม
ด้วยอาร์เรย์ SA เราสามารถค้นหาอาร์เรย์อันดับ นี่ไม่ใช่เรื่องยากดังนั้นเราจะไม่อธิบาย รหัสทั้งหมดสำหรับการค้นหา SA มีการแนบด้านล่าง
โมฆะคงที่สาธารณะหลัก (สตริง [] args) {string str = "aabaaaab"; MySuffixArrayTest ArrayTest = New MySuffixArrayTest (str.toString ()); arraytest.initsa (); // ค้นหา sa array} โมฆะสาธารณะ initsa () {road = new int [n]; SA = ใหม่ int [n]; ws = new int [255]; y = ใหม่ int [n]; x = ใหม่ int [n]; // วนซ้ำสตริงต้นฉบับเพื่อแปลงค่า int เป็นอาร์เรย์อันดับสำหรับ (int i = 0; i <n; i ++) {road [i] = (int) คำต่อท้าย [i]; } // การนับจำนวนครั้งแรกสำหรับ (int i = 0; i <n; i ++) {ws [อันดับ [i]] ++; x [i] = อันดับ [i]; } สำหรับ (int i = 1; i <ws.length; i ++) {ws [i]+= ws [i - 1]; } สำหรับ (int i = n-1; i> = 0; i--) {sa [-ws [อันดับ [i]]] = i; } // วนการเรียงลำดับแบบรวมสำหรับ (int j = 1, p = 0; j <= n; j = j << 1) {// ถ้าคุณต้องการเติมให้เพิ่มอาร์เรย์ที่เรียงลำดับแรก yp = 0; สำหรับ (int i = n - j; i <n; i ++) {y [p ++] = i; } // ช่วงคำหลักที่สองตามคำหลักแรก sa สำหรับ (int i = 0; i <n; i ++) {ถ้า (sa [i]> = j) {y [p ++] = sa [i] - j; }} // การเรียงลำดับคำหลักสองคำสำหรับ (int i = 0; i <ws.length; i ++) {ws [i] = 0; } สำหรับ (int i: x) {ws [i] ++; } สำหรับ (int i = 1; i <ws.length; i ++) {ws [i]+= ws [i - 1]; } สำหรับ (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 = 1; x [sa [0]] = 1; สำหรับ (int i = 1; i <n; i ++) {ถ้า (xb [sa [i]]! = xb [sa [i - 1]]) {x [sa [i]] = ++ จำนวน; } อื่นถ้า (sa [i] + j> = n && sa [i - 1] + j> = n) {x [sa [i]] = number; } อื่นถ้า (sa [i] + j <n && sa [i - 1] + j> = n) {x [sa [i]] = ++ จำนวน; } อื่นถ้า (xb [sa [i] + j]! = xb [sa [i - 1] + j]) {x [sa [i]] = ++ จำนวน; } else {x [sa [i]] = number; } if (number> = n) break; -สรุป
ด้านบนเป็นรหัสตัวอย่างสำหรับอาร์เรย์ SAC ของอาร์เรย์คำต่อท้าย Java ที่แนะนำให้คุณรู้จัก ฉันหวังว่ามันจะเป็นประโยชน์กับคุณ หากคุณมีคำถามใด ๆ โปรดฝากข้อความถึงฉันและบรรณาธิการจะตอบกลับคุณทันเวลา ขอบคุณมากสำหรับการสนับสนุนเว็บไซต์ Wulin.com!