寻找反转 sprintf() 函数输出的算法

StackOverflow https://stackoverflow.com/questions/9882

题

我正在开发一个需要解析日志文件的项目。我正在寻找一种快速算法，可以接受如下组消息：

P1 处的温度为 35F。

P1 处的温度为 40°F。

P3 处的温度为 35F。

记录器停了下来。

记录器启动。

P1 处的温度为 40°F。

并以 printf() 的形式输出一些内容：

"The temperature at P%d is %dF.", Int1, Int2" 
{(1,35), (1, 40), (3, 35), (1,40)}

该算法需要足够通用才能识别消息组中的几乎所有数据负载。

我尝试搜索这种技术，但我什至不知道搜索的正确术语。

有帮助吗？

解决方案

概述：

A 幼稚的！！ 算法以每列的方式跟踪单词的频率，其中可以假设每一行都可以用分隔符分成几列。

输入示例：

狗跳过了月亮
猫跳过了月亮
月亮跳过了月亮
汽车跳过了月亮

频率：

Column 1: {The: 4}
Column 2: {car: 1, cat: 1, dog: 1, moon: 1}
Column 3: {jumped: 4}
Column 4: {over: 4}
Column 5: {the: 4}
Column 6: {moon: 4}

我们可以通过根据字段总数进行分组来进一步划分这些频率列表，但在这个简单方便的示例中，我们仅使用固定数量的字段 (6)。

下一步是迭代生成这些频率列表的行，所以让我们以第一个示例为例。

  1. 这: ：满足一些手波标准，算法决定它必须是静态的。
  2. 狗: ：根据频率列表的其余部分，它似乎不是静态的，因此它必须是动态的，而不是静态文本。我们循环遍历一些预定义的正则表达式并得出 /[a-z]+/i.
  3. 超过: ：与 #1 相同的交易；它是静态的，所以保持原样。
  4. 这: ：与 #1 相同的交易；它是静态的，所以保持原样。
  5. 月亮: ：与 #1 相同的交易；它是静态的，所以保持原样。

因此，只需查看第一行，我们就可以将以下正则表达式组合在一起：

/The ([a-z]+?) jumps over the moon/

注意事项：

  • 显然，只要确信频率列表足以对整个数据进行采样，就可以选择在第一次扫描时扫描部分或整个文档。

  • 误报可能会渗透到结果中，这将取决于过滤算法（挥手）来提供静态和动态字段之间的最佳阈值，或进行一些人工后处理。

  • 总体想法可能是好的，但实际实现肯定会影响该算法的速度和效率。

其他提示

我认为您可能忽略并错过了 fscanf() 和 sscanf()。与 fprintf() 和 sprintf() 相反。

感谢所有的好建议。克里斯，是对的。我正在寻找一种通用的解决方案来规范任何类型的文本。该问题的解决方案归结为动态地查找两个或多个相似字符串中的模式。几乎就像根据前两个元素预测集合中的下一个元素：

1：珠穆朗玛峰高 30000 英尺

2：K2 高 28000 英尺

=> 模式是什么？=> 回答：

[名称] 高 [数字] 英尺

现在文本文件可以有数百万行和数千个模式。我想非常非常快地解析文件，找到模式并收集与每个模式关联的数据集。

我考虑创建一些高级语义哈希来表示消息字符串中的模式。我将使用标记生成器并为每个标记类型赋予特定的“权重”。然后我会对哈希进行分组并评估它们的相似性。分组完成后，我将收集数据集。

我希望我不必重新发明轮子，并且可以重用已经存在的东西。

克劳斯

这取决于您想要做什么，如果您的目标是快速生成 sprintf() 输入，那么这是可行的。如果您尝试解析数据，也许正则表达式也可以。

您不会找到一个可以简单地接受任意输入、猜测您想要从中获得什么数据并生成您想要的输出的工具。对我来说，这听起来像是强大的人工智能。

