เจาะลึกระดับ C++

บทแนะนำภาษา C++

ส่วนแรกของบทแนะนำนี้ครอบคลุมเนื้อหาพื้นฐานที่ได้นำเสนอไปแล้วใน 2 โมดูลสุดท้าย รวมถึงให้ข้อมูลเพิ่มเติมเกี่ยวกับแนวคิดขั้นสูง เรามุ่งเน้นโมดูลนี้ที่หน่วยความจำแบบไดนามิก รวมถึงรายละเอียดเพิ่มเติมเกี่ยวกับออบเจ็กต์และคลาส นอกจากนี้ยังมีการแนะนำหัวข้อขั้นสูงบางอย่าง เช่น การรับช่วงมา พหุสัณฐาน เทมเพลต ข้อยกเว้น และเนมสเปซ เราจะศึกษาสิ่งเหล่านี้ภายหลังในหลักสูตร C++ ขั้นสูง

การออกแบบตามวัตถุ

นี่เป็นบทแนะนำที่ยอดเยี่ยมเกี่ยวกับการออกแบบตามออบเจ็กต์ เราจะใช้วิธีการที่แสดงในโปรเจ็กต์ของโมดูลนี้

เรียนรู้ตามตัวอย่างที่ 3

เรามุ่งเน้นโมดูลนี้ในการฝึกฝนการใช้ตัวชี้ การออกแบบเชิงวัตถุ อาร์เรย์หลายมิติ และคลาส/ออบเจ็กต์ให้มากขึ้น ลองดูตัวอย่างต่อไปนี้ เราไม่ได้จะเน้นย้ำได้มากพอว่ากุญแจสำคัญในการเป็นโปรแกรมเมอร์ที่ดีคือการฝึกฝน ฝึกฝน และฝึกฝน

---

แบบฝึกหัดที่ 1: ฝึกมากขึ้นโดยใช้ตัวชี้

หากต้องการแบบฝึกหัดเพิ่มเติมเกี่ยวกับเคอร์เซอร์ โปรดอ่านแหล่งข้อมูลนี้ ซึ่งครอบคลุมเคอร์เซอร์ทุกด้านและมีตัวอย่างโปรแกรมมากมาย

โปรแกรมต่อไปนี้จะออกมาเป็นอย่างไร โปรดอย่าเรียกใช้โปรแกรมดังกล่าว แต่ให้วาดภาพความทรงจำเพื่อระบุเอาต์พุต

void Unknown(int *p, int num);
void HardToFollow(int *p, int q, int *num);

void Unknown(int *p, int num) {
  int *q;

  q = #
  *p = *q + 2;
  num = 7;
}

void HardToFollow(int *p, int q, int *num) {
  *p = q + *num;
  *num = q;
  num = p;
  p = &q;
  Unknown(num, *p);
}

main() {
  int *q;
  int trouble[3];

  trouble[0] = 1;
  q = &trouble[1];
  *q = 2;
  trouble[2] = 3;

  HardToFollow(q, trouble[0], &trouble[2]);
  Unknown(&trouble[0], *q);

  cout << *q << " " << trouble[0] << " " << trouble[2];
}

เมื่อพิจารณาผลลัพธ์ด้วยตนเองแล้ว ให้เรียกใช้โปรแกรมเพื่อดูว่าคุณถูกต้องหรือไม่

แบบฝึกหัดที่ 2: ฝึกใช้คลาสและวัตถุมากขึ้น

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

แบบฝึกหัดที่ 3: อาร์เรย์หลายมิติ

ลองพิจารณาโปรแกรมต่อไปนี้

const int kStudents = 25;
const int kProblemSets = 10;

// This function returns the highest grade in the Problem Set array.
int get_high_grade(int *a, int cols, int row, int col) {
  int i, j;
  int highgrade = *a;

  for (i = 0; i < row; i++)
    for (j = 0; j < col; j++)
      if (*(a + i * cols + j) > highgrade)  // How does this line work?
        highgrade = *(a + i*cols + j);
  return highgrade;
}

