Dalam skenario seperti forum dan ruang obrolan, untuk memastikan pengalaman pengguna, kita sering perlu memblokir banyak kata yang buruk. Untuk pencarian kata kunci tunggal, secara alami lebih efisien dalam indeksof dan metode reguler. Namun, jika ada banyak kata kunci, jika Anda berulang kali memanggil indeks atau kata -kata reguler untuk mencocokkan teks lengkap, konsumsi kinerja sangat tinggi. Karena string target biasanya berukuran besar, perlu untuk memastikan bahwa hasilnya diperoleh dalam satu traversal. Berdasarkan kebutuhan seperti itu, mudah untuk memikirkan cara untuk mencocokkan setiap karakter dalam seluruh teks secara berurutan. Misalnya, untuk teks ini: "Mike Jordan mengatakan" lakukan saja ", jadi Mark telah menjadi pembuat kode." Jika kata kunci kami adalah "Mike" dan "Mark", maka Anda dapat melintasi seluruh kalimat. Saat Anda menemukan "M", maka lihat apakah Anda dapat mencocokkan "I" atau "A". Jika Anda dapat mencocokkan sampai akhir, Anda akan berhasil menemukan kata kunci, jika tidak, Anda akan terus melintasi. Maka struktur kata kunci harus seperti ini:
var kata kunci = {m: {i: {k: {e: {end: true}}}}, a: {r: {k: {end: true}}}}}}Dari yang di atas, kita dapat melihat bahwa data ini adalah struktur pohon, dan masih memakan waktu untuk membuat struktur pohon berdasarkan grup kata kunci, sementara kata kunci sudah diberikan, sehingga Anda dapat membuat struktur data seperti itu sebelumnya sebelum dicocokkan. Kodenya adalah sebagai berikut:
fungsi buildtree (kata kunci) {var tblcur = {}, key, str_key, length, j, i; var tblroot = tblCur; untuk (j = kata kunci.length - 1; j> = 0; j - = 1) {str_key = kata kunci [j]; Panjang = str_key.length; untuk (i = 0; i <panjang; i += 1) {key = str_key.charat (i); if (tblcur.hasownproperty (key)) {tblcur = tblcur [key]; } else {tblCur = tblCur [key] = {}; }} tblcur.end = true; // kata kunci terakhir tblcur = tblroot; } return tblroot;}Kode ini menggunakan pernyataan kontinu: tblCur = tblCur [key] = {}. Perintah eksekusi di sini adalah perintah eksekusi pernyataan. Karena tingkat operasi [] lebih tinggi dari =, hal pertama adalah membuat atribut kunci dalam objek TBLCUR. Dikombinasikan dengan tblroot = tblCur = {}, urutan eksekusi adalah:
var tblroot = tblCur = {}; tblroot = tblCur; tblCur ['key'] = tidak terdefinisi; // sekarang tblroot = {key: tidak terdefinisi} tblcur ['key'] = {}; tblCur = tblCur ['key'];Melalui kode di atas, data kueri yang diperlukan dibangun. Mari kita lihat metode penulisan antarmuka kueri.
Untuk setiap kata dari string target, kita mulai dari atas kata kunci ini. Pertama, kata kunci [a]. Jika ada, lihat kata kunci [a] [b]. Jika kata kunci terakhir [a] [b] ... [x] = true, itu berarti kecocokan berhasil. Jika kata kunci [a] [b] ... [x] = tidak terdefinisi, maka pencocokan akan dimulai kembali dari posisi berikutnya.
Pencarian fungsi (konten) {var tblcur, p_star = 0, n = content.length, p_end, match, // apakah akan menemukan match_key, match_str, arrmatch = [], // penyimpanan hasil arrlength = 0; // indeks panjang arrmatch while (p_star <n) {tblcur = tblroot; // melacak kembali ke root p_end = p_star; match_str = ""; cocok = false; do {match_key = content.charat (p_end); if (! (tblCur = tblCur [match_key])) {// akhir pertandingan ini P_Star += 1; merusak; } else {match_str += match_key; } p_end += 1; if (tblcur.end) // apakah akan mencocokkan dengan ekor {match = true; }} while (true); if (match) {// maksimum match arrmatch [arrlength] = {key: match_str, begin: p_star - 1, end: p_end}; arrlength += 1; p_star = p_end; }} return arrmatch;}Di atas adalah inti dari seluruh sistem pencocokan kata kunci. Di sini kami menggunakan fitur bahasa JS dengan sangat baik, dan efisiensinya sangat tinggi. Saya menggunakan 500.000 kata "Soushen ji" untuk mengujinya dan menemukan 300 idiom yang diberikan. Efek pencocokan sekitar 1 detik. Yang penting, karena teks target dilalui sekaligus, panjang teks target memiliki sedikit efek pada waktu kueri. Jumlah kata kunci yang memiliki dampak yang lebih besar pada waktu kueri adalah jumlah kata kunci. Setiap kata dalam teks target melintasi kata kunci, sehingga memiliki dampak tertentu pada kueri.
Analisis sederhana
Saya kira Anda bertanya -tanya ketika Anda membaca artikel di atas. Anda dapat melintasi semua kata kunci untuk setiap kata. Bahkan jika beberapa kata kunci sebagian sama, cukup memakan waktu untuk melintasi mereka sepenuhnya. Namun, sifat -sifat objek dalam JS dibangun menggunakan tabel hash. Data struktur ini sangat berbeda dari traversal array sederhana, dan efisiensinya jauh lebih tinggi daripada traversal array berbasis pesanan. Beberapa siswa mungkin tidak terbiasa dengan struktur data, jadi saya akan berbicara secara singkat tentang konten yang relevan dari tabel hash.
Pertama, mari kita lihat penyimpanan data.
Penyimpanan data dalam memori terdiri dari dua bagian, satu adalah nilainya dan yang lainnya adalah alamatnya. Pikirkan ingatan sebagai kamus Xinhua, penjelasan kata adalah nilainya, dan direktori adalah alamatnya. Kamus diurutkan oleh Pinyin, misalnya, "Ni" dengan pengucapan yang sama diatur dalam bagian yang sama, yaitu, array diatur dengan rapi di area memori. Struktur ini adalah array, Anda dapat menentukan "ni" nomor 1 dan 10 untuk mengaksesnya. Diagram struktur adalah sebagai berikut:
Keuntungan dari array adalah bahwa mereka mudah dilintasi, dan mereka dapat secara langsung mengakses data yang sesuai melalui subskrip. Tetapi sangat sulit untuk menambah atau menghapus item tertentu. Misalnya, jika Anda ingin menghapus item 6, maka data setelah item 5 harus dipindahkan ke depan dengan satu posisi. Jika Anda ingin menghapus bit pertama, seluruh array perlu dipindahkan, yang banyak mengkonsumsi.
Untuk menyelesaikan masalah penambahan dan penghapusan array, daftar tertaut muncul. Jika kita membagi nilai menjadi dua bagian, bagian digunakan untuk menyimpan nilai asli, dan bagian lainnya digunakan untuk menyimpan alamat, yang menunjuk ke struktur lain yang sama, dan sebagainya, membentuk daftar yang ditautkan. Strukturnya adalah sebagai berikut:
Dapat dilihat dengan jelas dari gambar di atas bahwa menambahkan dan menghapus daftar yang ditautkan sangat sederhana. Cukup tulis ulang item target dan item berikutnya dari item sebelumnya dan itu akan selesai. Namun, sangat sulit untuk menanyakan nilai suatu barang. Anda harus melintasi itu pada gilirannya untuk mengakses lokasi target.
Untuk mengintegrasikan keunggulan kedua struktur ini, Anda harus memikirkan struktur berikut.
Struktur data ini adalah struktur tabel hash. Alamat header dari daftar tertaut disimpan dalam array, dan tabel data dua dimensi dapat dibentuk. Adapun bagaimana data didistribusikan, ini adalah algoritma hashing, dan terjemahan reguler harus menjadi algoritma hashing. Meskipun ada banyak jenis algoritma, pada prinsipnya, mereka menyelesaikan kunci melalui fungsi, dan kemudian menempatkan data sesuai dengan hasil yang diperoleh dari solusi. Dengan kata lain, pemetaan terbentuk antara kunci dan alamat yang sebenarnya, jadi pada saat ini kita tidak lagi mengakses array dengan mengganti array atau hanya melintasi itu, tetapi sebaliknya menemukan data dengan fungsi terbalik dari fungsi hash. Objek dalam JS adalah struktur hash. Misalnya, kami mendefinisikan OBJ. Obj.name melalui hashing, dan posisinya dalam memori mungkin 90 pada gambar di atas. Ketika kami ingin mengoperasikan obj.name, lapisan yang mendasarinya akan secara otomatis membantu kami menemukan posisi 90 melalui algoritma hash, yang berarti bahwa kami langsung mulai mencari daftar yang ditautkan dari 12 item array, daripada melintasi seluruh blok memori dari 0.
Tentukan objek obj {key: value} di js. Kunci dikonversi menjadi string dan kemudian hash untuk mendapatkan alamat memori, dan kemudian memasukkan nilainya ke dalamnya. Ini memungkinkan kami untuk memahami mengapa kami dapat menambah dan menghapus atribut sesuka hati, dan mengapa kami juga dapat menetapkan atribut ke array di JS, dan tidak ada apa yang disebut array lintas batas.
Dalam situasi di mana volume data besar, tabel hash memiliki keuntungan yang sangat jelas karena mengurangi banyak perhitungan yang tidak perlu melalui algoritma hash. Optimalisasi kinerja yang disebut sebenarnya untuk membuat komputer lebih sedikit komputasi; Optimalisasi terbesar adalah tidak menghitung!
Optimalisasi algoritma
Sekarang setelah Anda memahami implementasi algoritma yang mendasari, Anda dapat mempertimbangkan mengoptimalkan algoritma dalam retrospeksi. Namun, sebelum mengoptimalkan, Anda harus menekankan satu hal: jangan secara membabi buta mengejar kinerja! Misalnya, dalam hal ini, kita dapat mencocokkan hingga 5.000 kata paling banyak, sehingga algoritma yang ada sudah cukup, dan semua optimisasi tidak perlu. Alasan mengapa saya masih berbicara tentang optimasi adalah untuk meningkatkan pemahaman saya tentang algoritma dan program, daripada benar -benar melakukan optimasi 1MS.
Kami menemukan bahwa tidak ada kata kunci kami yang memiliki satu kata, jadi itu akan menjadi sia -sia bagi kami untuk melintasi kata kunci sesuai dengan unit satu kata. Optimalisasi di sini adalah untuk pra-statistik panjang maksimum dan minimum kata kunci, dan mencari dalam satuan panjang minimum setiap kali. Misalnya, kata kunci dalam test case saya adalah idiom, dan yang terpendek adalah 4 karakter, jadi setiap kali saya cocok, saya cocok dengan 4 karakter bersama -sama. Jika saya menekan, terus cari secara mendalam untuk menemukan panjang maksimum. Dengan kata lain, ketika kita pertama kali membangun pohon, pertama kali dibangun dengan panjang minimum, dan kemudian ditambahkan kata demi kata.
Perhitungan sederhana dibuat. Menurut kasus uji kami, untuk 300 idiom, kami hanya perlu membandingkan satu kata sekali, dan untuk permintaan satu kata, kami perlu membandingkan 4 kali, dan setiap perbandingan yang harus kami akses struktur pohon kami, yang merupakan konsumsi kinerja yang dapat dihindari. Lebih penting lagi, perbandingan di sini bukan perbandingan string. Kata kunci kami di sini semuanya ada sebagai kunci, dan efeknya sama dengan kunci dalam OBJ, yang hashed kunci dan kemudian mengakses alamat yang sesuai! Jadi jangan khawatir tentang perbedaan antara membandingkan satu kata dan membandingkan empat kata. Kami tidak membandingkan string!
Itu semua tentang mencocokkan beberapa kata kunci. Saya tidak akan memposting versi kode yang dioptimalkan karena umumnya tidak tersedia.