فاصله همینگ (Hamming Distance) چیست؟ از مفهوم تا پیاده‌سازی و کاربردهای واقعی

Hamming Distance یکی از ساده‌ترین معیارهای اندازه‌گیری اختلاف میان دو دنباله است. اگر دو رشته یا دو آرایه هم‌طول داشته باشیم، فاصله همینگ برابر است با تعداد موقعیت‌هایی که مقدار دو دنباله در آن‌ها با یکدیگر متفاوت است.

این مفهوم در الگوریتم‌ها، نظریه کدگذاری، شبکه، تشخیص خطا، پردازش داده و حتی بعضی مسائل Machine Learning کاربرد دارد.

ایده اصلی

دو رشته زیر را در نظر بگیرید:

karolin
kathrin

کاراکترها را موقعیت‌به‌موقعیت مقایسه می‌کنیم:

k a r o l i n
k a t h r i n
    ↑ ↑ ↑

سه موقعیت متفاوت هستند، بنابراین:

Hamming Distance = 3

نکته مهم این است که در تعریف کلاسیک، دو دنباله باید طول یکسان داشته باشند.

تعریف رسمی

اگر دو رشته هم‌طول x و y با طول n داشته باشیم، فاصله همینگ را می‌توان به شکل زیر نوشت:

H(x, y) = Σ [x[i] ≠ y[i]]

برای هر موقعیت، اگر عناصر متفاوت باشند مقدار 1 و در غیر این صورت 0 در نظر گرفته می‌شود.

مثلاً:

x = 1011101
y = 1001001

مقایسه:

1 0 1 1 1 0 1
1 0 0 1 0 0 1
    ↑   ↑

پس:

H(x, y) = 2

الگوریتم چگونه کار می‌کند؟

روش محاسبه بسیار مستقیم است:

1. بررسی می‌کنیم دو ورودی طول یکسان داشته باشند.
2. یک شمارنده با مقدار صفر ایجاد می‌کنیم.
3. از ابتدای دنباله تا انتها حرکت می‌کنیم.
4. هر زمان دو مقدار متفاوت باشند، شمارنده را یک واحد افزایش می‌دهیم.
5. در پایان مقدار شمارنده همان Hamming Distance است.

شبه‌کد:

function hammingDistance(a, b):
    if length(a) != length(b):
        error

    distance = 0

    for i from 0 to length(a) - 1:
        if a[i] != b[i]:
            distance++

    return distance

پیاده‌سازی با TypeScript

function hammingDistance(a: string, b: string): number {
  if (a.length !== b.length) {
    throw new Error("Inputs must have the same length.");
  }

  let distance = 0;

  for (let i = 0; i < a.length; i++) {
    if (a[i] !== b[i]) {
      distance++;
    }
  }

  return distance;
}

console.log(hammingDistance("karolin", "kathrin")); // 3

این پیاده‌سازی تنها یک بار روی رشته حرکت می‌کند و به فضای اضافی قابل‌توجهی نیاز ندارد.

پیچیدگی زمانی و فضایی

اگر طول رشته‌ها n باشد:

Time Complexity: O(n)
Space Complexity: O(1)

برای محاسبه دقیق باید هر موقعیت حداقل یک بار بررسی شود؛ بنابراین O(n) بهترین مرتبه زمانی معمول برای این مسئله است.

Hamming Distance برای اعداد باینری

یکی از کاربردهای مهم این الگوریتم مقایسه بیت‌ها است.

فرض کنید دو عدد داریم:

x = 10  -> 1010
y = 14  -> 1110

فقط یک بیت متفاوت است:

1010
1110
 ↑

پس فاصله همینگ برابر 1 است.

برای اعداد، می‌توان از عملگر XOR استفاده کرد:

1010
XOR
1110
----
0100

هر بیت 1 در خروجی XOR نشان‌دهنده یک موقعیت متفاوت است.

در نتیجه:

Hamming Distance = تعداد بیت‌های 1 در x XOR y

نمونه TypeScript:

function hammingDistanceBits(x: number, y: number): number {
  let value = x ^ y;
  let distance = 0;

  while (value !== 0) {
    distance += value & 1;
    value >>>= 1;
  }

  return distance;
}

بهینه‌سازی شمارش بیت‌ها

برای شمارش بیت‌های 1 می‌توان از تکنیک Brian Kernighan استفاده کرد:

function hammingDistanceBits(x: number, y: number): number {
  let value = x ^ y;
  let distance = 0;

  while (value !== 0) {
    value &= value - 1;
    distance++;
  }

  return distance;
}

