В этой главе мы рассмотрели как детерминированные (DFA), так и недетерминированные (NFA) конечные автоматы. При этом мы исследовали несколько простых примеров DFA-автоматов.

Мы установили также, что при кодировании вручную конечные DFA-автоматы проще определить, понять и создать соответствующий код, в то время как конечные NFA-автоматы больше подходят для автоматических процессов. В заключение мы реализовали полную машину обработки регулярных выражений, которая выполняет синтаксический анализ и компиляцию регулярного выражения в конечный NFA-автомат (представленный таблицей переходов). Этот конечный NFA-автомат может использоваться для сопоставления строк.

Сжатие данных

Думая о данных, обычно мы представляем себе ни что иное, как передаваемую этими данными информацию: список клиентов, мелодию на аудио компакт-диске, письмо и тому подобное. Как правило, мы не слишком задумываемся о физическом представлении данных. Заботу об этом - отображении списка клиентов, воспроизведении компакт-диска, печати письма - берет на себя программа, манипулирующая данными.

Сопоставление строк с регулярными выражениями || Оглавление || Представление данных


Фундаментальные алгоритмы и структуры данных в Delphi



Новости за месяц

  • Май
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс