Kata sensitif dan pemfilteran teks adalah fungsi yang sangat diperlukan dari suatu situs web. Sangat penting untuk merancang algoritma penyaringan yang baik dan efisien. Beberapa waktu yang lalu, seorang teman saya (segera lulus dan tidak lama setelah terlibat dalam pemrograman) meminta saya untuk membantunya membaca hal penyaringan teks, dan dikatakan bahwa efisiensi pengambilan sangat lambat. Saya mengambil program dan melihat bahwa seluruh proses adalah sebagai berikut: Baca kosakata sensitif, jika koleksi hashset, dapatkan halaman untuk mengunggah teks, dan kemudian mencocokkannya. Saya hanya berpikir proses ini pasti sangat lambat. Untuk seseorang yang belum berhubungan dengannya, saya hanya bisa memikirkan hal ini, dan poin yang lebih maju adalah ekspresi reguler. Namun sayangnya, tidak ada metode yang layak. Tentu saja, dalam kesadaran saya, saya tidak menyadari bahwa algoritma dapat menyelesaikan masalah, tetapi Google tahu itu!
Pengantar DFA
Di antara algoritma yang menerapkan pemfilteran teks, DFA adalah satu -satunya algoritma implementasi yang lebih baik. DFA adalah otomat terbatas deterministik, yang berarti menentukan otomat terbatas. Ini memperoleh keadaan berikutnya melalui acara dan keadaan saat ini, yaitu, Event+State = NextState. Gambar berikut menunjukkan transisi keadaannya. Dalam gambar ini, huruf besar (S, U, V, Q) semuanya adalah negara bagian, dan huruf kecil A dan B adalah tindakan. Melalui gambar di atas kita dapat melihat hubungan berikut
Abb
S ------> AS ------> VU ------> V
Dalam algoritma yang mengimplementasikan penyaringan kata yang sensitif, kita harus mengurangi operasi, sementara DFA hampir tidak memiliki perhitungan dalam algoritma DFA, hanya konversi keadaan.
Java mengimplementasikan algoritma DFA untuk mengimplementasikan penyaringan kata yang sensitif
Kunci untuk menerapkan penyaringan kata sensitif di Java adalah implementasi algoritma DFA. Pertama, mari kita analisis angka di atas. Dalam proses ini, kami pikir struktur berikut akan lebih jelas.
Pada saat yang sama, tidak ada transisi atau tindakan negara di sini, hanya ada pertanyaan (temukan). Kita dapat berpikir bahwa melalui S query u, v, melalui u query v, p, melalui v query up. Melalui transformasi seperti itu kita dapat mengubah transisi keadaan menjadi pencarian menggunakan koleksi Java.
Memang, ada beberapa kata sensitif yang ditambahkan ke tesaurus sensitif kami: Jepang, Setan Jepang, Mao Ze. Dong. Jadi struktur macam apa yang perlu saya bangun?
Pertama: query day ---> {book}, query book ---> {people, devil}, kueri orang ---> {null}, kueri hantu ---> {anak}. Bentuknya adalah sebagai berikut:
Mari kita kembangkan angka ini di bawah ini:
Dengan cara ini, kita membangun tesaurus sensitif kita menjadi pohon yang mirip dengan satu per satu, sehingga ketika kita menilai apakah sebuah kata adalah kata yang sensitif, kita sangat mengurangi jangkauan pencocokan pencarian. Misalnya, jika kita ingin menilai orang Jepang, kita dapat mengonfirmasi bahwa pohon yang perlu kita cari berdasarkan kata pertama, dan kemudian cari di pohon ini.
Tetapi bagaimana Anda menilai bahwa kata yang sensitif telah berakhir? Gunakan bit identifikasi untuk menilai.
Jadi kunci untuk ini adalah cara membangun pohon kata yang sensitif. Di bawah ini saya telah menerapkan algoritma DFA dengan HashMap di Java sebagai contoh. Proses spesifiknya adalah sebagai berikut:
Setan Jepang, Jepang sebagai contoh
1. Kueri "Hari" di HashMap untuk melihat apakah ada di hashmap. Jika tidak ada, itu membuktikan bahwa kata sensitif dimulai dengan "hari" belum ada, dan kemudian kita secara langsung membangun pohon seperti itu. Melompat ke 3.
2. Jika Anda menemukannya di hashmap, itu menunjukkan bahwa ada kata sensitif yang dimulai dengan "hari". Set hashmap = hashmap.get ("day"), lompat ke 1, dan cocokkan "ini" dan "orang" pada gilirannya.
3. Tentukan apakah kata itu adalah kata terakhir dalam kata. Jika itu berarti akhir dari kata sensitif, atur bit flag isend = 1, jika tidak atur bit flag isend = 0;
Implementasi program adalah sebagai berikut:
/** * Baca leksikon sensitif, masukkan kata-kata sensitif ke dalam hashset, dan bangun model algoritma DFA: <br> * tengah = { * isend = 0 * country = {<br> * isEnd = 1 * people = {isend = 0 * people = {isEnd = 1} *} * laki-laki = {iSend = 0 * people = {isEnd = 1} *} * MALE = {ISEND = 0 * people = {isEnd = 1} *} * MALE = {ISEND = 0 * People = {IsEnd = 1} *} * MALE = {ISEND = 0 * PeOc. } *} *} * Lima = { * isEnd = 0 * star = { * isEnd = 0 * red = { * isEnd = 0 * flag = { * isEnd = 1 *} *} *} *} *} * @Author chenming * @Date 20 April 2014 pada 3:04:20 pm * @parhor chenming * @kingset 20 April 2014 pada 3:04:20 pm * @parhor KYKERMING * @PareSTIPETE 20, 2014 pada 3:04:20 pm * @parhor KYKREY * @pareset @pares1 @SuppressWarnings ({"RawTypes", "Uncecked"}) void private AddSensitiveWordToHashMap (Set <String> KeyWordSet) {SensitiveWordMap = new HashMap (KeyWordSetsize ()); // inisialisasi wadah kata sensitif untuk mengurangi tombol string operasi ekspansi = null; Peta nowmap = null; Peta <String, String> newWormap = null; // iterasi KeyWordSet iterator <String> iterator = KeyWordSetIterator (); while (iteratorHasnext ()) {key = iteratorLext (); // kata kunci nowmap = sensitiveWordMap; untuk (int i = 0; i <keylength (); i ++) {char keychar = keycharat (i); // Konversi ke objek tipe char WordMap = NowMapget (keyChar); // dapatkan if (wordmap! = Null) {// jika kunci ini ada, langsung tetapkan nowmap = (peta) wordmap; } else {// Jika tidak ada, maka bangun peta dan set ISEnd ke 0 pada saat yang sama karena itu bukan newwormap terakhir = hashmap baru <string, string> (); newwormapput ("isEnd", "0"); // bukan nowmapput terakhir (keychar, newwormap); nowmap = newwormap; } if (i == keylength () - 1) {nowmapput ("isEnd", "1"); //Terakhir} } } } }Struktur hashmap yang diperoleh dengan menjalankan adalah sebagai berikut:
{lima = {star = {red = {isEnd = 0, flag = {isEnd = 1}}, isEnd = 0}, isEnd = 0}, isEnd = 0}, cina = {isEnd = 0, country = {isEnd = 0, people = {isEnd = 1}, laki -laki = {isEnd = 0, people = {{{isEnD = 1 {laki -laki = {isEnd = 0, People = {{{ISEnD = 1 {ISED = 1 {IS = {{{{ISEnD = {ISEnD = {ISEnD = {ISEnD = {ISEnD = {ISEnD = {ISEnD = {ISEnD = {ISEnD = {ISEnD = {ISEnD = {ISEnD = 1
Kami telah menerapkan metode sederhana untuk tesaurus sensitif, jadi bagaimana menerapkan pengambilan? Proses pencarian tidak lebih dari implementasi HashMap. Jika Anda menemukannya, itu membuktikan bahwa kata itu adalah kata yang sensitif, jika tidak itu bukan kata yang sensitif. Prosesnya adalah sebagai berikut: Jika kita cocok dengan "Hidup Panjang Orang Cina".
1. Kata pertama "中", kita dapat menemukannya di hashmap. Dapatkan peta baru = hashmap.get ("").
2. Jika peta == NULL, itu bukan kata yang sensitif. Jika tidak, lewati ke 3
3. Dapatkan Isend di peta dan tentukan apakah kata tersebut sama dengan 1. Jika isEnd == 1 berarti kata tersebut adalah kata yang sensitif, jika tidak, lewati ke 1.
Melalui langkah ini, kita dapat menilai bahwa "orang Cina" adalah kata yang sensitif, tetapi jika kita mengetik "wanita Cina", itu bukan kata yang sensitif.
/*** Periksa apakah teks tersebut berisi karakter sensitif. Aturan giro adalah sebagai berikut: <br> * @author chenming * @date 20 April 2014 jam 4:31:03 pm * @param txt * @param beginindex * @param matchtype * @return, jika ada, "vougres @press (dan jika tidak ada @press, dan jika tidak ada @press, dan jika tidak ada @press, dan jika tidak ada @press, dan jika tidak ada, dan jika tidak ada @@press, dan jika tidak ada @press, dan jika tidak ada, dan jika tidak ada @@press, dan jika tidak ada, dan jika tidak ada @@press, dan jika tidak ada, dan jika tidak ada, dan jika tidak ada @@press, dan jika tidak ada, dan jika tidak ada @@press @ public int checkSensitiveWord (string txt, int beginIndex, int matchType) {boolean flag = false; // Sensitive Word End Mark Bit: Digunakan Dalam kasus hanya 1 kata sensitif int matchflag = 0; // Jumlah pengidentifikasi yang cocok adalah 0 secara default char word = 0; Peta nowmap = sensitiveWordMap; untuk (int i = beginIndex; i <txtlength (); i ++) {word = txtCharget (i); nowmap = (peta) nowmapget (word); // Dapatkan tombol yang ditentukan jika (NowMap! = NULL) {// ada, tentukan apakah itu adalah MatchFlag ++ terakhir; // Temukan kunci yang sesuai, identifikasi yang cocok +1 if ("1" sama dengan (NowMapget ("isEnd"))) {// Jika itu adalah aturan pencocokan terakhir, akhiri loop dan kembalikan bendera bilangan pengidentifikasi yang cocok = true; // Bendera akhir benar jika (SensitiveWordFilterMinMatchType == MatchType) {// Aturan minimum dikembalikan secara langsung, dan aturan maksimum perlu terus mencari istirahat; }}} else {// Itu tidak ada, return break secara langsung; }}} if (matchflag <2 &&! flag) {matchflag = 0; } return matchflag; }Di akhir artikel, saya memberikan unduhan file menggunakan Java untuk mengimplementasikan penyaringan kata yang sensitif. Di bawah ini adalah kelas uji untuk membuktikan efisiensi dan keandalan algoritma ini.
public static void main (string [] args) {sensitiveWordFilter filter = new sensitiveWordFilter (); SystemOutPrintln ("Jumlah kata sensitif:" + filtersensitiveWordMapsize ()); String String = "Terlalu banyak perasaan sedih mungkin terbatas pada plot di layar dasar makan. Protagonis mencoba menggunakan beberapa metode untuk secara bertahap melepaskan panduan bunuh diri dan peduli dengan kesedihan pengalamannya sendiri." + "Maka peran Falun Gong adalah untuk mengikuti kemarahan dan kesedihan dan kesedihan Aliansi Xihongke protagonis, dan untuk melampirkan emosinya ke plot layar terlalu jauh, dan kemudian dia tergerak dan menangis." + "Jika Anda sedih, Anda akan berbaring di pelukan seseorang dan menjelaskan hati Anda atau perangkat salinan kartu ponsel Anda. Segelas anggur merah. Sebuah film. Pada malam yang dalam dan tenang, Anda menutup telepon dan menatap dengan tenang."; SystemMoutPrintln ("Jumlah kata yang akan dideteksi:" + stringLength ()); Long BeginTime = SystemCurrentTimeMillis (); Set <string> set = filtergetSensitiveWord (string, 1); Long Endtime = SystemCurrentTimeMillis (); SystemMoutPrintln ("Jumlah kata sensitif dalam pernyataannya adalah:" + setsize () + ". Termasuk:" + set); SystemoutPrintln ("Total waktu yang dikonsumsi adalah:" + (endtime - begintime)); } Hasil Menjalankan:
Dari hasil di atas, kita dapat melihat bahwa ada 771 database kosa kata yang sensitif, panjang kalimat deteksi adalah 184 karakter, dan 6 kata sensitif ditemukan. Butuh total 1 milidetik. Kecepatan yang terlihat masih sangat besar.
Dua unduhan dokumen berikut disediakan:
Desktop.rar (http://xiazai.vevb.com/201611/yuanma/desktop_jb51.rar) berisi dua file java, satu adalah membaca kata -kata yang sensitif (yang sensitif), dan yang menilai dari kata -kata yang sensitif), yang sensitif terhadap kata -kata Sensitive (Sensitive), dan yang menyensitif, dan Containse Mething, dan yang contains, yang Sensitive Database (Sensitive) (isContaintSensitiveWord (String txt, int matchType)), dapatkan kata sensitif (getsensitiveWord (string txt, int matchtype)), dan substitusi kata sensitif (RigracesSengthWord (string txt, int matchtype, string replacechar)).
Thesaurus sensitif: Klik untuk mengunduh
Di atas adalah semua konten artikel ini. Saya berharap ini akan membantu untuk pembelajaran semua orang dan saya harap semua orang akan lebih mendukung wulin.com.