int main() {
 int grades[kStudents][kProblemSets] = {
   {75, 70, 85, 72, 84},
   {85, 92, 93, 96, 86},
   {95, 90, 83, 76, 97},
   {65, 62, 73, 84, 73}
 };
 int std_num = 4;
 int ps_num = 5;
 int highest;

 highest = get_high_grade((int *)grades, kProblemSets, std_num, ps_num);
 cout << "The highest problem set score in the class is " << highest << endl;

 return 0;
}

โปรแกรมนี้จะมีข้อความระบุว่า "บรรทัดนี้ทำงานอย่างไร" - คุณพอจะเข้าใจแล้วหรือยัง โปรดดูคำอธิบายของเราที่นี่

เขียนโปรแกรมที่เริ่มต้นอาร์เรย์ 3-สลัว และเติมค่ามิติข้อมูลที่ 3 ด้วยผลรวมของดัชนีทั้ง 3 รายการ นี่คือวิธีแก้ปัญหาของเราที่นี่

แบบฝึกหัดที่ 4: ตัวอย่างการออกแบบ OO ที่ครอบคลุม

ต่อไปนี้เป็นตัวอย่างการออกแบบเชิงวัตถุโดยละเอียดที่บอกขั้นตอนตั้งแต่ต้นจนจบ โค้ดเวอร์ชันสุดท้ายจะเขียนด้วยภาษาโปรแกรม Java แต่คุณจะอ่านได้ตลอดหากเดินทางมาได้ไกลเพียงใด

โปรดสละเวลาทำความเข้าใจตัวอย่างทั้งหมด วิดีโอนี้แสดงให้เห็นภาพกระบวนการและเครื่องมือออกแบบที่สนับสนุนกระบวนการเป็นอย่างดี

การทดสอบหน่วย

เกริ่นนำ

การทดสอบเป็นส่วนสำคัญของกระบวนการทางวิศวกรรมซอฟต์แวร์ การทดสอบหน่วยเป็นการทดสอบประเภทหนึ่งซึ่งจะตรวจสอบฟังก์ชันการทำงานของซอร์สโค้ดโมดูลขนาดเล็กเพียงโมดูลเดียวการทดสอบหน่วยดำเนินการโดยวิศวกรเสมอ และมักจะทำในเวลาเดียวกับที่กำลังเขียนโค้ดโมดูล ไดรเวอร์ทดสอบที่คุณใช้ทดสอบคลาส Composer และฐานข้อมูลคือตัวอย่างของการทดสอบ 1 หน่วย

การทดสอบหน่วยมีลักษณะดังต่อไปนี้ พวกเขา...

• ทดสอบคอมโพเนนต์แยกต่างหาก
• เป็นตัวกำหนด
• มักจะจับคู่กับคลาสเดี่ยว
• หลีกเลี่ยงการพึ่งพิงทรัพยากรภายนอก เช่น ฐานข้อมูล ไฟล์ เครือข่าย
• ดำเนินการอย่างรวดเร็ว
• สามารถเรียกใช้ในลำดับใดก็ได้

มีเฟรมเวิร์กและวิธีการแบบอัตโนมัติซึ่งให้การสนับสนุนและความสอดคล้องสำหรับการทดสอบหน่วยในองค์กรวิศวกรรมซอฟต์แวร์ขนาดใหญ่ มีเฟรมเวิร์กการทดสอบหน่วยโอเพนซอร์สที่ซับซ้อน ซึ่งเราจะดูข้อมูลเพิ่มเติมได้จากบทเรียนนี้ภายหลัง

ด้านล่างคือการทดสอบที่เกิดขึ้นเป็นส่วนหนึ่งของการทดสอบ 1 หน่วย

เราจะทดสอบสิ่งต่อไปนี้ในสถานการณ์จริง

