Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Листинг 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) заложил основы теории информации, в том числе идею о том, что данные могут быть представлены определенным минимальным количеством битов. Эта величина получила название энтропии данных (термин был заимствован из термодинамики). Шеннон установил также, что обычно количество бит в физическом представлении данных превышает значение, определяемое их энтропией.
В качестве простого
Однако посмотрим на это под другим углом: во всех приведенных примерах записи данных мы сохраняем одни и те же результаты - одну и ту же информацию - используя все меньший и меньший объем памяти. Другими словами, мы выполняем сжатие данных.
Сжатие данных
Думая о данных, обычно мы представляем себе ни что иное, как передаваемую этими данными информацию: список клиентов, мелодию на аудио компакт-диске, письмо и тому подобное. Как правило, мы не слишком задумываемся о физическом представлении данных. Заботу об этом - отображении списка клиентов, воспроизведении компакт-диска, печати письма - берет на себя программа, манипулирующая данными.
Представление данных
Рассмотрим двойственность природы данных: с одной стороны, содержимое информации, а с другой - ее физическое представление. В 1950 году Клод Шеннон (Claude Shannon) заложил основы теории информации, в том числе идею о том, что данные могут быть представлены определенным минимальным количеством битов. Эта величина получила название энтропии данных (термин был заимствован из термодинамики). Шеннон установил также, что обычно количество бит в физическом представлении данных превышает значение, определяемое их энтропией.
В качестве простого примера рассмотрим исследование понятия вероятности с помощью монеты. Можно было бы подбросить монету множество раз, построить большую таблицу результатов, а затем выполнить определенный статистический анализ этого большого набора данных с целью формулирования или доказательства какой-то теоремы. Для построения набора данных, результаты подбрасывания монеты можно было бы записывать несколькими различными способами: можно было бы записывать слова "орел" или "решка"; можно было бы записывать буквы "О" или "Р"; или же можно было бы записывать единственный бит (например "да" или "нет", в зависимости от того, на какую сторону падает монета). Согласно теории информации, результат каждого подбрасывания монеты можно закодировать единственным битом, поэтому последний приведенный вариант был бы наиболее эффективным с точки зрения объема памяти, необходимого для кодирования результатов. С этой точки зрения первый вариант является наиболее расточительным, поскольку для записи результата единственного подбрасывания монеты требовалось бы четыре или пять символов.