代码之家  ›  专栏  ›  技术社区  ›  jkeys

保存关键字最有效的数据结构是什么?

  •  1
  • jkeys  · 技术社区  · 15 年前

    我决定编写一个小的解析器来解析bbcode并返回格式正确的html。我很难决定用什么最有效的方式来表示关键词。我可以使用单独的字符串来保存它们,但我觉得必须有一些未知的数据结构(对我来说),才能进行有效的查找。

    我使用C++,如果在STL中我可以使用任何东西。我不打算实际使用它,所以我不需要使用任何类似PHP的东西。它将没有一个GUI接口;只需输入一个文本文件,然后输出一个新文件,并解析出HTML。

    编辑:通过关键字,我指的是开始和结束标签,例如 [b] [/b] .

    3 回复  |  直到 15 年前
        1
  •  4
  •   Alex Martelli    15 年前

    因为你提前知道你所有的关键词,你可以利用 perfect hashing ,例如通过 this library --另见维基百科 entry 以及它的指针。

        2
  •  2
  •   Kristoffon    15 年前

    经典的答案是哈希表。定时插入/更换。

    但你想要什么还不完全清楚。如果只是为了保持关键字整齐有序,而不是通过简单的数组来填充代码,那么可以使用defines来索引和选择它们。

        3
  •  1
  •   San Jacinto    15 年前

    经典的是在1973年的论文中引入的aho corasick关键字树。

    线性时间词插入,线性时间词查找。