บทคัดย่อ. ความยากของการศึกษาเวบกราฟอยู่ที่ปริมาณเวบเพจมหาศาล ในปัจจุบันการศึกษาเวบกราฟถูกนำไปใช้ในหลายจุดประสงค์ อาธิเช่น การให้คะแนนความสำคัญของเวบเพจ การตรวจจับเวบสแปม การคัดแยกกลุ่มสังคม งานวิจัยนี้ได้นำเสนอต้นแบบกรอบการทำงานเพื่อสร้างเวบกราฟ เวบกราฟผกผัน และ API Web Service ผลลัพท์ที่ได้จากงานวิจัยนี้สามารถนำไปใช้คำนวณค่าเพจแรงค์ด้วยวิธี Power Method กรอบการทำงานนี้ยังเป็นต้นแบบระบบพื้นฐานของเสิร์ชเอนจิ้นสำหรับประเทศไทย งานวิจัยนี้ได้ใช้ตัวอย่างชุดข้อมูลทดสอบ เดือนสิงหาคมและกันยายน ปี 2008 จากโครงการ WebBase พัฒนาโดย มหาวิทยาลัย Stanford จากการทดลองพบว่ากรอบการทำงานที่ได้ออกแบบไปนั้นสามารถทำงานได้อย่างมีประสิทธิภาพบนหน่วยประมวลผล Core 2 Duo 3.0 GHz. และหน่วยความจำขนาด 2 GB

Studying Web graph is often difficult due to their large size. Recently, there are several purposes of Web graph such known as ranking of search result, web spam detection, community identification. In this paper, we propose the prototype of Massive Thai Web Graph Framework and API Web service. Our Web graph can work well with the well-known Page Rank algorithm that is Power Method. Our framework is the prototype infrastructure for Thai Search Engine. We concern the datasets in August and September 2008 from Stanford WebBase Project made available Stanford University. Form the experiments; our framework can work efficiently with Intel Core 2 Duo 3.0 GHz and memory 2GB.

ในเดือนมกราคม 2010 WWWSize (htt) ได้ทำดัชนีเวบเพจทั่วโลกแล้วกว่า 20 พันล้านเวบเพจ จากข้อมูลดังกล่าวพบว่าปัจจุบันเวบเพจในระบบอินเตอร์เนตมีปริมาณมหาศาลและเพิ่มขึ้นอย่างทวีคูณส่งผลให้การพัฒนาระบบสืบค้นข้อมูลมีความท้าทายมากยิ่งขึ้น (J. Kleinberg, 1999) ได้นำเสนอการสร้างแบบจำลองการเชื่อมโยงเวบเพจหรือเวบกราฟซึ่งเป็นโครงสร้างพื้นฐานของระบบสืบค้นข้อมูล หลังจากนั้นการสร้างเวบกราฟได้ถูกนำไปประยุกต์ใช้งานหลากหลายประเภท อาธิเช่น การคำนวณค่าเพจแรงค์เพื่อจัดอันดับความสำคัญของเวบเพจ การตรวจจับเวบสแปม และการจัดกลุ่มเวบเพจ เป็นต้น (Cho, Junghoo and Garcia-Molina, Hector and Haveliwala, Taher and Lam, Wang and Paepcke, Andreas and Raghavan, Sriram and Wesley, Gary., 2006) ได้นำเสนอสถาปัตยกรรมเพื่อสร้างระบบสนับสนุนการทำวิจัยเกี่ยวกับระบบ Search Engine ประกอบด้วย Web Crawler, Web Indexing, Web Repository เป็นต้น นอกจากระบบดังกล่าวจะสนับสนุนข้อมูลให้กับนักวิจัยแล้ว นักวิจัยสามารถนำข้อมูลไปใช้ได้เลยโดยที่ไม่ต้องเสียเวลาในส่วนของการเตรียมข้อมูล นอกจากนั้นข้อมูลดังกล่าวจะเป็นชุดข้อมูลมาตรฐานในการทำการทดลองต่างๆ ให้กับงานวิจัยอื่นๆ เพื่อการวัดผลและเปรียบเทียบประสิทธิภาพการทำงาน งานวิจัยนี้ได้นำเสนอต้นแบบกรอบการทำงานเพื่อสร้างเวบกราฟ เวบกราฟผกผัน และ API Web Service เพื่อให้นักวิจัยที่สนใจสามารถนำข้อมูลเวบกราฟไปใช้โดยที่ไม่ต้องเสียเวลาในการเตรียมข้อมูลสนับสนุนการทดลอง ในบทที่ 2 จะกล่าวถึงความรู้พื้นฐานเกี่ยวกับงานวิจัย ในบทที่ 3 จะกล่าวถึงรายละเอียดของข้อมูลทดสอบ ในบทที่ 4 จะกล่าวถึงรายละเอียดวิธีการทำงานและหลักการทำงาน ในบทที่ 5 จะกล่าวถึงผลการทดลอง ในบทที่ 6 จะสรุปผลการทดลองและแนวทางการพัฒนาต่อในอนาคต

