数据结构/算法流数据和确定主题

Question

我想知道有效的算法/数据结构来识别流数据中的以下信息。

考虑像Twitter这样的实时流数据。我主要对下面的查询感兴趣，而不是存储实际的数据。

我需要我的查询来运行实际数据，但不是任何重复。

由于我对存储完整的数据不感兴趣，因此我很难识别重复的帖子。但是，我可以散列所有帖子并检查它们。但我想确定接近重复的帖子。我怎样才能做到这一点。

确定用户正在讨论的前k个主题。

我想确定用户正在讨论的热门话题。我不想要Twitter中显示的最高频率词。相反，我想给一些高级别话题的最常见的话题名称。

我希望我的系统是实时的。我的意思是，我的系统应该能够处理任何数量的流量。

我能想到map缩减的方法，但我不知道如何处理同步问题。例如，重复的帖子可以到达不同的节点，并且它们都可以将它们存储在索引中。

在一个典型的新闻来源，一个将删除数据中的任何停用词。在我的系统中，我想通过识别广泛主题中的顶级常用单词来更新停用词列表。

什么将是有效的算法/数据结构来实现这一点。

我想存储一段时间内的主题来检索数据中有趣的模式。说，周五晚上，每个人都想去看电影。什么将是存储这些数据的有效方式。

我想将它存储在Hadoop分布式文件系统，但过了一段时间后，这些指标变得如此之大，I/O将是我的主要瓶颈。

考虑来自世界各地推文的多语种数据。我如何确定在一个地理区域内正在讨论的类似主题？

这里有2个问题。一种是识别正在使用的语言。它可以基于个人推特进行识别。但是这些信息可能会影响用户的隐私。其他的想法，可以通过训练算法来运行它。目前最好的方法是什么？其他问题实际上是在字典中查找单词，并将其与常见的中间语言（如说英语）相关联。如何照顾词义消歧，如同一个词在不同的比赛中使用。

识别单词边界

一种可能是使用某种训练算法。但是，最好的方法是什么？这在某种程度上类似于词义消歧，因为您可以根据实际的句子确定词边界。

我想开发一个原型并评估系统而不是具体的实现。我认为它不可能取消实时twitter数据。我认为这种方法可以在一些在线免费提供的数据上进行测试。任何想法，我可以得到这些数据。

您的反馈是赞赏。

谢谢你的时间。

- 巴拉

Answer 1

有几个不同的问题埋在这里。我无法理解你所要问的所有问题，但我明白这是一个大问题：你想按主题对消息进行分类。你也想删除重复项。

删除重复是（相对）容易。要删除“接近”的重复项，您可以先从数据中删除不感兴趣的部分。您可以先删除大小写和标点符号。你也可以删除最常用的单词。然后，您可以将结果消息添加到布隆过滤器。散列对于Twitter来说不够好，因为散列的消息不会比完整的消息小得多。你最终会得到一个不适合内存的散列。这就是为什么你会使用布隆过滤器。它可能必须是非常大的Bloom过滤器，但它仍然会比散列表更小。

另一部分是一个困难的分类问题。你可能不想自己写这个部分。有许多库和程序可用于分类，但可能很难找到适合您需求的库和程序。 Vowpal Wabbit项目就是一个例子，它是一种用于分类的快速在线算法。但是，它一次只能用于一个类别。对于多个类别，您必须运行多个副本并分别进行培训。

识别语言听起来不那么困难。不要试图做一些像“训练”这样聪明的事情，而应该将每种语言中最常见的词语放在词典中。对于每条消息，请使用词语出现频率最高的语言。

如果你想让算法自己拿出类别，祝你好运。

Answer 2

我真的不知道，如果我回答你的主要问题，但你可以通过计算它们之间的Levenshtein distance确定两个消息的相似性。您可以将其视为两个字符串之间的“编辑差异”（I.E.，需要对一个字符进行多少编辑，然后将其转换为另一个字符）。

Answer 3

你好，我们已经使用api.cortical.io功能创建了一个非常相似的演示。 您可以在那里创建每条推文的语义指纹。 （您也可以提取最顶级的关键字或一些类似的词语，这些词语并不需要真正成为推文的一部分）。 我们使用指纹根据内容过滤Twitter流。 在twistiller.com你可以看到结果。针对四个不同的主题区域监视公众1％的Twitter流。