ดาวน์โหลด DawgSharp - ดาวน์โหลดซอร์สโค้ด DawgSharp

DawgSharp

ซอร์สโค้ดอื่น ๆ

1.0.0

ดาวน์โหลด

[แพ็คเกจ NuGet] [รับใบอนุญาตเชิงพาณิชย์]

DawgSharp พจนานุกรมสตริงที่ชาญฉลาดใน C#

DAWG (Directed Acyclic Word Graph) เป็นโครงสร้างข้อมูลสำหรับจัดเก็บและค้นหารายการคำและพจนานุกรมขนาดใหญ่ อาจมีประสิทธิภาพมากกว่าคลาส .NET Dictionary ถึง 40 เท่าสำหรับข้อมูลบางประเภท

ตามตัวอย่าง เว็บไซต์ของฉันโฮสต์พจนานุกรมจำนวน 2 ล้านคำ ซึ่งเคยกินพื้นที่ดิสก์ถึง 56 เมกะไบต์ และใช้เวลาโหลด 7 วินาที (เมื่อใช้ Dictionary และ BinarySerializer) หลังจากเปลี่ยนมาใช้ DAWG ตอนนี้จะใช้เวลา 1.4 เมกะไบต์บนดิสก์ และ 0.3 วินาทีในการโหลด

สิ่งนี้เป็นไปได้อย่างไร? เหตุใดพจนานุกรมมาตรฐานจึงไม่ฉลาดเท่า DAWG ประเด็นก็คือ DAWG ทำงานได้ดีกับสตริงภาษาธรรมชาติ และอาจทำงานได้ไม่ดีเช่นกันกับสตริงที่สร้างขึ้น เช่น คีย์ใบอนุญาต (OIN1r4Be2su+UXSeOj0TaQ) คำในภาษามนุษย์มักจะมีลำดับตัวอักษรทั่วไปมากมาย เช่น -ility ใน ความสามารถ ความเป็นไปได้ ความคล่องตัว ฯลฯ และอัลกอริธึมใช้ประโยชน์จากสิ่งนั้นโดยการค้นหาลำดับเหล่านั้นและจัดเก็บเพียงครั้งเดียวสำหรับหลายคำ DAWG ยังได้รับการพิสูจน์แล้วว่ามีประโยชน์ในการแสดงข้อมูล DNA (ลำดับของยีน) ประวัติความเป็นมาของ DAWG ย้อนกลับไปในปี 1985 หากต้องการดูพื้นหลังเพิ่มเติม โปรดใช้ Google DAWG หรือ DAFSA (ระบบกำหนดสถานะอัตโนมัติแบบอะไซคลิกจำกัด)

DawgSharp เป็นการใช้งาน DAWG ซึ่งเป็นหนึ่งในหลาย ๆ อะไรทำให้ที่นี่พิเศษ?

เขียนด้วยภาษา C# ล้วนๆ คอมไพล์เป็น MSIL (AnyCPU) และทำงานบน .NET 3.5 ขึ้นไป
มันไม่มีการพึ่งพา
มันไม่แนะนำข้อจำกัดเกี่ยวกับอักขระในคีย์ การใช้งานที่แข่งขันกันบางอย่างอนุญาตให้ใช้ตัวอักษรภาษาอังกฤษได้เพียง 26 ตัวเท่านั้น การใช้งานนี้จัดการกับอักขระ Unicode ใด ๆ
อัลกอริธึมการบดอัดจะเข้าชมทุกโหนดเพียงครั้งเดียวซึ่งทำให้รวดเร็วมาก (5 วินาทีสำหรับรายการคำ 2 ล้านคำของฉัน)
มันนำเสนอการคงอยู่นอกกรอบ: เรียก Load/Save เพื่อเขียนข้อมูลลงดิสก์แล้วอ่านกลับ
มีการทดสอบหน่วย (โดยใช้กรอบการทดสอบ Visual Studio)
มีเซสชั่นการทำโปรไฟล์ประสิทธิภาพหลายชั่วโมงคน ดังนั้นจึงค่อนข้างเร็วที่สุดเท่าที่จะเป็นไปได้ ขั้นตอนต่อไปในการทำให้เร็วขึ้นคือการเขียนโค้ดที่เกี่ยวข้องใหม่ใน IL
เป็นมิตรกับ GC: Garbage Collector จะเห็น ints ขนาดใหญ่เพียง 3 อาร์เรย์เท่านั้น โดยที่ Dictionary จะเก็บสตริงได้หลายล้านสตริง

การใช้งาน

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

ขั้นแรกให้รับโค้ดโดยการโคลนพื้นที่เก็บข้อมูลนี้หรือติดตั้งแพ็คเกจ NuGet

สร้างและเติมวัตถุ DawgBuilder :

 var words = new [ ] { " Aaron " , " abacus " , " abashed " } ;

var dawgBuilder = new DawgBuilder < bool > ( ) ; // <bool> is the value type.
                                             // Key type is always string.
foreach ( string key in words )
{
    dawgBuilder . Insert ( key , true ) ;
}

