用自动机表达嵌套的数据

我们已使用 terark.com 进行商业化运营

嵌套数据的典型就是文件系统的目录层次,XML,JSON 等,它们都有专门的存储方式。不过,如果用自动机来存储,更是恰到好处,在这种应用场景中,使用 这篇文章 中提到的 map2:将路径的每层目录用分隔符隔开,比如/ 分隔

这样一来,自动机的嵌套数据模型就出奇得简单,DFA_Interface 中有相应的方法来操作这样的数据模型:

  • 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

 

我们已使用 terark.com 进行商业化运营

作者:
该日志由 rockeet 于2014年07月14日发表在自动机分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
转载请注明: 用自动机表达嵌套的数据
标签:
【上一篇】
【下一篇】

您可能感兴趣的文章:

发表评论

您必须 登录 后才能发表评论。