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

จากวิกิพีเดีย สารานุกรมเสรี

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

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

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

ขั้นตอนวิธี[แก้]

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

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

ขั้นตอนเข้ารหัส[แก้]

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

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

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

ขั้นตอนเปรียบเทียบ[แก้]

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

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

ตารางคำนวณระดับต่ำสุด[แก้]

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

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

ตัวอย่างการทำงาน[แก้]

Wikibooks
วิกิตำรา มีตัวอย่างการประยุกต์ในภาษา VB.NET:
en:Algorithm_implementation/String_searching/Match_Rating_Approach

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

การเข้ารหัส[แก้]

  1. "HARPER" เมื่อถูกตัดตัวอักษรที่เป็นสระทั้งหมดออกกลายเป็น "HRPR"
  2. ไม่มีพยัญชนะคู่ ไม่มีการเปลี่ยนแปลง ยังคงเป็น "HRPR"
  3. ผลลัพธ์ความยาวไม่เกิน 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"

อ้างอิง[แก้]