กลับไปหน้าบทความ

อ่าน 2 นาที

เมตริกสตริง

ในคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์เมตริกสตริง (หรือที่รู้จักกันในชื่อเมตริกความคล้ายคลึงของสตริงหรือฟังก์ชันระยะทางของสตริง ) คือเมตริกที่วัดระยะทาง ("ความคล้ายคลึงผกผัน")...

เมตริกสตริง

ในคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์เมตริกสตริง (หรือที่รู้จักกันในชื่อเมตริกความคล้ายคลึงของสตริงหรือฟังก์ชันระยะทางของสตริง ) คือเมตริกที่วัดระยะทาง ("ความคล้ายคลึงผกผัน") ระหว่างสตริงข้อความ สองสตริง สำหรับการจับคู่หรือเปรียบเทียบสตริงโดยประมาณ และในการค้นหาสตริงแบบคลุมเครือข้อกำหนดสำหรับเมตริก สตริง (เช่น ในทางตรงกันข้ามกับการจับคู่สตริง ) คือการปฏิบัติตามอสมการสามเหลี่ยมตัวอย่างเช่น สตริง "Sam" และ "Samuel" สามารถถือได้ว่าอยู่ใกล้กัน[ 1 ]เมตริกสตริงจะให้ตัวเลขที่บ่งบอกถึงระยะทางที่เฉพาะเจาะจงกับอัลกอริทึม

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

เมตริกสตริงถูกนำมาใช้อย่างมากในการบูรณาการข้อมูลและปัจจุบันถูกนำไปใช้ในด้านต่างๆ เช่นการตรวจจับการฉ้อโกงการวิเคราะห์ลายนิ้วมือ การตรวจ จับการลอกเลียนแบบ การรวมออนโทโลยีการวิเคราะห์ DNAการวิเคราะห์ RNA การวิเคราะห์ภาพ การเรียนรู้ ของเครื่องจักรตามหลักฐานการลบข้อมูล ซ้ำในฐาน ข้อมูล การขุดข้อมูล การค้นหา แบบเพิ่มขึ้นการบูรณาการข้อมูลการตรวจจับมัลแวร์ [ 3 ] และการบูรณาการความรู้ เชิงความ หมาย

รายการเมตริกสตริง

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

ตัวอย่างการวัดสตริงที่เลือก

ชื่อ คำอธิบาย ตัวอย่าง
ระยะทางแฮมมิงเฉพาะสำหรับสตริงที่มีความยาวเท่ากันเท่านั้น จำนวนอักขระที่เปลี่ยนแปลง " ka rol in " และ " ka thr in " คือ 3
ระยะทางเลเวนสไตน์และระยะทางดาเมอเรา-เลเวนสไตน์การขยายความหมายของระยะทางแฮมมิงที่อนุญาตให้ใช้สายที่มีความยาวต่างกัน และ (ร่วมกับดาเมอโร) สำหรับการเปลี่ยนคีย์ kitt e n and sitting have a distance of 3 .
  1. k itten s itten (เปลี่ยน "k" เป็น "s")
  2. sitt e nsitt ฉัน n (แทนที่ "i" สำหรับ "e")
  3. sittinsittin g (เติม "g" ที่ท้าย)
ระยะทาง Jaro–WinklerJaroWinklerDist("MARTHA","MARHTA") =
  • คือจำนวนอักขระที่ตรงกัน ;
  • เป็นครึ่งหนึ่งของจำนวนการสลับตำแหน่ง ( "MARTHA"[3]!=H, "MARHTA"[3]!=T)
อักขระ k ที่พบบ่อยที่สุดMostFreqKeySimilarity(' r e s e a r ch', 's eeking ', 2) = 2
  • ตัวชี้วัดความคล้ายคลึงของสตริงสำหรับการบูรณาการข้อมูล ภาพรวม ที่ค่อนข้างสมบูรณ์ดัชนีเอกสารสำคัญที่Wayback Machine
  • ห้องสมุดโอเพนซอร์สของมหาวิทยาลัยคาร์เนกีเมลลอน
  • โปรเจกต์ StringMetricคือ ไลบรารี Scalaสำหรับวัดค่าเมตริกของสตริงและอัลกอริธึมทางด้านสัทศาสตร์
  • Naturalเป็น โปรเจกต์ไลบรารี JavaScriptสำหรับประมวลผลภาษาธรรมชาติ ซึ่งรวมถึงการใช้งานเมตริกสตริงยอดนิยมต่างๆ
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=String_metric&oldid=1239983587 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ เมตริกสตริง

ในคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์เมตริกสตริง (หรือที่รู้จักกันในชื่อเมตริกความคล้ายคลึงของสตริงหรือฟังก์ชันระยะทางของสตริง ) คือเมตริกที่วัดระยะทาง ("ความคล้ายคลึงผกผัน")...

รายการเมตริกสตริง

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

ตัวอย่างการวัดสตริงที่เลือก

ชื่อ คำอธิบาย ตัวอย่าง ระยะทางแฮมมิง เฉพาะสำหรับสตริงที่มีความยาวเท่ากันเท่านั้น จำนวนอักขระที่เปลี่ยนแปลง " ka rol in " และ " ka thr in " คือ 3 ระยะทางเลเวนสไตน์ และ ระยะทางดาเมอเรา-เลเวนสไตน์...

ลิงก์ภายนอก

ตัวชี้วัดความคล้ายคลึงของสตริงสำหรับการบูรณาการข้อมูล ภาพรวม ที่ค่อนข้างสมบูรณ์ดัชนีเอกสารสำคัญที่ Wayback Machine ห้องสมุดโอเพนซอร์สของมหาวิทยาลัยคาร์เนกีเมลลอน โปรเจกต์ StringMetricคือ ไลบรารี Scala สำหรับวัดค่าเมตริกของสตริงและอัลกอริธึมทางด้านสัทศาสตร์...