Local File Search Engine

เครื่องมือค้นหาไฟล์ในเครื่อง

นี่เป็นการใช้งานพื้นฐานของเครื่องมือค้นหาไฟล์ที่ใช้ python เพื่อตอบแบบสอบถามในไฟล์ข้อความบนระบบโลคัล เราได้ใช้ "การถ่วงน้ำหนักคำศัพท์ tf-idf" และ "ความคล้ายคลึงโคไซน์" เพื่อจัดอันดับความเกี่ยวข้องของเอกสารที่ตรงกัน การคำนวณ tf-idf ได้รับการคำนวณล่วงหน้าทำให้การค้นหาเร็วขึ้นมาก นอกจากนี้ยังใช้เพื่อเพิ่มความเร็วในการค้นหา Stemming (Porter Stemmer) มีการจัดเตรียมอินเทอร์เฟซผู้ใช้พื้นฐานโดยใช้ไลบรารี Tkinter ของ Python

คุณสมบัติ

• เนื่องจากการแสดงเวกเตอร์ใช้ในการคำนวณความคล้ายคลึงกันระหว่างเอกสารสองฉบับ วิธีการจึงรองรับ การสืบค้นคำเดียว และ การสืบค้นหลายคำ
• ข้อความค้นหาแบบวลี หรือการทำงานแบบตรงทั้งหมดก็อยู่ที่นั่นเช่นกัน เช่น “Search engine” เมื่อพิมพ์เครื่องหมายคำพูดจะแสดงผลการจับคู่แบบตรงทั้งหมด แทนที่จะรวมการจับคู่ระหว่าง “search” และ “engine”

วิ่งยังไง?

 python2 createIndex_tfidf.py stopwords.dat testIndex.dat titleIndex.dat

createIndex_tfidf.py จะทำงานเพียงครั้งเดียวเพื่อคำนวณค่า tdf-idf บนคลังข้อมูล

 python2 queryIndex_tfidf.py stopwords.dat testIndex.dat titleIndex.dat

สร้าง สคริปต์ดัชนี (createIndex_tfidf.py)

ไฟล์ที่แตกต่างกันสามไฟล์โดยรวมจะถูกสร้างขึ้นในขั้นตอนนี้:

• titleIndex.dat

  ไฟล์นี้จัดเก็บ docId (รหัสเอกสาร) ที่ไม่ซ้ำกันซึ่งกำหนดให้กับแต่ละเอกสารในคลังข้อมูล

• testIndex.dat

ในที่นี้ ไฟล์ดัชนีจะถูกสร้างขึ้น (หรือที่เรียกว่าโครงสร้างข้อมูลดัชนีแบบกลับหัว) ซึ่งมีข้อมูลเกี่ยวกับคำศัพท์เฉพาะทั้งหมด (ยกเว้นคำหยุด) ที่ปรากฏในเอกสารทั้งหมด เอกสารแต่ละฉบับจะได้รับรหัสที่ไม่ซ้ำกันโดยเริ่มจาก 0 โดยจัดเก็บไว้ใน titleIndex ข้อมูล ข้อมูลเกี่ยวกับคำศัพท์จะถูกเก็บไว้ในไฟล์ดัชนีดังนี้: term|docID0:pos1,pos2;docID1:pos3,pos4,pos5;…..|tf0,tf1,tf2...|idf ที่นี่ tf0,tf1,tf2 แสดงถึงความถี่ของเทอมใน docID0, docID1, docID2 ตามลำดับ idf แสดงถึงความถี่ของเอกสารผกผัน และ pos1 แสดงถึงตำแหน่งของคำในเอกสารที่เกี่ยวข้อง และอื่นๆ

• lines.dat

  ไฟล์นี้จัดเก็บข้อมูลเกี่ยวกับบรรทัดที่มีคำนั้นปรากฏในเอกสารต่างๆ ข้อมูลบรรทัดนี้แสดงเป็น : term|docID0:line1,line2;docID1:line3,line4,line5

  ก่อนที่จะสร้างไฟล์เหล่านี้ ข้อกำหนดทั้งหมดของเอกสารจะถูกตรวจสอบในรายการคำหยุด หากคำนั้นปรากฏในคำหยุด คำนั้นจะถูกข้ามไป ไม่เช่นนั้นข้อมูลจะถูกจัดเก็บไว้ในไฟล์ด้านบนเหล่านี้ นอกจากนี้ แต่ละคำจะถูกสร้างขึ้นโดย Porter Stemmer ก่อนที่จะถูกเพิ่มลงในดัชนี

