ต้นไม้บีเค

ต้นไม้บีเค (อังกฤษ: BK-tree หรือ อังกฤษ: Burkhard-Keller Trees) เป็นโครงสร้างข้อมูลแบบต้นไม้ซึ่งออกแบบมาเพื่อค้นหาสตริงที่ใกล้เคียงกับสตริง ใช้ในการตรวจสอบตัวสะกดตามระยะห่าง Levenshtein Distance ระหว่างคำสองคำซึ่งโดยทั่วไปแล้วจะมีจำนวนการเปลี่ยนแปลงที่ต้องทำเพื่อเป็นการเปลี่ยนเป็นคำอื่น

ต้นไม้ BK เป็นต้นไม้เมตริกที่แนะนำโดย Walter Austin Burkhard และ Robert M. Keller ที่ปรับให้เหมาะกับพื้นที่เมตริกแบบไม่ต่อเนื่อง สำหรับความเรียบง่ายให้เราพิจารณาเมตริกแบบไม่ต่อเนื่อง จำนวนเต็ม {\ displaystyle d (x, y)} d (x, y) จากนั้น ต้นไม้บีเคมีการกำหนดในลักษณะดังต่อไปนี้ มีการเลือกองค์ประกอบตามอำเภอใจ a เป็นโหนดราก โหนดรากอาจมี subtrees เป็นศูนย์หรือมากกว่า ทรีย่อย k-th สร้างขึ้นใหม่จากทุกองค์ประกอบ b เช่น {\ displaystyle d (a, b) = k} d (a, b) = k ต้นไม้บีเคสามารถใช้สำหรับการจับคู่สายโดยประมาณในพจนานุกรม

ตัวอย่างเช่น ใช้เป็นตัวตรวจสอบการสะกดหรือเมื่อค้นหาคำค้นหาแบบ "คลุมเครือ" จุดมุ่งหมายคือการกลับมาเช่น "seek" และ "peek" ถ้าฉันค้นหา "aeek" สิ่งที่ทำให้เป็นต้นไม้บีเค ก็คือพวกเขาใช้ปัญหาที่ไม่มีทางออกที่ชัดเจนนอกเหนือจากการค้นหาแบบ Brute force> และนำเสนอวิธีการที่เรียบง่ายและสง่างามเพื่อเร่งการค้นหาอย่างมาก

ความเป็นมาของต้นไม้บีเค

ต้นไม้บีเค ได้รับการเสนอโดย Burkhard and Keller เป็นครั้งแรกในปีพ. ศ. 2516 ในบทความ "แนวทางบางอย่างที่ตรงกับการค้นหาไฟล์" สำเนาเท่านั้นของออนไลน์นี้ดูเหมือนจะอยู่ในที่เก็บถาวรของ ACM ซึ่งเป็นการสมัครรับข้อมูลเท่านั้น รายละเอียดเพิ่มเติมได้จากบทความเรื่อง "Fast String Matching ในพจนานุกรม"

ก่อนที่เราจะสามารถกำหนดต้นไม้บีเค เราจำเป็นต้องกำหนดคู่ของการลงทะเบียนล่วงหน้า ในการทำดัชนีและค้นหาพจนานุกรมของเราเราจำเป็นต้องมีวิธีเปรียบเทียบสตริง วิธีการบัญญัติสำหรับนี้คือระยะทาง Levenshtein ซึ่งใช้เวลาสองสายและส่งกลับจำนวนที่แสดงถึงจำนวนขั้นต่ำของการแทรกการลบและการแทนที่ที่ต้องการในการแปลสตริงหนึ่ง ๆ ลงในอีก ฟังก์ชั่นสายอื่น ๆ ก็ยอมรับได้ (ตัวอย่างเช่นตัวเดียวที่นำแนวคิด transpositions มาใช้ในการปฏิบัติงานของอะตอม) ตราบเท่าที่พวกเขามีคุณสมบัติตรงตามเกณฑ์ที่กำหนดไว้ด้านล่าง