1. อินเทอร์เฟซของโมดูลได้รับการทดสอบเพื่อให้แน่ใจว่าข้อมูลไหลเข้าและออกได้อย่างถูกต้อง
2. โครงสร้างข้อมูลในเครื่องจะได้รับการตรวจสอบเพื่อให้แน่ใจว่ามีการจัดเก็บข้อมูลอย่างถูกต้อง
3. ระบบจะทดสอบเงื่อนไขขอบเขตเพื่อให้มั่นใจว่าโมดูลทำงานได้อย่างถูกต้องในขอบเขตที่จำกัดหรือจำกัดการประมวลผล
4. เราทดสอบเส้นทางอิสระผ่านโมดูลเพื่อให้แน่ใจว่าแต่ละเส้นทาง และทำให้แต่ละคำสั่งในโมดูลทำงานอย่างน้อย 1 ครั้ง 
   
5. สุดท้าย เราต้องตรวจสอบว่าข้อผิดพลาดได้รับการจัดการอย่างเหมาะสม

การครอบคลุมของโค้ด

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

ในแผนภาพนี้ เส้นสีแดงจะไม่ได้รับการทดสอบ แต่ในขณะที่ทดสอบเส้นที่ไม่มีสี

แทนที่จะพยายามให้ครอบคลุม 100% เราเน้นไปที่การทดสอบที่ทำให้มั่นใจว่าโมดูลทำงานอย่างถูกต้อง โดยเราจะทดสอบสิ่งต่อไปนี้

• ตัวพิมพ์เล็ก
• การทดสอบช่วง เช่น การทดสอบค่าบวก/ลบ
• กรณีสุดโต่ง
• กรณีความล้มเหลว
• การทดสอบเส้นทางที่มีแนวโน้มจะดำเนินการมากที่สุด
  

กรอบการทดสอบหน่วย

เฟรมเวิร์กการทดสอบ 1 หน่วยส่วนใหญ่ใช้การยืนยันเพื่อทดสอบค่าระหว่างการดำเนินการในเส้นทาง การยืนยันคือข้อความที่ตรวจสอบว่าเงื่อนไขเป็นจริงหรือไม่ การยืนยันอาจเกิดจากความสำเร็จ ความล้มเหลวที่ไม่ร้ายแรง หรือความล้มเหลวที่ร้ายแรง หลังจากดำเนินการยืนยัน โปรแกรมจะดำเนินต่อไปตามปกติหากผลลัพธ์สำเร็จหรือล้มเหลวไม่ร้ายแรง ถ้ามีความล้มเหลวร้ายแรงเกิดขึ้น ระบบจะล้มเลิกฟังก์ชันปัจจุบัน

การทดสอบประกอบด้วยโค้ดที่กำหนดสถานะหรือปรับเปลี่ยนโมดูล ควบคู่ไปกับการยืนยันจำนวนหนึ่งซึ่งจะยืนยันผลลัพธ์ที่คาดหวัง หากการยืนยันทั้งหมดในการทดสอบสำเร็จ นั่นคือ ให้ผลลัพธ์เป็น "จริง" หมายความว่าการทดสอบจะสำเร็จหรือไม่

กรอบการทดสอบประกอบด้วยการทดสอบอย่างน้อย 1 รายการ เราจัดกลุ่มการทดสอบเป็นกรณีการทดสอบที่แสดงถึงโครงสร้างของโค้ดที่ทดสอบ ในหลักสูตรนี้ เราจะใช้ CPPUnit เป็นเฟรมเวิร์กการทดสอบหน่วย เฟรมเวิร์กนี้ช่วยให้เราเขียนการทดสอบ 1 หน่วยใน C++ และเรียกใช้การทดสอบได้โดยอัตโนมัติ ทำให้มีรายงานเกี่ยวกับความสำเร็จหรือความล้มเหลวของการทดสอบ

การติดตั้ง CPPUnit

ดาวน์โหลดโค้ด CPPUnit จาก SourceForge ค้นหาไดเรกทอรีที่เหมาะสมแล้ววางไฟล์ tar.gz ในนั้น จากนั้นป้อนคำสั่งต่อไปนี้ (ใน Linux, Unix) โดยใช้ชื่อไฟล์ cppunit ที่เหมาะสม

gunzip filename.tar.gz
tar -xvf filename.tar

