การเข้าหาด้วยการจัดระดับคู่

การเข้าหาด้วยการจัดระดับคู่ หรือ แมทช์เรตติงแอพโพรช (อังกฤษ: Match Rating Approach) เป็นขั้นตอนวิธีเชิงสัทลักษณ์อย่างหนึ่งซึ่งทำการเปรียบเทียบและจัดระดับความคล้ายคลึงให้กับชื่อภาษาอังกฤษที่มีลักษณะพ้องเสียงกัน ขั้นตอนวิธีนี้ถูกพัฒนาขึ้นโดยสายการบินเวสเทอร์นแอร์ไลน์ (Western Airlines) เมื่อปี พ.ศ. 2520 (ค.ศ. 1977)

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

การเข้าหาด้วยการจัดระดับคู่นั้นทำงานได้ดีเป็นพิเศษเมื่อใช้กับชื่อที่มีตัวอักษร "y" เช่นสามารถจับคู่นามสกุลอย่าง "Smith" และ "Smyth" ได้อย่างประสบความสำเร็จเมื่อเปรียบเทียบกับขั้นตอนวิธี New York State Identification and Intelligence System (NYSIIS) แต่ยังคงทำงานได้ไม่ดีนักเมื่อชื่อที่ผ่านการเข้ารหัสมีความยาวต่างกันเกินสองตัวอักษร

 ขั้นตอนวิธี 

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

ต่อไปนี้จะเป็นลำดับขั้นตอนโดยละเอียด

 ขั้นตอนเข้ารหัส 

ขั้นตอนเข้ารหัสนี้กระทำบนคำทุกๆ คำที่จะทำการจัดระดับ

 ลบตัวอักษรที่เป็นสระออกทั้งหมด (a, e, i, o, u) ยกเว้นแต่ว่าตัวอักษรที่ว่านั้นเป็นตัวอักษรตัวแรกของคำ
 ลบพยัญชนะตัวที่สองออกจากพยัญชนะคู่ทั้งหมด (ตักอักษรตัวที่สองใน bb, pp, dd, tt, ฯลฯ)
 หากผลลัพธ์ยังมีความยาวเกิน 6 ตัวอักษร ให้นำ 3 ตัวอักษรแรกของรหัสมาต่อกับ 3 ตัวอักษรหลังแล้วตัดส่วนที่เหลือที้ง

ผลลัพธ์ที่ได้นี้ต่อไปนี้จะเรียกว่ารหัส ซึ่งต้องใช้ในการเปรียบเทียบต่อไป

 ขั้นตอนเปรียบเทียบ 

ขั้นตอนเปรียบเทียบกระทำบนรหัสคู่ที่จะทำการจัดระดับความคล้าย โดยทำการเปรียบเทียบรหัสทีละคู่

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

 ตารางคำนวณระดับต่ำสุด 

ตารางต่อไปนี้แสดงการคำนวณระดับต่ำสุดจากความยาวรวมของรหัส

 ความยาวรวม ระดับต่ำสุด ความยาวรวม ≤ 4 5 4 < ความยาวรวม ≤ 7 4 7 < ความยาวรวม ≤ 11 3 ความยาวรวม = 12 2

 ตัวอย่างการทำงาน 

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

 การเข้ารหัส 

 "HARPER" เมื่อถูกตัดตัวอักษรที่เป็นสระทั้งหมดออกกลายเป็น "HRPR"
 ไม่มีพยัญชนะคู่ ไม่มีการเปลี่ยนแปลง ยังคงเป็น "HRPR"
 ผลลัพธ์ความยาวไม่เกิน 6 ตัวอักษร ยังคงเดิมเป็น "HRPR"

 การเปรียบเทียบ 

เมื่อเข้ารหัสชื่อ "Harper" เรียบร้อยแล้ว ต่อไปก็ต้องนำรหัสที่ได้นี้ไปเปรียบเทียบกับฐานข้อมูล โดยชื่อที่มีอยู่ในฐานข้อมูลมีจำนวน 5 ชื่อด้วยกัน เมื่อนำชื่อเหล่านี้ไปเข้ารหัสจะได้รหัสดังต่อไปนี้ "LDN" "HRPR" "HRPRD" "HRP" และ "HBLTWNS" ลองนำรหัสเหล่านี้มาเปรียบเทียบกับรหัส "HRPR" ของ "Harper" ก็จะตรวจสอบได้ว่าชื่อเหล่านี้มีความคล้ายคลึงกับชื่อ "Harper" หรือไม่

 ขั้นตอน LDN HRPR HRPRD HRP HBLTWNS 1. ความยาวต่างกับ HRPR 0 ตัวอักษร — ผ่าน 0 ตัวอักษร — ผ่าน 1 ตัวอักษร — ผ่าน 1 ตัวอักษร — ผ่าน 3 ตัวอักษร — ไม่ผ่าน 2. ความยาวรวมกับ HRPR 7 ตัวอักษร 8 ตัวอักษร 9 ตัวอักษร 7 ตัวอักษร - ระดับต่ำสุด (ดูตาราง) 4 3 3 4 - 3, 4. ตัวอักษรที่ไม่ตรงกัน LDN ไม่มี D R - จำนวนตัวอักษรที่ไม่ตรงกัน 3 ตัวอักษร 0 ตัวอักษร 1 ตัวอักษร 1 ตัวอักษร - 5. ระดับความคล้าย (6 ลบด้วยจำนวนตัวอักษรที่ไม่ตรงกัน) 6 - 3 = 3 6 - 0 = 6 6 - 1 = 5 6 - 1 = 5 - 6. ระดับความคล้าย ≥ ระดับต่ำสุด 3 < 4 — ไม่ผ่าน 6 ≥ 3 — ผ่าน 5 ≥ 3 — ผ่าน 5 ≥ 4 — ผ่าน -

ได้ข้อสรุปว่า ชื่อ "Harper" นั้นมีความคล้ายคลึงกับชื่อที่มีรหัสเป็น "HRPR" "HRPRD" และ "HRP" แต่ไม่คล้ายคลึงกับชื่อที่มีรหัสเป็น "LDN" และ "HBLTWNS"

 อ้างอิง 

 An Overview of The Issues Related to the use of Personal Identifiers, HSMD, Statistics Canada 
 การประยุกต์บนภาษา C#

หมวดหมู่:ขั้นตอนวิธี