稀疏矩阵压缩，访问时间快

我正在写一个lexer生成器作为一个业余项目，我想知道如何进行表压缩。所讨论的表是short的2D阵列并且非常稀疏。它们在一个维度中总是256个字符。另一个维度的大小根据lexer中的状态数而变化。

压缩的基本要求是

• 数据应该是可访问的，而无需解压缩整个数据集。并且在常数O（1）时间内可访问
• 计算压缩表的速度相当快

我了解行位移法，这是我目前已经实现的方法。这可能是我天真的实现，但我所拥有的生成速度慢得可怕，尽管访问速度很快。我想我可以使用一些已经建立的字符串搜索算法，比如这里的一个算法，让它更快。

我想一个选择是使用Dictionary，但这感觉像是作弊，我希望如果我使用带有一些既定算法的直数组，我能够获得快速访问时间。也许我不必要为此担心。

据我所知，flex在词法表中没有使用这种算法。相反，它似乎使用了一种名为行/列等价的东西，我真的找不到任何解释。

我真的很想知道flex使用的行/列等效算法是如何工作的，或者我是否应该为这项任务考虑其他好的选择。

编辑：详细说明此数据的实际内容。它是lexer中状态转换的状态信息。数据需要以压缩格式存储在内存中，因为状态表可能很大。也正是从这个内存中，可以直接访问实际值，而无需解压缩表。我有一个使用行位移的工作解决方案，但它的计算速度非常慢——部分原因是我的实现很愚蠢。

也许我对行位移方法的实现会让我们更清楚地了解如何访问这些数据。它有点冗长，我希望我把它放在pastebin上而不是这里没关系。

数据非常稀疏。它通常是一大串零，然后是每个州的几个空头。例如，对其进行游程编码是微不足道的，但它会破坏线性访问时间。

Flex显然有两对表，base和default用于第一对，next和check用于第二对。这些表似乎以我不理解的方式相互索引。龙之书试图解释这一点，但就像那本神秘知识的大部头经常发生的情况一样，它所说的在像我这样的小人物身上消失了。