Menyetel ke Julia: Algoritma Levenshtein – Beragampengetahuan

Oleh: Jan Vanhove

Repost dari:

Dalam posting blog kedua tentang Julia ini, saya akan berbagi
dengan Anda implementasi Julia dari algoritma Levenshtein.

Algoritma Levenshtein

Algoritma Levenshtein dasar digunakan untuk menghitung jumlah minimum
masukkan, hapus dan ganti diperlukan untuk mengonversi a
string ke string lain. Misalnya, untuk mengonversi bahasa Inggris mengira di dalam
Perancis memuji, Anda memerlukan setidaknya dua operasi. Anda bisa mengganti
B dengan satu T lalu ganti T dengan satu e; atau kamu bisa
menghapus B lalu masukkan e. Seperti yang ditunjukkan contoh ini, ada
ada banyak cara untuk mengonversi satu string ke string lainnya menggunakan min
jumlah operasi yang diperlukan, tetapi minimum itu sendiri unik
untuk setiap pasang kabel.

Dibuat di Julia

Saya tidak akan membahas logika algoritma Levenshtein di sini.
Berikut adalah implementasi pseudocode sederhana Julia
ditemukan di Wikipedia, dengan asumsi biayanya 1 untuk semua operasi.
Fungsi mengambil dua input (string a yang akan dikonversi
ke dalam rantai b) dan menampilkan array dengan jarak Levenshtein
antara semua substring dari a wajah dan semua substring dari b
Di samping itu. Entri di pojok kanan bawah array ini
adalah jarak Levenshtein antara string penuh dan ini adalah hasilnya
terpisah itu baik.

function levenshtein(a::String, b::String)
  # Initialise table
  distances = zeros(Int, length(a) + 1, length(b) + 1)
  distances[:, 1] = 0:length(a)
  distances[1, :] = 0:length(b)

  # Levenshtein logic
  for row in 2:(length(a) + 1)
    for col in 2:(length(b) + 1)
      distances[row, col] = min(
        distances[row - 1, col - 1] + 
          Int(a[row - 1] != b[col - 1] ? 1 : 0)
        , distances[row, col - 1] + 1
        , distances[row - 1, col] + 1
      )
    end
  end

  return distances, distances[length(a) + 1, length(b) + 1]
end

Hitung jarak Levenshtein antara
dari Jerman Zyklus (‘siklus’) dan nya
mitra Swedia mengayun.
Perhatikan penggunaan dari ; di akhir baris untuk menekan
keluaran.

dist_matrix, lev_cost = levenshtein("zyklus", "cykel");
display(dist_matrix)

## 7×6 Matrix{Int64}:
##  0  1  2  3  4  5
##  1  1  2  3  4  5
##  2  2  1  2  3  4
##  3  3  2  1  2  3
##  4  4  3  2  2  2
##  5  5  4  3  3  3
##  6  6  5  4  4  4

Tes ini: Anda benar-benar membutuhkan empat operasi
untuk mengubah Zyklus di dalam mengayun.

Fungsi vektor

Tetapi bagaimana jika kita ingin menerapkan yang baru?
fungsi untuk beberapa pasangan string?
Mari kita kenali dulu tiga pasang kata Belanda-Jerman:

dutch = ("boek", "zuster", "sneeuw");
german = ("buch", "schwester", "schnee");

Kita bisa menjalankannya sendiri levenshtein() lebih dari tiga
pasangan kata tanpa memperkenalkan for loop secara sederhana
tambahkan titik ke nama fungsi:

levenshtein.(dutch, german)

## (([0 1 … 3 4; 1 0 … 2 3; … ; 3 2 … 2 3; 4 3 … 3 3], 3), ([0 1 … 8 9; 1 1 … 8 9; … ; 5 4 … 5 6; 6 5 … 6 5], 5), ([0 1 … 5 6; 1 0 … 4 5; … ; 5 4 … 4 3; 6 5 … 5 4], 4))

Namun, sejak levenshtein() keluaran fungsi
dua informasi (baik matriks dengan
jarak antara substring serta akhir
Levenshtein), hasil panggilan vektor ini
satu set dari tiga himpunan bagian, yang masing-masing berisi
matriks dan jarak Levenshtein akhir masing-masing.
Inilah mengapa output di atas terlihat sangat berantakan.
Jika kita hanya ingin mendapatkan jarak Levenshtein,
kita bisa menulis for loop untuk membongkarnya.
Tapi menurut saya solusi yang lebih mudah adalah dengan menulis pembungkus terlebih dahulu
sekitar levenshtein() fungsi keluaran saja
jarak Levenshtein terakhir dan gunakan versi vektor
dari pembungkus ini sebagai gantinya:

function lev_dist(a::String, b::String)
  return levenshtein(a, b)[2]
end

Sekarang mari kita gunakan versi vektor dari lev_dist():

lev_dist.(dutch, german)

## (3, 5, 4)

Cantik!

Dapatkan aktivitas

Sekarang kita tahu bahwa kita membutuhkan empat operasi untuk diubah
Zyklus di dalam mengayun dan tahun untuk berubah fitnah
di dalam Schwester. Tapi itu adalah kegiatan yang Anda butuhkan
untuk transformasi ini?
Fungsi lev_alignment() keluaran didefinisikan di bawah ini
sekumpulan aktivitas yang dapat melakukan pekerjaan.
(Tidak seperti jumlah minimum operasi yang diperlukan untuk
mengonversi satu string ke string lain, diperlukan serangkaian operasi
tidak diidentifikasi secara unik.)

