Temu Duga Pengekodan: Bagaimana Anda Mengira Edit Distance dengan Pengaturcaraan Dinamik?

Masalah dan senario yang berkaitan

Diberikan dua rentetan source dan target, kembalikan bilangan minimum pengeditan yang diperlukan untuk mengubah source menjadi target. Satu pengeditan menyisipkan satu aksara, memadam satu aksara, atau menggantikan satu aksara. Setiap operasi berkos satu. Mana-mana rentetan boleh kosong, dan kedua-duanya hanya mengandungi huruf kecil bahasa Inggeris.

source = "horse"
target = "ros"

horse -> rorse   replace h with r
rorse -> rose    delete r
rose  -> ros     delete e

answer = 3

Katakan m = source.length dan n = target.length, dengan kedua-dua panjang paling banyak 2,000. Tugasan ini hanya meminta kos minimum, bukan skrip pengeditan (edit script). Kertas kerja Wagner–Fischer mentakrifkan pembetulan rentetan sebagai jujukan berkos minimum bagi penyisipan, pemadaman dan penggantian serta memberikan algoritma yang masanya berkadaran dengan hasil darab kedua-dua panjang tersebut. Panduan temu duga 2026 semasa masih menggunakan edit distance sebagai latihan pengaturcaraan dinamik dua rentetan yang kanonikal. Ini menyokong nilai persediaan topik ini; ia tidak membuktikan kekerapan atau atribusi syarikat tertentu.

Masalah ini muncul dalam penyemakan ejaan (spell checking), pemadanan kabur (fuzzy matching), pemautan rekod (record linkage), dan perbandingan jujukan, tetapi takrifan pengeluaran mungkin menggunakan operasi berwajaran, transposisi, penormalan, atau token khusus domain. Versi temu duga sengaja menetapkan pengeditan aksara berkos unit supaya keadaan (state) dan pembuktiannya tidak kabur.

Perkara yang dinilai oleh penemu duga

Isyarat pertama ialah takrifan keadaan (state definition) dengan sempadan yang tepat. Takrifkan dp[i][j] sebagai edit minimum yang diperlukan untuk mengubah i aksara pertama source menjadi j aksara pertama target. “Jawapan sehingga i dan j” adalah terlalu samar untuk mewajarkan peralihan atau memulakan awalan kosong.

Isyarat kedua ialah menerbitkan ketiga-tiga peralihan aksara yang tidak sepadan. Operasi terakhir bagi penyelesaian optimum mestilah salah satu daripada padam (delete), sisip (insert), atau ganti (replace). Mengeluarkan operasi terakhir tersebut meninggalkan masalah awalan yang lebih kecil. Calon mesti memetakan setiap operasi ke sel bersebelahan yang betul dan bukannya menghafal tiga koordinat.

Isyarat ketiga ialah mengendalikan aksara akhir yang sepadan tanpa mencipta kerja tambahan. Jika source[i - 1] sama dengan target[j - 1], penyelesaian optimum boleh membiarkan aksara tersebut tidak berubah, jadi nilainya datang daripada dp[i - 1][j - 1]. Pembuktian juga mesti menunjukkan bahawa tiada penyelesaian yang lebih murah tersembunyi oleh pilihan ini.

Isyarat keempat ialah mengenali bentuk kebergantungan (dependency shape). Suatu baris hanya menggunakan baris sebelumnya dan sel kirinya sendiri, maka matriks penuh O(mn) tidak diperlukan apabila hanya jarak (distance) yang dikembalikan. Meletakkan rentetan yang lebih pendek pada dimensi lajur memberikan ruang bantuan O(min(m, n)).

Isyarat terakhir ialah mengekalkan kontrak masalah. Menukar rentetan baris dan lajur adalah sah di sini kerana kos unit penyisipan dan pemadaman menjadikan jarak simetri. Ia tidak sah secara automatik apabila penyisipan dan pemadaman mempunyai wajaran yang berbeza. Teks Unicode juga memerlukan pilihan eksplisit antara UTF-16 code units, Unicode code points, dan grapheme clusters yang dilihat oleh pengguna.

Soalan untuk dijelaskan sebelum menjawab

