从日志文件中查找最常见的字符串

Question

从日志文件中查找最常见的字符串

c++cdata-structures

3

我想在一个巨大的日志文件中找到最常见的字符串。有没有人能帮我如何做到这一点。一种方法是对每个字符串进行哈希并计算最大值，但这不是高效的。有更好的方法吗？

谢谢和问候，

Mousey.

- mousey

我看不到其他的方法，只能逐个单词计数并将单词和计数器放入列表中。如果结构变得太大，您可以考虑将文件拆分为较小的部分，在那里进行计数，然后进行第二轮计数。 - tofi9

4

为什么我们每次提问都要被问是否是作业？别这样了。 - FogleBird

@greg 这不是作业。我现在没有在任何学校里。 - mousey

9个回答

3

"巨大"有多大？什么是"字符串"? Unix命令行工具非常好用：

tr -s ' \011' '\012' < /var/log/messages | sort | uniq -c | sort -rn | head -20

生成

    786 --
    635 labrador
    635 Jun
    393 MARK
    236 kernel:
    163 17
    153 usb
    136 22
    118 21
    113 USB
     74 device
     73 20
     73 19
     72 18
     57 5-1:
     51 address
     43 speed
     36 New
     34 0
     33 using

在写和调试 C 程序的时间内，你可以运行许多 Shell 脚本。

- Norman Ramsey

1

+1 个赞 :) 当然，如果你需要重复执行这个任务，你可能会对加速它感兴趣。 - Matthieu M.

3

除非哈希算法很昂贵（我一直认为它们很便宜），否则哈希既可以节省内存（平均哈希长度可能比平均行或单词长度更短，以字节为单位，假设使用8位ASCII），又可以更快地进行字典查找。

不想使用哈希的原因是什么？

- Robert Hui

3

如果性能很重要，您可能需要查看trie或Radix tree。

如果您只是想知道一个字符串是否出现了超过50％的次数（我们将其称为主要字符串），则可以执行以下操作（看看我能否搞定）：

1. 获取第一个字符串并假设它是主要字符串，并将其发生次数设置为1；

2. 获取下一个字符串；

3. 如果它与当前的主要候选者相同，则增加其发生次数；

4. 否则，减少出现次数；

5. 如果出现次数达到0，请使用当前字符串替换主要候选者；

6. 只要有字符串可读，就从2重复；

7. 如果在结尾处出现次数大于0，请重新扫描日志并计算候选者的实际出现次数以检查它是否真的是主要字符串。

因此，您需要两次遍历日志。

注意：这是一道曾经用于ACM编程竞赛的问题，在这里可以找到更多信息。

- Eugen Constantin Dinca

50%是一个很大的假设，我想知道是否可能以某种方式调整方法来适用于任意百分比（使用更多空间）。 - Matthieu M.

@Matthieu M.：问题中使用的定义是：“非空序列N个数字的大多数数字恰好是在序列中出现超过N/2次的数字。”“超过50%”只是我试图记住它的方式...这是一个非常大的假设，但据我所知，这是以线性时间获得答案的唯一方法（您最多可以在日志文件中两次通过单词）。另一方面，尝试和基数树都提供了相当不错的性能（以使用更多的空间为代价）。 - Eugen Constantin Dinca

2

假设您的意思是按行或单词（或其他分隔符），您可以遍历每个“字符串”并将其放入数据结构中。每次找到相同的字符串时，您将增加数据结构中该字符串的值。

stl map可以做到这一点。字符串将成为键，与键关联的值将是找到该字符串的次数。您还可以使用stl multiset。您只需计算具有相同键的项目数。

- BSchlinker

哦，天啊，不要重复搜索字符串。这样做的性能将会非常糟糕。 - Stefan Valianu

@Stefan 我理解这一点 - （我自己从不会实现这样的技术）。然而，Mousey的帖子似乎并未表明他在寻求性能方面的帮助。 - BSchlinker

不是要冒犯，但有一种方法是对每个字符串进行哈希处理并计算最大值，但这并不高效。有没有更好的方法来解决这个问题呢？我假设更好意味着更高效，因为他说哈希处理由于效率问题不足够。 - Stefan Valianu

@Stefan，我道歉了。当我阅读原帖时，我以为他说他不能使用哈希，但没有说明原因。现在我明白我看错了，已经修改了我的答案。 - BSchlinker

1

我认为最好的方法是进行单次扫描，计算单词并通过单词在映射中累积计数。

如果您的日志文件是特定语言的，您可能希望忽略常见单词，如“the”、“a”。您还可以考虑使用词干提取算法。

- dsmith

0

如果你所说的“字符串”是指“单词”，那么我能想到的最有效的方法就是在读取单词时计算重复的单词，而不是存储然后计数。

- Luca Matteis

我怎样才能在不使用哈希表的情况下完成它？ - mousey

你是假设整个文件都在内存中缓冲，还是每次迭代都要回到磁盘上？在你的方法中，你仍然需要保持一个已经计数过的单词列表，对吗？ - dsmith

0

如果你在谈论日志文件中的任意子字符串，那么这个问题是无法在多项式时间内解决的。如果确实是一个巨大的日志文件，我相信你会很困难。

然而，如果你在谈论文件中的任何特定单词，你将不得不引用计数你的单词。这需要某种类型的映射。

如果你在谈论文件中的任何特定行，你将不得不引用计数你的行。这需要某种类型的映射。

无论哪种方式，你都需要使用某种类型的引用计数。

- Stefan Valianu

0

也许我的答案不是完全正确的。但是perl就是为这些目的而制作的。在perl中，这很容易实现。对于这个问题，大多数perl代码可以在六行内完成。

- prabhakaran

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sdg · Accepted Answer

如果您所说的字符串是一行文本，那么在任何类Unix的shell上，您都应该能够执行如下操作：

sort logfile.txt | uniq -c

这假设你的每一行没有独特的内容（例如时间戳），且文件大小足够小，可以用这种方式来处理。

当然，这并没有直接使用C或C++，但考虑到这些工具本身可能是用其中一种编码的，所以应该算是使用了。