Поиск трех частей строки в Python с помощью регулярных выражений - PullRequest
Новая
       1

Поиск трех частей строки в Python с помощью регулярных выражений

1 голос
/ 16 марта 2012

У меня есть три строки, которые являются объединением трех компонентов:

  • одно слово из списка 1 (включает пустую строку)
  • одно слово из списка 2
  • одно слово из списка 3 (включает пустую строку)

Списки 1, 2 и 3 могут содержать до 5000 элементов. Элементы в одном списке отсутствуют в других (кроме пустой строки). Однако есть слова, которые могут быть частью других слов.

Я ищу эффективный способ найти три компонента. Прямо сейчас я делаю следующее: 

for word in list2:
    if word in long_word:
        try:
           [bef, aft] = long_word.split(word)
        except ValueError: # too many values to unpack
           continue
        if bef in list1 and aft in list3:
           print('Found: {}, {}, {}'.format(bef, word, aft))
           break
else:
    print('Not found')

Интересно, есть ли лучший способ? Я думал об использовании трубы в регулярном выражении. Но кажется, что количество альтернатив слишком велико, как я получаю: OverflowError: превышен предел размера кода регулярного выражения.

Спасибо

Обновление

Я попробовал модифицированную версию предложенного решения: 

def fj(long_word, list1, list2, list3):
    for x in filter(long_word.startswith, list1):
        for y in filter(long_word[len(x):].startswith, list2):
            z = long_word[len(x)+len(y):]
            if z in list3:
                yield x, y, z

def sid(long_word, list1, list2, list3):
    for w1 in list1:
        if not long_word.startswith(w1):
            continue
        cut1 = long_word[len(w1):]
        for w2 in list2:
           if not cut1.startswith(w2):
               continue
           cut2 = cut1[len(w2):]
           for w3 in list3:
               if cut2 == w3:
                   yield w1, w2, w3

def my(long_word, list1, list2, list3):
    for word in list2:
        if word in long_word:
            try:
               [bef, aft] = long_word.split(word)
            except ValueError: # too many values to unpack
               continue
            if bef in list1 and aft in list3:
               yield bef, word, aft

Это (нормализованные) результаты для времени, которое я получаю, используя списки с 8000 элементов, повторяющимися 10000 раз, каждый раз выбирая случайным образом одно слово из каждого списка для генерации long_word

  • мой: 1,0
  • sid: 4.5
  • FJ: 2,7

Я действительно удивлен, поскольку думал, что метод fj будет самым быстрым.

Ответы [ 3 ]

2 голосов
/ 16 марта 2012

Регулярные выражения, вероятно, здесь не очень подходят, я бы сказал так: 

for x in filter(long_word.startswith, list1):
    for y in filter(long_word[len(x):].startswith, list2):
        z = long_word[len(x)+len(y):]
        if z in list3:
            print('Found: {}, {}, {}'.format(x, y, z))
            break
    else:
        continue
    break
else:
    print('Not found')
0 голосов
/ 16 марта 2012

Мой ответ не полностью отвечает на ваш вопрос, но он напоминает нам о том, с чем мы имеем дело в этом квесте.

Списки 1, 2 и 3 могут содержать до 5000 элементов.

Это означает, что списки 1, 2 и 3 являются конечными регулярными языками .С этого момента я буду обозначать Список 1 как A, Список 2 как B, а Список 3 как C.

  • одно слово из списка 1 (включая пустую строку)
  • одно слово из списка 2
  • одно слово из списка 3 (содержит пустую строку)

Таким образом, пустая строка (лямбда) находится в A и C.

У вас есть строка w, которую можно записать в виде

w = abc

где a - строка в A, b -строка в B, а c - строка в C.

То, что вы пытаетесь сделать, это разбить w на подстроки a, b и c.

Поскольку a может быть пустым иc может быть пустым, у вас есть следующие возможности:

  1. w = abc
  2. w = ab
  3. w = bc
  4. w = b

Для начала давайте исключим тривиальный сценарий # 4. 

if w in B:
  a = ""
  b = w
  c = ""
  print('Found: {}, {}, {}'.format(a, b, c))

Дополнительные сведения появятся, когда я обдумаю это.

0 голосов
/ 16 марта 2012

Наивным алгоритмом было бы запустить 3 цикла: 

for w1 in list1:
    p1=re.match(w1,s)
    if p1==None:
        continue
    for w2 in list2:
       p2=re.match(w2,s[p1.pos+len(w1):])  
       if p2==None:
         continue
       for w3 in list3:
           p3=re.match(w3,s[p2.pos+len(w2):])

Я думаю, что вы все еще сталкиваетесь с проблемой того, что подстроки list1 являются частями list2.Метод FJ может быть лучше.

...