วันจันทร์ที่ 12 ตุลาคม พ.ศ. 2552

จุดกำเนิดของ Google(the birth of google) 2/4

หน้าที่ 2 - อินเตอร์เน็ต ทฤษฎีกราฟ และ BackRub Project

**หมายเหตุ (1บท ความนี้เป็นแบบ XML Live-Feeding Article ทดลองใช้เป็นครั้งแรกใน วิชาการ.คอม บทความจะออนไลน์ทันที และผู้เขียนบทความสามารถปรับแก้บทความ ได้ตลอดเวลา จนกว่าบทความจะสมบูรณ์ 2บทความนี้เขียนเพื่อวิชาการ.คอม โดยเฉพาะ (VCharkarn.com's exclusive article) )


ผศ.ดร.บุญญฤทธิ์ อุยยานนวาระ สถาบันเทคโนโลยีนานาชาติสิรินธร (SIIT) มหาวิทยาลัยธรรมศาสตร์ นักเขียนประจำ วิชาการ.คอม


Page เริ่มหัวข้อวิจัยเกี่ยวกับเว็บก็จริง แต่ไม่ได้เริ่มมองหาวิธีที่จะค้นหาข้อมูลบนเว็บ แต่สิ่งที่เค้ามองเห็นกลับเป็น มุมมองทางด้านคณิตศาสตร์ของเว็บไซท์มากกว่า คือ Page มองแบบนี้ครับ...

ถ้าหากมองว่า 1 เซอร์ฟเวอร์ หรือ 1 เว็บไซท์ เช่น วิชาการ.คอม หรือ 1 คอมพิวเตอร์ เป็นเพียง จุด (Node, Vertex) จุดหนึ่งบนกราฟ (Graph) และ ลิ๊งค์ (link) เช่น www.ipst.ac.th ที่ วิชาการ.คอม เชื่อมต่อไปยังเว็บไซท์อื่นๆ เหมือนกับเป็นทางเชื่อมต่อกัน หรือ ขอบ(Edge) ระ่หว่างจุดเหล่านั้น หรือ พูดง่ายๆว่า Page มองเห็น อินเตอร์เน็ตเป็นกราฟ นั่นเอง (แฮ่ะๆ แบบนี้เรียกว่ามันอยู่ในสัญชาติญาณ มองอินเตอร์เน็ตเป็นกราฟ ทำได้ไงเนี่ย) ซึ่งบ้านเรา นิสิต นักศึกษาระดับปริญญาตรี ด้านทางสายวิทย์ มักจะได้เรียนเรื่อง กราฟ ประเภทนี้ในเรื่อง ทฤษฏีกราฟ (Graph Theory) แถวๆปีต้นๆ (ซึ่งน้องๆตัวเล็กๆอาจสับสนนิดนึง เพราะกราฟที่คุ้นเคยอาจจะหมายถึง กราฟที่เป็นตัวแทนของข้อมูล เช่น กราฟแท่ง กราฟเชิงเส้น ซะมากกว่า)

ถ้า ไม่ใช่ในวิชาคณิตศาสตร์ ก็จะเป็นวิชา Algorithm โดยเฉพาะพวกที่เรียน วิทยาการคอมพิวเตอร์ ก็น่าจะผ่านหูผ่านตากันมาแล้วทุกคน (ถ้าไม่ใส่ไหคืนอาจารย์ไปหมดแล้วซะก่อน) (มีอาจารย์และนักคณิตศาสตร์ ในเมืองไทยหลายคน ที่เชี่ยวชาญเรื่อง Graph Theory เช่น ดร.จริยา อุ่ยยะเสถียร ภาควิชาคณิตศาสตร์ จุฬาลงกรณ์มหาวิทยาลัย ที่จบปริญญาเอกเรื่องนี้มาโดยเฉพาะ เดี๋ยวจะลองเกี้ยวมาช่วยเขียน เรื่อง Graph Theory อีกซักบทความ)



ตัวอย่างกราฟ สมมติให้จุดแต่ละจุด แทนคอมพิวเตอร์แต่ละเครื่อง และเส้นเชื่อมแทนลิงค์ที่เชื่อมหากัน

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

ซึ่งตรงนี้แหละที่ Page มองแล้วเห็นว่ามันช่างน่าตื่นเต้น น่าสนใจ น่าติดตาม เสียเหลือเกิน Page เคยบอกว่า Internet คือ กราฟที่ใหญ่ที่สุดที่มนุษย์เคยสร้างขึ้น และมันก็ยังจะเติบโต ใหญ่ขึ้น ใหญ่ขึ้น ทุกๆวัน ด้วยอัตราเร็วในการเติบโตสูงมาก โอ! มันช่างเป็นเรื่องที่น่าสนใจทำวิทยานิพนธ์เหลือเกิน (ถ้าเป็นคนสามัญชนคนไทยธรรมดา ก็อาจจะบอกว่า โอ! มันซับซ้อนเหลือเกิน ไม่มีทางทำได้หรอก ทำไปเดี๋ยวไม่จบ หนีดีกว่า) ซึ่ง Prof. Winograd อาจารย์ที่ปรึกษาของเค้าก็เห็นด้วย และเห็นว่าน่าจะศึกษาเรื่องของโครงสร้างของกราฟของเว็บ เป็นการเริ่มต้นวิทยานิพนธ์

Page ทำการศึกษาด้วยตัวเองอยู่ไม่นาน เค้าก็เจอปัญหาแรกเข้าให้...

โอ เคตรงนี้เราเข้าเรื่อง graph theory กันนิดนึง (เอาเป็นว่าผมพยายามวงเล็บภาษาอังกฤษของคำไทยไว้ด้วยครับ จะได้ช่วยให้คนทีคุ้นเคยกับคำอังกฤษในวิชานี้แล้ว ได้เห็นภาพง่ายขึ้นนะ) คืออย่างนี้ ในกราฟปกติ ขอบของกราฟ (Edge) จะเป็นตัวบ่งถึงความสัมพันธ์กันระหว่าง จุด (Vertex) ซึ่งโดยปกติแล้ว เราจะรู้และนับจำนวนได้ว่า จากจุดจุดหนึ่ง มีขอบ หรือ เส้นลากไปยังจุดอื่นๆ อีกกี่จุด และมีกี่จุดที่ลากมาหาตัวเอง แต่หน้าเว็บเพจกลับไม่เป็นแบบนั้นซะทีเดียว เพราะ ที่หน้าเว็บเพจหนึ่งๆ (สมมติว่าเว็บ 1 หน้าเป็น 1 จุดในกราฟ) เรารู้ครับว่า จากจุดที่เราอยู่ปัจจุบัน มันลิงค์ไปยังหน้าไหนบ้าง คือ เรารู้ว่ามันมี จำนวนขอบที่วิ่งออกไป (Out Degree) จากตัวเองกี่ขอบกี่เส้น และไปที่ไหนบ้าง แต่ที่เราไม่รู้นี่คือว่า มีเว็บเพจใดบ้าง กี่หน้า ที่ลิงค์มาหาหน้าที่เราสนใจ

โอย สับสนใช่มั้ยครับ ผมยกตัวอย่างเปรียบเทียบแบบนี้ก็แล้วกัน ถ้าผมถามคุณว่าคุณรู้จักคนกี่คน คุณอาจจะต้องนั่งไล่นับนิ้วไปเรื่อยๆ แต่คุณก็บอกได้ว่าคุณรู้จักใครบ้าง และคล้ายๆกัน ผมถามว่า "คุณรู้มั้ยว่ามีใครในโลกนี้รู้จักคุณบ้าง?" (เปรียบกับ "รู้มั้ยว่ามีเว็บไหนลิงค์มาที่เราบ้าง") คำตอบคือ ไม่รู้ จะไปรู้ได้ยังไงว่าใครรู้จักเราบ้าง

โอเค เริ่มเห็นภาพนะครับ ลองนึกตามแบบนี้นะครับ ว่าหน้าเว็บที่คุณอ่านอยู่ตอนนี้เนี่ย ลิงค์มาจากหน้าไหน URL อะไรบ้าง ถ้าคุณไม่กด Back มีข้อมูลตรงไหนบอกมั้ยครับ ? หรือแม้แต่คุณจะกด Back คุณก็รู้แค่ลิงค์เดียวที่ลิ๊งค์มาหาหน้านี้ แต่ที่จริง อาจจะมีหน้าเว็บอื่นๆอีกเป็นร้อยๆ ที่มีลิ๊งค์มาหาหน้านี้ ที่เราไม่รู้ คำถามคือ แล้วเราจะรู้ได้ยังไง ?

ซึ่ง ตรงนี้หล่ะยาก เพราะอินเตอร์เน็ตไม่ได้ให้ข้อมูลนี้มา และตรงนี้เองที่ Page คิดว่า มันน่าจะดี ถ้าหากว่าเรารู้ (หรืออย่างน้อย มีวิธีการที่จะทำให้รู้) ว่าใครลิงค์หาใครบ้าง หรือ มีใครลิงค์มาหาหน้านี้บ้างกี่คน Page ก็เลยเลือกเอาปัญหานี้ มาทำเป็นวิทยานิพนธ์ปริญญาเอก และตั้งชื่อเล่นโปรเจ็คของเค้าว่า "BackRub Project" (โครงการ "ถูหลัง" - แหม! ผมแปลตรงตัวไปหน่อยหรือปล่าวเนี่ย - สงสัยว่า Page คงอยากรู้ว่า ตอนที่อาบน้ำนี่ ใครถูหลังให้เค้าบ้าง - เอ้า ! ว่าไปโน่น)

โอเค งั้นกลับมาที่คำถามเดิม ถ้าเราอยากจะรู้ว่ามีใครรู้จักเราบ้างกี่คน เราจะทำอย่างไร จริงๆคำตอบนี้ง่ายมากครับ คุณก็ถามคนทุกๆคนทั่วทั้งโลกนี้เลยซิครับว่าเค้ารู้จักใครบ้าง ด้วยวิธีนี้ พอคุณถามครบทุกคนทั้งโลก คุณก็จะรู้ว่าทั้งโลกนี้มีคนรู้จักคุณกี่คนใช่ป่าวครับ แหม! คิดได้ไง ง่ายจัง

คล้ายๆกัน เพื่อจะรู้ว่าใครลิงค์มาที่หน้าเว็บนี้บ้าง Page ก็เริ่มจากการไล่ไปที่ละหน้าเว็บแล้วดูว่าหน้านั้นลิงค์ไปที่ไหนบ้าง (เหมือนว่าหน้านั้นรู้จักใครบ้าง) แล้วเก็บลิงค์ทั้งหมดในหน้านั้นมาเข้าคิวไว้ เพื่อจะได้ไล่ถามไปเรื่อยๆ (ตรงนี้แหล่ะครับที่เรียกว่า Crawler - หน้าถัดไปจะอธิบายอีกที) Page คิดว่าแหมไล่ไปเรื่อยๆแบบนี้ ซักอาทิตย์นึงก็เก็บเว็บหมดจากทั่วโลกแล้ว ... น้าน.... ก็เป็นจุดเริ่มต้นของ Backrub โปรเจ็คนั่นเอง


back rub line - ถ้ามองไปข้างหน้าอย่างเดียว เราไม่มีทางรู้ว่าใครกำลังถูหลังเราอยู่

จาก BackRub Project ที่ค่อยๆ เติบโตมา ด้วยน้ำมือของนักศึกษา 2 คน ที่ใช้ห้องนอนที่หอพักนักศึกษา ทำเป็น ห้อง Server และ ห้องเขียนโปรแกรม ได้กลายเป็น Google Project โปรแกรม Search Engine ขนาดจิ๋ว ที่ดูดทรัพยากร Network ของมหาวิทยาลัย สแตนฟอร์ด ที่ได้ชื่อว่า Network ที่เร็วเป็นอันดับต้นๆของโลก ได้อย่างไร ติดตามหน้า 3 จ้า...

ที่มา http://www.vcharkarn.com/varticle/317

ไม่มีความคิดเห็น:

แสดงความคิดเห็น