前言
目前 LLM（Large Language Model）从文本补全到内容创作，都展示出了强大的生成能力。然而通过 LLM 生成结构化的数据如 JSON 格式的输出，却仍然是一个有挑战性的任务。
生成结构化的数据不仅要求模型输出符合特定的语法规则，还需要确保数据的正确性和一致性。
虽然通过 Prompt 工程可能可以实现指定格式的结构化数据生成，但是这也很大程度取决于模型的能力，容易出现幻觉或格式错误。
本文将探讨如何结合人工规则让 LLM 输出符合 JSON 格式的数据，重点讲解 lm-format-enforcer 库的实现原理。
结构化生成原理
本文主要是结合 lm-format-enforcer 这个库来讲解如何让 LLM 生成指定格式的 JSON 数据。
目前该库也是被 vllm 作为 JSON 格式输出的后端之一。
结构化数据生成的原理用一句话概括就是：
每个 step 拿到当前 model 给出的 logits 之后，在采样下一个 token 之前，通过人工设定的规则可以得到当前 step 只允许采样的 token 集合，接着通过加 bias 的方式压制其他不允许采样的 token，从而实现指定的结构化数据生成。
那么怎么得到当前 step 可允许采样的 token 集合，就是本文重点讲解的内容了。
lm-format-enforcer 这个库包含两个核心模块，分别是 tokenizer 前缀树 和 字符级别的解析器，通过这两个模块就可以实现上述的功能。
构造 tokenizer 前缀树
lm-format-enforcer 这个库在初始化阶段，首先会根据 tokenizer 给出的词表，初始化一个字符级别的前缀树，这个前缀树怎么理解呢？
通过 tokenizer 给出的词表，我们可以得到一个词表中的 字符串 和 对应 token id 的映射。通过这些映射，就可以来构造这个前缀树。
树上每个节点对应词表中某个字符串的其中一个字符，每个节点的子节点就是连着的下一个字符，当字符串中的字符已经遍历完了，这时候就是填入该字符串对应的 token id。
现在通过具体的例子解释一下，这个前缀树是如何构造的。
我们用 llama2 模型的词表来解读，假设就取词表中的一个小子集。
下面用图展示树的构造过程：
遍历第 1 个映射：
假设第一个映射是空格字符到 Token ID 35。
遍历后续映射：
随着更多映射插入，树会逐渐增长。实际的前缀树比这个大多了，整个词表中的 字符串 和 token id 的映射都会通过这样的方式插入到前缀树中。
约束每个 step 可允许采样 token 范围
构造好前缀树之后，接下来就是讲解怎么得到每个 step 可允许采样的 token 集合。
lm-format-enforcer 还有另一个重要的模块就是 字符级别的解析器。
这个解析器的作用简单来理解就是，在初始化的时候，会接收用户指定的 json schema，接着在后续每一步生成过程中，会根据之前生成的内容，判断目前处于什么状态，然后根据当前所处的状态直接给出限定的字符集合。
下面举个简单的例子，比如用户指定的 json schema 是：
{
"type": "object",
"properties": {
"city": {
"type": "string"
