algorithm 1с - Расстояние Хэмминг против Левенштейна




вики нечеткий (2)

Этот вопрос действительно зависит от типов последовательностей, которые вы соответствуете, и чего вы хотите.

Если это не проблема, то «1234567890» и «0123456789» считаются совершенно разными, так как расстояние Хэмминга прекрасное.

Для проблемы, над которой я работаю, найти расстояния между двумя последовательностями, чтобы определить их сходство, порядок последовательности очень важен. Тем не менее, последовательности, которые у меня есть, не имеют одинаковой длины, поэтому я накладываю любые строки с недостатками с пустыми точками, так что обе последовательности имеют одинаковую длину, чтобы удовлетворить требованию расстояния Хэмминга. Есть ли какая-то серьезная проблема, когда я это делаю, поскольку все, о чем я забочусь, это количество транспозиций (не вставки или удаления, такие как Levenshtein)?

Я обнаружил, что расстояние Хэмминга намного, намного быстрее, чем Левенштейн как метрика расстояния для последовательностей длинной длины. Когда следует использовать расстояние Левенштейна (или производные от расстояния Левенштейн) вместо гораздо более дешевого расстояния Хэмминга? Расстояние Хемминга можно считать верхней границей возможных расстояний Левенштейна между двумя последовательностями, поэтому, если я сравниваю две последовательности для метрики сходства по порядку, а не абсолютное минимальное число ходов для соответствия последовательностям, почему я выбрал Левенштейна над Хэммином как метрику?


Я переписал код без некоторой сложности (и ошибок).

def test_o_o(a, b):

    L = len(a)
    H = L//2
    n, m = 0, H-1

    # find the first difference in the left-side
    while n < H:
        if a[n] != b[n]: break
        n += 1
    else: return

    # find the last difference in the left-side
    while m > -1:
        if a[m] != b[m]: break 
        m -= 1
    else: return

    # for slicing, we want end_index+1
    m += 1

    # compare each slice for equality
    # order: beginning, block 1, block 2, middle, end
    if (a[0:n] == b[0:n] and \
        a[n:m] == b[L-m:L-n] and \
        b[n:m] == a[L-m:L-n] and \
        a[m:L-m] == b[m:L-m] and \
        a[L-n:L] == b[L-n:L]):

        return n, m

Реализация является элегантной и эффективной.

break в else: return структуры else: return гарантируют, что функция вернется в максимально возможной точке. Они также подтверждают, что значения n и m были установлены в допустимые значения, но это не представляется необходимым при явной проверке срезов. Эти линии могут быть удалены без заметного влияния на время.

Явное сравнение срезов также будет короткозамкнуто, как только вы оцените значение False .

Первоначально я проверил, существовала ли перестановка путем преобразования b в a :

b = b[:]
b[n:m], b[L-m:L-n] = b[L-m:L-n], b[n:m]
if a == b:
   return n, m

Но это медленнее, чем прямое сравнение срезов. Сообщите мне, если алгоритм не говорит сам за себя, и я могу предложить дополнительное объяснение (возможно, даже доказательство) относительно того, почему он работает и минимален.





algorithm diff nlp levenshtein-distance hamming-distance