(หรืออีกทางหนึ่ง ให้ทำ var dawgBuilder = words.ToDawgBuilder(key => key, _ => true); )

เรียก BuildDawg เพื่อรับเวอร์ชันบีบอัดและบันทึกลงดิสก์:

 Dawg < bool > dawg = dawgBuilder . BuildDawg ( ) ; 
// Computer is working.  Please wait ...

using ( var file = File . Create ( " DAWG.bin " ) ) 
    dawg . SaveTo ( file ) ;

ตอนนี้อ่านไฟล์กลับเข้าไปและตรวจสอบว่ามีคำใดอยู่ในพจนานุกรมหรือไม่:

 var dawg = Dawg < bool > . Load ( File . Open ( " DAWG.bin " ) ) ;

if ( dawg [ " chihuahua " ] )
{
    Console . WriteLine ( " Word is found. " ) ;
}

ชนิดของค่า <TPayload>

คลาส Dawg และ DawgBuilder ใช้พารามิเตอร์เทมเพลตชื่อ <TPayload> สามารถเป็นประเภทใดก็ได้ที่คุณต้องการ เพียงเพื่อให้สามารถทดสอบได้ว่ามีคำใดอยู่ในพจนานุกรมหรือไม่ บูลก็เพียงพอแล้ว คุณยังสามารถทำให้เป็น int หรือ string หรือคลาสที่กำหนดเองได้ แต่จงระวังข้อจำกัดที่สำคัญประการหนึ่ง DAWG ทำงานได้ดีก็ต่อเมื่อชุดของค่าที่ TPayload สามารถรับได้นั้นค่อนข้างเล็ก ยิ่งเล็กยิ่งดี เช่น หากคุณเพิ่มคำจำกัดความสำหรับแต่ละคำ จะทำให้แต่ละรายการไม่ซ้ำกัน และกราฟของคุณจะกลายเป็นแผนภูมิต้นไม้ (ซึ่งอาจจะไม่แย่เกินไป!)

MatchPrefix()

อีกด้านที่น่าสนใจของ DAWG คือความสามารถในการดึงคำทั้งหมดที่ขึ้นต้นด้วยสตริงย่อยเฉพาะอย่างมีประสิทธิภาพ:

dawg . MatchPrefix ( " awe " )

ข้อความค้นหาข้างต้นจะส่งคืน IEnumerable<KeyValuePair> ซึ่งอาจมีคีย์ต่างๆ เช่น aweful, aweful และ excellent การเรียก dawg.MatchPrefix("") จะส่งคืนรายการทั้งหมดในพจนานุกรม

หากคุณต้องการค้นหาด้วยคำต่อท้ายแทน ไม่มีวิธี MatchSuffix แต่สามารถบรรลุผลตามที่ต้องการได้โดยการเพิ่มคีย์ที่กลับรายการแล้วใช้ MatchPrefix() บนคีย์ที่กลับรายการ:

dawgBuilder . Insert ( " ability " . Reverse ( ) , true ) ;
.. .
dawg . MatchPrefix ( " ility " . Reverse ( ) )

รับคำนำหน้า()

GetPrefixes() ส่งคืนรายการพจนานุกรมทั้งหมดที่มีคีย์เป็นสตริงย่อยของสตริงที่กำหนด ตัวอย่างเช่น:

dawg . GetPrefixes ( " awesomenesses " )

อาจคืนกุญแจเช่น ความน่าเกรงขาม ยอดเยี่ยม ยอดเยี่ยม และในที่สุด ยอดเยี่ยม

GetLongestCommonPrefixLength()

คุณสมบัติเรียบร้อยอีกอย่างหนึ่งคือวิธีการ int GetLongestCommonPrefixLength(IEnumerable<char> word) หากพบ word ในพจนานุกรม คำนั้นจะส่งคืนความยาว ถ้าไม่เช่นนั้นก็จะส่งคืนความยาวของคำที่ยาวที่สุด ที่ พบในพจนานุกรมและนั่นคือจุดเริ่มต้นของคำที่กำหนดด้วย ตัวอย่างเช่น หาก การจัดเตรียม อยู่ในพจนานุกรมแต่ไม่ได้ มีการยึดล่วงหน้า ดังนั้น dawg.GetLongestCommonPrefixLength("preempt") จะส่งคืนค่า 3 ซึ่งเป็นความยาวของ "pre"

ความปลอดภัยของด้าย

คลาส DawgBuilder ไม่ ปลอดภัยสำหรับเธรด และต้องเข้าถึงได้เพียงเธรดเดียวเท่านั้นในเวลาใดก็ตาม

คลาส Dawg นั้นไม่เปลี่ยนรูปและปลอดภัยต่อเธรด

มัลติดอว์ก

คลาส MultiDawg สามารถจัดเก็บค่าหลายค่ากับคีย์สตริงเดียวในลักษณะที่หน่วยความจำมีประสิทธิภาพมาก

แผนการในอนาคต

สถานการณ์การใช้งานเพิ่มเติม

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