พิชิตการค้นหาสตริงด้วยอัลกอริทึม Aho-Corasick

การจัดการสตริงและการค้นหารูปแบบในสตริงนั้นเป็นงานพื้นฐานในวิทยาศาสตร์ข้อมูล และเป็นงานทั่วไปสำหรับโปรแกรมเมอร์ทุกคน

อัลกอริธึมสตริงที่มีประสิทธิภาพมีบทบาทสำคัญในกระบวนการวิทยาศาสตร์ข้อมูลจำนวนมาก บ่อยครั้งสิ่งเหล่านี้เป็นสิ่งที่ทำให้กระบวนการดังกล่าวเป็นไปได้เพียงพอสำหรับการใช้งานจริง

ในบทความนี้ คุณจะได้เรียนรู้เกี่ยวกับอัลกอริธึมที่ทรงพลังที่สุดตัวหนึ่งสำหรับการค้นหารูปแบบในข้อความจำนวนมาก: อัลกอริธึม Aho-Corasick อัลกอริธึมนี้ใช้โครงสร้างข้อมูลแบบทดลอง (อ่านว่า "พยายาม") เพื่อติดตามรูปแบบการค้นหา และใช้วิธีการง่ายๆ ในการค้นหารูปแบบที่เกิดขึ้นทั้งหมดในกลุ่มข้อความใดๆ อย่างมีประสิทธิภาพ

บทความก่อนหน้านี้ใน Toptal Engineering Blog ได้สาธิตอัลกอริธึมการค้นหาสตริงสำหรับปัญหาเดียวกัน แนวทางในบทความนี้นำเสนอความซับซ้อนในการคำนวณที่ดีขึ้น

อัลกอริทึม Knuth-Morris-Pratt (KMP)

เพื่อให้เข้าใจวิธีที่เราสามารถค้นหารูปแบบต่างๆ ในข้อความได้อย่างมีประสิทธิภาพ อันดับแรก เราต้องจัดการกับปัญหาที่ง่ายกว่านี้ก่อน: มองหารูปแบบเดียวในข้อความที่กำหนด

สมมติว่าเรามีข้อความยาว N และรูปแบบ (ที่เราต้องการค้นหาในข้อความ) ที่มีความยาว M ไม่ว่าเราจะต้องการมองหารูปแบบนี้เพียงรูปแบบเดียวหรือทั้งหมด เราก็สามารถบรรลุความซับซ้อนในการคำนวณของ O(N + M) โดยใช้อัลกอริทึม KMP

ฟังก์ชันคำนำหน้า

อัลกอริทึม KMP ทำงานโดยการคำนวณฟังก์ชันนำหน้าของรูปแบบที่เรากำลังค้นหา ฟังก์ชันคำนำหน้าจะคำนวณตำแหน่งสำรองล่วงหน้าสำหรับคำนำหน้าทุกรูปแบบ

มากำหนดรูปแบบการค้นหาของเราเป็นสตริงที่มีป้ายกำกับว่า S สำหรับแต่ละสตริงย่อย S[0..i] โดยที่ i >= 1 เราจะพบคำนำหน้าสูงสุดของสตริงนี้ซึ่งเป็นส่วนต่อท้ายของสตริงนี้ด้วย เราจะติดป้ายกำกับความยาวของคำนำหน้านี้ P[i]

สำหรับรูปแบบ "abracadabra" ฟังก์ชันนำหน้าจะสร้างตำแหน่งทางเลือกต่อไปนี้:

ฟังก์ชันคำนำหน้าระบุลักษณะที่น่าสนใจของรูปแบบ

