java string similarity
v2.0.0
Perpustakaan yang menerapkan ukuran kesamaan string dan jarak yang berbeda. Selusin algoritme (termasuk jarak edit Levenshtein dan saudara kandungnya, Jaro-Winkler, Urutan Umum Terpanjang, kesamaan kosinus, dll.) saat ini diterapkan. Periksa tabel ringkasan di bawah ini untuk daftar lengkapnya...
Menggunakan pakar:
<dependency>
<groupId>info.debatty</groupId>
<artifactId>java-string-similarity</artifactId>
<version>RELEASE</version>
</dependency>
Atau periksa rilisnya.
Perpustakaan ini memerlukan Java 8 atau lebih baru.
Karakteristik utama dari setiap algoritma yang diimplementasikan disajikan di bawah ini. Kolom "biaya" memberikan perkiraan biaya komputasi untuk menghitung kesamaan antara dua string dengan panjang m dan n masing-masing.
| Dinormalisasi? | Metrik? | Jenis | Biaya | Penggunaan yang umum | ||
|---|---|---|---|---|---|---|
| Levenshtein | jarak | TIDAK | Ya | HAI(m*n) 1 | ||
| Levenshtein yang dinormalisasi | jarak kesamaan | Ya | TIDAK | HAI(m*n) 1 | ||
| Levenshtein tertimbang | jarak | TIDAK | TIDAK | HAI(m*n) 1 | OCR | |
| Damerau-Levenshtein 3 | jarak | TIDAK | Ya | HAI(m*n) 1 | ||
| Penyelarasan Senar Optimal 3 | jarak | TIDAK | TIDAK | HAI(m*n) 1 | ||
| Jaro-Winkler | kesamaan jarak | Ya | TIDAK | HAI(m*n) | koreksi kesalahan ketik | |
| Barisan Umum Terpanjang | jarak | TIDAK | TIDAK | HAI(m*n) 1,2 | utilitas diff, rekonsiliasi GIT | |
| Barisan Umum Terpanjang Metrik | jarak | Ya | Ya | HAI(m*n) 1,2 | ||
| N-Gram | jarak | Ya | TIDAK | HAI(m*n) | ||
| Q-Gram | jarak | TIDAK | TIDAK | Profil | HAI(m+n) | |
| Kesamaan kosinus | kesamaan jarak | Ya | TIDAK | Profil | HAI(m+n) | |
| Indeks Jaccard | kesamaan jarak | Ya | Ya | Mengatur | HAI(m+n) | |
| Koefisien Sorensen-Dice | kesamaan jarak | Ya | TIDAK | Mengatur | HAI(m+n) | |
| Ratcliff-Obershelp | kesamaan jarak | Ya | TIDAK | ? |
[1] Di perpustakaan ini, jarak edit Levenshtein, jarak LCS dan saudara kandungnya dihitung menggunakan metode pemrograman dinamis , yang memiliki biaya O(mn). Untuk jarak Levenshtein, algoritma ini kadang-kadang disebut algoritma Wagner-Fischer ("The string-to-string Correction Problem", 1974). Algoritma asli menggunakan matriks berukuran mxn untuk menyimpan jarak Levenshtein antara awalan string.
Jika alfabetnya terbatas, dimungkinkan untuk menggunakan metode empat orang Rusia (Arlazarov et al. "Tentang konstruksi ekonomi penutupan transitif grafik berarah", 1970) untuk mempercepat komputasi. Ini diterbitkan oleh Masek pada tahun 1980 ("A Faster Algorithm Computing String Edit Distances"). Metode ini membagi matriks menjadi blok-blok berukuran tx t. Setiap blok yang mungkin dihitung sebelumnya untuk menghasilkan tabel pencarian. Tabel pencarian ini kemudian dapat digunakan untuk menghitung kesamaan string (atau jarak) dalam O(nm/t). Biasanya t dipilih sebagai log(m) jika m > n. Dengan demikian, biaya komputasi yang dihasilkan adalah O(mn/log(m)). Metode ini belum diterapkan (belum).
[2] Dalam "Length of Maximal Common Subsequences", KS Larsen mengusulkan algoritma yang menghitung panjang LCS dalam waktu O(log(m).log(n)). Namun algoritme tersebut memiliki kebutuhan memori O(m.n²) dan karenanya tidak diterapkan di sini.
[3] Ada dua varian jarak string Damerau-Levenshtein: Damerau-Levenshtein dengan transposisi yang berdekatan (terkadang juga disebut jarak Damerau–Levenshtein tidak terbatas) dan Penyelarasan String Optimal (terkadang juga disebut jarak edit terbatas). Untuk Penyelarasan String Optimal, tidak ada substring yang dapat diedit lebih dari satu kali.
Meskipun topiknya mungkin tampak sederhana, ada banyak algoritma berbeda untuk mengukur kesamaan atau jarak teks. Oleh karena itu perpustakaan mendefinisikan beberapa antarmuka untuk mengkategorikannya.
Secara umum, algoritma yang mengimplementasikan NormalizedStringSimilarity juga mengimplementasikan NormalizedStringDistance, dan kesamaan = 1 - jarak. Namun ada beberapa pengecualian, seperti kesamaan dan jarak N-Gram (Kondrak)...
Antarmuka MetricStringDistance : Beberapa jarak sebenarnya merupakan jarak metrik, yang berarti verifikasi pertidaksamaan segitiga d(x, y) <= d(x,z) + d(z,y). Misalnya, Levenshtein adalah jarak metrik, namun NormalizedLevenshtein bukan.
Banyak algoritma pencarian tetangga terdekat dan struktur pengindeksan bergantung pada pertidaksamaan segitiga. Anda dapat memeriksa "Pencarian Kesamaan, Pendekatan Ruang Metrik" oleh Zezula dkk. untuk survei. Ini tidak dapat digunakan dengan ukuran kesamaan non-metrik.
Baca Javadoc untuk penjelasan rinci
Beberapa algoritme bekerja dengan mengubah string menjadi kumpulan n-gram (urutan n karakter, terkadang juga disebut k-shingles). Kesamaan atau jarak antar dawai maka persamaan atau jarak antar himpunan.
Beberapa di antaranya, seperti jaccard, menganggap string sebagai kumpulan sirap, dan tidak mempertimbangkan jumlah kemunculan setiap sirap. Lainnya, seperti kesamaan kosinus, bekerja menggunakan apa yang kadang-kadang disebut profil string, yang memperhitungkan jumlah kemunculan setiap sirap.
Untuk algoritme ini, kasus penggunaan lain dimungkinkan ketika menangani kumpulan data besar:
Jarak Levenshtein antara dua kata adalah jumlah minimum pengeditan satu karakter (penyisipan, penghapusan, atau penggantian) yang diperlukan untuk mengubah satu kata ke kata lainnya.
Ini adalah jarak string metrik. Implementasi ini menggunakan pemrograman dinamis (algoritma Wagner–Fischer), dengan hanya 2 baris data. Oleh karena itu, kebutuhan ruang adalah O(m) dan algoritma berjalan dalam 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" ));
}
}Jarak ini dihitung sebagai jarak levenshtein dibagi dengan panjang string terpanjang. Nilai yang dihasilkan selalu dalam interval [0,0 1,0] tetapi bukan merupakan metrik lagi!
Kesamaan dihitung sebagai 1 - jarak yang dinormalisasi.
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" ));
}
}Implementasi Levenshtein yang memungkinkan penentuan bobot berbeda untuk substitusi karakter berbeda.
Algoritma ini biasanya digunakan untuk aplikasi pengenalan karakter optik (OCR). Untuk OCR, biaya substitusi P dan R lebih rendah dibandingkan biaya substitusi P dan M misalnya karena dari sudut pandang OCR P mirip dengan R.
Ini juga dapat digunakan untuk koreksi otomatis pengetikan keyboard. Di sini biaya penggantian E dan R lebih rendah misalnya karena letaknya bersebelahan pada keyboard AZERTY atau QWERTY. Oleh karena itu kemungkinan pengguna salah mengetik karakter lebih tinggi.
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" ));
}
}Mirip dengan Levenshtein, jarak Damerau-Levenshtein dengan transposisi (terkadang juga disebut jarak Damerau-Levenshtein yang tidak dibatasi) adalah jumlah minimum operasi yang diperlukan untuk mengubah satu string ke string lainnya, di mana suatu operasi didefinisikan sebagai penyisipan, penghapusan, atau substitusi a karakter tunggal, atau transposisi dua karakter yang berdekatan .
Itu menghormati ketidaksetaraan segitiga, dan dengan demikian merupakan jarak metrik.
Hal ini berbeda dengan jarak penyelarasan string optimal, yang merupakan ekstensi di mana tidak ada substring yang dapat diedit lebih dari satu kali.
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" ));
}
}Akan menghasilkan:
1.0
2.0
1.0
1.0
1.0
6.0
Varian Penyelarasan String Optimal Damerau–Levenshtein (terkadang disebut jarak edit terbatas) menghitung jumlah operasi edit yang diperlukan untuk membuat string sama dengan syarat tidak ada substring yang diedit lebih dari satu kali , sedangkan Damerau–Levenshtein yang sebenarnya tidak menyajikan substring seperti itu. pembatasan. Perbedaan dari algoritma Levenshtein distance adalah penambahan satu perulangan untuk operasi transposisi.
Perhatikan bahwa untuk jarak penyelarasan string yang optimal, pertidaksamaan segitiga tidak berlaku sehingga ini bukan metrik yang sebenarnya.
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" ));;
}
}Akan menghasilkan:
3.0
Jaro-Winkler adalah jarak edit string yang dikembangkan di bidang hubungan rekaman (deteksi duplikat) (Winkler, 1990). Metrik jarak Jaro–Winkler dirancang dan paling cocok untuk string pendek seperti nama orang, dan untuk mendeteksi kesalahan ketik transposisi.
Jaro-Winkler menghitung kesamaan antara 2 string, dan nilai yang dikembalikan terletak pada interval [0.0, 1.0]. Ini (kira-kira) merupakan variasi Damerau-Levenshtein, dimana transposisi 2 karakter yang berdekatan dianggap kurang penting dibandingkan transposisi 2 karakter yang berjauhan. Jaro-Winkler menghukum penambahan atau penggantian yang tidak dapat dinyatakan sebagai transposisi.
Jarak dihitung sebagai 1 - kesamaan Jaro-Winkler.
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" ));
}
}akan menghasilkan:
0.9740740656852722
0.8962963223457336
Masalah barisan persekutuan terpanjang (LCS) terdiri dari mencari persamaan persekutuan terpanjang untuk dua (atau lebih) barisan. Ini berbeda dari masalah menemukan substring umum: tidak seperti substring, urutan berikutnya tidak perlu menempati posisi berurutan dalam urutan aslinya.
Ini digunakan oleh utilitas diff, oleh Git untuk merekonsiliasi beberapa perubahan, dll.
Jarak LCS antara senar X (panjang n) dan Y (panjang m) adalah n + m - 2 |LCS(X, Y)| min = 0 maks = n + m
Jarak LCS setara dengan jarak Levenshtein ketika hanya penyisipan dan penghapusan yang diperbolehkan (tidak ada substitusi), atau ketika biaya substitusi adalah dua kali lipat biaya penyisipan atau penghapusan.
Kelas ini mengimplementasikan pendekatan pemrograman dinamis, yang memiliki kebutuhan ruang O(mn), dan biaya komputasi O(mn).
Dalam "Length of Maximal Common Subsequences", KS Larsen mengusulkan algoritma yang menghitung panjang LCS dalam waktu O(log(m).log(n)). Namun algoritme tersebut memiliki kebutuhan memori O(m.n²) dan karenanya tidak diterapkan di sini.
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" ));
}
}Metrik jarak berdasarkan Urutan Umum Terpanjang, dari catatan "Metrik string berbasis LCS" oleh Daniel Bakkelund. http://heim.ifi.uio.no/~danielry/StringMetric.pdf
Jarak dihitung sebagai 1 - |LCS(s1, s2)| / maks(|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" ));
}
}Jarak N-Gram yang dinormalisasi seperti yang didefinisikan oleh Kondrak, "Kesamaan dan Jarak N-Gram", Pemrosesan String dan Pengambilan Informasi, Catatan Kuliah Ilmu Komputer Volume 3772, 2005, hlm 115-126.
http://webdocs.cs.ualberta.ca/~kondrak/papers/spire05.pdf
Algoritme ini menggunakan pembubuhan karakter khusus 'n' untuk menambah bobot karakter pertama. Normalisasi dilakukan dengan membagi total skor kemiripan dengan panjang asli kata terpanjang.
Dalam makalahnya, Kondrak juga mendefinisikan ukuran kesamaan, yang (belum) diterapkan.
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 ));
}
}Beberapa algoritme bekerja dengan mengubah string menjadi kumpulan n-gram (urutan n karakter, terkadang juga disebut k-shingles). Kesamaan atau jarak antar dawai maka persamaan atau jarak antar himpunan.
Biaya untuk menghitung persamaan dan jarak ini sebagian besar didominasi oleh k-shingling (mengubah string menjadi rangkaian k karakter). Oleh karena itu biasanya ada dua kasus penggunaan untuk algoritma ini:
Hitung langsung jarak antar string:
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" ));
}
}Atau, untuk kumpulan data besar, hitung terlebih dahulu profil semua string. Kesamaan kemudian dapat dihitung antar profil:
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 ));
}
}Perhatikan, ini hanya berfungsi jika objek KShingling yang sama digunakan untuk mengurai semua string masukan!
Jarak Q-gram, seperti yang didefinisikan oleh Ukkonen dalam "Perkiraan pencocokan string dengan q-gram dan kecocokan maksimal" http://www.sciencedirect.com/science/article/pii/0304397592901434
Jarak antara dua string didefinisikan sebagai norma L1 selisih profilnya (jumlah kemunculan setiap n-gram): SUM( |V1_i - V2_i| ). Jarak Q-gram adalah batas bawah jarak Levenshtein, tetapi dapat dihitung dalam O(m + n), dimana Levenshtein memerlukan O(mn)
Kesamaan antara dua string adalah kosinus sudut antara representasi dua vektor ini, dan dihitung sebagai V1. V2 / (|V1| * |V2|)
Jarak dihitung sebagai 1 - kesamaan kosinus.
Seperti jarak Q-Gram, string masukan terlebih dahulu diubah menjadi kumpulan n-gram (urutan n karakter, juga disebut k-shingles), namun kali ini kardinalitas setiap n-gram tidak diperhitungkan. Setiap string masukan hanyalah sekumpulan n-gram. Indeks Jaccard kemudian dihitung sebagai |V1 inter V2| / |V1 kesatuan V2|.
Jarak dihitung sebagai 1 - kesamaan. Indeks Jaccard adalah jarak metrik.
Mirip dengan indeks Jaccard, namun kali ini kemiripannya dihitung sebagai 2 * |V1 inter V2| / (|V1| + |V2|).
Jarak dihitung sebagai 1 - kesamaan.
Pengenalan Pola Ratcliff/Obershelp, juga dikenal sebagai Pencocokan Pola Gestalt, adalah algoritma pencocokan string untuk menentukan kesamaan dua string. Ini dikembangkan pada tahun 1983 oleh John W. Ratcliff dan John A. Obershelp dan diterbitkan dalam Jurnal Dr. Dobb pada bulan Juli 1988
Ratcliff/Obershelp menghitung kesamaan antara 2 string, dan nilai yang dikembalikan terletak pada interval [0.0, 1.0].
Jarak dihitung sebagai 1 - kesamaan Ratcliff/Obershelp.
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" ));
}
}akan menghasilkan:
0.8888888888888888
0.7777777777777778
SIFT4 adalah algoritma jarak string tujuan umum yang terinspirasi oleh JaroWinkler dan Longest Common Subsequence. Ini dikembangkan untuk menghasilkan ukuran jarak yang sedekat mungkin dengan persepsi manusia tentang jarak string. Oleh karena itu, ini memperhitungkan elemen-elemen seperti substitusi karakter, jarak karakter, barisan umum terpanjang, dll. Ini dikembangkan menggunakan pengujian eksperimental, dan tanpa latar belakang teoretis.
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);
}
}
Gunakan kesamaan java-string dalam proyek Anda dan ingin disebutkan di sini? Jangan ragu untuk menghubungi saya!
