การจัดการสตริงและการค้นหารูปแบบในนั้นเป็นงานพื้นฐานในวิทยาศาสตร์ข้อมูลและเป็นงานทั่วไปสำหรับโปรแกรมเมอร์ทุกคน
อัลกอริทึมสตริงที่มีประสิทธิภาพมีบทบาทสำคัญในกระบวนการวิทยาศาสตร์ข้อมูลมากมาย บ่อยครั้งที่เป็นสิ่งที่ทำให้กระบวนการดังกล่าวมีความเป็นไปได้เพียงพอสำหรับการใช้งานจริง
ในบทความนี้คุณจะได้เรียนรู้เกี่ยวกับอัลกอริทึมที่ทรงพลังที่สุดสำหรับการค้นหารูปแบบในข้อความจำนวนมาก: อัลกอริทึม Aho-Corasick อัลกอริทึมนี้ใช้ไฟล์ โครงสร้างข้อมูล trie (ออกเสียงว่า“ ลอง”) เพื่อติดตามรูปแบบการค้นหาและใช้วิธีง่ายๆในการค้นหาชุดรูปแบบที่กำหนดในข้อความใด ๆ
บทความก่อนหน้านี้ใน ApeeScape Engineering Blog ได้แสดงอัลกอริทึมการค้นหาสตริงสำหรับปัญหาเดียวกัน แนวทางในบทความนี้นำเสนอความซับซ้อนในการคำนวณที่ดีขึ้น
อัลกอริทึม Knuth-Morris-Pratt (KMP)
เพื่อให้เข้าใจว่าเราสามารถค้นหารูปแบบต่างๆในข้อความอย่างมีประสิทธิภาพได้อย่างไรอันดับแรกเราต้องจัดการกับปัญหาที่ง่ายกว่า: มองหารูปแบบเดียวในข้อความที่กำหนด
สมมติว่าเรามีข้อความขนาดใหญ่ที่มีความยาว น และรูปแบบ (ที่เราต้องการค้นหาในข้อความ) ของความยาว ม . ไม่ว่าเราต้องการค้นหารูปแบบนี้ที่เกิดขึ้นเพียงครั้งเดียวหรือทั้งหมดที่เกิดขึ้นเราสามารถบรรลุความซับซ้อนในการคำนวณของ O (N + M) โดยใช้อัลกอริทึม KMP
ฟังก์ชันคำนำหน้า
อัลกอริทึม KMP ทำงานโดยการคำนวณฟังก์ชันคำนำหน้าของรูปแบบที่เรากำลังค้นหา ฟังก์ชันคำนำหน้าจะคำนวณตำแหน่งทางเลือกล่วงหน้าสำหรับทุกคำนำหน้าของรูปแบบ
มากำหนดรูปแบบการค้นหาของเราเป็นสตริงโดยมีข้อความว่า S สำหรับแต่ละสตริงย่อย S[0..i] โดยที่ i >= 1 เราจะพบคำนำหน้าสูงสุดของสตริงนี้ซึ่งเป็นส่วนต่อท้ายของสตริงนี้ด้วย เราจะติดป้ายกำกับความยาวของคำนำหน้านี้ P[i]
สำหรับรูปแบบ 'abracadabra' ฟังก์ชันคำนำหน้าจะสร้างตำแหน่งทางเลือกต่อไปนี้:
ดัชนี (i) | 0 | หนึ่ง | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| ตัวละคร | ถึง | ข | ร | ถึง | ค | ถึง | ง | ถึง | ข | ร | ถึง |
ความยาวของคำนำหน้า (P[i]) | 0 | 0 | 0 | หนึ่ง | 0 | หนึ่ง | 0 | หนึ่ง | 2 | 3 | 4 |
ฟังก์ชันคำนำหน้าระบุลักษณะที่น่าสนใจของรูปแบบ
ลองนำคำนำหน้าเฉพาะของรูปแบบมาเป็นตัวอย่าง:“ abracadab” ค่าฟังก์ชันคำนำหน้าสำหรับคำนำหน้านี้คือสอง สิ่งนี้บ่งชี้ว่าสำหรับคำนำหน้า 'abracadab' นี้มีคำต่อท้ายของความยาว 2 ที่ตรงกับคำนำหน้าของความยาว 2 ทุกประการ (เช่นรูปแบบขึ้นต้นด้วย 'ab' และคำนำหน้าลงท้ายด้วย 'ab') นอกจากนี้ยังเป็น การจับคู่ที่ยาวที่สุดสำหรับคำนำหน้านี้
การนำไปใช้
นี่คือฟังก์ชัน C # ที่สามารถใช้คำนวณฟังก์ชันคำนำหน้าสำหรับสตริงใดก็ได้:
public int[] CalcPrefixFunction(String s) { int[] result = new int[s.Length]; // array with prefix function values result[0] = 0; // the prefix function is always zero for the first symbol (its degenerate case) int k = 0; // current prefix function value for (int i = 1; i 0 && s[i] != s[k]) k = result[k - 1]; if (s[k] == s[i]) k++; // we've found the longest prefix - case 1 result[i] = k; // store this result in the array } return result; } การเรียกใช้ฟังก์ชันนี้ในรูปแบบที่ยาวขึ้นเล็กน้อย“ abcdabcabcdabcdab” จะทำให้เกิดสิ่งนี้:
ดัชนี (i) | 0 | หนึ่ง | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | สิบเอ็ด | 12 | 13 | 14 | สิบห้า | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ตัวละคร | ถึง | ข | ค | ง | ถึง | ข | ค | ถึง | ข | ค | ง | ถึง | ข | ค | ง | ถึง | ข |
ฟังก์ชันคำนำหน้า (P[i]) | 0 | 0 | 0 | 0 | หนึ่ง | 2 | 3 | หนึ่ง | 2 | 3 | 4 | 5 | 6 | 7 | 4 | 5 | 6 |
ความซับซ้อนในการคำนวณ
แม้ว่าจะมีสองลูปซ้อนกัน แต่ความซับซ้อนของฟังก์ชันคำนำหน้าก็เป็นเพียง O (ม) , ที่ไหน ม คือความยาวของรูปแบบ ส .
สิ่งนี้สามารถอธิบายได้อย่างง่ายดายโดยสังเกตว่าลูปทำงานอย่างไร
แอพที่ดีที่สุดสำหรับ android nougat
การวนซ้ำรอบนอกทั้งหมดผ่าน i สามารถแบ่งออกเป็นสามกรณี:
-
เพิ่มขึ้น
kโดยหนึ่ง ลูปเสร็จสิ้นการวนซ้ำหนึ่งครั้ง -
ไม่เปลี่ยนค่าศูนย์ของ
kลูปเสร็จสิ้นการวนซ้ำหนึ่งครั้ง -
ไม่เปลี่ยนแปลงหรือลดค่าบวกของ
k
สองกรณีแรกสามารถทำงานได้มากที่สุด ม ครั้ง.
สำหรับกรณีที่สามให้กำหนด P(s, i) = k1 และ P(s, i + 1) = k2, k2 <= k1. แต่ละกรณีเหล่านี้ควรนำหน้าด้วย k1 - k2 เกิดขึ้นในกรณีแรก จำนวนการลดลงไม่เกิน k1 - k2 + 1 และโดยรวมแล้วเรามีไม่เกิน 2 * ม การทำซ้ำ
คำอธิบายของตัวอย่างที่สอง
ลองดูรูปแบบตัวอย่างที่สอง“ abcdabcabcdabcdab” นี่คือวิธีที่ฟังก์ชันคำนำหน้าประมวลผลทีละขั้นตอน:
-
สำหรับสตริงย่อยว่างและสตริงย่อย“ a” ของความยาวหนึ่งค่าของฟังก์ชันคำนำหน้าจะถูกกำหนดเป็นศูนย์ (
k = 0) -
ดูที่สตริงย่อย“ ab” ค่าปัจจุบันของ
kเป็นศูนย์และอักขระ“ b” ไม่เท่ากับอักขระ“ a.” ที่นี่เรามีกรณีที่สองจากส่วนก่อนหน้า ค่าของkอยู่ที่ศูนย์และค่าของฟังก์ชันคำนำหน้าสำหรับสตริงย่อย“ ab” ก็เป็นศูนย์เช่นกัน -
เป็นกรณีเดียวกันสำหรับสตริงย่อย“ abc” และ“ abcd” ไม่มีคำนำหน้าที่เป็นส่วนต่อท้ายของสตริงย่อยเหล่านี้ด้วย ค่าสำหรับพวกเขายังคงเป็นศูนย์
-
ตอนนี้เรามาดูกรณีที่น่าสนใจคือสตริงย่อย“ abcda” ค่าปัจจุบันของ
kยังคงเป็นศูนย์ แต่อักขระสุดท้ายของสตริงย่อยตรงกับอักขระตัวแรก สิ่งนี้ทำให้เกิดเงื่อนไขของs[k] == s[i]โดยที่k == 0และi == 4. อาร์เรย์ไม่มีดัชนีและkคือดัชนีของอักขระถัดไปสำหรับคำนำหน้าความยาวสูงสุด ซึ่งหมายความว่าเราพบคำนำหน้าความยาวสูงสุดสำหรับสตริงย่อยของเราซึ่งเป็นส่วนต่อท้ายด้วย เรามีกรณีแรกซึ่งค่าใหม่ของkเป็นค่าหนึ่งดังนั้นค่าของฟังก์ชันคำนำหน้า P ('abcda') เป็นหนึ่งเดียว -
กรณีเดียวกันนี้ก็เกิดขึ้นกับสตริงย่อยสองรายการถัดไป P (“ abcdab”) = 2 และ P (“ abcdabc”) = 3 . ที่นี่เรากำลังค้นหารูปแบบของเราในข้อความโดยเปรียบเทียบอักขระสตริงตามอักขระ สมมติว่าอักขระเจ็ดตัวแรกของรูปแบบตรงกับอักขระที่ประมวลผลต่อเนื่องกันเจ็ดอักขระ แต่อักขระตัวที่แปดนั้นไม่ตรงกัน จะเกิดอะไรขึ้นต่อไป? ในกรณีของการจับคู่สตริงที่ไร้เดียงสาเราควรคืนอักขระเจ็ดตัวกลับมาและเริ่มกระบวนการเปรียบเทียบอีกครั้งจากอักขระตัวแรกของรูปแบบของเรา ด้วยค่าฟังก์ชันคำนำหน้า (ที่นี่ P (“ abcdabc”) = 3 ) เรารู้ว่าคำต่อท้ายสามอักขระของเราตรงกับอักขระสามตัวของข้อความแล้ว และถ้าอักขระถัดไปในข้อความคือ“ d” ความยาวของสตริงย่อยที่ตรงกันของรูปแบบและสตริงย่อยในข้อความจะเพิ่มขึ้นเป็นสี่ (“ abcd”) มิฉะนั้น, P (“ abc”) = 0 และเราจะเริ่มกระบวนการเปรียบเทียบจากอักขระตัวแรกของรูปแบบ แต่สิ่งสำคัญคือเราจะไม่ส่งคืนในระหว่างการประมวลผลข้อความ
-
สตริงย่อยถัดไปคือ“ abcdabca” ในสตริงย่อยก่อนหน้าฟังก์ชันคำนำหน้าเท่ากับสาม ซึ่งหมายความว่า
k = 3มีค่ามากกว่าศูนย์และในเวลาเดียวกันเรามีความไม่ตรงกันระหว่างอักขระถัดไปในคำนำหน้า (s[k] = s[3] = 'd') และอักขระถัดไปในส่วนต่อท้าย (s[i] = s[7] = 'a') ซึ่งหมายความว่าเราเรียกใช้เงื่อนไขของs[k] != s[i]และคำนำหน้า“ abcd” ไม่สามารถเป็นส่วนต่อท้ายของสตริงของเราได้ เราควรลดค่าของkและใช้คำนำหน้าก่อนหน้าเพื่อเปรียบเทียบหากเป็นไปได้ ดังที่เราได้อธิบายไว้ข้างต้นอาร์เรย์จะไม่มีดัชนีและkคือดัชนีของอักขระถัดไปที่เราตรวจสอบจากคำนำหน้า ดัชนีสุดท้ายของคำนำหน้าที่ตรงกันในปัจจุบันคือk - 1เรารับค่าของฟังก์ชันคำนำหน้าสำหรับคำนำหน้าที่ตรงกันในปัจจุบันk = result[k - 1]ในกรณีของเรา (กรณีที่สาม) ความยาวของคำนำหน้าสูงสุดจะลดลงเป็นศูนย์จากนั้นในบรรทัดถัดไปจะเพิ่มขึ้นเป็นหนึ่งเนื่องจาก 'a' เป็นคำนำหน้าสูงสุดที่เป็นส่วนต่อท้ายของสตริงย่อยของเราด้วย -
(ที่นี่เราดำเนินการคำนวณต่อไปจนกว่าจะได้กรณีที่น่าสนใจกว่านี้)
-
เราเริ่มประมวลผลสตริงย่อยต่อไปนี้:“ abcdabcabcdabcd” ค่าปัจจุบันของ
kเป็นเจ็ด เช่นเดียวกับ“ abcdabca” ข้างต้นเราไม่ตรงกัน: เนื่องจากอักขระ“ a” (อักขระที่เจ็ด) ไม่เท่ากับอักขระ“ d” สตริงย่อย“ abcdabca” จึงไม่สามารถเป็นส่วนต่อท้ายของสตริงของเราได้ ตอนนี้เราได้ค่าที่คำนวณไว้แล้วของฟังก์ชันคำนำหน้าสำหรับ“ abcdabc” (สาม) และตอนนี้เรามีค่าที่ตรงกัน: คำนำหน้า“ abcd” เป็นส่วนต่อท้ายของสตริงของเราด้วย คำนำหน้าสูงสุดและค่าของฟังก์ชันคำนำหน้าสำหรับสตริงย่อยของเราคือสี่เพราะนั่นคือค่าปัจจุบันของkกลายเป็น -
เราดำเนินการต่อไปจนกว่าจะสิ้นสุดรูปแบบ
กล่าวโดยย่อ: ทั้งสองรอบใช้เวลาไม่เกิน 3 M ซ้ำซึ่งพิสูจน์ความซับซ้อนเป็น O (M) การใช้หน่วยความจำยังเป็น O (M)
การใช้อัลกอริทึม KMP
public int KMP(String text, String s) { int[] p = CalcPrefixFunction(s); // Calculate prefix function for a pattern string // The idea is the same as in the prefix function described above, but now // we're comparing prefixes of text and pattern. // The value of maximum-length prefix of the pattern string that was found // in the text: int maxPrefixLength = 0; for (int i = 0; i 0 && text[i] != s[maxPrefixLength]) maxPrefixLength = p[maxPrefixLength - 1]; // If a match happened, increase the length of the maximum-length // prefix. if (s[maxPrefixLength] == text[i]) maxPrefixLength++; // If the prefix length is the same length as the pattern string, it // means that we have found a matching substring in the text. if (maxPrefixLength == s.Length) { // We can return this value or perform this operation. int idx = i - s.Length + 1; // Get the previous maximum-length prefix and continue search. maxPrefixLength = p[maxPrefixLength - 1]; } } return -1; } อัลกอริทึมข้างต้นจะวนซ้ำผ่านข้อความทีละอักขระและพยายามเพิ่มคำนำหน้าสูงสุดสำหรับทั้งรูปแบบของเราและลำดับของอักขระถวายตัวบางส่วนในข้อความ ในกรณีที่ล้มเหลวเราจะไม่คืนตำแหน่งของเราไปก่อนหน้านี้ในข้อความ เราทราบคำนำหน้าสูงสุดของสตริงย่อยที่พบของรูปแบบ คำนำหน้านี้เป็นส่วนต่อท้ายของสตริงย่อยที่พบนี้และเราสามารถดำเนินการค้นหาต่อไปได้
ความซับซ้อนของฟังก์ชันนี้เหมือนกับฟังก์ชันคำนำหน้าซึ่งทำให้ความซับซ้อนในการคำนวณโดยรวม O (N + M) ด้วย O (ม) หน่วยความจำ.
เรื่องไม่สำคัญ: วิธีการ
String.IndexOf()และString.Contains()ในกรอบงาน. NET มีอัลกอริทึมที่มีความซับซ้อนเหมือนกันภายใต้ประทุน
อัลกอริทึม Aho-Corasick
ตอนนี้เราต้องการทำแบบเดียวกันสำหรับหลายรูปแบบ
node.js javascript ฝั่งเซิร์ฟเวอร์คืออะไร
สมมติว่ามี ม รูปแบบของความยาว L1 , L2 , ... , ล . เราต้องหารูปแบบที่ตรงกันทั้งหมดจากพจนานุกรมในรูปแบบข้อความที่มีความยาว น .
วิธีแก้ปัญหาที่ไม่สำคัญคือการใช้อัลกอริทึมจากส่วนแรกและเรียกใช้ ม ครั้ง. เรามีความซับซ้อนของ O (N + L1 + N + L2 + … + N + Lm) เช่น O (M * N + L) .
การทดสอบใด ๆ ที่ร้ายแรงเพียงพอจะฆ่าอัลกอริทึมนี้
การใช้พจนานุกรมที่มีคำศัพท์ภาษาอังกฤษที่ใช้บ่อยที่สุด 1,000 คำเป็นรูปแบบและใช้เพื่อค้นหา 'สงครามและสันติภาพ' ของตอลสตอยเวอร์ชันภาษาอังกฤษอาจใช้เวลาสักพัก หนังสือมีความยาวมากกว่าสามล้านอักขระ
หากเราใช้คำศัพท์ภาษาอังกฤษที่ใช้บ่อย 10,000 คำอัลกอริทึมจะทำงานช้าลงประมาณ 10 เท่า เห็นได้ชัดว่าอินพุตที่มากกว่านี้เวลาดำเนินการก็จะเพิ่มขึ้นเช่นกัน
นี่คือจุดที่อัลกอริทึม Aho-Corasick ใช้เวทมนตร์
ความซับซ้อนของอัลกอริทึม Aho-Corasick คือ O (N + L + Z) , ที่ไหน ด้วย คือจำนวนการแข่งขัน อัลกอริทึมนี้ถูกคิดค้นโดย Alfred V. และ Margaret J. Corasick ในปีพ. ศ. 2518
การนำไปใช้
ที่นี่เราต้องการ Trie และเราได้เพิ่มแนวคิดที่คล้ายกันกับฟังก์ชันคำนำหน้าที่อธิบายไว้ข้างต้นให้กับอัลกอริทึม เราจะคำนวณค่าฟังก์ชันคำนำหน้าสำหรับพจนานุกรมทั้งหมด
จุดยอดแต่ละจุดในสามเหลี่ยมจะจัดเก็บข้อมูลต่อไปนี้:
public class Vertex { public Vertex() { Children = new Hashtable(); Leaf = false; Parent = -1; SuffixLink = -1; WordID = -1; EndWordLink= -1; } // Links to the child vertexes in the trie: // Key: A single character // Value: The ID of vertex public Hashtable Children; // Flag that some word from the dictionary ends in this vertex public bool Leaf; // Link to the parent vertex public int Parent; // Char which moves us from the parent vertex to the current vertex public char ParentChar; // Suffix link from current vertex (the equivalent of P[i] from the KMP algorithm) public int SuffixLink; // Link to the leaf vertex of the maximum-length word we can make from the current prefix public int EndWordLink; // If the vertex is the leaf, we store the ID of the word public int WordID; } มีหลายวิธีในการนำลิงค์ลูกไปใช้ อัลกอริทึมจะมีความซับซ้อนของ O (N + L + Z) ในกรณีของอาร์เรย์ แต่จะมีข้อกำหนดหน่วยความจำเพิ่มเติมของ O (L * q) , โดยที่ q คือความยาวของตัวอักษรเนื่องจากเป็นจำนวนชายด์สูงสุดที่โหนดสามารถมีได้
ถ้าเราใช้โครงสร้างบางอย่างกับ O (บันทึก (q)) เข้าถึงองค์ประกอบของมันเรามีข้อกำหนดหน่วยความจำเพิ่มเติมของ O (L) แต่ความซับซ้อนของอัลกอริทึมทั้งหมดจะเป็นอย่างไร O ((N + L) * บันทึก (q) + Z) .
ในกรณีของตารางแฮชเรามี O (L) หน่วยความจำเพิ่มเติมและความซับซ้อนของอัลกอริทึมทั้งหมดจะเป็น O (N + L + Z) .
บทช่วยสอนนี้ใช้ตารางแฮชเนื่องจากจะใช้กับชุดอักขระต่างๆเช่นอักขระภาษาจีน
เรามีโครงสร้างสำหรับจุดยอดแล้ว ต่อไปเราจะกำหนดรายการจุดยอดและเริ่มต้นโหนดรูทของสาม
public class Aho { List Trie; List WordsLength; int size = 0; int root = 0; public Aho() { Trie = new List(); WordsLength = new List(); Init(); } private void Init() { Trie.Add(new Vertex()) size++; } } จากนั้นเราเพิ่มรูปแบบทั้งหมดลงในผ้าไตร สำหรับสิ่งนี้เราต้องการวิธีการเพิ่มคำในสาม:
public void AddString(String s, int wordID) { int curVertex = root; for (int i = 0; i ณ จุดนี้คำรูปแบบทั้งหมดอยู่ในโครงสร้างข้อมูล สิ่งนี้ต้องใช้หน่วยความจำเพิ่มเติมของ O (L) .
ต่อไปเราต้องคำนวณลิงก์คำต่อท้ายและลิงค์รายการพจนานุกรมทั้งหมด
เพื่อให้ชัดเจนและเข้าใจง่ายฉันจะสำรวจ Trie ของเราจากรากไปยังใบไม้และทำการคำนวณที่คล้ายกันเช่นที่เราทำสำหรับอัลกอริทึม KMP แต่ตรงกันข้ามกับอัลกอริทึม KMP ที่เราพบความยาวสูงสุด คำนำหน้าซึ่งเป็นส่วนต่อท้ายของสตริงย่อยเดียวกันตอนนี้เราจะพบคำต่อท้ายที่มีความยาวสูงสุดของสตริงย่อยปัจจุบันซึ่งเป็นคำนำหน้าของรูปแบบบางอย่างในสาม ค่าของฟังก์ชันนี้จะไม่ใช่ความยาวของส่วนต่อท้ายที่พบ จะเป็นลิงค์ไปยังอักขระสุดท้ายของส่วนต่อท้ายสูงสุดของสตริงย่อยปัจจุบัน นี่คือสิ่งที่ฉันหมายถึงโดยลิงค์ต่อท้ายของจุดยอด
ฉันจะประมวลผลจุดยอดตามระดับ สำหรับสิ่งนั้นฉันจะใช้ไฟล์ การค้นหาก่อนกว้าง (BFS) อัลกอริทึม:
และด้านล่างนี้คือการใช้งานการข้ามผ่านนี้:
public void PrepareAho() { Queue vertexQueue = new Queue(); vertexQueue.Enqueue(root); while (vertexQueue.Count > 0) { int curVertex = vertexQueue.Dequeue(); CalcSuffLink(curVertex); foreach (char key in Trie[curVertex].Children.Keys) { vertexQueue.Enqueue((int)Trie[curVertex].Children[key]); } } } และด้านล่างคือ CalcSuffLink วิธีการคำนวณลิงก์คำต่อท้ายสำหรับแต่ละจุดยอด (เช่นค่าฟังก์ชันคำนำหน้าสำหรับแต่ละสตริงย่อยในสาม):
public void CalcSuffLink(int vertex) { // Processing root (empty string) if (vertex == root) { Trie[vertex].SuffixLink = root; Trie[vertex].EndWordLink = root; return; } // Processing children of the root (one character substrings) if (Trie[vertex].Parent == root) { Trie[vertex].SuffixLink = root; if (Trie[vertex].Leaf) Trie[vertex].EndWordLink = vertex; else Trie[vertex].EndWordLink = Trie[Trie[vertex].SuffixLink].EndWordLink; return; } // Cases above are degenerate cases as for prefix function calculation; the // value is always 0 and links to the root vertex. // To calculate the suffix link for the current vertex, we need the suffix // link for the parent of the vertex and the character that moved us to the // current vertex. int curBetterVertex = Trie[Trie[vertex].Parent].SuffixLink; char chVertex = Trie[vertex].ParentChar; // From this vertex and its substring we will start to look for the maximum // prefix for the current vertex and its substring. while (true) { // If there is an edge with the needed char, we update our suffix link // and leave the cycle if (Trie[curBetterVertex].Children.ContainsKey(chVertex)) { Trie[vertex].SuffixLink = (int)Trie[curBetterVertex].Children[chVertex]; break; } // Otherwise, we are jumping by suffix links until we reach the root // (equivalent of k == 0 in prefix function calculation) or we find a // better prefix for the current substring. if (curBetterVertex == root) { Trie[vertex].SuffixLink = root; break; } curBetterVertex = Trie[curBetterVertex].SuffixLink; // Go back by sufflink } // When we complete the calculation of the suffix link for the current // vertex, we should update the link to the end of the maximum length word // that can be produced from the current substring. if (Trie[vertex].Leaf) Trie[vertex].EndWordLink = vertex; else Trie[vertex].EndWordLink = Trie[Trie[vertex].SuffixLink].EndWordLink; } ความซับซ้อนของวิธีนี้คือ O (L) ; ความซับซ้อนอาจขึ้นอยู่กับการใช้งานคอลเล็กชันย่อย O (L * บันทึก (q)) .
การพิสูจน์ความซับซ้อนคล้ายกับการพิสูจน์ฟังก์ชันคำนำหน้าความซับซ้อนในอัลกอริทึม KMP
ลองดูภาพต่อไปนี้ นี่คือการแสดงภาพสามมิติสำหรับพจนานุกรม { abba, cab, baba, caab, ac, abac, bac } ด้วยข้อมูลการคำนวณทั้งหมด:
ขอบ Trie เป็นสีน้ำเงินเข้มลิงก์ส่วนต่อท้ายเป็นสีฟ้าอ่อนและลิงก์คำต่อท้ายพจนานุกรมเป็นสีเขียว โหนดที่ตรงกับรายการพจนานุกรมจะเน้นด้วยสีน้ำเงิน
และตอนนี้เราต้องการอีกเพียงวิธีเดียวเท่านั้นคือการประมวลผลกลุ่มข้อความที่เราตั้งใจจะค้นหา:
public int ProcessString(String text) { // Current state value int currentState = root; // Targeted result value int result = 0; for (int j = 0; j และตอนนี้พร้อมใช้งานแล้ว:
ในการป้อนข้อมูลเรามีรายการรูปแบบ:
c corp vs.s corp vs llc
List patterns; และข้อความค้นหา:
string text; และนี่คือวิธีการรวมเข้าด้วยกัน:
// Init the trie structure. As an optional parameter we can put the approximate // size of the trie to allocate memory just once for all nodes. Aho ahoAlg = new Aho(); for (int i = 0; i เท่านี้ก็เรียบร้อย! ตอนนี้คุณรู้แล้วว่าอัลกอริทึมที่เรียบง่าย แต่ทรงพลังนี้ทำงานอย่างไร!
Aho-Corasick มีความยืดหยุ่นจริงๆ รูปแบบการค้นหาไม่จำเป็นต้องเป็นเพียงคำพูดเท่านั้น แต่เราสามารถใช้ทั้งประโยคหรือกลุ่มอักขระแบบสุ่ม
ประสิทธิภาพ
อัลกอริทึมได้รับการทดสอบบน Intel Core i7-4702MQ
สำหรับการทดสอบฉันใช้พจนานุกรมสองคำ: คำศัพท์ภาษาอังกฤษที่ใช้บ่อยที่สุด 1,000 คำและคำศัพท์ภาษาอังกฤษที่ใช้บ่อยที่สุด 10,000 คำ
ในการเพิ่มคำเหล่านี้ทั้งหมดลงในพจนานุกรมและเตรียมโครงสร้างข้อมูลเพื่อทำงานกับพจนานุกรมแต่ละชุดอัลกอริทึมต้องใช้ 55ms และ 135ms ตามลำดับ
อัลกอริทึมประมวลผลหนังสือจริงที่มีความยาว 3-4 ล้านอักขระภายใน 1.0-1.3 วินาทีในขณะที่ใช้เวลา 9.6 วินาทีสำหรับหนังสือที่มีอักขระประมาณ 30 ล้านตัว
การขนานอัลกอริทึม Aho-Corasick
การใช้งานคู่ขนานกับอัลกอริทึม Aho-Corasick นั้นไม่มีปัญหาเลย:
ข้อความขนาดใหญ่สามารถแบ่งออกเป็นหลายส่วนและสามารถใช้หลายเธรดเพื่อประมวลผลแต่ละกลุ่มได้ แต่ละเธรดสามารถเข้าถึง trie ที่สร้างขึ้นตามพจนานุกรม
สิ่งที่เกี่ยวกับคำที่แบ่งออกเป็นรอยต่อระหว่างชิ้น? ปัญหานี้สามารถแก้ไขได้ง่ายๆ
ปล่อย น เป็นความยาวของข้อความขนาดใหญ่ของเรา ส มีขนาดเท่าก้อนและ ล เป็นความยาวของรูปแบบที่ใหญ่ที่สุดในพจนานุกรม
ตอนนี้เราสามารถใช้เคล็ดลับง่ายๆ เราแบ่งส่วนที่มีการทับซ้อนกันในตอนท้ายเช่นการ [S * (i - 1), S * i + L - 1] โดยที่ i เป็นดัชนีของชิ้นส่วน เมื่อเราจับคู่รูปแบบเราสามารถรับดัชนีเริ่มต้นของการจับคู่ปัจจุบันได้อย่างง่ายดายและตรวจสอบว่าดัชนีนี้อยู่ในช่วงกลุ่มโดยไม่มีการทับซ้อนกัน [S * (i - 1), S * i - 1]
อัลกอริทึมการค้นหาสตริงที่หลากหลาย
อัลกอริทึม Aho-Corasick เป็นอัลกอริธึมการจับคู่สตริงที่มีประสิทธิภาพซึ่งให้ความซับซ้อนที่ดีที่สุดสำหรับอินพุตใด ๆ และไม่ต้องใช้หน่วยความจำเพิ่มเติมมากนัก
อัลกอริทึมมักใช้ในระบบต่างๆเช่นตัวตรวจสอบการสะกดตัวกรองสแปมเครื่องมือค้นหาข้อมูลชีวสารสนเทศศาสตร์ / การค้นหาลำดับดีเอ็นเอเป็นต้นในความเป็นจริงเครื่องมือยอดนิยมบางอย่างที่คุณอาจใช้ทุกวันกำลังใช้อัลกอริทึมนี้อยู่เบื้องหลัง
ฟังก์ชันคำนำหน้าจากอัลกอริทึม KMP ในตัวเองเป็นเครื่องมือที่น่าสนใจที่นำความซับซ้อนของการจับคู่รูปแบบเดียวมาใช้กับเวลาเชิงเส้น อัลกอริทึม Aho-Corasick เป็นไปตามแนวทางที่คล้ายกันและใช้โครงสร้างข้อมูลสามแบบเพื่อทำแบบเดียวกันสำหรับหลายรูปแบบ
ฉันหวังว่าคุณจะพบว่าบทช่วยสอนเกี่ยวกับอัลกอริทึม Aho-Corasick นี้มีประโยชน์
