Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
- Название:Фундаментальные алгоритмы и структуры данных в Delphi
- Автор:
- Жанр:
- Издательство:ДиаСофтЮП
- Год:2003
- ISBN:ISBN 5-93772-087-3
- Рейтинг:
- Избранное:Добавить в избранное
-
Отзывы:
-
Ваша оценка:
Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi краткое содержание
Книга "Фундаментальные алгоритмы и структуры данных в Delphi" представляет собой уникальное учебное и справочное пособие по наиболее распространенным алгоритмам манипулирования данными, которые зарекомендовали себя как надежные и проверенные многими поколениями программистов. По данным журнала "Delphi Informant" за 2002 год, эта книга была признана сообществом разработчиков прикладных приложений на Delphi как «самая лучшая книга по практическому применению всех версий Delphi».
В книге подробно рассматриваются базовые понятия алгоритмов и основополагающие структуры данных, алгоритмы сортировки, поиска, хеширования, синтаксического разбора, сжатия данных, а также многие другие темы, тесно связанные с прикладным программированием. Изобилие тщательно проверенных примеров кода существенно ускоряет не только освоение фундаментальных алгоритмов, но также и способствует более квалифицированному подходу к повседневному программированию.
Несмотря на то что книга рассчитана в первую очередь на профессиональных разработчиков приложений на Delphi, она окажет несомненную пользу и начинающим программистам, демонстрируя им приемы и трюки, которые столь популярны у истинных «профи». Все коды примеров, упомянутые в книге, доступны для выгрузки на Web-сайте издательства.
Фундаментальные алгоритмы и структуры данных в Delphi - читать онлайн бесплатно полную версию (весь текст целиком)
Интервал:
Закладка:
if not (Ch in sdClass^ ) then
Deque.Enqueue(sdNextState1);
end;
mtTerminal : begin
{в случае достижения конечного состояния строка соответствует регулярному выражению, если регулярное выражение не содержало никакого символа привязки или достигнут конец строки}
if (not FAnchorEnd) or (StrInx > length(S)) then begin
Result := true;
Exit;
end;
end;
end;
end;
end;
{достижение этой точки свидетельствует либо о том, что очередь исчерпана, либо о достижении конца строки. В первом случае подстрока не соответствует регулярному выражению, поскольку отсутствуют состояния для сопоставления. Во втором случае необходимо проверить состояния, расположенные слева от очереди, чтобы проверить, не является ли одно из них конечным. Если это так, строка соответствует регулярному выражению, определенному таблицей переходов}
while not Deque.IsEmpty do
begin
State := Deque.Pop;
with PNFAState (FTable [ State ])^ do
begin
case sdMatchType of
mtNone : begin
{для бесплатных переходов необходимо заталкивать в очередь следующие состояния}
Deque.Push(sdNextState2);
Deque.Push(sdNextState1);
end;
mtTerminal : begin
{в случае достижения конечного состояния строка соответствует регулярному выражению, если регулярное выражение не содержало никакого символа привязки или достигнут конец строки}
if (not FAnchorEnd) or (StrInx > length(S)) then begin
Result := true;
Exit;
end;
end;
end; {case}
end;
end;
finally
Deque.Free;
end;
end;
Было бы желательно, чтобы подпрограмму сопоставления можно было бы применять не только к любой начальной позиции строки, но, при необходимости, и только ко всей строке.
Поэтому представим два новых символа операций регулярных выражений: символы операций привязки "^" и "$". Знак вставки "^" означает, что любое соответствие должно иметь место только с начала строки. Знак доллара "$" означает, что совпадение должно происходить на всем пути до самого конца строки. Так, например, регулярное выражение "^function" означает "совпадение со словом function с начала строки", a "^end.$" означает, что вся строка должна состоять из символов е, n, d и точки. Она не должна содержать никаких других символов. Символы ^ и $ могут присутствовать, соответственно, только в начале и конце регулярного выражения. Они не могут находиться ни в какой другой позиции.
Это обусловливает небольшое изменение определенных нами грамматических правил. Изменение не очень велико, но, как мы видели, корректная формулировка грамматических правил существенно упрощает создание кода. Код реализации нового правила и соответствующего метода синтаксического анализа приведен в листинге 10.16. Естественно, интерфейсный метод Parse также изменен, чтобы вызывать именно его, а не первоначальный метод.
Листинг 10.16. Использование операций привязки
{ ::= | '^' <���ехрr> | '$' | '^' <���ехрr> '$'}
function TtdRegexEngine.rcParseAnchorExpr : integer;
begin
{проверить на наличие начального символа '^'}
if (FPosn^ = '^') then begin
FAnchorStart :=true;
inc(FPosn);
end;
{выполнить синтаксический анализ выражения}
Result := rcParseExpr;
{в случае успеха необходимо выполнить проверку на наличие конечного символа '$'}
if (Result <> ErrorState) then begin
if (FPosn^ = '$') then begin
FAnchorEnd := true;
inc(FPosn);
end;
end;
end;
Теперь код выполнения сопоставления строк можно изменить для сопоставления как целых строк, так и подстрок. Если регулярное выражение начинается с символа "А", нужно просто попытаться становить соответствие строки, начиная с первого символа. Если нет, необходимо попытаться установить соответствие с каждой из подстрок, образованных из исходной строки. Код метода MatchString, в котором принимается это решение, приведен в листинге 10.17.
Листинг 10.17. Метод MatchString
function TtdRegexEngine.MatchString(const S : string): integer;
var
i : integer;
ErrorPos : integer;
ErrorCode : TtdRegexError;
begin
{если синтаксический анализ строки регулярного выражения еще не был выполнен, необходимо его выполнить}
if (FTable.Count = 0) then begin
if not Parse (ErrorPos, ErrorCode) then
rcError(tdeRegexParseError, 'MatchString', ErrorPos);
end;
{теперь необходимо выяснить, соответствует ли строка регулярному выражению (сопоставление пустых строк не выполняется)}
Result := 0;
if (S <> '') then
{если указанное регулярное выражение содержит начальный символ привязки, нужно проверить соответствие строки только начиная с первой позиции}
if FAnchorStart then begin
if rcMatchSubString(S, 1) then
Result := 1;
end
{в противном случае необходимо проверить соответствие строки в каждой из позиций и при первом же успешном сопоставлении выполнить возврат}
else begin
for i := 1 to length(S) do
if rcMatchSubString (S, i) then begin
Result := i;
Break;
end;
end;
end;
Если вы еще раз внимательно просмотрите листинг 10.15, то увидите, что код сопоставления уже обеспечивает применение конечного символа привязки. Код воспринимает конечное состояние в качестве признака соответствия регулярному выражению, если регулярное выражение не содержало конечного символа привязки, или же в случае достижения конца строки. При невыполнении любого из этих условий, конечное состояние будет игнорироваться..
Полный исходный код класса TtdRegexEngine можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDRegex.pas.
Резюме
В этой главе мы рассмотрели как детерминированные (DFA), так и недетерминированные (NFA) конечные автоматы. При этом мы исследовали несколько простых примеров DFA-автоматов.
Мы установили также, что при кодировании вручную конечные DFA-автоматы проще определить, понять и создать соответствующий код, в то время как конечные NFA-автоматы больше подходят для автоматических процессов. В заключение мы реализовали полную машину обработки регулярных выражений, которая выполняет синтаксический анализ и компиляцию регулярного выражения в конечный NFA-автомат (представленный таблицей переходов). Этот конечный NFA-автомат может использоваться для сопоставления строк.
Глава 11. Сжатие данных.
Думая о данных, обычно мы представляем себе ни что иное, как передаваемую этими данными информацию: список клиентов, мелодию на аудио компакт-диске, письмо и тому подобное. Как правило, мы не слишком задумываемся о физическом представлении данных. Заботу об этом - отображении списка клиентов, воспроизведении компакт-диска, печати письма - берет на себя программа, манипулирующая данными.
Представление данных
Рассмотрим двойственность природы данных: с одной стороны, содержимое информации, а с другой - ее физическое представление. В 1950 году Клод Шеннон (Claude Shannon) заложил основы теории информации, в том числе идею о том, что данные могут быть представлены определенным минимальным количеством битов. Эта величина получила название энтропии данных (термин был заимствован из термодинамики). Шеннон установил также, что обычно количество бит в физическом представлении данных превышает значение, определяемое их энтропией.
Читать дальшеИнтервал:
Закладка:
