Cocokkan dua string tetapi memungkinkan untuk tingkat kesalahan

10

Bagaimana saya bisa mencocokkan dua string, tetapi pada saat yang sama memungkinkan jumlah karakter X salah dalam pertandingan. Jumlah kesalahan harus merupakan variabel yang dapat dikontrol.

Sementara X jumlah karakter tidak dapat cocok dengan string, harus ada batasan berapa banyak yang dijalankan secara berurutan. Diberikan dua string, saya mungkin mengizinkan 5 karakter berbeda, tetapi tidak lebih dari 2 berturut-turut.

Saya sedang mencari algoritma yang direkomendasikan untuk membandingkan dua string ini, atau mungkin sudah ada solusi yang diketahui untuk ini.

algorithms strings Reactgular
sumber
4
The Levenshtein jarak mungkin sesuatu untuk melihat, meskipun spesifik dari 'tidak lebih dari 2 berturut-turut' bukan bagian dari algoritma yang. Halaman lihat juga memiliki banyak algoritma terkait lainnya yang mungkin Anda cari.
@MichaelT jika saya memiliki sesuatu seperti itu pasti akan sesuai dengan kebutuhan saya. Terima kasih.
Reactgular
@MichaelT Saya menemukan ini> dotnetperls.com/levenshtein Anda harus meletakkan itu sebagai jawaban karena ini menyelesaikan masalah saya.
Reactgular
Anda mungkin ingin melihat pencocokan Soundex. en.wikipedia.org/wiki/Soundex
Gilbert Le Blanc

Jawaban:

12

Titik awal pencarian string perkiraan adalah jarak Levenshtein . Algoritma ini menghitung jumlah pengeditan karakter tunggal (masukkan, hapus, dan substitusi) untuk mengubah satu kata menjadi kata lain.

Contohnya adalah kitten-> sittingyang memiliki jarak edit tiga

  1. k itten -> s itten (gantikan 's' untuk 'k')
  2. sitt e n -> sitt i n (gantikan 'i' untuk 'e')
  3. sittin -> sittin g (tambahkan 'g' di akhir)

Ada variasi pada algoritma ini, terutama jarak Damerau-Levenshtein yang memungkinkan untuk transposisi dua karakter yang berdekatan ('hte' ke 'the' memiliki Jarak DL 1 dan jarak Levenshtein 2) dan oleh karena itu seringkali lebih sesuai untuk pengecekan ejaan. Variasi lain ada untuk aplikasi di mana kesenjangan penting (string DNA).

Jarak Levenshtein dikenal dan tidak terlalu sulit untuk ditemukan (Saya pernah memiliki alasan untuk memburu implementasi itu sebagai fungsi dalam oracle - itu jauh lebih cepat daripada menarik semua data dan kemudian menjalankan sisi kode kueri). Rosettacode memiliki banyak (54) implemntations dari jarak Levenshtein (perhatikan bahwa beberapa bahasa memiliki ini sebagai bagian dari perpustakaan string di suatu tempat - jika Anda menggunakan Java, lihat apache commons lang ). Wikibooks memiliki 31 implementasi dan pandangan sekilas pada keduanya tidak menunjukkan kode yang sama untuk bahasa yang sama.

Cara kerjanya adalah membangun matriks yang sesuai dengan hubungan antara dua string:

 .kitten
.0123456
s1123456
i2212345
t3321234
t4432123
i5543223
n6654332
g7765443

The .baris dan kolom menyatakan bahwa Anda bisa mendapatkan target string dengan 'hanya' memasukkan setiap huruf dari string kosong. Ini bukan kasus yang ideal, tetapi ada untuk menumbuhkan algoritma.

Jika nilainya sama dengan titik itu ('i' == 'i'), nilainya sama dengan nilai diagonal ke kiri. Jika dua tempat berbeda ('s'! = 'K') nilainya adalah minimum:

  • diagonal ke atas dan ke kiri +1 (substitusi)
  • langsung di atas +1 (penyisipan)
  • langsung ke kiri + 1 (penghapusan)

Nilai pengembalian jarak edit adalah nilai di kanan bawah matriks.

Jika Anda mengikuti dari kanan bawah ke kiri atas dengan minimum, Anda dapat melihat pengeditan dilakukan:

 .kitten
.0.   .
s.1   .
i  1  .
t   1 .
t    1.
i.....2
n      2
g......3

Perhatikan bahwa ini adalah pendekatan yang lebih intensif memori. Itu dapat dikurangi dalam ruang lingkup memori dengan tidak membangun matriks penuh - semua algoritma peduli adalah bagian dari data dan dapat dikurangi dari N*Mruang ke 2*max(N,M)ruang dengan hanya menyimpan baris sebelumnya (dan apa yang telah dihitung pada saat ini baris). Project Code menunjukkan bagaimana hal ini dapat dilakukan (dengan kode C # untuk mengunduh).

Komunitas
sumber