• Operasi manakah yang dibenarkan? Masalah ini membenarkan penyisipan, pemadaman dan penggantian. Transposisi

bersebelahan bukan satu operasi tunggal.

• Berapakah kos satu pengeditan? Setiap operasi yang dibenarkan berkos satu. Kos berwajaran mengubah rekurens dan mungkin

menghilangkan simetri.

• Apakah unit perbandingannya? Gesaan menggunakan huruf kecil bahasa Inggeris, jadi pengindeksan JavaScript adalah selamat untuk

pelaksanaan ini. Teks Unicode umum memerlukan kontrak berasingan.

• Adakah kita hanya mengembalikan jarak atau skrip pengeditan? Hanya jarak. Pembinaan semula operasi biasanya

mengekalkan jadual penuh atau maklumat pendahulu (predecessor) yang eksplisit.

• Bolehkah mana-mana input kosong? Ya. Mengubah rentetan kosong menjadi awalan dengan panjang j memerlukan tepat j

penyisipan; sebaliknya memerlukan i pemadaman.

• Apakah had saiz? Panjang sehingga 2,000 menjadikan masa O(mn) boleh diterima tetapi menjadikan rekursi eksponen

dan memori jadual penuh yang tidak perlu tidak diingini.

• Bolehkah input ditukar untuk menjimatkan memori? Ya di bawah kontrak kos unit ini kerana jaraknya adalah

simetri. Nyatakan andaian tersebut sebelum menggunakannya.

Rangka jawapan 30 saat

“Saya mentakrifkan dp[i][j] sebagai edit minimum daripada i aksara source pertama kepada j aksara target pertama. Kos awalan kosong memulakan baris dan lajur pertama. Aksara akhir yang sama menggunakan nilai pepenjuru tanpa perubahan. Jika tidak, edit terakhir ialah padam, sisip, atau ganti, jadi saya mengambil satu ditambah minimum bagi sel di atas, di kiri, dan pepenjuru. Setiap sel hanya bergantung pada baris sebelumnya dan nilai kiri baris semasa, jadi saya meletakkan rentetan yang lebih pendek pada lajur dan menyimpan dua baris. Itu memberikan masa O(mn) dan ruang O(min(m, n)). Saya mengesahkan rentetan kosong, rentetan sama, panjang asimetri, dan keputusannya terhadap rujukan jadual penuh pada input kecil.”

Penyelesaian terperinci langkah demi langkah

Bermula daripada awalan. Katakan dp[i][j] ialah bilangan minimum edit yang dibenarkan yang mengubah source[0..i - 1] menjadi target[0..j - 1].

Sempadan awalan kosong terhasil terus daripada kontrak:

dp[0][j] = j   // insert all j target characters
dp[i][0] = i   // delete all i source characters

Bagi awalan yang tidak kosong, periksa aksara akhirnya. Jika sepadan, mengekalkan aksara akhir yang dikongsi itu mengurangkan masalah kepada dua awalan yang lebih pendek:

if source[i - 1] == target[j - 1]:
  dp[i][j] = dp[i - 1][j - 1]

Jika berbeza, kelaskan edit terakhir bagi mana-mana jujukan optimum:

delete source[i - 1]:       dp[i - 1][j]     + 1
insert target[j - 1]:       dp[i][j - 1]     + 1
replace the final character: dp[i - 1][j - 1] + 1

dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

Kes-kes ini adalah menyeluruh (exhaustive) kerana operasi terakhir mestilah salah satu daripada tiga edit yang dibenarkan. Ia bersifat membina (constructive): tambahkan edit yang dinamakan kepada penyelesaian optimum bagi awalan lebih kecil yang dipilih, dan ia menghasilkan penyelesaian yang sah untuk (i, j). Sebaliknya, keluarkan edit terakhir daripada mana-mana penyelesaian optimum; bakinya menyelesaikan awalan lebih kecil yang sepadan, jadi ia tidak boleh berkos lebih rendah daripada sel tersebut. Ini membuktikan rekurens ketidaksepadanan.

