Расстояние Левенштейна из транзитивно похожие слова


Цель кодекса заключается в следующем: два слова друзей, если они есть расстояние Левенштейна на 1. То есть, вы можете добавлять, удалять или заменой ровно одной буквы в слове х, чтобы создать слова Ю. слова социальная сеть состоит из всех его друзей, а также всех их друзей, и всех своих друзей друзей, и так далее. Рассчитывать на друзей в социальной сети определенные слова.

Мой код реализуется с помощью префиксного дерева, написанная Стивом ханов. Его код здесь: http://stevehanov.ca/blog/index.php?id=114.

То, что я сделал это:

social_links = set_up_dictionary_from_text('dictionary.txt')
tree = Trie()
for i in social_links:
    tree.insert(i)
def find(keyword):
    neighbors = [keyword]
    already_in_set = set()
    while len(neighbors) > 0:
        if neighbors[-1] not in already_in_set:
            temp = neighbors[-1]
            already_in_set.add(neighbors.pop())
            current_neighbors = search(tree, temp)
            neighbors.extend(current_neighbors)
        else:
            already_in_set.add(neighbors.pop())
    return(len(already_in_set))

Этот код работает, но работает более 8 минут для файлов, которые являются более 100 000 слов. Я что-то делаю не так? Или я не должен использовать Python для этого?



Комментарии
1 ответ

Во-первых, это не проблема питона. Скорее это вопрос реализации себя.

Я согласен с @Гарет рис . Вы всегда должны обеспечить минимальный рабочий пример кода. Это верно для StackOverflow и особенно актуально для CodeReview. В этом отношении все, что мы можем рассмотреть это немного подрезали вы предоставляете в предположении, что функции вам не дают делать определенные вещи.

Первое, что вы можете вырезать это else: блок. Он входит эквивалентность последний элемент neighbors в already_in_set и то, что он делает это добавляет последний элемент neighbors для already_in_set; другими словами: ничего. В качестве побочного эффекта вы не поп-последний элемент, и так как вы делаете это в обоих случаях лучше выделил выше if.

Похоже search(tree, temp) возвращает итерируемый вещь, содержащая все чин 1 соседи temp. Если вы не сделаете какие-либо кэширование, search невероятно медленно! Грубо говоря это O(len(dictionary.txt) * max([len(word) for word in dictionary.txt])^2) для наивных реализации и O(max([len(word) for word in dictionary.txt]) * depth(tree)) для одного в блоге вы упоминаете.

Чтобы сделать дела хуже, ты делаешь это для каждого друга, слова ровно (так как вы чернослив дубликаты). Так что ваш ход O(len(dictionary.txt)*max([friends(word) for word in dictionary.txt])*O(search)) который в очень грубой худшем случае может быть O(len(dictionary.txt)^4) (!); хотя этот случай относится только к теоретическим соображениям.

Вот список вещей, которые вы можете сделать:


  • Кэш Левенштейна двух слов; также вам не нужны фактические значения, а результат выражения distance <= 1 так что есть простор для оптимизации. Также это является симметричной: distance(a,b) = distance(b,a) так что вы можете кэшировать два значения для каждого вычисления

  • Кешировать результат search(tree, temp). Опять же, это симметричный: if b in search(tree,a) then a in search(tree,b) так вы можете кэш этот результат для каждого элемента search(tree,a) не вычисляя их [обратите внимание, что это рефлексивного тоже: a in search(tree,a)]

  • Кешировать результат find(keyword). find определяет группу связи на dictionary.txt; следовательно, если b in find(a) и c in find(a) потом еще: a in find(b), a in find(c), c in find(b), b in find(c). Вы можете просто кэш это число для каждого элемента в сети.

Делать все эти вещи будут снизить худший показатель случае
O(O(find)+O(search)+O(distance)) = O(len(dictionary.txt)^2) и должен сделать это значительно быстрее. Вы могли бы подумать о том, чтобы уменьшить количество вычислений, необходимых для search и distance потенциально снижая общую сложность, но я не думаю, что в этом дальше.

1
ответ дан 15 апреля 2018 в 10:04 Источник Поделиться