อ่าน 2 นาที
เมตริกสตริง
ในคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์เมตริกสตริง (หรือที่รู้จักกันในชื่อเมตริกความคล้ายคลึงของสตริงหรือฟังก์ชันระยะทางของสตริง ) คือเมตริกที่วัดระยะทาง ("ความคล้ายคลึงผกผัน")...
เมตริกสตริง
ในคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์เมตริกสตริง (หรือที่รู้จักกันในชื่อเมตริกความคล้ายคลึงของสตริงหรือฟังก์ชันระยะทางของสตริง ) คือเมตริกที่วัดระยะทาง ("ความคล้ายคลึงผกผัน") ระหว่างสตริงข้อความ สองสตริง สำหรับการจับคู่หรือเปรียบเทียบสตริงโดยประมาณ และในการค้นหาสตริงแบบคลุมเครือข้อกำหนดสำหรับเมตริก สตริง (เช่น ในทางตรงกันข้ามกับการจับคู่สตริง ) คือการปฏิบัติตามอสมการสามเหลี่ยมตัวอย่างเช่น สตริง "Sam" และ "Samuel" สามารถถือได้ว่าอยู่ใกล้กัน[ 1 ]เมตริกสตริงจะให้ตัวเลขที่บ่งบอกถึงระยะทางที่เฉพาะเจาะจงกับอัลกอริทึม
เมตริกสตริงที่เป็นที่รู้จักกันอย่างแพร่หลายที่สุดคือเมตริกพื้นฐานที่เรียกว่าระยะทาง Levenshtein (หรือที่รู้จักกันในชื่อระยะทางแก้ไข) [ 2 ] มันทำงานระหว่างสตริงอินพุตสองสตริง โดยส่งคืนตัวเลขที่เทียบเท่ากับจำนวนการแทนที่และการลบที่จำเป็นในการแปลงสตริงอินพุตหนึ่งเป็นอีกสตริงหนึ่ง เมตริกสตริงแบบง่าย เช่นระยะทาง Levenshteinได้ขยายไปรวมถึงวิธีการเปรียบเทียบทางสถิติตามเสียงโทเค็น ไวยากรณ์และอักขระ
เมตริกสตริงถูกนำมาใช้อย่างมากในการบูรณาการข้อมูลและปัจจุบันถูกนำไปใช้ในด้านต่างๆ เช่นการตรวจจับการฉ้อโกงการวิเคราะห์ลายนิ้วมือ การตรวจ จับการลอกเลียนแบบ การรวมออนโทโลยีการวิเคราะห์ DNAการวิเคราะห์ RNA การวิเคราะห์ภาพ การเรียนรู้ ของเครื่องจักรตามหลักฐานการลบข้อมูล ซ้ำในฐาน ข้อมูล การขุดข้อมูล การค้นหา แบบเพิ่มขึ้นการบูรณาการข้อมูลการตรวจจับมัลแวร์ [ 3 ] และการบูรณาการความรู้ เชิงความ หมาย
รายการเมตริกสตริง
- ระยะทางเลเวนสไตน์หรือระยะทางแก้ไขซึ่งเป็นการขยาย ความของระยะทางเลเวนสไตน์
- ระยะทาง Damerau–Levenshtein
- สัมประสิทธิ์ Sørensen–Dice
- ระยะทางเป็นบล็อกหรือระยะทาง L1หรือระยะทางเป็นบล็อกในเมือง
- ระยะทางแฮมมิง
- สัมประสิทธิ์การจับคู่แบบง่าย (SMC)
- ความคล้ายคลึงของ Jaccardหรือสัมประสิทธิ์ Jaccardหรือสัมประสิทธิ์ Tanimoto
- ดัชนีทเวอร์สกี
- สัมประสิทธิ์การทับซ้อน
- ระยะทางแปรผัน[ 4 ]
- ระยะทางเฮลลิงเกอร์หรือระยะทางภัตตาจารยะ
- รัศมีข้อมูล ( ความแตกต่างของเจนเซน-แชนนอน )
- การเบี่ยงเบนแบบเฉียง[ 4 ]
- ความน่าจะเป็นของความสับสน[ 4 ]
- เมตริกเทา (Tau metric)ซึ่งเป็นการประมาณค่าความแตกต่างแบบคัลแบ็ก-ไลเบลอร์ (Kullback–Leibler divergence)
- เมตริก Fellegi และ Sunters (SFS) [ 4 ]
- การจับคู่สูงสุด[ 4 ]
- ระยะทางตามไวยากรณ์[ 5 ]
- เมตริกระยะทางTFIDF [ 6 ]
นอกจากนี้ยังมีฟังก์ชันที่ใช้วัดความแตกต่างระหว่างสตริง แต่ไม่จำเป็นต้องเป็นไปตามอสมการสามเหลี่ยม และด้วยเหตุนี้จึงไม่ถือว่าเป็นเมตริกในความหมายทางคณิตศาสตร์ ตัวอย่างของฟังก์ชันดังกล่าวคือระยะทาง Jaro– Winkler
ตัวอย่างการวัดสตริงที่เลือก
| ชื่อ | คำอธิบาย | ตัวอย่าง |
|---|---|---|
| ระยะทางแฮมมิง | เฉพาะสำหรับสตริงที่มีความยาวเท่ากันเท่านั้น จำนวนอักขระที่เปลี่ยนแปลง | " ka rol in " และ " ka thr in " คือ 3 |
| ระยะทางเลเวนสไตน์และระยะทางดาเมอเรา-เลเวนสไตน์ | การขยายความหมายของระยะทางแฮมมิงที่อนุญาตให้ใช้สายที่มีความยาวต่างกัน และ (ร่วมกับดาเมอโร) สำหรับการเปลี่ยนคีย์ | kitt e n and sitting have a distance of 3 .
|
| ระยะทาง Jaro–Winkler | JaroWinklerDist("MARTHA","MARHTA") =
| |
| อักขระ k ที่พบบ่อยที่สุด | MostFreqKeySimilarity(' r e s e a r ch', 's eeking ', 2) = 2 |
ลิงก์ภายนอก
- ตัวชี้วัดความคล้ายคลึงของสตริงสำหรับการบูรณาการข้อมูล ภาพรวม ที่ค่อนข้างสมบูรณ์ดัชนีเอกสารสำคัญที่Wayback Machine
- ห้องสมุดโอเพนซอร์สของมหาวิทยาลัยคาร์เนกีเมลลอน
- โปรเจกต์ StringMetricคือ ไลบรารี Scalaสำหรับวัดค่าเมตริกของสตริงและอัลกอริธึมทางด้านสัทศาสตร์
- Naturalเป็น โปรเจกต์ไลบรารี JavaScriptสำหรับประมวลผลภาษาธรรมชาติ ซึ่งรวมถึงการใช้งานเมตริกสตริงยอดนิยมต่างๆ
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ เมตริกสตริง
ในคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์เมตริกสตริง (หรือที่รู้จักกันในชื่อเมตริกความคล้ายคลึงของสตริงหรือฟังก์ชันระยะทางของสตริง ) คือเมตริกที่วัดระยะทาง ("ความคล้ายคลึงผกผัน")...
รายการเมตริกสตริง
นอกจากนี้ยังมีฟังก์ชันที่ใช้วัดความแตกต่างระหว่างสตริง แต่ไม่จำเป็นต้องเป็นไปตามอสมการสามเหลี่ยม และด้วยเหตุนี้จึงไม่ถือว่าเป็น เมตริก ในความหมายทางคณิตศาสตร์ ตัวอย่างของฟังก์ชันดังกล่าวคือ ระยะทาง Jaro– Winkler
ตัวอย่างการวัดสตริงที่เลือก
ชื่อ คำอธิบาย ตัวอย่าง ระยะทางแฮมมิง เฉพาะสำหรับสตริงที่มีความยาวเท่ากันเท่านั้น จำนวนอักขระที่เปลี่ยนแปลง " ka rol in " และ " ka thr in " คือ 3 ระยะทางเลเวนสไตน์ และ ระยะทางดาเมอเรา-เลเวนสไตน์...
ลิงก์ภายนอก
ตัวชี้วัดความคล้ายคลึงของสตริงสำหรับการบูรณาการข้อมูล ภาพรวม ที่ค่อนข้างสมบูรณ์ดัชนีเอกสารสำคัญที่ Wayback Machine ห้องสมุดโอเพนซอร์สของมหาวิทยาลัยคาร์เนกีเมลลอน โปรเจกต์ StringMetricคือ ไลบรารี Scala สำหรับวัดค่าเมตริกของสตริงและอัลกอริธึมทางด้านสัทศาสตร์...