สคริปต์ดัชนีแบบสอบถาม (queryIndex_tfidf.py)

ในสิ่งนี้ ก่อนอื่นเลย ข้อมูลทั้งหมดจากไฟล์ lines.dat,titleIndex.dat และ testIndex.dat จะถูกเก็บไว้อีกครั้งโดยใช้พจนานุกรมใน Python

ขณะนี้ Queries ประเภทต่างๆ ที่รองรับได้แก่:

• One Word Queries (OWQ) นี่คือแบบสอบถามแบบคำเดียวและผลลัพธ์คือรายการเอกสารที่มีคำที่ถามพร้อมกับหมายเลขบรรทัดที่มีคำนั้นอยู่ในเอกสารที่เกี่ยวข้อง

• การสืบค้นคำหลายคำ (MWQ) ข้อมูลเข้าใน MWQ จะเป็นลำดับของคำ และผลลัพธ์คือรายการเอกสารที่มีคำค้นหาใดๆ พร้อมด้วยหมายเลขบรรทัด

• การสืบค้นแบบวลี (PQ) การป้อนข้อมูลใน PQ จะเป็นลำดับของคำอีกครั้ง และเอกสารที่ตรงกันคือเอกสารที่มีคำสืบค้นทั้งหมดตามลำดับที่ระบุ

การจัดอันดับเอกสาร

ตอนนี้เราพบรายการเอกสารที่มีการสืบค้นแล้ว ก็ถึงเวลาจัดอันดับเอกสารเหล่านั้น รูปแบบการจัดอันดับที่เราใช้ที่นี่จะขึ้นอยู่กับ tf-idf Tf-Idf เป็นรูปแบบการถ่วงน้ำหนักที่กำหนดน้ำหนักให้กับแต่ละเทอมในเอกสารโดยพิจารณาจากความถี่ของเทอม (tf) และความถี่ของเอกสารผกผัน (idf) คำที่มีคะแนนน้ำหนักสูงกว่าจะถือว่ามีความสำคัญมากกว่า เป็นหนึ่งในแผนการถ่วงน้ำหนักที่ได้รับความนิยมมากที่สุดในการเรียกข้อมูล

ความถี่ภาคเรียน(Tf)

ความถี่ของคำ (tf) ของคำนั้นเป็นเอกสารเฉพาะ โดยพื้นฐานแล้วมันคือจำนวนครั้งของคำว่า t ในเอกสาร D การเลือก tf เป็นพารามิเตอร์ค่อนข้างสมเหตุสมผล เนื่องจากเมื่อคำใดปรากฏในเอกสารมากขึ้น คำนั้นจะมีความสำคัญมากขึ้น เราสามารถแสดงเอกสารด้วยเวกเตอร์ที่มีขนาดเท่ากับหมายเลข ของคำศัพท์เฉพาะในเอกสาร และแต่ละค่าแสดงถึงจำนวนคำศัพท์ในเอกสารที่กำหนด การแสดงเอกสารเป็นเวกเตอร์ในพื้นที่เวกเตอร์ทั่วไปเรียกว่าแบบจำลองพื้นที่เวกเตอร์ และถือเป็นพื้นฐานสำคัญในการดึงข้อมูล แต่นี่คือข้อเสียเปรียบประการหนึ่ง เนื่องจากเอกสารมีขนาดใหญ่ขึ้น น้ำหนักของ tf จะเพิ่มขึ้นตามความถี่ของคำศัพท์จะเพิ่มขึ้น ดังนั้นเอกสารที่มีข้อมูลเดียวกันกับเอกสารอื่นที่คัดลอกมากกว่าหนึ่งครั้งจะถือว่ามีความสำคัญมากกว่า เพื่อกำจัดข้อเสียเปรียบนี้ เราจะแบ่งแต่ละค่าในเวกเตอร์ตามบรรทัดฐาน เพื่อให้เวกเตอร์กลายเป็นเวกเตอร์หน่วย

