Эффективный способ найти элементы списка, которые содержат подстроки из другого списка

Question

list1 = ["happy new year", "game over", "a happy story", "hold on"]
list2 = ["happy", "new", "hold"]

Предположим, у меня есть два списка строк, я хочу использовать новый список для хранения совпавших пар этих двух списков, как показано ниже:

list3=[["happy new year","happy"],["happy new year","new"],["a happy story","happy"],["hold on","hold"]]

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

На самом деле это данные некоторых древних китайских скриптов.Первый список содержит имена людей в 10-13 веках, а второй список содержит названия всех стихотворений того периода.Древние китайцы часто записывают свои социальные отношения в названии своих произведений.Например, кто-то может написать стихотворение под названием «Для моего друга Ван Анши».В этом случае люди «Ван Анши» в первом списке должны совпадать с этим названием.Также есть такие случаи, как «Для моего друга Ван Анши и Су Ши», в названии которого содержится более одного человека.Так что в основном это огромная работа, в которой участвуют 30 000 человек и 160 000 стихов.

Ниже приведен мой код:

list3 = []

for i in list1:
        for j in list2:
            if str(i).count(str(j)) > 0:
                list3.append([i,j])

Я использую str (i), потому что python всегда принимает мои китайские строки как float.И этот код работает, но слишком медленно.Я должен найти другой способ сделать это.Спасибо!

Answer 1

Используйте регулярное выражение для поиска через модуль re . Механизм регулярных выражений может обрабатывать соответствующие элементы в поиске по тексту намного лучше, чем вложенный цикл for.

Я собираюсь использовать более подходящие имена переменных, чтобы было понятнее, куда должен идти список; titles - это названия стихотворений, которые вы просматриваете, и names то, что вы пытаетесь сопоставить. matched - это пары (title, name), которые вы хотите создать:

import re

titles = ["happy new year", "game over", "a happy story", "hold on"]
names = ["happy", "new", "hold"]

by_reverse_length = sorted(names, key=len, reverse=True)
pattern = "|".join(map(re.escape, by_reverse_length))
any_name = re.compile("({})".format(pattern))
matches = []

for title in titles:
    for match in any_name.finditer(title):
        matches.append((title, match.group()))

Приведенный выше выводит требуемый результат:

>>> matches
[('happy new year', 'happy'), ('happy new year', 'new'), ('a happy story', 'happy'), ('hold on', 'hold')]

Имена сортируются по длине, в обратном порядке, так что более длинные имена находятся перед более короткими с тем же префиксом; например Hollander найдено до Holland найдено до Holl.

Строка pattern создается из ваших имен для формирования шаблона ...|...|... альтернатив , любой из этих шаблонов может совпадать, но механизм регулярных выражений найдет перечисленные ранее в последовательности над этими. поставить позже, отсюда необходимость обратной сортировки по длине. (...) круглые скобки вокруг всего шаблона имен говорят механизму регулярных выражений захватывать этой части текста в группе. Вызов match.group() в цикле может затем извлечь сопоставленный текст.

Функция *1034*re.escape() предназначена для предотвращения «метасимволов» в именах, символов со специальным значением, таких как ^, $, (, ) и т. Д. от интерпретации как их специальные значения регулярных выражений.

Функция re.finditer() (и метод для скомпилированных шаблонов) затем находит непересекающиеся совпадения по порядку слева направо, поэтому она никогда не будет соответствовать более коротким подстрокам и дает нам возможность извлечь соответствует объекту для каждого. Это дает вам больше возможностей, если вы хотите знать о начальных позициях совпадений , а также о других метаданных, если они вам нужны. В противном случае re.findall() также может быть использовано здесь.

Если вы собираетесь использовать вышеприведенный текст с западными алфавитами , а не на китайском, то, возможно, вы также захотите добавить маркеры границы слова \b:

any_name = re.compile("\b({})\b".format(pattern))

в противном случае подстроки могут быть сопоставлены с частью большего слова. Поскольку в китайском языке нет символов границы слов (таких как пробелы и знаки препинания), вы не хотите использовать \b в таких текстах.

Answer 2

Если списки длиннее, возможно, стоило бы создать своего рода «индекс» предложений, в которых появляется данное слово. Создание индекса занимает примерно столько же времени, сколько и поиск первого слова из list2 во всех предложениях в list1 (он должен зацикливаться на всех словах во всех предложениях), и после его создания вы можете получить предложения, содержащие слово, гораздо быстрее в O (1).

list1 = ["happy new year", "game over", "a happy story", "hold on"]    
list2 = ["happy", "new", "hold"]

import collections    
index = collections.defaultdict(list)

for sentence in list1:
    for word in sentence.split():
        index[word].append(sentence)

res = [[sentence, word] for word in list2 for sentence in index[word]]

Результат:

[['happy new year', 'happy'],
 ['a happy story', 'happy'],
 ['happy new year', 'new'],
 ['hold on', 'hold']]

Используется str.split для разделения слов в пробелах, но если предложения более сложные, например, если они содержат знаки препинания, вы можете вместо этого использовать регулярное выражение с границами слов \b и, возможно, нормализовать предложения (например, преобразовать в нижний регистр или применить регистр, хотя не уверены, применимо ли это к китайскому языку).