c++ - 根据某些特定规则对文本进行标记。 C++中的算法

Question

我正在编写一个程序，它将根据某些特定规则对输入文本进行标记。我为此使用 C++。

规则

Letter 'a' should be converted to token 'V-A'
Letter 'p' should be converted to token 'C-PA'
Letter 'pp' should be converted to token 'C-PPA'
Letter 'u' should be converted to token 'V-U'

这只是一个示例，实时我有大约 500 多个这样的规则。如果我以“appu”的形式提供输入，它应该像“V-A + C-PPA + V-U”一样进行标记化。我已经实现了执行此操作的算法，并希望确保我做的是正确的事情。

算法

所有规则都将保存在一个 XML 文件中，并带有相应的 token 映射。有点像

<rules>
  <rule pattern="a" token="V-A" />
  <rule pattern="p" token="C-PA" />
  <rule pattern="pp" token="C-PPA" />
  <rule pattern="u" token="V-U" />
</rules>

1 - 当应用程序启动时，读取此 xml 文件并将值保存在“std::map”中。这将一直可用到应用程序结束(单例模式实现)。

2 - 迭代输入文本字符。对于每个字符，寻找一个匹配项。如果找到，则变得更加贪婪并通过从输入文本中获取下一个字符来寻找更多匹配项。这样做直到我们得到一个不匹配。因此，对于输入文本“appu”，首先查找“a”的匹配项。如果找到，尝试通过从输入文本中获取下一个字符来获得更多匹配。所以它会尝试匹配 'ap' 但没有找到匹配项。所以它只是返回。

3 - 替换输入文本中的字母“a”，因为我们得到了它的标记。

4 - 对输入文本中的剩余字符重复步骤 2 和 3。

下面是更简单的步骤说明

input-text = 'appu'
tokens-generated=''

// First iteration
character-to-match = 'a'
pattern-found = true

// since pattern found, going recursive and check for more matches
character-to-match = 'ap'
pattern-found = false

tokens-generated = 'V-A'

// since no match found for 'ap', taking the first success and replacing it from input text
input-text = 'ppu'

// second iteration
character-to-match = 'p'
pattern-found = true

// since pattern found, going recursive and check for more matches
character-to-match = 'pp'
pattern-found = true

// since pattern found, going recursive and check for more matches
character-to-match = 'ppu'
pattern-found = false

tokens-generated = 'V-A + C-PPA'

// since no match found for 'ppu', taking the first success and replacing it from input text
input-text = 'u'

// third iteration
character-to-match = 'u'
pattern-found = true

tokens-generated = 'V-A + C-PPA + V-U'  // we'r done!

问题

1 - 这个算法看起来是否适合这个问题，或者是否有更好的方法来解决这个问题？

2 - 如果这是正确的方法，std::map 是一个不错的选择吗？还是我需要创建自己的键/值容器？

3 - 是否有可用的库可以像上面那样标记字符串？

任何帮助将不胜感激

:)

Answer 1

所以您要遍历 map 中的所有标记以寻找匹配项？您也可以在那里使用列表或数组；无论如何，这将是一个低效的搜索。

找到适合开始或继续比赛的 token 的更有效方法是将它们存储为 trie .在那里查找一个字母会给你一个子树，它只包含以那个字母为第一个字母的标记，然后你就可以继续向下搜索，直到你可以去。

---

编辑:让我进一步解释一下。

首先，我应该解释一下，除了名称之外，我对 C++ std::map 不熟悉，这使得这是一个完美的例子，说明为什么人们将这些东西的理论学习为以及特定编程语言中特定库的详细信息:除非该库严重滥用名称“map”(这不太可能)，否则名称本身告诉我很多关于数据结构的特征。例如，我知道会有一个函数，给定一个键和 map ，将非常有效地搜索并返回与该键关联的值，并且可能还有一个函数会为您提供一个列表/array/所有键中的任何一个，您可以使用自己的代码自行搜索。

我对你的数据结构的解释是你有一个映射，其中的键是你所说的模式，那些是字符列表(或数组，或类似性质的东西)，值是标记。因此，您可以在给定完整模式的情况下快速找到与其关联的标记。

不幸的是，虽然这样的映射非常适合将您的 XML 输入格式转换为内部数据结构，但它不太适合您需要进行的搜索。请注意，您不是查找整个模式，而是查找模式的第一个字符，生成一组可能的标记，然后从第一个生成的模式集中查找模式的第二个字符 查找，等等。

因此，您真正需要的不是单个 map ，而是 map 的 map ，每个 map 都由一个字符键入。在顶层查找“p”应该会为您提供一个新 map ，其中包含两个键:p，生成 C-PPA token ，以及“其他任何东西”，生成 C-PA token 。这实际上是一个 trie 数据结构。

这有意义吗？

如果您首先以这种方式编写解析代码，这可能会有所帮助:想象一下其他人将编写函数来执行您需要的查找，并且他是一个非常优秀的程序员并且几乎可以完成您的任何魔术想。编写解析代码，集中精力使其尽可能简单和干净，使用您需要的这些任意函数创建任何界面(同时不要变得微不足道并用一个函数替换整个东西!)。现在您可以查看最终得到的查找函数，它告诉您需要如何访问您的数据结构，这将引导您找到所需的数据结构类型。一旦你弄明白了，你就可以弄清楚如何加载它。