Проверьте, содержат ли две строки одинаковый набор слов в Python - PullRequest
Новая
       68

Проверьте, содержат ли две строки одинаковый набор слов в Python

5 голосов
/ 25 июня 2019

Я пытаюсь сравнить два предложения и посмотреть, содержат ли они одинаковый набор слов.
Например: сравнение «сегодня хороший день» и «сегодня хороший день» должно вернуть истинное значение
Я использую функцию Счетчик из модуля коллекций прямо сейчас 

from collections import Counter


vocab = {}
for line in file_ob:
    flag = 0
    for sentence in vocab:
        if Counter(sentence.split(" ")) == Counter(line.split(" ")):
            vocab[sentence]+=1
            flag = 1
            break
        if flag==0:
            vocab[line]=1

Кажется, что он отлично работает на несколько строк, но мой текстовый файл имеет более 1000, и он никогда не завершает выполнение. Есть ли другой способ, более эффективный, который помог бы мне вычислить результат для всего файла?

EDIT:

Мне просто нужна замена для метода Counter, чтобы что-то заменить. И никаких изменений в реализации.

Ответы [ 4 ]

3 голосов
/ 26 июня 2019

Вам действительно не нужно использовать две петли.

Правильный способ использования диктов

Допустим, у вас есть dict: 

my_dict = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5, 'f': 5, 'g': 6}

Вашкод в основном эквивалентен: 

for (key, value) in my_dict.items():
    if key == 'c':
        print(value)
        break
#=> 3

Но весь смысл dict (и set, Counter, ...) в том, чтобы иметь возможность напрямую получить желаемое значение: 

my_dict['c']
#=> 3

Если ваш dict имеет 1000 значений, первый пример будет в среднем в 500 раз медленнее, чем второй.Вот простое описание, которое я нашел на Reddit :

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

Рефакторированный код

Вы простонужно найти общую подпись между "Today is a good day!" и "Is today a good day?".Один из способов - извлечь слова, преобразовать их в строчные, отсортировать и объединить.Важно то, что вывод должен быть неизменным (например, tuple, string, frozenset).Таким образом, его можно использовать внутри наборов, счетчиков или диктов напрямую , без необходимости перебирать каждый ключ. 

from collections import Counter

sentences = ["Today is a good day", 'a b c', 'a a b c', 'c b a', "Is today a good day"]

vocab = Counter()
for sentence in sentences:
    sorted_words = ' '.join(sorted(sentence.lower().split(" ")))
    vocab[sorted_words] += 1

vocab
#=> # Counter({'a day good is today': 2, 'a b c': 2, 'a a b c': 1})

или даже короче: 

from collections import Counter

sentences = ["Today is a good day", 'a b c', 'a a b c', 'c b a', "Is today a good day"]

def sorted_words(sentence):
    return ' '.join(sorted(sentence.lower().split(" ")))

vocab = Counter(sorted_words(sentence) for sentence in sentences)
# Counter({'a day good is today': 2, 'a b c': 2, 'a a b c': 1})

Этот код должен быть намного быстрее того, что вы пробовали до сих пор.

Еще одна альтернатива

Если вы хотите сохранить оригинальные предложения в списке, вы можете использовать setdefault:

sentences = ["Today is a good day", 'a b c', 'a a b c', 'c b a', "Is today a good day"]

def sorted_words(sentence):
    return ' '.join(sorted(sentence.lower().split(" ")))

vocab = {}
for sentence in sentences:
    vocab.setdefault(sorted_words(sentence), []).append(sentence)

vocab

#=> {'a day good is today': ['Today is a good day', 'Is today a good day'],
# 'a b c': ['a b c', 'c b a'],
# 'a a b c': ['a a b c']}
3 голосов
/ 25 июня 2019

Попробуйте что-то вроде

set(sentence.split(" ")) == set(line.split(" "))

Сравнение набор объектов происходит быстрее, чем сравнение counter .Объекты set и counter в основном являются наборами, однако, когда вы используете объект counter для сравнения, он должен сравнивать и ключи, и значения, тогда как набор должен сравнивать только ключи.Спасибо Эрику и Бармару за ваш ввод.

Ваш полный код будет выглядеть как 

from collections import Counter
vocab = {a dictionary of around 1000 sentences as keys}
for line in file_ob:
    for sentence in vocab:
        if set(sentence.split(" ")) == set(line.split(" ")):
            vocab[sentence]+=1
2 голосов
/ 25 июня 2019

В вашем коде вы можете извлечь конструкцию Counter вне внутреннего цикла, вместо того, чтобы пересчитывать каждую для каждой пары - это должно улучшить алгоритм с коэффициентом, пропорциональным avg # токенов на строку. 

from collections import Counter
vocab = {a dictionary of around 1000 sentences as keys}

vocab_counter = {k: Counter(k.split(" ")) for k in vocab.keys() }

for line in file_obj:
    line_counter = Counter(line.split(" "))
    for sentence in vocab:
        if vocab_counter[sentence] == line_counter:
            vocab[sentence]+=1

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

2 голосов
/ 25 июня 2019

Чтобы учесть повторяющиеся / множественные слова, ваше сравнение на равенство может быть: 

def hash_sentence(s):                                                                                                                                                                                                                                         
    return hash(''.join(sorted(s.split())))                                                                                                                                                                                                                   

a = 'today is a good day'                                                                                                                                                                                                                                     
b = 'is today a good day'                                                                                                                                                                                                                                     
c = 'today is a good day is a good day'                                                                                                                                                                                                                       

hash_sentence(a) == hash_sentence(b)  # True
hash_sentence(a) == hash_sentence(c)  # False

Также обратите внимание, что в вашей реализации каждое предложение считается n раз (for sentence in vocab:).

...