หากทำงานใน Windows คุณอาจต้องหายูทิลิตีในการแยกไฟล์ tar.gz ขั้นตอนถัดไปคือการรวบรวมไลบรารี เปลี่ยนเป็นไดเรกทอรี cppunit ไฟล์ดังกล่าวมีไฟล์ INSTALL ซึ่งให้คำแนะนำที่เฉพาะเจาะจง โดยปกติแล้ว คุณจะต้องเรียกใช้สิ่งต่อไปนี้

./configure
make install

หากพบปัญหา โปรดดูไฟล์ INSTALL ไลบรารีมักจะอยู่ในไดเรกทอรี cppunit/src/cppunit หากต้องการตรวจสอบว่าคอมไพล์ใช้งานได้ ให้ไปที่ cppunit/examples/simple ไดเรกทอรี และพิมพ์ "make" หากทุกอย่างคอมไพล์ได้อยู่แล้ว คุณก็พร้อมแล้ว

มีบทแนะนำที่ยอดเยี่ยมได้ที่นี่ โปรดอ่านบทแนะนำนี้และสร้างคลาสจำนวนเชิงซ้อนและการทดสอบ 1 หน่วยที่เกี่ยวข้อง มีตัวอย่างเพิ่มเติมหลายรายการในไดเรกทอรี cppunit/examples

เหตุใดฉันจึงต้องทำเช่นนี้

การทดสอบ 1 หน่วยมีความสำคัญอย่างยิ่งในอุตสาหกรรมด้วยกันด้วยเหตุผลหลายประการ คุณคุ้นเคยกับเหตุผลหนึ่งอยู่แล้ว คือเราต้องหาวิธีตรวจสอบงานของเราขณะพัฒนาโค้ด แม้ในขณะที่เราพัฒนาโปรแกรมขนาดเล็กมากๆ เราก็เขียนผู้ตรวจสอบหรือคนขับด้วยสัญชาตญาณเพื่อให้มั่นใจว่าโปรแกรมของเราทำในสิ่งที่คาดหวัง

จากประสบการณ์อันยาวนาน วิศวกรทราบว่าโอกาสที่โปรแกรมจะได้ผลจริงในครั้งแรกนั้นน้อยมาก การทดสอบ 1 หน่วยต่อยอดแนวคิดนี้โดยทำให้โปรแกรมการทดสอบเป็นแบบตรวจสอบด้วยตนเองและทำซ้ำได้ โดยการยืนยันจะแทนที่การตรวจสอบผลลัพธ์ด้วยตนเอง และเนื่องจากทำให้ตีความผลลัพธ์ได้ง่าย (การทดสอบผ่านหรือไม่ผ่านก็ได้) การทดสอบจึงทำซ้ำแล้วซ้ำอีกได้ ซึ่งทำให้มีตาข่ายนิรภัยที่ทำให้โค้ดมีความยืดหยุ่นต่อการเปลี่ยนแปลงมากขึ้น

ลองทำความเข้าใจเรื่องนี้ให้เข้าใจง่ายๆ ก็คือ เมื่อคุณส่งรหัสที่เสร็จแล้วไปยัง CVS เป็นครั้งแรก รหัสจะทํางานได้อย่างสมบูรณ์แบบ และยังคงทำงานได้อย่างสมบูรณ์อีกระยะหนึ่ง แล้วอยู่มาวันหนึ่ง มีคนเปลี่ยนรหัสของคุณ ในไม่ช้าหรือหลังจากนั้นจะมีผู้ทำให้โค้ดเสียหาย คุณคิดว่าพวกเขาจะสังเกตเห็นได้เองไหม ไม่น่าจะเป็นไปได้ แต่เมื่อคุณเขียนการทดสอบ 1 หน่วย จะมีระบบที่เรียกใช้การทดสอบดังกล่าวได้โดยอัตโนมัติทุกวัน ทั้งหมดนี้เรียกว่าระบบการผสานรวมอย่างต่อเนื่อง ดังนั้น เมื่อวิศวกรคนนั้น X ทำลายโค้ดของคุณ ระบบจะส่งอีเมลที่ไม่เหมาะสมไปให้จนกว่าวิศวกรจะซ่อมเสร็จ แม้ว่าวิศวกร X จะเป็นคุณก็ตาม

