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