เวบเพจ (Web Page) คือ หน้าเว็บแต่ละหน้าที่ประกอบไปด้วยข้อมูล รูปภาพ เสียง และวิดีโอ โดยเป็นข้อมูลแบบสื่อผสมหรือมัลติมีเดีย และกลุ่มของเวบเพจที่มีชื่อโดเมนเหมือนกันเรียกว่า เวบไซต์ สำหรับงานวิจัยนี้จะสนใจแต่เวบเพจแบบนิ่ง(Static Web Page) กล่าวคือ เวบเพจที่แสดงผลข้อมูลเหมือนกันทุกครั้งโดยปราศจากเงื่อนไขจากผู้ใช้งาน สำหรับเวบเพจที่ไม่ใช่ Static Web Page เช่น http://www.mikelab.net/home.php?id=1 ไฮเปอร์ลิงค์ (Hyperlink) คือ URL ปลายทางที่ปรากฏในเวบเพจนั้นๆ ผ่านข้อความ Anchor Text

เวบกราฟ (Web Graph) หมายถึง กราฟของเวบเพจที่เชื่อมโยงระหว่างเวบเพจด้วย Hyperlinks โดยกำหนดให้ Vertex คือ เซตของเวบเพจที่แสดงข้อมูลในลักษณะที่ปราศจากเงื่อนไขหรือการตัดสินใจ (Static Web Page) และ Edge คือ เซตของ Hyperlink ที่เชื่อมโยงระหว่างเวบเพจ สำหรับ Invert ของเวบกราฟ เรียกว่า เวบกราฟผกผัน (Transpose Web Graph) กล่าวคือเราสามารถหา Forward Link ของแต่ละหน้าเวบเพจได้จากเวบกราฟ และ Backward Link ได้จากเวบกราฟผกผัน และสำหรับเวบเพจใดๆ กำหนดให้ความถี่ของ Forward Link เรียกว่า Out-degree และความถี่ของ Backward Link เรียกว่า In-degree และจะกำหนดให้แต่ละ Hyperlinks ที่ปรากฏ คือหนึ่งโหนด (Node) และนิยามให้ Dangling Node หมายถึง เวบเพจใดๆ ที่มี Out-degree = 0 กล่าวคือเวบเพจนั้นไม่มี Forward Link นั่นเอง

งานวิจัยนี้ได้ทำการทดลองโดยใช้ข้อมูลทดสอบจากโครงการ WebBase (Cho, Junghoo and Garcia-Molina, Hector and Haveliwala, Taher and Lam, Wang and Paepcke, Andreas and Raghavan, Sriram and Wesley, Gary., 2006) แบบแยกเก็บตามไซต์ พัฒนาโดยมหาวิทยาลัยสแตนฟอร์ด โดยมีลักษณะโครงสร้างของข้อมูลนำเข้า ดังรูปภาพที่ 1 รูปแบบของข้อมูลทดสอบแบบแยกเก็บตามไซต์

==P=>>>>=i===<<<<=T===>=A===<=!Junghoo==>
URL: http://www.mikelab.net/                  
Date: Jan 20, 2010     
Position: 949                       
DocId: 1                             
HTTP/1.1 200 OK  
                     
<html>…</html> 	-- page separator

กรอบการทำงานของระบบนี้เริ่มจากให้เวบคราวเลอร์ทำการเก็บเวบเพจที่อยู่ในระบบอินเตอร์เนตแบบแยกเก็บตามไซต์โดยใช้รูปแบบของ Stanford WebBase Project และทำการบีบอัดแต่ละไฟล์ด้วย GZIP Compression หลังจากนั้นเราจะได้ Web Repository ที่รวบรวมเวบเพจเพื่อเป็นข้อมูลนำเข้าของระบบที่ได้ออกแบบไว้ดังรูปภาพที่ 2

เราได้ทำการออกแบบต้นแบบระบบการสร้างเวบกราฟ และ API สำหรับนักวิจัยที่สนใจได้เข้ามาใช้ทรัพยากร ระบบที่เสนอนั้นประกอบด้วย 2 การทำงานหลัก ได้แก่ การสร้างเวบกราฟ เวบกราฟผกผัน และการทำงานของระบบ API

