Bagaimana untuk Mengira Kesamaan Rentetan di Jawa Menggunakan Jarak Levenshtein?

Perbandingan Rentetan Kesamaan dalam Jawa

Memahami Keperluan untuk Langkah-langkah Persamaan

Apabila bekerja dengan data teks, menjadi penting untuk menilai persamaan antara rentetan. Ini boleh terbukti bermanfaat dalam tugas seperti mengenal pasti kandungan pendua, mencari hasil carian yang paling serupa, atau bahkan mengekstrak maklumat bermakna daripada teks. Nasib baik, terdapat kaedah yang cekap dan mantap dalam Java untuk mengira persamaan rentetan.

Memperkenalkan Fungsi Keserupaan

Pendekatan yang paling biasa untuk perbandingan rentetan melibatkan pengiraan indeks persamaan yang mengukur tahap persamaan antara dua rentetan. Ukuran persamaan yang digunakan secara meluas ialah Jarak Levenshtein, yang mengira bilangan minimum suntingan (sisipan, pemadaman atau penggantian) yang diperlukan untuk mengubah satu rentetan kepada rentetan yang lain. Metrik jarak ini biasanya dinormalisasi kepada julat antara 0 dan 1, dengan nilai yang lebih tinggi menunjukkan persamaan yang lebih besar.

Melaksanakan Jarak Levenshtein

Satu cara untuk mengira Levenshtein Jarak adalah dengan menggunakan kaedah **String.getLevenshteinDistance()** yang disediakan oleh **Teks ​​Apache Commons** perpustakaan, yang melaksanakan algoritma Levenshtein standard. Sebagai alternatif, anda juga boleh melaksanakan algoritma secara manual seperti yang ditunjukkan dalam kod di bawah:

public static int editDistance(String s1, String s2) {
  int n = s1.length() + 1;
  int m = s2.length() + 1;
  int[][] matrix = new int[n][m];

  for (int i = 0; i < n; i++) {
    matrix[i][0] = i;
  }

  for (int j = 0; j < m; j++) {
    matrix[0][j] = j;
  }

  for (int i = 1; i < n; i++) {
    for (int j = 1; j < m; j++) {
      int cost = (s1.charAt(i - 1) == s2.charAt(j - 1)) ? 0 : 1;
      matrix[i][j] = Math.min(
        matrix[i - 1][j] + 1, // deletion
        Math.min(
          matrix[i][j - 1] + 1, // insertion
          matrix[i - 1][j - 1] + cost // substitution
        )
      );
    }
  }

  return matrix[n - 1][m - 1];
}

Mengira Indeks Kesamaan

Setelah Jarak Levenshtein dikira, persamaan indeks boleh diperolehi dengan menormalkannya kepada panjang yang lebih lama rentetan:

public static double similarity(String s1, String s2) {
  double longerLength = Math.max(s1.length(), s2.length());
  return 1.0 - (editDistance(s1, s2) / longerLength);
}

Kesimpulan

Dengan melaksanakan Jarak Levenshtein dan fungsi persamaan dalam Java, anda memperoleh alat yang berkuasa untuk menilai persamaan antara rentetan. Teknik ini menemui banyak aplikasi dalam pemprosesan bahasa semula jadi, analisis data dan domain lain yang membandingkan kandungan teks adalah penting.

Atas ialah kandungan terperinci Bagaimana untuk Mengira Kesamaan Rentetan di Jawa Menggunakan Jarak Levenshtein?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!