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

ในทางทฤษฎีข้อมูลแล้ว ระยะทางแฮมมิง (อังกฤษ: 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) ที่ไม่เท่ากับคุณสมบัติของช่องสัญญาณกับรหัสมีความสัมพันธ์กันโดยที่ การเข้ารหัสที่ซับซ้อนจะทำให้ข้อมูลที่เข้ารหัสเปลี่ยนไปอยู่ในรูปข้อมูลที่มีขนาดใหญ่ขึ้น ทำให้โอกาสที่จะเกิดการผิดพลาดของข้อมูลสูงขึ้น น้ำหนักของแฮมมิงถูกใช้ในการวิเคราะห์ได้หลายอย่างโดยการนำมาต่อยอดจากทฤษฎี เช่นในทางด้านการออกแบบฮาร์ดแวร์คอมพิวเตอร์ จะใช้ระยะทางแฮมมิงในการลดเวลาในการเปลี่ยนขั้นการทำงานของฮาร์ดแวร์ ซอฟต์แวร์ ที่ใช้เช่นระบบ เอทีเอ็ม ซึ่งข้อมูลที่รับส่งในการสื่อสารต้องไม่มีการผิดพลาดเลย จึงมีการตรวจสอบว่าข้อมูลที่ได้รับผิดพลาดหรือไม่ และหารข้อมูลนั้นผิดพลาดสามารถแก้ไขได้หรือไม่ เป็นต้น

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

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

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

รหัสเทียม

   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)

สรุป แก้

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

อ้างอิง แก้

Hamming, Richard W. (1950), "Error detecting and error correcting codes" (PDF), Bell System Technical Journal, 29 (2): 147–160, MR 0035935, คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 2006-05-25, สืบค้นเมื่อ 2011-09-08.
Pilcher, C. D.; Wong, J. K.; Pillai, S. K. (March 2008), "Inferring HIV transmission dynamics from phylogenetic sequence relationships", PLoS Med., 5 (3): e69, doi:10.1371/journal.pmed.0050069, PMC 2267810, PMID 18351799.
Wegner, Peter (1960), "A technique for counting ones in a binary computer", Communications of the ACM, 3 (5): 322, doi:10.1145/367236.367286.

ดูเพิ่ม แก้

การตรวจจับและแก้ไขความผิดพลาด

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

ตัวอย่างของระยะทางแฮมมิง
Hamming Code Tool เครื่องมือสำหรับใช้สร้างรหัสแฮมมิง
set_matcher เก็บถาวร 2011-08-07 ที่ เวย์แบ็กแมชชีน เครื่องมือสำหรับจับคู่เซ็ต 2 กลุ่มที่มีประชากรฐานแบบเดียวกัน โดยอาศัยระยะทางแฮมมิง