标记的文本取决于一些特定规则。算法在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多规则是这样。如果我提供投入为'亚太邮联'，它应标记像'V-A+C-PPA+V-U'.我已经实施了一种算法，这样做并希望确保我是在做正确的事情。

算法

所有的规则将是保持在XML文件的相映射的标记。喜欢的东西

<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:：地图'.这将提供直到结束的应用(单一模式实现)。

2-迭代所输入的文字。对于每个角色，寻找相匹配。如果发现，成为更多的贪婪，并寻找更多的比赛，通过采取下一个符的输入文本。这样做，直到我们得到一个没有匹配。因此，对于输入文本'亚太邮联'，第一次寻找匹配'一个'.如果发现，试图获得更多的匹配，采取的下一个字符的输入文本。因此它会尽量比赛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-如果这是一个正确的方法、性传染疾病:：地图是一个好的选择在这里？或者我需要创造我自己的key/value容器？

3-是有一个图书馆提供它可tokenize串像上面？

任何帮助，将不胜感激

:)

Answer 1

所以你去过所有的标记在你的地图寻找相匹配的?你还不如使用一个清单或阵列，在那里；这将是一个效率低搜索。

一个更有效的方式找到公正的标记适用于开始或继续比赛将来储存他们的作为 trie.查阅的一封信那里会给你一个子trie其中只包含该标记，这有这封信作为第一个字母，然后你就继续找下尽可能可以去。

---

编辑：让我解释这一点进一步。

首先，我应该解释一下我不熟悉这些C++ std::map, ，超出了名，这使它成为一个完美的例子为什么一个学习理论的这些东西，以及于详细的特别图书馆特别是在编程语言：除非该图书馆是严重滥用的名称"地图"(这是不太可能)、名称本身告诉我很多关于数据的特征的结构。我知道，例如，那将是一个函数，给出一个单一的关键和地图，将非常有效地搜索和返回的价值相关联的关键，这也是可能的功能，这将给你一个清单/array/不管所有的钥匙，你能搜索你自己用你自己的代码。

我的解释的数据结构是，你有一张地图在哪里键是你叫什么模式，这些被列表(或阵列，或一些这类性质的)的字符，值是令牌。因此，你可以给出一个完整的模式，迅速找到令牌与它相关联。

不幸的是，虽然这样的地图是一个好比赛的转换XML输入格式的内部数据结构，这不是一个好比赛的搜索你需要做的。注意，你不看了整个图案，但第一个字符模式，产生一套可能的标记，然后通过查阅第二字符的图案 从内组模式产生的，首先查找, 等等。

所以你真正需要的不是一个单一的地图，但地图的地图的地图，每个键控通过一个单一的角色。查找"p"在顶层应该给你一个新的地图，有两项： p, 生产 C-PPA 令，"任何人"，生产的 C-PA 令牌。这实际上是一个构数据结构。

这有意义吗？

它可以帮助如果你开始写作的分析代码的第一次，在这一方式:想象一下别人会写信的功能要做的查找你需要的，他是一个真正的良好程序和可以做到的几乎任何魔法，你想要的。编写分析代码，集中于使这样简单和清洁，尽可能建立的任何接口使用这些武断的职能你需要(同时没有得到微不足道和更换整个事情有一个功能!).现在，你可以看看在查找功能的你结束了，告诉你，你怎么需要对数据的访问的结构，它会引导你的数据类型的结构需要。一旦你弄出来，然后你可以工作了如何以负荷。

Answer 2

1. 这个方法会起作用 - 我不确定它是否有效，但它应该起作用。

2. 我会使用标准 std::map 而不是您自己的系统。

3. 有类似的工具 lex （或者 flex）可以用于此目的。问题是您是否可以重新生成当 XML 规范更改时将构造的词法分析器。如果 XML 规范不经常更改，您也许可以使用诸如 lex 更轻松地进行扫描和绘图。如果 XML 规范可以根据程序使用者的意愿进行更改，那么 lex 可能不太合适。

有一些警告 - 尤其是 lex 和 flex 生成 C 代码，而不是 C++。

我还会考虑研究模式匹配技术——这类技术 egrep 特别是用途。这样做的优点是可以在运行时处理（因为 egrep 一直这样做）。或者您可以选择脚本语言 - Perl、Python...或者您可以考虑类似 PCRE（Perl 兼容正则表达式）库之类的东西。

Answer 3

但更好的，如果你要使用Boost库，总有标记生成器库中的加速 - >的 http://www.boost.org/doc/libs/1_39_0/libs/tokenizer/index.html

Answer 4

您可以使用正则表达式（也许是 boost::regex 库）。如果所有模式都只是字母字符串，则像“(a|p|pp|u)”这样的正则表达式会找到贪婪匹配。所以：

1. 使用上述模式运行 regex_search 来定位下一个匹配项
2. 将匹配文本插入 std::map 以获取替换文本。
3. 打印不匹配的消耗输入并将替换文本打印到输出，然后对剩余输入重复 1。

并做了。

Answer 5

它可能看起来有点复杂，但最有效的方式来做到这一点是利用一个图来表示一个状态图。起初，我还以为 boost.statechart 会有所帮助，但我想这是不是真的合适。这种方法可以更有效地，使用一个简单的std ::映射如果有许多规则，可能的字符的数量是有限的，文本的长度来读取是相当高的。

所以无论如何，使用简单的曲线图：

0）创建图表与 “开始” 顶点

1）读取的XML配置文件，并在需要时创建顶点（从一个过渡“字符集合”（例如“PP”），以附加的一个（例如，“PPA”））。每个顶点在内部，一个转换表存储到下一个顶点。如果“关键文本”是完整的，标记的顶点作为最终和存储所产生的文本

2）现在阅读文本和使用该图表解释。开始在“开始”顶点。 （*）用表来解释一个字符，并跳转到新的顶点。如果没有新的顶点已被选中，可以发出一个错误。否则，如果新的顶点是最后的，打印生成的文本，并跳回到开始的顶点。返回到（*），直到没有解释更多的文本。

您可以使用 boost.graph 来表示图形，但我认为这是你所需要的过于复杂。让你自定义的代表。