42      Глава 2. Структуры данных Python

Аналогично с помощью команды del и среза можно удалить элементы:

del my_list[5:]

Эта команда удалит элементы с индексами 5 и выше, тем самым возвращая список к прежнему виду:

['Pay bills', 'Tidy up', 'Walk the dog', 'Go to the pharmacy', 'Cook dinner']

Использование списка в качестве очереди

Очередь — это абстрактный тип данных, который может быть реализован с помощью структуры данных списка. Один конец очереди всегда используется для добавления элементов (enqueue), а другой — для их удаления (dequeue) согласно методологии первым вошел — первым вышел (FIFO, first-in, first-out). На практике методология FIFO часто используется при хранении товаров на складе: продукция, поступающая первой, первой склад и покидает. Подобная организация помогает предотвратить истечение сроков годности, поскольку в первую очередь продаются товары, произведенные раньше.

Список Python легко превратить в очередь, используя объект deque (сокращение от double-ended queue, двусторонняя очередь). Рассмотрим, как это работает, на примере нашего списка дел. Чтобы список функционировал как очередь, завершенные задачи должны вычеркиваться из начала, а новые — появляться в конце, как показано на рис. 2.1.

Т

Д а

Pay

Tidy

Walk the

Go to the

Cook

Wash the

bills

up

dog

pharmacy

dinner

car

О а

С а

В

С

П-

П

а

а

а

а

В

Pay

Tidy

Walk the

Go to the

Cook

e

Take a

bills

dog

pharmacy

dinner

Wash the

up

carr

drive

П а

Рис. 2.1. Пример использования списка как очереди

Списки      43

Вот как реализовать процесс, показанный на рисунке:

from collections import deque queue = deque(my_list) queue.append('Wash the car') print(queue.popleft(), ' - Done!') my_list_upd = list(queue)

В этом скрипте мы сначала превращаем исходный объект my_listв объект deque, который является частью модуля Python collections. Конструктор объекта deque()добавляет набор методов к передаваемому в него объекту списка, и тогда этот список можно легко использовать в качестве очереди. В данном примере мы добавляем новый элемент в правую часть очереди с помощью метода append(), а затем удаляем элемент из левой части с помощью метода popleft(). Этот метод не только удаляет крайний левый элемент, но и возвращает его, вставляя в выводимое на экран сообщение. Вот каким оно должно быть:

Pay bills - Done!

После обратного преобразования объекта deque в список (последняя строка скрипта) новый перечень дел будет выглядеть так:

['Tidy up', 'Walk the dog', 'Go to the pharmacy', 'Cook dinner', 'Wash the car']

Как видите, первый элемент был вытеснен из списка, а новый добавлен.

Использование списка в качестве стека

Как и очередь, стек является абстрактной структурой данных, которую можно организовать поверх списка. Стек реализует методологию последним вошел, — первым вышел (LIFO, last-in, first-out), когда последний добавленный элемент извлекается первым. Чтобы наш список дел функционировал как стек, мы должны выполнять задачи в обратном порядке, начиная с самой правой. Вот как эта концепция реализуется в Python:

my_list = ['Pay bills', 'Tidy up', 'Walk the dog', 'Go to the pharmacy', 'Cook dinner']

stack = []

for task in my_list: stack.append(task)

while stack:

44      Глава 2. Структуры данных Python

print(stack.pop(), ' - Done!')) print('\nThe stack is empty')

В цикле for мы переносим задачи, начиная с первой, из списка дел в стек, объявленный как другой список. Это пример использования append() в цикле для динамического заполнения пустого списка. Затем, в цикле while, мы удаляем задачи из стека, начиная с последней. Мы делаем это с помощью метода pop(), который удаляет последний элемент из списка и возвращает его. Вывод стека будет таким:

Cook dinner - Done!

Go to the pharmacy - Done!

Walk the dog - Done!

Tidy up - Done!

Pay bills - Done!

The stack is empty

Использование списков и стеков для обработки естественного языка

