用自动机表达嵌套的数据
嵌套数据的典型就是文件系统的目录层次,XML,JSON 等,它们都有专门的存储方式。不过,如果用自动机来存储,更是恰到好处,在这种应用场景中,使用 这篇文章 中提到的 map2:将路径的每层目录用分隔符隔开,比如用 / 分隔。
这样一来,自动机的嵌套数据模型就出奇得简单,DFA_Interface 中有相应的方法来操作这样的数据模型:
1 2 3 4 5 |
bool step_key(MatchContext&, auchar_t delim, fstring) const; bool step_key(MatchContext&, auchar_t delim, fstring, const ByteTR&) const; bool step_key_l(MatchContext&, auchar_t delim, fstring) const; bool step_key_l(MatchContext&, auchar_t delim, fstring, const ByteTR&) const; size_t for_each_value(MatchContext&, const OnMatchKey&) const; |
- DFA_Interface 的大部分匹配函数都有一个带有 ByteTR 参数的重载版本,ByteTR 用来将输入字节进行转码后再匹配,例如要忽略大小写就用:tolower ,当然前提是建库时也将所有字符 Key 字符都用 tolower 转化了
- 带 _l 后缀的方法名表示最长匹配,不带的表示最短匹配
- MatchContext 保存了匹配信息,用作后续匹配,或者直接传给 for_each_value ,枚举当前路径下的所有文件名(对文件系统,就是文件的相对路径)
- 如果使用 kvbin_build 创建自动机,delim 就是256 (在 byte 表示范围以外),从而 所有的 key, value 可以是任意二进制串
如此简单的数据模型,功能却是异常得强大:
- 数据可以嵌套任意多层
- 可以执行渐进匹配
- 充分利用了自动机的高效压缩功能,这类数据往往都有较高的冗余,利于自动机的压缩
示例代码: samples/automata/abstract_api/step_key.cpp