ระยะทางจาโร-วิงเคลอร์

ระยะทางจาโร-วิงเคลอร์ (อังกฤษ: Jaro–Winkler distance) คือวิธีการแบบหนึ่งที่ใช้วัดความเหมือนกันระหว่างสองสายอักขระจากจำนวนตัวอักษรร่วม โดย วิลเลียมส วิงเคลอร์ (William Winkler) ได้นำวิธีการเปรียบเทียบสายอักขระแบบระยะทางจาโร ที่ แมททิว จาโร (Matthew Jaro) ได้นำเสนอขึ้น มาปรับปรุงเพิ่มเติม จึงเรียกว่าระยะทางจาโร-วิงเคลอร์ โดยค่าที่ได้จากวิธีวัดแบบระยะทางจาโร-วิงเคลอร์ จะมีค่าตั้งแต่ 0 (สายอักขระทั้งสองไม่มีตัวใดตรงกันเลย) ถึง 1 (สายอักขระทั้งสองตรงกันทุกตัว)

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

นิยาม

ให้ ${\displaystyle d_{j}}$  คือระยะทางจาโร ของสายอักขระสองสาย จะได้

${\displaystyle d_{j}={\frac {1}{3}}\left({\frac {c}{m}}+{\frac {c}{n}}+{\frac {c-t}{m}}\right)}$ 

• ${\displaystyle m}$  คือความยาวของสายอักขระสายแรก
• ${\displaystyle n}$  คือความยาวของสายอักขระสายที่สอง
• ${\displaystyle c}$  คือจำนวนคู่ของตัวอักษรที่ตรงกัน
• ${\displaystyle t}$  คือจำนวนเต็มครึ่งหนึ่ง ของคู่อักษรที่ตรงกันที่ต้องเปลี่ยนลำดับ

หากสายอักขระสองสาย มีตัวอักษรที่เหมือนกันแต่ตำแหน่งไม่ตรงกัน จะถือว่าอักษรนั้นตรงกัน ถ้าระยะห่างระหว่างอักษรที่เหมือนกันของอักขระสองสาย มีค่าไม่เกิน r โดยที่ ${\displaystyle r=\left\lfloor {\frac {\max(m,n)}{2}}\right\rfloor -1}$ 

ตัวอย่างเช่น การเทียบ CRATE กับ TRACE ระยะห่างระหว่างตัวอักษรสูงสุดที่ยังถือว่าตรงกันคือ (5/2)-1 = 1.5 จะเห็นว่ามีเพียงตัวอักษร ‘R’ ‘A’ ‘E’ เท่านั้นที่อักษรตรงกัน ถึงแม้ว่า ‘C’ และ ‘T’ จะปรากฏที่สายอักขระทั้งสอง แต่ระยะห่างของ ‘C’ ระหว่างสายอักขระสองสายมีค่าเกิน 1 (สายอักขระแรก C อยู่ตำแหน่งที่ 1 สายอักขระที่สอง C อยู่ที่ตำแหน่งที่ 4 ดังนั้นห่างกัน 4 – 1 = 3 ซึ่งเกิน r) จึงไม่ถือว่าตรงกัน สำหรับอักษร ‘T’ ก็เช่นเดียวกัน ดังนั้น c จึงมีค่าเท่ากับ 3 และ t = 0 (จำนวนอักษรที่ตรงกันคือ 3 ซึ่งอักษรที่ตรงกันทั้งสามนี้ ไม่มีการสลับตำแหน่งกัน) กรณี DwAyNE เทียบกับ DuANE จะเห็นว่าคู่ของอักษรที่ตรงกันมีตำแหน่งเรียงกันตามลำดับเหมือนกันทั้งสองสายคือ D-A-N-E ดังนั้นจึงไม่มีตำแหน่งที่ต้องต้องเปลี่ยนลำดับ t จึงเท่ากับ 0

ให้ ${\displaystyle d_{w}}$  คือระยะทางจาโร-วิงเคลอร์

${\displaystyle d_{w}=d_{j}+({\frac {\ell }{10}}(1-d_{j}))}$ 

• ${\displaystyle d_{j}}$  คือระยะทางจาโร สำหรับสายอักขระสองสาย
• ${\displaystyle \ell }$  คือความยาวของอักขระด้านหน้าที่ตรงกัน เริ่มจากตำแหน่งแรกจนถึงตำแหน่งสุดท้ายที่ตรงกัน โดยค่าที่ได้จะต้องไม่เกิน 4

ตัวอย่าง

ให้ ${\displaystyle m}$  แทนความยาวของสายอักขระ MARTHA และ ${\displaystyle n}$  แทนความยาวของสายอักขระ MARHTA จะได้

• ${\displaystyle c=6}$ 
• ${\displaystyle m=6}$ 
• ${\displaystyle n=6}$ 
• คู่ของตัวอักษรที่ตรงกัน (M, A, R, T, H, A) (M, A, R, H, T, A)

อักษรที่ตรงกัน 6 ตัว มีอักษรสองตัวที่ไม่ได้เรียงกันตามลำดับ คืออักษรตำแหน่งที่ 4 และ 5 ดังนั้น ${\displaystyle t={\frac {2}{2}}=1}$ 

จะได้ค่าระยะทางจาโร

${\displaystyle d_{j}={\frac {1}{3}}\left({\frac {6}{6}}+{\frac {6}{6}}+{\frac {6-1}{6}}\right)=0.944}$ 