Bagi aksara akhir yang sepadan, terdapat penyelesaian optimum yang membiarkannya sepadan. Jika sesuatu jujukan optimum mengedit aksara akhir source atau target, keluarkan kesan akhir tersebut dan jajar aksara yang sama sebagai ganti; ini tidak meningkatkan kos. Kerja yang selebihnya adalah tepat masalah awalan pepenjuru. Aruhan pada i + j, yang disandarkan oleh sempadan awalan kosong, membuktikan setiap sel dan oleh itu membuktikan dp[m][n].

Hanya tiga nilai sebelumnya yang diperlukan semasa mengisi baris: previous[j] untuk pemadaman, current[j - 1] untuk penyisipan, dan previous[j - 1] untuk penggantian atau pemadanan. Kod ini menjadikan rentetan yang lebih pendek sebagai lajur. Pertukaran tersebut ialah pengoptimuman memori di bawah takrifan kos unit yang simetri ini; ia tidak mengubah jawapan.

export function editDistance(source: string, target: string): number {
  const rows = source.length >= target.length ? source : target
  const columns = source.length >= target.length ? target : source

  let previous = Array.from(
    { length: columns.length + 1 },
    (_, index) => index,
  )

  for (let row = 1; row <= rows.length; row += 1) {
    const current = new Array<number>(columns.length + 1)
    current[0] = row

    for (let column = 1; column <= columns.length; column += 1) {
      if (rows[row - 1] === columns[column - 1]) {
        current[column] = previous[column - 1]
        continue
      }

      const deleteCost = previous[column] + 1
      const insertCost = current[column - 1] + 1
      const replaceCost = previous[column - 1] + 1
      current[column] = Math.min(deleteCost, insertCost, replaceCost)
    }

    previous = current
  }

  return previous[columns.length]
}

Bagi source = "horse" dan target = "ros", dimensi lajur yang lebih pendek mempunyai panjang tiga. Baris akhir berakhir dengan tiga, sepadan dengan jujukan satu-penggantian-tambah-dua-pemadaman. Algoritma mengembalikan kos; ia tidak mendakwa bahawa jujukan edit khusus ini adalah unik.

Kerumitan, sempadan, dan pilihan kejuruteraan

Algoritma mengisi (m + 1)(n + 1) keadaan konsep, jadi masa ialah O(mn). Setiap baris mempunyai min(m, n) + 1 entri, dan hanya dua baris wujud pada satu-satu masa, jadi ruang bantuan ialah O(min(m, n)). Memperuntukkan semula satu baris bagi setiap lelaran tidak mengubah batas asimtotik; dua tatasusunan yang boleh diguna semula boleh mengurangkan tekanan peruntukan tanpa mengubah algoritma.

Jawapan maksimum di bawah penyisipan, pemadaman dan penggantian unit ialah max(m, n): gantikan min(m, n) aksara pertama, kemudian sisip atau padam perbezaan panjang. Nilai minimum adalah sekurang-kurangnya |m - n|, kerana setiap edit mengubah panjang paling banyak satu. Batas ini ialah penegasan (assertions) yang berguna dalam ujian.

Bagi rentetan JavaScript umum, pengindeksan beroperasi pada UTF-16 code units. Lelaran rentetan mengekalkan pasangan surrogate dengan menghasilkan Unicode code points, tetapi ia masih boleh memisahkan satu grapheme cluster seperti emoji ditambah ton kulit atau jujukan zero-width-joiner. Ciri keserupaan pengeluaran mesti memutuskan sama ada pengeditan dikenakan pada code units, code points, grapheme clusters yang dinormalkan, perkataan, atau token domain sebelum memilih tokenizer. Penormalan senyap juga boleh mengubah semantik produk, jadi ia tergolong dalam kontrak dan bukannya di dalam gelung DP ini.

Jika pemanggil hanya bertanya sama ada jarak adalah paling banyak k, tolak terlebih dahulu apabila |m - n| > k, kemudian nilaikan hanya jalur pepenjuru (diagonal band) dan berhenti apabila tiada keadaan dalam jalur aktif boleh kekal dalam k. Itu adalah kontrak output yang berbeza; pelaksanaan jarak penuh tidak sepatutnya menambah kerumitan tersebut secara spekulatif.

Contoh jawapan berkualiti tinggi

