วิทยาศาสตร์ข้อมูลและฐานข้อมูล

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

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

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

อัลกอริทึม Aho-Corasick สำหรับปัญหาการค้นหาสตริงที่มีประสิทธิภาพ



ในบทความนี้คุณจะได้เรียนรู้เกี่ยวกับอัลกอริทึมที่ทรงพลังที่สุดสำหรับการค้นหารูปแบบในข้อความจำนวนมาก: อัลกอริทึม 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 สามารถแบ่งออกเป็นสามกรณี:

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

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

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

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

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

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

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

  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 เรารับค่าของฟังก์ชันคำนำหน้าสำหรับคำนำหน้าที่ตรงกันในปัจจุบัน 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 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) อัลกอริทึม:

Trie ที่จะประมวลผลโดยอัลกอริธึมการค้นหาอันดับแรก

และด้านล่างนี้คือการใช้งานการข้ามผ่านนี้:

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 สำหรับพจนานุกรมประกอบด้วย 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 นั้นไม่มีปัญหาเลย:

อัลกอริทึม Aho-Corasick ทำงานแบบขนานในสี่ส่วนของข้อความที่กำหนด

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

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

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

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

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

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

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

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

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

ทำลายหลักการออกแบบ (ด้วยอินโฟกราฟิก)

การออกแบบ Ux

ทำลายหลักการออกแบบ (ด้วยอินโฟกราฟิก)
ตลาดล้านดอลลาร์ดีกว่าตลาดพันล้านดอลลาร์หรือไม่?

ตลาดล้านดอลลาร์ดีกว่าตลาดพันล้านดอลลาร์หรือไม่?

นักลงทุนและเงินทุน