Как оптимизировать редактирование кода расстояния?

Question

Как оптимизировать этот код расстояния редактирования, т. Е. Найти количество бит, измененных между двумя значениями! например word1 = '010000001000011111101000001001000110001' word2 = '010000001000011111101000001011111111111'

Когда я пытался запустить на Hadoop, это занимало целую вечность?

Как уменьшить цикл for и сравнения?

#!/usr/bin/python

import os, re, string, sys

from numpy import zeros

def calculateDistance(word1, word2):

    x = zeros( (len(word1)+1, len(word2)+1) )

    for i in range(0,len(word1)+1):

        x[i,0] = i

    for i in range(0,len(word2)+1):

        x[0,i] = i

    for j in range(1,len(word2)+1):

        for i in range(1,len(word1)+1):

            if word1[i-1] == word2[j-1]:

                x[i,j] = x[i-1,j-1]

            else:

                minimum = x[i-1, j] + 1

                if minimum > x[i, j-1] + 1:

                    minimum = x[i, j-1] + 1

                if minimum > x[i-1, j-1] + 1:

                    minimum = x[i-1, j-1] + 1

                x[i,j] = minimum

    return x[len(word1), len(word2)]

Answer 1

Я искал алгоритм подсчета битов в Интернете и нашел эту страницу , которая имеет несколько хороших алгоритмов.Моя любимая есть однострочная функция, которая утверждает, что работает для Python 2.6 / 3.0:

return sum( b == '1' for b in bin(word1 ^ word2)[2:] )

У меня нет Python, поэтому я не могу проверить, но если эта не работаетпопробуйте один из других.Ключ состоит в том, чтобы посчитать количество единиц в битовой XOR ваших двух слов, потому что для каждой разницы будет 1.

Вы вычисляете Расстояние Хэмминга , верно?

РЕДАКТИРОВАТЬ: я пытаюсь понять ваш алгоритм, и то, как вы манипулируете входами, похоже, что они на самом деле массивы, а не просто двоичные числа.Поэтому я ожидаю, что ваш код будет выглядеть примерно так:

return sum( a != b for a, b in zip(word1, word2) )

EDIT2: я понял, что делает ваш код, и это совсем не расстояние Хемминга!На самом деле это расстояние Левенштейна , которое подсчитывает, сколько добавлений, удалений или подстановок необходимо, чтобы превратить одну строку в другую (расстояние Хэмминга учитывает только подстановки, поэтому подходит только для строк цифр одинаковой длины),Глядя на страницу Википедии, ваш алгоритм является более или менее прямым портом псевдокода, который у них там есть.Как они указывают, временная и пространственная сложность сравнения строк длиной m и n составляет O (mn) , что довольно плохо.У них есть несколько предложений по оптимизации в зависимости от ваших потребностей, но я не знаю, для чего вы используете эту функцию, поэтому я не могу сказать, что будет лучше для вас.Если расстояние Хемминга достаточно для вас, приведенного выше кода должно хватить (сложность по времени O (n) ), но он дает разные результаты для некоторых наборов строк, даже если они имеют одинаковую длину, например'0101010101' и '1010101010', которые имеют расстояние Хемминга 10 (перевернуть все биты) и расстояние Левенштейна 2 (удалите первые 0 и добавьте их в конце)

Answer 2

Поскольку вы еще не указали, какое расстояние редактирования вы используете, я пойду на конечность и предположу, что это расстояние Левенштейна. В этом случае вы можете сбрить некоторые операции здесь и там:

def levenshtein(a,b):
    "Calculates the Levenshtein distance between a and b."
    n, m = len(a), len(b)
    if n > m:
        # Make sure n <= m, to use O(min(n,m)) space.
        # Not really important to the algorithm anyway.
        a,b = b,a
        n,m = m,n

    current = range(n+1)
    for i in range(1,m+1):
        previous, current = current, [i]+[0]*n
        for j in range(1,n+1):
            add, delete = previous[j]+1, current[j-1]+1
            change = previous[j-1]
            if a[j-1] != b[i-1]:
                change = change + 1
            current[j] = min(add, delete, change)

    return current[n]

edit: также вы не упоминаете свой набор данных. В соответствии с его характеристиками реализация может измениться, чтобы извлечь из этого выгоду.

Answer 3

Ваш алгоритм, кажется, выполняет много работы.Он сравнивает каждый бит со всеми битами в противоположном битовом векторе, что означает, что вы получаете алгоритмическую сложность O (m * n).В этом нет необходимости, если вы вычисляете расстояние Хэмминга, поэтому я предполагаю, что это не так.

Ваш цикл создает матрицу x[i,j], которая выглядит примерно так:

   0  1  0  0  0  0  0  0  1  0  0 ... (word1)
0  0  1  0  0  0  0  0  0  1
1  1  0  1  1  1  1  1  1  0
0  0  1  0  1  1  1  1  1  1
0  0  1  1  0  1  1  1  1  2
0  0  1  1  1  0  1  1  1  2
0  0  1  1  1  1  0  1  1  2
1
1
...
(example word2)

обнаруживая определенные типы правок, но не зная, какой алгоритм расстояния редактирования вы пытаетесь реализовать, я действительно не могу сказать вам, как его оптимизировать.