นอกจากช่วยคุณพัฒนาซอฟต์แวร์และคอยดูแลซอฟต์แวร์ให้ปลอดภัยเมื่อมีการเปลี่ยนแปลงแล้ว ยังมีการทดสอบ 1 หน่วย ดังนี้

• สร้างข้อกำหนดเฉพาะที่ดำเนินการได้และเอกสารที่ซิงค์กับโค้ดอยู่เสมอ กล่าวคือ คุณอาจอ่านการทดสอบ 1 หน่วยเพื่อเรียนรู้เกี่ยวกับลักษณะการทำงานที่โมดูลรองรับ
• ช่วยให้คุณแยกข้อกำหนดออกจากการนำไปใช้งานได้ เนื่องจากคุณกำลังยืนยันพฤติกรรมที่มองเห็นได้จากภายนอก คุณจึงมีโอกาสที่จะคิดเกี่ยวกับพฤติกรรมดังกล่าวอย่างชัดเจน แทนที่จะผสมผสานกันเรื่องวิธีนำพฤติกรรมดังกล่าวไปใช้
• รองรับการทดสอบ หากคุณมีตาข่ายนิรภัยที่แจ้งเตือนเมื่อคุณทำงานผิดปกติของโมดูล คุณก็มีแนวโน้มที่จะลองทำสิ่งต่างๆ และกำหนดค่าการออกแบบใหม่มากขึ้น
• ปรับปรุงการออกแบบ การเขียนการทดสอบ 1 หน่วยอย่างละเอียดมักทำให้คุณต้องทำให้โค้ดทดสอบได้มากขึ้น โค้ดที่ทดสอบได้มักจะเป็นแบบแยกส่วนมากกว่าโค้ดที่ทดสอบไม่ได้
• รักษาคุณภาพสูง ข้อบกพร่องเล็กๆ น้อยๆ ในระบบที่สำคัญอาจทำให้บริษัทสูญเสียเงินหลายล้านดอลลาร์ หรือแย่กว่านั้นคือความสุขหรือความไว้วางใจของผู้ใช้ ตาข่ายนิรภัยที่การทดสอบ 1 หน่วยจะช่วยลดความเป็นไปได้นี้ การแก้ไขข้อบกพร่องตั้งแต่เนิ่นๆ ช่วยให้ทีม QA มีเวลารับมือกับความล้มเหลวที่ซับซ้อนและซับซ้อน แทนที่จะต้องรายงานความล้มเหลวที่ชัดเจน

ใช้เวลาเขียนการทดสอบหน่วยโดยใช้ CPPUnit สำหรับแอปพลิเคชันฐานข้อมูล Composer ดูไดเรกทอรี cppunit/examples/ เพื่อรับความช่วยเหลือ

วิธีการทำงานของ Google

บทนำ

ลองจินตนาการถึงพระสงฆ์ในยุคกลางกำลังดูพระคัมภีร์นับพันเล่มในที่เก็บถาวรของอารามของตน"อยู่ที่ไหนนั่นของอริสโตเติล..."

โชคดีสำหรับเขาแล้ว บันทึกลายมือได้รับการจัดระเบียบตามเนื้อหาและจารึกสัญลักษณ์พิเศษไว้เพื่อให้ดึงข้อมูลที่มีอยู่ในแต่ละรายการได้สะดวก หากไม่มีการจัดระเบียบเช่นนี้ การค้นหาต้นฉบับที่เกี่ยวข้องก็เป็นเรื่องยากมาก

กิจกรรมการเก็บและเรียกข้อมูลที่เป็นลายลักษณ์อักษรจากคอลเล็กชันขนาดใหญ่เรียกว่าการดึงข้อมูล (IR) กิจกรรมนี้มีความสำคัญมากขึ้นเรื่อยๆ ในหลายศตวรรษ โดยเฉพาะสิ่งประดิษฐ์ต่างๆ เช่น กระดาษและแท่นพิมพ์ ก่อนหน้านี้สมัยนี้เคยมีคนอยู่แค่ไม่กี่คน อย่างไรก็ตาม ในปัจจุบัน ผู้คนหลายร้อยล้านคนมีส่วนร่วมในการดึงข้อมูลในทุกๆ วันเมื่อใช้เครื่องมือค้นหาหรือค้นหาในเดสก์ท็อป

