65.9K
CodeProject 正在变化。 阅读更多。
Home

基于变量的字符串解析器

Dileepa Jayathilaka
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.67/5 (3投票s)

2007年2月27日

8分钟阅读

viewsIcon

39597

downloadIcon

562

关于一个将字符串与由变量和常量组成的模板统一的工具的文章。

Screenshot - StringUnifier.jpg

引言

有些人可能称之为标记器而不是解析器。然而，这不仅仅是另一个字符串标记器。实际上，字符串标记器是这项工作的一部分，因此如果需要，它也可以用作标记器。然而，有趣的部分在于使用变量进行解析（您可以控制这些变量的属性，例如长度、可能的字符串等！）。为了快速了解其用法，我列出了三种可以使用它的情况。第一种很简单，而第二种和第三种则更高级。

  1. 找出字典中所有以“ad”开头并以“y”结尾的单词。
  2. 在一篇文本中查找所有形式为“in <任意单词> of <一到两个单词> this”的出现（短语），以及出现在该短语之前和之后的那两个单词。
  3. 找出字典中所有形式为“<任意数量的字符> <一个字符，例如 X> <两个或更多字符> <X>（再次）”的单词

其中的概念是将给定的字符串（可能是单个单词、数字模式或整个文本）与由变量和字符串组成的给定模板统一起来。

示例模板是：aa+X+Y+b+Y+X，其中变量用大写字母表示（在此示例中为X和Y）。可以设置约束，例如“变量X的长度应在 2 到 5 之间”，“变量Y只能与集合 {ab,b,ca} 中的某个字符串统一”。

背景

我正在为僧伽罗语（我的母语）开发一个词性标注器。在僧伽罗语中，单词的前缀和后缀与其词性标签（名词、动词等）之间存在很强的联系。然而，没有明确的规则可以体现这些联系，它们都是概率性的，就像大多数其他语言一样。我想根据各种模板分解字典中的单词，并尝试探索这些模板与单词词性标签之间的联系。答案是开发一个工具来将给定的字符串与一个显然由变量和常量（字符串）序列组成的给定模板统一起来。

我试图使这个工具尽可能通用，以便它可以在完全不同的上下文中重用。之后，我将其用于句子解析（而不是原始要求中的单词解析）来探索句子中的单词模式。

字符串的单位

我使用了“字符串”而不是“字符”作为字符串的单位，这样会更通用。因此，输入字符串是子字符串的序列（字符串列表 - CStrList 类封装了这一点）。如果有人需要使用字符作为单位（如在统一字符串是单词时更常见），他们可以使用单个字符字符串（我使用了CString）。

程序的输入和输出

输入是要解析的字符串（更具体地说，是字符串列表）以及需要统一的模板。输出是一个解决方案列表，其中每个解决方案都具有变量的唯一组合值。让我举个例子

输入字符串：a+b+d+c+d+ab+b+d+c+b+aa

模板：a+X+d+Y+X+Z

其中 X、Y 和 Z 是变量。

    将有三个解决方案
  1. {X = b, Y = c+d+ab, Z = d+c+b+aa}
  2. {X = b, Y = c+d+ab+b+d+c, Z = aa}
  3. {X = b+d+c, Y = ab, Z = b+aa}

通过指定变量约束，我们可以减少解决方案的数量来处理更具体的情况。

变量

变量（封装在CVariable类中）代表一个字符串单元列表。变量的长度是它包含的字符串单元的数量。

变量的属性是

  1. 长度
  2. 最小长度
  3. 最大长度
  4. 可能的字符串（值集 - 字符串列表 - 该变量可以统一为此）

设置这些属性是可选的。用户可以省略任何未设置的属性。例如，如果给定变量的可能字符串列表为空，则程序假定该变量可以与任何字符串统一。当需要约束时，可以设置一个或多个属性为所需值。但是，有一个内置的约束是不可更改的——变量长度必须大于零，即任何变量都不能与空字符串统一。

算法

让我用另一个例子来解释算法。假设给定的模板是“a+X+a+Y+X+b+Z+d”（其中X、Y和Z是变量），要解析的字符串是“a+b+a+c+a+b+b+c+b+c+d”

  1. 我们查找模板的开头和结尾的常量。在这种情况下，模板开头有常量“a”，结尾有常量“d”。我们检查这些常量是否能在给定字符串的开头和结尾找到。如果找到，我们就从字符串和模板中移除它们。如果此测试失败，则可以终止统一，即没有解决方案。

    第一步之后，我们需要将字符串“b+a+c+a+b+b+c+b+c”与模板“X+a+Y+X+b+Z”进行统一

  2. 现在在模板中搜索中间常量。在这里，我们找到“a”和“b”。我们在字符串的左侧尽可能多的方向定位它们。
    X a Y+X b Z
b a c+a b b+c+b+c

    从这个方向，我们得出变量的解决方案为 {X = b, Y+X = c+a, Z = b+c+b+c}。

  3. 现在我们像解联立方程一样求解这个方程组。从第二个方程（Y+X = c+a）出发，我们只能得到一种分解方式，即 Y=c & X=a，因为变量的最小长度是 1。然而，X=a 与 X=b（第一个方程）相矛盾。因此，这个解决方案不能被接受。
  4. 下一步是将最右边的常量（此处为**b**）移动到下一个可能的左侧位置。方向将如下所示
    X a Y+X b Z
