Search Engine
หลายท่านคงเคยได้ยิน และได้ใช้กันอยู่เป็นประจำในการค้นหาข้อมูลผ่านอินเทอร์เน็ต โดยหลายท่านรู้จัก Google , Yahoo หรือ Ask.com เป็นต้น แต่มันทำงานอย่างไร ทำไม Search Engine ถึงได้ค้นหาตรงใจ ค้นปุ๊ป เจอปั๊ป เพื่อเป็นการเข้าใจหลักการทำงานของ Search Engine เลยจำเป็นต้องพัฒนาขึ้นมาเอง เพื่อให้เข้าใจทุกขั้นตอน และ Pan & James Search (เหตุผลที่เลือก ชื่อ Search Enging นี้ เพราะช่วงนั้น คุณปัง กับคุณเจมส์ กำลัง Hot ครับ) ที่ผมและกลุ่ม ได้พัฒนาขึ้นมาเพื่อเป็น Project ขอบวิชา Information Retrival (IR) ตอนที่ได้ศึกษาอยู่ครับ …
ขั้นตอนการทำงาน มีลักษณะการทำงานเหมือน Modern Search Engine ทั่วไปครับ .. แต่จะมีส่วนที่ใช้เทคนิค n-Gram เข้ามาช่วยเสริมเพื่อพยายามเดาคีย์เวิร์ด (Keywork หรือ Query) ของผู้ใช้ ดังนี้
1. บทนำ
ปัจจุบันการใช้อินเทอร์เน็ตเข้ามามีบทบาทในชีวิตประจำวัน เพื่อใช้เป็นช่องทางสื่อสารและแพร่กระจายข่าวสารของหน่วยงาน บริษัท สถานศึกษาต่าง ๆ ดังนั้นอินเทอร์เน็ตจึงเป็นแหล่งรวมของข้อมูลข่าวสารต่าง ๆ เมื่อความนิยมการใช้งานอินเทอร์เน็ตเป็นไปอย่างแพร่หลาย ทำให้ปริมาณข้อมูลมีมากขึ้น การสืบค้นข้อมูลต่าง ๆ จึงเป็นไปได้ยากลำบาก จึงมีบริการสืบค้นข้อมูล (Search Engine) มาใช้มากยิ่งขึ้น ซึ่งตัวอย่างการสืบค้นข้อมูลของเว็บไซต์ ตัวอย่างเช่น Google ,Yahoo และ Ask เป็นต้น
รายงานฉบับนี้ได้พัฒนา Search Engine ขึ้นมา มีชื่อว่า Pan & James Search โดยมีโครงสร้างหลัก ๆ ของการสืบค้นข้อมูลทางเว็บไซต์ทั่ว ๆ ไป คือ มีโปรแกรม Crawler ทําหน้าที่อ่านเวบเพจ จากเว็บไซต์ต่าง ๆโดยอัตโนมัติ ซึ่งสามารถกำหนดความลึก (Dept) ของเพจนั้น ๆ ได้ จากนั้นจึงนําเว็บเพจที่อ่านได้มาทําดัชนี (Index) ซึ่งจะตรวจสอบลิงค์ในแต่ละหน้าของเวบเพจเพื่อเข้าไปทําดัชนีของเวบเพจนั้นต่อไปอีก ในส่วนที่รับค่า Query จากผู้ใช้งานนั้น ได้นำ N-Gram มาใช้ในการตัดคำที่รับค่ามาจากผู้ใช้ เพื่อเสนอแนะ (Suggestion) คำที่ถูกต้องในกรณีที่ผู้ใช้งานพิมพ์คำที่สะกดผิด หรือคีย์ผิดเข้ามา โดยนำ N-Gram มาทำการตัดคำ และนำคำมาหาค่าความคล้ายคลึงกับคำต่าง ๆ ที่อยู่ในพจนานุกรม (Dictionary) และนำคำที่ได้ไปค้นหาเพื่อให้ได้ผลลัพท์ที่ใกล้เคียงกับความต้องการของผู้ใช้มากที่สุด
ส่วนของการประมวลผลข้อความ (Text processing) ได้ใช้กระบวนการตัดคำ (Word Segmentation) ฿าษาไทยโดยใช้พจนานุกรม (Dictionary Approach) ซึ่งเป็นการแบ่งตัวอักษรจากข้อความ (String) เพื่อหาขอบเขตของแต่ละหน่วยคำ(Morpheme) โดยอ่านตัวอักษรทีละอักขระ แล้วนำไปเทียบกับพจนานุกรม และในส่วนของการสร้างดัชนีคำ (Index) ได้มีกลไกการทํางานแบบสร้างดัชนีคําทั้งในภาษาไทยและภาษาอังกฤษตามหลักการแบบ ดัชนีผกผัน (Inverted Index) และจับเก็บคําโดยใช้วิธีแฮชชิง (Hashing) รูปแบบของดัชนีผกผันช่วยให้สามารถค้นหาคําได้อย่างรวดเร็ว เพราะไม่มีกระบวนการค้นหาคําจากข้อมูลต้นฉบับใด ๆ หากมีแต่เพียงการสืบค้นจากตารางเก็บดัชนีเท่านั้น
ส่วนของการสืบค้นข้อมูล (Searching) เป็นส่วนที่นำคําที่ต้องการค้นหาจากผู้ใช้ผ่านทาง User Interface มาค้นหาในฐานข้อมูล และส่งผลการค้นหากลับไปแสดงบนหน้าจอ ซึ่ง Model ที่นำมาใช้ คือ Vector Space Model (VSM) ซึ่งการค้นคืนจะได้เอกสารที่มีแม้แต่ความเหมือนแค่เพียงบางส่วน โดยที่ไม่ต้องเป็นคำที่ตรงกันทั้งหมด โดยดูจากค่าความคล้ายคลึง (Similarity) ของเอกสารกับคำค้น และเอกสารที่ค้นคืนได้สามารถนำไปจัดอันดับ (Ranking) ได้
2. ทฤษฎีที่เกี่ยวข้อง
2.1 Search Engine
เป็นการค้นหาข้อมูลที่ใช้โปรแกรมช่วยในการค้นหาข้อมูลจากอินเทอร์เน็ต โปรแกรมจะรวบรวมข้อมูลเกี่ยวกับเว็บไซต์บนเครือข่ายอินเทอร์เน็ตโดยอัตโนมัติแล้วส่งข้อมูลที่ได้กลับมา ผลลัพธ์ที่ได้จะครอบคลุมทุกเว็บไซต์ ตัวอย่างเว็บไซต์ ที่เป็น Search Engine เช่น www.google.com www.lycos.com www.yahoo.com www.ask.com เป็นต้น ซึ่งมีสถาปัตยกรรมดังภาพที่ 1
฿าพที่ 1 สถาปัตยกรรมของ Search Engine
2.2 Web Crawler
เป็นโปรแกรมล็ก ๆ ที่ถูกส่งมาจาก Search Engine โดยจะคอยวิ่งไต่ไปตามลิงค์ต่าง ๆ ของเว็บไซต์ต่าง ๆ เพื่อทำการเก็บข้อมูลของหน้าเพจ โดยการะทำการคัดลอกเนื้อหาของหน้าเพจนั้น ๆ ทั้งหมด แล้วจึงส่งกลับไปยัง Server ของตนเอง เพื่อทำการจัดเก็บข้อมูลลงสู่ฐานข้อมูลเพื่อไว้สำหรับประมวลผลการค้นหา
2.4 N-Gram
N-Gram คือ แบบจำลองที่ใช้คำนวณค่าความน่าจะเป็นของชุดอักขระ (Character Sequence) ที่เกิดขึ้นร่วมกันเป็นคำ หรือค่าความน่าจะเป็นของคำที่เขียนเรียงกัน (Word Sequence) ที่เกิดขึ้นร่วมกันเป็นประโยค โดยค่าความน่าจะเป็นของชุดอักขระหรือคำ ประมาณได้จากคลังข้อมูลที่สร้างไว้ ซึ่ง N-Gram ได้ใช้หลักการของสถิติในหลาย ๆ ด้านมาประยุกต์ใช้ [1]
Gram คือ หน่วยที่ใช้ในการสร้างแบบจำลอง อาจจะเป็นเสียง คำ หรือ อักขระก็ได้ Gram มีได้หลายขนาดแล้วแต่จะกำหนด ตั้งแต่ 1 จนถึง nในแบบจำลองเอ็นGram นี้ใช้ความยาวของสายอักขระและสายคำแตกต่างกัน ได้แก่ 2- 3-Gram 4-Gram ฯลฯ ถ้าจะประมาณค่าความน่าจะเป็นของสายคำหรือสายอักขระจากคลังข้อมูลโดยการใช้วิธี N-Gram ผลที่ได้มีดังนี้
การประมาณค่าด้วย 2-Gram (Probability bigram) คือ การประมาณค่าความน่าจะเป็นของสายอักขระ (สายคำ) ที่เกิดขึ้นร่วมกันว่ามีค่าเท่ากับผลคูณของความน่าจะเป็นที่จะพบอักขระ(คำ) ทีละ 2 ตัว (คำ) ติดกันในสายอักขระ (สายคำ) นั้น
การประมาณค่าด้วย 3-Gram (Probability trigram) คือ การประมาณค่าความน่าจะเป็นของสายอักขระ (สายคำ) ที่เกิดขึ้นร่วมกันว่ามีค่าเท่ากับผลคูณของความน่าจะเป็นที่จะพบอักขระ (คำ) ทีละ 3 ตัว (คำ) ติดกันในสายอักขระ (สายคำ) นั้น
วิธีการใช้แบบจำลอง N-Gram นี้เป็นวิธีทางสถิติที่นิยมใช้กันมากที่สุด เพราะเป็นวิธีที่เรียบง่าย มีประสิทธิภาพสูง และเหมาะสำหรับวิเคราะห์฿าษา สามารถใช้ระบุภาษาได้ดีกว่าวิธีอื่นๆ โดยเมื่อดูจากทบทวนวรรณกรรมต่อไปจะแสดงให้เห็นประสิทธิ฿าพของแบบจำลอง N-Gram วิธีการใช้ N-Gram ในงานระบุภาษาและผลการทดลอง
3. กระบวนการของ Pan & James Search
รายงานฉบับนี้ได้จัดทำ Search Engine ชื่อว่า Pan & James Search โดย Search Engine มีกระบวนการดังภาพที่ 2 โดยแบ่งกระบวนการเป็น 6 ขั้นตอน ดังนี้
฿าพที่ 2 สถาปัตยกรรมของ Search Engine : Pan & James Search
3.1 Crawler
ในรายงานฉบับนี้ได้สร้าง Web Crawler ตัวหนึ่ง ชื่อว่า James Bot โดยจะไต่ไปตามเว็บเพจต่าง ๆ เพื่อรวบรวมข้อมูลจากเว็บเพจต่าง ๆ โดยสามารถกำหนดความลึก (Dept) ในการไต่ไปตามลำดับของลิงค์ต่าง ๆ โดยทำการคัดลอกไฟล์เอกสารของเว็บเพจต่าง ๆ กลับมายัง Server ของตนเอง โดยสามารถเลือกประเภทไฟล์ของเอกสารบนเว็บไซต์ได้ เช่น ไฟล์เอกสาร HTML, PDF , PPT และ Doc เป็นต้น ซึ่งมีสถาปัตยกรรม ดังภาพที่ 3
฿าพที่ 3 สถาปัตยกรรมของ James Bot
3.2 User Interface
ในส่วนของ User Interface มีหน้าที่ในการรับ Query จากผู้ใช้ โดยผู้ใช้สามารถป้อนคำที่ต้องการค้นหา เพื่อนำ Query ไปสู่กระบวนการค้นหาต่อไป และยังเป็นส่วนที่แสดงผลลัพธ์จากการค้นคืนให้กับผู้ใช้ ซึ่งในขั้นตอนการรับค่าจากผู้ใช้ ได้นำการตัดคำ ซึ่งอยู่ในส่วนประมวลผลข้อความ โดยใช้ N-Gram มาตัดคำ เพื่อตรวจสอบคำที่ผู้ใช้ป้อนเข้ามาว่าเป็นคำที่ถูกต้องหรือไม่ ซึ่งเป็นการเดา (Suggestion) คำที่คาดว่าน่าจะเป็น ที่ผู้ใช้อาจป้อนเข้ามาผิด ดังภาพที่ 4โดยมีกระบวนการ ดังนี้
1. รับค่า Query ที่ได้จากผู้ใช้
2. นำ N-Gram มาตัดคำของค่า Query ที่รับจากผู้ใช้ โดยใช้ 4 N-Gram ในการตัดคำ ตัวอย่างเช่น รับค่า Query คือ ท่องเที่ย เมื่อทำการตัดคำโดยใช้ N-Gram แล้ว จะได้ผลลัพธ์ดังนี้
_ท่อง ท่องเ องเที่ งเที่ย เที่ย_ ที่ย_ _ ย_ _ _
3. แล้วจึงนำคำที่ถูกตัดมาแล้ว มาเทียบคำกับพจนานุกรม (Dictionary) จากนั้นจึงให้น้ำหนักกับคำที่ตัดได้
4. เมื่อคำต่าง ๆ ผ่านกระบวนการให้น้ำหนักแล้ว จะดูคำที่มีค่าน้ำหนักสูงสุด จึงจะนำคำนั้น ๆ ไปทำการค้นหา แทนคำที่คีย์เข้ามาผิด
฿าพที่ 4 กระบวนการตรวจสอบการรับค่าจาก User Interface โดยใช้ N-Gram
3.3 Text Processing
การประมวลผลข้อความ (Text processing) บนพื้นฐานของระบบการค้นคืนสารสนเทศ (Information Retrieval) สิ่งที่เป็นพื้นฐานที่จำเป็นอย่างยิ่งคือ “หน่วยคำ” ดังนั้นการหาขอบเขตของแต่ละคำจึงเป็นสิ่งแรกที่ต้องคำนึงถึง เพราะหากเลือกการหาขอบเขตคำไม่เหมาะสม อาจนำมาสู่ ระบบการประมวลผลข้อความที่ไม่ถูกต้อง ซึ่งในรายงานฉบับนี้ได้แบ่งส่วนการประมวลผลข้อความนี้ เป็น 2 ส่วน ดังนี้
3.3.1 ส่วนประมวลผลข้อความสำหรับนำไปสร้างดัชนีคำ (Index Terms) ซึ่งในรายงานฉบับนี้ได้ใช้ Full Text Search ในการสร้าง Index ดังภาพที่ 5
ภาพที่ 5 กระบวนการประมวลผลข้อความเพื่อนำคำไปสร้าง Index
ซึ่งโครงสร้างของการประมวลผลข้อความมีดังนี้
3.3.1.1 จากภาพที่ 5 เมื่อ Crawler ไต่ไปตามเว็บต่าง ๆ แล้ว จะได้เอกสารบนเว็บ (Html) เอกสารจะมีรูปแบบที่เป็นไร้โครงสร้าง จึงเริ่มด้วยการตัดช่องว่าง (Space) สำหรับภาษาอังกฤษ ส่วนภาษาไทยจะใช้กระบวนการตัดคำ (Word Segmentation) ซึ่งเป็นการแบ่งตัวอักษรจากข้อความ (String) เพื่อหาขอบเขตของแต่ละหน่วยคำ(Morpheme) เนื่องจากส่วนใหญ่฿าษาไทยมีการเขียนในลักษณะที่ติดกันโดยไม่มีการใช้เครื่องหมายวรรคตอนคั่นระหว่างคำเหมือนภาษาอังกฤษ ซึ่งใช้ช่องว่าง (Space) คั่นระหว่างคำ แต่ภาษาไทยจะมีการเว้นวรรคเป็นระยะเพื่อให้ผู้อ่านทำความเข้าใจกับความหมายของคำ ในรายงานฉบับนี้ใช้การตัดคำส่วนภาษาไทย โดยอ่านตัวอักษรทีละอักขระ แล้วนำไปเทียบกับพจนานุกรมที่ชื่อว่า Lexitron จึงจะทำการตัดคำตามพจนานุกรม จะได้คำตามพจนานุกรมทั้งเอกสาร
฿าพที่ 6 แสดงการตัดคำเพื่อนำไปสร้าง Index
3.3.1.2 เมื่อทำการตัดคำแล้ว ขั้นตอนต่อไปจะทำการตัดคำหยุด (Stopword) ซึ่งเป็นคำที่ไม่จำเป็น หรือคำที่ใช้บ่อย ๆ เช่น “การ” “ความ” “ควร” “ที่” “จะ” “ไป” “ใช้” “ได้” “and” “the” “a” “on” “from” เป็นต้น
3.3.1.3 แปลงคำให้อยู่ในรากศัพท์ (Stemming) โดยทำให้เป็นคำ ๆ เดียว ซึ่งส่วนนี้จะใช้กับ฿าษาอังกฤษ เช่น “run” “ran” “running” จะถูกตัดให้เป็นคำว่า “run” คำเดียว เป็นต้น
3.3.1.4 นำคำที่ได้ทั้งหมด มาเก็บไว้ในฐานข้อมูล เพื่อนำไปทำดัชนีคำ (Index)
3.3.2 ส่วนประมวลผลข้อความสำหรับการรับค่า Query จากผู้ใช้ จาก฿าพที่ 4 ในส่วนของ User Interface ได้นำ N-gram มาประยุกต์ใช้ในการตัดคำ เพื่อเดาคำ (Suggestion) ที่มีการคีย์ผิดพลาดขึ้นมา สำหรับภาษาไทยการหาขอบเขตคำค่อนข้างเป็นปัญหาเนื่องจากลักษณะการเขียนภาษาไทยนั้นไม่มีการใช้ตัวอักษรหรือสัญลักษณ์ที่นำมาใช้คั่นระหว่างคำหรือว่ามีการวรรคระหว่างคำเหมือนภาษาอังกฤษ นั่นคือต้องมีกระบวนการตัดคำ (Word segmentation) ที่เหมาะสมก่อนเป็นอันดับแรก หากจะให้นิยามของการตัดคำ คือ การแบ่งตัวอักษรจากข้อความ (String) เพื่อหาขอบเขตของแต่ละหน่วยคำ (Morpheme) เนื่องจากส่วนใหญ่ภาษาไทยมีการเขียนในลักษณะที่ติดกันโดยไม่มีการใช้เครื่องหมายวรรคตอนคั่นระหว่างคำเหมือนภาษาอังกฤษดังที่กล่าวไปซึ่งใช่ช่องว่าง (Space) คั่นระหว่างคำ แต่ภาษาไทยจะมีการเว้นวรรคเป็นระยะเพื่อให้ผู้อ่านทำความเข้าใจกับความหมายของคำ
การตัดคำโดยใช้ N-Gram โดยทำการนำบางส่วนของข้อความนั้นออกมาเป็นข้อความตามค่า N ซึ่งเรียกวิธีนี้ว่า N-Gram เข้ามาใช้ในการตัดคำแทน และเราจะทำการเพิ่มช่องว่างข้างหน้า และท้ายของข้อความ (ใช้ _ ในการแสดงช่องว่าง) เพื่อเพิ่มโอกาสในการจับคู่ของคำที่อยู่ข้างต้น และท้ายของข้อความ แต่ในภาษาไทยนั้นเราไม่สามารถกำหนดได้ว่า 1 ตัวอักษรคือ 1 Gram เนื่องจากภาษาไทยมีสระและวรรณยุกต์ ดังนั้นคำที่ประกอบไปด้วยสระ และวรรณยุกต์จะถือว่าเป็น 1 Gram เช่น มีข้อความ “สวัสดี” ทำการตัดคำแบบ N-Gram ได้ดังภาพที่ 7
฿าพที่ 7 แสดงการตัดคำแบบ N-Gram
3.4 Indexing
ในขั้นตอนนี้ระบบจะทำการสร้างดัชนีจากเอกสารบนเว็บ โดย Crawler ทำการดูดเอกสารมาจากเว็บต่าง ๆ โดยที่เอกสารต่าง ๆ ต้องผ่านการประมวลผลข้อความ (Text Processing) มาก่อน เพื่อสกัดเอาคำที่สำคัญ ๆ มาไปสร้างดัชนีคำ (Index Term) ซึ่งขั้นตอนการประมวลผลข้อความจะทำการตัดช่องว่าง คำหยุด (Stop Words) และแปลงคำให้เป็นรากศัพท์ (Streaming) เมื่อมีการเปลี่ยนแปลงเอกสารหรือการเพิ่มเอกสาร ระบบจะต้องการสร้างดัชนีใหม่เพื่อให้สอดคล้องกับเอกสารใหม่ โดยได้ใช้เทคนิคดัชนีผกผัน (Incremental Indexing) ซึ่งทำให้ไม่เสียเวลาในการแก้ไขข้อมูลดัชนีใหม่ทั้งหมด ในกรณีที่มีการเปลี่ยนแปลงของเอกสารเพียงเล็กน้อย ซึ่งรายงานนี้ได้ใช้การสร้างดัชนีแบบ Inverted File Index โดยเมื่อทำการประมวลผลข้อความตามที่ได้กล่าวไปข้างต้นแล้ว จากนั้นจึงนำมาเก็บเป็นไฟล์ดัชนีซึ่งมีคำต่าง ๆ พร้อมทั้งจำนวนเอกสารที่คำนั้น ๆ ปรากฎอยู่ และแต่ละคำก็จะมีข้อมูลซึ่งระบุรายการหมายเลขของเอกสารพร้อมทั้งจำนวนค่าที่ปรากฎอยู่ในเอกสารนั้น ดังภาพที่ 8 และเก็บรายละเอียดของเอกสารบนเว็บ เช่น URL เพื่ออ้างถึงที่อยู่ของเว็บเพจนั้นๆ ซึ่งกระบวนการสร้างดัชนีคำมีรายละเอียดดังภาพที่ 9
วิธีการในการจัดทำดัชนีของคำหลักที่พบภายในเอกสาร โดยการกำหนดความสำคัญของคำเมื่อเทียบกับเอกสารทั้งระบบ โดยใช้ค่า TF/IDF (Term Frequency/Inverse Document Frequency) มีสูตร ดังนี้
โดยที่
Wij คือค่าน้ำหนักของคำที่ tj ในเอกสาร Di
tfij คือความถี่ของคำที่ tj ในเอกสาร Di
N คือจำนวนเอกสารทั้งหมด
nj คือจำนวนเอกสารที่มีคำที่ tj ปรากฎอยู่อย่างน้อย 1 ครั้ง
พารามิเตอร์ nj ในสมการนี้จะหาค่าได้เมื่อระบบได้รู้ทุกเอกสารที่มีในระบบ ในกรณีนี้จะต้องมีฐานข้อมูลของคำไว้ให้ระบบ โดยคำในฐานข้อมูลนี้ได้มีการตัดคำหยุด (Stop Word) ออกไปแล้ว เพื่อกรองคำที่ไม่สื่อถึงความสำคัญของเอกสาร ดังนั้น คำที่มีค่าความสำคัญในขอบเขตที่กำหนดจะถูกเลือกเป็นคำสำคัญ (Significant word) และจะถูกจัดเก็บลงในฐานข้อมูล
฿าพที่ 8 การสร้างดัชนีแบบ Inverted Index
฿าพที่ 9 ฐานข้อมูลจาก Indexer
3.5 Searching
เป็นส่วนที่นำคําที่ต้องการค้นหาจากผู้ใช้ผ่านทาง User Interface มาค้นหาในฐานข้อมูล และส่งผลการค้นหากลับไปแสดงบนหน้าจอ โดยนําคําศัพท์แต่ละคําที่ได้มาเปิดหาในฐานข้อมูลดัชนีคำและนําผลลัพธ์ที่ได้จากการค้นหาของแต่ครั้งมาหาเอกสารที่มีคําศัพท์ครบทุกคํา แล้วจึงแสดงชื่อ URL และคําอธิบายของเว็บเพจนั้น ๆ เพื่อกลับไปแสดงทางหน้าจอของผู้ใช้งาน
ซึ่ง Model ที่นำมาใช้ คือ Vector Space Model (VSM) โดยการค้นคืนแบบ VSM นั้น จะทำการค้นคืนได้เอกสารที่มีแม้แต่ความเหมือนแค่เพียงบางส่วน โดยที่ไม่ต้องเป็นคำที่ตรงกันทั้งหมด ซึ่งค่าความเหมือนระหว่างเอกสารกับคำค้น โดยคุณสมบัติของ Vector ทำให้สามารถคำนวณค่าความคล้ายคลึง (Similarity) จากการคำนวณด้วยค่าของมุม Cosine ซึ่งพิจารณาจากความถี่ของคำ และเอกสารที่ค้นคืนได้สามารถนำไปจัดอันดับ (Ranking) ได้ โดยมีสูตรคำนวณหาค่า Similarity ดังนี้
โดยเริ่มจากการให้น้ำหนักของคำที่ใช้กันอย่างมากในการสืบค้นข้อมูลคือ tf x idf (Term Frequency x Inverse Document Frequency) โดยค่า idf คำนวณจากค่า log(N/df) ซึ่ง N คือจำนวนเอกสารในชุดเอกสารทั้งหมด และ df คือ จำนวนเอกสารที่มีคำ ๆ นั้นปรากฎอยู่ โดยที่ค่า tf คือ ความถี่ของคำ k จากสูตรหาค่า Similarity จึงหาค่าความคล้ายคลึงของคู่เอกสารได้
3.6 Ranking
เมื่อทำการค้นหาข้อมูล (Searching) เพื่อนำมาแสดงให้กับผู้ใช้ จะมีการจัดทำลำดับของเอกสาร (Ranking) ตามลำดับความเหมือนของเอกสารกับข้อความที่ต้องการค้นหา (Similarity) ซึ่งเอกสารที่เกี่ยวข้องกับผู้ใช้มากที่สุด (High Relevance) จะถูกแสดงอยู่ในลำดับต้น ๆ ซึ่งการจัดลำดับของเอกสารจะดูจากความถี่ของคำในเอกสาร
4. หน้าจอ Search Engine : Pan & James Search
฿าพที่ 10 แสดงหน้าจอ Crawler : James Bot
฿าพที่ 11 แสดงหน้าจอหลักของ Search Engine : Pan & James Search
฿าพที่ 12 แสดงหน้าจอผลลัพธ์ของการ Search
5. สรุปผล
5.1 การสกัดคำออกจากเว็บเพจที่ได้ทำการ Crawler นั้นยังทำได้ไม่ดีพอ บางเว็บเพจมีเนื้อหาที่มีหลากหลายภาษา , สัญลักษณ์ และเว็บเพจต่าง ๆ ถูกเขียนอย่างไร้โครงสร้าง (Un Structure) อีกทั้งเว็บเพจสมัยใหม่ใช้เทคโนโลยี Server Side Script ที่พัฒนาบนเว็บเซอร์เวอร์ เช่น ภาษา PHP , ASP.NET และ JSP เป็นต้น ทำให้การ Crawler ไม่สามารถได้เนื้อเว็บเพจจริงๆ เพื่อนำมาจัดเก็บเป็น Index จะได้เพียงเฉพาะโครงสร้างของเว็บเพจเท่านั้น
5.2 จากงานวิจัยทางด้านการตัดคำภาษาไทยโดยใช้ N-Gram [1] พบว่าใช้ 3-Gram และ 4-Gram จะทำให้ได้ประสิทธิภาพที่ดี โดยในรายงานฉบับนี้ได้ใช้ N-Gram (4-Gram) มาใช้ในการทำ Query Suggestion โดย นำ Query ที่ผู้ใช้ป้อนเข้ามาเปรียบเทียบใน Dictionary (Lexitron) เพื่อจะได้แนะนำและช่วยคำที่ผู้ใช้อาจป้อน Query ผิด จากการทดลองใช้ 3-Grams สามารถหาค่าความคล้ายคลึงระหว่าง Query กับคำใน Dictionary ได้มากกว่า 4-Grams แต่เมื่อทดลองใช้ 4-Grams สามารถหาค่าความคล้ายคลึงได้น้อยกว่า 3-Grams และยังได้ประสิทธิภาพในการค้นคืนเอกสารได้ดีกว่า 3-Grams
5.3 การตัดคำ (Word Segmentation) การเขียนในภาษาไทยนั้นจะมีความแตกต่างกับภาษาอังกฤษอย่างเด่นชัด เนื่องจากภาษาอังกฤษจะมีช่องว่างในการระบุคำแต่ละคำ ซึ่งการตัดคำของภาษาไทยส่วนใหญ่นั้นจะอาศัยโปรแกรมตัดคำ โดยใช้พจนานุกรมในการตัดคำแต่ก็ไม่ได้มีประสิทธิภาพที่ดี 100% เนื่องจากมีความเป็นไปได้ที่คำที่ปรากฏในเอกสาร อาจจะไม่ปรากฏในพจนานุกรม และไม่สามารถตัดคำที่เป็นประโยคได้ ดังนั้นจึงทำให้ประสิทธิภาพการสืบค้นและการทำ Index ยังไม่ดีเท่าที่ควร
5.4 การ Search โดยใช้เทคนิค Vector Space Mode นั้นได้ค่า Rank ของเว็บเพจที่ค้นหา แต่อาจไม่ตรงกับความต้องการของผู้ใช้จริงๆ เนื่องจากเป็นเพียงการนำ Query ที่ User ป้อนไปค้นหากับ Index Term โดยดูจากความถี่ของคำนั้นในแต่ละเว็บเพจที่ถูกจัดทำ Index ไว้และนำมาแสดงผลลัพท์ให้กับผู้ใช้ตามลำดับ ซึ่งเนื้อหา ความหมาย ไม่ตรงกับความต้องการของผู้สืบค้น เช่น ผู้ใช้ต้องการค้นหาคำว่า “สุรินทร์” แต่ผลลัพท์ที่ได้จากการ Ranking อาจได้ผลลัพท์เกี่ยวกับจังหวัดสุรินทร์มาในอันดับต้น ๆ แต่ผู้ใช้อาจหมายถึงหมู่เกาะสุรินทร์ จังหวัดพังงาก็ได้
6. ข้อเสนอแนะ
6.1 สืบค้นโดยดูจาก Keyword อาจไม่ตรงกับความต้องการของผู้ใช้ (Relevant) ควรนำคำในลักษณะเชิงความหมายมาใช้ โดยการสร้างฐานความรู้และโครงสร้างความรู้เชิงความหมาย (Knowledge Base and Ontology) ซึ่งออนโทโลยีในการอธิบายความหมายของสิ่งต่าง ๆ สามารถจัดหมวดหมู่เอกสารของข้อมูลได้ในขอบเขตความสนใจหนึ่ง ๆ (Domain) ออนโทโลยีถูกสร้างขึ้นมาเพื่อจำกัดองค์ความรู้ (Knowledge) ของขอบเขตข้อมูลนั้น ๆ การนำออนโทโลยีมาใช้งานจึงเป็นทางเลือกหนึ่งในการแชร์ข้อมูล และแยกองค์ความรู้ออกจากฐานข้อมูล เพื่อให้ได้ผลลัพท์ที่ตรงตามผู้ใช้มากที่สุด และสามารถค้นหาเว็บเพจที่ตรงตามความต้องการของผู้ใช้ได้ดีกว่าค้นด้วยคำสำคัญ (Keyword)
6.2 การ Crawler นั้นไม่ควรสำเนาเว็บเพจไว้ที่ Server ควรจัดเก็บเฉพาะ Index เพียงอย่างเดียว เพื่อประหยัดเนื้อที่ โดยจัดเก็บเฉพาะข้อมูลสำคัญ ๆ เช่น URL, Title , Keyword เป็นต้น และเมื่อผู้ใช้ค้นหาจะแสดง URL เพื่อให้ผู้ใช้ Link ไปยังเว็บเพจนั้น ๆ แทน
6.3 การตัดคำเพื่อสร้างดัชนีคำนั้น เราได้ใช้หลักการตัดคำโดยใช้พจนานุกรม (Dictionary) เพียงอย่างเดียว ข้อเสนอแนะคือ ควรใช้แบบจำลอง N-Gram เพื่อเพิ่มความสามารถของการตัดคำ หรือควรนำหลักการตัดคำโดยใช้กฎ (Rule base approach) และหลักการตัดคำโดยใช้คลังข้อมูล (Corpus based approach) มาผสมผสานกัน เพื่อเพิ่มความถูกต้อง และแม่นยำในการค้นหา
6.4 การสร้างดัชนีคำ ควรนำเทคนิคอื่นมาใช้ในการวิเคราะห์คำให้ได้ผลมากยิ่งขึ้น เนื่องจากจะมีคำบางประเภทที่ทำให้หาคำในพจนานุกรม เช่น คำกำกวม คำที่ไม่รู้จัก เป็นต้น ควรนำเทคนิคการตัดคำหลาย ๆ แบบมาประยุกต์ใช้ เช่น การทำเหมืองข้อความ (Text Mining) หรืออาจใช้การจัดกลุ่มเอกสาร (Document Clustering) ซึ่งเป็นวิธีที่จะจัดกลุ่มเอกสารปริมาณมาก ๆ แบบอัตโนมัติ เพื่อแยกเอกสารออกเป็นกลุ่มตามความคล้ายคลึงและความสัมพันธ์กันซึ่งขึ้นอยู่กับข้อความที่ปรากฏในเอกสารแต่ละฉบับ
7. เอกสารอ้างอิง
[1] อัษฎางค์ แตงไทย และ ชุลีรัตน์ จรัสกุลชัย, “การย่อความ฿าษาไทยโดยกรรมวิธีการแยกค่า
แบบเดี่ยว”, The Proc of NCSEC. 2004.
[2] Ricardo Baeza-Yates and Berthier Ribeiro-Neto(1999) : Modern Information Retrieval , Addison-Wesley
[3] A Collaborative Framework for Collecting Thai Unknown Words from
the Web [National Electronics and Computer Technology Center (NECTEC)]
Available on http://acl.ldc.upenn.edu/P/P06/P06-2045.pdf
