Как я могу эффективно отсортировать список строк на основе расстояния редактирования?

Я пытаюсь отсортировать список по расстоянию редактирования, используя расстояние Левенштейна.

def suggest(dic, word, distance, maxSugestions=5):
   list = []
   for i in range(1, 200):
       for word1 in sorted(dic):
           if distance(word1, word) == i:
               list.append(word1)
               if len(list) == maxSugestions:
                   return list

Это моя текущая функция, которая получает список строк (в этом списке около 43 тысяч строк), слово, которое я хочу сравнить, функция, которая возвращает расстояние редактирования между двумя строками и целое число maxSugestions, которое должно быть в списке.

Это текущая функция расстояния:

def levDistance(str1, str2):
   matrix = [[0 for x in range(len(str2) + 1)] for x in range(len(str1) + 1)]

   for i in range(len(str1) + 1):
       for j in range(len(str2) + 1):
           if i == 0:
               matrix[i][j] = j
           elif j == 0:
               matrix[i][j] = i
           elif str1[i-1] == str2[j-1]:
               matrix[i][j] = matrix[i-1][j-1]
           else:
               matrix[i][j] = 1 + min(matrix[i][j-1], matrix[i-1][j], matrix[i-1][j-1])    

   return matrix[len(str1)][len(str2)]

Текущая функция submit() работает, однако мне нужно ее оптимизировать, так как это занимает слишком много времени, и я не знаю, как мне это сделать. Любая помощь благодарна. Спасибо

Вы пытались использовать sorted с указанным key?

— 10.12.2020 12:05

если вы вычисляете одно и то же расстояние много раз, то лучше сначала создать словарь со всеми расстояниями {(word1,word2):distance, ... }

— 10.12.2020 12:09

в текущем коде вы запускаете sorted(dic) внутри for i in range(1, 200), поэтому вы повторяете одну и ту же сортировку 200 раз - вы можете отсортировать ее только один раз перед for-циклом

— 10.12.2020 12:12

когда у вас будет словарь {(word1,word2):distance, ... }, вы можете использовать функцию sorted(..., key=...) с key, которая использует `расстояние для сортировки

— 10.12.2020 12:26

python

10.12.2020 12:02

Почему в Python есть оператор "pass"?

Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.

Некоторые методы, о которых вы не знали, что они существуют в Python

Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...

Основы Python Часть I

Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?

LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа

Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:

Оптимизация кода с помощью тернарного оператора Python

И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это

Советы по эффективной веб-разработке с помощью Python

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

764

Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Я попробовал эту технику, надеюсь, она сработает для вас.

def edit_distance(word, string_to_take_distance_with = "someString"):
    '''
    Description:
        give you the edit distance between 2 words
        word                            : String 1 (dynamic) 
        string_to_take_distance_with    : String 2 (static)
        
    '''
    
    
    length_of_string  = len(word)+1
    length_of_string2 = len(string_to_take_distance_with)+1

    tbl = {}
    for i in range(length_of_string): tbl[i,0]=i
    for j in range(length_of_string2): tbl[0,j]=j
    for i in range(1, length_of_string):
        for j in range(1, length_of_string2):
            cost = 0 if word[i-1] == string_to_take_distance_with[j-1] else 1
            tbl[i,j] = min(tbl[i, j-1]+1, tbl[i-1, j]+1, tbl[i-1, j-1]+cost)

    return tbl[i,j]




sorted(["hello","helo","aen"], key=edit_distance)

10.12.2020 12:43

Ответ принят как подходящий

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

def suggest(dic, word, distance, maxSugestions=5):
   return [i[1] for i in sorted([(distance(word1, word), word1) for word1 in dic])[:maxSuggestion]]

Затем идет ваша реализация! Если вы все еще хотите, чтобы это было еще быстрее, лучше использовать библиотеку editdistance . (Или любая другая реализация на основе C, если это имеет значение) вместо реализации на основе Python. У меня это получилось в 20 раз быстрее, чем реализация на Python. Из исходного ответа:

Я использовал реализацию вычисления расстояния Левенштейна на основе c используя библиотеку editdistance. При исследовании я обнаружил, что многие такие задачи имеют реализацию на основе C, например алгоритмы умножения матриц и поиска и т. д. легко доступный. Кроме того, вы всегда можете написать модуль на C и использовать это в питоне. editdistance.eval('banana', 'bahama') взял только 1.71 µs ± 289 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) по сравнению с моей определенной функцией levenshteinDistance('banana', 'bahama'), которая потребовала 34.4 µs ± 4.2 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) Это ускорение в 20 раз.

P.S. Я не являюсь автором пакета и нашел пакет, используя номинальный поиск в Google «реализация расстояния Левенштейна на основе C».

10.12.2020 12:51