Списки и стеки имеют широкое применение, в том числе в области обработки естественного языка (NLP, Natural Language Processing). Например, они используются для извлечения из текста именных групп (noun chunk). Такая группа состоит из существительного и зависимых слов (то есть всех слов слева1 от существительного, которые синтаксически от него зависят, например прилагательных или артиклей в английском языке). Таким образом, чтобы извлечь из текста все именные группы, нужно найти в нем все существительные с зависимыми словами, располагающимися слева от существительного. Это можно сделать с помощью алгоритма на основе стека, как показано на рис. 2.2.

На рисунке в качестве примера представлена одна именная группа — A ubiquitous data structure2. Стрелки на синтаксическом дереве справа показывают, каким образом слова A, ubiquitous и data синтаксически связаны с существительным structure, известным как вершина (head) дочерних элементов. Алгоритм пословно анализирует текст слева направо и помещает слово в стек, если оно является существительным или расположенным слева от него зависимым словом. Если алгоритм встречает слово, которое не подходит под это описание, или если в тексте не осталось слов, значит, именная группа найдена целиком, и она извлекается из стека.

1Порядок расположения зависимых слов по отношению к главному зависит от языка. — Примеч. ред.

2 «A ubiquitous data structure» — «распространенная структура данных». — Примеч. пер.

				Списки      45
П а а
	Stack		A ubiquitous data structure
				С а а
		A ubiquitous	data structure

а а

A ubiquitous data structure A ubiquitous data structure

И а			A		ubiquitous			data			structure
	A ubiquitous data	structure
			DET		ADJ			NOUN			NOUN
			О -		П а а-		С -			С -
	A ubiquitous	data structure

A ubiquitous data structure

A ubiquitous data structure

Рис. 2.2. Пример использования списка в качестве стека

Чтобы реализовать такой алгоритм, потребуется установить spaCy, основную библиотеку Python с открытым исходным кодом для обработки естественного языка, а также одну из ее моделей для английского языка. Используйте следующие команды:

$ pip install -U spacy

$ python -m spacy download en_core_web_sm

В следующем скрипте spaCy используется для реализации ведущей библиотеки Python для обработки естественного языка:

import spacy

txt = 'List is a ubiquitous data structure in the Python programming language.'

nlp = spacy.load('en_core_web_sm') doc = nlp(txt)

stk = []

for w in doc:

if w.pos_ == 'NOUN' or w.pos_ == 'PROPN': stk.append(w.text)

elif (w.head.pos_ == 'NOUN' or w.head.pos_ == 'PROPN') and

(w in w.head.lefts):

46      Глава 2. Структуры данных Python

stk.append(w.text) elif stk:

chunk = '' while stk:

chunk = stk.pop() + ' ' + chunk print(chunk.strip())

Первые несколько строк скрипта — стандартный процесс настройки анализа текстовой фразы с помощью spaCy. Импортируем библиотеку spaCy, выбираем предложение, которое нужно разобрать, и загружаем модель spaCy для английского языка. После этого применяем к предложению пайплайн nlp и даем spaCy инструкцию сгенерировать синтаксическую структуру предложения. Это необходимо для таких задач, как извлечение именных групп.

ПРИМЕЧАНИЕ

Чтобы узнать более подробную информацию о spaCy, обратитесь к документации1.

Далее реализуем алгоритм, описанный ранее, по каждому слову текста. Если мы нашли существительное или один из дочерних элементов, расположенных слева от этого существительного, , отправляем слово в стек с помощью метода append(). Определяем эти слова, используя встроенные свойства spaCy, например w.head.lefts, которое позволяет перемещаться по синтаксической структуре предложения и находить нужные слова. Так, с помощью w in w.head. lefts мы ищем вершину (w.head), а затем дочерние слова, расположенные слева от нее (.lefts), и определяем, является ли данное слово (w) одним из них. Например, при анализе слова ubiquitous свойство w.head вернет слово structure (его синтаксическую вершину), а .lefts, примененное к structure, вернет слова a, ubiquitous и data, демонстрируя таким образом, что ubiquitous действительно является дочерним элементом, расположенным слева от structure.

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

List

a ubiquitous data structure

the Python programming language.

1 https://spacy.io