Можете ли вы создать список Python из строки, одновременно сохраняя символы в определенных ключевых словах?

Ответ 1

С re.findall. Вместо этого выберите ключевые слова.

>>> import re
>>> s = "xyzcarbusabccar"
>>> re.findall('car|bus|[a-z]', s)
['x', 'y', 'z', 'car', 'bus', 'a', 'b', 'c', 'car']

Если у вас есть перекрывающиеся ключевые слова, обратите внимание, что это решение найдет первое, с которым вы сталкиваетесь:

>>> s = 'abcaratab'
>>> re.findall('car|rat|[a-z]', s)
['a', 'b', 'car', 'a', 't', 'a', 'b']

Вы можете сделать решение более общим, заменив часть [a-z] на то, что вам нравится, \w например, или просто ., чтобы соответствовать любому символу.

Краткое объяснение, почему это работает и почему регулярное выражение '[a-z]|car|bus' не работает: Механизм регулярных выражений пытается чередовать параметры слева направо и "нетерпеливо" возвращает совпадение. Это означает, что он считает, что все чередование соответствует, как только один из вариантов был полностью согласован. На этом этапе он не будет пытаться выполнить какие-либо из оставшихся опций, но прекратит обработку и немедленно сообщит о совпадении. С помощью '[a-z]|car|bus' двигатель сообщает о совпадении, когда видит какой-либо символ в классе символов [a-z] и никогда не будет проверять, можно ли также сопоставить "автомобиль" или "шину".

Ответ 2

s = "xyzcarbusabccar"
import re

print re.findall("bus|car|\w", s)
['x', 'y', 'z', 'car', 'bus', 'a', 'b', 'c', 'car']

Или, может быть, \S для любых символов без пробелов:

s = "xyzcarbusabccar!"
import re

print re.findall("bus|car|\S", s)
['x', 'y', 'z', 'car', 'bus', 'a', 'b', 'c', 'car', '!']

Просто убедитесь, что вы правильно настроили порядок, добавив более длинные слова, если вы хотите получить самые длинные совпадения.

In [7]: s = "xyzcarsbusabccar!"

In [8]: re.findall("bus|car|cars|\S", s)
Out[8]: ['x', 'y', 'z', 'car', 's', 'bus', 'a', 'b', 'c', 'car', '!']

In [9]: re.findall("bus|cars|car|\S", s)
Out[9]: ['x', 'y', 'z', 'cars', 'bus', 'a', 'b', 'c', 'car', '!']

Ответ 3

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

Я предлагаю хранить ключевые слова в дереве (который использует избыточность) и более эффективен в пространстве.

Если ключевые слова ["art,"at","atm","bus","can","car"], словарь выглядит следующим образом:

                 .
                 ^
            /    ¦      \

          /      ¦        \
        a        b           c
        ^        ^           ^
      /   \       \           \
    r       t      u           a
    ^       ^      ^           ^
   /       /  \     \        /   \
  t       m   /0     s      n     r
  ^       ^          ^      ^     ^
 /      /             \      \     \
/0     /0             /0      /0   /0

Я сделал это двоичным, так как было легче рисовать. node "/0" имеет значение конца слова (виртуальный символ), а "." - корень.

Я реализовал этот простой класс Tree для построения дерева и необходимых функций

class Tree(object):

    def __init__(self, name='root', children=None):
        self.name = name
        self.children = {}
        if children is not None:
            for child in children:
                self.add_child(child.name,child)

    def __repr__(self):
        return self.name

    def add_child(self, node):
        assert isinstance(node, Tree)
        self.children[node.name] = node


    def has_child(self,name):
        return name in self.children

    def get_child(self,name):
        return self.children[name]

    def print_tree(self,level=0):
        sys.stdout.write('-' * level)
        print self.name
        for childTag in self.children:
            self.children[childTag].print_tree(level+1)

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

keywords = ["car","at","atm","bus"]
keywordsTree = Tree('')

for keyword in keywords:
    keywordsTreeNode = keywordsTree
    for character in keyword:
        if not keywordsTreeNode.has_child(character):
            keywordsTreeNode.add_child(Tree(character))
        keywordsTreeNode = keywordsTreeNode.get_child(character)

    keywordsTreeNode.add_child(Tree('/0'))

Наконец, мы ищем вход для ключевых слов. Нижеприведенное решение предлагает для данной позиции во входных данных все ключевые слова, совпадающие с этой позиции.

inputWords = "xyzcarbusabccar8hj/0atm"
output = []
lengthInput = len(inputWords)
for position in range(0,lengthInput):
    ##add by default the character
    # allMathcedKeyWords = [inputWords[position]]

    allMathcedKeyWords = []
    keywordsTreeNode = keywordsTree
    searchPosition = position
    curMathcedWord = ''

    while searchPosition < lengthInput and keywordsTreeNode.has_child(inputWords[searchPosition]) :

        keywordsTreeNode = keywordsTreeNode.get_child(inputWords[searchPosition])
        curMathcedWord = curMathcedWord + inputWords[searchPosition]

        if (keywordsTreeNode.has_child("/0")):
            allMathcedKeyWords.append(curMathcedWord)

        searchPosition += 1

    if len(allMathcedKeyWords)==0:
        allMathcedKeyWords = inputWords[position]

    output.append(allMathcedKeyWords)

print output

Этот код выводит этот

['x', 'y', 'z', 
 ['car'], 
 'a', 'r', 
 ['bus'], 
  'u', 's', 'a', 'b', 'c',   
 ['car'],
  'a', 'r', '8', 'h', 'j', '/', '0', 
 ['at', 'atm'], 
  't', 'm']

Важным для приведенного выше кода является тот факт, что виртуальный символ в конце слов - это две буквы ("/0") и никогда не будет сопоставлен (даже если комбинация появляется во входной последовательности, как описано выше). Кроме того, он обрабатывает любой строковый символ (для ввода и ключевых слов - также не нужно вводить escape-символы, как в re.findall())

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

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

Пример, имеющий ключевые слова "car" и "art", а также художественную и входную последовательность "acart", полученные графики выглядят следующим образом:

             ______________
            ¦              ¦
- a -> c -> a -> r -> t ->
       ¦______________¦

Анализ сложности

Space : longest_word_length * number_of_letters_in_keywords
        input_length + input_length * input_length (worst case-fully connected graph)
Time  : input_length * longest_word_length
        input_length + input_length * input_length (worst case-fully connected graph)