การเริ่มต้นใช้งานการดึงข้อมูล

ดร. ซูสส์เขียนหนังสือสำหรับเด็ก 46 เล่มตลอดระยะเวลา 30 ปี หนังสือของเขาบอกเล่าถึงแมว วัว และช้าง ซึ่งเป็นผู้ที่เป็นรอยยิ้มกว้างและเจ้าขุนนางก็ได้ คุณจำได้ไหมว่าสิ่งมีชีวิตชนิดใดอยู่ในเรื่องใด หากคุณไม่เป็นผู้ปกครอง จะมีเฉพาะเด็กๆ เท่านั้นที่จะบอกคุณได้ว่าเรื่องราวของดร. ซูสส์ชุดใดที่มีสิ่งมีชีวิตลักษณะนี้

(COW และ BEE) หรือ CROWS

เราจะใช้โมเดลการดึงข้อมูลแบบคลาสสิกบางรูปแบบเพื่อช่วยเราแก้ไขปัญหานี้

แนวทางที่ชัดเจนคือแบบ Brute Force นั่นคือ รับเรื่องราวทั้ง 46 เรื่องของ Dr. Seuss แล้วเริ่มอ่านเลย จดบันทึกแต่ละเล่มที่มีคำว่า COW และ BEE จากนั้นค้นหาหนังสือที่มีคำว่า CROWS ตรงนี้คอมพิวเตอร์เร็วกว่าเรามาก หากมีข้อความทั้งหมดจากหนังสือของ Dr. Seuss ในรูปแบบดิจิทัล เช่น เป็นไฟล์ข้อความ เราก็จะใช้ไฟล์เหล่านั้น Grep ได้ เทคนิคนี้ใช้ได้ผลดีสำหรับคอลเล็กชันเล็กๆ เช่น หนังสือของดร. ซูสส์

อย่างไรก็ตาม มีหลายสถานการณ์ที่เราต้องการมากกว่านี้ ตัวอย่างเช่น การรวบรวมข้อมูลทั้งหมดที่ออนไลน์อยู่ในปัจจุบันมีขนาดใหญ่เกินกว่าที่จะจัดการได้ นอกจากนี้เรายังไม่ได้ต้องการเพียงเอกสารที่ตรงกับเงื่อนไขของเรา แต่เรายังเคยชินกับการจัดอันดับเอกสารตามความเกี่ยวข้องด้วย

อีกวิธีหนึ่งนอกเหนือจาก grep คือการสร้างดัชนีของเอกสารในคอลเล็กชันก่อนที่จะทำการค้นหา ดัชนีใน IR คล้ายกับดัชนีที่อยู่ท้ายตำราเรียน เราทำรายการของคำ (หรือคำ) ทั้งหมดในเรื่องราวของดร.ซูสส์ โดยไม่รวมคำต่างๆ เช่น "the" "and" และคำเชื่อมอื่นๆ คำบุพบท ฯลฯ (เรียกว่า คำหยุด) จากนั้นเราจะนำเสนอข้อมูลนี้ในลักษณะที่อำนวยความสะดวกในการค้นหาคำศัพท์และระบุเรื่องราวที่มี

การแทนค่าที่เป็นไปได้ 1 อย่างคือเมทริกซ์ที่มีเรื่องราวอยู่ด้านบนสุด และคำศัพท์ที่อยู่ในแต่ละแถว "1" ในคอลัมน์บ่งบอกว่าคำนั้นปรากฏในเรื่องราวของคอลัมน์นั้น

