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

การเข้าหาด้วยการจัดระดับคู่ หรือ แมทช์เรตติงแอพโพรช (อังกฤษ: 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 มาลบออกด้วยจำนวนของตัวอักษรที่ไม่ตรงกัน (จำนวนตัวอักษรที่เหลือของรหัสที่ยาวที่สุด) จะได้ระดับความคล้าย
 หากระดับความคล้ายมีค่าเท่ากับหรือมากกว่าระดับต่ำสุดก็จะถือว่าคำทั้งสองคำนั้นมีความคล้ายคลึงกัน

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

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

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

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

การเข้ารหัส 

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

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

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

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

อ้างอิง 

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

ขั้นตอนวิธี