เข็มในกองหญ้า: บทแนะนำอัลกอริธึมการค้นหาข้อความขนาดใหญ่ที่ดี

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

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

แอปพลิเคชั่น

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

แนวทางตรง

วิธีพื้นฐานที่สุดคือการวนซ้ำวลีค้นหา และค้นหาข้อความแต่ละวลีทีละข้อความ วิธีนี้ไม่ได้ขยายขนาดได้ดี การค้นหาสตริงภายในอีกอันมีความซับซ้อน O(n) ทำซ้ำสำหรับ ม. วลีค้นหานำไปสู่ ​​แย่ O(m * n)

ข้อดี (น่าจะเท่านั้น) ของแนวทางตรงที่ง่ายต่อการนำไปใช้ ดังที่ปรากฏในตัวอย่าง C# ต่อไปนี้:

 String[] search_phrases = File.ReadAllLines ("terms.txt"); String text_body = File.ReadAllText("body.txt"); int count = 0; foreach (String phrase in search_phrases) if (text_body.IndexOf (phrase) >= 0) ++count;

การรันโค้ดนี้บนเครื่องพัฒนาของฉัน [1] เทียบกับตัวอย่างทดสอบ [2] ฉันมีรันไทม์ 1 ชั่วโมง 14 นาที ซึ่งเกินเวลาที่คุณต้องหยิบกาแฟสักถ้วย ลุกขึ้นและยืดกล้ามเนื้อ หรือข้อแก้ตัวอื่นใด นักพัฒนาใช้เพื่อข้ามงาน

แนวทางที่ดีกว่า - The Trie

สถานการณ์ก่อนหน้าสามารถปรับปรุงได้สองวิธี ตัวอย่างเช่น กระบวนการค้นหาสามารถแบ่งพาร์ติชันและทำขนานกันบนโปรเซสเซอร์/คอร์หลายตัว แต่การลดรันไทม์ที่ทำได้โดยวิธีนี้ (รันไทม์รวม 20 นาที สมมติว่ามีการแบ่งที่สมบูรณ์แบบมากกว่า 4 โปรเซสเซอร์/คอร์) ไม่ได้แสดงให้เห็นถึงความซับซ้อนที่เพิ่มขึ้นของการเข้ารหัส/การดีบัก

ทางออกที่ดีที่สุดคือวิธีแก้ปัญหาที่ข้ามเนื้อหาของข้อความเพียงครั้งเดียว สิ่งนี้ต้องการให้วลีค้นหาจัดทำดัชนีในโครงสร้างที่สามารถขวางเป็นเส้นตรง ขนานกับเนื้อหาข้อความในครั้งเดียว บรรลุความซับซ้อนขั้นสุดท้ายของ O(n)

โครงสร้างข้อมูลที่เหมาะอย่างยิ่งสำหรับสถานการณ์จำลองนี้คือ tri โครงสร้างข้อมูลที่หลากหลายนี้มักถูกมองข้ามและไม่โด่งดังเท่าโครงสร้างที่เกี่ยวข้องกับต้นไม้อื่นๆ เมื่อพูดถึงปัญหาการค้นหา

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

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

ข้อดีของการทดลองใช้คือลดเวลาในการค้นหาลงอย่างมาก เพื่อให้ง่ายต่อการเข้าใจวัตถุประสงค์ของบทช่วยสอนนี้ ให้ลองนึกภาพต้นไม้ไบนารี การข้ามต้นไม้ไบนารีมีความซับซ้อนของ O(log 2 n) เนื่องจากแต่ละโหนดแยกออกเป็นสองส่วน โดยตัดการข้ามผ่านที่เหลือครึ่งหนึ่ง ด้วยเหตุนี้ ต้นไม้สามส่วนจึงมีความซับซ้อนในการเคลื่อนที่ของ O(log 3 n) อย่างไรก็ตาม จำนวนโหนดย่อยถูกกำหนดโดยลำดับที่แสดง และในกรณีของข้อความที่อ่านได้/สื่อความหมาย จำนวนของโหนดย่อยมักจะสูง

อัลกอริทึมการค้นหาข้อความ

ยกตัวอย่างง่ายๆ สมมติว่าวลีค้นหาต่อไปนี้:

• “ครอบครัวเดียวกัน”
• “ครอบครัวที่แตกต่าง”
• “การดำรงอยู่ต่างหาก”
• “สมาชิกของลีก”

จำไว้ว่าเรารู้วลีค้นหาของเราล่วงหน้า ดังนั้นเราจึงเริ่มต้นด้วยการสร้างดัชนีในรูปแบบของการพยายาม:

ต่อมา ผู้ใช้ซอฟต์แวร์ของเรานำเสนอไฟล์ที่มีข้อความต่อไปนี้:

