Создание и использование словаря

Постановка задачи

Для множества слов S={S₁, S₂, … ,S_n}, имеющих соответственно толкования T={T₁, T₂, … ,T_n }, создать словарь и для последовательности слов P=(P₁, P₂, … ,P_k) с буквами из алфавита A={a₁, a₂, … ,a_m} определить для каждого слова P_i из P по словарю, принадлежит ли оно множеству S, и если принадлежит, то найти его толкование TP_i (см. [1], [3]).

Решение задачи создания и использования словаря

Под словарем для множества слов с толкованиями подразумевается структура данных, которая позволяет находить слова, определяя их толкования, и поддерживает операцию вставки слов с соответствующими им толкованиями.

Таким образом, словарь SL должен представлять собой структуру данных с реализованными на ней операциями НАЙТИ(u,SL,t,b) и ВСТАВИТЬ(u,t,SL). Здесь операция НАЙТИ(u,SL,t,b) осуществляет поиск слова u в словаре SL и возвращает, если слово найдено, его толкование t и значение b= true , в противном случае возвращается значение b = false. Операция ВСТАВИТЬ(u,t,SL) пополняет словарь SL новым словом u, имеющим толкование t, если этого слова в словаре не было, и меняет толкование слова u в словаре SL на t, если это слово в словаре уже было.

Задача создания словаря решается следующей процедурой:

procedure СОЗДАНИЕ_СЛОВАРЯ(S; T; n; var SL);

begin

for i:= 1 to n do ВСТАВИТЬ(S[i]_,T[i],SL)

end;

В задаче создания и использования словаря требуется создать словарь и для каждого слова P[i] из P определить по созданному словарю, принадлежит ли оно множеству S, если принадлежит, то найти его толкование TP_i и положить bP[i]=true, если же не принадлежит, то положить bP[i]=false.

procedure СОЗДАНИЕ_И_ИСПОЛЬЗОВАНИЕ_СЛОВАРЯ(S; T; n; P; k; var SL; var TP; var bP);

begin

СОЗДАНИЕ_СЛОВАРЯ(S; T; n; SL);

for i:= 1 to k do НАЙТИ(P[i],SL,TP[i],bP[i]);

end;

Тривиальный алгоритм

В данном алгоритме в качестве структуры данных для словаря используется список. Временная сложность исполнения процедуры СОЗДАНИЕ И ИСПОЛЬЗОВАНИЕ СЛОВАРЯ может быть оценена величиной O((k+n)×n).

Алгоритм с использованием АВЛ-дерева

В данном алгоритме в качестве структуры данных для словаря используется АВЛ-дерево. Временная сложность исполнения процедуры СОЗДАНИЕ И ИСПОЛЬЗОВАНИЕ СЛОВАРЯ может быть оценена величиной O((k+n)×log(n)).

Задания для лабораторной работы № 3

1. Написать программу, реализующую тривиальный алгоритм и алгоритм с использованием АВЛ-дерева для решения поставленной задачи, основываясь на псевдокоде процедуры СОЗДАНИЕ И ИСПОЛЬЗОВАНИЕ СЛОВАРЯ.

2. Написать программу, реализующую оба алгоритма, для проведения экспериментов, в которых можно выбирать:

· количество букв в алфавите,

· число n слов в словаре,

· число k слов в последовательности,

· количество s букв в словах,

· способ независимого друг от друга задания слов словаря (множество S) и слов последовательности P из числа следующих:

· непосредственный ввод,

· псевдослучайное образование слов выбранной длины, составленных из равновероятно встречающихся букв алфавита,

· образование требуемого количества слов, являющихся по выбору либо лексикографически минимальными, либо лексикографически максимальными в данном алфавите A.

Выходом данной программы должно быть время работы T₁ тривиального алгоритма и время работы T₂ использующего АВЛ-деревья алгоритма в секундах.

3. Провести эксперименты на основе следующих данных:

3.1. S и P составлены из n и k соответственно псевдослучайных семибуквенных слов в 33-буквенном алфавите, n=10⁴+1, k=1, … ,10⁴+1 с шагом 100 (нарисовать графики функций T₁(k) и T₂(k)),

3.2. S и P состоят из n и k соответственно лексикографически минимальных семибуквенных слов в 33-буквенном алфавите, n=10⁴+1, k=1,…,10⁴+1 с шагом 100 (нарисовать графики функций T₁(k) и T₂(k)),

3.3. S состоит из n лексикографически минимальных, а P состоит из k лексикографически максимальных семибуквенных слов в 33-буквенном алфавите, n = 10⁴+1, k = 1, … ,10⁴+1 с шагом 100 (нарисовать графики функций T₁(k) и T₂(k)).

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

Поиск фрагмента в тексте

Постановка задачи

Для слов Y = Y₁ Y_{2 …} Y_n и X = X₁ X_{2 …} X_m в алфавите A найти все вхождения слова Y в X. В дальнейшем под решением этой задачи мы будем понимать такую функцию f: {1, 2, … ,m}®{0, 1, 2, … , n}, что f[j] = n, если Y₁ Y_{2 …} Y_n =X _j-(n-1) X _{j-(n-2) …} X _j (на j-ой букве слова X заканчивается очередное вхождение в него слова Y), и f[j]<n в противном случае. Для избавления псевдокодов алгоритмов от мешающих их пониманию деталей, мы будем в дальнейшем считать, что 1≤n≤m.