ลองใช้คำนำหน้าเฉพาะของรูปแบบเป็นตัวอย่าง: “abracadab” ค่าฟังก์ชันส่วนนำหน้าสำหรับคำนำหน้านี้คือสอง สิ่งนี้บ่งชี้ว่าสำหรับคำนำหน้านี้ "abracadab" มีคำต่อท้ายของความยาวสองที่ตรงกับคำนำหน้าของความยาวสอง (เช่น รูปแบบเริ่มต้นด้วย "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 < s.Length; i++) { // We're jumping by prefix function values to try smaller prefixes // Jumping stops when we find a match, or reach zero // Case 2 if we stop at a zero-length prefix // Case 3 if we stop at a match while (k > 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" จะสร้างสิ่งนี้:

ความซับซ้อนในการคำนวณ

แม้ว่าจะมีสองลูปซ้อนกัน แต่ความซับซ้อนของฟังก์ชันคำนำหน้าก็แค่ O(M) โดยที่ M คือความยาวของรูปแบบ S

สิ่งนี้สามารถอธิบายได้ง่าย ๆ โดยการสังเกตการทำงานของลูป

การวนซ้ำรอบนอกทั้งหมดผ่าน i สามารถแบ่งออกเป็นสามกรณี:

1. เพิ่ม k ขึ้นหนึ่ง การวนซ้ำเสร็จสิ้นการวนซ้ำหนึ่งครั้ง

2. ไม่เปลี่ยนค่าศูนย์ของ k การวนซ้ำเสร็จสิ้นการวนซ้ำหนึ่งครั้ง

3. ไม่เปลี่ยนแปลงหรือลดค่าบวกของ k

สองกรณีแรกสามารถทำงานได้สูงสุด M ครั้ง

สำหรับกรณีที่สาม ให้นิยาม P(s, i) = k1 และ P(s, i + 1) = k2, k2 <= k1 แต่ละกรณีเหล่านี้ควรนำหน้าด้วยการเกิด k1 - k2 ของกรณีแรก จำนวนการลดลงไม่เกิน k1 - k2 + 1 . และโดยรวมแล้ว เรามีการวนซ้ำไม่เกิน 2 * M

คำอธิบายของตัวอย่างที่สอง

ลองดูตัวอย่างรูปแบบที่สอง “abcdabcabcdabcdab” นี่คือวิธีที่ฟังก์ชัน prefix ประมวลผล ทีละขั้นตอน:

1. สำหรับสตริงย่อยว่างและสตริงย่อย "a" ของความยาวหนึ่ง ค่าของฟังก์ชันคำนำหน้าจะถูกตั้งค่าเป็นศูนย์ ( k = 0 )

2. ดูสตริงย่อย "ab" ค่าปัจจุบันของ k เป็นศูนย์และอักขระ "b" ไม่เท่ากับอักขระ "a" ที่นี่เรามีกรณีที่สองจากส่วนก่อนหน้านี้ ค่าของ k อยู่ที่ศูนย์ และค่าของฟังก์ชันนำหน้าสำหรับสตริงย่อย “ab” ยังเป็นศูนย์อีกด้วย

3. เป็นกรณีเดียวกันสำหรับสตริงย่อย "abc" และ "abcd" ไม่มีคำนำหน้าที่เป็นคำต่อท้ายของสตริงย่อยเหล่านี้ด้วย ค่าสำหรับพวกเขาอยู่ที่ศูนย์

4. ทีนี้ มาดูกรณีที่น่าสนใจกันดีกว่า สตริงย่อย “abcda” ค่าปัจจุบันของ k ยังคงเป็นศูนย์ แต่อักขระตัวสุดท้ายของสตริงย่อยของเราตรงกับอักขระตัวแรก สิ่งนี้ทริกเกอร์เงื่อนไขของ s[k] == s[i] โดยที่ k == 0 และ i == 4 อาร์เรย์มีการทำดัชนีเป็นศูนย์ และ k คือดัชนีของอักขระถัดไปสำหรับคำนำหน้าความยาวสูงสุด ซึ่งหมายความว่าเราพบคำนำหน้าความยาวสูงสุดสำหรับสตริงย่อยของเราซึ่งเป็นส่วนต่อท้ายด้วย เรามีกรณีแรก โดยที่ค่าใหม่ของ k เป็นหนึ่ง ดังนั้นค่าของฟังก์ชันนำหน้า P("abcda") จึงเป็นหนึ่ง

5. กรณีเดียวกันนี้จะเกิดขึ้นสำหรับสตริงย่อยสองสตริงถัดไป P("abcdab") = 2 และ P("abcdabc") = 3 ที่นี่ เรากำลังค้นหารูปแบบของเราในข้อความ เปรียบเทียบสตริงอักขระทีละอักขระ สมมติว่าอักขระเจ็ดตัวแรกของรูปแบบตรงกับอักขระเจ็ดตัวที่ต่อเนื่องกันของข้อความที่ประมวลผล แต่อักขระที่แปดไม่ตรงกัน จะเกิดอะไรขึ้นต่อไป? ในกรณีของการจับคู่สตริงที่ไร้เดียงสา เราควรส่งคืนอักขระเจ็ดตัวกลับและเริ่มกระบวนการเปรียบเทียบอีกครั้งจากอักขระตัวแรกของรูปแบบของเรา ด้วยค่าฟังก์ชันคำนำหน้า (ที่นี่ P("abcdabc") = 3 ) เราทราบดีว่าส่วนต่อท้ายสามอักขระของเราตรงกับอักขระสามตัวของข้อความแล้ว และถ้าอักขระตัวถัดไปในข้อความคือ "d" ความยาวของสตริงย่อยที่ตรงกันของรูปแบบและสตริงย่อยในข้อความจะเพิ่มขึ้นเป็นสี่ ("abcd") มิฉะนั้น P("abc") = 0 และเราจะเริ่มกระบวนการเปรียบเทียบจากอักขระตัวแรกของรูปแบบ แต่สิ่งที่สำคัญคือเราจะไม่ส่งคืนระหว่างการประมวลผลข้อความ

6. สตริงย่อยถัดไปคือ “abcdabca” ในสตริงย่อยก่อนหน้า ฟังก์ชันคำนำหน้ามีค่าเท่ากับสาม ซึ่งหมายความว่า k = 3 มากกว่าศูนย์ และในขณะเดียวกัน เราก็มีความไม่ตรงกันระหว่างอักขระตัวถัดไปในคำนำหน้า ( s[k] = s[3] = "d" ) และอักขระตัวถัดไปในส่วนต่อท้าย ( s[i] = s[7] = "a" ) ซึ่งหมายความว่าเราทริกเกอร์เงื่อนไขของ s[k] != s[i] และคำนำหน้า “abcd” ไม่สามารถเป็นส่วนต่อท้ายของสตริงของเราได้ เราควรลดค่าของ k และใช้คำนำหน้าก่อนหน้าเพื่อเปรียบเทียบ ถ้าเป็นไปได้ ตามที่เราอธิบายไว้ข้างต้น อาร์เรย์นั้นไม่มีดัชนี และ k คือดัชนีของอักขระตัวถัดไปที่เราตรวจสอบจากคำนำหน้า ดัชนีสุดท้ายของคำนำหน้าที่ตรงกันในปัจจุบันคือ k - 1 เราใช้ค่าของฟังก์ชัน prefix สำหรับคำนำหน้าที่ตรงกันในปัจจุบัน k = result[k - 1] ในกรณีของเรา (กรณีที่สาม) ความยาวของคำนำหน้าสูงสุดจะลดลงเป็นศูนย์ จากนั้นในบรรทัดถัดไปจะเพิ่มขึ้นเป็นหนึ่ง เนื่องจาก "a" เป็นคำนำหน้าสูงสุดที่เป็นคำต่อท้ายของสตริงย่อยของเราด้วย

7. (ที่นี่เราดำเนินการคำนวณต่อไปจนกว่าจะพบกรณีที่น่าสนใจมากขึ้น)

8. เราเริ่มประมวลผลสตริงย่อยต่อไปนี้: “abcdabcabcdabcd” ค่าปัจจุบันของ k คือเจ็ด เช่นเดียวกับ “abcdabca” ด้านบน เราพบข้อความที่ไม่ตรงกัน เนื่องจากอักขระ “a” (อักขระตัวที่เจ็ด) ไม่เท่ากับอักขระ “d” สตริงย่อย “abcdabca” จึงไม่สามารถเป็นส่วนต่อท้ายของสตริงของเราได้ ตอนนี้เราได้รับค่าที่คำนวณแล้วของฟังก์ชันคำนำหน้าสำหรับ "abcdabc" (สาม) และตอนนี้เรามีการจับคู่: คำนำหน้า "abcd" เป็นส่วนต่อท้ายของสตริงของเรา คำนำหน้าสูงสุดและค่าของฟังก์ชันนำหน้าสำหรับสตริงย่อยของเราคือสี่ เพราะนั่นคือสิ่งที่ค่าปัจจุบันของ k กลายเป็น

9. เราดำเนินการตามขั้นตอนนี้ต่อไปจนกว่าจะสิ้นสุดรูปแบบ

กล่าวโดยย่อ: ทั้งสองรอบใช้เวลาไม่เกิน 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 < text.Length; i++) { // As in the prefix function, we're jumping by prefixes until k is // greater than 0 or we find a prefix that has matches in the text. while (maxPrefixLength > 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(M)

เรื่องไม่สำคัญ: วิธีการ String.IndexOf() และ String.Contains() ใน .NET framework มีอัลกอริทึมที่มีความซับซ้อนเหมือนกันภายใต้ประทุน

อัลกอริทึม Aho-Corasick

ตอนนี้เราต้องการทำเช่นเดียวกันสำหรับหลายรูปแบบ

สมมติว่ามีรูปแบบ M ที่มีความยาว L1 , L2 , …, Lm เราจำเป็นต้องค้นหารูปแบบที่ตรงกันทั้งหมดจากพจนานุกรมในข้อความที่มีความยาว N

วิธีแก้ปัญหาเล็กๆ น้อยๆ ก็คือการใช้อัลกอริทึมใดๆ จากส่วนแรกและเรียกใช้ M ครั้ง เรามีความซับซ้อนของ O(N + L1 + N + L2 + … + N + Lm) เช่น O(M * N + L)

การทดสอบที่จริงจังเพียงพอจะฆ่าอัลกอริทึมนี้

การใช้พจนานุกรมที่มีคำศัพท์ภาษาอังกฤษที่พบบ่อยที่สุด 1,000 คำเป็นรูปแบบและใช้เพื่อค้นหา "สงครามและสันติภาพ" เวอร์ชันภาษาอังกฤษของตอลสตอยอาจใช้เวลาสักครู่ หนังสือเล่มนี้มีความยาวมากกว่าสามล้านตัวอักษร

หากเราใช้คำศัพท์ภาษาอังกฤษที่พบบ่อยที่สุด 10,000 คำ อัลกอริทึมจะทำงานช้าลงประมาณ 10 เท่า เห็นได้ชัดว่าสำหรับอินพุตที่มากกว่านี้ เวลาดำเนินการก็จะเพิ่มขึ้นเช่นกัน

นี่คือจุดที่อัลกอริธึม Aho-Corasick ใช้เวทย์มนตร์

ความซับซ้อนของอัลกอริทึม Aho-Corasick คือ O(N + L + Z) โดยที่ Z คือจำนวนการจับคู่ อัลกอริทึมนี้คิดค้นโดย Alfred V. Aho และ Margaret J. Corasick ในปี 1975

การดำเนินการ

ในที่นี้ เราจำเป็นต้องมีการทดลอง และเราเพิ่มแนวคิดที่คล้ายคลึงกันให้กับอัลกอริทึมของเราในฟังก์ชันคำนำหน้าที่อธิบายไว้ข้างต้น เราจะคำนวณค่าฟังก์ชันคำนำหน้าสำหรับพจนานุกรมทั้งหมด

แต่ละจุดยอดในการทดสอบจะเก็บข้อมูลต่อไปนี้:

 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(log(q)) เข้าถึงองค์ประกอบ เรามีความต้องการหน่วยความจำเพิ่มเติมของ O(L) แต่ความซับซ้อนของอัลกอริธึมทั้งหมดจะเป็น O((N + L) * log(q) + ซี) .

ในกรณีของตารางแฮช เรามีหน่วยความจำเพิ่มเติม O(L) และความซับซ้อนของอัลกอริธึมทั้งหมดจะเป็น O(N + L + Z)

บทช่วยสอนนี้ใช้ตารางแฮชเพราะมันจะทำงานกับชุดอักขระต่างๆ เช่น อักษรจีน

เรามีโครงสร้างสำหรับจุดยอดแล้ว ต่อไป เราจะกำหนดรายการของจุดยอดและเริ่มต้นโหนดรากของ trie

 public class Aho { List<Vertex> Trie; List<int> WordsLength; int size = 0; int root = 0; public Aho() { Trie = new List<Vertex>(); WordsLength = new List<int>(); Init(); } private void Init() { Trie.Add(new Vertex()) size++; } }

จากนั้นเราก็เพิ่มลวดลายทั้งหมดลงในชุดทดลอง สำหรับสิ่งนี้ เราต้องการวิธีการเพิ่มคำในกลุ่ม tri:

 public void AddString(String s, int wordID) { int curVertex = root; for (int i = 0; i < s.Length; ++i) // Iterating over the string's characters { char c = s[i]; // Checking if a vertex with this edge exists in the trie: if (!Trie[curVertex].Children.ContainsKey(c)) { Trie.Add(new Vertex()); Trie[size].SuffixLink = -1; // If not - add vertex Trie[size].Parent = curVertex; Trie[size].ParentChar = c; Trie[curVertex].Children[c] = size; size++; } curVertex = (int)Trie[curVertex].Children[c]; // Move to the new vertex in the trie } // Mark the end of the word and store its ID Trie[curVertex].Leaf = true; Trie[curVertex].WordID = wordID; WordsLength.Add(s.Length); }

ณ จุดนี้ คำรูปแบบทั้งหมดอยู่ในโครงสร้างข้อมูล สิ่งนี้ต้องการหน่วยความจำเพิ่มเติมของ O(L)

ต่อไปเราต้องคำนวณลิงค์ต่อท้ายและลิงค์รายการพจนานุกรมทั้งหมด

เพื่อให้ชัดเจนและเข้าใจง่าย ฉันจะสำรวจการทดลองของเราจากรากไปยังใบไม้ และทำการคำนวณที่คล้ายกันเหมือนที่เราทำสำหรับอัลกอริทึม KMP แต่ตรงกันข้ามกับอัลกอริทึม KMP ที่เราพบความยาวสูงสุด คำนำหน้าที่เป็นคำต่อท้ายของสตริงย่อยเดียวกัน ตอนนี้เราจะพบส่วนต่อท้ายที่มีความยาวสูงสุดของสตริงย่อยปัจจุบันซึ่งเป็นคำนำหน้าของรูปแบบบางส่วนในทรี ค่าของฟังก์ชันนี้จะไม่ใช่ความยาวของคำต่อท้ายที่พบ มันจะเป็นลิงค์ไปยังอักขระตัวสุดท้ายของส่วนต่อท้ายสูงสุดของสตริงย่อยปัจจุบัน นี่คือสิ่งที่ผมหมายถึงโดยลิงก์ต่อท้ายของจุดยอด

ฉันจะประมวลผลจุดยอดตามระดับ สำหรับสิ่งนั้น ฉันจะใช้อัลกอริทึมการค้นหาแบบกว้างก่อน (BFS)

และด้านล่างคือการดำเนินการข้ามผ่านนี้:

 public void PrepareAho() { Queue<int> vertexQueue = new Queue<int>(); 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 สำหรับคำนวณลิงก์ต่อท้ายสำหรับจุดยอดแต่ละจุด (เช่น ค่าฟังก์ชันนำหน้าสำหรับสตริงย่อยแต่ละรายการใน trie):

 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 * log(q))

การพิสูจน์ความซับซ้อนนั้นคล้ายคลึงกับฟังก์ชันการพิสูจน์ความซับซ้อนในอัลกอริธึม KMP

ลองดูที่ภาพต่อไปนี้ นี่คือการแสดงภาพของ trie สำหรับพจนานุกรม { 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 < text.Length; j++) { // Calculating new state in the trie while (true) { // If we have the edge, then use it if (Trie[currentState].Children.ContainsKey(text[j])) { currentState = (int)Trie[currentState].Children[text[j]]; break; } // Otherwise, jump by suffix links and try to find the edge with // this char // If there aren't any possible edges we will eventually ascend to // the root, and at this point we stop checking. if (currentState == root) break; currentState = Trie[currentState].SuffixLink; } int checkState = currentState; // Trying to find all possible words from this prefix while (true) { // Checking all words that we can get from the current prefix checkState = Trie[checkState].EndWordLink; // If we are in the root vertex, there are no more matches if (checkState == root) break; // If the algorithm arrived at this row, it means we have found a // pattern match. And we can make additional calculations like find // the index of the found match in the text. Or check that the found // pattern is a separate word and not just, eg, a substring. result++; int indexOfMatch = j + 1 - WordsLength[Trie[checkState].WordID]; // Trying to find all matched patterns of smaller length checkState = Trie[checkState].SuffixLink; } } return result; }

และตอนนี้ก็พร้อมใช้งานแล้ว:

ในการป้อนข้อมูล เรามีรายการรูปแบบ:

 List<string> 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 < patterns.Count; i++) { ahoAlg.AddString(patterns[i], i); // Add all patterns to the structure } // Prepare algorithm for work (calculates all links in the structure): ahoAlg.PrepareAho(); // Process the text. Output might be different; in my case, it's a count of // matches. We could instead return a structure with more detailed information. int countOfMatches = ahoAlg.ProcessString(text);

และนั่นแหล่ะ! ตอนนี้คุณรู้แล้วว่าอัลกอริธึมที่เรียบง่ายแต่ทรงพลังนี้ทำงานอย่างไร!

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 ไม่ใช่ปัญหาเลย:

ข้อความขนาดใหญ่สามารถแบ่งออกเป็นกลุ่มต่างๆ ได้ และสามารถใช้หลายเธรดเพื่อประมวลผลแต่ละกลุ่มได้ แต่ละเธรดสามารถเข้าถึงการพยายามสร้างตามพจนานุกรม

แล้วคำที่แยกจากกันที่ขอบเขตระหว่างส่วนต่างๆ ล่ะ? ปัญหานี้สามารถแก้ไขได้ง่าย

ให้ N เป็นความยาวของข้อความขนาดใหญ่ของเรา S เป็นขนาดของกลุ่ม และ L เป็นความยาวของรูปแบบที่ใหญ่ที่สุดในพจนานุกรม

ตอนนี้เราสามารถใช้เคล็ดลับง่ายๆ เราแบ่งส่วนย่อยโดยมีการทับซ้อนกันในตอนท้าย เช่น ใช้ [S * (i - 1), S * i + L - 1] โดยที่ i เป็นดัชนีของกลุ่ม เมื่อเราได้รูปแบบที่ตรงกัน เราสามารถรับดัชนีเริ่มต้นของการจับคู่ปัจจุบันได้อย่างง่ายดาย และเพียงแค่ตรวจสอบว่าดัชนีนี้อยู่ในช่วงกลุ่มที่ไม่มีคาบเกี่ยวกัน [S * (i - 1), S * i - 1]

อัลกอริธึมการค้นหาสตริงที่หลากหลาย

อัลกอริธึม Aho-Corasick เป็นอัลกอริธึมการจับคู่สตริงที่ทรงพลังซึ่งนำเสนอความซับซ้อนที่ดีที่สุดสำหรับอินพุตใดๆ และไม่ต้องการหน่วยความจำเพิ่มเติมมากนัก

อัลกอริทึมนี้มักใช้ในระบบต่างๆ เช่น เครื่องตรวจการสะกด ตัวกรองสแปม เครื่องมือค้นหา การค้นหาลำดับชีวสารสนเทศ/DNA เป็นต้น อันที่จริง เครื่องมือยอดนิยมบางอย่างที่คุณอาจใช้ทุกวันกำลังใช้อัลกอริทึมนี้อยู่เบื้องหลัง

ฟังก์ชันนำหน้าจากอัลกอริทึม KMP เป็นเครื่องมือที่น่าสนใจที่นำความซับซ้อนของการจับคู่รูปแบบเดียวลงมาจนถึงเวลาเชิงเส้น อัลกอริธึม Aho-Corasick ใช้แนวทางที่คล้ายกันและใช้โครงสร้างข้อมูลแบบทดลองเพื่อทำแบบเดียวกันสำหรับรูปแบบต่างๆ

ฉันหวังว่าคุณจะพบว่าบทช่วยสอนนี้เกี่ยวกับอัลกอริทึม Aho-Corasick มีประโยชน์