ภาษายุโรปเป็นสมาชิกของครอบครัวเดียวกัน การดำรงอยู่ของพวกเขาต่างหากคือตำนาน

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

ตัวบ่งชี้การพยายามกลับมาเริ่มต้นในสองกรณี: เมื่อถึงจุดสิ้นสุดของสาขา ซึ่งหมายความว่าพบวลีค้นหา หรือเมื่อพบคำที่ไม่ตรงกัน ซึ่งในกรณีนี้ไม่พบที่ตรงกัน

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

ลองใช้อัลกอริธึมนี้กับตัวอย่างโครงสร้างข้อมูลแบบทดลองของเราและดูว่าจะเป็นอย่างไร:

ดังที่เราเห็น ระบบค้นหาวลีที่ตรงกันสองประโยคได้สำเร็จ "ครอบครัวเดียวกัน" และ "การดำรงอยู่อย่างแยกจากกัน"

ตัวอย่างในโลกแห่งความเป็นจริง

สำหรับโครงการล่าสุด ฉันได้รับการนำเสนอด้วยปัญหาต่อไปนี้: ลูกค้ามีบทความจำนวนมากและวิทยานิพนธ์ระดับปริญญาเอกที่เกี่ยวข้องกับสาขาการทำงานของเธอ และได้สร้างรายการวลีของตนเองซึ่งแสดงถึงชื่อเรื่องและกฎเกณฑ์เฉพาะที่เกี่ยวข้องกับสาขาเดียวกัน งาน.

ภาวะที่กลืนไม่เข้าคายไม่ออกของเธอคือ: จากรายชื่อวลี เธอเชื่อมโยงบทความ/วิทยานิพนธ์กับวลีเหล่านั้นอย่างไร เป้าหมายสุดท้ายคือการสุ่มเลือกกลุ่มวลีและมีรายการบทความ/วิทยานิพนธ์ที่กล่าวถึงวลีเฉพาะเหล่านั้นที่พร้อมสำหรับการจับได้ทันที

ตามที่กล่าวไว้ก่อนหน้านี้ มีสองส่วนในการแก้ปัญหานี้: การทำดัชนีวลีในกลุ่มทดลอง และการค้นหาจริง ส่วนต่อไปนี้เป็นการนำไปใช้อย่างง่ายใน C # โปรดทราบว่าการจัดการไฟล์ ปัญหาการเข้ารหัส การล้างข้อความ และปัญหาที่คล้ายกันนั้นไม่ได้รับการจัดการในตัวอย่างเหล่านี้ เนื่องจากสิ่งเหล่านี้อยู่นอกขอบเขตของบทความนี้

การจัดทำดัชนี

การดำเนินการสร้างดัชนีเพียงแค่ข้ามวลีทีละคำและแทรกลงใน trie หนึ่งคำต่อโหนด/ระดับ โหนดจะแสดงด้วยคลาสต่อไปนี้:

 class Node { int PhraseId = -1; Dictionary<String, Node> Children = new Dictionary<String, Node>(); public Node() { } public Node(int id) { PhraseId = id; } }

