Efficient document clustering using suffix array

Abstract

Nowadays the Search Engine is popular among users in searching the information on the Internet. However, the results are sometimes unmatched with users' need or placed in the latter pages of the document, and the searching wastes their time to arrive at. Such problems have been solved by an idea of clustering that is grouping documents having the same or similar content together. A Suffix Tree Clustering (STC), one of the most popular clustering techniques currently in use, is an efficient technique, which employs the Suffix Tree Algorithm in performing a string matching. The shortfall of the technique is that it requires an extensive memory to execute and due to the complexity of the implementation, some errors may occur. This thesis solves these technical problems by using Suffix Array instead of Suffix Tree. Similar to the Suffix Tree Clustering technique, the Suffix Array Clustering technique employs a Suffix Array Algorithm in doing a string matching. From our intensive study and program development for the Suffix Array Algorithm and Suffix Tree Algorithm, we found that the major advantages of the Suffix Array Algorithm over the Suffix Tree Algorithm were that the Suffix Array Algorithm is easier to implement and generally requires less memory. In addition, we compared the speed of execution of the two techniques and found that the Suffix Tree Clustering is faster when applied to a small document collection, but slower than, the Suffix Array Clustering when applied to a large document collection. The rationale is that the STC requires more memory space than SAC in maintaining its structure. Thus in the case of collection grows larger, the size of tree grows up faster then that of array. This results in more time taken in maintaining the structure when the tree structure goes beyond the capacity of memory. Hence, SAC is suitable for a large document collection or suitable to run on the computer system with very limited memory resource.;"ปัจจุบันการใช้เครื่องมือค้นหาข้อมูลบน Internet โดยใช้ Search Engine ได้รับความนิยมเป็นอย่างมากแต่ทว่าผลลัพธ์ที่ได้รับจาก Search engine บางครั้งก็ไม่ตรงกับที่ผู้ใช้ต้องการหรือบางครั้งข้อมูลที่ต้องการค้นหาอาจจะอยู่ใน Page หลัง ๆ ไม่ได้อยู่ใน Page แรก ๆ ของเอกสาร ทำให้ผู้ใช้ต้องเสียเวลาในการเข้าถึงข้อมูลที่ต้องการค้นหา จากปัญหาที่เกิดขึ้น โดยกา"