Я пишу генератор лексеров как проект для свободного времени, и мне интересно, как сделать сжатие таблиц. Рассматриваемые таблицы представляют собой двумерные массивы short и очень разреженные. Они всегда 256 символов в одном измерении. Другое измерение различается по размеру в зависимости от количества состояний в лексере.
Основные требования к сжатию таковы:
- Данные должны быть доступны без распаковки полного набора данных. И доступны в постоянном времени O (1).
- Достаточно быстро для вычисления сжатой таблицы.
Я понимаю метод смещения строк, который я сейчас реализовал. Это может быть моей наивной реализацией, но то, что у меня есть, ужасно медленно генерируется, хотя довольно быстро доступно. Я полагаю, что я мог бы сделать это быстрее, используя некоторый установленный алгоритм поиска строк, такой как один из найденных алгоритмов здесь .
Полагаю, можно было бы использовать Dictionary, но это похоже на читерство, и мне хотелось бы получить быстрое время доступа, которое я смог бы получить, если бы использовал прямые массивы с некоторым установленным алгоритмом. Возможно, я излишне беспокоюсь об этом.
Из того, что я могу собрать, flex не использует этот алгоритм для своих таблиц лексизма. Вместо этого он, кажется, использует нечто, называемое эквивалентность строки / столбца, для которого я действительно не смог найти никакого объяснения.
Мне бы очень хотелось узнать, как работает этот алгоритм эквивалентности строк / столбцов, который использует flex, или есть ли другой хороший вариант, который я должен рассмотреть для этой задачи.
Редактировать: Чтобы уточнить больше о том, что на самом деле эти данные. Это информация о состоянии для переходов состояний в лексере. Данные должны храниться в сжатом формате в памяти , поскольку таблицы состояний могут быть огромными. Это также из этой памяти, что фактические значения будут доступны напрямую, без распаковки таблиц. У меня есть рабочее решение, использующее смещение строк, но его убийственно медленно вычислять - частично из-за моей глупой реализации.
Возможно, моя реализация метода смещения строк прояснит, как получить доступ к этим данным. Это немного многословно, и я надеюсь, что все в порядке, что я положил его на пастин вместо здесь.
Данные очень скудные. Обычно это большой набор нулей, за которыми следуют несколько шорт для каждого состояния. Было бы тривиально, например, кодировать его по длине прогона, но это испортило бы
время линейного доступа.
Flex , очевидно, имеет две пары таблиц: base и default для первой пары и next и check для второй пары. Эти таблицы, кажется, индексируют друг друга способами, которые я не понимаю. Книга Дракона пытается объяснить это, но, как это часто бывает с этим томом тайного знания, то, что он говорит, теряется в более слабых умах, таких как мой.