การจับคู่รูปแบบเกสตั ลต์^{[ 1 ]}หรือการจดจำรูปแบบแรตคลิฟฟ์/โอเบอร์สเฮลป์ [ ^{2 ] เป็น}อัลกอริทึมการจับคู่สตริงเพื่อกำหนดความคล้ายคลึงกันของสตริงสองสตริงพัฒนาขึ้นในปี 1983 โดยจอห์น ดับเบิลยู. แรตคลิฟฟ์ และจอห์น เอ. โอเบอร์สเฮลป์และตีพิมพ์ในวารสารดร.ด็อบบ์ในเดือนกรกฎาคม 1988 ^{[ 2 ]}

ความคล้ายคลึงกันของสตริงสองสตริงจะถูกกำหนดโดยสูตรนี้: สองเท่าของจำนวนอักขระ ที่ตรงกัน หารด้วยจำนวนอักขระทั้งหมดของทั้งสองสตริง อักขระที่ตรงกันจะถูกกำหนดให้เป็นสตริงย่อยร่วมที่ยาวที่สุด^{[ 3 ]}บวกกับจำนวนอักขระที่ตรงกันในบริเวณที่ไม่ตรงกันทั้งสองด้านของสตริงย่อยร่วมที่ยาวที่สุดแบบเรียกซ้ำ : ^{[ 2 ] [ 4 ]}${\displaystyle S_{1}}$${\displaystyle S_{2}}$${\displaystyle K_{m}}$

${\displaystyle D_{ro}={\frac {2K_{m}}{|S_{1}|+|S_{2}|}}}$

โดยที่ค่าตัวชี้วัดความคล้ายคลึงสามารถมีค่าได้ระหว่างศูนย์ถึงหนึ่ง:

${\displaystyle 0\leq D_{ro}\leq 1}$

ค่า 1 หมายถึงการจับคู่กันอย่างสมบูรณ์ของทั้งสองสตริง ในขณะที่ค่า 0 หมายถึงไม่มีการตรงกันเลย แม้แต่ตัวอักษรเดียวก็ไม่มีเหมือนกัน

อักขระที่ใช้ในการจับคู่แบบ Ratcliff/Obershelp อาจแตกต่างกันอย่างมากจากลำดับย่อยร่วมที่ยาวที่สุดของสตริงที่กำหนด ตัวอย่างเช่นและมีสตริงย่อยร่วมที่ยาวที่สุดเพียงสตริงเดียว และไม่มีอักขระร่วมทางด้านขวาของการปรากฏ และเช่นเดียวกันทางด้านซ้าย ทำให้ได้อย่างไรก็ตาม ลำดับย่อยร่วมที่ยาวที่สุดของและคือโดยมีความยาวรวม${\displaystyle S_{1}=q\;ccccc\;r\;ddd\;s\;bbbb\;t\;eee\;u}$${\displaystyle S_{2}=v\;ddd\;w\;bbbb\;x\;eee\;y\;ccccc\;z}$${\displaystyle ccccc}$${\displaystyle K_{m}=5}$${\displaystyle S_{1}}$${\displaystyle S_{2}}$${\displaystyle (ddd)\;(bbbb)\;(eee)}$${\displaystyle 10}$

ไลบรารีPythondifflibซึ่งเปิดตัวในเวอร์ชัน 2.1 ^{[ 1 ]}ใช้ขั้นตอนวิธีที่คล้ายคลึงกันซึ่งมีมาก่อนขั้นตอนวิธี Ratcliff-Obershelp เนื่องจากพฤติกรรมรันไทม์ที่ไม่เหมาะสมของเมตริกความคล้ายคลึงนี้ จึงได้มีการนำวิธีการสามวิธีมาใช้ สองวิธีนั้นให้ค่าขอบเขตบนในเวลาการทำงานที่เร็วกว่า^{[ 1 ]}ตัวแปรที่เร็วที่สุดจะเปรียบเทียบเฉพาะความยาวของสตริงย่อยสองสตริงเท่านั้น: ^{[ 6 ]}

${\displaystyle D_{rqr}={\frac {2\cdot \min(|S1|,|S2|)}{|S1|+|S2|}}}$,

ขอบเขตบนที่สองคำนวณจากผลรวมของอักขระที่ใช้ทั้งหมดซึ่งปรากฏอยู่ในสตริงทั้งสอง หารด้วยความยาวของสตริงทั้งสอง แต่จะไม่พิจารณาลำดับของอักขระ${\displaystyle S_{1}}$${\displaystyle S_{2}}$

${\displaystyle D_{qr}={\frac {2\cdot {\big |}\{\!\vert S1\vert \!\}\cap \{\!\vert S2\vert \!\}{\big |}}{|S1|+|S2|}}}$

# การใช้งาน DQR ใน Python import collectionsdef quick_ratio ( s1 : str , s2 : str ) -> float : """คืนค่าขอบเขตบนของ ratio() อย่างรวดเร็ว""" length = len ( s1 ) + len ( s2 )ถ้าความยาวไม่ตรงกันให้คืนค่า1.0intersect = ( collections.Counter ( s1 ) & collections.Counter ( s2 ) ) matches = sum ( intersect.values ( ) ) return 2.0 * matches / length​​​

โดยทั่วไปแล้วสิ่งต่อไปนี้ใช้ได้:

${\displaystyle 0\leq D_{ro}\leq D_{qr}\leq D_{rqr}\leq 1}$และ

${\displaystyle 0\leq K_{m}\leq |\{\!\vert S1\vert \!\}\cap \{\!\vert S2\vert \!\}{\big |}\leq \min(|S1|,|S2|)\leq {\frac {|S1|+|S2|}{2}}}$.

• แรตคลิฟฟ์, จอห์น ดับเบิลยู.; เมตเซเนอร์, เดวิด (กรกฎาคม 1988) "การจับคู่รูปแบบ: แนวทางเกสตัลต์" บันทึกของดร. ด็อบบ์ (46)

• การจับคู่รูปแบบ