如何在磁盘上存储一个巨大的马尔可夫链，同时又能在不使用太多RAM的情况下查询它？

Question

我将马尔可夫链表示为一个嵌套的数据结构，在Python中表示为dicts的dict。。。E、 g.为了理解我的意思，给定句子'this is purely an example, this is not serious.'，我生成所有连续的对，并记录它们后面的符号及其频率：

{',': {'this': {'is': 1}},
 'an': {'example': {',': 1}},
 'example': {',': {'this': 1}},
 'is': {'not': {'serious': 1}, 'purely': {'an': 1}},
 'not': {'serious': {'.': 1}},
 'purely': {'an': {'example': 1}},
 'this': {'is': {'not': 1, 'purely': 1}}}

然后，我可以使用重复项访问进行查询。E、 这两个都可以看到。在

在这个人为的例子中，链的状态大小为2，但我用3、4、5、6的状态生成它们。文本语料库也是巨大的，其结果是代表链的字典占用了数十GB的内存。在

我在研究在磁盘上存储马尔可夫链的其他方法。我已经考虑过Neo4J，但它似乎不太适合这个特定的用例。这同样适用于Postgres的ltree结构。 然后，我在关系数据库中选择了一个简单的表，如下所示（状态大小4）：

^{pr2}$

在建造结构时会有一个性能上的折衷，但因为只有在可以接受的情况下才支付。在

有没有更好的方法可以在磁盘上存储大的Markov链，这样可以在不需要大量RAM的情况下进行查询？在

Answer 1

马尔可夫过程在某种意义上是一个概率状态机，它满足马尔可夫特性（你可以从任何状态启动状态机，这样过去的事件不会影响概率）。在

因此，您应该存储一个状态索引（通过它进行查询），以及一个Blob或更具描述性的内容，其中包括可以转换到的状态及其概率。在

在构建状态索引时，不应该只使用增量索引，而应该使用某种类似二进制搜索的方法，这在机器学习应用程序的领域中是有意义的。在

例如，对于“is”、“not”、“purely”和“this”（为了简单起见，我省略了“，”，“an”，“example”）可以有状态1000 1100 0100和0000。然后，状态“this is”将为0001，第一个00表示“this”，第二个01表示“is”。在这里，我假设“this is”将包含完整状态，例如，在您的数据集中不会有另一个“this is”。如果是这样的话，我认为这是对Markov属性的破坏或查询逻辑中的缺陷（而不是bigram，您应该查询其他东西）。在

无论如何，这应该是RAM高效的，可以让你有多种搜索策略。在