เราจะดูแต่ละแถวหรือคอลัมน์ ในรูปแบบเวกเตอร์ได้ เวกเตอร์บิตของแถวจะระบุว่าคำนั้นปรากฏอยู่ที่เรื่องราวใด เวกเตอร์บิตของคอลัมน์จะระบุคำศัพท์ที่ปรากฏในเรื่องราว

กลับไปที่ปัญหาเดิม:

(COW และ BEE) หรือ CROWS

เราใช้เวกเตอร์บิตของคำเหล่านี้ก่อนใช้ AND ด้วยคำสั่ง OR เล็กน้อย จากนั้นใช้ OR กับผลลัพธ์

(100001 และ 010011) หรือ 000010 = 000011

คำตอบ: "คุณบราวน์ Can Moo! จะทำได้ไหม" และ "Lorax" นี่คือภาพ ของโมเดลบูลีน ซึ่งเป็นโมเดลที่ "ตรงกันทั้งหมด"

สมมติว่าเราต้องขยายเมทริกซ์ให้รวมเรื่องราวทั้งหมดเกี่ยวกับ Dr. Seuss และคำที่เกี่ยวข้องทั้งหมดในเรื่องราวนั้น เมทริกซ์จะเพิ่มขึ้นอย่างมาก และการสังเกตที่สำคัญคือรายการส่วนใหญ่จะเป็น 0 เมทริกซ์อาจไม่ใช่การนำเสนอที่ดีที่สุดสำหรับดัชนี เราต้องคิดค้นวิธีจัดเก็บ 1 ส่วน

การเพิ่มประสิทธิภาพบางอย่าง

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

หากไม่คุ้นเคยกับรายการที่ลิงก์ เพียงทำการค้นหาใน Google ด้วย "รายการที่ลิงก์ใน C++" และคุณจะพบแหล่งข้อมูลมากมายที่อธิบายวิธีสร้างรายการ และการใช้งาน เราจะอธิบายเรื่องนี้อย่างละเอียดยิ่งขึ้นในโมดูลหลังจากนี้

โปรดสังเกตว่าเราใช้รหัสเอกสาร (DocIDs) แทนชื่อของเรื่องราว นอกจากนี้ เรายังจัดเรียง DocID เหล่านี้เพื่อช่วยในการประมวลผลการค้นหา

เราจะประมวลผลการค้นหาอย่างไร สำหรับปัญหาเดิม เราจะหารายการการโพสต์ของ COW ตามด้วยรายการการโพสต์ของ BEE จากนั้นเราจะ "รวม" เข้าด้วยกัน

1. เก็บรักษาเครื่องหมายไว้ในทั้ง 2 รายการและดำเนินการตามรายการโพสต์ 2 รายการ พร้อมกัน
2. ในแต่ละขั้นตอน ให้เปรียบเทียบ DocID ที่ตัวชี้ทั้ง 2 ชี้ไป
3. หากค่าเหล่านี้เหมือนกัน ให้ใส่ DocID ไว้ในรายการผลลัพธ์ หรือมิฉะนั้นให้เลื่อนตัวชี้ไปยัง docID ที่เล็กกว่า

ต่อไปนี้คือวิธีที่เราสามารถสร้างดัชนีกลับสี:

1. กำหนดรหัสเอกสารให้กับเอกสารที่สนใจแต่ละรายการ
2. ระบุคำที่เกี่ยวข้อง (tokenize) ในเอกสารแต่ละฉบับ
3. สำหรับแต่ละคำ ให้สร้างระเบียนที่ประกอบด้วยคำนั้น, DocID ที่มี และความถี่ในเอกสารนั้น โปรดทราบว่าอาจมีระเบียนหลายรายการสำหรับคำหนึ่งๆ หากคำนั้นปรากฏในเอกสารมากกว่า 1 ฉบับ
4. จัดเรียงระเบียนตามคำ
5. สร้างรายการพจนานุกรมและการโพสต์โดยการประมวลผลระเบียนเดียวสำหรับคำๆ หนึ่ง และจะรวมระเบียนหลายรายการสำหรับคำที่ปรากฏในเอกสารมากกว่า 1 ฉบับด้วย สร้างรายการรหัสเอกสารที่ลิงก์ (ตามลำดับการจัดเรียง) แต่ละพจน์ยังมีความถี่ซึ่งเป็นผลรวมของความถี่ในระเบียนทั้งหมดหนึ่งๆ อีกด้วย

