Более эффективное сравнение строк в списке

Question

Я пишу программу для выявления судебных дел, цитируемых в большом количестве текстов из разных источников, и подсчета, сколько раз каждое цитируется в текстах.Проблема связана с тем фактом, что дела существуют в двух штатах в большинстве документов: они полностью или частично упоминаются в данном тексте (т. Е. «Тимоти Айвори Карпентер против Соединенных Штатов Америки»), а затем упоминаются в более кратком изложении.Форма в остальной части документа (например, «Карпентер против США»).В настоящее время я добавляю заголовки в огромный список, а затем запускаю этот список с помощью пакета обнаружения сходства строк FuzzyWuzzy.

Сейчас я каждый раз сравниваю каждую переменную с любой другой переменной, что НЕПРАВИЛЬНО неэффективно.Мой вопрос: есть ли способ запустить только те сравнения, которые не были выполнены?Я знаю, что могу сократить список пополам и сделать его немного более эффективным, но я все равно сравнил бы половину списка с самим собой.Моя другая мысль состояла в том, чтобы создать список, который был сравнен, и дать перекрестную ссылку на каждую пару и ее зеркальную версию (то есть как «1: 5», так и «5: 1»), с точки зрения времени обработки, которое в итоге составляет 34%.медленнее, чем просто грубое принуждение.

if variable_list = ['1','2','3','4','5']

Сейчас я сравниваю каждое из следующих действий:

1:1 1:2 1:3 1:4 1:5
2:1 2:2 2:3 2:4 2:5
3:1 3:2 3:3 3:4 3:5
4:1 4:2 4:3 4:4 4:5
5:1 5:2 5:3 5:4 5:5

, что ужасно, я знаю

Есть ли способ заставить Python запускать это вместо этого?

Одна часть проблемы заключается в том, что вы не можете просто проверить, было ли выполнено сравнение, потому что перекрывающиеся проверки являются зеркальными, а не идентичными (т.е. избыточность3: 1 означает, что 1: 3 уже сравнивалось, а не 3: 1)

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

1:1 1:2 1:3 1:4 1:5
2:2 2:3 2:4 2:5
3:3 3:4 3:5
4:4 4:5
5:5

Код:

for var_1 in variable_list:

    for var_2 in variable_list:

    ### The chunk below sets the parameters to filter the strings

        if fuzz.token_set_ratio(var_2_reg_filt, var_1_reg_filt) > 91:

            if fuzz.ratio(var_2_reg_filt, var_1_reg_filt) > 87:

                if fuzz.partial_ratio(var_2_reg_filt, var_1_reg_filt) > 87:

                    if fuzz.token_sort_ratio(var_2_reg_filt, var_1_reg_filt) > 83:

                        ### This code then removes the longer of the two strings
                        ### -- and replaces it with the shorter version

                        if (len(var_1_reg_filt)) > (len(var_2_reg_filt)):

                            <<< Code to Replace var_1 with var_2 >>>

                        if (len(var_1_reg_filt)) < (len(var_2_reg_filt)):

                            <<< Code to Replace var_1 with var_2 >>>

Это не проблема с кодом ошибки, а концептуальная.Я включил код, чтобы показать, что я делал: Выполнение каждой итерации var_1: var_2 через три разных фильтра для отбраковки закрытых, но неправильных совпадений.

Answer 1

Я предполагаю, что вам нужны комбинации ваших переменных, смотрите итератор combinations в пакетах itertools

import itertools
vars = ['1','2','3','4','5']
list(itertools.combinations(vars,2))
>>>
[('1', '2'),
 ('1', '3'),
 ('1', '4'),
 ('1', '5'),
 ('2', '3'),
 ('2', '4'),
 ('2', '5'),
 ('3', '4'),
 ('3', '5'),
 ('4', '5')]

, если вам нужно сравнить их с собой, вы можете использовать combinations_with_replacement

так что в конце ваш цикл должен выглядеть как

for var_1, var_2 in itertools.combinations(variable_list,2):
    ....