เหตุใด textreuse packge ใน R จึงทำให้ถัง LSH มีขนาดใหญ่กว่า minhashes เดิม
เท่าที่ฉันเข้าใจหนึ่งในหน้าที่หลักของวิธี LSH คือการลดข้อมูลแม้จะอยู่นอกเหนือแฮชที่อยู่เบื้องหลัง ฉันใช้textreuse
แพ็คเกจใน R และฉันประหลาดใจกับขนาดของข้อมูลที่สร้างขึ้น textreuse
เป็นแพ็คเกจROpenSci ที่ผ่านการตรวจสอบโดยเพื่อนดังนั้นฉันคิดว่ามันทำงานได้อย่างถูกต้อง แต่คำถามของฉันยังคงมีอยู่
สมมติว่าฉันใช้ 256 การเรียงสับเปลี่ยนและ 64 แบนด์สำหรับฟังก์ชัน minhash และ LSH ของฉันตามลำดับ - ค่าจริงที่มักใช้ในการตรวจจับด้วยความคล้ายคลึงกันที่แน่นอน (~ 98%) ต่ำถึง 50%
หากฉันแฮชไฟล์ข้อความแบบสุ่มโดยใช้TextReuseTextDocument
(256 perms) และกำหนดให้trtd
ฉันจะมี:
object.size(trtd$minhashes)
> 1072 bytes
ตอนนี้มาสร้างที่เก็บข้อมูล LSH สำหรับวัตถุนี้ (64 แบนด์) และกำหนดให้l
ฉันจะมี:
object.size(l$buckets)
> 6704 bytes
ดังนั้นแฮชที่เก็บไว้ในที่เก็บข้อมูล LSH จึงมีขนาดใหญ่กว่ามินแฮชดั้งเดิมหกเท่า ฉันเข้าใจว่าสิ่งนี้เกิดขึ้นเนื่องจากtextreuse
ใช้การย่อย md5เพื่อสร้างแฮชที่เก็บข้อมูล
แต่สิ่งนี้ไม่สิ้นเปลือง / มากเกินไปและฉันไม่สามารถปรับปรุงได้หรือไม่? เป็นเรื่องปกติหรือไม่ที่เทคนิคการลดข้อมูลของเราจะทำให้ท้องอืดได้ถึงขนาดนี้? และการจับคู่เอกสารตามแฮชดั้งเดิมนั้นมีประสิทธิภาพมากขึ้นหรือไม่ (คล้ายกับ perms = 256 และ bands = 256) จากนั้นใช้เกณฑ์เพื่อกำจัดผลบวกปลอมหรือไม่?
โปรดทราบว่าฉันได้ตรวจสอบข้อความทั่วไปเช่นMining of Massive Datasetsแล้ว แต่คำถามนี้ยังคงเกี่ยวกับการนำไปใช้งานนี้โดยเฉพาะ นอกจากนี้โปรดทราบว่าคำถามไม่ได้เกิดจากความอยากรู้อยากเห็นเท่านั้น แต่ยังไม่จำเป็นอีกด้วย เมื่อคุณมีแฮชหลายล้านหรือหลายพันล้านแฮชความแตกต่างเหล่านี้จะมีความสำคัญ
คำตอบ
ผู้เขียนแพ็คเกจที่นี่ ใช่การใช้แฮช / แบนด์มากกว่าที่คุณต้องการจะเป็นการสิ้นเปลือง (แม้ว่าโปรดทราบว่าเรากำลังพูดถึงกิโลไบต์ที่นี่ซึ่งอาจน้อยกว่าเอกสารต้นฉบับมาก)
คำถามคือคุณต้องการอะไร? หากคุณต้องการค้นหาเฉพาะการจับคู่ที่ใกล้เคียงกัน (เช่นด้วยคะแนน Jaccard ใกล้เคียงกับ 1.0) คุณไม่จำเป็นต้องค้นหาที่ละเอียดอ่อนโดยเฉพาะ อย่างไรก็ตามหากคุณต้องการตรวจจับการแข่งขันที่มีศักยภาพที่เชื่อถือได้ซึ่งแชร์เฉพาะส่วนที่ทับซ้อนกันบางส่วนเท่านั้น (เช่นด้วยคะแนน Jaccard ที่ใกล้เคียงกับ 0) คุณต้องมีแฮช / วงดนตรีเพิ่มเติม
เนื่องจากคุณได้อ่าน MMD แล้วคุณสามารถค้นหาสมการได้ที่นั่น แต่มีฟังก์ชั่นสองอย่างในแพ็คเกจซึ่งมีการบันทึกไว้ที่นี่ซึ่งสามารถช่วยคุณคำนวณจำนวนแฮช / แบนด์ที่คุณต้องการได้ lsh_threshold()
จะคำนวณคะแนน Jaccard ตามเกณฑ์ที่จะตรวจพบ ในขณะที่lsh_probability()
จะบอกคุณว่ามีความเป็นไปได้เพียงใดที่จะตรวจพบเอกสารคู่ที่มีคะแนน Jaccard ที่ระบุ เล่นกับสองฟังก์ชั่นเหล่านี้จนกว่าคุณจะได้จำนวนแฮช / แบนด์ที่เหมาะสมที่สุดสำหรับปัญหาการค้นหาของคุณ