function lev_alignment(a::String, b::String)
  source = Vector{Char}()
  target = Vector{Char}()
  operations = Vector{Char}()
  
  lev_matrix = levenshtein(a, b)[1]
  
  row = size(lev_matrix, 1)
  col = size(lev_matrix, 2)

  while (row > 1 && col > 1)
    if lev_matrix[row - 1, col - 1] == lev_matrix[row, col] &&
        lev_matrix[row - 1, col - 1] <= min(
          lev_matrix[row - 1, col]
          , lev_matrix[row, col - 1]
          )
      row = row - 1
      col = col - 1
      pushfirst!(source, a[row])
      pushfirst!(target, b[col])
      pushfirst!(operations, ' ')
    else 
      if lev_matrix[row - 1, col] <= min(
          lev_matrix[row - 1, col - 1]
          , lev_matrix[row, col - 1])
        row = row - 1
        pushfirst!(source, a[row])
        pushfirst!(target, ' ')
        pushfirst!(operations, 'D')
      elseif lev_matrix[row, col - 1] <= lev_matrix[row - 1, col - 1]
        col = col - 1
        pushfirst!(source, ' ')
        pushfirst!(target, b[col])
        pushfirst!(operations, 'I')
      else
        row = row - 1
        col = col - 1
        pushfirst!(source, a[row])
        pushfirst!(target, b[col])
        pushfirst!(operations, 'S')
      end
    end
  end

  # If first column reached, move up.
  while (row > 1)
    row = row - 1
    pushfirst!(source, a[row])
    pushfirst!(target, ' ')
    pushfirst!(operations, 'D')
  end

  # If first row reached, move left.
  while (col > 1)
    col = col - 1
    pushfirst!(source, ' ')
    pushfirst!(target, b[col])
    pushfirst!(operations, 'I')
  end
  
  return vcat(
    reshape(source, (1, :))
    , reshape(target, (1, :))
    , reshape(operations, (1, :))
  )
end

Saya tidak akan menyebutkan logika di balik algoritme karena ini lebih dari itu
tentang belajar Julia bahwa algoritma Levenshtein.
Di sisi Julia, perhatikan dulu bagaimana vektor karakternya kosong
dapat diinisialisasi. Selanjutnya, perhatikan bahwa pushfirst!()
fungsi dihias dengan a ! (sebuah ‘ledakan’). Ini berkomunikasi
bagi siapa pun yang membaca kode, fungsi ini berubah
beberapa masukannya. Misalnya, pushfirst!(source, a[row])
berarti karakter saat ini a (YAITU, a[row])
ditambahkan di depan source vektor. Itu adalah,
Perintah ini berubah source vektor.
Terakhir source, target Dan operations vektor
semua vektor kolom. Untuk menunjukkan kepada mereka
bagus, saya mengonversi masing-masing menjadi matriks satu baris
menggunakan reshape(). Maka tiga baris yang dihasilkan adalah
splicing vertikal menggunakan vcat() untuk menunjukkan bagaimana
dua string dapat disejajarkan dan operasi apa yang diperlukan
untuk mengubah satu menjadi yang lain.

Mari kita lihat bagaimana kita bisa berubah Zyklus di dalam mengayun:

lev_alignment("zyklus", "cykel")

## 3×7 Matrix{Char}:
##  'z'  'y'  'k'  ' '  'l'  'u'  's'
##  'c'  'y'  'k'  'e'  'l'  ' '  ' '
##  'S'  ' '  ' '  'I'  ' '  'D'  'D'

Jadi kita ganti C Karena z,
masukkan a e dan hapus Teman Dan S.
Seperti yang saya sebutkan, rangkaian kegiatan ini tidak
diidentifikasi secara unik. Memang kita juga bisa memiliki
mengganti C Karena z, e Karena SAYA
Dan SAYA Karena Teman lalu hapus S.
Ini juga sesuai dengan jarak Levenshtein
dari empat operasi.

Jarak Levenshtein yang Dinormalisasi

Di atas, kami menghitung jarak Levenshtein mentah.
Masalah dengan ini adalah pasangan string lebih panjang
akan cenderung memiliki jarak Levenshtein mentah yang lebih besar
dari pasangan string yang lebih pendek, bahkan jika mereka terlihat
lebih mirip. Untuk mengatasinya, kita bisa menghitung
sebaliknya, jarak Levenshtein dinormalisasi.
Ada berbagai cara untuk menghitungnya;
satu opsi adalah membagi jarak Levenshtein mentah
Menurut panjang keselarasan:

function norm_lev_dist(a::String, b::String)
  raw_dist = lev_dist(a, b)
  alignment_length = size(lev_alignment(a, b), 2)
  return raw_dist / alignment_length
end

(Di belakang panggung, kami menjalankan algoritme Levenshtein
dua kali: sekali masuk lev_dist() dan lagi di lev_alignment().
Ini sepertinya boros – kecuali jika penyusun Julia bisa
untuk membersihkan pekerjaan ganda? saya tidak yakin.)

Kami memperoleh jarak Levenshtein yang dinormalisasi sebagai
sekitar 0,57 untuk Zyklus – mengayun:

norm_lev_dist("zyklus", "cykel")

## 0.5714285714285714

Kami juga dapat menggunakan versi vektor dari fungsi ini:

norm_lev_dist.(dutch, german)

## (0.75, 0.5555555555555556, 0.5)

Tentu saja, jarak Levenshtein yang dinormalisasi adalah simetris,
jadi kami mendapatkan hasil yang sama ketika kami menjalankan perintah berikut:

norm_lev_dist.(german, dutch)

## (0.75, 0.5555555555555556, 0.5)

Terkait