โปรเจ็กต์

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

ต่อไปนี้คือขั้นตอนที่เป็นไปได้ในการทำโครงการนี้:

1. สิ่งแรกที่ต้องทำคือกำหนดกลยุทธ์สำหรับการระบุคำในเอกสาร ทำรายการคำหยุดทั้งหมดที่คุณนึกออก แล้วเขียนฟังก์ชันที่อ่านคำในไฟล์ บันทึกคำศัพท์ และกำจัดคำหยุด คุณอาจต้องเพิ่มคำหยุดในรายการเมื่อดูรายการคำจากคำซ้ำ
2. เขียนกรอบการทดสอบ CPPUnit เพื่อทดสอบฟังก์ชัน และสร้าง Makefile เพื่อรวมทุกอย่างเข้าด้วยกันสำหรับบิลด์ ให้คุณตรวจสอบไฟล์เป็น CVS โดยเฉพาะอย่างยิ่งหากคุณทํางานร่วมกับพาร์ทเนอร์ คุณอาจต้องหาข้อมูลเกี่ยวกับวิธีเปิดอินสแตนซ์ CVS ให้กับวิศวกรระยะไกล
3. เพิ่มการประมวลผลเพื่อรวมข้อมูลตำแหน่ง กล่าวคือ ไฟล์ใดและตำแหน่งใดในไฟล์คือคำที่อยู่ในไฟล์ คุณอาจต้องคิดเลขคำนวณ เพื่อระบุเลขหน้าหรือหมายเลขย่อหน้า
4. เขียนกรอบการทดสอบ CPPUnit เพื่อทดสอบฟังก์ชันเพิ่มเติมนี้
5. สร้างดัชนีกลับสีและเก็บข้อมูลตำแหน่งในระเบียนของแต่ละคำ
6. เขียนกรอบการทดสอบเพิ่มเติม
7. ออกแบบอินเทอร์เฟซเพื่อให้ผู้ใช้ป้อนข้อความค้นหาได้
8. ประมวลผลดัชนีกลับสีและส่งข้อมูลตำแหน่งไปยังผู้ใช้โดยใช้อัลกอริทึมการค้นหาที่อธิบายไว้ข้างต้น
9. อย่าลืมใส่กรอบการทดสอบสำหรับส่วนสุดท้ายนี้ด้วย

อย่างที่เราได้ทำโปรเจ็กต์ทั้งหมดมาแล้ว ให้ใช้ฟอรัมและแชทเพื่อค้นหาพาร์ทเนอร์โปรเจ็กต์และแชร์ไอเดีย

ฟีเจอร์เพิ่มเติม

ขั้นตอนการประมวลผลทั่วไปในระบบ IR จำนวนมากเรียกว่าการตัดคำ แนวคิดหลักเบื้องหลังการสร้างจากรากคือผู้ใช้ที่ค้นหาข้อมูลเกี่ยวกับ "การดึงข้อมูล" จะสนใจเอกสารที่มีข้อมูลที่มีคำว่า "ดึงข้อมูล" "ดึงข้อมูล" "การดึงข้อมูล" และอื่นๆ ด้วย ระบบต่างๆ อาจเสี่ยงต่อข้อผิดพลาดได้เนื่องจากโครงสร้างหน้าของรูปไม่ดี จึงทำให้ยากสักหน่อย เช่น ผู้ใช้ที่สนใจ "การดึงข้อมูล" อาจได้รับเอกสารชื่อ "ข้อมูลเกี่ยวกับ Golden Retrievers" เนื่องจากมาจากรากคำเดียวกัน อัลกอริทึมที่มีประโยชน์สําหรับการตัดคำคืออัลกอริทึมของ Porter

แอปพลิเคชัน: ใช้ได้ทุกที่

ดูการประยุกต์ใช้แนวคิดเหล่านี้ได้ที่ Panoramas.dk