ตอนนี้เราสามารถให้ข้อสังเกตที่เป็นประโยชน์อย่างยิ่งเกี่ยวกับระยะทาง Levenshtein สร้างเป็น Metric Space ใส่เพียงแค่เมตริกพื้นที่คือความสัมพันธ์ใด ๆ ที่เป็นไปตามเกณฑ์ขั้นพื้นฐานสามอย่าง:

d (x, y) = 0 <-> x = y (ถ้าระยะห่างระหว่าง x และ y เท่ากับ 0 แล้ว x = y)

d (x, y) = d (y, x) (ระยะทางจาก x เป็น y เท่ากับระยะทางจาก y ถึง x)

d (x, y) + d (y, z) = d (x, z)

ข้อสุดท้ายของเกณฑ์เหล่านี้เรียกว่า Triangle Inealality ความไม่เท่ากันของสามเหลี่ยมกล่าวว่าเส้นทางจาก x ถึง z ต้องไม่ยาวกว่าเส้นทางใด ๆ ที่ผ่านจุดกึ่งกลางอื่น (เส้นทางจาก x ไป y ถึง z) มองไปที่รูปสามเหลี่ยมตัวอย่างเช่นคุณไม่สามารถวาดรูปสามเหลี่ยมเพื่อให้ได้รับจากจุดหนึ่งไปอีกมุมหนึ่งโดยไปตามสองด้านมากกว่าที่จะไปตามด้านอื่น ๆ

เกณฑ์ทั้งสามประการพื้นฐานตามที่พวกเขาเป็นทั้งหมดที่จำเป็นสำหรับบางอย่างเช่นระยะทาง Levenshtein เพื่อให้มีคุณสมบัติเป็น Metric Space โปรดสังเกตว่านี่เป็นเรื่องที่กว้างกว่าเช่น Euclidian Space - Euclidian Space เป็นเมตริก แต่ Metric Spaces (เช่น Levenshtein Distance) ไม่ใช่ Euclidian ตอนนี้เรารู้ว่า Levenshtein Distance (และฟังก์ชันทางสายอื่น ๆ ที่คล้ายคลึงกัน) แสดงถึง Metric Space เรามาสังเกตการณ์ Burkhard และ Keller ที่สำคัญ

การสร้างต้นไม้บีเค

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

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

ถ้าเริ่มต้นต้นไม้ด้วยชุดคำ [book, books, cake] แล้วต้นไม้จะมีลักษณะเช่นนี้ถ้าฉันเริ่มต้นโดยการทำคำว่า หนังสือเป็นโหนดราก

ขั้นตอนการสร้างต้นไม้บีเค

1) LevenshteinDistance (caqe, book) -> 4

   a) ตรวจสอบ (4 <= 1) - อย่าเพิ่มหนังสือในรูปแบบที่ตรงกัน

   ข) รวบรวมข้อมูลขอบทั้งหมดระหว่าง 3 ถึง 5 (4-1,4 + 1)

2) รวบรวมข้อมูลในเส้นทางขอบ 4 จากหนังสือ

3) LevenshteinDistance (caqe, cake) -> 1

   ก. ตรวจสอบ (1 <= 1) - เพิ่มเค้กในรูปแบบที่ตรงกัน

   b) รวบรวมข้อมูลขอบทั้งหมดระหว่าง 0 ถึง 2 (1-1, 1 + 1)

4) รวบรวมข้อมูลในเส้นทางขอบ 1 จากเค้ก

5) LevenshteinDistance (caqe, cape) -> 1

   a) (1 <= 1) - เพิ่มแหลมเป็นไม้ขีด

6) รวบรวมข้อมูลในเส้นทางขอบ 2 จากเค้ก

7) LevenshteinDistance (caqe, cart) -> 2

   a) ตรวจสอบ (2 <= 1) - อย่าเพิ่มรถเข็นเป็นไม้ขีด

จากตัวอย่างนี้ปรากฏว่าเราสามารถค้นหาการสะกดผิดที่เวลา O (log n) ซึ่งดีกว่า O (n)