“Saya akan memodelkan masalah ini ke atas awalan. Katakan dp[i][j] ialah kos minimum untuk mengubah i aksara source pertama menjadi j aksara target pertama. Sempadan awalan kosong ialah panjang masing-masing. Bagi aksara akhir yang sama, saya mengekalkan nilai pepenjuru. Bagi aksara akhir yang berbeza, saya mengelaskan jujukan optimum mengikut edit terakhirnya: memadam menggunakan sel di atas, menyisip menggunakan sel di kiri, dan menggantikan menggunakan pepenjuru, dengan menambah satu pada nilai minimum. Kes-kes tersebut adalah menyeluruh, dan mengeluarkan edit terakhir membuktikan rekurens dari arah bertentangan.

“Memandangkan sesuatu sel hanya menggunakan baris sebelumnya dan sel kiri baris semasa, saya menyimpan dua baris. Kos unit penyisipan dan pemadaman menjadikan jarak ini simetri, jadi rentetan yang lebih pendek boleh dijadikan lajur dan memori menjadi O(min(m, n)); masa kekal O(mn). Saya tidak akan menggunakan pertukaran itu untuk wajaran asimetri. Saya akan menguji kedua-dua arah rentetan kosong, rentetan sama, contoh horse kepada ros, dan rentetan pendek yang dijana terhadap versi jadual penuh. Jika penemu duga memerlukan skrip pengeditan, saya akan mengekalkan maklumat pendahulu dan bukannya berjanji untuk memulihkannya daripada baris yang ditimpa.”

Kesilapan lazim

• Menggunakan pemadanan aksara tamak (greedy) → aksara yang berulang dan anjakan terkemudian menyebabkan edit yang mudah secara tempatan kehilangan

minimum global → takrifkan keadaan awalan optimum dan bandingkan semua operasi akhir yang sah.

• Memulakan baris dan lajur pertama kepada sifar → kes rentetan kosong menjadi percuma → **tetapkan kos sempadan

kepada panjang awalan masing-masing.**

• Tertukar jiran insert dan delete → kod mungkin melepasi contoh simetri tetapi gagal pada

awalan asimetri → terangkan rentetan yang tinggal selepas mengeluarkan operasi terakhir.

• Menambah satu apabila aksara akhir sepadan → aksara sama yang tidak berubah dicaj sebagai penggantian → **salin

pepenjuru tepat seperti sedia ada apabila sepadan.**

• Mengembalikan jawapan rolling-row sambil menjanjikan skrip pengeditan → pendahulu yang ditimpa tidak dapat membina semula

laluan → kekalkan matriks atau backpointers apabila operasi diperlukan.

• Menukar rentetan di bawah wajaran asimetri → penyisipan dalam satu arah menjadi pemadaman dalam arah yang lain →

kekalkan orientasi asal melainkan model kos adalah simetri.

• Memanggil indeks JavaScript sebagai “aksara” untuk sebarang Unicode → pasangan surrogate atau grapheme clusters akan

dikira tanpa diduga → takrifkan dan lakukan tokenisasi unit perbandingan secara eksplisit.

Set ujian yang fokus merangkumi ("", "") = 0, ("", "abc") = 3, ("abc", "") = 3, ("same", "same") = 0, ("aaaa", "aa") = 2, ("horse", "ros") = 3, dan ("intention", "execution") = 5. Bandingkan pelaksanaan rolling dengan rujukan jadual penuh ke atas semua rentetan pendek daripada abjad kecil. Periksa juga identiti, simetri di bawah model kos ini, |m - n| ≤ d ≤ max(m, n), dan ketaksamaan segi tiga pada ganda tiga rentetan yang dijana. Akhir sekali, jalankan input sama dan berbeza sepenuhnya sepanjang 2,000 untuk mengesahkan laluan saiz ekstrem kekal dalam jangkaan masa kuadratik dan ruang linear.

Soalan susulan temu duga

Susulan 1: Bagaimana anda akan mengembalikan operasi pengeditan sebenar?