แต่ละวลีจะแสดงด้วย ID ซึ่งสามารถเป็นแบบง่ายๆ ได้เหมือนกับจำนวนที่เพิ่มขึ้น และส่งผ่านไปยังฟังก์ชันการจัดทำดัชนีต่อไปนี้ (รูทตัวแปรคือรูทที่แท้จริงของ trie):

 void addPhrase(ref Node root, String phrase, int phraseId) { // a pointer to traverse the trie without damaging // the original reference Node node = root; // break phrase into words String[] words = phrase.Split (); // start traversal at root for (int i = 0; i < words.Length; ++i) { // if the current word does not exist as a child // to current node, add it if (node.Children.ContainsKey(words[i]) == false) node.Children.Add(words[i], new Node()); // move traversal pointer to current word node = node.Children[words[i]]; // if current word is the last one, mark it with // phrase Id if (i == words.Length - 1) node.PhraseId = phraseId; } }

กำลังค้นหา

ขั้นตอนการค้นหาเป็นการนำอัลกอริธึม trie ไปใช้โดยตรงที่กล่าวถึงในบทช่วยสอนด้านบน:

 void findPhrases(ref Node root, String textBody) { // a pointer to traverse the trie without damaging // the original reference Node node = root; // a list of found ids List<int> foundPhrases = new List<int>(); // break text body into words String[] words = textBody.Split (); // starting traversal at trie root and first // word in text body for (int i = 0; i < words.Length;) { // if current node has current word as a child // move both node and words pointer forward if (node.Children.ContainsKey(words[i])) { // move trie pointer forward node = node.Children[words[i]]; // move words pointer forward ++i; } else { // current node does not have current // word in its children // if there is a phrase Id, then the previous // sequence of words matched a phrase, add Id to // found list if (node.PhraseId != -1) foundPhrases.Add(node.PhraseId); if (node == root) { // if trie pointer is already at root, increment // words pointer ++i; } else { // if not, leave words pointer at current word // and return trie pointer to root node = root; } } } // one case remains, word pointer as reached the end // and the loop is over but the trie pointer is pointing to // a phrase Id if (node.PhraseId != -1) foundPhrases.Add(node.PhraseId); }

ผลงาน

รหัสที่นำเสนอนี้ดึงมาจากโครงการจริงและได้ลดความซับซ้อนลงเพื่อวัตถุประสงค์ของเอกสารนี้ การรันโค้ดนี้อีกครั้งบนเครื่องเดิม [1] และเทียบกับตัวอย่างการทดสอบเดียวกัน [2] ส่งผลให้ใช้เวลารันไทม์ 2.5 วินาทีสำหรับการสร้าง trie และ 0.3 วินาทีสำหรับการค้นหา มากสำหรับเวลาพักใช่มั้ย?

รูปแบบต่างๆ

สิ่งสำคัญคือต้องยอมรับว่าอัลกอริทึมตามที่อธิบายไว้ในบทช่วยสอน Trie นี้อาจล้มเหลวได้ในบางกรณี ดังนั้นจึงได้รับการออกแบบโดยคำนึงถึงคำค้นหาที่กำหนดไว้ล่วงหน้าอยู่แล้ว

ตัวอย่างเช่น หากจุดเริ่มต้นของข้อความค้นหาหนึ่งเหมือนกับบางส่วนของข้อความค้นหาอื่น เช่น:

• “ เพื่อแบ่งปัน และสนุกกับเพื่อน”
• “ฉันมีตั๋วสองใบ ที่จะแบ่งให้ ใครซักคน”

และเนื้อความข้อความมีวลีที่ทำให้ตัวชี้ tri เริ่มต้นเส้นทางที่ไม่ถูกต้อง เช่น:

ฉันมีตั๋วสองใบที่จะแบ่งปันและสนุกกับเพื่อนๆ

จากนั้นอัลกอริธึมจะไม่จับคู่คำใด ๆ เนื่องจากตัวบ่งชี้การพยายามจะไม่กลับไปที่โหนดเริ่มต้นจนกว่าตัวบ่งชี้ข้อความจะผ่านจุดเริ่มต้นของคำที่ตรงกันในเนื้อหาข้อความแล้ว

สิ่งสำคัญคือต้องพิจารณาว่า edge case ประเภทนี้เป็นไปได้สำหรับแอปพลิเคชันของคุณหรือไม่ก่อนใช้งานอัลกอริทึม หากเป็นเช่นนั้น อัลกอริทึมสามารถแก้ไขได้ด้วยตัวบ่งชี้การพยายามเพิ่มเติมเพื่อติดตามการแข่งขันทั้งหมด ณ เวลาที่กำหนด แทนที่จะเป็นเพียงการจับคู่ครั้งเดียว

บทสรุป

การค้นหาข้อความเป็นศาสตร์ลึกในวิทยาการคอมพิวเตอร์ สาขาที่เต็มไปด้วยปัญหาและแนวทางแก้ไขเหมือนกัน ประเภทข้อมูลที่ฉันต้องจัดการ (ข้อความ 23MB เป็นหนังสือมากมายในชีวิตจริง) อาจดูเหมือนเป็นเหตุการณ์ที่เกิดขึ้นได้ยากหรือเป็นปัญหาเฉพาะ แต่นักพัฒนาที่ทำงานเกี่ยวกับการวิจัยทางภาษาศาสตร์ การเก็บถาวร หรือการจัดการข้อมูลประเภทอื่นๆ พบข้อมูลจำนวนมากขึ้นเป็นประจำ

ดังที่เห็นได้ชัดในบทช่วยสอนเกี่ยวกับโครงสร้างข้อมูลแบบทดลองข้างต้น การเลือกอัลกอริทึมที่ถูกต้องสำหรับปัญหาในมือเป็นสิ่งสำคัญอย่างยิ่ง ในกรณีพิเศษนี้ แนวทางสามวิธีลดรันไทม์ลงได้ 99.93% จากเวลาหนึ่งชั่วโมงเหลือน้อยกว่า 3 วินาที

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

[1] เครื่องที่ใช้สำหรับการทดสอบนี้มีข้อกำหนดดังต่อไปนี้:

• Intel i7 4700HQ
• แรม 16GB

ทำการทดสอบบน Windows 8.1 โดยใช้ .NET 4.5.1 และ Kubuntu 14.04 โดยใช้ mono เวอร์ชันล่าสุด และผลลัพธ์ก็ใกล้เคียงกันมาก

[2] ตัวอย่างทดสอบประกอบด้วยวลีค้นหา 280K ที่มีขนาดรวม 23.5MB และเนื้อหาข้อความ 1.5MB