Алгоритм / Python для разбора файла журнала на вложенные пары начала и конца

Question

Я пытаюсь облегчить чтение файла журнала.

Мне удалось преобразовать каждую строку файла журнала так, чтобы у меня был Python-текст с фактами о каждой строке, то есть у меня есть файлв памяти как массив, который выглядит примерно так:

[
    {'keyword':'a', 'is_pair':True, 'type':'open', 'details':'iwiv', 'linenumber':5},
    {'keyword':'a', 'is_pair':True, 'type':'open', 'details':'83fi', 'linenumber':200},
    {'keyword':'a', 'is_pair':True, 'type':'open', 'details':'28c8', 'linenumber':360},
    {'keyword':'a', 'is_pair':True, 'type':'close', 'details':'28c8', 'linenumber':365},
    {'keyword':'a', 'is_pair':True, 'type':'open', 'details':'28c8', 'linenumber':370},
    {'keyword':'a', 'is_pair':True, 'type':'close', 'details':'28c8', 'linenumber':375},
    {'keyword':'a', 'is_pair':True, 'type':'open', 'details':'aowq', 'linenumber':400},
    {'keyword':'b', 'is_pair':True, 'type':'open', 'details':'pwiv', 'linenumber':520},
    {'keyword':'b', 'is_pair':True, 'type':'close', 'details':'pwiv', 'linenumber':528},
    {'keyword':'d', 'is_pair':False, 'details':'9393', 'linenumber':600},
    {'keyword':'b', 'is_pair':True, 'type':'open', 'details':'viao', 'linenumber':740},
    {'keyword':'b', 'is_pair':True, 'type':'close', 'details':'viao', 'linenumber':741},
    {'keyword':'b', 'is_pair':True, 'type':'open', 'details':'viao', 'linenumber':750},
    {'keyword':'b', 'is_pair':True, 'type':'close', 'details':'viao', 'linenumber':777},
    {'keyword':'a', 'is_pair':True, 'type':'close', 'details':'aowq', 'linenumber':822},
    {'keyword':'a', 'is_pair':True, 'type':'close', 'details':'83fi', 'linenumber':850},
    {'keyword':'a', 'is_pair':True, 'details':'iwiv', 'linenumber':990},
    {'keyword':'c', 'is_pair':False, 'details':'1212', 'linenumber':997},
]

Я пытаюсь сделать "пару""ближайших соседей", чье "ключевое слово" соответствует **,например, сопоставление вложенных скобок и вывод результатов в виде некоего стандартизированного синтаксиса текста для вложения, такого как XML или JSON.

Я уже знаю, какие ключевые слова «созданы отдельно» против «должны» иметьсовпадение, «помеченное в моих входных данных как« is_pair ».

Я хотел бы дать какой-то« диапазон линий »для пары, которую я объединяю ... для тех, которые являются однострочными, яне волнует, если это пара «начало» и «конец» с одинаковым номером, нулевым концом, совершенно другой меткой (как в моих примерах) и т. д.

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

Пример 1

<a start="5" end="990">
    iwiv
    <a start="200" end="850">
        83fi
        <a start="360" end="365">
            28c8
        </a>
        <a start="370" end="375">
            28c8
        </a>
        <a start="400" end="822">
            aowq
            <b start="520" end="528">
                pwiv
            </b>
            <d linenumber="600">
                9393
            </d>
            <b start="740" end="741">
                viao
            </b>
            <b start="750" end="777">
                viao
            </b>
        </a>
    </a>
</a>
<c linenumber="997">
    1212
</c>

Пример 2

<a start="5" end="990" details="iwiv">
    <a start="200" end="850" details="83fi">
        <a start="360" end="365" details="28c8"/>
        <a start="370" end="375" details="28c8"/>
        <a start="400" end="822" details="aowq">
            <b start="520" end="528" details="pwiv"/>
            <d linenumber="600" details="9393"/>
            <b start="740" end="741" details="viao"/>
            <b start="750" end="777" details="viao"/>
        </a>
    </a>
</a>
<c linenumber="997" details="1212"/>

Пример 3

[
    {
        'keyword':'a',
        'start':5,
        'end':990,
        'details':'iwiv', 
        'inner':[
            {
                'keyword':'a',
                'start':200,
                'end':850,
                'details':'83fi',
                'inner':[
                    {'keyword':'a', 'details':'28c8'},
                    {'keyword':'a', 'details':'28c8'},
                    {
                        'keyword':'a',
                        'start':400,
                        'end':822,
                        'details':'aowq',
                        'inner':[
                            {'keyword':'b', 'start':520, 'end':528, 'details':'pwiv'},
                            {'keyword':'d', 'linenumber':600, 'details':'9393'},
                            {'keyword':'b', 'start':740, 'end':741,  'details':'viao'},
                            {'keyword':'b', 'start':750, 'end':777,  'details':'viao'}
                        ]
                    }
                    ]
            }
        ]
    },
    {'keyword':'c', 'linenumber':997, 'details':'1212'}
]

Не обязательноМне нужна помощь с деталями написания файлов JSON или XML.

В алгоритме, в частности Pythonically, я не уверен, что это аспект «сопоставления комков» этой работы.