การสร้างเวบกราฟเริ่มจากการแตกไฟล์ GZIP ที่ละไฟล์ใน Web Repository แล้วเก็บข้อความทั้งหมดลงบนหน่วยความจำ หลังจากนั้นให้นำข้อความที่ได้มาแบ่งเป็นเวบเพจย่อยๆ โดยใช้ข้อความคั่นเอกสาร หรือ Document Separator เมื่อได้ลำดับของเวบเพจในเวบไซต์นั้นๆแล้ว ระบบจะค้นหาลำดับของ Hyperlink ในเวบเพจนั้นๆ แล้วนำลำดับของ Hyperlink ที่ได้เก็บลงใน Hash Table เพื่อสร้างตัวเลขแทน URL นั้นๆ หลังจากนั้นเราจะนำ Source ID และ ลำดับของ Destination ID มาเขียนลงในเวบกราฟแบบ Binary Format ดังรูปภาพที่ 3 ในขณะเดียวกันระบบจะสร้าง Hash Table ในหน่วยความจำชั่วคราวเพื่อเก็บ Transpose Web Graph นั่นหมายความว่า เราจะเก็บ Web Graph ลงหน่วยความจำถาวร และจะเก็บ Transpose Web Graph ลงในหน่วยความจำชั่วคราวก่อน ท้ายสุดนี้เมื่อระบบทำงานครบทุกไฟล์ใน Web Repository แล้ว ระบบจะย้ายข้อมูล Transpose Web Graph ที่อยู่ในหน่วยความจำสำรองลงหน่วยความจำถาวร

เนื่องจากแต่ละเวบเพจอาจมี URL ที่มีเป้าหมายเดียวกันแต่รูปแบบไม่เหมือนกัน กระบวนการ URL Canonicalization (URL) หรือ URL Normalization คือ กระบวนการแก้ไข URL ให้อยู่ในมาตรฐานเดียวกันซึ่งจะช่วยแก้ปัญหาดังกล่าว ปัจจุบันระบบสืบค้นข้อมูลต่างใช้กระบวนการดังกล่าวเพื่อลดจำนวนเวบเพจที่ซ้ำๆกันในการทำดัชนี ส่วนประกอบของ URL มีดังนี้