Kekalkan jadual penuh dan lakukan jejak ke belakang (backtrack) daripada (m, n). Pemadanan bergerak secara pepenjuru tanpa mengeluarkan operasi; jika tidak, pilih sel bersebelahan yang nilainya ditambah kos edit yang sepadan sama dengan nilai semasa. Tentukan peraturan pemutus seri (tie-break) yang stabil kerana mungkin wujud beberapa skrip minimum. Kaedah terus menggunakan ruang O(mn). Pembinaan semula ruang linear boleh dilakukan dengan teknik divide-and-conquer, tetapi ia merupakan algoritma berasingan dan hanya patut diperkenalkan apabila keperluan memori menuntutnya.

Susulan 2: Apakah yang berubah apabila operasi mempunyai wajaran berbeza?

Tambahkan wajaran yang berkaitan pada setiap peralihan dan bukannya nilai satu. Pembuktian optimal-substructure yang sama berfungsi apabila kos adalah bukan negatif dan ditakrifkan oleh kontrak. Jika kos penyisipan dan pemadaman berbeza, jarak mungkin mempunyai arah (directional), jadi menukar rentetan untuk memendekkan baris tidak lagi betul secara automatik. Kos edit negatif merosakkan tafsiran biasa dan memerlukan pertimbangan semula model.

Susulan 3: Bagaimana anda akan menyokong transposisi bersebelahan?

Mula-mula jelaskan sama ada transposisi hanya menukar aksara bersebelahan dan sama ada transposisi bertindih (overlapping) dibenarkan. Rekurens restricted optimal-string-alignment boleh memeriksa dua aksara sebelumnya yang tambahan dan satu sel dua baris dan lajur ke belakang. Jarak Damerau–Levenshtein penuh mempunyai keperluan keadaan yang berbeza. Sekadar menambah satu semakan pepenjuru secara tidak formal boleh melaksanakan varian yang salah.

Susulan 4: Apakah kaitannya dengan longest common subsequence (LCS)?

Jika penggantian dilarang atau berkos sama seperti satu pemadaman ditambah satu penyisipan, jarak penyisipan-dan-pemadaman boleh diterbitkan daripada LCS sebagai m + n - 2 * LCS(source, target). Dengan penggantian kos unit, formula tersebut secara amnya bukan edit distance: menggantikan satu aksara yang tidak sepadan berkos satu, manakala padam-tambah-sisip berkos dua. Nyatakan kos operasi sebelum menggunakan hubungan tersebut.

Susulan 5: Bagaimana anda menjawab “adakah jarak paling banyak k?” dengan lebih pantas?

Kembalikan false serta-merta apabila perbezaan panjang melebihi k. Jika tidak, kira hanya keadaan dalam lingkungan k dari pepenjuru utama, anggap sel di luar jalur sebagai tidak boleh dicapai, dan berhenti jika sempadan aktif tidak boleh kembali dalam bajet. Ini boleh mengurangkan kerja secara ketara apabila k adalah kecil, manakala kes terburuk bagi jarak tanpa sekatan kekal kuadratik.

Susulan 6: Bagaimana anda mengendalikan teks Unicode sebenar yang dilihat oleh pengguna?

Pilih unit bersama pemilik produk (product owner). Lelaran code-point menghalang pemisahan pasangan surrogate, tetapi ia masih boleh memisahkan beberapa aksara yang dilihat oleh pengguna. Segmentasi grafem lebih sepadan dengan aksara yang kelihatan, dan penormalan Unicode boleh menjadikan jujukan yang setara secara kanonikal dibandingkan secara konsisten. Lokal (locale), case folding, aksen, dan peraturan peringkat token ialah keputusan produk. Gunakan pra-pemprosesan tersebut sebelum DP dan uji contoh daripada bahasa yang disokong.

Susulan 7: Bolehkah satu baris menggantikan dua baris?

Ya. Sebelum menulis ganti dp[j], simpan nilai lamanya sebagai pepenjuru seterusnya; dp[j] masih mewakili sel di atas, dan dp[j - 1] sudah mewakili sel kiri baris semasa. Ini mengurangkan faktor pemalar, bukan ruang asimtotik. Dalam temu duga, dua baris selalunya lebih mudah dibuktikan dan kurang terdedah kepada ralat melainkan penemu duga meminta varian in-place secara khusus.