การกรองคำและข้อความที่ละเอียดอ่อนเป็นฟังก์ชั่นที่ขาดไม่ได้ของเว็บไซต์ จำเป็นอย่างยิ่งในการออกแบบอัลกอริทึมการกรองที่ดีและมีประสิทธิภาพ เมื่อไม่นานมานี้เพื่อนของฉัน (จบการศึกษาเร็ว ๆ นี้และไม่นานหลังจากมีส่วนร่วมในการเขียนโปรแกรม) ขอให้ฉันช่วยเขาอ่านสิ่งที่กรองข้อความและมันบอกว่าประสิทธิภาพการดึงข้อมูลช้ามาก ฉันใช้โปรแกรมมากกว่านี้และเห็นว่ากระบวนการทั้งหมดมีดังนี้: อ่านคำศัพท์ที่ละเอียดอ่อนหากคอลเลกชัน HashSet รับหน้าเพื่ออัปโหลดข้อความแล้วจับคู่ ฉันแค่คิดว่ากระบวนการนี้จะต้องช้ามาก สำหรับคนที่ไม่ได้ติดต่อกับเขาฉันสามารถนึกถึงสิ่งนี้ได้และจุดขั้นสูงคือการแสดงออกปกติ แต่น่าเสียดายที่ไม่มีวิธีใดที่เป็นไปได้ แน่นอนในจิตสำนึกของฉันฉันไม่ได้ตระหนักว่าอัลกอริทึมสามารถแก้ปัญหาได้ แต่ Google รู้ดี!
รู้เบื้องต้นเกี่ยวกับ DFA
ในบรรดาอัลกอริทึมที่ใช้การกรองข้อความ DFA เป็นอัลกอริทึมการใช้งานที่ดีกว่าเท่านั้น DFA เป็น Automaton จำกัด ที่กำหนดไว้ซึ่งหมายถึงการกำหนดค่าอัตโนมัติ จำกัด มันได้รับสถานะถัดไปผ่านเหตุการณ์และสถานะปัจจุบันนั่นคือเหตุการณ์+state = nextstate รูปต่อไปนี้แสดงการเปลี่ยนแปลงของสถานะ ในรูปนี้ตัวอักษรตัวพิมพ์ใหญ่ (s, u, v, q) เป็นสถานะทั้งหมดและตัวอักษรตัวพิมพ์เล็ก A และ B เป็นการกระทำ ผ่านภาพด้านบนเราสามารถเห็นความสัมพันธ์ต่อไปนี้
ABB
S ------> US ------> VU ------> V
ในอัลกอริทึมที่ใช้การกรองคำที่ละเอียดอ่อนเราจะต้องลดการดำเนินการในขณะที่ DFA แทบจะไม่มีการคำนวณในอัลกอริทึม DFA เพียงการแปลงสถานะเท่านั้น
Java ใช้อัลกอริทึม DFA เพื่อใช้การกรองคำที่ละเอียดอ่อน
กุญแจสำคัญในการใช้การกรองคำที่ละเอียดอ่อนใน Java คือการใช้อัลกอริทึม DFA ก่อนอื่นให้วิเคราะห์ตัวเลขด้านบน ในกระบวนการนี้เราคิดว่าโครงสร้างต่อไปนี้จะชัดเจนขึ้น
ในเวลาเดียวกันไม่มีการเปลี่ยนแปลงของรัฐหรือการกระทำที่นี่มีเพียงการสืบค้น (ค้นหา) เราสามารถคิดได้ว่าผ่าน s Query u, v, ผ่าน u uery v, p, ผ่าน v คำถามขึ้น ผ่านการเปลี่ยนแปลงดังกล่าวเราสามารถเปลี่ยนการเปลี่ยนแปลงของสถานะเป็นการค้นหาโดยใช้คอลเลกชัน Java
เป็นที่ยอมรับว่ามีคำศัพท์ที่ละเอียดอ่อนหลายคำในอรรถาภิธานที่ละเอียดอ่อนของเรา: ญี่ปุ่นปีศาจญี่ปุ่น, เหมา Ze ดง ดังนั้นฉันต้องสร้างโครงสร้างแบบไหน?
ครั้งแรก: Query Day ---> {Book}, Query Book ---> {People, Devil}, Query Person ---> {null}, Query Ghost ---> {เด็ก} รูปร่างมีดังนี้:
ขยายรูปนี้ด้านล่าง:
ด้วยวิธีนี้เราสร้างอรรถาภิธานที่ละเอียดอ่อนของเราเป็นต้นไม้ที่คล้ายกับทีละคนดังนั้นเมื่อเราตัดสินว่าคำนั้นเป็นคำที่ละเอียดอ่อนเราจะลดช่วงของการจับคู่การค้นหาอย่างมาก ตัวอย่างเช่นหากเราต้องการตัดสินภาษาญี่ปุ่นเราสามารถยืนยันได้ว่าต้นไม้ที่เราต้องค้นหาตามคำแรกจากนั้นค้นหาในต้นไม้นี้
แต่คุณจะตัดสินได้อย่างไรว่าคำที่ละเอียดอ่อนสิ้นสุดลง? ใช้บิตประจำตัวเพื่อตัดสิน
ดังนั้นกุญแจสำคัญในการนี้คือวิธีการสร้างต้นคำที่ละเอียดอ่อนเช่นนี้ ด้านล่างฉันได้ใช้อัลกอริทึม DFA กับ HashMap ใน Java เป็นตัวอย่าง กระบวนการเฉพาะมีดังนี้:
ตัวอย่างปีศาจญี่ปุ่นญี่ปุ่นเป็นตัวอย่าง
1. แบบสอบถาม "วัน" ใน HashMap เพื่อดูว่ามีอยู่ใน HashMap หรือไม่ หากไม่มีอยู่มันก็พิสูจน์ได้ว่าคำที่ละเอียดอ่อนเริ่มต้นด้วย "วัน" ยังไม่มีอยู่แล้วเราก็สร้างต้นไม้ดังกล่าวโดยตรง ข้ามไป 3.
2. หากคุณพบมันใน HashMap มันบ่งบอกว่ามีคำที่ละเอียดอ่อนเริ่มต้นด้วย "วัน" SET HASHMAP = HASHMAP.GET ("วัน") ข้ามไปที่ 1 และจับคู่ "สิ่งนี้" และ "บุคคล" ในทางกลับกัน
3. พิจารณาว่าคำนั้นเป็นคำสุดท้ายในคำหรือไม่ ถ้ามันหมายถึงจุดสิ้นสุดของคำที่ละเอียดอ่อนให้ตั้งค่าบิต FLAG ISEND = 1 มิฉะนั้นตั้งค่าบิต FLAG ISEND = 0;
การใช้งานโปรแกรมมีดังนี้:
/** * อ่านพจนานุกรมที่ละเอียดอ่อนใส่คำที่ละเอียดอ่อนลงใน HashSet และสร้างโมเดลอัลกอริทึม DFA: <br> * Middle = { * isend = 0 * Country = {<br> * isend = 1 * คน = {isend = 0 * people = {isend = 1} *} } *} *} * five = { * isend = 0 * star = { * isend = 0 * red = { * isend = 0 * flag = { * isend = 1 *} *} *} *} *} * @author chenming * @date 20 เมษายน 2014 ที่ 3:04:20 pm * @param @suppresswarnings ({"rawtypes", "unchecked"}) โมฆะส่วนตัว AddSensitiveWordToHashMap (Set <String> keywordSet) {SensitiveWordMap = ใหม่ HASHMAP (KeywordSetSize ()); // เริ่มต้นคอนเทนเนอร์คำที่ละเอียดอ่อนเพื่อลดคีย์สตริงการทำงานของการขยายตัว = null; แผนที่ nowmap = null; แผนที่ <สตริงสตริง> newWormap = null; // iteration keywordset iterator <String> iterator = keywordSetIterator (); ในขณะที่ (iteratorhasnext ()) {key = iteratorNext (); // คำหลัก nowmap = SensitiveWordMap; สำหรับ (int i = 0; i <keylength (); i ++) {char keychar = keycharat (i); // แปลงเป็น Object-Type Object WordMap = NowMapget (keychar); // รับ if (wordmap! = null) {// ถ้าคีย์นี้มีอยู่ให้กำหนด nowmap = (แผนที่) WordMap โดยตรง; } else {// ถ้าไม่มีอยู่ให้สร้างแผนที่และตั้งค่าจะเป็น 0 ในเวลาเดียวกันเพราะมันไม่ใช่ newWormap สุดท้าย = ใหม่ hashmap <string, string> (); Newwormapput ("isend", "0"); // ไม่ใช่ NowMapput สุดท้าย (keychar, newwormap); nowmap = newWormap; } if (i == keyLength () - 1) {nowmapput ("isend", "1"); //ล่าสุด} } } } }โครงสร้าง hashmap ที่ได้รับจากการทำงานมีดังนี้:
{five = {star = {red = {isend = 0, flag = {isend = 1}}, isend = 0}, isend = 0}, isend = 0}, จีน = {isend = 0, ประเทศ = {isend = 0, คน = {isend = 1}
เราได้ใช้วิธีง่ายๆสำหรับอรรถาภิธานที่ละเอียดอ่อนดังนั้นจะใช้การดึงข้อมูลได้อย่างไร? กระบวนการค้นหาไม่มีอะไรมากไปกว่าการใช้ HashMap หากคุณพบว่ามันพิสูจน์ได้ว่าคำนั้นเป็นคำที่ละเอียดอ่อนมิฉะนั้นจะไม่ใช่คำที่ละเอียดอ่อน กระบวนการนี้มีดังนี้: ถ้าเราจับคู่ "Long Live the Chinese People"
1. คำแรก "中" เราสามารถค้นหาได้ใน HashMap รับแผนที่ใหม่ = hashmap.get ("")
2. ถ้าแผนที่ == null มันไม่ใช่คำที่ละเอียดอ่อน มิฉะนั้นข้ามไปที่ 3
3. รับ isend ในแผนที่และตรวจสอบว่าคำนั้นเท่ากับ 1 ถ้า isend == 1 หมายความว่าคำนั้นเป็นคำที่ละเอียดอ่อนหรือไม่หรือข้ามไปที่ 1
ผ่านขั้นตอนนี้เราสามารถตัดสินได้ว่า "คนจีน" เป็นคำที่ละเอียดอ่อน แต่ถ้าเราพิมพ์ "ผู้หญิงจีน" มันไม่ใช่คำที่ละเอียดอ่อน
/*** ตรวจสอบว่าข้อความมีอักขระที่ละเอียดอ่อนหรือไม่ กฎการตรวจสอบมีดังนี้: <br> * @author Chenming * @date 20 เมษายน 2014 เวลา 4:31:03 PM * @param txt * @param startIndex * @param matchtype * @return ถ้ามันมีอยู่ "RawTypes"}) Int PublicensitiveWord (String txt, int beginindex, int matchType) {boolean flag = false; // บิตจุดสิ้นสุดคำที่ละเอียดอ่อน: ใช้ในกรณีที่มีเพียง 1 บิตของคำศัพท์ที่ละเอียดอ่อน int matchflag = 0; // จำนวนตัวระบุที่ตรงกันคือ 0 โดยเริ่มต้นถ่านคำ = 0; แผนที่ nowmap = sensitivewordmap; สำหรับ (int i = startIndex; i <txtLength (); i ++) {word = txtcharat (i); nowmap = (แผนที่) nowmapget (word); // รับคีย์ที่ระบุ if (nowmap! = null) {// มีอยู่ให้ตรวจสอบว่ามันเป็น matchflag ++ สุดท้าย; // ค้นหาคีย์ที่สอดคล้องกันตัวระบุที่ตรงกัน +1 ถ้า ("1" เท่ากับ (nowmapget ("isend"))) {// ถ้าเป็นกฎการจับคู่สุดท้ายให้จบลูป // ธงท้ายเป็นจริงถ้า (SensitiveWordFilterMinMatchType == MatchType) {// กฎขั้นต่ำจะถูกส่งคืนโดยตรงและกฎสูงสุดจำเป็นต้องมองหาการหยุดพักต่อไป }}} else {// มันไม่มีอยู่, ส่งคืน break โดยตรง; }}} if (MatchFlag <2 &&! Flag) {MatchFlag = 0; } return matchflag; -ในตอนท้ายของบทความฉันให้ดาวน์โหลดไฟล์โดยใช้ Java เพื่อใช้การกรองคำที่ละเอียดอ่อน ด้านล่างนี้เป็นคลาสทดสอบเพื่อพิสูจน์ประสิทธิภาพและความน่าเชื่อถือของอัลกอริทึมนี้
โมฆะคงที่สาธารณะหลัก (สตริง [] args) {ตัวกรอง sensitiveWordFilter = new SensitiveWordFilter (); SystemOutPrintln ("จำนวนคำที่ละเอียดอ่อน:" + filtersitiveSitiveDodmapsize ()); String String = "ความรู้สึกเศร้ามากเกินไปอาจถูก จำกัด อยู่ที่แปลงบนหน้าจอฐานการให้อาหารตัวเอกของตัวเอกพยายามใช้วิธีการบางอย่างเพื่อค่อยๆปล่อยคู่มือการฆ่าตัวตายและใส่ใจเกี่ยวกับความโศกเศร้าของประสบการณ์ของเขาเอง" + "จากนั้นบทบาทของ Falun Gong คือการติดตามความโกรธของ Xihongke Alliance และความเศร้าโศกของตัวเอกของตัวเอก + "ถ้าคุณเศร้าคุณจะนอนอยู่ในอ้อมแขนของใครบางคนและอธิบายหัวใจหรืออุปกรณ์คัดลอกการ์ดโทรศัพท์มือถือของคุณไวน์แดงสักแก้วภาพยนตร์ในคืนที่ลึกและเงียบสงบคุณปิดโทรศัพท์และจ้องมองอย่างเงียบ ๆ "; SystemOutPrintln ("จำนวนคำที่ตรวจพบ:" + stringLength ()); Long Begintime = SystemCurrentTimeMillis (); ตั้งค่า <string> set = filterGetSensitiveWord (สตริง, 1); endtime long = systemCurrentTimeMillis (); SystemOutPrintln ("จำนวนคำที่ละเอียดอ่อนในคำสั่งคือ:" + setSize () + "รวม:" + set); SystemoutPrintln ("ใช้เวลาทั้งหมดคือ:" + (endtime - begintime)); - ผลการทำงาน:
จากผลลัพธ์ข้างต้นเราจะเห็นได้ว่ามีฐานข้อมูลคำศัพท์ที่ละเอียดอ่อน 771 ฐานความยาวของประโยคการตรวจจับคือ 184 ตัวอักษรและพบคำที่ละเอียดอ่อน 6 คำ ใช้เวลาทั้งหมด 1 มิลลิวินาที ความเร็วที่มองเห็นยังคงมีอยู่มาก
มีการดาวน์โหลดเอกสารสองฉบับต่อไปนี้:
desktop.rar (http://xiazai.vevb.com/201611/yuanma/desktop_jb51.rar) มีไฟล์ Java สองไฟล์หนึ่งไฟล์คือการอ่านฐานข้อมูลคำศัพท์ที่ละเอียดอ่อน (isContaintSensitiveWord (String txt, int matchType), การได้รับคำที่ละเอียดอ่อน (getSensitiveWord (สตริง txt, int matchType)) และแทนที่คำที่ละเอียดอ่อน (แทนที่คำตอบ (สตริง txt, int matchtype, สตริง
อรรถาภิธานที่ละเอียดอ่อน: คลิกเพื่อดาวน์โหลด
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่ามันจะเป็นประโยชน์ต่อการเรียนรู้ของทุกคนและฉันหวังว่าทุกคนจะสนับสนุน wulin.com มากขึ้น