Jarak edit (atau Levenshtein) antara dua string adalah jumlah minimal penyisipan karakter tunggal, penghapusan dan penggantian yang diperlukan untuk mengubah satu string menjadi yang lain. Jika kedua string memiliki panjang n masing-masing, diketahui bahwa ini dapat dilakukan dalam waktu O (n ^ 2) dengan pemrograman dinamis. Kode Python berikut melakukan perhitungan ini untuk dua string s1
dan s2
.
def edit_distance(s1, s2):
l1 = len(s1)
l2 = len(s2)
matrix = [range(l1 + 1)] * (l2 + 1)
for zz in range(l2 + 1):
matrix[zz] = range(zz,zz + l1 + 1)
for zz in range(0,l2):
for sz in range(0,l1):
if s1[sz] == s2[zz]:
matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, matrix[zz][sz+1] + 1, matrix[zz][sz])
else:
matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, matrix[zz][sz+1] + 1, matrix[zz][sz] + 1)
return matrix[l2][l1]
Dalam tugas ini Anda harus sedekat mungkin untuk menghitung jarak sunting tetapi dengan batasan memori yang parah. Kode Anda diizinkan untuk mendefinisikan satu array yang berisi 1000 integer 32-bit dan ini adalah satu-satunya penyimpanan sementara yang Anda gunakan dalam perhitungan Anda. Semua variabel dan struktur data harus dimuat dalam array ini. Secara khusus, Anda tidak akan dapat mengimplementasikan algoritma di atas karena untuk string 1000 panjang karena akan mengharuskan Anda untuk menyimpan setidaknya 1.000.000 angka. Di mana bahasa Anda secara alami tidak memiliki bilangan bulat 32 bit (misalnya Python), Anda hanya perlu memastikan bahwa Anda tidak pernah menyimpan angka yang lebih besar dari 2 ^ 32-1 dalam array.
Anda dapat membaca dalam data menggunakan pustaka standar pilihan Anda tanpa khawatir tentang batasan memori di bagian itu. Untuk membuat kompetisi adil untuk bagian utama kode Anda, Anda hanya dapat menggunakan operasi yang secara fungsional setara dengan yang ada dalam bahasa pemrograman C dan tidak dapat menggunakan perpustakaan eksternal.
Agar lebih jelas, memori untuk menyimpan data input atau digunakan oleh penerjemah bahasa Anda, JVM, dll. Tidak diperhitungkan dalam batas Anda dan Anda tidak boleh menulis apa pun ke disk. Anda harus menganggap data input hanya-baca ketika berada di memori sehingga Anda tidak dapat menggunakannya kembali untuk mendapatkan lebih banyak ruang kerja.
Apa yang harus saya terapkan?
Kode Anda harus dibaca dalam file dalam format berikut. Itu akan memiliki tiga baris. Baris pertama adalah jarak sunting yang sebenarnya. Yang kedua adalah string 1 dan yang ketiga adalah string 2. Saya akan mengujinya dengan data sampel di https://bpaste.net/show/6905001d52e8 di mana string memiliki panjang 10.000 tetapi tidak boleh khusus untuk data ini. Seharusnya menampilkan jarak edit terkecil yang dapat ditemukan antara dua string.
Anda juga perlu membuktikan jarak sunting Anda sebenarnya berasal dari serangkaian suntingan yang valid. Kode Anda harus memiliki saklar yang mengubahnya menjadi mode yang dapat menggunakan lebih banyak memori (sebanyak yang Anda suka) dan mengeluarkan operasi edit yang memberikan jarak edit Anda.
Skor
Skor Anda akan menjadi (optimal edit distance/divided by the edit distance you find) * 100
. Untuk memulai, perhatikan bahwa Anda bisa mendapatkan skor hanya dengan menghitung jumlah ketidakcocokan antara kedua string.
Anda dapat menggunakan bahasa apa pun yang Anda suka yang tersedia secara bebas dan mudah dipasang di Linux.
Tie break
Dalam kasus tie-break, saya akan menjalankan kode Anda di mesin Linux saya dan kode tercepat menang.
for(int i=0;i<=5;i++)
diizinkan karena menyimpan datai
?{ uint32_t foo[1000]; for (foo[0] = 0; foo[0] < 5; ++foo[0]) printf("%d ", foo[0]); }
ini dengan asumsi array 32 bit integer Anda akan dipanggilfoo
.Jawaban:
C ++, Skor 92,35
Algoritma Estimasi: Algoritma menemukan tempat pertama dua string berbeda, dan kemudian mencoba semua permutasi operasi N yang mungkin (masukkan, hapus, ganti - karakter yang cocok dilewati tanpa menggunakan operasi). Ini skor setiap set operasi yang mungkin didasarkan pada seberapa jauh lebih jauh bahwa set operasi berhasil cocok dengan dua string, ditambah seberapa banyak hal itu menyebabkan panjang string saling bertemu. Setelah menentukan himpunan tertinggi dari operasi N, operasi pertama dalam himpunan diterapkan, ketidakcocokan berikutnya ditemukan, dan proses berulang sampai akhir string tercapai.
Program mencoba semua nilai N mulai 1-10 dan memilih level yang memberikan hasil terbaik. N = 10 umumnya yang terbaik sekarang karena metode penilaian mempertimbangkan panjang string. Nilai N yang lebih tinggi mungkin akan lebih baik, tetapi membutuhkan waktu yang lebih banyak secara eksponensial.
Penggunaan Memori: Karena program ini murni iteratif, hanya membutuhkan sedikit memori. Hanya 19 variabel yang digunakan untuk melacak status program. Ini ditetapkan oleh #defines untuk bertindak sebagai variabel global.
Penggunaan: Program ini digunakan sama dengan feersum: parameter pertama diasumsikan sebagai file, dan setiap parameter tambahan menunjukkan bahwa pengeditan harus ditampilkan. Program selalu mencetak perkiraan jarak sunting, dan skor.
Output Verifikasi: Output verifikasi yang diformat dalam tiga baris:
Baris atas adalah string target, tengah adalah operasi, dan bagian bawah adalah string yang sedang diedit. Spasi pada garis operasi menunjukkan bahwa karakter cocok. 'R' menunjukkan bahwa string edit memiliki karakter di posisi itu diganti dengan karakter string target. 'I' menunjukkan bahwa string edit memasukkan karakter string target pada posisi itu. 'D' menunjukkan bahwa string edit memiliki karakter di posisi itu dihapus. Suntingan edit dan target memiliki ruang yang disisipkan ketika karakter lain disisipkan atau dihapus sehingga mereka berbaris.
sumber
C ++ 75.0
Program ini dirancang untuk bekerja dengan string teks yang berubah-ubah. Panjangnya bisa berbeda, asalkan tidak melebihi 13824 karakter. Menggunakan 1.897 bilangan bulat 16-bit, yang setara dengan 949 bilangan bulat 32-bit. Awalnya saya menulisnya dalam C, tetapi kemudian menyadari tidak ada fungsi untuk membaca satu baris.
Argumen baris perintah pertama harus berupa nama file. Jika argumen kedua ada, ringkasan hasil edit dicetak. Baris pertama dalam file diabaikan sementara yang kedua dan ketiga adalah string.
Algoritma adalah versi dua kali lipat dari algoritma yang biasa. Ini pada dasarnya melakukan jumlah operasi yang sama, tetapi tentu saja jauh kurang akurat, karena jika urutan umum terpecah di tepi blok, banyak potensi penghematan hilang.
sumber
Python,
100Saya berhasil menghitung jarak edit dengan sempurna dalam batas memori yang diberikan. Sayangnya, entri ini melanggar dua aturan tantangan, dalam surat jika tidak dalam semangat.
Pertama, saya belum benar-benar menyimpan data saya di 1000 int 32-bit. Untuk string 10.000 karakter, program saya membuat dua array 10.000 elemen yang hanya akan berisi +1, 0, atau -1. Pada 1,585 bit per nomor ternary, dimungkinkan untuk mengemas 20000 trit tersebut menjadi 31700 bit, meninggalkan 300 bit lebih dari cukup untuk 7 integer 16-bit saya yang tersisa.
Kedua, saya belum menerapkan mode yang diperlukan untuk menampilkan suntingan. Saya telah, secara bergantian, menerapkan mode yang mencetak matriks edit lengkap. Sangat mungkin untuk menghitung jalur edit dari matriks itu, tetapi saya tidak punya waktu sekarang untuk mengimplementasikannya.
contoh input:
contoh keluaran verbose:
sumber