ความถี่ของเอกสารผกผัน (Idf)

เราไม่สามารถใช้ความถี่ของคำศัพท์ในการคำนวณน้ำหนักของคำศัพท์ในเอกสารเท่านั้น เนื่องจาก tf ถือว่าคำศัพท์ทั้งหมดมีความสำคัญเท่าเทียมกัน อย่างไรก็ตาม คำบางคำเกิดขึ้นน้อยมากและมีการเลือกปฏิบัติมากกว่าคำอื่นๆ หากเราใช้ tf เป็นหน่วยวัดในการจัดอันดับเพียงอย่างเดียว ถ้าเราค้นหาหัวข้อ เช่น คลื่นเสียง เราอาจจะได้รับเอกสารจำนวนมากที่มีคลื่นแสงและคลื่นอื่นๆ เนื่องจากความถี่ของคำเป็นเพียงพารามิเตอร์เท่านั้น

เพื่อลดผลกระทบนี้ เราใช้ความถี่ของเอกสารผกผัน ความถี่ของเอกสารของคำนั้นโดยทั่วไปคือจำนวนเอกสารที่มีคำนั้น ดังนั้นความถี่เอกสารผกผัน (idf) ของคำศัพท์คือจำนวนเอกสารในคลังข้อมูลหารด้วยความถี่เอกสารของคำศัพท์ โดยทั่วไปพบว่าปัจจัยของ idf ค่อนข้างมาก และจะได้ผลลัพธ์ที่ดีกว่าหากเราใช้ log(idf) เนื่องจากบันทึกเป็นฟังก์ชันที่เพิ่มขึ้น เราจึงสามารถใช้มันได้โดยไม่ขัดขวางผลลัพธ์ของเรา

การให้คะแนน Tf-Idf

เราได้กำหนดทั้ง tf และ idf แล้ว และตอนนี้เราสามารถรวมสิ่งเหล่านี้เข้าด้วยกันเพื่อสร้างคะแนนสูงสุดของเทอม t ในเอกสาร d เราจะแสดงเอกสารเป็นเวกเตอร์อีกครั้ง โดยแต่ละรายการจะเป็นน้ำหนัก tf-idf ของคำที่เกี่ยวข้องในเอกสาร น้ำหนัก tf-idf ของเทอม t ในเอกสาร d เป็นเพียงการคูณ tf ด้วย idf

ตอนนี้เราได้สร้างเวกเตอร์ของแต่ละเอกสารตามน้ำหนัก tf-idf แล้ว ถึงเวลาตอบคำถามโดยใช้เวกเตอร์เอกสารที่กำหนด ก่อนอื่น เราจะสร้างเวกเตอร์การสืบค้นบนพื้นฐานที่คล้ายกันเมื่อเราสร้างเวกเตอร์เอกสาร เช่น ตามคะแนน tf-idf (พิจารณาการสืบค้นเอกสารด้วยตัวมันเอง) ตอนนี้เรามีเวกเตอร์การสืบค้นพร้อมแล้ว เราจะค้นหาเอกสารทั้งหมดที่มีการสืบค้นของเรา ตอนนี้เราจะหาดอทโปรดัคของเวกเตอร์แบบสอบถามและเวกเตอร์เอกสารซึ่งมีแบบสอบถามอยู่ ยิ่ง จุด ผลิตภัณฑ์ที่คล้ายกันมากเท่าไรก็คือเวกเตอร์แบบสอบถามที่มีเวกเตอร์เอกสาร ซึ่งหมายความว่ามุมระหว่างเวกเตอร์เอกสารและเวกเตอร์แบบสอบถามมีขนาดเล็ก เทคนิคการค้นหาความคล้ายคลึงกันระหว่างแบบสอบถามและเอกสารนี้เรียกว่าความคล้ายคลึงโคไซน์

ข้อบกพร่องของโครงการ

• ไม่สามารถปรับขนาดได้เมื่อขนาดคำศัพท์ใหญ่เกินไปเนื่องจากเวกเตอร์เอกสารมีขนาด = ขนาดคำศัพท์
• จนถึงตอนนี้รองรับเฉพาะไฟล์ข้อความเท่านั้น