Odległość Hamminga pomiędzy dwoma ciągami o równej długości jest to liczba miejsc, w których odpowiadające im symbole są różne. Innymi słowy, mierzy minimalną liczbę podstawień wymaganych by zmienić jeden ciąg w drugi lub liczbę błędów, które zmieniają jeden ciąg w drugi.

Szukanie wzorcowego ciągu odbywa się za pomocą zdefiniowanych przez użytkownika odległości Hamminga. Podejmowane są następujące kroki:

Krok 1: Wzorcowy ciąg z zawartością odległości Hamminga jest zbierany od użytkownika do wyszukiwania w stosie. Na podstawie ciągów generowana jest tablica suffixowa (przyrostków)

Krok 2: Kiedy wzorcowy ciąg z odległością Hamminga równą 1, jest poszukiwany w stosie, trasa zostanie ustalona bez idealnie dopasowanego wzorca. Zamiast tego dopuszczalny jest błąd w jednym symbolu.

Krok 3: Jeśli liczba błędów jest większa od odległości Hamminga wartość wprowadzona przez użytkownika, a następnie zajdzie zgodność z wyszukiwania algorytmem Search left, trasa zostanie podjęta w lewo lub w prawo w zależności od kolejności ortograficznej łańcucha wzorcowego i ciągu bieżącego w tablicy suffixowej.

Pozwala to uzyskać przybliżone wyniki wyszukiwania zamiast dokładnych.
Implementacja dostępna w pliku HammingDistance.zip pod adresem
http://cs.elitepc.pl/HammingDistance
lub
tutaj


Autor: Krzysztof Wołk