มี 3 อักขระแรกที่เข้ากันคือ (M, A, R) ดังนั้น ${\displaystyle \ell =3}$ 

จะได้ค่าระยะทางจาโร-วิงเคลอร์

${\displaystyle d_{w}=0.944+({\frac {3}{10}}(1-0.944))=0.961}$ 

ให้ ${\displaystyle m}$  แทนความยาวของสายอักขระ JONES และ ${\displaystyle n}$  แทนความยาวของสายอักขระ JOHNSON จะได้

• ${\displaystyle c=4}$ 
• ${\displaystyle m=5}$ 
• ${\displaystyle n=7}$ 
• คู่ของตัวอักษรที่ตรงกัน (J, O, N, S) (J, O, N, S)

อักษรที่ตรงกันทั้ง 4 ตัว มีตำแหน่งเรียงกันตามลำดับเหมือนกันทั้งสองสายอักขระ ดังนั้น ${\displaystyle t=0}$ 

จะได้ค่าระยะทางจาโร

${\displaystyle d_{j}={\frac {1}{3}}\left({\frac {4}{5}}+{\frac {4}{6}}+{\frac {4-0}{4}}\right)=0.790}$ 

มี 2 อักขระแรกที่เข้ากันคือ (J, O) ดังนั้น ${\displaystyle \ell =2}$ 

จะได้ค่าระยะทางจาโร-วิงเคลอร์

${\displaystyle d_{w}=0.790+({\frac {2}{10}}(1-0.790))=0.832}$ 

ให้ ${\displaystyle m}$  แทนความยาวของสายอักขระ DWAYNE และ ${\displaystyle n}$  แทนความยาวของสายอักขระ DUANE จะได้

• ${\displaystyle c=4}$ 
• ${\displaystyle m=6}$ 
• ${\displaystyle n=5}$ 
• คู่ของตัวอักษรที่ตรงกัน (D, A, N, E) (D, A, N, E)

อักษรที่ตรงกันทั้ง 4 ตัว มีตำแหน่งเรียงกันตามลำดับเหมือนกันทั้งสองสายอักขระ ดังนั้น ${\displaystyle t=0}$ 

จะได้ค่าระยะทางจาโร

${\displaystyle d_{j}={\frac {1}{3}}\left({\frac {4}{6}}+{\frac {4}{5}}+{\frac {4-0}{4}}\right)=0.822}$ 

มีเพียงอักขระแรกที่เข้ากัน คือ (D) ดังนั้น ${\displaystyle \ell =1}$ 

จะได้ค่าระยะทางจาโร-วิงเคลอร์

${\displaystyle d_{w}=0.822+({\frac {1}{10}}(1-0.822))=0.84}$ 

ให้ ${\displaystyle m}$  แทนความยาวของสายอักขระ DIXON และ ${\displaystyle n}$  แทนความยาวของสายอักขระ DICKSONX จะได้

• ${\displaystyle r=\left\lfloor {\frac {8}{2}}\right\rfloor -1=3}$ 
• ${\displaystyle c=4}$ 
• ${\displaystyle m=5}$ 
• ${\displaystyle n=8}$ 
• คู่ของตัวอักษรที่ตรงกัน (D, I, O, N) (D, I, O, N)

อักษรที่ตรงกันทั้ง 4 ตัว มีตำแหน่งเรียงกันตามลำดับเหมือนกันทั้งสองสายอักขระ ดังนั้น ${\displaystyle t=0}$  สำหรับอักษร X ในสายอักขระไม่นำมาพิจาณา เนื่องจากระยะห่างของ X ระหว่างสายอักขระสองสายมีค่าเกิน r

จะได้ค่าระยะทางจาโร

${\displaystyle d_{j}={\frac {1}{3}}\left({\frac {4}{5}}+{\frac {4}{8}}+{\frac {4-0}{4}}\right)=0.767}$ 

มี 2 อักขระแรกที่เข้ากันคือ (D, I) ดังนั้น ${\displaystyle \ell =2}$ 

จะได้ค่าระยะทางจาโร-วิงเคลอร์

${\displaystyle d_{w}=0.767+({\frac {2}{10}}(1-0.767))=0.813}$ 

ดูเพิ่ม

• ระยะทางแฮมมิง
• การตรวจจับและแก้ไขความผิดพลาด
• ขั้นตอนวิธีสายอักขระ (en:String algorithms)

อ้างอิง

• Jaro, M. A. (1989). "Advances in record linkage methodology as applied to the 1985 census of Tampa Florida". Journal of the American Statistical Society. 84 (406): 414–20.
• Jaro, M. A. (1995). "Probabilistic linkage of large public health data file". Statistics in Medicine. 14 (5–7): 491–8. doi:10.1002/sim.4780140510. PMID 7792443.
• Winkler, W. E. (1990). "String Comparator Metrics and Enhanced Decision Rules in the Fellegi-Sunter Model of Record Linkage" (PDF). Proceedings of the Section on Survey Research Methods. American Statistical Association: 354–359.
• Winkler, W. E. (2006). "Overview of Record Linkage and Current Research Directions" (PDF). Research Report Series, RRS.

แหล่งข้อมูลอื่น

• Implementation & documentation in Java LingPipe. Features extensive comparison with the original strcmp.c implementation.
• PHP implementation released under GPLv3.0