Partial string matching using bit-sliced signature files

Abstract

The partial string searching using text pattern matching in unformatted data normally requires much processing time because it compares an indicated query with all data which are usually in large size. A signature file represents an actual file in searching. Since signature file size is much smaller than an actual files size, the processing time is faster. However, signature file algorithm cannot be directly use in partial searching. This thesis proposes a new approach to the use of signature files algorithm in partial string searching. We develop a searching algorithm called Wildcard Searching with Signature File (WSSF). WSSF creates two signature file that will be used in partial string searching. From theoretical analysis an experimentation of WSSF with actual data, we found that WSSF is more efficient than any existing text pattern matching algorithms when applied to partial string searching. This thesis presents how WSSF works and its procedures in detail. The researches on WSSF, its experimentation with real data, and its results are discussed. Moreover, suggestions and comments for improving WSSF in using this algorithm in the real world are also presented.

ปกติการค้นหาบางส่วนของคำ (Partial String Searching) ในข้อมูลที่ไม่มี รูปแบบต้องใช้เวลาในการประมวลผลมาก เมื่อใช้เทคนิคของการค้นหาแบบเปรียบเทียบ กับข้อมูลโดยตรง (Text Pattern Matching) เพราะจะต้องค้นหาเปรียบเทียบกับ ข้อมูลทั้งหมดซึ่งมักจะมีขนาดใหญ่ แฟ้มข้อมูลลายเซ็นจะทำหน้าที่เป็นตัวแทนของข้อมูลจริง ซึ่งสามารถจะใช้ในการค้นหาได้เช่นเดียวกับข้อมูลจริง แต่จะมีขนาดเล็กกว่าข้อมูลจริง มาก จึงทำให้การค้นหาทำได้เร็วกว่า อย่างไรก็ตาม แฟ้มข้อมูลลายเซ็นไม่สามารถจะใช้ กับการค้นหาแบบบางส่วนได้โดยตรง งานวิทยานิพนธ์นี้จะได้นำเสนอวิธีการที่จะใช้แฟ้ม ข้อมูลลายเซ็นในการค้นหาแบบบางส่วน วิธีการค้นหาที่เรียกว่า WSSF (Wildcard Searching with Signature Files) ได้ถูกพัฒนาขึ้น WSSF จะสร้างแฟ้มข้อมูล ลายเซ็น 2 แฟ้ม ซึ่งจะสนับสนุนการค้นหาแบบบางส่วนได้ จากการวิเคราะห์และทดลอง กับข้อมูลจริงพบว่า WSSF ให้ประสิทธิภาพในการค้นหาแบบบางส่วนได้ดีกว่าวิธีการปกติ วิทยานิพนธ์ฉบับนี้จะได้นำเสนอวิธีการของ WSSF โดยละเอียด พร้อมกับการ วิเคราะห์การนำไปทดลองกับข้อมูลจริง พร้อมทั้งผลการทดลองที่ได้ นอกจากนี้ยังจะได้ นำเสนอข้อแนะนำต่างๆ ในการที่จะปรับปรุง WSSF ให้ดีขึ้นสำหรับการใช้งานจริง