b a c+a+b b c+b+c

    解决方案集为 {X = b, Y+X = c+a+b, Z = c+b+c}

  5. 解方程。从第二个方程出发，有两种可能的分解。
    1. Y = c & X = a+b
    2. Y = c+a & X = b

    分解（i）与第一个方程矛盾。然而，分解（ii）是一个有效的解决方案。导出的解决方案是 {X = b, Y = c+a, Z = c+b+c}。我们将此解决方案添加到我们的解决方案集中。

  6. 接下来，移动在先前步骤中我们正在移动的常量左边的常量。移动规则相同。
    X a Y+X b Z
b+a+c a b b c+b+c

推导出可能的解决方案并将正确的解决方案添加到解决方案集中。

这些是算法的前几个步骤。现在，您可能对它是如何工作的有了一个大概的了解。现在我将以更正式的方式描述完整的算法。

  • 首先，从字符串和模板中移除模板中的前缀和后缀常量（如果存在）。
  • 将模板中剩余的常量（位于变量之间的常量）定位在左侧尽可能多的方向。
  • 在此之后，每次移动一个常量（向右）。移动规则是：将最左侧的可能常量移动到其下一个左侧位置。在每个唯一的常量位置组合处，推导出可能的解决方案并将正确的解决方案添加到解决方案集中。当常量无法移动时（即当常量处于最右侧可能方向时），过程结束。

使用代码

使用代码一点也不难。您无需理解算法即可使用代码。我将解释在应用程序中使用它的所有步骤。

  1. 包含“Parser.h”文件。
  2. 创建一个CParser类的对象。
    CParser m_Parser;
  3. 向解析器对象添加变量。
    // create variable
CVariable* pVar = new CVariable;

pVar->s_Name = "X"; 
pVar->i_MinLength = 2; 
pVar->i_MaxLength = 5;
// add possible strings
// we add two possible strings (a+b  and  c)
CStrList oStrList;
oStrList.push_back("a");
oStrList.push_back("b");
pVar->lst_PossibleStrings.push_back(oStrList);
oStrList.clear();
oStrList.push_back("c");
pVar->lst_PossibleStrings.push_back(oStrList);
//add the variable to parser
m_Parser.AddVariable(pVar);
  4. 创建模板 - 创建模板元素并按顺序推送到模板中
    //create template
CTemplate* pTemplate = new CTemplate;
//now create elements and append to template
//we create the template X+a here. Therefore there are two elements
CTemplateElement* pElement = new CTemplateElement;
pElement->b_IsVar = true;
pElement->s_Str = "X";
pTemplate->lst_Elements.push_back(pElement);
pElement = new CTemplateElement;
pElement->b_IsVar = false;
pElement->s_Str = "a";
pTemplate->lst_Elements.push_back(pElement);
  5. 创建要解析的字符串
    //we create the string ab+c+a here
CStrList oStrList;
oStrList.push_back("ab")
oStrList.push_back("c")
oStrList.push_back("a")
  6. 调用解析器的ParseStrList方法
    CVariableValueSolutionSet* pSolutionSet = 
    m_Parser.ParseStrList(oStrList, pTemplate);
    工具中的类
  • CStrList - 此类派生自 std::list<CString>
  • CTemplateElement - 代表模板中的一个元素。它可以是变量或常量（由标志b_IsVar标记）。如果这是变量，则成员s_Str将包含变量名，否则包含字符串。
  • CTemplate - 由CTemplateElement列表组成
  • CVaiable - 代表一个变量
  • CVariableContainer - 此类用于内部操作。用户不必关心它。
  • CVariableValueSolution - 表示一个解决方案。它由一个映射组成，其中键是变量名，值是赋给变量的字符串
  • CVariableValueSolutionSet - 解析操作的输出集合
  • CParser - 执行解析。

*使用CParser::ParseStrList方法返回的CVariableValueSolutionSet对象后，必须销毁它。同时销毁模板。

pSolutionSet->Destroy();
pTemplate->Destroy();

无需删除变量，因为解析器对象将在其析构函数中删除它们。

TokenizeString 方法：这是一个在此工具中使用的全局方法。其声明如下。

void TokenizeString(CString sStr, list<CString> lstSeperators, 
    list<CString>& lstSubStr, list<CString>& lstTokens)
  • sStr - 要标记化的字符串
  • lstSeperators - 分隔符列表
  • lstSubStr - 按顺序包含解析后的子字符串（输出参数）
  • lstTokens - 按顺序包含解析后的标记（输出参数）

您可能会发现此方法在您的应用程序中有用。

关注点

我通过几次不成功的尝试才得出这个算法。使用了一个递归函数来实现算法。是否存在用于此类操作的标准算法？

我成功地将此算法用于解析单词和句子。如果有人将其用于分析大型文本，请告诉我结果，尤其是性能。

是否有人可以将其扩展以处理空变量？

历史

2007 年 2 月 20 日：初始发布
© . All rights reserved.