制作这样的东西，即使只是为了识别数字，也会变得非常棘手。例如“123.456”是一个数字还是两个数字？这个“123456”怎么样？“35F”是十进制数和“F”还是十六进制值 0x35F？您将必须构建一些能够按照您需要的方式进行解析的东西。您可以使用正则表达式来完成此操作，也可以使用 sscanf, ，或者你可以用其他方式来做，但你必须编写一些自定义的东西。

但是，使用基本的正则表达式，您可以自己完成此操作。这不会很神奇，但也没有那么多工作。像这样的东西将解析您感兴趣的行并合并它们（Perl）：

my @vals = ();
while (defined(my $line = <>))
{
    if ($line =~ /The temperature at P(\d*) is (\d*)F./)
    {
        push(@vals, "($1,$2)");
    }
}
print "The temperature at P%d is %dF. {";
for (my $i = 0; $i < @vals; $i++)
{
    print $vals[$i];
    if ($i < @vals - 1)
    {
        print ",";
    }
}
print "}\n";

这个的输出是L

The temperature at P%d is %dF. {(1,35),(1,40),(3,35),(1,40)}

您可以对需要解析的每种类型的行执行类似的操作。您甚至可以从文件中读取这些正则表达式，而不是对每个正则表达式进行自定义编码。

我不知道有什么具体的工具可以做到这一点。当我遇到类似的问题需要解决时，我所做的就是尝试猜测正则表达式来匹配行。

然后我处理这些文件并仅显示不匹配的行。如果一条线不匹配，则意味着该模式是错误的，应进行调整或添加另一个模式。

经过大约一个小时的工作，我成功找到了大约 20 个模式来匹配 10000 多行。

就您而言，您可以首先“猜测”一种模式是 "The temperature at P[1-3] is [0-9]{2}F.". 。如果您重新处理文件并删除任何匹配的行，则会留下“仅”：

记录器停了下来。

记录器启动。

然后您可以将其与 "Logger (.+).".

然后，您可以优化模式并找到新的模式来匹配您的整个日志。

@约翰：我认为这个问题涉及一种算法，该算法实际上可以识别日志文件中的模式并自动“猜测”适当的格式字符串和数据。这 *scanf 家庭本身无法做到这一点，只有首先认识到这些模式，它才能提供帮助。

@德里克公园：好吧，即使是强大的人工智能也不能确定它有正确的答案。

也许可以使用一些类似压缩的机制：

  1. 查找大的频繁子串
  2. 查找大的、频繁的子串模式。（IE。[模式：1] [垃圾] [模式：2]）

另一个要考虑的项目可能是按以下方式对行进行分组 编辑距离. 。将相似的线分组应该将问题分成每组一个模式的块。

事实上，如果你能写出这个， 让全世界都知道, ，我想我们很多人都会喜欢这个工具！

@安德斯

好吧，即使是强大的人工智能也不能确定它有正确的答案。

我当时认为足够强大的人工智能可以 通常 从上下文中找出正确答案。例如强大的人工智能可以识别出在这种情况下“35F”是一个温度而不是一个十六进制数字。肯定有一些情况，即使是强大的人工智能也无法回答。不过，这些都是人类无法回答的相同情况（假设 非常 强人工智能）。

当然，这并不重要，因为我们没有强大的人工智能。:)

http://www.logparser.com 转发到一个看起来相当活跃的 IIS 论坛。这是 Gabriele Giuseppini 的“日志解析器工具包”的官方网站。虽然我从未真正使用过这个工具，但我确实从 Amazon Marketplace 上买了一本便宜的书 - 今天一本的价格低至 16 美元。没有什么比死树界面更适合翻页了。

浏览这个论坛，我以前没有听说过“MS Log Parser 的新 GUI 工具，Log Parser Lizard” http://www.lizardl.com/.

当然，关键问题是语法的复杂性。要使用任何类型的日志解析器（该术语很常用），您需要确切地知道您要扫描的内容，您可以为其编写 BNF。很多年前我学过一门基于Aho-and-Ullman的《龙之书》的课程，彻底理解LALR技术可以给你最佳的速度，当然前提是你有那个CFG。

另一方面，你似乎确实可能正在追求类似人工智能的东西，这是完全不同的复杂程度。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top