<scheme> : <netloc> <path> [? <query> ] [ # <fragment> ]

• URL scheme name (scheme) มีหน้าที่ระบุโปรโตคอล เช่น http, https, ftp, mailto เป็นต้น
• Network Location part(netloc) มีหน้าที่ระบุชื่อโดเมนเนมและพอร์ต เช่น mikelab.net:80
• Hierarchical path(path) มีหน้าที่ระบุที่อยู่ของเวบเพจในโดเมนนั้นๆ เช่น /home/index.html
• Query มีหน้าที่ระบุเงื่อนไขจากผู้ใช้งาน มักตามหลังเครื่องหมาย ? เช่น ?id=3&product=4
• Fragment มีหน้าที่อ้างอิงส่วนต่างๆ ของเวบเพจ มักตามหลังด้วยเครื่องหมาย # เช่น #home

กระบวนการขั้นตอน URL Canonicalization มีดังนี้

1. เปลี่ยน scheme และ netloc เป็นตัวอักษรตัวเล็ก

    HTTP://www.Foo.com/ → http://www.foo.com/

2. เพิ่ม / ต่อท้าย netloc

   http://www.foo.com → http://www.foo.com/

3. ตัดส่วนของพอร์ต 80 เนื่องจากเป็นค่าพอร์ตปริยายของผู้ให้บริการเวบไซต์

    http://www.foo.com:80/bar.html → http://www.foo.com/bar.html

4. เปลี่ยนจาก Relative path เป็น Absolute path

    http://www.foo.com/../a/b/../c/./d.html → http://www.foo.com/a/c/d.html

5. ตัดส่วนของ Query ทิ้ง

    http://www.foo.com/bar?id=&sort=ascending → http://www.foo.com/bar

6. ตัดส่วนของ Fragment ทิ้ง

    http://www.foo.com/bar.html#section1 → http://www.foo.com/bar.html

(T. Haveliwala, 1999) ได้เสนอวิธีการสร้างเวบกราฟแบบ Naïve Technique งานวิจัยนี้ได้ใช้วิธีดังกล่าว สำหรับรายละเอียดสามารถอธิบายเป็นขั้นตอนได้ดังนี้

• กำหนดให้เวบเพจที่จะเก็บลงในเวบกราฟจะต้องเป็นเวบเพจที่ไม่ใช่ Dangling Node

• เนื่องจากความยาวของ URL มีความยาวไม่เท่ากันและใช้พื้นที่ในการเก็บข้อมูลจำนวนมาก ผู้วิจัยได้เสนอให้บีบอัดข้อมูล URL โดยใช้ตัวเลขจำนวนเต็ม 32 บิต แทน URL ใดๆ และเก็บคู่อันดับ (URL,ID) โดยให้ Key คือ URL และ Value คือ Node ID ลงใน Hash Table สำหรับงานวิจัยนี้ได้เลือก Oracle Berkeley DB (Ora) เป็นฐานข้อมูล Open-Source ที่มีโครงสร้างข้อมูลแบบ Hash Table
• โครงสร้างข้อมูลของเวบกราฟได้ถูกออกแบบให้เก็บข้อมูลลงหน่วยความจำถาวรในรูปแบบ Binary Format โดยให้ Source Node และลำดับของ Destination Node แทนด้วยเลขจำนวนเต็ม 32 บิต สำหรับ Out Degree ให้แทนด้วยเลขจำนวนเต็ม 16 บิต ซึ่งสามารถดูรายละเอียดเพิ่มเติมได้จากรูปภาพที่ 3 โครงสร้างข้อมูลสำหรับเวบกราฟ

• สำหรับเวบกราฟผกผัน หรือ Transpose Web Graph สามารถดูได้จากรูปภาพที่ 4

เนื่องจากกระบวนการขั้นตอนเพื่อสร้างเวบกราฟและเวบกราฟผกผันใช้เวลานาน เพื่อลดทรัพยากรในการคำนวณดังกล่าว งานวิจัยนี้ได้ออกแบบ API Web Service บน HTTP Protocol ผ่าน GET,POST Method ให้ผู้อื่นสามารถเข้ามาใช้ทรัพยากรที่งานวิจัยนี้ผลิตขึ้นมาได้ งานวิจัยนี้ได้เลือกใช้รูปแบบมาตรฐานข้อมูลแบบ JSON (JSO)ในการรับส่งระหว่าง Server-Client สำหรับบริการที่งานวิจัยได้นำเสนอ

งานวิจัยนี้พัฒนาโดยใช้ภาษา Python เวอร์ชั่น 2.6.4 บนระบบปฏิบัติการ Ubuntu Desktop 9.10(Kernel 2.31.14) บนเครื่องคอมพิวเตอร์ที่มีหน่วยประมวลผล Intel Core2Duo E8400 3.0 GHz และหน่วยความจำขนาด 2 GB สำหรับตัวเลขสถิติหลังจากทำการทดลองสามารถดูได้จากรูปภาพที่ 7

ข้อสังเกตุที่ได้จากรูปภาพที่ 7 พบว่าเมื่อขนาดข้อมูลของเดือนสิงหาคมมีมากกว่าเดือนกันยายนเกือบ 2 เท่า แปรผันตรงกับจำนวนเส้นเชื่อม (Edge) เนื่องจากการเพิ่มขึ้นของข้อมูลและปริมาณเส้นเชื่อมทำให้เสียเวลาในการเก็บข้อมูลลงเวบกราฟและเวบกราฟผกผันมากขึ้น ทำให้กระบวนการทำงานกับชุดข้อมูลทดสอบเดือนสิงหาคมใช้เวลามากกว่าชุดข้อมูลทดสอบเดือนกันยายน

งานวิจัยนี้ได้นำเสนอต้นแบบกรอบการทำงานเพื่อสร้างเวบกราฟ เวบกราฟผกผัน และ API Web Service สามารถสร้างฐานความรู้ขั้นพื้นฐานสำหรับการพัฒนาระบบสืบค้นข้อมูลภาษาไทยได้เป็นอย่างดี นอกจากนั้นยังอำนวยความสะดวกให้นักวิจัยท่านอื่นที่สนใจสามารถนำข้อมูลไปใช้งานได้ทันทีโดยไม่ต้องเสียเวลาในการเตรียมข้อมูลในการศึกษาและทำการทดลอง ผลลัพท์ที่ได้จากกรอบการทำงานสามารถนำไปใช้คำนวนเพื่อจัดลำดับความสำคัญของเอกสารหรือค่าเพจแรงค์ด้วยวิธี Power Method ได้จริง

แนวทางการพัฒนาต่อในอนาคต ได้แก่ การพัฒนาให้กรอบการทำงานสามารถสร้างเวบกราฟและเวบกราฟผกผันกับปริมาณเวบเพจที่มากกว่านี้เพื่อให้สอดคล้องกับขนาดของเวบเพจในปัจจุบันซึ่งมีปริมาณมหาศาลด้วยวิธีการบีบอัดเวบกราฟให้มีขนาดเล็กลงและสามารถเก็บข้อมูลทั้งกราฟลงบนหน่วยความจำสำรองได้ การเพิ่มขีดความสามารถในการทำงานมากยิ่งขึ้นด้วยระบบ Distributed Computing หรือ Distributed File System และการเก็บข้อความ Anchor Text หรือ Surrounded Text เพื่อเป็นฐานความรู้ให้กับระบบเวบคราวเลอร์เจาะจงเวบภาษาไทย เป็นต้น