6

Twitter's Trending Topics often consist of more than just one word. But for composed terms there are often different ways of spelling, e.g.:

"Half Blood Prince" / "Half-Blood Prince"

To find all updates mentioning a Trending Topic, you need all the ways of spelling. Twitter does this:

Twitter's Trending Topics Admin

You have the topic name on the left and the different ways of spellings on the right. Do you think this is done manually or automatically? Is it possible to do this automatically? If yes: How?

I hope you can help me. Thanks in advance!

4

7 回答 7

7

您基本上想要的是找到两个字符串之间的相似性。

我认为Soundex算法是您正在寻找的。它可用于根据它们的声音比较字符串。或如 wiki 所述：

Soundex 是一种语音算法，用于按声音索引名称，如英语发音。目标是将同音异义词编码为相同的表示形式，以便尽管拼写存在细微差异，但仍可以匹配它们。

和：

使用这个算法[编辑：即用一个字母和三个数字“评价”单词]，“罗伯特”和“鲁珀特”都返回相同的字符串“R163”，而“鲁宾”产生“R150”。“Ashcraft”产生“A261”。

还有Levenshtein距离。

祝你好运。

于 2009-07-29T22:50:52.810 回答
6

我将尝试根据 Broken Link 的评论回答我自己的问题（谢谢你）：

您已经从文档数据库中提取了由 1 到 3 个单词组成的短语。在这些提取的短语中，有以下短语：

  • 混血王子
  • 混血王子
  • 混血王子

对于每个短语，您去除所有特殊字符和空格并将字符串变为小写：

$phrase = '混血王子'; $phrase = preg_replace('/[^az]/i', '', $phrase); $phrase = strtolower($phrase); // 结果是“混血王子”

完成此操作后，所有 3 个短语（见上文）都有一个共同的拼写：

  • 混血王子 => 混血王子
  • 混血王子 => 混血王子
  • 混血王子 => 混血王子

所以“混血王子”是父短语。您将普通短语和父短语都插入到数据库中。

要显示类似 Twitter 的“热门话题管理员”，请执行以下操作：

// first select the top 10 parent phrases
$sql1 = "SELECT parentPhrase, COUNT(*) as cnt FROM phrases GROUP BY parentPhrase ORDER BY cnt DESC LIMIT 0, 10";
$sql2 = mysql_query($sql1);
while ($sql3 = mysql_fetch_assoc($sql2)) {
    $parentPhrase = $sql3['parentPhrase'];
    $childPhrases = array(); // set up an array for the child phrases
    $fifthPart = round($sql3['cnt']*0.2);
    // now select all child phrases which make 20% of the parent phrase or more
    $sql4 = "SELECT phrase FROM phrases WHERE parentPhrase = '".$sql3['parentPhrase']."' GROUP BY phrase HAVING COUNT(*) >= ".$fifthPart;
    $sql5 = mysql_query($sql4);
    while ($sql6 = mysql_fetch_assoc($sql5)) {
        $childPhrases[] = $sql3['phrase'];
    }
    // now you have the parent phrase which is on the left side of the arrow in $parentPhrase
    // and all child phrases which are on the right side of the arrow in $childPhrases
}

这就是你的想法吗，断链？这行得通吗？

于 2009-08-06T23:09:43.837 回答
3

有很多方法可以做到这一点。一篇关于谷歌风格“你的意思是”检查的直截了当的文章是一个很好的阅读关于如何实现这一点的想法。由谷歌研究主管彼得·诺维格撰写。

http://norvig.com/spell-correct.html

于 2009-08-06T02:36:16.453 回答
1

“anderstornvig”提到了 Levenshtein/edit 距离，这是一个好主意，但不太合适，因为某些排列比其他排列更重要。问题似乎在于，当我们确定哪些差异“显着”和哪些“无关紧要”时，我们使用了大量特定领域的知识。例如，我们知道“混血王子”中的连字符很重要，但“Firefox 3”中的数字很重要。

出于这个原因，您可能会考虑自定义一个简单的指标，例如 Levenshtein。添加参数，让您自定义哪些类型的差异是重要的，哪些类型是不重要的。

特别是，Levenshtein 计算了将一个字符串转换为另一个字符串所需的“编辑”次数（即插入、删除和替换）。实际上，它对每个编辑的权重都相同。您可以编写一个以不同方式对某些编辑进行加权的实现。例如，将“-”更改为“”应该具有非常低的权重（表示不重要）。将“3”更改为“2”，当数字单独时，应该具有非常高的权重（表示高度重要性）。

通过参数化计算，您为不断改进算法创造了一条途径。构建一个初始配置并在一些测试数据上运行它。找到指标薄弱的地方——例如，它合并了你认为应该分开的两个术语——并修改参数化，直到你满意为止。

这样，您可以使用特定领域的知识来训练您的算法。

于 2009-08-06T23:00:58.050 回答
1

假设趋势主题是通过计算生成的，那么在 Twitter 上执行此操作的确切算法将很难猜测。它很可能是高度机密和专利的（就像专利算法听起来一样可怕）。

我觉得有理由相信他们会使用某种自然语言算法。根据具体情况，它们通常在计算上执行起来非常繁重，并且只会在某种程度上做你想做的事情。

关于这个主题的一个明显有用的阅读来自 wiki：

祝你好运。

于 2009-08-02T14:01:52.007 回答
1

他们很可能有一些自动系统来建议可能的组合候选者，然后人类做出最终选择来组合它们。可能有一些它们会自动组合。

  • 您删除空格和其他标点符号的建议是一个很好的建议。他们很可能会自动组合仅在标点符号或空格上有所不同的事物。
  • 复数与单数：寻找这些差异很容易自动化，并且会产生可能的组合候选者。
  • 常见拼写错误 - 有常见拼写错误的数据库。他们甚至可能依赖 Google API 来提供拼写建议（我认为他们公开了这一点）。
  • Soundex（或类似的）是查找拼写错误的好方法，但它需要首先通过上述两个过滤器（删除空格、标点符号和复数），然后如果它们相同，则很可能需要人工进行调用. 但是，如果您可以提供一个图形表示来显示具有相同或相似 soundex 的聚类，那么您真的可以让这部分变得简单。当集群开始出现和趋势时，您可以自动发送通知（他们实际上只关心趋势主题，所以即使组合的集群没有趋势，他们也可以等待检查它。）

你真正需要一个人介入的地方是有常见的昵称。像 Michael Jackson、MJ、Michael 等。或者 MacDonalds、McD、Micky-D's 等。然后在技术方面你有 Visual Studio、VS2008、VS 等或 StackOverflow、SO 等。然后是 C#、C-Sharp、 C#.NET 都是一样的，但是 C 和 C++ 是不同的。

所以它必须是一个组合。它可能依赖于基于先前分析或其他来源的已知变化和组合的数据库，但该数据库将由编辑定期维护。

于 2009-08-08T01:03:33.450 回答
0

我记得当 MJ 去世时，推特手动返回并修复主题以指向他去世的推文。如今，要求计算机自动执行此类操作将是很多事情，尽管可以松散地完成。

于 2009-07-29T22:49:14.827 回答