ระยะทางแฮมมิง

จากวิกิพีเดีย สารานุกรมเสรี
ตัวอย่างลูกบาศก์ของเลขฐานสอง 3 หลัก
ตัวอย่างลูกบาศก์ของเลขฐานสอง 3 หลักที่แสดงแฮมมิง เช่น 010>110>111 , 100>000>001>011

ในทางทฤษฎีข้อมูลแล้ว ระยะทางแฮมมิง (อังกฤษ: Hamming distance) ระหว่าง 2 ข้อความที่มีความยาวเท่ากัน คือจำนวนตำแหน่งที่มีสัญลักษณ์หรืออักขระที่แตกต่างกัน กล่าวอีกนัยหนึ่ง มันคือจำนวนน้อยที่สุดที่ต้องใช้เพื่อเปลี่ยนจากข้อความหนึ่งไปเป็นอีกข้อความหนึ่ง หรือจำนวนตัวอักษรที่คลาดเคลื่อนที่เปลี่ยนจากข้อความหนึ่งไปเป็นอีกข้อความหนึ่ง

ตัวอย่าง[แก้]

ระยะทางแฮมมิงระหว่าง:

"ความรัก" กับ "ความสุข" คือ 3

1011101 กับ 1001001 คือ 2

2173596 กับ 2733996 คือ 3

คุณสมบัติพิเศษ[แก้]

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

ประวัติ[แก้]

ระยะทางแฮมมิง ตั้งชื่อตาม ริชาร์ด แฮมมิง (Richard Hamming) ผู้ที่นำเสนอให้ใช้ระยะทางแฮมมิงในการตรวจสอบคำ ในคริสต์ทศวรรษ 1950 ระยะทางแฮมมิงได้ถูกใช้ในการสื่อสาร โดยการนับจำนวนเลขฐานสองที่มีความยาวคงที่ ที่มีหลักต่างไปเพื่อตรวจเช็คความผิดพลาด หรือเรียกว่า ระยะทางสัญญาณ (Signal distance) โดยการสื่อสารในระบบดิจิตอลโดยส่วนมากไม่ว่าจะเป็นภาคพื้นดินเช่นระบบโทรศัพท์มือถือจนถึงการสื่อสารผ่านดาวเทียมมีโอกาสที่ข้อมูลที่ส่งผ่านระบบส่อสารผิดพลาดจึงมีการนำ Error Control Coding มาใช้ในการสื่อสารด้วย เพื่อลดความผิดพลาดของการสื่อสาร โดยจากสื่อสาร Error Control Coding คือการเข้ารหัสสัญญาณ และการถอดรหัสสัญญาณ โดยวิธีการลดความผิดพลาดของการสื่อสารทำโดยการตรวจจับความผิดพลาด (Error Detection) หรือแก้ไขข้อมูลความผิดพลาด (Error Correction)ในช่องสัญญาณแต่ละประเภทจะมีความจุของช่องสัญญาณ (Channel Capacity) ที่ไม่เท่ากับคุณสมบัติของช่องสัญญาณกับรหัสมีความสัมพันธ์กันโดยที่ การเข้ารหัสที่ซับซ้อนจะทำให้ข้อมูลที่เข้ารหัสเปลี่ยนไปอยู่ในรูปข้อมูลที่มีขนาดใหญ่ขึ้น ทำให้โอกาสที่จะเกิดการผิดพลาดของข้อมูลสูงขึ้น น้ำหนักของแฮมมิงถูกใช้ในการวิเคราะห์ได้หลายอย่างโดยการนำมาต่อยอดจากทฤษฎี เช่นในทางด้านการออกแบบฮาร์ดแวร์คอมพิวเตอร์ จะใช้ระยะทางแฮมมิงในการลดเวลาในการเปลี่ยนขั้นการทำงานของฮาร์ดแวร์ ซอฟต์แวร์ ที่ใช้เช่นระบบ เอทีเอ็ม ซึ่งข้อมูลที่รับส่งในการสื่อสารต้องไม่มีการผิดพลาดเลย จึงมีการตรวจสอบว่าข้อมูลที่ได้รับผิดพลาดหรือไม่ และหารข้อมูลนั้นผิดพลาดสามารถแก้ไขได้หรือไม่ เป็นต้น

ขั้นตอนวิธี[แก้]

  1. ตรวจสอบข้อความที่จะทำการเปรียบเทียบว่ามีขนาดเท่ากัน
  2. นำอักษร ณ ตำแหน่งเดียวกันมาเปรียบเทียบว่ามีตำแหน่งไหนที่ไม่เป็นตัวเดียวกันบ้าง
  3. จำนวนตัวอักษรที่ไม่เป็นตัวเดียวกันนั้น คือ ระยะแฮมมิง

ตัวอย่างการเขียนโปรแกรมเพื่อตรวจสอบระยะทางแฮมมิง[แก้]

  • รหัสเทียม
   HammingDistance(A,B){
      for (ทุกตัวอักษร) {
         if (ตัวอักษรของ A ไม่เท่ากับ ตัวอักษรของ B){ 
            นับค่า 
         }
      }
      return ตัวนับ
   }
  • ในภาษาC
   int N;
   cin>>N;
   char a[N],b[N];
   cin>>a>>b;
   int sum=0;
   for (int i=0;i<N;i++)if(a[i]!=b[i])sum++;
   cout<<"Hamming distance is "<<sum<<"\n";

วิเคราะห์เวลาการทำงาน[แก้]

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

สรุป[แก้]

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

อ้างอิง[แก้]

ดูเพิ่ม[แก้]

แหล่งข้อมูลอื่น[แก้]