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

**การเข้าหาด้วยการจัดระดับคู่** หรือ **แมทช์เรตติงแอพโพรช** (อังกฤษ: **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#

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