عبارت:

value & (value - 1)

در هر مرحله کم‌ارزش‌ترین بیت 1 را حذف می‌کند.

کاربردهای واقعی

1. تشخیص و تصحیح خطا

فاصله همینگ در Error Detection و Error-Correcting Codes بسیار مهم است. اگر داده‌ای هنگام انتقال تغییر کند، اختلاف بیت‌ها می‌تواند برای تشخیص خطا استفاده شود.

2. مقایسه کدهای باینری

در سیستم‌های دیجیتال می‌توان میزان تفاوت دو Binary Code را با Hamming Distance اندازه گرفت.

3. شبکه و ارتباطات

در بعضی پروتکل‌ها و روش‌های انتقال داده، این معیار برای بررسی تغییرات داده در مسیر انتقال استفاده می‌شود.

4. پردازش تصویر و ویژگی‌های باینری

اگر ویژگی‌های یک تصویر به صورت Binary Descriptor ذخیره شوند، Hamming Distance می‌تواند برای مقایسه سریع آن‌ها به کار رود.

5. Machine Learning

برای داده‌های دسته‌ای یا ویژگی‌های باینری، Hamming Distance می‌تواند معیار ساده‌ای برای Similarity یا Distance باشد.

مثلاً:

User A = [1, 0, 1, 1, 0]
User B = [1, 1, 1, 0, 0]

فاصله همینگ برابر 2 است.

Hamming Distance و Levenshtein Distance چه تفاوتی دارند؟

این دو مفهوم گاهی با هم اشتباه گرفته می‌شوند.

Hamming Distance فقط جایگزینی در موقعیت‌های متناظر را بررسی می‌کند و ورودی‌ها باید هم‌طول باشند.

اما Levenshtein Distance سه عملیات را در نظر می‌گیرد:

• Insert
• Delete
• Replace

برای مثال:

cat
cut

هر دو معیار فاصله 1 می‌دهند.

اما برای:

cat
cats

Hamming Distance در تعریف کلاسیک قابل استفاده نیست، زیرا طول‌ها متفاوت‌اند؛ ولی Levenshtein Distance برابر 1 است.

چه زمانی Hamming Distance انتخاب مناسبی است؟

از Hamming Distance زمانی استفاده کنید که:

• دو دنباله طول یکسان دارند.
• موقعیت عناصر اهمیت دارد.
• فقط می‌خواهید تعداد اختلاف‌ها را بدانید.
• با داده‌های باینری کار می‌کنید.
• سرعت و سادگی مهم است.

اگر Insert و Delete نیز باید محاسبه شوند، معیارهایی مانند Levenshtein مناسب‌تر هستند.

یک سؤال رایج مصاحبه

صورت مسئله:

دو عدد صحیح x و y داده شده‌اند. تعداد بیت‌هایی را که باید تغییر کنند تا x به y تبدیل شود محاسبه کنید.

راه‌حل:

1. x XOR y
2. تعداد بیت‌های 1 در نتیجه

مثلاً:

x = 1  -> 0001
y = 4  -> 0100

XOR     -> 0101

در نتیجه دو بیت باید تغییر کنند:

Hamming Distance = 2

اشتباهات رایج

یکی از رایج‌ترین اشتباهات این است که Hamming Distance را روی رشته‌هایی با طول متفاوت اجرا کنیم.

اشتباه دیگر این است که تصور کنیم فاصله همینگ محل جابه‌جایی یا حذف و اضافه شدن کاراکتر را تشخیص می‌دهد. این الگوریتم فقط موقعیت متناظر را مقایسه می‌کند.

همچنین برای اعداد باینری، ابتدا XOR و سپس شمارش بیت‌های 1 معمولاً ساده‌ترین راه‌حل است.

جمع‌بندی

Hamming Distance الگوریتم پیچیده‌ای نیست، اما ایده‌ای بسیار مهم در علوم کامپیوتر است.

اصل آن را می‌توان در یک جمله خلاصه کرد:

فاصله همینگ تعداد موقعیت‌هایی است که دو دنباله هم‌طول در آن‌ها با یکدیگر تفاوت دارند.

برای رشته‌ها معمولاً با یک حلقه ساده و برای اعداد باینری با ترکیب XOR + Bit Counting پیاده‌سازی می‌شود.

سادگی، زمان اجرای O(n) و کاربرد آن در داده‌های باینری باعث شده Hamming Distance در موضوعاتی مانند الگوریتم‌ها، شبکه، کدگذاری، پردازش داده و مسائل مصاحبه برنامه‌نویسی همچنان کاربردی باشد.