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

ในทางทฤษฎีข้อมูลแล้ว ระยะทางแฮมมิง  () ระหว่าง 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 Code Tool เครื่องมือสำหรับใช้สร้างรหัสแฮมมิง
 set_matcher  เครื่องมือสำหรับจับคู่เซ็ต 2 กลุ่มที่มีประชากรฐานแบบเดียวกัน โดยอาศัยระยะทางแฮมมิง 

หมวดหมู่:การวัดความคล้ายกันของสายอักขระ
หมวดหมู่:ทฤษฎีสารสนเทศ
หมวดหมู่:การเข้ารหัส
หมวดหมู่:ทรงลูกบาศก์