Как мне приблизиться к преобразованию чего-либо из «линейного списка» в «гнездо», где каждый элемент с open соответствует следующему ближайшему close того же ключевого слова, которое еще не «заявлено»"лучшим кандидатом?

Answer 1

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

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

data = \
[
    {'keyword':'a', 'is_pair':True, 'type':'open', 'details':'iwiv', 'linenumber':5},
    {'keyword':'a', 'is_pair':True, 'type':'open', 'details':'83fi', 'linenumber':200},
    {'keyword':'a', 'is_pair':True, 'type':'open', 'details':'28c8', 'linenumber':360},
    {'keyword':'a', 'is_pair':True, 'type':'close', 'details':'28c8', 'linenumber':365},
    {'keyword':'a', 'is_pair':True, 'type':'open', 'details':'28c8', 'linenumber':370},
    {'keyword':'a', 'is_pair':True, 'type':'close', 'details':'28c8', 'linenumber':375},
    {'keyword':'a', 'is_pair':True, 'type':'open', 'details':'aowq', 'linenumber':400},
    {'keyword':'b', 'is_pair':True, 'type':'open', 'details':'pwiv', 'linenumber':520},
    {'keyword':'b', 'is_pair':True, 'type':'close', 'details':'pwiv', 'linenumber':528},
    {'keyword':'d', 'is_pair':False, 'details':'9393', 'linenumber':600},
    {'keyword':'b', 'is_pair':True, 'type':'open', 'details':'viao', 'linenumber':740},
    {'keyword':'b', 'is_pair':True, 'type':'close', 'details':'viao', 'linenumber':741},
    {'keyword':'b', 'is_pair':True, 'type':'open', 'details':'viao', 'linenumber':750},
    {'keyword':'b', 'is_pair':True, 'type':'close', 'details':'viao', 'linenumber':777},
    {'keyword':'a', 'is_pair':True, 'type':'close', 'details':'aowq', 'linenumber':822},
    {'keyword':'a', 'is_pair':True, 'type':'close', 'details':'83fi', 'linenumber':850},
    {'keyword':'a', 'is_pair':True, 'type':'close', 'details':'iwiv', 'linenumber':990}, # added 'type':'close'
    {'keyword':'c', 'is_pair':False, 'details':'1212', 'linenumber':997},
]

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

# The level of nesting, since we increase if we find an open
# the first open will get a depth of 0
depth = -1

# We store the complete answers and the stacked answers.
result, stack = [], []


for row in data:
    # Check if the type is open, or if the data is unpaired
    if row.get('type', None) == 'open' or not row['is_pair']:

        # We store it on the stack and increase nesting level
        stack.append(row)
        depth += 1

    # If there is no match, we close it directly.
    # Or if the type is closing
    if not row['is_pair'] or row.get('type', None) == 'close':

        # We get the last item on the stack
        matching_open = stack.pop(-1)

        # We will sort on the linenumbers to make sure that everything will be in order
        # we also store the dept for our layout (we are following example 2)
        result.append((matching_open['linenumber'], depth,
                       f'{" " * 4 * depth}<{row["keyword"]} start="{matching_open["linenumber"]}" '
                       f'end="{row["linenumber"]}" details="{row["details"]}">'))

        # Decrease nesting level
        depth -= 1

По сути, мы будем циклически проверять ваши данные и проверять наличие открытого типа. Если это так, мы добавляем его в стек. если мы нашли подходящее закрытие, мы добавим его к найденным результатам. Чтобы распечатать его в правильном порядке и добавить закрывающую скобку, нам также необходимо знать глубину вложения. Для форматирования я добавил дополнительную вкладку (4 пробела) для каждого добавленного уровня.

Если в стеке еще что-то осталось, мы можем проверить это с помощью;

if stack:
    raise ValueError("There is still a value in the stack, matching is not possible!")

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

# For the closing signs we need to keep track of our depth and opening keyword
temp = []
old_depth = None

# We only need the depth and message, so we discard the linenumber
for _, depth, message in sorted(result, key= lambda x: x[0]):

    # If the old depth was larger, we dropped a depth and we
    # need to put in a closing sign </a>
    if old_depth is not None and old_depth > depth:
        for num in range(old_depth - depth):
            close_open = temp.pop(-1)
            print(f'{" "*4*(old_depth-num -1)}</{close_open}>')

    # If we jump a depth we need to store the closing sign
    if old_depth is not None and old_depth < depth:
        temp.append(message[4*depth + 1])

    # Update the depth and print the message, since we append everything
    old_depth = depth
    print(message)

Это приведет к следующему выводу

<a start="5" end="990" details="iwiv">
    <a start="200" end="850" details="83fi">
        <a start="360" end="365" details="28c8">
        <a start="370" end="375" details="28c8">
        <a start="400" end="822" details="aowq">
            <b start="520" end="528" details="pwiv">
            <d start="600" end="600" details="9393">
            <b start="740" end="741" details="viao">
            <b start="750" end="777" details="viao">
        </a> 
    </a>
</a>
<c start="997" end="997" details="1212">

Answer 2

Я бы предложил решить это с помощью стека.Если данные вложены правильно, они будут легко решены.

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