java string similarity
v2.0.0
ห้องสมุดที่ใช้การวัดความเหมือนและระยะทางของสตริงที่แตกต่างกัน อัลกอริธึมหลายสิบรายการ (รวมถึงระยะการแก้ไขของ Levenshtein และพี่น้อง, Jaro-Winkler, ผลสืบเนื่องร่วมที่ยาวที่สุด, ความคล้ายคลึงโคไซน์ ฯลฯ ) ถูกนำมาใช้ในปัจจุบัน ตรวจสอบตารางสรุปด้านล่างเพื่อดูรายการทั้งหมด...
ใช้มาเวน:
<dependency>
<groupId>info.debatty</groupId>
<artifactId>java-string-similarity</artifactId>
<version>RELEASE</version>
</dependency>
หรือตรวจสอบการเผยแพร่
ไลบรารีนี้ต้องการ Java 8 หรือใหม่กว่า
ลักษณะสำคัญของอัลกอริธึมที่นำไปใช้แต่ละอันมีดังต่อไปนี้ คอลัมน์ "ต้นทุน" ให้การประมาณต้นทุนการคำนวณเพื่อคำนวณความคล้ายคลึงกันระหว่างสองสตริงที่มีความยาว m และ n ตามลำดับ
| ทำให้เป็นมาตรฐาน? | เมตริก? | พิมพ์ | ค่าใช้จ่าย | การใช้งานทั่วไป | ||
|---|---|---|---|---|---|---|
| เลเวนชไตน์ | ระยะทาง | เลขที่ | ใช่ | โอ(ม*น) 1 | ||
| เลเวนชไตน์ที่ทำให้เป็นมาตรฐาน | ระยะทาง ความคล้ายคลึงกัน | ใช่ | เลขที่ | โอ(ม*น) 1 | ||
| เลเวนชไตน์แบบถ่วงน้ำหนัก | ระยะทาง | เลขที่ | เลขที่ | โอ(ม*น) 1 | โอซีอาร์ | |
| ดาเมเรา-เลเวนชไตน์ 3 | ระยะทาง | เลขที่ | ใช่ | โอ(ม*น) 1 | ||
| การจัดตำแหน่งสตริงที่เหมาะสมที่สุด 3 | ระยะทาง | เลขที่ | เลขที่ | โอ(ม*น) 1 | ||
| จาโร-วิงเคลอร์ | ความคล้ายคลึงกัน ระยะทาง | ใช่ | เลขที่ | โอ(ม*น) | แก้ไขคำผิด | |
| ผลสืบเนื่องทั่วไปที่ยาวที่สุด | ระยะทาง | เลขที่ | เลขที่ | O(ม*น) 1,2 | ยูทิลิตี้ต่าง ๆ การกระทบยอด GIT | |
| ลำดับต่อมาที่ยาวที่สุดแบบเมตริก | ระยะทาง | ใช่ | ใช่ | O(ม*น) 1,2 | ||
| เอ็น-แกรม | ระยะทาง | ใช่ | เลขที่ | โอ(ม*น) | ||
| คิว-แกรม | ระยะทาง | เลขที่ | เลขที่ | ประวัติโดยย่อ | O(ม+น) | |
| ความคล้ายคลึงโคไซน์ | ความคล้ายคลึงกัน ระยะทาง | ใช่ | เลขที่ | ประวัติโดยย่อ | O(ม+น) | |
| ดัชนีแจ็คการ์ด | ความคล้ายคลึงกัน ระยะทาง | ใช่ | ใช่ | ชุด | O(ม+น) | |
| สัมประสิทธิ์โซเรนเซน-ลูกเต๋า | ความคล้ายคลึงกัน ระยะทาง | ใช่ | เลขที่ | ชุด | O(ม+น) | |
| แรตคลิฟฟ์-โอเบอร์สเฮลป์ | ความคล้ายคลึงกัน ระยะทาง | ใช่ | เลขที่ | - |
[1] ในไลบรารีนี้ ระยะทางแก้ไขของ Levenshtein, ระยะทาง LCS และพี่น้องของพวกเขาจะถูกคำนวณโดยใช้วิธี การเขียนโปรแกรมแบบไดนามิก ซึ่งมีต้นทุน O(mn) สำหรับระยะทางเลเวนชไทน์ บางครั้งอัลกอริทึมเรียกว่า อัลกอริทึมของวากเนอร์-ฟิสเชอร์ ("ปัญหาการแก้ไขสตริงต่อสตริง", 1974) อัลกอริธึมดั้งเดิมใช้เมทริกซ์ขนาด mxn เพื่อจัดเก็บระยะห่างของ Levenshtein ระหว่างคำนำหน้าสตริง
หากตัวอักษรมีจำกัด ก็เป็นไปได้ที่จะใช้ วิธีการของชาวรัสเซีย 4 คน (Arlazarov et al. "On Economic Construction of the Transitive closure of a directing Graph", 1970) เพื่อเร่งการคำนวณ สิ่งนี้เผยแพร่โดย Masek ในปี 1980 ("A Faster Algorithm Computing String Edit Distances") วิธีนี้จะแยกเมทริกซ์ออกเป็นบล็อกขนาด tx t แต่ละบล็อกที่เป็นไปได้จะถูกคำนวณล่วงหน้าเพื่อสร้างตารางการค้นหา ตารางการค้นหานี้สามารถใช้เพื่อคำนวณความคล้ายคลึงกันของสตริง (หรือระยะทาง) ในหน่วย O(nm/t) โดยปกติแล้ว t จะถูกเลือกเป็น log(m) ถ้า m > n ต้นทุนการคำนวณที่ได้จึงเป็น O(mn/log(m)) ยังไม่ได้ใช้วิธีนี้ (ยัง)
[2] ใน "ความยาวของลำดับย่อยร่วมสูงสุด" KS Larsen เสนออัลกอริทึมที่คำนวณความยาวของ LCS ในเวลา O(log(m).log(n)) แต่อัลกอริทึมมีข้อกำหนดหน่วยความจำ O(m.n²) และดังนั้นจึงไม่ได้นำมาใช้ที่นี่
[3] ระยะสายอักขระ Damerau-Levenshtein มีสองรูปแบบ: Damerau-Levenshtein ที่มีการขนย้ายที่อยู่ติดกัน (บางครั้งเรียกว่าระยะ Damerau–Levenshtein ไม่จำกัด) และการจัดตำแหน่งสายอักขระที่เหมาะสมที่สุด (บางครั้งเรียกว่าระยะการแก้ไขแบบจำกัด) สำหรับการจัดตำแหน่งสตริงที่เหมาะสมที่สุด จะแก้ไขสตริงย่อยไม่ได้มากกว่าหนึ่งครั้ง
แม้ว่าหัวข้ออาจดูเรียบง่าย แต่ก็มีอัลกอริธึมที่แตกต่างกันมากมายในการวัดความคล้ายคลึงหรือระยะทางของข้อความ ดังนั้นไลบรารีจึงกำหนดอินเทอร์เฟซบางส่วนเพื่อจัดหมวดหมู่
โดยทั่วไป อัลกอริธึมที่ใช้ NormalizedStringSimilarity ยังใช้ NormalizedStringDistance และความคล้ายคลึง = 1 - ระยะทาง แต่มีข้อยกเว้นบางประการ เช่น ความเหมือนและระยะทางของ N-Gram (คอนดราค)...
อินเทอร์เฟซ MetricStringDistance : ระยะทางบางส่วนคือระยะทางแบบเมตริก ซึ่งหมายความว่าตรวจสอบความไม่เท่าเทียมกันของสามเหลี่ยม d(x, y) <= d(x,z) + d(z,y) ตัวอย่างเช่น Levenshtein คือระยะทางแบบเมตริก แต่ NormalizedLevenshtein ไม่ใช่
อัลกอริธึมการค้นหาเพื่อนบ้านที่ใกล้ที่สุดและโครงสร้างการจัดทำดัชนีจำนวนมากอาศัยความไม่เท่าเทียมกันของสามเหลี่ยม คุณสามารถตรวจสอบ "การค้นหาความคล้ายคลึง แนวทางอวกาศเมตริก" โดย Zezula และคณะ สำหรับการสำรวจ สิ่งเหล่านี้ไม่สามารถใช้กับการวัดความคล้ายคลึงกันที่ไม่ใช่ตัวชี้วัด
อ่าน Javadoc สำหรับคำอธิบายโดยละเอียด
อัลกอริธึมบางตัวทำงานโดยการแปลงสตริงเป็นชุดของ n-gram (ลำดับของอักขระ n ตัว บางครั้งเรียกว่า k-shingles) ความคล้ายคลึงหรือระยะห่างระหว่างสายอักขระก็คือความคล้ายคลึงหรือระยะห่างระหว่างเซต
บางส่วนเช่น jaccard ถือว่าสตริงเป็นชุดของงูสวัด และไม่พิจารณาจำนวนการเกิดงูสวัดแต่ละอัน อย่างอื่น เช่น ความคล้ายคลึงโคไซน์ ทำงานโดยใช้สิ่งที่บางครั้งเรียกว่าโปรไฟล์ของสตริง ซึ่งจะพิจารณาจำนวนครั้งที่เกิดขึ้นของแต่ละมุงหลังคา
สำหรับอัลกอริธึมเหล่านี้ กรณีการใช้งานอื่นอาจเป็นไปได้เมื่อต้องจัดการกับชุดข้อมูลขนาดใหญ่:
ระยะห่างของ Levenshtein ระหว่างสองคำคือจำนวนขั้นต่ำของการแก้ไขอักขระตัวเดียว (การแทรก การลบ หรือการแทนที่) ที่จำเป็นในการเปลี่ยนคำหนึ่งเป็นอีกคำหนึ่ง
เป็นระยะทางสตริงเมตริก การใช้งานนี้ใช้การเขียนโปรแกรมแบบไดนามิก (อัลกอริธึม Wagner–Fischer) โดยมีข้อมูลเพียง 2 แถว ความต้องการพื้นที่คือ O(m) และอัลกอริทึมทำงานใน O(mn)
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
Levenshtein l = new Levenshtein ();
System . out . println ( l . distance ( "My string" , "My $tring" ));
System . out . println ( l . distance ( "My string" , "My $tring" ));
System . out . println ( l . distance ( "My string" , "My $tring" ));
}
}ระยะนี้คำนวณเป็นระยะทางเลเวนชไทน์หารด้วยความยาวของสตริงที่ยาวที่สุด ค่าผลลัพธ์จะอยู่ในช่วงเวลา [0.0 1.0] เสมอ แต่มันไม่ใช่เมตริกอีกต่อไป!
ความคล้ายคลึงกันคำนวณเป็น 1 - ระยะทางมาตรฐาน
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
NormalizedLevenshtein l = new NormalizedLevenshtein ();
System . out . println ( l . distance ( "My string" , "My $tring" ));
System . out . println ( l . distance ( "My string" , "My $tring" ));
System . out . println ( l . distance ( "My string" , "My $tring" ));
}
}การใช้งาน Levenshtein ที่ช่วยให้สามารถกำหนดน้ำหนักที่แตกต่างกันสำหรับการแทนที่อักขระที่แตกต่างกัน
โดยปกติอัลกอริทึมนี้ใช้สำหรับแอปพลิเคชันการรู้จำอักขระด้วยแสง (OCR) สำหรับ OCR ต้นทุนของการทดแทน P และ R จะต่ำกว่า ต้นทุนของการทดแทน P และ M เช่น เนื่องจากจากและ OCR มุมมอง P คล้ายกับ R
นอกจากนี้ยังใช้สำหรับการแก้ไขอัตโนมัติของการพิมพ์ด้วยแป้นพิมพ์อีกด้วย ในที่นี้ค่าใช้จ่ายในการทดแทน E และ R นั้นต่ำกว่า เช่น เนื่องจากสิ่งเหล่านี้อยู่ติดกันบนแป้นพิมพ์ AZERTY หรือ QWERTY ดังนั้นความน่าจะเป็นที่ผู้ใช้พิมพ์อักขระผิดจึงสูงกว่า
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
WeightedLevenshtein wl = new WeightedLevenshtein (
new CharacterSubstitutionInterface () {
public double cost ( char c1 , char c2 ) {
// The cost for substituting 't' and 'r' is considered
// smaller as these 2 are located next to each other
// on a keyboard
if ( c1 == 't' && c2 == 'r' ) {
return 0.5 ;
}
// For most cases, the cost of substituting 2 characters
// is 1.0
return 1.0 ;
}
});
System . out . println ( wl . distance ( "String1" , "Srring2" ));
}
}เช่นเดียวกับเลเวนชไทน์ ระยะทางดาเมเรา-เลเวนชไทน์ที่มีการขนย้าย (บางครั้งเรียกว่าระยะทางดาเมเรา-เลเวนชไทน์แบบไม่จำกัด) คือจำนวนการดำเนินการขั้นต่ำที่จำเป็นในการแปลงสตริงหนึ่งไปเป็นอีกสตริงหนึ่ง โดยที่การดำเนินการถูกกำหนดเป็นการแทรก การลบ หรือการแทนที่ อักขระตัวเดียว หรือ การขนย้ายของอักขระสองตัวที่อยู่ติดกัน
มันเคารพอสมการของสามเหลี่ยม และดังนั้นจึงเป็นระยะทางหน่วยเมตริก
อย่าสับสนกับระยะการจัดตำแหน่งสตริงที่เหมาะสมที่สุด ซึ่งเป็นส่วนขยายที่ไม่สามารถแก้ไขสตริงย่อยได้มากกว่าหนึ่งครั้ง
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
Damerau d = new Damerau ();
// 1 substitution
System . out . println ( d . distance ( "ABCDEF" , "ABDCEF" ));
// 2 substitutions
System . out . println ( d . distance ( "ABCDEF" , "BACDFE" ));
// 1 deletion
System . out . println ( d . distance ( "ABCDEF" , "ABCDE" ));
System . out . println ( d . distance ( "ABCDEF" , "BCDEF" ));
System . out . println ( d . distance ( "ABCDEF" , "ABCGDEF" ));
// All different
System . out . println ( d . distance ( "ABCDEF" , "POIU" ));
}
}จะผลิต:
1.0
2.0
1.0
1.0
1.0
6.0
ตัวแปรการจัดตำแหน่งสตริงที่เหมาะสมที่สุดของ Damerau–Levenshtein (บางครั้งเรียกว่าระยะการแก้ไขที่จำกัด) คำนวณจำนวนการดำเนินการแก้ไขที่จำเป็นเพื่อทำให้สตริงเท่ากันภายใต้เงื่อนไขที่ ไม่มีการแก้ไขสตริงย่อยมากกว่าหนึ่งครั้ง ในขณะที่ Damerau–Levenshtein ที่แท้จริงจะไม่แสดงเช่นนั้น ข้อ จำกัด ความแตกต่างจากอัลกอริทึมสำหรับระยะทางเลเวนชไทน์คือการเพิ่มการเกิดซ้ำหนึ่งครั้งสำหรับการดำเนินการขนย้าย
โปรดทราบว่าสำหรับระยะการจัดแนวสตริงที่เหมาะสมที่สุด ความไม่เท่าเทียมกันของสามเหลี่ยมจะไม่คงอยู่ ดังนั้นจึงไม่ใช่หน่วยวัดที่แท้จริง
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
OptimalStringAlignment osa = new OptimalStringAlignment ();
System . out . println ( osa . distance ( "CA" , "ABC" ));;
}
}จะผลิต:
3.0
Jaro-Winkler เป็นระยะทางแก้ไขสตริงที่พัฒนาขึ้นในพื้นที่ของการเชื่อมโยงบันทึก (การตรวจจับซ้ำ) (Winkler, 1990) การวัดระยะทาง Jaro–Winkler ได้รับการออกแบบและเหมาะที่สุดสำหรับสตริงสั้นๆ เช่น ชื่อบุคคล และเพื่อตรวจจับการพิมพ์ผิดของการขนย้าย
Jaro-Winkler คำนวณความคล้ายคลึงกันระหว่าง 2 สตริง และค่าที่ส่งคืนจะอยู่ในช่วงเวลา [0.0, 1.0] มันเป็น (โดยประมาณ) รูปแบบหนึ่งของ Damerau-Levenshtein โดยที่การขนย้ายของอักขระปิด 2 ตัวถือว่ามีความสำคัญน้อยกว่าการขนย้ายของอักขระ 2 ตัวที่อยู่ห่างจากกัน Jaro-Winkler ลงโทษการเพิ่มเติมหรือการเปลี่ยนตัวที่ไม่สามารถแสดงเป็นการขนย้ายได้
ระยะทางคำนวณเป็น 1 - ความคล้ายคลึงกันของจาโร-วิงเคลอร์
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
JaroWinkler jw = new JaroWinkler ();
// substitution of s and t
System . out . println ( jw . similarity ( "My string" , "My tsring" ));
// substitution of s and n
System . out . println ( jw . similarity ( "My string" , "My ntrisg" ));
}
}จะผลิต:
0.9740740656852722
0.8962963223457336
ปัญหาลำดับย่อยร่วมที่ยาวที่สุด (LCS) ประกอบด้วยการค้นหาลำดับย่อยที่ยาวที่สุดร่วมของลำดับสองลำดับ (หรือมากกว่า) มันแตกต่างจากปัญหาในการค้นหาสตริงย่อยทั่วไป: ต่างจากสตริงย่อยตรงที่ลำดับย่อยไม่จำเป็นต้องมีตำแหน่งที่ต่อเนื่องกันภายในลำดับดั้งเดิม
มันถูกใช้โดยยูทิลิตี้ diff, โดย Git สำหรับการกระทบยอดการเปลี่ยนแปลงหลายรายการ ฯลฯ
ระยะห่าง LCS ระหว่างสตริง X (ความยาว n) และ Y (ความยาว m) คือ n + m - 2 |LCS(X, Y)| นาที = 0 สูงสุด = n + ม
ระยะทาง LCS เทียบเท่ากับระยะทาง Levenshtein เมื่ออนุญาตให้มีการแทรกและการลบเท่านั้น (ไม่มีการทดแทน) หรือเมื่อต้นทุนของการเปลี่ยนตัวเป็นสองเท่าของต้นทุนของการแทรกหรือการลบ
คลาสนี้ใช้วิธีการเขียนโปรแกรมแบบไดนามิก ซึ่งมีความต้องการพื้นที่ O(mn) และต้นทุนการคำนวณ O(mn)
ใน "ความยาวของลำดับย่อยร่วมสูงสุด" KS Larsen เสนออัลกอริทึมที่คำนวณความยาวของ LCS ในเวลา O(log(m).log(n)) แต่อัลกอริทึมมีข้อกำหนดหน่วยความจำ O(m.n²) และดังนั้นจึงไม่ได้นำมาใช้ที่นี่
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
LongestCommonSubsequence lcs = new LongestCommonSubsequence ();
// Will produce 4.0
System . out . println ( lcs . distance ( "AGCAT" , "GAC" ));
// Will produce 1.0
System . out . println ( lcs . distance ( "AGCAT" , "AGCT" ));
}
}การวัดระยะทางอิงตามลำดับย่อยร่วมที่ยาวที่สุด จากบันทึกย่อ "เมตริกสตริงแบบอิง LCS" โดย Daniel Bakkelund http://heim.ifi.uio.no/~danielry/StringMetric.pdf
ระยะทางคำนวณเป็น 1 - |LCS(s1, s2)| / สูงสุด(|s1|, |s2|)
public class MyApp {
public static void main ( String [] args ) {
info . debatty . java . stringsimilarity . MetricLCS lcs =
new info . debatty . java . stringsimilarity . MetricLCS ();
String s1 = "ABCDEFG" ;
String s2 = "ABCDEFHJKL" ;
// LCS: ABCDEF => length = 6
// longest = s2 => length = 10
// => 1 - 6/10 = 0.4
System . out . println ( lcs . distance ( s1 , s2 ));
// LCS: ABDF => length = 4
// longest = ABDEF => length = 5
// => 1 - 4 / 5 = 0.2
System . out . println ( lcs . distance ( "ABDEF" , "ABDIF" ));
}
}ระยะทาง N-Gram ที่ทำให้เป็นมาตรฐานตามที่กำหนดโดย Kondrak, "ความคล้ายคลึงและระยะทาง N-Gram", การประมวลผลสตริงและการดึงข้อมูล, หมายเหตุการบรรยายในวิทยาการคอมพิวเตอร์ เล่ม 3772, 2005, หน้า 115-126
http://webdocs.cs.ualberta.ca/~kondrak/papers/spire05.pdf
อัลกอริทึมใช้การลงท้ายด้วยอักขระพิเศษ 'n' เพื่อเพิ่มน้ำหนักของอักขระตัวแรก การทำให้เป็นมาตรฐานทำได้โดยการหารคะแนนความคล้ายคลึงทั้งหมดด้วยความยาวดั้งเดิมของคำที่ยาวที่สุด
ในรายงานนี้ Kondrak ยังให้คำจำกัดความของการวัดความคล้ายคลึงซึ่งยังไม่ได้นำมาใช้ (ยังไม่ได้ใช้)
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
// produces 0.583333
NGram twogram = new NGram ( 2 );
System . out . println ( twogram . distance ( "ABCD" , "ABTUIO" ));
// produces 0.97222
String s1 = "Adobe CreativeSuite 5 Master Collection from cheap 4zp" ;
String s2 = "Adobe CreativeSuite 5 Master Collection from cheap d1x" ;
NGram ngram = new NGram ( 4 );
System . out . println ( ngram . distance ( s1 , s2 ));
}
}อัลกอริธึมบางตัวทำงานโดยการแปลงสตริงเป็นชุดของ n-gram (ลำดับของอักขระ n ตัว บางครั้งเรียกว่า k-shingles) ความคล้ายคลึงหรือระยะห่างระหว่างสายอักขระก็คือความคล้ายคลึงหรือระยะห่างระหว่างเซต
ค่าใช้จ่ายในการคำนวณความคล้ายคลึงและระยะทางเหล่านี้ส่วนใหญ่จะถูกกำหนดโดย k-shingling (การแปลงสตริงเป็นลำดับของอักขระ k) ดังนั้น โดยทั่วไปแล้วจะมีกรณีการใช้งานสองกรณีสำหรับอัลกอริทึมเหล่านี้:
คำนวณระยะห่างระหว่างสตริงโดยตรง:
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
QGram dig = new QGram ( 2 );
// AB BC CD CE
// 1 1 1 0
// 1 1 0 1
// Total: 2
System . out . println ( dig . distance ( "ABCD" , "ABCE" ));
}
}หรือสำหรับชุดข้อมูลขนาดใหญ่ ให้คำนวณโปรไฟล์ของสตริงทั้งหมดล่วงหน้า ความคล้ายคลึงกันสามารถคำนวณระหว่างโปรไฟล์ได้:
import info . debatty . java . stringsimilarity . KShingling ;
import info . debatty . java . stringsimilarity . StringProfile ;
/**
* Example of computing cosine similarity with pre-computed profiles.
*/
public class PrecomputedCosine {
public static void main ( String [] args ) throws Exception {
String s1 = "My first string" ;
String s2 = "My other string..." ;
// Let's work with sequences of 2 characters...
Cosine cosine = new Cosine ( 2 );
// Pre-compute the profile of strings
Map < String , Integer > profile1 = cosine . getProfile ( s1 );
Map < String , Integer > profile2 = cosine . getProfile ( s2 );
// Prints 0.516185
System . out . println ( cosine . similarity ( profile1 , profile2 ));
}
}โปรดทราบว่าวิธีนี้ใช้ได้เฉพาะในกรณีที่ใช้วัตถุ KShingling เดียวกันเพื่อแยกวิเคราะห์สตริงอินพุตทั้งหมด !
ระยะทาง Q-gram ตามที่กำหนดโดย Ukkonen ใน "การจับคู่สตริงโดยประมาณกับ q-gram และการจับคู่สูงสุด" http://www.sciencedirect.com/science/article/pii/0304397592901434
ระยะห่างระหว่างสองสตริงถูกกำหนดให้เป็นบรรทัดฐาน L1 ของความแตกต่างของโปรไฟล์ (จำนวนที่เกิดขึ้นของแต่ละ n-กรัม): SUM( |V1_i - V2_i| ) ระยะทาง Q-gram เป็นขอบเขตล่างของระยะทาง Levenshtein แต่สามารถคำนวณได้ในหน่วย O(m + n) โดยที่ Levenshtein ต้องการ O(mn)
ความคล้ายคลึงกันระหว่างสองสายคือโคไซน์ของมุมระหว่างการแทนเวกเตอร์ทั้งสองนี้ และคำนวณเป็น V1 V2 / (|V1| * |V2|)
ระยะทางคำนวณเป็น 1 - ความคล้ายคลึงโคไซน์
เช่นเดียวกับระยะทาง Q-Gram สตริงอินพุตจะถูกแปลงเป็นชุดของ n-gram ในตอนแรก (ลำดับของอักขระ n ตัว หรือที่เรียกว่า k-shingles) แต่คราวนี้ไม่ได้คำนึงถึงภาวะเชิงการนับของ n-gram แต่ละตัว แต่ละสตริงอินพุตเป็นเพียงชุดของ n-gram ดัชนี Jaccard จะถูกคำนวณเป็น |V1 ระหว่าง V2| / |V1 ยูเนี่ยน V2|
ระยะทางคำนวณเป็น 1 - ความคล้ายคลึงกัน ดัชนี Jaccard คือระยะเมตริก
คล้ายกับดัชนี Jaccard แต่คราวนี้ความคล้ายคลึงกันคำนวณเป็น 2 * |V1 ระหว่าง V2| / (|V1| + |V2|)
ระยะทางคำนวณเป็น 1 - ความคล้ายคลึงกัน
Ratcliff/Obershelp Pattern Recognition หรือที่รู้จักกันในชื่อ Gestalt Pattern Matching เป็นอัลกอริธึมการจับคู่สตริงสำหรับระบุความคล้ายคลึงกันของสองสตริง ได้รับการพัฒนาในปี 1983 โดย John W. Ratcliff และ John A. Obershelp และตีพิมพ์ใน Dr. Dobb's Journal ในเดือนกรกฎาคม 1988
Ratcliff/Obershelp คำนวณความคล้ายคลึงกันระหว่าง 2 สตริง และค่าที่ส่งคืนจะอยู่ในช่วงเวลา [0.0, 1.0]
ระยะทางคำนวณเป็น 1 - ความคล้ายคลึงกันของแรตคลิฟฟ์/โอเบอร์สช่วย
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
RatcliffObershelp ro = new RatcliffObershelp ();
// substitution of s and t
System . out . println ( ro . similarity ( "My string" , "My tsring" ));
// substitution of s and n
System . out . println ( ro . similarity ( "My string" , "My ntrisg" ));
}
}จะผลิต:
0.8888888888888888
0.7777777777777778
SIFT4 เป็นอัลกอริธึมระยะทางสตริงสำหรับวัตถุประสงค์ทั่วไปที่ได้รับแรงบันดาลใจจาก JaroWinkler และ Longest Common Subsequence ได้รับการพัฒนาเพื่อสร้างการวัดระยะทางที่ใกล้เคียงกับการรับรู้ของมนุษย์เกี่ยวกับระยะทางของเชือกมากที่สุด ดังนั้นจึงคำนึงถึงองค์ประกอบต่างๆ เช่น การแทนที่อักขระ ระยะห่างของอักขระ ลำดับย่อยร่วมที่ยาวที่สุด เป็นต้น ได้รับการพัฒนาโดยใช้การทดสอบเชิงทดลอง และไม่มีพื้นฐานทางทฤษฎี
import info.debatty.java.stringsimilarity.experimental.Sift4;
public class MyApp {
public static void main(String[] args) {
String s1 = "This is the first string";
String s2 = "And this is another string";
Sift4 sift4 = new Sift4();
sift4.setMaxOffset(5);
double expResult = 11.0;
double result = sift4.distance(s1, s2);
assertEquals(expResult, result, 0.0);
}
}
ใช้ java-string-similarity ในโปรเจ็กต์ของคุณและต้องการให้กล่าวถึงที่นี่หรือไม่ อย่าลังเลที่จะวางสายฉัน!
