Научитесь реализовывать Edit Distance from Scratch

Недавно я прошел курс «Обработка естественного языка с использованием вероятностных моделей» от deeplearning.ai на Coursera. Этот курс охватывал широкий круг тем, таких как Коррекция орфографии, Добавление тегов речи, Моделирование языка и Преобразование Word в вектор . Все темы были освещены подробно и с подробными практическими упражнениями.

Но все мы знаем, что если мы не практикуем изученные концепции, мы обязательно забудем о них в кратчайшие сроки. Итак, я подумал о том, чтобы написать этот блог об одной из очень важных метрик, которые были рассмотрены в курсе - «Изменить расстояние или расстояние Левенштейна».

В этой статье будут рассмотрены следующие темы:

• Введение в редактирование расстояния
• Реализуйте это с помощью рекурсии
• Понять динамическое программирование и его реализация
• Работайте над проблемой, используя полученные навыки

Что такое Edit Distance и как его реализовать?

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

В этом разделе мы научимся реализовывать расстояние редактирования.

Метрика расстояния

Расстояние Левенштейна рассчитывается по следующей формуле:

Где хвост означает остальную часть последовательности, за исключением 1-го символа, на жаргоне Python это a[1:].

Пояснения к условиям:

• Если b - пустая последовательность (|b|=0), тогда стоимость равна длине a (|a|).
• Если a - пустая последовательность (|a|=0), тогда стоимость равна длине b (|b|).
• Если первые символы a и b совпадают (a[0] = b[0]), то стоимость - это стоимость хвоста подпоследовательности (a) (a[1:]) и хвоста (b) (b[1:]).
• Наконец, стоимость - это минимум операции вставки, удаления или замены, которые определены:
• lev(tail(a), b) указывает, что символ удален из
• lev(a, tail(b) указывает, что символ вставлен в
• lev(tail(a), tail(b)) обозначает замену

Примечание. Здесь, в приведенной выше формуле, стоимость вставки, удаления или замены осталась прежней, то есть 1. Но стоимость замены обычно рассматривается как 2, что мы и будем использовать при реализации.

Изменить расстояние с помощью рекурсии

Мы можем напрямую преобразовать приведенную выше формулу в рекурсивную функцию для вычисления расстояния редактирования между двумя последовательностями, но временная сложность такого решения составляет 𝑂 (3 (𝑚 + 𝑛)).

Итак, как только мы проясним, как работает дистанционное редактирование, мы напишем для него более оптимизированное решение, используя динамическое программирование, имеющее временную сложность 𝑂 (𝑚 ∗ 𝑛).

Ниже представлена ​​рекурсивная функция. Я также добавлю немного повествования, то есть функцию для распечатки операций (вставка, удаление или замена), которые она выполняет.

# Below are the costs of different operations.
ins_cost = 1
del_cost = 1
sub_cost = 2
# Below function will take the two sequence and will return the distance between them.
def edit_distance_recurse(seq1, seq2, operations=[]):
    """Returns the Edit Distance between the provided two sequences."""
    
    if len(seq2) == 0:
        operations = operations + ([f"Delete `{seq1}` from sequence1."] if len(seq1) else [])
        return len(seq1), operations
    
    if len(seq1) == 0:
        operations = operations + ([f"Insert `{seq2}` into sequence1."] if len(seq2) else [])
        return len(seq2), operations
    
    if seq1[0] == seq2[0]:
        operations = operations + [f"Make no change for character `{seq1[0]}`."]
        return edit_distance_recurse(seq1[1: ], seq2[1: ], operations)
    
    # calculate cost if insertion was made
    ins_operations = operations + [f"Insert `{seq2[0]}` in sequence1."]
    insertion, ins_operations = edit_distance_recurse(seq1, seq2[1: ], ins_operations)
    
    # calculate cost if deletion was done
    del_operations = operations + [f"Delete `{seq1[0]}` from sequence1."]
    deletion, del_operations = edit_distance_recurse(seq1[1: ], seq2, del_operations)
    
    # calculate cost if substitution was done
    sub_operations = operations + [f"Replace `{seq1[0]}` in sequence1 with `{seq2[0]}`."]
    substitution, sub_operations = edit_distance_recurse(seq1[1: ], seq2[1: ], sub_operations)
    
    # calculate minimum cost
    min_cost = min(insertion + ins_cost, deletion + del_cost, substitution + sub_cost)
    
    if min_cost == (substitution + sub_cost):
        return min_cost, sub_operations
    elif min_cost == deletion + del_cost:
        return min_cost, del_operations
    else:
        return min_cost, ins_operations

Давайте проверим эту функцию на нескольких примерах

seq1 = "numpy"
seq2 = "numexpr"
score, operations = edit_distance_recurse(seq1, seq2)
print(f"Edit Distance between `{seq1}` & `{seq2}` is: {score}")
print("\nOperations performed are:\n")
for operation in operations:
    print(operation)

Вывод:

Edit Distance between `numpy` & `numexpr` is: 4
Operations performed are:
Make no change for character `n`.
Make no change for character `u`.
Make no change for character `m`.
Insert `e` in sequence1.
Insert `x` in sequence1.
Make no change for character `p`.
Replace `y` in sequence1 with `r`.

Причина, по которой расстояние редактирования должно быть 4: символы n,u,m остаются неизменными (отсюда и стоимость 0), затем вставляются e & x, в результате чего общая стоимость на данный момент составляет 2. Затем не было внесено никаких изменений в p, поэтому не изменилась стоимость и, наконец, y is replaced with r, что привело к дополнительной стоимости в 2 раза.

Следовательно, общая стоимость составляет 4.

Изменить расстояние с помощью динамического программирования

Динамическое программирование может применяться к проблемам, имеющим перекрывающиеся подзадачи. Как и в нашем случае, где получить расстояние редактирования между numpy и numexpr, мы сначала вычисляем то же самое для подпоследовательностей nump и nume, затем для numpy и numex и так далее ...

Как только мы решаем конкретную подзадачу, мы сохраняем ее результат, который позже используется для решения общей проблемы.

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

Теперь давайте разберемся, как разбить проблему на подзадачи, сохранить результаты, а затем решить общую проблему.

На изображении ниже - по строкам у нас есть sequence1, который мы хотим преобразовать в sequence2 (который находится по столбцам) с минимальной стоимостью преобразования.

Символ # перед двумя последовательностями указывает на пустую строку или начало строки.

Теперь мы заполним эту матрицу стоимостью различных подпоследовательностей, чтобы получить общее решение. Но сначала давайте посмотрим на базовые случаи:

• Когда sequence1 пусто, тогда стоимость получения sequence2 - это просто стоимость добавления символов, которые присутствуют в sequence2. Первая строка в Maxtrix указывает, что sequence1 пусто.

• Если обе последовательности пусты, то стоимость 0.

• Если мы добавим символ n к sequence1, мы получим стоимость 1.

• Таким же образом мы заполним нашу первую строку, где значение в каждом столбце равно 1 + previous column value, т.е. добавляется стоимость добавления еще одного символа.

• Примечание. значение 7 в последнем столбце означает, что если sequence1 пусто, то стоимость преобразования sequence1 в sequence2 составляет 7. Кроме того, стоимость преобразования пустой последовательности в подпоследовательность 'num' составляет 3.
• Напротив, у нас есть случай, когда sequence2 пусто, а sequence1 нет. Затем значения в строках представляют стоимость удаления символов для получения пустой последовательности.

• Примечание. здесь стоимость 5 представляет собой общую стоимость удаления всех символов sequence1 и получения пустого sequence2.

Теперь матрица с заполненными базовыми значениями затрат будет иметь следующий вид:

Решение подзадач и заполнение матрицы.

• Значение в (’n’, ’n’) равно 0, поскольку оба символа являются одинаковыми и, следовательно, конверсия не взимается.

• В приведенной ниже матрице показано, что стоимость преобразования #n в #nu составляет 1, поскольку стоимость подстрок #n & #n составляет 0, мы добавляем только стоимость добавления u к sub-sequence1.

• Как и выше, стоимость преобразования #nu в #n составляет 1, поскольку стоимость подстрок #n & #n составляет 0, мы добавляем только стоимость удаления u из sub-sequence1.

• После нескольких итераций матрица будет выглядеть, как показано ниже. Примечание. Подпоследовательности #num & #num для пользователей стоят 0, поскольку они идентичны.

• До сих пор мы рассматривали только операции вставки и удаления, но теперь мы также рассмотрим пример подстановки. Чтобы найти подпоследовательности #nump & #nume, мы сначала вычислим стоимость подпоследовательностей #num & #num (которая, как мы отметили выше, составляет 0), следовательно, общая стоимость равна 0 + 2 = 20 + 2 = 2 - стоимость замены p на e.

• Полная матрица приведена ниже, а общая стоимость указана в последнем столбце последней строки - 4.

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

Приведенная ниже функция позволяет выполнять операции с минимальными затратами.

def min_cost_path(cost, operations):
    
    # operation at the last cell
    path = [operations[cost.shape[0]-1][cost.shape[1]-1]]
    
    # cost at the last cell
    min_cost = cost[cost.shape[0]-1][cost.shape[1]-1]
    
    row = cost.shape[0]-1
    col = cost.shape[1]-1
    
    while row >0 and col > 0:
            
        if cost[row-1][col-1] <= cost[row-1][col] and cost[row-1][col-1] <= cost[row][col-1]:
            path.append(operations[row-1][col-1])
            row -= 1
            col -= 1
        elif cost[row-1][col] <= cost[row-1][col-1] and cost[row-1][col] <= cost[row][col-1]:
            path.append(operations[row-1][col])
            row -= 1
        else:
            path.append(operations[row][col-1])
            col -= 1
                    
    return "".join(path[::-1][1:])

Нижеприведенные функции вычисляют расстояние редактирования с использованием динамического программирования

def edit_distance_dp(seq1, seq2):
    
    # create an empty 2D matrix to store cost
    cost = np.zeros((len(seq1)+1, len(seq2)+1))
    
    # fill the first row
    cost[0] = [i for i in range(len(seq2)+1)]
    
    # fill the first column
    cost[:, 0] = [i for i in range(len(seq1)+1)]
    
    # to store the operations made
    operations = np.asarray([['-' for j in range(len(seq2)+1)] \
                                 for i in range(len(seq1)+1)])
    
    # fill the first row by insertion 
    operations[0] = ['I' for i in range(len(seq2)+1)]
    
    # fill the first column by insertion operation (D)
    operations[:, 0] = ['D' for i in range(len(seq1)+1)]
    
    operations[0, 0] = '-'
    
    # now, iterate over earch row and column
    for row in range(1, len(seq1)+1):
        
        for col in range(1, len(seq2)+1):
            
            # if both the characters are same then the cost will be same as 
            # the cost of the previous sub-sequence
            if seq1[row-1] == seq2[col-1]:
                cost[row][col] = cost[row-1][col-1]
            else:
                
                insertion_cost = cost[row][col-1] + ins_cost
                deletion_cost = cost[row-1][col] + del_cost
                substitution_cost = cost[row-1][col-1] + sub_cost
                
                # calculate the minimum cost
                cost[row][col] = min(insertion_cost, deletion_cost, substitution_cost)
                
                # get the operation
                if cost[row][col] == substitution_cost:
                    operations[row][col] = 'S'
                    
                elif cost[row][col] == ins_cost:
                    operations[row][col] = 'I'
                else:
                    operations[row][col] = 'D'
                
    return cost[len(seq1), len(seq2)], min_cost_path(cost, operations)

Выполните указанную выше функцию для образцов последовательностей.

seq1 = "numpy"
seq2 = "numexpr"
score, operations = edit_distance_dp("numpy", "numexpr")
print(f"Edit Distance between `{seq1}` & `{seq2}` is: {score}")
print("\nOperations performed are:\n")
for operation in operations:
    if operation == '-':
        print('No Change.')
    elif operation == 'I':
        print('Insertion')
    elif operation == 'D':
        print('Deletion')
    else:
        print('Substitution')

Вывод:

Edit Distance between `numpy` & `numexpr` is: 4.0
Operations performed are:
No Change.
No Change.
No Change.
Insertion
Deletion
No Change.
Substitution

Используйте "Изменить расстояние", чтобы решить проблему.

Набор данных, который мы собираемся использовать, содержит файлы, содержащие список пакетов с установленными их версиями для двух версий языка Python: 3.6 и 3.9.

Записи пакета Pandas в двух файлах:

• pandas
• pandas==1.2.1

В этом упражнении для каждого пакета, упомянутого в одном файле, мы найдем наиболее подходящий из второго файла. Пригодность будет зависеть от расстояния Левенштейна или метрики «Изменить расстояние».

Загрузите данные

def preprocessor(package):
    """
    This takes a input package and applies preprocessing steps like converting to lowercase,
    strip the `\n` and `space` from the ends.
    """
    return package.lower().strip()

Загрузите требования Python 3.6

# Open the file and read the list of packages
with open('/kaggle/input/pip-requirement-files/Python_ver36.txt', 'r') as f:
    py36 = f.readlines()
    
# clean the data
py36 = list(map(preprocessor, py36))

print("Number of packages for Python 3.6 are: ", len(py36))
print(f"\nFew of the records are:\n{py36[:5]}")

Вывод:

Number of packages for Python 3.6 are:  276

Few of the records are:
['absl-py==0.11.0', 'alabaster==0.7.12', 'anaconda-client==1.7.2', 'anaconda-project==0.8.3', 'appdirs']

Загрузите требования Python 3.9

with open('/kaggle/input/pip-requirement-files/Python_ver39.txt', 'r') as f:
    py39 = f.readlines()
    
# clean the data
py39 = list(map(preprocessor, py39))
    
print("Number of packages for Python 3.9 are: ", len(py39))
print(f"\nFew of the records are:\n{py39[:5]}")

Вывод:

Number of packages for Python 3.9 are:  146

Few of the records are:
['alabaster==0.7.12', 'anyio==2.0.2', 'appdirs==1.4.4', 'argon2-cffi==20.1.0', 'astroid==2.4.2']

Получите попарное расстояние между файлами требований

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

Затем для каждого пакета, упомянутого в файле требований версии Python 3.6, мы найдем наиболее подходящий пакет из файла версии Python 3.9.

# to store the best matching package for py36 found in py39
p36_best_match = {}
# for each package in py36 get the score
for pack36 in py36:
    
    best_score = float('inf')
    best_package = None
    
    # match with each package in py39
    for pack39 in py39:
        
        # get the edit distance between pack36 and pack39
        score, _ = edit_distance_dp(pack36, pack39)
        
        # if the score is less than best score so far
        # store the new score and package name
        if score < best_score:
            best_score = score
            best_package = pack39
            
    # append the details of best package found for pack36
    p36_best_match[pack36] = (best_package, best_score)
# print the results
for pack36, (pack39, score) in p36_best_match.items():
    print(f"Best matching package for `{pack36}` with distance of {score} is `{pack39}`")

Некоторые из выходных записей:

Best matching package for `absl-py==0.11.0` with distance of 9.0 is `py==1.10.0`
Best matching package for `alabaster==0.7.12` with distance of 0.0 is `alabaster==0.7.12`
Best matching package for `anaconda-client==1.7.2` with distance of 15.0 is `nbclient==0.5.1`
Best matching package for `anaconda-project==0.8.3` with distance of 17.0 is `odo==0.5.0`
Best matching package for `appdirs` with distance of 7.0 is `appdirs==1.4.4`
Best matching package for `argh` with distance of 10.0 is `rsa==4.7`

Проверьте правильность вышеуказанного решения

Для этого мы просто обрежем часть версии имен пакетов ==x.x.x как из py36, так и из наиболее подходящего пакета из py39, а затем проверим, совпадают они или нет.

# this function will trim the versions and return of they are same or not
def is_same(pack1, pack2):
    return pack1.split('==')[0] == pack2.split('==')[0]
print(f"Are packages `pandas` and `pandas==1.1.1` same? {is_same('pandas', 'pandas==1.1.1')}")

Are packages `pandas` and `pandas==1.1.1` same? True

Получите точность

# get total number of packages in py36
total_packs_in_py36 = len(py36)
# get the count of records where match was found
total_matched_records = sum([is_same(pack36, pack39) for pack36, (pack39, _) in p36_best_match.items()])
# get the accuracy
accuracy = total_matched_records * 1.0 / total_packs_in_py36
print(f"The total number of correct matches are: {total_matched_records} out of {total_packs_in_py36} and the accuracy is: {accuracy:.2f}")

Вывод:

The total number of correct matches are: 138 out of 276 and the accuracy is: 0.50

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

Лучшим подходящим пакетом для xlrd с расстоянием 10,0 является rsa==4.7

# find the actual corresponding record of 'xlrd' in py39 list
for pack39 in py39:
    if pack39.startswith('xlrd'):
        print(pack39)
        break

Вывод:

В списке py39 нет соответствующей записи «xlrd», т. Е. Он никогда не устанавливался для версии Python 3.9.

Количество записей в py36 составляет 276, а в py39 - только 146, поэтому мы можем найти совпадающие имена только для 53% ( 146/276) записей списка py36.

Кроме того, использованные данные были загружены на Kaggle, и доступ к рабочему блокноту можно получить с помощью - https://www.kaggle.com/pikkupr/implement-edit-distance-from-sratch

Надеюсь, что объяснения были ясными, и вы узнали из этой записной книжки, и дайте мне знать в комментариях, если у вас возникнут какие-либо вопросы.